Why Does an n-Qubit State Vector Need 2^n Amplitudes?

Simulating an n-qubit quantum state vector on classical hardware requires storing 2^n complex amplitudes because quantum mechanics describes a system of n qubits as a superposition over all possible classical bitstrings of length n simultaneously. Unlike classical bits, which each occupy a single definite state, qubits exist in a combined state space whose dimension grows exponentially with every additional qubit.

Classical Bits vs. Quantum Bits

A classical register of \(n\) bits can only be in one of \(2^n\) possible configurations at any given moment, such as 0101. To represent that state in memory, a classical computer only needs \(n\) bits.

A single qubit, however, exists in a linear combination (superposition) of both basis states, \(|0\rangle\) and \(|1\rangle\):

\[|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\]

Here, \(\alpha\) and \(\beta\) are complex numbers called probability amplitudes, subject to the normalization condition \(|\alpha|^2 + |\beta|^2 = 1\). Even for \(n = 1\), a classical simulator must store \(2^1 = 2\) complex numbers.

The Tensor Product and Exponential Growth

When multiple qubits are combined into a single quantum system, their joint state space is formed by the tensor product (\(\otimes\)) of their individual state spaces. For two qubits, the combined basis consists of \(2 \times 2 = 4\) states: \(|00\rangle\), \(|01\rangle\), \(|10\rangle\), and \(|11\rangle\).

In general, an \(n\)-qubit state vector \(|\Psi\rangle\) is written as:

\[|\Psi\rangle = \sum_{x \in \{0,1\}^n} c_x |x\rangle\]

Each of the \(2^n\) basis states \(|x\rangle\) has its own independent complex amplitude \(c_x\). Adding just one more qubit doubles the number of basis states and therefore doubles the number of complex amplitudes required to describe the system.

Why Entanglement Prevents Compression

If qubits were always independent (unentangled), an \(n\)-qubit state could be written as a simple product of \(n\) single-qubit states, requiring only \(2n\) complex numbers. However, quantum gates such as the CNOT gate create entanglement, meaning the joint state can no longer be factored into separate single-qubit states.

Because arbitrary quantum circuits can generate entangled states where every amplitude \(c_x\) carries correlated information about all \(n\) qubits, a general-purpose state-vector simulator cannot compress the representation. It must track all \(2^n\) complex amplitudes explicitly in memory.

Practical Memory Limits on Classical Hardware

Each complex amplitude is typically stored as two 64-bit floating-point numbers (16 bytes total in double precision). The memory required for \(n\) qubits is therefore:

\[\text{Memory} = 16 \times 2^n \text{ bytes}\]

For \(n = 30\) qubits, this requires \(16 \times 2^{30}\) bytes, or \(16\text{ GiB}\) of RAM, which fits on a standard workstation. By \(n = 40\) qubits, the requirement jumps to \(16\text{ TiB}\), and by \(n = 50\) qubits, it reaches \(16\text{ PiB}\), exceeding the memory capacity of most supercomputers.