42

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


24

Yes, it can do so in a rather trivial way: Use only reversible classical logical gates to simulate computations using boolean logic (for instance, using TOFFOLI to simulate NAND gates), use only the standard basis states $\lvert 0\rangle$ and $\lvert 1\rangle$ as input, and only perform standard basis state measurements at the output. In this way you can ...


7

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


3

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


1

Yes, it can because quantum computing is a generalization of classical computing. So the procedure you ask for exists. We can take a universal classical logic gate such as NOR gate, generalize to a reversible quantum version of that NOR gate. Thus a procedure can be as follows: Design classical circuit Rewrite classical circuit using only the chosen ...


Only top voted, non community-wiki answers of a minimum length are eligible