31
$\begingroup$

Peter Shor showed 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).

Improve this question
$\endgroup$
8
  • 6
    $\begingroup$ Take a look at this Math Overflow question and the quantum algorithms zoo. $\endgroup$
    – Peter Shor
    Dec 20, 2010 at 13:11
  • 4
    $\begingroup$ 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 $\endgroup$
    – Peter Shor
    Dec 20, 2010 at 15:01
  • 1
    $\begingroup$ Any BQP-complete problem serves as an example of a problem in BQP that is not known to be in NP. $\endgroup$
    – Robin Kothari
    Dec 20, 2010 at 16:09
  • 2
    $\begingroup$ Regarding a quantum graph isomorphism algorithm: tuvalu.santafe.edu/~moore/qip-slides.pdf. $\endgroup$
    – Huck Bennett
    Dec 20, 2010 at 18:31
  • 1
    $\begingroup$ BQP-complete? Can someone cite a BQP-complete problem please? $\endgroup$
    – Cem Say
    Jan 19, 2011 at 9:50

2 Answers 2

Reset to default
34
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I guess the problems I asked about fall into category 2 (QFT/HSP) in the MathOverflow question, and that's the key commonality. Thanks! $\endgroup$
    – Huck Bennett
    Dec 20, 2010 at 18:44
  • 10
    $\begingroup$ This is a nice survey on everything that Peter said arxiv.org/abs/0812.0380 $\endgroup$
    – Marcos Villagra
    Dec 21, 2010 at 23:39
  • $\begingroup$ With Prof. Babai's result on Graph isomorphism, what is about the complexity of Quantum computer algorithm on GI? $\endgroup$
    – XL _At_Here_There
    Oct 9, 2017 at 3:55
  • $\begingroup$ We don't have any quantum algorithms that do better than classical algorithms at this point. $\endgroup$
    – Peter Shor
    Oct 9, 2017 at 11:14
21
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.