Unifying and Extending Strong Simulation of Quantum Circuits

• Classical circuit simulation supports hardware calibration and benchmarking, while improved simulation can shift the boundary for claims of quantum advantage.Source: §1 · p. 3
• A circuit becomes a sum-product query: gate factors encode wire inputs and outputs, intermediate wire states are aggregated, and free boundary variables index amplitudes.Source: §1 · pp. 3–4
• InsideOut eliminates aggregated variables by multiplying their factors and summing over their values; its cost depends on the FAQ’s fractional hypertree width.The framework uses the same evaluation algorithm across different simulation approaches, with semirings and intermediate-factor representations determining how evaluation proceeds.Source: §1 · pp. 4–5
• FAQ evaluation recovers the treewidth bound and a rank-width bound using a phase semiring, with fractional hypertree width sometimes yielding a smaller bound than treewidth.The FAQ reconstruction of the rank-width bound is technically simpler and more compact than the original construction.Source: §1 · p. 5
• For Clifford circuits, affine-quadratic factors stay polynomial in size under InsideOut multiplication and aggregation, giving polynomial-time exact-amplitude computation without a bounded-width assumption.Source: §1 · p. 5
• Tensor layout symmetry width combines local rank-width with a global measure of interaction, and is strictly more general than treewidth and rank-width approaches.The paper exhibits circuits with tensor layout symmetry width at most 2 despite unbounded treewidth and rank-width.Source: §1 · p. 6

2.1 Functional aggregate queries

• An FAQ combines factors with semiring operations, aggregating bound variables while free variables index the resulting factor.The factor scopes record variable interactions independently of factor values and representations.Source: §2 · p. 6, §2.1 · pp. 6–7

2.2 Quantum circuits and simulation

• Strong simulation computes the exact transition amplitude ⟨y|UC|x⟩; its squared magnitude is the probability of observing y.The section allows arbitrary computational-basis input and output assignments.Source: §2.2 · p. 8

2.3 Quantum circuits as FAQs

• Gate factors over wire-segment variables multiply, and summing internal indices contracts them while boundary factors select the input and output assignments.The resulting scalar FAQ equals the transition amplitude.Source: §2.3 · pp. 8–9
• Leaving input, output, or both boundaries free yields the state coefficients, a matrix row, or the full computational-basis matrix of the circuit.The FAQ's free variables identify the corresponding output coordinates.Source: §2.3 · pp. 9–10

2.4 Rewriting FAQs with functional dependencies

• Gate-support functional dependencies can eliminate determined bound variables, but substitutions may enlarge the scopes of other factors.In the example, substitutions reduce six original bound variables to one, while increasing one Hadamard factor's scope.Source: §2.4 · pp. 10–12

3 FAQ evaluation and InsideOut

• InsideOut is semiring-valued variable elimination: it multiplies factors containing a variable, aggregates that variable, and replaces the bucket with a message.Distributivity justifies pushing aggregation through the product.Source: §3 · pp. 12–13

3.1 The InsideOut algorithm

• The elimination order affects evaluation cost but not the query value; free variables remain arguments of the result.Each message summarizes consumed factors as a function of their remaining variables.Source: §3.1 · p. 13
• Sparse evaluators can use indicator projections of outside factors to restrict assignments to those extending to supported tuples.Such projections filter message computation without changing the variables being eliminated.Source: §3.1 · p. 13
• InsideOut can return the FAQ answer as a factorized representation instead of materializing a single full table.Variables can also be eliminated in batches, with every active factor touching the batch included in its block message.Source: §3.1 · p. 14

Explicit evaluation and fractional hypertree width

• Support-listed FAQ factors admit a fractional-width evaluation bound that computes a factorized output representation, with scalar evaluation as the empty-free-variable case.For free variables, the stated output-sensitive bound also depends on the output support size.Source: §4 · p. 15

Recovering the Markov–Shi bound

• The FAQ formulation recovers the Markov–Shi treewidth bound, while fractional hypertree width can be strictly lower and yield runtime improvements.The comparison uses a circuit graph tree decomposition to bound the FAQ hypergraph's fractional width.Source: §4 · pp. 15–16

Measurement probabilities

• Pairing amplitude and conjugate-amplitude wire indices extends the same graph-width argument to measurement probabilities without changing the factor scopes or widths.Unobserved outputs are traced out by enforcing equality between the paired indices.Source: §4 · p. 16

