77
$\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).

Improve this question
$\endgroup$
0

4 Answers 4

Reset to default
50
$\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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ "Randomness = ignorance" is a very deep misunderstanding. It boils down to uncertainty principle and noncommutativeness of observables. ONLY in a quantum setting you can have an experiment, in which the outcome cannot be predicted EVEN IN PRINCIPLE, - the quantum measurement. No classical random generator can capture this feature of a quantum computer. But the current terminology is such that neither weak nor strong definitions of simulation require this, so, technically speaking, we can simulate a quantum computer classically, even though the final randomness will not be quantumly random. $\endgroup$
    – mavzolej
    Sep 24, 2020 at 5:19
  • $\begingroup$ @mavzolej: I think you're taking current theories a tad too literally, coming to a quantum-mysticism sort of view. That said, at current we can't prove that Quantum Mechanics doesn't emerge from a deeper deterministic theory. Sure such a theory might be stupidly complex; sure it might be non-local or/and retro-causative, but it could exist. Given that we can't exclude the possibility of determinism, what sense does it make to assert fundamental quantum randomness as anything more than a feature of the current theory? $\endgroup$
    – Nat
    Sep 24, 2020 at 19:14
  • 2
    $\begingroup$ You're talking now about hidden variables , this possibility has been studied thoroughly and eliminated. $\endgroup$
    – mavzolej
    Sep 24, 2020 at 21:12
  • 2
    $\begingroup$ @mavzolej: Are you referring to Bell experiments for local hidden variables? Because deterministic generalizations have not been eliminated; nor could they be, even in theory. (Well, in extreme theoretical contexts, the question gets interesting. But, practically speaking.) $\endgroup$
    – Nat
    Sep 24, 2020 at 21:15
13
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 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, 2018 at 18:07
  • 4
    $\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, 2018 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, 2018 at 21:37
11
$\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.

Improve this answer
$\endgroup$
2
  • 4
    $\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, 2018 at 17:01
  • $\begingroup$ this might help - datatracker.ietf.org/meeting/interim-2020-qirg-01/materials/… $\endgroup$
    – Nathan Aw
    Apr 16, 2020 at 10:27
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Just few notes. A quantum annealer and a gate-based computer are equivalent. A quantum computer is Turing machine. This all means that any problem solvable by a Turing machine can be solved on QC, despite whether it is gate-based computer or annealer. $\endgroup$
    – Martin Vesely
    Dec 14, 2022 at 7:18

Your Answer

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