It is sometimes said that quantum effects lead to non computable results in the weak sense that quantum computers might allow truly random actions (at least according to some interpretations). I think this has been equated to quantum machines being equivalent to non probabilistic or non deterministic Turing machines (whatever that means, not an expert). What are some examples of uncomputable actions that these non deterministic Turing machines (or quantum computers if different) can do that classical deterministic ones cannot ?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
There was some initial characterization of quantum computers as going beyond Turing. But this is not the way we see things today.
Around 1982, Richard Feynman stated of his proposed quantum computer/simulator:
It's not a Turing machine, but a machine of a different kind.
In 1989 David Deutsch stated, upon the demonstration of the BB84 key distribution at Yorktown Heights, that the researchers:
have created the first information processing device with capabilities that exceed those of the Universal Turing Machine.
These make for great headlines, but they are kind of "lies-to-children" that we wouldn't say nowadays, for reasons discussed below.
Quantum computers cannot solve uncomputable problems.
Generally an uncomputable problem is a problem that cannot be formally decided, either decided to be true or false, in finite time. The prototypical example of an uncomputable problem is the Halting problem of deciding whether a given computer program will halt (or, alternatively, will run forever). However, there are many other beautiful problems that have been shown to be undecidable - see this great thread on MathOverflow.
Importantly, a quantum computer can be simulated (although inefficiently) on a classical computer. So, because a classical computer cannot solve the Halting problem as it's uncomputable, a quantum computer cannot either (because if it could, then we could simulate the quantum computer with the classical computer and still solve the Halting problem with a classical computer, which would be in violation of Turing's theorem).
A quantum computer probably cannot efficiently simulate a nondeterministic Turing machine.
A nondeterministic Turing machine is a type of Turing machine that can "take multiple paths" in a nondeterministic fashion, and can essentially "guess" the answer to a decision problem. The formal definition of a nondeterministic Turing machine involves a tape with transitions being relations rather than functions.
I find the formal definition using six-tuples and tapes etc. to be quite awkward, but I think most people are more comfortable talking about witnesses rather than nondeterminism. This is why we talk about witness that can be efficiently (polynomially) verified.
Regarding quantum computers, after some initial hope in the late 90's, however, it's now believed that a quantum computer cannot efficiently simulate such nondeterministic machines.
Still, quantum computers can presumably do many wonderful things more efficiently than classical computers.
Nonetheless the key question driving much of the research in the field is what can a quantum computer do more efficiently than a classical computer. Could a quantum computer efficiently solve a problem that can't even be efficiently verified classically? I think yes.
Still one of the best places to go to for such problems, I think, is the quantum algorithm zoo, although I don't know how often it's updated.
The power of quantum computers is expected not to be solely due to the probabilistic nature of such computers.
For example another kind of nondeterministic Turing machine is a probabilistic Turing machine - where the transitions can be random. This is akin to a (classical) computer afforded with extra coin-flip gates.
Although such a coin-flip gate is similar to a Hadamard gate, it's reasonable to suppose that a quantum computer can efficiently do even more than such a probabilistic Turing machine. For example, although a probabilistic Turing machine can efficiently (with high probability) determine whether a number is prime based on the Miller-Rabin primality test, we don't know how to have a probabilistic Turing machine efficiently factor a number, but by Shor we do have an efficient algorithm for a quantum computer.
Thus quantum computers probably get their power from something else, other than or in addition to their randomness - perhaps some combination of superposition, entanglement, and interference.
We know containment of many classes of such Turing machines, but we don't know strict separation for many such classes.
Letting
- RE (recursively enumerable) be the class of languages decidable by a Turing machine, whether efficiently or not,
- P (polynomial) be the class of languages efficiently decidable by a deterministic Turing machine,
- NP (nondeterministic polynomial) be the class of languages efficiently decidable by a nondeterministic Turing machine,
- BPP (bounded error polynomial) be the class of languages efficiently decidable by a probabilistic Turing machine, and
- BQP (bounded error quantum polynomial) be the class of languages efficiently decidable by a quantum computer,
we have P$\subseteq$NP$\subsetneq$RE, and P$\subseteq$BPP$\subseteq$BQP$\subsetneq$RE, with the million-dollar question being whether P$\subsetneq$NP. Many people (including myself) believe a strict separation between P and NP, and also between BPP and BQP, but we don't know how to prove these separations yet. This is why I had to use so many "likely's" etc. in the answer.
Quantum mechanics does provably enable some tasks that can't be done classically.
Nonetheless, regardless of all the caveats and the exceptions mentioned above, quantum mechanics does empower a certain amount of provable separation between what's achievable classically versus what's achievable quantumly. Perhaps the emblematic example of this is the Bell inequality and its manifestation in the CHSH game. The BB84 scheme mentioned earlier also offers information-theoretical security guarantees (that couldn't ever be achieved with a magic box like the Enigma machine or RSA fobs).
These kinds of splits between classical and quantum may have been what the founders, such as Feynman and Deutsch, meant by saying that quantum mechanics does something different than a Turing machine. But such non-local tasks wouldn't be described as uncomputable in the Turing sense.
answered Feb 11, 2023 at 4:48
-
$\begingroup$ Just to be clear the possibility that the measurement results in quantum computers are random (at least in Copenhagen view), contrary to a deterministic Turing machine, does not add anything to to the things that a quantum computer can do? I am not talking about efficiently solving a problem but on the capability side. $\endgroup$– MauricioCommented Feb 11, 2023 at 12:09
-
$\begingroup$ "Lies to children"? Are you implying the statements were intentionally misleading? $\endgroup$– kodluCommented Feb 11, 2023 at 14:36
-
$\begingroup$ oops obviously not, I didn't know the term lies to children. $\endgroup$– kodluCommented Feb 11, 2023 at 14:37
-
2$\begingroup$ I think it's still worth pointing out that one could make legitimate arguments that quantum mechanics does allow things that are "impossible" classically. Mostly when you keep into account (non)locality aspects. Eg nonlocal games kinds of deals, certain cryptographic safety guarantees etc. There's also arguments to be made about allowing "true randomness", but I find these ultimately problematic and not that convincing. But clearly, as you point out, one should not talk about "solving uncomputable problems", as that means something specific that is different from these tasks. $\endgroup$– glS ♦Commented Feb 11, 2023 at 17:21