# Why can't you efficiently simulate quantum computers on classical computers

I have just started learning about quantum computers, and my understanding of quantum mechanics is very limited. However, I can not find an answer to my question. So my question can be divided into two main sub-questions:

• If a qubit can just be represented as two complex numbers (to represent the wave function of the superposition, why can't a computer just simulate a quantum computer with, say 32-bits per qubits? So, instead of the number of bits growing as $$2^n$$, it would be something like $$k\times n$$, where $$k$$ is some number of bits, e.g. 32. What is the fundamental difference between the qubit and a 32-bit set of two complex numbers

• If a classical computer cannot simulate a quantum computer, how can a laser? I saw a video which uses lasers. Since lasers can simulate a quantum computer, why can't a classical computer?

• Directly related to this video, why do you need to entangle the photons of the lasers to add more qubits? What role does entanglement play?

Superposition isn't what causes problems for simulation, but rather the way multiple qubits are combined (which is what gives rise to the notion of entanglement). Yes, the state of a single qubit is represented by two numbers, but the state of, $$n$$ qubits is not represented by $$n$$ independent qubit states (i.e. $$2n$$ complex numbers), but by the tensor product of them, which is $$2^n$$ numbers.

More concretely, let's say we have three qubits. The state of the qubits is not

$$| \psi \rangle = a_1 | 0 \rangle_1 + b_1 | 1 \rangle_1 + a_2 | 0 \rangle_2 + b_2 | 1 \rangle_2 + a_3 | 0 \rangle_3 + b_3 | 1 \rangle_3$$

but rather

$$| \psi \rangle = c_1 | 000 \rangle + c_2 | 001 \rangle + \cdots + c_7 | 110 \rangle + c_8 | 111 \rangle$$

Notice how we have a coefficient for every combination of all three basis states.

Quantum computation, at a basic level, is done via quantum gates; these are matrices that act on subsets of qubits, so a $$1$$-qubit gate is a $$2 \times 2$$ matrix, a $$2$$-qubit gate is $$4 \times 4$$, $$3$$-qubit gate $$8 \times 8$$ and so on. A quantum circuit consists of a sequence of these gates being multiplied by the state, one-by-one, and each multiplication entails modifying all $$2^n$$ numbers in the state; this is why simulation is so hard.

So how does a quantum computer sidestep this problem?

Now, different quantum computer hardware implementations work very differently, so let's look at your laser example. First off, assuming you're talking about trapped-ion devices, the laser doesn't simulate the quantum computer, but rather performs the quantum computing operations on the qubits (the ions) by coupling ions together; the photons aren't entangled, but the ions are.

A sequence of laser pulses will in effect alter the state of the qubits in a way mathematically described by performing a matrix multiplication. However, the laser isn't actually multiplying any numbers; that's just the way we describe the state. In other words, we're letting the physics of the laser and trapped ions do the computation for us.

• Your first claim is a bit misleading. Entanglement does not necessitate the impossibility of classical simulation. For instance, you can prepare many highly entangled states using only Clifford circuits, which can be simulated efficiently by a classical computer, see Gottesman-Knill. Perhaps stick to just the claim that it's essentially due to "the way multiple qubits are combined". Jan 11 at 22:44
• Fair enough, I was using entanglement as a basic catch-all for combining qubits, since it's one of the two "pillars" that people talk about in QC, alongside superposition. I'll edit accordingly. Jan 11 at 23:07
• the edit looks good! Jan 12 at 14:17