Statevector Simulation

A statevector simulator stores every amplitude of a finite pure quantum state and updates them under gates. Its arithmetic can be accurate to roundoff while its memory cost grows exponentially. The implementation challenge is to apply local gates without constructing dense full-register matrices.

Helpful background. Tensor products in code establishes index maps; measurement sampling treats outcomes.

Amplitude-pair kernels

Use $n$ qubits and integer index $s=\sum_j2^jb_j$, with qubit 0 the least significant bit. For a one-qubit gate $U$ on qubit $j$, pair each index $s$ with bit $j=0$ with $s'=s+2^j$:

$$\begin{pmatrix}\psi'_s\\\psi'_{s'}\end{pmatrix} =U\begin{pmatrix}\psi_s\\\psi_{s'}\end{pmatrix}.$$

Load both old amplitudes before overwriting either. This gives $2^{n-1}$ small matrix-vector operations. A controlled gate applies the same update only when the control bits have the requested values.

For a $k$-qubit gate, group $2^k$ amplitudes for each assignment of spectator bits. The order of target bits defines the local matrix order. A two-qubit matrix documented as acting on $(a,b)$ cannot be silently applied to $(b,a)$.

A transparent reference kernel for one target and controls conditioned on bit value one is:

import numpy as np

def gate_action(psi, gate, target, controls=()):
    psi = np.asarray(psi)
    gate = np.asarray(gate)
    size = psi.size
    if psi.ndim != 1 or size == 0 or size & (size - 1):
        raise ValueError("State length must be a positive power of two")
    n = size.bit_length() - 1
    if (gate.shape != (2, 2) or target not in range(n)
            or any(c not in range(n) for c in controls)
            or target in controls or len(set(controls)) != len(controls)):
        raise ValueError("Invalid gate shape or target/control indices")
    out = psi.astype(np.result_type(psi.dtype, gate.dtype), copy=True)
    bit = 1 << target
    mask = sum(1 << c for c in controls)
    for s in range(size):
        if not s & bit and s & mask == mask:
            a, b = out[s], out[s | bit]
            out[s] = gate[0, 0] * a + gate[0, 1] * b
            out[s | bit] = gate[1, 0] * a + gate[1, 1] * b
    return out

Each amplitude belongs to at most one updated pair, so copying its two old values is sufficient. This pedagogical kernel prioritizes transparent indexing; production kernels usually vectorize or compile the loop. It preserves norm when the gate is unitary, but deliberately does not renormalize arbitrary linear operators and thereby hide errors. Verify distinct control and target roles using asymmetric inputs, not only the Bell circuit below.

Bell circuit and ordering checks

Initialize $|00\rangle$, apply Hadamard to qubit 0, then controlled-$X$ with control 0 and target 1. The final amplitudes are

$$\psi=\frac1{\sqrt2}(1,0,0,1).$$

This verifies entanglement creation but does not distinguish all ordering conventions because the result is symmetric. Supplement it with $X$ on qubit 0 alone, which produces integer index 1, and $X$ on qubit 1 alone, which produces index 2.

A phase gate on a populated branch tests complex arithmetic. For example, applying $\operatorname{diag}(1,i)$ to qubit 0 of the Bell state gives $(1,0,0,i)/\sqrt2$. Probabilities are unchanged, so test amplitudes or interference after a later gate.

Memory and bandwidth

Complex double storage is $16\,2^n$ bytes. At 30 qubits one vector uses 16 GiB; work arrays can double or triple that. This is a storage calculation, not a claim that every 16 GiB machine can run the simulation.

Small-gate kernels often move more memory than their arithmetic cost suggests. Gate fusion can reduce passes through the vector, but an excessively large fused gate increases matrix storage and arithmetic. Benchmark the actual gate pattern and target-bit distribution.

Distributed statevectors require communication for gates acting on bits encoded in the process index. Reordering logical qubits can change communication cost, but the mapping must remain visible to measurement and output routines.

Verification and comparison

Check norm preservation and compare local kernels against dense matrices on small registers. Apply a circuit followed by its exact inverse, including reversed gate order. A norm test alone cannot distinguish a wrong unitary from the intended one.

Two statevectors representing the same pure state can differ by global phase. Compare fidelity $|\langle\phi|\psi\rangle|^2$ or align phase before taking a vector norm. For nearly orthogonal states phase alignment is unstable, so use fidelity or projector distance.

Sampling random pure states improves coverage but does not replace basis-vector tests of a linear kernel. Testing every computational basis vector for a small gate establishes all columns of its action.

Exercise

Estimate how many additional qubits fit when available memory doubles, and explain why reduced precision cannot remove exponential scaling.

Solution

Doubling memory permits one additional qubit at fixed representation and workspace ratio. Halving bytes per amplitude likewise saves approximately one qubit. Reduced precision may be useful if its accumulated error is acceptable, but the $2^n$ number of amplitudes remains.

References

• Häner, T., and Steiger, D. S., “0.5 petabyte simulation of a 45-qubit quantum circuit,” Proceedings of SC17, article 33 (2017), arXiv:1704.01127 — statevector memory and distributed gate kernels.
• Watrous, J., The Theory of Quantum Information, Cambridge University Press (2018), author’s text — circuit and state conventions.