# Consequences of $SAT \in BQP$

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?
• @Walther: I notice you updated the question to add the bit about an exponential speed-up, but frankly the distinction between polynomial and exponential speed-ups is somewhat artificial, and so I don't really see this affecting physics in any way. – Joe Fitzsimons Apr 18 '11 at 15:18
• @Joe: I've added that bit only to clarify what I had in mind when I asked the question (i.e. that quantum would seem more powerful than classical in the sense that the former would solve NP-complete problems in polynomial time, while the latter not yet or never). But now I see that if someone reads the current version of the question and then reads your answer, he may be misguided and think that a sentence in your answer is wrong: that's why I'm going to remove that bit. – Giorgio Camerani Apr 18 '11 at 16:52
• Sorry, I didn't mean to suggest that you reword it. – Joe Fitzsimons Apr 18 '11 at 16:57
• @Joe: No, don't worry! ;-) Really, I don't want that the question and its answers are misaligned: it would be confusing for the readers and unjust for those people who answered. – Giorgio Camerani Apr 18 '11 at 17:08
• – Kaveh Apr 20 '11 at 6:46

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.

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.

• Sure, possibility #2 isn't a laughable possibility (even, I must emphasize, in the hypothetical situation that NPBQP). But your argument could also be used to argue for #1 as well. Given a choice between the three possibilities, I choose #3 because it is the most conservative possibility; but also because I think it is important to emphasize that there are in principle good physical and empirical reasons for making complexity-theoretic conjectures. – Niel de Beaudrap Apr 18 '11 at 15:11
• @Neil: I really disagree. I don't see it as at all conservative (rather the opposite) to assert quantum mechanics is likely wrong because quantum computers would be powerful. There is simply no evidence for 1, which is why the argument wouldn't apply. There is enormous evidence that quantum computation is, at least in principle, possible. – Joe Fitzsimons Apr 18 '11 at 15:15
• @Joe: Sure, our models of QC are excellent abstractions of QM (which itself is a pretty good theory) as far as we can tell. It also admits reasonable error bounds in principle, and hope for composable error correction. But it's hard enough to get all the pieces into place to get noiseless operations, isn't it? In any case, we're talking counterfactuals here, and the condition here is a doozy — can you tell me that a result such as NPBQP wouldn't give you a moment's pause to think that, maybe, there's a big catch waiting for QC somewhere? – Niel de Beaudrap Apr 18 '11 at 15:31
• @Neil: Yes, it is certainly tricky to build a QC, but what you are suggesting seems to be a no-go theorem. I can't see how you could possibly have such a theorem without significantly (and unnaturally in my opinion) altering quantum mechanics. I can tell you that NP $\subseteq$ BQP would not for a minute make me doubt the correctness of quantum mechanics, and I do not see how we can have a situation where QM is correct but there is a no-go theorem for QCs. – Joe Fitzsimons Apr 18 '11 at 15:37
• @Neil: Actually, 2 seems to be the case now. I really doubt BQP = P, so quantum circuits can likely not be simulated efficiently classically. Yet there is every indication that we can in fact build quantum computers (though it's tricky!). – Joe Fitzsimons Apr 18 '11 at 16:17