# Quantum Computing Complexity?

After reading a recent post on Church's Thesis, I ran into Turing-Church's Strong Thesis, that may be potentially disproven by advances in Quantum Computing. Does anyone know of a good resource that gets into the potential of quantum computing on complexity theory? And how complexity calculations would be done in that environment?

I am also not well read in complexity theory in general, so I may have made an ill-posed question here.

-

This is a very active field of current research. The book "Quantum Computation and Quantum Information", By Michael Nielsen and Ike Chuang, is one of the standard references.

Peter Shor found the original application of quantum computation to factorization, and I believe (without having full knowledge) that this still stands as one of the few instances of such an application - unfortunately, factorization is one of the few natural NP problems that are not known to be NP complete, so it may be the case that quantum computation "only" helps this particular problem (and problems trivially equivalent to it). The Wikipedia article on BQP is another useful reference.

-
Thanks Alon! Very helpful – Michael Hoffman Oct 30 '09 at 2:56
There are other cases where a quantum algorithm provides an exponential speedup over the best known classical algorithm. But the fundamental problem is that nobody knows where BQP sits... we know it is between BPP and PP (and hence PSPACE), but we can't even separate P from PSPACE, so it's really tough to pin it down more exactly than that. – Steve Flammia Oct 30 '09 at 3:47

First, Alon's summary of applications of quantum computing is not complete. What Shor's algorithm (or more precisely, Simon-Shor-Kitaev) really does is that it fully analyzes any finite abelian group in polynomial time (polynomial in log |G|), provided that inverses and the group law are available in black-box form, and elements have unique names. Thus, you can factor N by analyzing the multiplicative group of Z/N. You can analyze elliptic curves, other abelian varieties, D-modules, etc. You can find the cardinality, find orders of elements, compute discrete logarithms, etc.

There are other quantum algorithms that do black-box things that certainly look like they could be useful. What makes Shor's algorithm special is that there are lots of obvious ways to replace the black box by a "white box", i.e., by an explicit computational problem.

These algorithms provide strong evidence that the quantum polynomial time class, BQP, is larger than P, polynomial time (and BPP, randomized polynomial time).

And that is the original question about the strong Church-Turing thesis. The strong Church-Turing thesis posits that all natural models of polynomial-time computation are equivalent. At the moment, it looks like there are two natural models, P (which is conjectured to equal BPP) and BQP. As Alon says, factoring is not known to be NP-complete, but there is nothing unfortunate about that. It would surprise a lot of people if NP turned out to be a natural class, and it is a standard conjecture that BQP does not contain NP.

-
BTW, Aaronson's analysis of the Fourier checking problem provides (oracle) evidence that $\mathbf{BQP} \not \subset \mathbf{PH}$, and in particular that $\mathbf{BQP} \not \subset \mathbf{NP}$. – Steve Huntsman Oct 5 '10 at 18:53

Scott Aaronson maintains a list of references on Quantum Computing. (In the right hand side bar, you'll have to scroll down a bit.) His Scientific American article may be the lowest level introduction which doesn't actually lie to you.

-

The following paper by Watrous summarizes a lot of definitions and gives good background material. It has pictures to show the relationship to other complexity classes, too. One important recent result that isn't discussed is that quantum interactive proofs (QIP) are equivalent to PSPACE.

-
Incidentally John Watrous was part of the group that proved QIP=PSPACE. The survey also doesn't contain the containment QIP(2) in PSPACE, which was proved after the survey article. – Rune Nov 1 '09 at 13:31

If you understand classical complexity theory, the quickest way to understand all the implications of quantum complexity (without all the gory details) is to read John Watrous' survey on Quantum complexity theory.

For a pedagogical treatment of quantum computing, read a text like Nielsen and Chuang, or the other one by Laflamme/Mosca/Kaye. Then read John Watrous' survey.

For a pedagogical treatment of complexity theory, read the first few chapters of either Arora/Barak, or Goldreich's book. Then read John Watrous' survey.

Bottom line: John Watrous' survey is awesome.

-
Where can I find the survey? And thanks for the comment! – Michael Hoffman Nov 1 '09 at 14:40
DOH! It's mentioned above, nvm – Michael Hoffman Nov 1 '09 at 14:41