Could quantum computing help resolve some computability problems like p vs np or the halting problem?

Question

How much could " quantum " logic push the limits of computability in the sense of standard logic. Don't know if this is even a sensible question and it's as vague as it gets, that's why I'm posting it here not on owerflow although might be something still in research.

Answer 1

Quantum computers don't give you any new computable functions, so they certainly can't solve the halting problem in the sense of there being a quantum algorithm that can decide if an arbitrary classical algorithm halts. P vs NP is a sharp mathematical problem about classical computation so QC can't really have any bearing on that problem per se.

However, quantum computers do give new algorithms, and there are several well-known problems where the fastest known quantum algorithm is faster than the fastest known classical algorithm. (By "fast" here, I mean in terms of asymptotic time complexity). So a question related to P=NP that would make sense would be if any NP-hard problems can be solved in polynomial time by a quantum computer. The answer is that we don't know. The most famous polynomial time quantum algorithm, Shor's algorithm, solves the prime factorization problem in polynomial time whereas there is no known classical algorithm that does this. However, prime factorization is not known to be NP-complete, and expert consensus is that it is probably not.

Answer 2

Everything computable in the quantum sense is also computable in the standard sense, so you don't get any new power that way. On the complexity side, things are more interesting, but not (yet) as drastic as one might expect: it is still open, for example, whether a quantum computer can solve NP-complete (in the usual sense) problems in polynomial time. "Quantum speedup," such as we have so far, is due to structural properties of the problem in question (e.g. factoring) which general problems in NP do not have (as far as we know).

This article by Aaronson is a good starting point for this sort of thing. To quote from the article:

[Quantum computers] would solve certain specific problems, such as factoring integers, dramatically faster than we know how to solve them with today’s computers, but analysis suggests that for most problems quantum computers would surpass conventional ones only slightly. [...] A quantum algorithm capable of solving NP-complete problems efficiently would, like Shor’s algorithm, have to exploit the problems’ structure.

---

As an aside, though, we need to be careful when we talk about "quantum computers." If we're just talking about computation which somehow uses quantum mechanics, this is a wildly-underdetermined notion: certainly very weird laws of physics could in principle allow us to build computers which lean on quantum phenomena somehow for huge computational power (including beyond classical computability). That seems wildly implausible though. There is an axiomatic notion of quantum computation, however, which so far matches what we know about quantum physics, and with respect to which we can in fact prove impossibility results (e.g. "everything quantum computable is classically computable").