Theoretical Computer Science
- cc.complexity-theory quantum-computing np np-intermediate
- Updated Sun, 22 May 2022 03:05:14 GMT
-
NP-intermediate problems with efficient quantum solutions
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).
Solution
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 (4)
- +1 – I guess the problems I asked about fall into category 2 (QFT/HSP) in the MathOverflow question, and that's the key commonality. Thanks! — Dec 20, 2010 at 18:44
- +0 – This is a nice survey on everything that Peter said arxiv.org/abs/0812.0380 — Dec 21, 2010 at 23:39
- +0 – With Prof. Babai's result on Graph isomorphism, what is about the complexity of Quantum computer algorithm on GI? — Oct 09, 2017 at 03:55
- +0 – We don't have any quantum algorithms that do better than classical algorithms at this point. — Oct 09, 2017 at 11:14