Are quantum computers able to simulate every physical process that a classical one can simulate?

Question

I edited the question since this comment was (rightly) made:

There are few things that are more annoying than questions where the question text is not self-contained.

So:
Quantum supremacy has been reached quite recently.
It is said that a quantum computer, because of its stronger computing power can simulate physical processes much faster than a classical computer.
Now, quantum computers make a huge amount of different permutations of whatever. How does this relate to physical processes?
For example, a classical computer can compute the trajectory of an object in our solar system with high accuracy. I can't see how a quantum computer can do this job by performing permutations with incredible speed. So I'm not asking if a QC can perform this simulation faster but if it can be calculated at all by a QC.
So here is my question: Is the collection of physical processes that can be simulated by a quantum computer limited to specific processes or is a quantum computer, in principle, capable to perform the same calculations (of every physical process) a classical computer is capable of?
I don't know that much about quantum programming (or programming in general), so an additional question could be if the algorithms used in a quantum computer program are similar to those used in a classical one but this I better ask on the appropriate site (specially dedicated to all stuff related to quantum computers).

Norbert Schuch · Accepted Answer

Yes, a quantum computer is capable of carrying out all computations a classical computer can do.

Classical computers act on classical bitstrings $x_1x_2dots  x_N$, e.g. 01010010....  The action of a gate/operation on a classical input is to map such a bitstring to a different one.  Any classical computation can be expressed as a sequence of reversible operations.  Then, the action of any classical gate/operation is a reversible action on the bitstring, that is, a permutation. Typically, we will only consider gates acting on very few bits.
A quantum computer acts on qubits.  These can be in any basis state $|x_1x_2dots x_Nrangle$, as well as superpositions thereof.  Gates are unitary transformations acting on a few qubits.
If you now initialize your quantum computer into a basis state $|x_1x_2dots x_Nrangle$ and only act with permutations - a special case of unitaries - then your quantum computer effectively carries out the classical computation.
So yes, a quantum computer is capable of carrying out all computations a classical computer can do -- and more.

Peter · Answer

If the Church-Turing thesis is correct, then it's possible. Conversely, if it cannot, then the C-T thesis would be wrong. This would be huge news in the field of computing!
I have heard no news of such a fundamental breakthrough in computing theory, and Wikipedia has not either.

Andrew Steane · Answer

The question has two aspects: the formal computer science/mathematical aspect, and the practical aspect.
On the formal computer science aspect, classical computing is a strict subset of quantum computing. That means that anything a classical computer can do, a quantum computer can also do, and furthermore it means that the quantum computer will not be slower than the classical one, when measured in terms of number of operations and memory elements required for a given task.
However, from a practical point of view, quantum computers are designed to tackle a set of problems for which they are not just equal to but better than classical computers. Here 'better than' means 'exponentially faster than'. In order to get access to this speed-up, the quantum computer must exploit quantum superposition and entanglement, and this requires extreme precision and protection of the computing elements from noise. The requirements are much more severe than for classical computing, and as a result the quantum computer will typically have a much slower clock rate or basic logic gate rate, and the design is not well-suited to tackling the sorts of problems that do not exploit entanglement. Thus in practice quantum computers are not fast at tasks that cannot exploit the quantum speed-up, and that means most tasks in practice. But the tasks which can be speeded up include some that have very wide-ranging application, especially to scientific research.
To summarise, quantum computers can do everything that classical computers can do, but in practice you would choose a classical computer for some tasks because its design allows it a faster gate rate (and it is cheaper to build).

Are quantum computers able to simulate every physical process that a classical one can simulate?

3 Answers

Add your own answers!

Ask a Question