How is a quantum simulator able to simulate a quantum mechanical properties on a classical computer?

Question

I'm confused as to how a classical computer can simulate quantum mechanical properties through the use of classical bits. Why do we need quantum computers if a quantum simulator can do it's job on a classical computer?

Answer 1

If you mean to ask about how a classical computer can simulate how a quantum computer would compute, think about it as follows. The theory of quantum computation gives us a framework to express these computations in a mathematical form. These, of course, are equations. For example, suppose that a quantum algorithm requires the action of a particular quantum gate on a quantum state. In the context of pure quantum states, this means that the quantum state is expressed as a unit-norm vector belonging to the complex Hilbert space. The action of the quantum gate would then be expressed as a matrix multiplication of the unitary matrix representing the quantum gate and the said state vector. Thus, once these quantum computations have been reduced to matrix-vector calculations, it becomes straightforward to implement those calculations on your (classical) framework of choice, such as Matlab or Numpy. Since entangled states would just be be non-separable multi-qubit states, it follows that the state vectors can represent entangled states as well. Even measurements can be simulated classically by generating random outcomes based on the probability distribution resulting from the state amplitudes.

However, these classical simulations of quantum computations would not be efficient for all cases. For example, for representing the state of 1 qubit, you need a 2 dimensional vector; for 2 qubits, 4 dimensions; for 4 qubits, 16 dimensional vectors - the growth is exponential. So, if you need to represent a 32 qubit state classically, you need a complex vector of $2^{32}$ dimensions. If each entry of the vector is a complex number, with the real and imaginary parts each being expressed in 16 bits (for instance), we are already talking about a memory requirement of $2^{32} * 2 * 16 \text{bits} = 17.2 \text{GB}$. Meaningful quantum calculations which would require at least ~100 qubits would become highly inefficient on classical computers. Thus, we would require true quantum computers, even though simulators might be helpful in rapid prototyping for small circuits.

Answer 2

A system composed of $n$ qubits is described by $2^n$ parameters (complex numbers). So simulation of quantum computer has generally exponential complexity in size of simulated problem. As a result only small quantum circuits can be simulated on a classical computer in reasonable time.

However, there is a special familly of quantum cirucits composed only from so-called Clifford gates $H$, $S$ and $CNOT$ which can be simulated efficiently on a classical computer. But to have a quantum computer universal, you also need $T$ gate which is non-Clifford one and cannot be simulated efficiently. This causes that a quantum computer cannot be generally simulated efficiently. See Gottesman-Knill theorem for more information.