Consequences of $SAT \in BQP$

Question

As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far:

1. Quantum computers are not known to solve NP-complete problems in polynomial time.
2. "Quantum magic won't be enough" (Bennett et al. 1997): if you throw away the problem structure, and just consider the space of $2^n$ possible solutions, then even a quantum computer needs about $\sqrt{2^n}$ steps to find the correct one (using Grover's algorithm)
3. If a quantum polynomial time algorithm for a NP-complete problem is ever found, it must exploit the problem structure in some way (otherwise bullett 2 would be contradicted).

I've some (basic) questions that no one seems to have asked so far on this site (maybe because they are basic). Suppose someone finds a bounded error quantum polynomial time algorithm for $SAT$ (or any other NP-complete problem), thus placing $SAT$ in $BQP$, and implying $NP \subseteq BQP$.

Questions

1. Which would be the theoretical consequences of such a discovery? How would the overall picture of complexity classes be affected? Which classes would become equal to which others?
2. A result like that would seem to suggest that quantum computers had an inherently superior power than classical computers. Which would be the consequences of a result like that on physics? Would it emanate some light on any open problem in physics? Would physics be changed after a similar result? Would the law of physics as we know them be affected?
3. The possibility (or not) to exploit the problem structure in a general enough (i.e. specific-instance independent) manner seems to be the very core of the P = NP question. Now if a bounded error polynomial time quantum algorithm for $SAT$ is found, and it must exploit the problem structure, wouldn't its structure-exploitation-strategy be usable also in the classical scenario? Is there any evidence indicating that such a structure-exploitation may be possible for quantum computers, while remaining impossible for classical ones?

Answer 1

I'm not going to try to answer the first question, as someone like Scott Aaronson, Peter Shor or John Watrous can no doubt give you a far more comprehensive answer on that front.

As regards question 2, it is important to note that quantum computers are in fact more powerful than classical computers in many instances:

1. There is a rather generic polynomial speed-up gained by quantum computers over classical computers in quite a number of problems. From a complexity point of view, this is perhaps somewhat less interesting than an exponential speed-up, but is something that we can actually prove.
2. Quantum communication complexity can often vary dramatically from classical communications complexity for the same problem. Again, this is something that can be proven (see for example the Mermin-GHZ game).
3. Quantum queries to oracles are very often far more powerful than classical queries to the same oracle (see for example the Deutsch-Josza algorithm).

With this is mind, it is already known that quantum computers are fundamentally more powerful than classical computers. I think I would be correct in saying that the majority of physicists who work on such things would already assume that it is not possible to find a classical algorithm to efficiently simulate every quantum system, and so while a result showing that NP was contained in BQP would certainly be surprising, it would not be particularly likely to provide a breakthrough in the understanding of any particular physical phenomenon. Rather it would provide somewhat stronger evidence that quantum physics is hard to simulate.

There is no fundamental physics that is dependent on the computational complexity of simulating it, so finding an efficient quantum algorithm for an NP-complete problem would not have fundamental consequences for the correctness of our current understanding of how the universe functions (though I am inclined to agree with Scott Aaronson's suggestion that it is interesting to see if you could have physical laws emerge from computational assumptions).

It is extremely tempting to say that this would have consequences for adiabatic evolution of quantum systems (and I guess you might get an answer or two suggesting that), etc., but this would be incorrect, as they are governed by a specific physical process, and so showing that it is in principle possible to solve SAT in polynomial time on a quantum computer, wouldn't say anything about their specific evolution.

As regards your last question, we already have examples where problem structure is exploited to yield a polynomial quantum algorithm, but which do not lead to such a classical algorithm (factoring for example). So, as far as our current understanding goes, a problem with a structure exploitable to yield a polynomial time quantum algorithm does not imply that the structure is exploitable to yield a classical polynomial time algorithm.

Answer 2

Scott Aaronson was often fond of pointing out (and probably still is fond of pointing out, assuming he hasn't gotten tired of doing so) that physical processes do not always find the global minimum of an energy landscape. In particular, if you were to formulate an instance of an NP-complete optmization problem as an energy-minimisation problem for a physical system, there is no reason — either theoretical or empirical — to believe that such a physical system will "relax" after some time to a solution of the problem (i.e.  an energy configuration which is a global minimum). It will more likely relax to a local minumum: one for which slightly different configurations require more energy, but where a substantially different configuration may have less energy.

So, while proving NP ⊆ BQP would be a triumph of the first order — for all complexity theorists, not just for quantum computation theorists — it would suggest that there is a whole new theory of "physical" models of computation waiting to be discovered. Why? Well, models of computation can be construed as models of physics (albeit highly specialized ones): namely, what computational resources are physically reasonable. One of the 'slogans' of quantum computation is that Nature isn't classical, [darn] it^† — so unless you can simulate quantum mechanics on a classical computer, what you can physically compute efficiently is almost certainly more powerful than P. And yet, we have evidence that it is less powerful than NP; so it would have to be less powerful than BQP as well, if it so happened that NP ⊆ BQP.

So, a proof of NP ⊆ BQP would present us with a trilemma: either

1. quantum circuits can be simulated efficiently on a classical computer, proving NP ⊆ BQP ⊆ P, thereby surpassing every theorist's wildest dreams or nightmares;
2. quantum circuits can't be simulated on a classical computer, but scalable quantum computers can be built to solve problems in NP, giving rise to truly explosive interest in quantum computing and ensuring that experimental physicists have career security for the forseeable future;
3. there is another model of computation waiting to be discovered, intermediate between P and BQP in power, which describes (or rather, better approximates) what is efficiently physically computable.

I suspect that the smart money would be on #3, as fun as either #1 or #2 would be from an academic perspective.

^† With apologies to Feynman, who I suspect did not often mince his curses.