<p>The folklore answer is that factoring is "structured" in a way that general NP-complete problems aren't, and this is why we have only been able to find quantum advantage for intermediate problems.</p>

<p>Arguably a simpler version of your question is to look not at computational complexity, but at the query complexity of boolean functions.  Here we can say some things provably, such as the fact that superpolynomial speedups are possible only for <em>partial functions</em> (proved in <a href="http://arxiv.org/abs/quant-ph/9802049">http://arxiv.org/abs/quant-ph/9802049</a>) and not for functions that are symmetric in their inputs and outputs (proved in <a href="http://arxiv.org/abs/0911.0996">http://arxiv.org/abs/0911.0996</a>).</p>

<p>These results do not directly shed light on the BQP vs NP question, but are I think meaningful steps towards determining where there is quantum advantage.</p>

CC BY-SA 4.0
2024-12-03T01:26:35.357Z
It's great to see the greats in this thread...
QuestionEverything
CC BY-SA 3.0
2011-06-27T16:41:54.960Z
2011-06-27T16:41:54.960Z
Aram Harrow
<p>Graph isomorphism is not known to be in BQP. There has been a lot of work done on trying to put it in. A very intriguing observation is that graph isomorphism could be solved if quantum computers could solve the non-abelian hidden subgroup problem for the symmetric group (factoring and discrete log are solved by using the abelian hidden subgroup problem, which in turn is solved by applying the quantum Fourier transform on abelian groups). </p>

<p>One of the ways people have tried to solve graph isomorphism was by applying the quantum Fourier transform for non-abelian groups. There are algorithms for the quantum Fourier transform for many non-abelian groups, including the symmetric group. Unfortunately, it appears that it may not be possible to use the quantum Fourier transform for the symmetric group to solve graph isomorphism; there have been quite a few papers written about this which show that it doesn't work, given various assumptions on the structure of the algorithm. These papers are probably what you find when you google.</p>

CC BY-SA 2.5
2010-12-20T18:44:38.320Z
I guess the problems I asked about fall into category 2 (QFT/HSP) in the MathOverflow question, and that's the key commonality. Thanks!
Huck Bennett
CC BY-SA 2.5
2010-12-21T23:39:15.240Z
This is a nice survey on everything that Peter said http://arxiv.org/abs/0812.0380
Marcos Villagra
CC BY-SA 3.0
2017-10-09T03:55:44.390Z
With Prof. Babai's result on Graph isomorphism, what is about the complexity of Quantum computer algorithm on GI?
XL _At_Here_There
CC BY-SA 3.0
2017-10-09T11:14:55.120Z
We don't have any quantum algorithms that do better than classical algorithms at this point.
Peter Shor 
CC BY-SA 2.5
2010-12-20T13:07:01.773Z
2010-12-20T13:17:37.140Z
2010-12-20T13:17:37.140Z
Peter Shor 
<p>Peter Shor <a href="http://arxiv.org/abs/quant-ph/9508027v2">showed</a> that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) only yields a quadratic improvement over the classical algorithm, hinting that NP-complete problems are still intractable on quantum computers. As Arora and Barak point out, there's also a problem in BQP that is not known to be in NP, leading to the conjecture that the two classes are incomparable.</p>

<p>Is there any knowledge/conjecture as to why these NP-intermediate problems are in BQP, but why SAT (as far as we know) isn't? Do other NP-intermediate problems follow this trend? In particular, is graph isomorphism in BQP? (this one doesn't google well).</p>

