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:

Quantum computers are not known to solve NP-complete problems in polynomial time.
"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)
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

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?

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?

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
@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

Joe Fitzsimons · Accepted Answer · 2011-04-18T13:40:41.497

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:

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.
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).
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.

Jozsa is mispelled ('Josza'). – Dávid Horváth Jan 13 '21 at 23:04 — Dávid Horváth, Jan 13 '21 at 23:04

Niel de Beaudrap · Answer 2 · 2011-04-18T19:37:42.490

20

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

quantum circuits can be simulated efficiently on a classical computer, proving NP ⊆ BQP ⊆ P, thereby surpassing every theorist's wildest dreams or nightmares;
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;
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.

edited Apr 18 '11 at 19:37

answered Apr 18 '11 at 14:51

Niel de Beaudrap

8,821
31
70

Why not 2? Surely proving NP is in BQP does not make a quantum computer any less consistent with the laws of physics, and hence could hardly have an impact on whether or not it is realisable. – Joe Fitzsimons Apr 18 '11 at 15:05
1

Sure, possibility #2 isn't a laughable possibility (even, I must emphasize, in the hypothetical situation that NP ⊆ BQP). 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
3

@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
1

@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 NP ⊆ BQP 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
2

@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
3

@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
1

@Joe: So long as we are speculating on what would happen if we could prove NP ⊆ BQP, without specifying what form the proof might take, let me make a further vague speculation. Perhaps BQP would be sufficiently sensitive to differences in quantum states (to distinguish between YES/NO instances of NP problems) that it would entail a crippling sensitivity to coupling with the environment in any model strong enough to contain NP. This is, of course, the standard skeptic "something will go wrong somehow" argument; but supplemented with the hypothesis NP ⊆ BQP. – Niel de Beaudrap Apr 18 '11 at 17:20
1

@Neil: It seems impossible to reconcile such a view with the threshold theorem without introducing a non-linearity (which would likely make the model more computationally powerful) or breaking QM in a very unnatural way. – Joe Fitzsimons Apr 18 '11 at 21:45
1

