The standard approach to simulating a quantum circuit classically is straightforward but brutally inefficient: track the full state vector. For a system of $N$ qubits, this vector consists of $2^N$ complex amplitudes. Every time a gate is applied, the entire vector must be updated. By the time a circuit reaches roughly 45 to 50 qubits, storing this state vector requires petabytes of memory, hitting an insurmountable physical "memory wall."
To validate near-term quantum algorithms and verify circuit correctness without access to fault-tolerant quantum hardware, classical simulators must bypass this exponential storage requirement. A rapidly growing body of research achieves this by shifting the problem from tracking state vectors to contracting tensor networks and manipulating symbolic decision diagrams.
Shifting the Paradigm: From State Evolution to Network Contraction
Instead of maintaining a massive global state vector and evolving it step-by-step, we can treat an entire quantum circuit as a graph of interconnected tensors. In this view, state initializations are input tensors, quantum gates are intermediate tensors, and the wires connecting them represent shared indices (or tensor "legs").
The simulation problem then transforms from vector evolution into tensor network contraction—the process of multiplying these tensors together along their shared indices to compute specific output amplitudes or properties. As Allcock et al. demonstrate, this approach avoids exponential memory scaling entirely for circuits with moderate depth or specific connectivity patterns, enabling the simulation of systems with hundreds of qubits.
State Vector Simulation (Exponential Memory):
[Initial State] ---> [Gate 1] ---> [Gate 2] ---> [Full State Vector (2^N)]
Tensor Network Simulation (Graph Contraction):
(Input)---[Gate 1]---(Wire)---[Gate 2]---(Output) <-- Contract along wires
The computational complexity of this method is no longer dictated by the total number of qubits, but rather by the order in which the tensors are multiplied. Finding an efficient sequence is known as contraction path optimization. By mapping a quantum circuit to a line graph, Fried et al. show that graph-theoretic tree decomposition techniques can identify an optimal contraction sequence. By minimizing the "treewidth" of the decomposition, the simulator ensures that the intermediate tensors generated during computation remain small enough to fit into memory.
Exploiting Structure: Entanglement and Topology
Tensor network simulation works because physical quantum circuits rarely explore the entire, unstructured $2^N$-dimensional Hilbert space. Instead, they feature localized interactions and structured, limited entanglement.
When qubit interactions are restricted or low in entanglement, the global quantum state can be factorized into specialized tensor network topologies that act as low-rank approximations:
- Matrix Product States (MPS): For one-dimensional or low-depth topologies, states can be represented linearly. Because variational circuits for applications like quantum chemistry typically exhibit low entanglement, Shang et al. demonstrate that MPS representations can simulate chemical systems equivalent to 1,000 qubits in seconds, completely bypassing the state-vector memory wall.
- Tensor Rings: For more complex, cyclic entanglement patterns common in variational quantum classifiers and optimization algorithms, Patti et al. and Peddireddy et al. utilize factorized tensor rings. These cyclic structures capture non-local correlations efficiently, enabling exact classical simulations of large-scale optimization problems on near-term architectures.
Symbolic Compression via Tensor Decision Diagrams
Simulation is only half the challenge; verifying that a quantum circuit behaves correctly or matches its intended specification is equally critical. Even within a tensor network framework, representing quantum operations as dense matrices can quickly exhaust memory during formal verification.
To compress these representations, researchers developed Tensor Decision Diagrams (TDDs). As introduced by Hong et al., a TDD represents a tensor as a rooted, weighted, directed acyclic graph (DAG). It relies on a recursive decomposition based on the Boole-Shannon expansion adapted for tensors.
Dense Matrix Representation: Tensor Decision Diagram (TDD):
[ 1 0 0 0 ] (Root)
[ 0 1 0 0 ] / \
[ 0 0 0 1 ] [v1] [v2]
[ 0 0 1 0 ] \ /
(Shared Leaf)
*Identical sub-structures merge*
TDDs exploit the massive redundancies and structural symmetries inherent in quantum gates. If different sub-operations yield identical algebraic structures, the DAG merges those paths, caching intermediate results in a computed table. This symbolic compression allows for:
- Equivalence Checking: Determining if a noisy, physical circuit matches its ideal, noiseless counterpart (Hong et al.).
- Model Checking: Verifying quantum transition systems and assertion-based properties without state-space explosion (Mingsheng Ying; Ying et al.).
- Automated Rewriting: Preserving symbolic tensor structures rather than flattening them into matrices allows proof assistants like Coq to perform automated pattern matching and circuit simplification (Shi et al.).
Crucially, standard tensor contraction heuristics do not translate directly to these symbolic graphs. As Larsen et al. observe, specialized TDD contraction heuristics are required to preserve graph compression throughout the contraction process, preventing intermediate steps from exploding in size.
Scaling to Supercomputers and Distributed Hardware
When exact simulation pushes past the limits of a single machine, tensor networks offer natural pathways for parallelization via a technique called slicing. Slicing involves cutting chosen edges of the tensor network, breaking a single massive contraction down into thousands of independent, smaller contractions that can be distributed across cluster nodes or GPUs.
To minimize the computational overhead introduced by slicing, Yaojian Chen et al. developed a lifetime-based optimization method on the Sunway supercomputer. By tracking how long intermediate tensor dimensions persist across the computation, their framework minimizes redundant operations, scaling simulations across millions of cores. Furthermore, as evaluated by Vallero et al., tensor network methods scale exceptionally well on distributed GPU architectures when handling circuits with dense interconnections and high communication requirements.
Finally, tensor networks allow for structural path reuse. In workloads like quantum machine learning, the same circuit structure is executed repeatedly with varying data inputs. Kuan–Cheng Chen et al. demonstrate that optimizing the contraction path once and reusing it across thousands of data inputs drastically reduces simulation overhead. This optimization enables the practical validation of Quantum Support Vector Machines containing up to 784 qubits.
By treating quantum circuits as topological networks to be contracted or symbolic graphs to be simplified, this paradigm bypasses the state-vector memory wall, providing the foundational infrastructure needed to verify and scale the next generation of quantum algorithms.
Key Foundational Work
Model Checking for Verification of Quantum Circuits (2021) — contributed 2 concept elements to this direction.
Approximate Equivalence Checking of Noisy Quantum Circuits (2021) — contributed 2 concept elements to this direction.
qTorch: The quantum tensor contraction handler (2018) — contributed 2 concept elements to this direction.