58
$\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$
38
$\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$
  • 1
    $\begingroup$ Would you be able to explain what you mean by randomness just being ignorance? I'm very possibly looking at this the wrong way, but it does read to me like you're saying that everything is deterministic, which is purely an interpretational issue, so doesn't have any defined answer $\endgroup$ – Mithrandir24601 Mar 12 '18 at 22:49
  • 3
    $\begingroup$ Said another way, anyone who claims that the universe is fundamentally non-deterministic is claiming that they know for certain that no one will ever discover a way to predict certain things. Since they can't actually prove such a proposition, since it's literally impossible to somehow know that for sure, they'd be making an entirely meaningless claim, on-par with any other unfalsifiable dogma. Such dogma isn't in the realm of science or reason. $\endgroup$ – Nat Mar 12 '18 at 23:18
  • 3
    $\begingroup$ I would say that "true randomness" is computationally equivalent to ignorance. This is because, when you analyze the expected output of a randomized program, inserting a sampling step in the middle (to "resolve ignorance") does not change the distribution that the program is sampling from. $\endgroup$ – Craig Gidney Mar 12 '18 at 23:29
  • 1
    $\begingroup$ @Nat There are ways to prove "true randomness" (no one could have known the outcome before we measured) under reasonable assumptions (e.g. no signaling) using Bell's theorem. It might be worth a question. $\endgroup$ – M. Stern Mar 12 '18 at 23:42
  • 3
    $\begingroup$ If a quantum computer can do it, then a classical Turing machine could, too. - This stops being true as soon as you relax a bit what you mean by a "quantum computer". If for example your computer is "delocalized" (that is, maybe one part of it is somewhere and another part somewhere else, which is totally conceivable) then you are able to do things that are straight out impossible within classical physics. Violating Bell's inequalities is the paradigmatic example of this, but also a great many tasks that are usually expressed in terms of "games" fall into this category. $\endgroup$ – glS Mar 13 '18 at 16:35
6
$\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$
  • 5
    $\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
  • $\begingroup$ @Nat the question was about Turing machines, though, not about "classical devices"... $\endgroup$ – Bjørn Kjos-Hanssen Mar 12 '18 at 18:59
  • 1
    $\begingroup$ @Nat right, but not every classical device is a Turing machine $\endgroup$ – Bjørn Kjos-Hanssen Mar 12 '18 at 19:01
  • 2
    $\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
  • 1
    $\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
2
$\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$
  • $\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.