arXiv:2610.00547
Unifying and Extending Strong Simulation of Quantum Circuits
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.
AI Summary
The paper asks whether structural and algebraic guarantees for exact classical circuit simulation can be expressed within one evaluation framework. It encodes transition amplitudes as functional aggregate queries (FAQs): gate tensors are factors, internal wire indices are summed out, and boundary indices are fixed or retained. InsideOut variable elimination supplies the common algorithm; intermediate-factor representations determine its cost. For explicitly listed factors of maximum support size $N$, a supplied decomposition of fractional width $w$ gives scalar evaluation in $\widetilde O(N^w)\operatorname{poly}(|Q|)$ time, recovering treewidth-based simulation and exposing sparsity-sensitive refinements. For quadratically compatible phase representations, evaluation over the formal phase ring $\mathbb R[\mathbb Z_r]$ recovers the $O(4^k\operatorname{poly}(|C|))$ amplitude bound given a phase-graph rank-decomposition of width $k$. Affine–quadratic factors instead remain polynomially sized under multiplication and marginalization, recovering exact Clifford amplitudes for every elimination order, including compact symbolic answers with free boundaries. The new criterion, tensor layout symmetry width, combines local phase-graph cut-rank with separator permutation symmetries. Exact tree-tensor representations and symmetry-derived rank bounds give a constructive tractability guarantee. A circuit family has this width at most two despite unbounded phase-graph rank-width and circuit line-graph treewidth. The phase-based results require quadratic compatibility. Structural evaluation bounds assume supplied decompositions or plans; explicit output tensors can remain exponentially large. The Clifford implementation has weaker quantitative bounds than specialized simulators. Extensions to broader gates, mixed representations, and efficient noisy or approximate simulation remain future work.
Error found: The final rewriting Note deletes the CNOT support constraint without performing its corresponding substitution, producing an expression that gives an incorrect circuit amplitude. Example 'tw-vs-fractional' incorrectly identifies the expanded circuit graph as K_n, so its stated justification of treewidth n−1 and the resulting quantitative comparison is invalid.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 50 pages