Example: functional dependencies

• Functional dependencies among Toffoli-factor variables simplify the three-data-qubit FAQ to a single-bag decomposition with fractional width 3/2.The example assigns weight 1/2 to each of the three Toffoli hyperedges.Source: §4 · pp. 16–17

Example: fractional width versus treewidth

• For the clique circuit family, circuit-graph treewidth is n−1 whereas the reduced FAQ has fractional hypertree width n/2.The reduced FAQ's fractional edge cover assigns weight 1/(n−1) to each T-edge.Source: §4 · p. 17

5.3 Evaluation and rank-width bound

• For fixed computational-basis boundaries, compatible quadratic phase representations permit amplitude evaluation in O(4^k poly(|C|)) time given a width-k rank-decomposition of the phase graph.The evaluation applies to the FD-reduced circuit FAQ over the formal phase semiring.Source: §5 · p. 17, §5.3 · p. 22

5.1 Quantum circuits over compatible gate sets

• A gate is quadratically r-compatible when its FD-reduced factor has a full-support quadratic K_r representation with pairwise terms of coefficient r/2.The gate set {H, T, CZ} is given as quadratically 8-compatible.Source: §5.1 · pp. 18–19

5.2 The phase graph and rank-width

• The phase graph records parity of quadratic interactions among variables, and its rank-width bounds the cut-rank across branches of a rank-decomposition.Isolated variables remain vertices, while repeated quadratic terms cancel.Source: §5.2 · p. 20

5.3 Evaluation and rank-width bound

• InsideOut eliminates rank-decomposition branches while keeping each branch message as a small K_r-expression, with at most r2^k distinct phase terms.The bound follows because the crossing-interaction parity vectors have at most 2^k values; the resulting scalar amplitude is recovered after evaluation.Source: §5.3 · pp. 21–23
• The scalar amplitude theorem does not bound the size of a symbolic output representation with free boundary variables.Materializing a full output tensor on f free Boolean variables requires writing 2^f entries.Source: §5.3 · p. 22

6 Tensor compression and separator symmetries

• A message with 2^k phase-monomial terms can have an exact TTN with O(k) arrays and bounded bond dimension.This illustrates how a compact tensor representation can capture separator-message symmetry even when its phase-monomial representation is large.Source: §6 · p. 24

6.1 Phase coefficient tensors

• A phase coefficient tensor stores an atom’s Kr-values as real coordinates indexed by Boolean assignments and a residue, with factor multiplication given by residue convolution and aggregation by Boolean summation.These operations match the product and marginalization updates used by InsideOut.Source: §6.1 · p. 25

6.2 Exact TTN representations

• An exact TTN can be reduced to maximum bond dimension at most max{r, DR(A)} in polynomial time; TTN multiplication and Boolean-variable marginalization are also constructible.The reduction uses the ranks of coefficient-tensor flattenings, while multiplication and marginalization implement the operations needed by InsideOut.Source: §6.2 · pp. 26–27

6.3 Local factors on a tree decomposition

• Each bag tensor has an exact TTN with maximum bond dimension at most r^2ρt(R), encoding internal phase residues and interaction signatures across layout cuts.The bond dimensions are bounded by r^2 times the maximum local cut-rank parameter ρt(R).Source: §6.3 · pp. 28–29
• For the child-bag example, summing the ai legs yields an exact coefficient-tensor TTN with maximum bond dimension 16 despite 2k phase monomials.The construction uses O(k) arrays, and the two top bonds have dimension 8.Source: §6.3 · p. 30

6.4 Updating across separators

• Within each separator symmetry class, messages depend only on the number of variables assigned 1, so the number of classes bounds separator-message ranks.Permutations within classes preserve the message; the symmetry bound converts that invariance into rank bounds for coefficient layouts.Source: §6.4 · pp. 31–32

6.5 Tensor layout symmetry width and evaluation

• Theorem 6.10 computes exact circuit amplitudes by constructing bag tensor trains from local cut-rank and compressing separator messages using symmetry bounds.For a reduced plan, each update multiplies the local factor by child messages, sums out internal variables, then compresses the message before passing it upward.Source: §6.5 · p. 33
• The analysis relates TLSW to phase-graph rank-width and circuit-graph treewidth; for gates acting on at most a qubits, the circuit-graph maximum degree is at most 2a.The bounds use a plan with an empty separator for the rank-width comparison and relate the circuit line graph to the circuit graph.Source: §6.5 · pp. 33–34
• The clique-chain family shows that bounded TLSW does not require bounded phase-graph rank-width or circuit-graph treewidth.Theorem 6.12 gives the separation for its circuit family with K8 gate lifts.Source: §6.5 · p. 34

