Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation
Alexis de Colnet, Floris Geerts, Rihan Hai, Alfons Laarman, Joon Hyung Lee, Guillermo A. Pérez · 2026
Read Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation by Alexis de Colnet, Floris Geerts, Rihan Hai, Alfons Laarman, Joon Hyung Lee, Guillermo A. Pérez (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29944.txt.
Introduction
Alexis de Colnet and five colleagues simulate quantum circuits by summing Feynman paths over Boolean path variables forming a graph. For a quadratic sum with even modulus and width-k rank decomposition, their program computes an amplitude in a modest exponential in k times polynomial steps. Clifford-plus-T circuits sit at modulus eight, with rank-width never topping linear rank-width. A stabilizer-rank tweak using Gauss-sum tables keeps cost at the same bound, yet turns polynomial on mixed families where pure guarantees blow up.
Catalog record
| CREATOR | Alexis de Colnet, Floris Geerts, Rihan Hai, Alfons Laarman, Joon Hyung Lee, Guillermo A. Pérez |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66263 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29944
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation Thanks: This work was supported by the FWO/NWO KR2iQS project (G076326N), a collaboration between the University of Antwerp and Leiden University. Alexis de Colnet, Floris Geerts, Rihan Hai, Alfons Laarman, Joon Hyung Lee, Guillermo A. Pérez Abstract Strongly simulating a quantum circuit, that is, computing an output amplitude, amounts to summing the circuit’s Feynman paths, a weighted count over assignments to the Boolean “path” variables. The circuit’s gates induce correlations among these variables, forming a graph whose structure determines the hardness of the simulation task. This sum-of-powers viewpoint underlies recent simulators built on knowledge-representation tools from artificial intelligence, namely binary decision diagrams and weighted model counting. We show that the structural quantity most accurately governing the difficulty is the rank-width of the path-variable graph, and we give an algorithm that evaluates the amplitude in time that is exponential only in this rank-width and polynomial in the circuit size. Rank-width can be far smaller than the widths that control competing methods: as corollaries, our algorithm reproduces a recent decision-diagram simulation breakthrough as a special case and matches the Markov–Shi tensor-network contraction bound. To complement this, we exhibit circuit families on which our algorithm provably beats both competing methods. The new method applies to every circuit built from Hadamard and diagonal gates, in particular to circuits over Clifford + T +\mathrm{T} . In practical terms, general-purpose decision-diagram and model-counting tools can serve as the workhorse, with our specialized algorithm dispatched to exploit a small rank-width of the associated graph when it is present. 1 Introduction Classical strong simulation of quantum circuits remains indispensable: it forms a basis for circuit compilation and optimization pipelines, aids the study of noise in actual hardware, and helps triangulate truly quantum-hard regimes that are infeasible for classical machines. The difficulty lies in the fact that an n -qubit state is described by 2^{n} amplitudes; therefore, a useful simulator must exploit structure rather than represent the state naively. Tensor-network contraction gives a standard route to strong simulation of quantum circuits. If N_{C} is the tensor-network graph of a circuit C , with tensor vertices and shared indices as edges, then a contraction order is naturally governed by the treewidth of the line graph L(N_{C}) of N_{C} . We write \operatorname{cc}(N_{C})=\operatorname{tw}(L(N_{C})) for this contraction complexity. The Markov–Shi simulation bound is single-exponential in the corresponding tensor-network width parameter [ 14 ] and linear in the circuit size. The route we develop instead is the sum-of-powers (SOP): the expression of an amplitude as a sum over Feynman paths. This representation is classical [ 8 ] , but it has recently been turned into competitive simulators by encoding it with knowledge-representation tools from artificial intelligence: e.g. binary decision diagrams, in FeynmanDD [ 24 , 4 ] , and weighted model counting [ 23 , 15 , 20 , 12 ] . Fixing the circuit’s input \bm{y} and output \bm{z} turns the circuit into a scalar Z=\frac{1}{R}\sum_{\bm{x}\in\{0,1\}^{V}}\omega_{r}^{f(\bm{x})}, a sum of roots of unity over assignments to a set V of Boolean path variables; the exponent f is a degree-two polynomial: a constant, one linear term per variable, and a quadratic sign term for each interacting pair of variables (for \{\mathrm{H},\mathrm{T},\mathrm{CZ}\} the modulus is r=8 , see Section 3 ). The interacting pairs form the SOP variable graph G_{C}=(V,E) , and the difficulty of evaluating Z is concentrated in the structure of this graph. Our main result is that the right structural measure of G_{C} is its rank-width , a branching width parameter from structural graph theory. We give a dynamic program ( Section 4 ) that evaluates Z , hence the amplitude, in time exponential only in the rank-width of G_{C} and polynomial in the circuit size. Contributions. We establish the following based on parameters in Table 1 : 1. We give an explicit rank-decomposition dynamic program for quadratic SOPs, running in time O(nr4^{k}\operatorname{poly}(n)+r\log r) on an n -variable graph of rank-width k and modulus r ( Theorem 2 , Theorem 3 ), when provided with a rank-width decomposition. Applied to circuits over Hadamard and diagonal gates, this is a rank-width fixed-parameter strong simulation algorithm ( Section 6 ). On the way, we also expose a treewidth fixed-parameter strong simulation algorithm by combining the insight that G_{C} is the “primal graph” of the SOP with classical graphical-model algorithms ( Section 3.2 ). 2. We relate the SOP variable graph to the parameters of the tensor-network and decision-diagram approaches: G_{C} is a minor of the tensor line graph, giving \operatorname{tw}(G_{C})\leq\operatorname{cc}(N_{C}) ( Lemma 1 ) and \operatorname{rw}(G_{C})\leq\operatorname{cc}(N_{C})+1 [ 18 ] ; and since rank-width is at most linear rank-width, we recover the decision-diagram guarantee of [ 4 ] ( Corollary 1 ) as a special case. 3. We construct circuit families with \operatorname{rw}(G_{C})=O(1) while \operatorname{lrw}(G_{C}) and \operatorname{cc}(N_{C}) are unbounded ( Corollary 2 ), explicitly separating the rank-width, linear-rank-width, and treewidth approaches. On these families, our rankwidth-parameterized algorithm runs with fixed polynomial overhead, whereas decision-diagram and tensor-network guarantees both degrade. Although we state the construction for the \{\mathrm{H},\mathrm{T},\mathrm{CZ}\} gate set, it requires only that the Hadamard gate is the sole non-diagonal single-qubit gate. In fact, arbitrary diagonal single-qubit gates contribute linear terms but leave G_{C} unchanged. The results therefore cover every circuit over Hadamard, \mathrm{CZ} , and arbitrary phase rotation gates, and in particular all of Clifford +\mathrm{T} ( Section 6.2 ). Table 1 : Graph objects used in the paper. Treewidth travels from tensor network to the SOP variable graph via L(N_{C}) ; rank-width is used directly on G_{C} . Graph Definition Relation used here N_{C} Tensor-network graph: tensors are vertices and shared indices are edges. Tensor contraction is measured through the line graph. For bounded tensor arity \Delta , \operatorname{tw}(L(N_{C}))\leq\Delta(\operatorname{tw}(N_{C})+1)-1 . L(N_{C}) Line graph of N_{C} : vertices are the bond indices (edges of N_{C} ); adjacency means co-occurrence in a tensor. \operatorname{cc}(N_{C})=\operatorname{tw}(L(N_{C})) . The SOP variable graph G_{C} is a minor of L(N_{C}) . G_{C} SOP variable graph: vertices are the SOP variables V ; edges are the quadratic cross-terms \{u,v\}\in E in f . The rank-width dynamic-programming algorithm (DP) runs on this graph. Also \operatorname{tw}(G_{C})\leq\operatorname{cc}(N_{C}) . Other related work. Weighted model counting has recently been proposed as a general framework for quantum physics computations, including partition functions [ 23 ] ; the present work uses such encodings as one practical route and contributes a rank-width fixed-parameter algorithm for the underlying SOP. Recent and independent work has also identified rank-width as a useful parameter for quantum-circuit simulation, mainly through ZX-calculus and stabilizer-decomposition methods. Kuyanov and Kissinger [ 13 ] give a contraction algorithm for graph-like ZX diagrams whose claimed running time is \widetilde{O}(4^{R}) given a rank-decomposition of width R . Codsi and Laakkonen [ 5 ] develop a framework connecting graph-width measures and stabilizer decompositions, obtaining slice-wise polynomial-time algorithms parameterized by treewidth or rank-width of an associated tensor network together with the number of non-Clifford operations. These results are complementary to ours: they show, from a ZX/tensor-network perspective, that rank-width is a natural structural parameter for simulation. Our contribution is different in that we work directly with the quadratic SOP representation underlying FeynmanDD-style simulation; give an explicit DP that runs on a rank-decomposition of the SOP