3
$\begingroup$

Forgive me if this question was already asked somewhere on this site-I haven't found it but it is possible that I've overlooked it. So basically, I would like to summarize different notions of quantum models of computations, namely:

  1. Quantum circuits
  2. Quantum Turing machine
  3. Universal quantum computer as described in Deutsch's paper: Quantum Theory, Church-Turing Principle and the Universal Quantum Computer.

As far as I know, every quantum computer can be simulated on a classical computer: I suppose that this refers to ,,quantum circuit'' model of computation: it would mean that the class of problems which can be solved (theoretically) on a quantum computer coincides with the class of problems which can be solved by a classical computer. However, Deutsch in his paper argues that the are problems which cannot be solved by a classical computer yet can be solved by his (universal) quantum computer which suggest that his notion of computability would be different.

For the puropose of this discussion call $QC,QTM,QUC$ the classes of problems which can be solved (assuming unbounded time and memory resources) by quantum circuit model of computation, by quantum Turing machines and by universal quantum computer of Deutsch respectively. Let $RE$ be a class of problems solvable by a classical computer.

Question: What are the inclusions between those classes?

If comparing complexity classes is usually very difficult subject, I also welcome answers of the sort ,,it is not known but widely believed that some of these two classes coincide''.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Deutsch was engaged in hyperbole in manners that we wouldn’t say nowadays. Quantum computers cannot solve problems in the computational sense that classical computers cannot. $\endgroup$
    – Mark Spinelli
    Commented Sep 13, 2023 at 10:50
  • 1
    $\begingroup$ Also FYI you are asking about computability classes; for a counterpart question about complexity classes please see this question (which I answered similarly and I'd invite others to answer as well). $\endgroup$
    – Mark Spinelli
    Commented Sep 13, 2023 at 20:04

1 Answer 1

Reset to default
3
$\begingroup$

A quantum computer (or quantum Turing machine or quantum circuit) cannot solve any problem that a classical computer could not, because one can simulate the other

Initially in a comment I had proposed that Deutsch was "engaged in hyperbole". Truth-be-told, I think that, in all likelihood, Deutsch and Feynman and others certainly knew that their quantum computers were more powerful than classical computers, but didn't have the language to describe the particular power afforded by them. Hence they defaulted with statements that could be read as saying that quantum computers are more powerful in the Turing-sense of the word. But I don't think Deutsch (or Feynman) intended to exaggerate their quantum simulators in the manner suggesting that they were broader than classical computers insofar as being able to solve the Halting problem.

Secondly I'm not sure if Deutsch really had much of a distinction between his quantum Turing machine and a "universal quantum computer". Certainly he described a quantum Turing machine as having the tape be held in superposition, and also constructively programmed a (universal) quantum computer by giving Algol-pseudocode to run the EPR experiment. But, just as no one programs a classical computer with a Turing machine (except as a bit of a sport), no one would program a quantum computer with a quantum Turing machine.

Also, Deutsch and Feynman worked for a while in the circuit model (while Bernstein and Vazirani initially used the quantum Turing model). But there is a small catch in the circuit model - both classical and quantum! - where we have to be careful not to embed an uncomputable problem into our definition of the circuit. This is the "uniformity condition" that Andrew Yao glossed over but that was corrected later after Shor's algorithm.

But using your definitions, at least we have that the following are equivalent:

  1. $RE$, the class of all problems solvable with a classical computer
  2. $QTM$, the class of all problems solvable with a (universal) quantum Turing machine
  3. $QUC$, the class of all problems solvable with a universal quantum computer
  4. $QC$, the class of all problems solvable with a quantum circuit

To show that two classes $A$ and $B$ are equivalent, it suffices to show that $A$ can be simulated by $B$, and that $B$ can be simulated by $A$.

I would broadly prove this as follows:

  • Yao showed that a quantum circuit is equivalent to a quantum Turing machine by patiently showing how one could simulate the other;
  • Feynman showed that a quantum circuit can simulate a classical circuit, at least because of the unitarity of, and classical universality of, the CCNOT (Toffoli) gate and/or the CSWAP (Fredkin) gate; and
  • Schrodinger initially showed that we can classically simulate a quantum circuit just by keeping track of the wavefunction, while Feynman improved this to show that it suffices to look at the Feynman path integral.

Because a quantum circuit can be simulated by a classical computer, just by updating the wavefunction after each gate, we cannot use the quantum circuit to solve the Halting problem. For, if we did, then we could use the classical computer to simulate the quantum circuit to solve the Halting problem, in violation of Turing's theorem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for the very informative answer! I agree that it is impossible to solve the halting problem with quantum computers: however as far as I remember Deutsch was alluding to much more modest goal, namely: generating true random numbers. How this fits into the overall picture? $\endgroup$
    – truebaran
    Commented Sep 13, 2023 at 13:13
  • $\begingroup$ You may look at this question on a sister site. I'd have nothing to add beyond that conversation now, but there is some suggestion that a TM augmented with a truly random number generator may not be compatible with one without. Honestly though from what we now know about the power of (classical) pseudorandom number generators I would feel that generating true random numbers with a bunch of Hadamard gates is not that impressive. Is that still within the metes and bounds of what's considered RE? $\endgroup$
    – Mark Spinelli
    Commented Sep 13, 2023 at 16:35
  • $\begingroup$ Yeah, I agree that for all practical purposes pseudo-random generators are good as well but recently I came across very interesting paper of Klaas Landsman about undecidability and indeterminism: from this paper I've learned that truly random numbers are the so called Kolmogorov 1-random numbers and the situation for those numbers is very peculiar, namely: 1. If you have infinite series of truly random coin tosses, almost all (with respect to the product measure) outcomes will be 1-random 2. But there are only finitely many 1-random numbers for which you can prove their 1-randomness $\endgroup$
    – truebaran
    Commented Sep 14, 2023 at 0:16
  • $\begingroup$ and moreover 3. Once you have a number which is 1-random only at most finitely many of its digits can be computable! So while I agree that generating truly random numbers maybe is not so spectacular but there is definitively some ,,foundational'' aspect to it which I find interesting for purely theoretical reasons. However thank you for pointing me to the other discussion on another forum-I think that the accepted answer adresses most of my issues $\endgroup$
    – truebaran
    Commented Sep 14, 2023 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.