Classical methods unify and extend quantum circuit simulation techniques
Unifying and Extending Strong Simulation of Quantum Circuits
Data Structures and Algorithms
Summary
Simulating quantum circuits on classical computers is often very hard because of the circuits' complexity. The authors show that many existing simulation techniques can be expressed in one common framework called functional aggregate queries (FAQs), which breaks down circuits into factors and combines them efficiently. This approach reveals new ways to speed up simulations for certain kinds of circuits, including some that were previously hard to handle. Their framework also introduces a new measure to understand when simulations can be done efficiently, helping guide future classical simulations of quantum devices.
What this means in practice
- •For quantum algorithm developers: Predict classical simulation costs of quantum circuits to choose algorithms less likely to be efficiently simulated.
- •For quantum hardware testers: Verify outputs of certain quantum circuits by simulating them exactly with classical resources guided by the new simulation framework.
Tested on simulated data.
Authors
Floris Geerts, Rihan Hai, Matthias Lanzinger, Reinhard Pichler, Emanuel Sallinger, Daniel Unterberger
Abstract
We establish functional aggregate queries (FAQs) as a unifying language for exact classical simulation of quantum circuits. A circuit becomes a sum-product query: factors encode gates, internal wire variables are aggregated, and free boundary variables index transition amplitudes. The central insight is that distinct sources of simulation tractability can be exploited within the same InsideOut evaluation scheme. The query specifies what is computed; the evaluation plan, semiring, and representation of intermediate factors determine the cost. This view unifies structural and algebraic simulation guarantees. With explicit factor representations, FAQ evaluation recovers the treewidth bound for tensor-network contraction and yields finer sparsity-sensitive bounds via fractional covers. Over a formal phase semiring, compressed intermediate factors recover rank-width-based simulation for compatible quadratic phase representations. For Clifford circuits, affine-quadratic factors are closed under multiplication and marginalization and remain polynomial in size, yielding polynomial-time exact amplitude computation without any bounded-width assumption. Beyond these recoveries, the framework yields a new tractability criterion: tensor layout symmetry width. This parameter combines local cut-rank with separator symmetry through exact tree-tensor representations. We give a constructive evaluation bound and exhibit a circuit family with bounded tensor layout symmetry width but unbounded phase-graph rank-width and circuit line-graph treewidth. These results establish representation-aware FAQ evaluation as a common algorithmic foundation for classical simulation and a systematic route to new tractable regimes.