If P = NP were true, would quantum computers be useful?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.