"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 an $\text{NP}$-complete problem is ever found, it must exploit the problem structure in some way.


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 $\text{SAT}$ (or any other $\text{NP}$-complete problem), thus placing $\text{SAT}$ in $\text{BQP}$, and implying $\text{NP} \subseteq \text{BQP}$.


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?


  • 3
    $\begingroup$ It seems that at least three different questions may be prepared starting from this one: (a) Suppose someone [...] -> consequences for CS (b) Suppose someone [...] -> consequences for Physics (c) the two final questions on classical vs quantum "structure-exploitation". I suggest this splitting in 3 would (eventually) produce higher-quality questions and meaninful answers. $\endgroup$ Commented Apr 10, 2018 at 14:49
  • 1
    $\begingroup$ For all three, I also recomment checking the phrase about "bullet 2 would be contradicted", which looks like a residual from a context with bullets. $\endgroup$ Commented Apr 10, 2018 at 16:05
  • 1
    $\begingroup$ That's weird. The book you linked seems to copy Theoretical Computer Science Q and A's verbatim: see cstheory.stackexchange.com/questions/6154/… . Is it even legal to have such a thing behind a paywall? $\endgroup$ Commented Apr 10, 2018 at 17:50
  • $\begingroup$ I guess it is legal if attribution is proper, but that is hard to check if stuff is behind a paywall. $\endgroup$ Commented Apr 10, 2018 at 17:56

2 Answers 2


Boaz Barak has a lovely essay on various hypothetical worlds with quantum computers. In particular, he calls your world where NP$\subseteq$BQP "popscitopia", and provides:

...in popscitopia quantum computers can be built, and NP $\subseteq$ BQP. This is the world that is described by some popular accounts of quantum computers as being able to “run exponentially many parallel computations at once”, a belief that is prevalent enough that Scott Aaronson devotes the tagline of his blog to refuting it.

As to which classes collapse, this might be gleanable from the Complexity Zoo's Hasse diagram (although it hasn't been updated in a while).

There's a snippet below - in particular, if NP contains a class, that class would then be contained in BQP if NP$\subseteq$BQP, and there would then be an arrow pointing from that class to BQP. Chasing the arrows around lets one hypothesize about such an inclusion.

Hasse Diagram of complexity classes

To be honest, though, it's hard to find an arrow pointing to NP that's not now pointing to BQP, for a complexity class among the "greatest hits". Many of these classes look pretty esoteric to me - e.g., is it noteworthy that YP would be in BQP if NP were in BQP?


If an NP-Complete problem is proven to be part of BQP, the whole industry of cryptography will be turned upside-down since the process of mathematically breaking a crypto-system can be expressed as a boolean-SAT problem.

It would become much more difficult to establish secret and secure communication, though not entirely impossible because being able to solve SAT would still not be enough (probably) to break a crypto-system in the case of cipher-text only attacks, and one could still use the one-time-pad without any problems. It would be come trivial to break challenge-response type authentication mechanisms though because that is a textbook example of a known plaintext attack.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.