@Joe: It isn't impossible to reconcile my view with the hypothesis that it may be difficult to achieve the threshold error rate for long times, e.g. because the bath from which you draw ancillas, cool detectors, or whatnot, keeps getting hotter. Anyway, I didn't mean to present a serious skeptical argument against QC. Whether or not NP ⊆ BQP holds (cough), probably the easiest way to see if we can build scalable quantum computers is to just try to build one. But *any* theorem is about an idealized system, and one must still approximate the ideal for it to be of any use. – Niel de Beaudrap Apr 19 '11 at 07:51
Joe's comments have garnered a number of up-votes, and my answer one down-vote. But Joe's arguments are no different from the usual arguments against QC or QM skeptics. I am not such a skeptic; only a realist who acknowledges that theorems are not about physical systems, but idealizations of them. Take a look at the caveats in the final paragraph of Gottesman's 2009 eprint. My position is that a result such as NP ⊆ BQP would warrant renewed caution, as it would be a surprising feature of QM. I hope that new response can be to this position. – Niel de Beaudrap Apr 19 '11 at 10:15
@Neil: That is a very specific argument for why it might be hard to build a quantum computer, not why it is impossible. But this seems to be more along the lines of suggessting that quantum computers are possible, but that we (as a species) may never be able to make them. In such a case, a complexity argument would seem to mean less not more. I understand that you are playing the skeptic, rather than necessarily being one, but I still cannot accept the argument you are putting forward. (to be continued) – Joe Fitzsimons Apr 19 '11 at 14:11
(continued) To me it seems either you can build quantum computers or there is some feature of physics which prevents them in principle. (Technically I suppose this could be undecidable, but that is not a possibility I consider to be at all likely). We know quantum computation is entirely consistent with quantum mechanics, and so any no-go theorem would necessarily modify quantum mechanics. To me, it seems far far more likely that NP $\subseteq$ BQP than quantum mechanics than that quantum mechanics is incorrect in such a way as to allow a no-go theorem for QCs (though I doubt both). – Joe Fitzsimons Apr 19 '11 at 14:19
@Joe: So, you disagree even in principle that there could under any conditions be a high-level obstacle, akin to the second law of thermodynamics, which could ever pose an unsuperable statistical obstacle to the construction of quantum computers? The spontaneous descrambling of eggs is certainly possible under Newtonian mechanics, but we recognize that the effective behaviour of systems makes this an event ruled out in practise. I am saying that I would find the existence of an analogous principle, ruling out universal QC, tremendously less surprising if it we found out that NP ⊆ BQP. – Niel de Beaudrap Apr 19 '11 at 15:07
@Neil: Yes, I don't see how such a situation could be consistent with our current understanding of physics. However, even if I believed it was possible, I still doubt that I would find it more likely that it is the case than that NP $\subseteq$ BQP. As a side note you need to be very careful with thermodynamical arguments (spin echo is essentially unscrambling eggs). – Joe Fitzsimons Apr 19 '11 at 15:21
@Joe: well, NP ⊆ BQP is also not consistent with most people's understanding of physics (for those who might care to consider the question). As for spin echo, isn't the effect more or less due to an approximately synchronized precession, and so more like resonant harmonic motion than diffusion (and so not very much like scrambling+unscrambling eggs)? Anyway, it's a bit tangential. – Niel de Beaudrap Apr 19 '11 at 15:38
@Neil: NP $\subseteq$ BQP is not really a question about our understanding of physics (we do not even know that NP $\neq$ P). – Joe Fitzsimons Apr 19 '11 at 16:18
@Joe: I'm not sure how the lack of knowledge about the latter conjecture implies anything about the "physicality", or lack thereof, of the former. – Niel de Beaudrap Apr 19 '11 at 17:42
@Neil: but if P=NP, then NP $\subseteq$ BQP, but this could no longer be a reason to believe that scalable quantum computers could be built, since we would already have scalable machines for NP-Complete problems. – Joe Fitzsimons Apr 19 '11 at 21:19
@Joe: if P = NP, then is an even more surprising statement about physics. Theoretical computer science may be a branch of mathematics, but no branch of mathematics which concerns itself with "feasible" computation can lay claim to "purity", or remoteness from physical processes. When I say that models of computation can be construed as models of physics, I mean it. We have ample evidence that P is a physically feasible model of computation; P = NP would mean that solving NP problems requires resources and physical conditions which are relatively easy to come by. – Niel de Beaudrap Apr 20 '11 at 06:17
@Neil: With a finite observable universe, no assymptotic statements of this kind are truely physical. It is entirely possible to have P=NP, but for the best scaling achievable to be polynomial, simply by having a big enough constant in front of the polynomial, and having an exponential with a much smaller constant, since the is some maximum possible input size. With this in mind, I really don't see these as being direct statements about physics, but rather an abstraction which may not have physical significance.But I can see we are destined to disagree, so maybe it's not worth continuing here. – Joe Fitzsimons Apr 20 '11 at 14:03
@Joe: it is also impossible to determine whether QM holds to arbitrary precision either, or for all energies, etc. *All* abstractions are in principle approximative models: the only question is how useful the approximation is. Asymptotic analysis gives big-picture information about resource usage, and is correlated to the actual solution process for an algorithm, just as studying ground-states of systems (despite T=0K being unachievable) gives us a charicature of the properties of systems at small but finite temperatures. In any case, I agree that this is not too important here. – Niel de Beaudrap Apr 20 '11 at 14:18
@Neil: There is a big difference here. Quantum mechanics is conjectured to accurately describe all of nature (both the regimes it has been tested in and those it hasn't). Conjecturing that you cannot build a machine to solve any NP problem efficiently is almost tautological, since there are instances that are simply to large to encode in the observable universe. We can't even make that statement about P, for exactly the same reason. As such, P=NP would not be a statement about physics, since physics only cares up to some maximum input size. – Joe Fitzsimons Apr 20 '11 at 15:00
(continued) To clarify what I mean, consider the case where there exists an algorithm for all instances of a given problem which can be expressed in less than N bits which takes time at most $n^2$, but in general the problem requires exponential time. Then if N is much greater than what can ever be encoded in the universe, the fact that the worst case takes exponential time is somewhat irrelevant to physics. – Joe Fitzsimons Apr 20 '11 at 15:06
@Joe: The conjecture that you cannot build a machine to "solve an arbitrary NP problem" is short-hand for saying that you can't bound the energy/time-requirements (for example) to anything which scales polynomially in the system size. The only reasons why we don't talk about the exact requirements is because (a) it depends on the exact implementation, and (b) for the theoretical study, we just don't care. But if we can talk about heat capacities or equilibration times (other instances where we talk about time/energy requirements for finite systems), why not scaling of run-times? – Niel de Beaudrap Apr 20 '11 at 15:20
@Neil: I don't think we are going to get anywhere here, and I suspect anyone following the comments will have by now lost interest. Perhaps this is an argument best saved for the next time we meet in person. – Joe Fitzsimons Apr 20 '11 at 15:31
@Joe: Quantum mechanics is conjectured to accurately describe natural phenomena only in regimes where general relativistic effects are negligible. An unified 'theory of everything' may or may not involve modifications to quantum mechanics that prevent the feasibility of quantum computation as we know it on large numbers of qubits, which may or may not be a practical size. Anyway, I don't think this is particularly related to the $NP \subseteq BQP$ issue. – Antonio Valerio Miceli-Barone Apr 20 '11 at 23:22
1

@Antonio: Not so. It is far more widely believed that GR breaks in the quantum gravity limit than that quantum mechanics breaks. But seriously, this is going way off topic... – Joe Fitzsimons Apr 20 '11 at 23:26
@Joe: IIUC, the notion that quantum mechanics holds at all scales is the assumption under which string theorists work, however this is not an hypothesis really justified from empirical evidence. Other have speculated, for instance, that quantum mechanics breaks as the energy separation between superposed eigenstates approaches Planck energy. Anyway, I agree that this discussion is off topic so perhaps we should drop it. – Antonio Valerio Miceli-Barone Apr 21 '11 at 09:33

Consequences of $SAT \in BQP$

2 Answers2

Linked