7.1 The affine–quadratic representation

• An AQ factor combines an affine-support constraint with a quadratic phase and a scalar over an exact coefficient ring.The representation is closed under the multiplication and aggregation operations used to form InsideOut messages.Source: §7.1 · p. 35

7.2 AQ bag evaluation

• The AQ implementation of (36) has total nonscalar cost O((b + 1)(w + 1)^3) when p ≤ w, apart from exact scalar arithmetic.Source: §7.2 · pp. 35–36
• When affine support determines an eliminated variable, AQ aggregation substitutes it; otherwise, interference can create a new support constraint without enumerating assignments.For two successive Hadamards, destructive interference yields the constraint x = y.Source: §7.2 · p. 36

7.3 Evaluation and output guarantees

• For every bound-variable ordering, AQ-FAQ evaluation computes an exact polynomial-size encoding in polynomial time.Theorem 7.2 gives a bound in terms of input encoding length and variable count, including exact scalar arithmetic.Source: §7.3 · p. 36
• The output is an AQ encoding rather than an explicit table, which matters because |Y| free variables may have 2^|Y| nonzero answers.The symbolic output remains polynomial in size even when the table could be exponentially large.Source: §7.3 · p. 36

7.4 Clifford circuits

• Clifford circuit FAQs are evaluable in polynomial time for every elimination order, including when any subset of input or output boundary variables is fixed.With all boundaries fixed, the output is the exact amplitude; with free boundaries, it is an AQ encoding.Source: §7.4 · p. 37
• The guarantee is elimination-order-independent, but it does not give the sharper worst-case bounds achieved by specialized Clifford simulators.The paper cites O((m + 1)n^2) and O(mn^(ω−1)) bounds for specialized methods and notes that sharper AQ bounds would require more refined evaluation.Source: §7.4 · p. 37

Tensor networks and graphical models

• Tensor-network contraction has treewidth-based complexity, while low-entanglement and tree-tensor methods also exploit compressed intermediate tensors.The paper emphasizes that width comparisons must specify both the measured graph and the representation of intermediate tensors.Source: §8 · p. 38

Path sums, exponential sums, and model counting

• Path-sum and weighted-model-counting methods aggregate weighted classical assignments, but expose different intermediate objects.For quadratic SOPs, the paper reduces the circuit FAQ and retains phase contributions over a phase semiring before recovering the complex answer.Source: §8 · p. 38

Decision diagrams and cut-rank compression

• Decision-diagram and quadratic-SOP methods use rank-width, and the paper recovers a rank-width guarantee in InsideOut using phase-monomial messages.The relevant phase graph is extracted after reductions required by the compatibility assumptions.Source: §8 · p. 38

Clifford simulation and affine–quadratic factors

• Stabilizer amplitudes have tableau and affine-quadratic descriptions, while this paper implements affine-quadratic closure through FAQ factors for arbitrary scopes.The FAQ evaluator supports polynomial-size messages under every bound-variable ordering and symbolic outputs for free variables.Source: §8 · p. 39

Stabilizer decompositions and hybrid representations

• Hybrid approaches combine stabilizer decompositions with non-Clifford resources, while FAQ evaluation separates sum-product semantics from the representations used for intermediate factors.The paper presents concrete instances of this interface, not a general conversion between all simulation representations.Source: §8 · p. 39

Database techniques for quantum computing

• Database-oriented work represents circuits as relations or queries; this paper makes support processing and intermediate-function representations explicit within FAQ evaluation.Examples in the related work include SQL-based simulation, workloads and planning, and conjunctive-query complexity analyses.Source: §8 · pp. 38–39

Conclusion

