Suppose that P = NP is true. Would there then be any practical application to building a quantum computer such as solving certain problems faster, or would any such improvement be irrelevant based on the fact that P = NP is true? How would you characterize the improvement in efficiency that would come about if a quantum computer could be built in a world where P = NP, as opposed to a world in which P != NP?

Here's a made-up example of about what I'm looking for:

If P != NP, we see that complexity class ABC is equal to quantum complexity class XYZ...but if P = NP, class ABC collapses to related class UVW anyway.

(Motivation: I am curious about this, and relatively new to quantum computing; please migrate this question if it is insufficiently advanced.)

  • 9
    $\begingroup$ We do not know if ${P}={NP}$ implies ${BQP}={P}$,such that there might be some problem in ${BQP}$ that is not in ${P}$ even if ${P}={NP}$....It is even also a open question whether or not ${BQP}$ is in ${PH}$.... $\endgroup$ – Tayfun Pay Feb 4 '15 at 22:36
  • 4
    $\begingroup$ More basically, the class $BQP$ captures "efficient" quantum algorithms (bounded-error quantum polynomial time). That is why Tayfun's formalization of your question is the natural one, e.g. if $P=NP$, are there problems still not in $P$, yet in $BQP$? And apparently it is consistent with our current knowledge that this happens. $\endgroup$ – usul Feb 5 '15 at 2:26

The paper "BQP and the Polynomial Hierarchy" by Scott Aaronson directly addresses your question. If P=NP, then PH would collapse. If furthermore BQP were in PH, then no quantum speed-up would be possible in that case. On the other hand, Aaronson gives evidence for a problem with quantum speedup outside PH, thus such a speed-up would survive a collapse of PH.

| cite | improve this answer | |
  • 10
    $\begingroup$ Actually Aaronson himself proved that the conjecture that he was based on this work is false. See scottaaronson.com/papers/glnfalse.pdf $\endgroup$ – Alex Grilo Feb 8 '15 at 9:34
  • 5
    $\begingroup$ @AlexGrilo Some of the results in the paper were unconditional and still stand: there is a oracle separation between relational versions of BQP and PH. $\endgroup$ – Sasho Nikolov Feb 9 '15 at 16:06
  • 8
    $\begingroup$ A clarification: while the "Generalized Linial-Nisan Conjecture" turned out to be false, the conjecture that the Fourier Checking / "Forrelation" problem is not in PH still stands. It's just that some other approach will be needed to prove it. Also, I can strengthen my result that there exists an oracle relative to which there are BQP relation problems not in BPP^PH, to show that there exists an oracle relative to which P=NP, but there are still BQP relation problems not in BPP. It's a straightforward extension, but unfortunately I haven't written it up yet. $\endgroup$ – Scott Aaronson Feb 12 '15 at 22:35

The answer is an unequivocal yes. Quantum computers would definitely still be useful.

Quantum computers are not oracles for BQP, but rather devices which process quantum states, and can communicate using quantum states. Just as the ability to make non-deterministic queries is fundamentally more powerful than the ability to make purely deterministic queries, independent of the status of P vs NP (and indeed this is the root of the oracle separations), the ability to make quantum queries and to communicate using quantum states is fundamentally more powerful than the purely classical counterpart.

This leads to advantages in a wide range of applications

  1. The ability to query oracles or external databases in superposition provides a provable separation between quantum computers and classical computers in terms of query complexity.
  2. There are a variety of communication tasks which see drastic reductions in communication cost which quantum communication is used.
  3. Quantum information processing allows for information theoretically secure protocols for a wider range of problems than are classically possible. Certainly QKD does not require a universal quantum computer to be implemented, but many protocols for other tasks do.
  4. Pre- and post-processing of large entangled quantum states allows you to violate the shot noise limit in metrology, resulting in more precise measurements.

Aside from the complexity arguments, there is another practical reason to want quantum computers. Much of the data processed on classical computers these days is derived from sensing the natural world (for example via the CCD in a digital camera). However, such measurements necessarily throw away some information about the system in order to render the measurement result as a classical bit string (for example collapsing spatial superpositions of photons), and it is not always clear which information will later be considered the most important when initially recording the data. It is, therefore, reasonable to believe that the ability to store and process quantum states directly, rather than collapsing them in some basis prior to processing will become increasingly desirable.

| cite | improve this answer | |

Addressing the practical part.

If $P=NP$, but SAT solvers run in $O(n^{2^{10^3}})$ this will be of no practical interest on current hardware.

On April 1st Doron Zeilberger proved (jokingly) that P is equal to NP. From the paper "Alas the complexity of our algorithm is $O(n^{10^{10000}})$ (with the implied constant being larger than the Skewes number)."

As far as I can tell sufficiently powerful quantum computer will be of practical interest in this case.

| cite | improve this answer | |
  • $\begingroup$ But quantum computers might not offer any speedup over a SAT solver that takes time $n^{2^{10^3}}$ either. $\endgroup$ – Sasho Nikolov Feb 9 '15 at 16:09
  • $\begingroup$ @SashoNikolov I addressed practical. Quantum computer which factors 2048 bit integers efficiently would be of practical interest to me as of now because of RSA keys ;). $\endgroup$ – joro Feb 9 '15 at 17:22
  • $\begingroup$ I believe that one can get linear time sorting algorithms with quantum computers. $\endgroup$ – Baby Dragon Jun 11 '15 at 2:00

There are studies in the relation between BQP and the polynomial hierachy PH. For instance, there is a problem relative to which BQP is not contained in PH (http://arxiv.org/abs/0910.4698), and a conjecture that proves the same result in an unrelativized world (http://arxiv.org/abs/1007.0305). See also the problem of BosonSampling, that is sampling from the probability outcome of photons coming out from a beam splitter network, is thought to be classically hard while can be implemented by a rather simple quantum systems which is not even a universal quantum computer (look for the paper Aaronson, Arkhipov - The Computational Complexity of Linear Optics). It is another hint that quantum computing is stongher than PH: indeed, if a classical computer can efficiently solve BosonSampling with an oracle for a PH problem, then $P^{\# P}\subseteq BPP^{PH}$ which imply the polynomial hierarchy would collapse.

In conclusion, we don't know what is the exact power of quantum computers but there are results suggesting that BQP might be outside PH.

| cite | improve this answer | |

Your Answer

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

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