79

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).

glS
  • 27,510
  • 7
  • 37
  • 125

4 Answers4

52

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.

Nat
  • 1,507
  • 1
  • 14
  • 27
13

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

Bjørn Kjos-Hanssen
  • 262
  • 4
  • 9
11

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.

agaitaarino
  • 3,907
  • 2
  • 13
  • 42
2

Yes. A Turing machine can simulate a quantum computer, but it really depends on how you define "simulation".

For example, with a quantum annealer, there are classical techniques like simulated quantum annealing that provide solutions to many problems. These can obviously be implemented using Turing machines. The real question is whether every problem that can be posed on a quantum annealer is solvable using classical techniques.

It really depends on whether your intent is to simulate the process of quantum computing, or to simulate the obtaining of the end result from equivalent initial conditions.

yubik
  • 21
  • 1