• Explicit-factor FAQs recover the Markov–Shi treewidth bound and yield stronger exponent bounds using functional dependencies and fractional edge covers.The explicit factors are represented by indexed listings of their nonzero entries.Source: §9 · p. 40
• A formal phase semiring gives an FAQ upper bound in terms of fractional hypertree-width that is never worse than the cited rank-width upper bound for compatible circuits.The conclusion describes this reconstruction as technically simpler and more compact than the earlier construction.Source: §9 · p. 40
• Tensor layout symmetry width combines the earlier approaches and is strictly more general than their treewidth and rank-width criteria.The paper exhibits circuits with tlsw at most 2 despite unbounded treewidth and rank-width.Source: §9 · p. 40
• For circuits over {H, S, CNOT} with computational-basis boundaries, applying InsideOut to the standard FAQ recovers the exact-amplitude consequence of Gottesman–Knill [Aaronson and Gottesman, 2004].The result uses affine-quadratic factors and does not require a width bound.Source: §9 · p. 40

Beyond quadratically compatible gate sets

• The rank-width and tensor-layout-symmetry results assume quadratically r-compatible gate sets, motivating investigation of relaxed conditions for gates such as fSim(π/2, π/6).The conclusion notes that this compatibility limitation also occurs in prior rank-width work.Source: §9 · pp. 40–41

Faster and more general AQ evaluation

• The presented affine-quadratic evaluation is less efficient in worst-case complexity than specialized Clifford simulation, and extending it beyond Clifford circuits remains an open direction.The conclusion suggests investigating faster FAQ evaluation and combinations with stabilizer-rank techniques.Source: §9 · p. 41

Noisy quantum circuits

• Efficient simulation of realistic noisy circuits remains a challenge, despite FAQs' ability to accommodate quantum channels through density-matrix encodings.Noise-aware representations and approximate FAQ evaluation are identified as possible directions.Source: §9 · p. 41

A Proof of the clique-chain separation

• The appendix establishes the three bounds in Theorem 6.12 and states the stronger lower bound lrw(PC(n)) ≥ n/2.The passage identifies the latter as a linear-rank-width bound.Source: A Proof of the clique-chain separation · p. 47

A.1 Circuit family and phase graph

• Identifying wire-segment variables through each Z_n; T_n repetition gives v_i,j, with Hadamard factors connecting the input, successive repetitions, and output.Source: §A.1 · p. 47
• For C(n), the phase graph G_n is a chain of n cliques of size n, with a perfect matching between consecutive cliques.Source: §A.1 · p. 47
• Figure 5 depicts C′(4, 3), with each dashed box marking one occurrence of B_4 = Z_4; T_4; H_4.Source: Figure 5 · p. 47

A.2 Bounded tensor layout symmetry width

• For n ≥ 3, the constructed plan P satisfies ρ(P) ≤ 1 and q(P) ≤ 2.Source: §A.2 · pp. 47–48
• For n ≥ 3, the unary coefficients are r/8 or 5r/8, so equal-coefficient classes—and thus any fixed plan’s TLSW profile—are independent of r.Source: §A.2 · p. 47
• The coefficient layout groups variables by qubit in a recursively refined binary-tree layout, and the evaluation plan processes adjacent clique bags along a path.Source: §A.2 · p. 48
• Local cut-rank stays at most one because cuts either isolate a singleton or separate unions of matching pairs, while clique cross-adjacency has rank at most one over F2.Source: §A.2 · p. 48
• When input bits match, exchanging their qubit variables preserves separator equivalence, leaving at most two symmetry classes before the final bag.Source: §A.2 · p. 48

A.3 Treewidth of the circuit graph

• For every n ≥ 2, tw(G_C(n)) ≥ n/4 − 1.Source: §A.3 · p. 48
• Contracting wire-segment edges at the CZ gates in one Z_n block produces a K_n minor in the circuit line graph.Source: §A.3 · p. 48
• Because the circuit graph has maximum degree four, the line-graph comparison yields the stated treewidth lower bound.Source: §A.3 · p. 48

A.4 Rank-width of the phase graph

• The lower-bound argument uses a balanced cut: it gains rank from split cliques, or from matching-edge crossings when a block is unsplit.Source: §A.4 · pp. 49–50
• If m variable blocks are split by a partition, the cut-rank is at least m/2, using an identity submatrix formed from alternating split blocks.Source: §A.4 · p. 49
• For every n ≥ 2, lrw(G_n) ≥ n/2, and for every n ≥ 3, rw(G_n) ≥ n/3.Source: §A.4 · p. 50
• For rank-width, a subcubic decomposition tree has a balanced edge cut, after which the split-block and unsplit-block cases give the n/3 bound.Source: §A.4 · p. 50