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

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:


Randomness can be more precisely captured by using distribution math anyway.
Randomness isn't a real "thing" to begin with; it's merely ignorance.  And we can always produce ignorance.

