On NP in BQP

In the wake of a misleading Economist article on the D-Wave quantum computer, Scott argues why he believes quantum computers cannot efficiently solve NP-complete problems, i.e., that the complexity class BQP does not contain NP. Let's look at that question purely from a computational complexity viewpoint.

Ideally we would like a mathematical proof that NP ⊄ BQP. But any such proof would imply P≠NP, one of the great open problems in mathematics.

Moving on, complexity theorists give evidence that a statement Q is false by a "Pigs Can Fly" argument, by showing that Q implies something else we don't believe. For example

• If there are sparse NP-complete sets then P=NP.
• If NP has efficient probabilistic algorithms (NP⊆BPP), then the polynomial-time hierarchy collapses.
• If good pseudorandom generators don't exist then exponential time has small circuits.

But we don't have any known consequences of NP⊆BQP.

What we do have is the result of Bennett, Bernstein, Brassard, Vazirani that BQP can't solve black-box NP problems, a relativized separation of NP from BQP. Relativized results like this don't tell us whether or not a statement is true, just that any proof that NP in BQP would require nonrelativizing techniques. So the sentence from the Economist article

In principle, by putting a set of entangled qubits into a suitably tuned magnetic field, the optimal solution to a given NP-complete problem can be found in one shot.

does not reflect current knowledge.

Can one have a nonrelativizing proof that NP is in BQP? We do have precedent. My very first theorem gave a relativized world where co-NP does not have interactive proof systems. We published the result in a 1988 paper Are there interactive protocols for co-NP languages? and we conjectured the answer was no. We were wrong.

But so far interactive proof and related systems have been the only source of reasonable nonrelativized proof techniques that we have seen in computational complexity and we haven't had any success using this algebraic structure of arithmetized satisfiability to make efficient quantum algorithms for NP problems.

I do conjecture that NP ⊄ BQP and most computational complexity theorists would agree with me. But until we see some negative consequences of NP in BQP, computational complexity theory has so far failed to give any real evidence that NP ⊄ BQP. We believe that NP ⊄ BQP for the same reason we believe that there are no probabilistic polynomial-time algorithms for Factoring—despite considerable effort, failure to find any algorithmic techniques that might solve the problem.