61
$\begingroup$

I know that a Turing machine1 can theoretically simulate "anything", but I don't know whether it could simulate something as fundamentally different as a quantum-based computer. Are there any attempts to do this, or has anybody proved it possible/not possible?

I've googled around, but I'm not an expert on this topic, so I'm not sure where to look. I've found the Wikipedia article on quantum Turing machine, but I'm not certain how exactly it differs from a classical TM. I also found the paper Deutsch's Universal Quantum Turing Machine, by W. Fouché et al., but it is rather difficult to understand for me.


1. In case it is not clear, by Turing machine I mean the theoretical concept, not a physical machine (i.e. an implementation of the theoretical concept).

$\endgroup$
42
$\begingroup$

Yes, a quantum computer could be simulated by a Turing machine, though this shouldn't be taken to imply that real-world quantum computers couldn't enjoy quantum advantage, i.e. a significant implementation advantage over real-world classical computers.

As a rule-of-thumb, if a human could manually describe or imagine how something ought to operate, that imagining can be implemented on a Turing machine. Quantum computers fall into this category.

At current, a big motivation for quantum computing is that qubits can exist in superpositions,$$ \left| \psi \right> = \alpha \left| 0 \right> + \beta \left| 1 \right>, \tag{1} $$essentially allowing for massively parallel computation. Then there's quantum annealing and other little tricks that are basically analog computing tactics.

But, those benefits are about efficiency. In some cases, that efficiency is beyond astronomical, enabling stuff that wouldn't have been practical on classical hardware. This causes quantum computing to have major applications in cryptography and such.

However, quantum computing isn't currently motivated by a desire for things that we fundamentally couldn't do before. If a quantum computer can perform an operation, then a classical Turing machine could perform a simulation of a quantum computer performing that operation.

Randomness isn't a problem. I guess two big reasons:

  1. Randomness can be more precisely captured by using distribution math anyway.

  2. Randomness isn't a real "thing" to begin with; it's merely ignorance. And we can always produce ignorance.

$\endgroup$
7
$\begingroup$

To simulate the collapse of the wave function you'd need a source of randomness. So you'd need a probabilistic Turing machine.

$\endgroup$
  • 6
    $\begingroup$ Classical devices can use typical random-number generators, or whatever's appropriate for their purposes. Randomness isn't a fundamental quality that needs to be sourced from quantum mechanics (which is a pretty big conceptual misunderstanding folks often get from the Copenhagen interpretation, which is perhaps best understood as a simplifying approximation). $\endgroup$ – Nat Mar 12 '18 at 18:07
  • 3
    $\begingroup$ In general if you don't care about efficiency, you can just try every element of a space instead of sampling from it, avoiding the need for randomness. $\endgroup$ – Tavian Barnes Apr 4 '18 at 18:38
  • 2
    $\begingroup$ If you truly wish to create all relevant quantum effects, you'd need to be able to violate the Bell inequality and hence a probabilistic Turing machine is insufficient. If you only want to match the computational power of the quantum Turing machine, we can use a Turing machine without randomness to do so. In any case, a probabilistic Turing machine isn't going to be useful. $\endgroup$ – Discrete lizard May 1 '18 at 21:37
3
$\begingroup$

To complete what others have said: as far as we know a (classical) Turing machine cannot truly simulate quantum correlations. This is explicitly claimed in section Properties of the universal quantum computer by the seminal paper by David Deutsch Quantum theory, the Church-Turing principle and the universal quantum computer (Proceedings of the Royal Society of London A 400, pp. 97-117 (1985)).

Details will depend on the implementation or on your exact definitions for Turing machine, of quantum computer, and especially of simulate (if you are generous enough with what simulates mean, anything can simulate anything). Generally speaking, it is possible to design a quantum computer which, when repeatedly operated by starting from the exact same starting state (or input bits), in every operation generates random output bits which present certain quantum correlations with each other.

As far as I know, a Turing machine cannot do that.

$\endgroup$
  • 1
    $\begingroup$ It might be worthwhile to add (It's perhaps more of a rephrasing, but one that I think is useful) that adding 'random number generation' to a Turing machine (e.g. as an oracle) doesn't help in the simulation of the quantum Turing machine, as it cannot simulate bits that violate the Bell inequality, while a quantum Turing machine can (as is stated in the paper by Deutsch, if I read it correctly). $\endgroup$ – Discrete lizard Apr 29 '18 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.