CC BY-SA 2.5
2010-12-20T13:11:23.390Z
Take a look at [this Math Overflow question](http://mathoverflow.net/questions/33597/are-there-any-known-quantum-algorithms-that-clearly-fall-outside-a-few-narrow-cla) and the [quantum algorithms zoo](http://www.its.caltech.edu/~sjordan/zoo.html).
Peter Shor 
CC BY-SA 2.5
2010-12-20T15:01:23.160Z
I suppose I should address the question as to why certain NP-intermediate problems are in BQP, and others are not known to be. The only thing I can really say confidently is that the problems known to be in BQP fall into various classes, and within each class, generally the same techniques are used in the solution. See the two links in my previous comment
Peter Shor 
CC BY-SA 2.5
2010-12-20T16:09:38.123Z
Any BQP-complete problem serves as an example of a problem in BQP that is not known to be in NP.
Robin Kothari
CC BY-SA 2.5
2010-12-20T18:31:19.163Z
Regarding a quantum graph isomorphism algorithm: http://tuvalu.santafe.edu/~moore/qip-slides.pdf.
Huck Bennett
CC BY-SA 2.5
2011-01-19T09:50:01.630Z
BQP-complete? Can someone cite a BQP-complete problem please?
Cem Say
CC BY-SA 2.5
2011-01-20T03:10:38.970Z
@Cem Look at Peter's "quantum algorithms zoo" link. There's a section on "Approximation and BQP-complete Problems" which lists a few examples.
Huck Bennett
CC BY-SA 3.0
2011-06-28T02:42:20.800Z
@Aram: I've rolled back your edit and modified the question slightly to clarify. I meant that there's a problem in BQP not *known* to be in NP (the Recursive Fourier Sampling problem, not even known to be in PH, p.230 A+B)
Huck Bennett
CC BY-SA 4.0
2019-03-21T17:23:48.837Z
The current "quantum algorithms zoo" link in the first comment (http://www.its.caltech.edu/~sjordan/zoo.html) is broken. I believe that the currently correct link is : http://quantumalgorithmzoo.org/. Can someone with higher reputation please fix this? Thanks in advance!
Jesse Stern
<cc.complexity-theory><quantum-computing><np><np-intermediate>
NP-intermediate problems with efficient quantum solutions
Huck Bennett
# NP-intermediate problems with efficient quantum solutions

(Asked by: username_0 on 2010-12-20)

username_1[showed](http://arxiv.org/abs/quant-ph/9508027v2) that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) only yields a quadratic improvement over the classical algorithm, hinting that NP-complete problems are still intractable on quantum computers. As Arora and Barak point out, there's also a problem in BQP that is not known to be in NP, leading to the conjecture that the two classes are incomparable.

Is there any knowledge/conjecture as to why these NP-intermediate problems are in BQP, but why SAT (as far as we know) isn't? Do other NP-intermediate problems follow this trend? In particular, is graph isomorphism in BQP? (this one doesn't google well).

**Tags:** cc.complexity-theory, quantum-computing, np, np-intermediate

> **Comments:**
> **username_1**: Take a look at [this Math Overflow question](http://mathoverflow.net/questions/33597/are-there-any-known-quantum-algorithms-that-clearly-fall-outside-a-few-narrow-cla) and the [quantum algorithms zoo](http://www.its.caltech.edu/~sjordan/zoo.html).  
> **username_1**: I suppose I should address the question as to why certain NP-intermediate problems are in BQP, and others are not known to be. The only thing I can really say confidently is that the problems known to be in BQP fall into various classes, and within each class, generally the same techniques are used in the solution. See the two links in my previous comment  
> **username_2**: Any BQP-complete problem serves as an example of a problem in BQP that is not known to be in NP.  
> **username_0**: Regarding a quantum graph isomorphism algorithm: http://tuvalu.santafe.edu/~moore/qip-slides.pdf.  
> **username_3**: BQP-complete? Can someone cite a BQP-complete problem please?  
> **username_0**: @Cem Look at Peter's "quantum algorithms zoo" link. There's a section on "Approximation and BQP-complete Problems" which lists a few examples.  
> **username_0**: @Aram: I've rolled back your edit and modified the question slightly to clarify. I meant that there's a problem in BQP not *known* to be in NP (the Recursive Fourier Sampling problem, not even known to be in PH, p.230 A+B)  
> **username_4**: The current "quantum algorithms zoo" link in the first comment (http://www.its.caltech.edu/~sjordan/zoo.html) is broken. I believe that the currently correct link is : http://quantumalgorithmzoo.org/. Can someone with higher reputation please fix this? Thanks in advance!  

---

## 2 answers

### Answer by username_1 on 2010-12-20. Score: 38 | Accepted answer

Graph isomorphism is not known to be in BQP. There has been a lot of work done on trying to put it in. A very intriguing observation is that graph isomorphism could be solved if quantum computers could solve the non-abelian hidden subgroup problem for the symmetric group (factoring and discrete log are solved by using the abelian hidden subgroup problem, which in turn is solved by applying the quantum Fourier transform on abelian groups).

One of the ways people have tried to solve graph isomorphism was by applying the quantum Fourier transform for non-abelian groups. There are algorithms for the quantum Fourier transform for many non-abelian groups, including the symmetric group. Unfortunately, it appears that it may not be possible to use the quantum Fourier transform for the symmetric group to solve graph isomorphism; there have been quite a few papers written about this which show that it doesn't work, given various assumptions on the structure of the algorithm. These papers are probably what you find when you google.

> **Comments:**
> **username_0**: I guess the problems I asked about fall into category 2 (QFT/HSP) in the MathOverflow question, and that's the key commonality. Thanks!  
> **username_7**: This is a nice survey on everything that Peter said http://arxiv.org/abs/0812.0380  
> **username_8**: With Prof. Babai's result on Graph isomorphism, what is about the complexity of Quantum computer algorithm on GI?  
> **username_1**: We don't have any quantum algorithms that do better than classical algorithms at this point.  

---

### Answer by username_5 on 2011-06-27. Score: 24

The folklore answer is that factoring is "structured" in a way that general NP-complete problems aren't, and this is why we have only been able to find quantum advantage for intermediate problems.

Arguably a simpler version of your question is to look not at computational complexity, but at the query complexity of boolean functions. Here we can say some things provably, such as the fact that superpolynomial speedups are possible only for *partial functions* (proved in <http://arxiv.org/abs/quant-ph/9802049>) and not for functions that are symmetric in their inputs and outputs (proved in <http://arxiv.org/abs/0911.0996>).

These results do not directly shed light on the BQP vs NP question, but are I think meaningful steps towards determining where there is quantum advantage.

> **Comments:**
> **username_6**: It's great to see the greats in this thread...  

---

