Unifying and Extending Strong Simulation of Quantum Circuits
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.
Related
- Strong Simulation of 1D Quantum Circuits via Reduced Transition Matrices
- Quantum simulation of classical RCL circuits via complexification and Schrödingerization
- Quantum Simulation of a Hyperbolically Driven Quantum System with Superconducting Circuits
- Complexity of tensor network simulation for noisy quantum circuits
- GPU-Accelerated Quantum Simulation of Stabilizer Circuits
BibTeX
@misc{geerts2026unifying,
title = {{Unifying and Extending Strong Simulation of Quantum Circuits}},
author = {Floris Geerts and Rihan Hai and Matthias Lanzinger and Reinhard Pichler and Emanuel Sallinger and Daniel Unterberger},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00547},
eprint = {2610.00547},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00547},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Unifying and Extending Strong Simulation of Quantum Circuits
AU - Floris Geerts
AU - Rihan Hai
AU - Matthias Lanzinger
AU - Reinhard Pichler
AU - Emanuel Sallinger
AU - Daniel Unterberger
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00547
UR - https://arxiv.org/abs/2610.00547
AB - 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.
ER -