Is P vs NP the same thing as being solvable by classical vs. quantum computers?

Is the P vs NP problem really a problem? Can't we say that the P problems are the problems solvable by classical computer because it fits into its architecture and NP problems are quantum in nature and can be solved by computers of quantum architecture?

1 Answer
1

No, classical computers can solve NP problems, just not quickly for large problem sizes.

Practical performance is not at all the point of the P vs NP problem.

I think (but am not sure) that there could be some classical-polynomial-time problems which a quantum computer could solve more quickly than a classical computer of comparable technology level.

The point of P vs. NP is that we haven't even proved that Nondeterministic Polynomial-time problems (solution verifiable in polynomial time) are actually harder than any/every possible P problem.

i.e. that the set of all NP problems is not identical to the set of P problems.

We currently don't know how to solve NP-complete problems in polynomial time, but nobody has proved we can't, and that's what the https://en.wikipedia.org/wiki/P_versus_NP_problem is about.

Quantum computing is a super-set of classical computing, so a quantum computer can solve every P problem in polynomial time. But not necessarily using a quantum algorithm that actually treats any bits as having values other than pure 0 or pure 1.

But we don't know if quantum computers can solve every NP problem in polynomial time. That's another open problem. (See comments: we don't know if BQP = NP, as well as not knowing if P = NP.)

Regardless of whether quantum computers exist that can solve (some?) NP problems in a reasonable amount of time, P vs NP is still an open question in theoretical CS. Classical computing is still a very interesting and relevant subject¹.

Given that nobody's found a way to solve NP-complete problems in polynomial time yet, it's highly unlikely that there is one, and if there is it's unlikely that it's fast for practical problem sizes. (Perhaps very large scale factors or exponents for a very quickly-growing polynomial that's still smaller than any exponential function as n approaches infinity.)

Requiring a quantum computer to solve efficiently (for large problem sizes) is related to whether any P algorithm is known for classical computers.

Quantum computing doesn't solve or obsolete the P vs. NP question.

Footnote 1: I expect classical computing to be at least theoretically interesting even in a hypothetical future where cheap microcontrollers can include some quantum logic without increasing their cost or requiring cryo-cooling or other expensive operating requirements.

But that hypothetical future is unlikely. Even given time for ramp-up of quantum-computer production lines to match the current vast economies of scale and technological maturity of doped silicon, decoherence is a major unsolved problem. There's no reason to expect that quantum computing will ever fully take over from classical; silicon is fundamentally pretty robust and can operate well at room temperature.

It might become an essential component of desktop computers in the future (the way floating point hardware or GPUs are now: ubiquitous on high-end CPUs but still absent on microcontrollers). But there will still be pure-classical components.

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.