"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$ Apr 10 '18 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$ Apr 10 '18 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$ Apr 10 '18 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$ Apr 10 '18 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.