Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses

1.2. Local-profile complexity.

• The framework represents states by weight-p Pauli expectations, controls class energy through profile metric entropy, and uses conditioning adapted from a nonsymmetric quantum de Finetti theorem.The conditioning construction makes product states a benchmark for every state class.Source: §1 · p. 3, §1.2 · p. 6

1. Introduction

• The framework gives energy lower bounds for reverse magic and every fixed higher magic-hierarchy level; sublinear-T Clifford+T circuits cannot beat product stabilizer states at leading order.The Clifford+T comparison permits unrestricted Clifford operations and arbitrary discardable ancillas.Source: §1 · p. 4

1.2. Local-profile complexity.

• For sufficiently large fixed p, classes with bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of √n.The paper identifies quadratic profile complexity as too small to approach the unrestricted optimum.Source: §1.2 · p. 6
• At subquadratic effective profile complexity, a class cannot outperform its conditioning benchmark at the leading √n energy scale; product states provide a universal benchmark.Sharper benchmarks can yield stronger comparisons for structured classes.Source: §1.2 · p. 6

1.3. Circuit size and depth.

• Circuit classes need nearly quadratically many one- and two-qubit gates for a leading-order advantage, while ground-state separation persists up to a fixed-constant multiple of n^2/log n gates.These bounds allow arbitrary discardable ancillas; for circuits of width O(n), separation holds up to depth O(n/log n), and the product-state comparison applies below that depth scale.Source: §1.3 · p. 7
• For total width O(n), depth Ω(n/log n) is required to approach the ground-state energy, while depth o(n/log n) yields only o(√n) improvement over product states.A continuous depth-workspace tradeoff also gives logarithmic-depth product-state comparison with arbitrary discardable ancillas.Source: §1.3 · p. 7
• Near-ground states require entangled components of essentially logarithmic size; under a stronger little-o condition, smaller entangled blocks provide no leading-order advantage over product states.The bounds remain valid when each block uses arbitrarily many discardable ancillas.Source: §1.3 · p. 8

1.4. Matrix product states.

• MPS require asymptotically growing bond dimension to reach low energy, and under the stated little-o condition have no leading-order advantage over product states.The results also hold for convex mixtures and state-dependent orderings of the physical qubits.Source: §1.4 · p. 8

1.5. The magic hierarchy.

• First-level forward magic with discardable ancillas has the product-state benchmark for D_n ≤ c log^2 n, while reverse magic allows arbitrarily many clean ancillas at each fixed depth.For forward magic, c may be any fixed value in (0, 1/2); for reverse magic with clean ancillas, the required interaction order p may depend on the fixed depth.Source: §1.5 · p. 9
• At every fixed magic-hierarchy level, both orientations with total width O(n) satisfy the ground-state obstruction when D_n ≤ L n/log n for sufficiently large n.The result extends energy lower bounds to both orientations at every fixed level, including classes where Clifford operations can spread observables beyond local lightcones.Source: §1.5 · p. 9

1.6. Stabilizer states and Clifford+T circuits.

• For any fixed finite T-gate density, sufficiently large fixed p forces an order-√n separation from the unrestricted optimum, with the required p threshold depending on the density.The obstruction holds uniformly over arbitrary discardable workspace.Source: §1.6 · pp. 10–11
• With t_n = o(n), Clifford+T circuits have no leading-order energy advantage over product stabilizer states, even with arbitrary discardable ancillas; their sharp large-p normalized energy is √(2 log 6).The sublinear T-count is measured against the number n of retained outputs, not total circuit width.Source: §1.6 · p. 11

1.7. Overview of the framework.

• Conditioning on measured qubits produces separable approximations whose residual profile entropy controls energy error, and structure-preserving measurements yield sharper benchmarks such as product stabilizer states.The framework adapts a nonsymmetric quantum de Finetti argument and uses Gaussian-process entropy bounds; the benchmark can also be refined for Clifford+T inputs.Source: §1.7 · pp. 12–13
• Subquadratic effective profile complexity cannot improve on product states at leading order, while uniformly bounded quadratic complexity leaves a positive order-√n gap for sufficiently large fixed p.The subquadratic comparison holds at the leading √n energy scale; the quadratic-complexity obstruction is against the unrestricted optimum.Source: §1.7 · p. 13
• Block-product and matrix product state entropy bounds come from discretizing their block and tensor descriptions, respectively.The paper directs the block-product and tensor-network arguments to Sections 3.3 and 3.4.Source: §1.7 · p. 14
• At controlled circuit width, counting Clifford blocks and discretizing shallow gates covers both magic orientations at every fixed hierarchy level.This argument is described in Section 4.2.Source: §1.7 · p. 14
• For forward magic, pruning and stabilizer structure yield an ancilla-independent profile-entropy bound by counting accessible Pauli-expectation patterns and discretizing shallow gates.Pruning leaves a mixed stabilizer input; the argument appears in Section 4.3.Source: §1.7 · p. 14
• For reverse magic, a final Clifford spreads local observables, so the method instead uses stabilizer constraints and depth to build an ancilla-independent representation, then counts Clifford operations and discretizes shallow gates.The argument is described in Section 4.4.Source: §1.7 · p. 14
• For Clifford+T, representing outputs as fixed projections of mixed stabilizer states on n + t qubits enables stabilizer counting independent of the original ancillary workspace.This argument is developed in Section 5.3.Source: §1.7 · p. 14

1.8. Open questions.

• Can fixed-p classes with effective profile complexity O(n^2) beat product states by c√n, and what complexity is needed to approach the unrestricted optimum?Theorem 1.2(ii) rules out that advantage at subquadratic complexity but does not establish quadratic sufficiency.Source: §1.8 · p. 14
• Can local-profile approximations retain structured entanglement by using states in the convex hull of an entangled benchmark, extending energy comparisons beyond separable approximations?The proposed errors would need to be small enough for a useful energy comparison.Source: §1.8 · p. 14
• Can one fixed random bounded-degree Hamiltonian ensemble rule out near-ground-state preparation at every constant depth, with its degree prefactor and energy-density gap independent of depth?This would yield an NLTS-type result for random spin glasses; [AGG26] has a degree prefactor that depends on depth, and the NLTS context cites [ABN22].Source: §1.8 · p. 14

2.1. Conditioning and local approximation.

• Conditioning measured qubits and averaging conditional product states yields a separable approximation whose p-qubit marginals can be compared with those of the original state.The number of measured qubits can be prescribed, and the approximation controls average squared trace-norm error over p-subsets of the unmeasured qubits; the measurements are proof devices, not assumed circuit operations.Source: §2.1 · p. 15, §2.1.3 · pp. 18–19

2.1.2. The Pauli POVM.

• The six-outcome Pauli POVM satisfies the trace-norm comparison with distortion constant κM = 4.It randomly selects a Pauli axis, measures that observable, and records both the axis and eigenvalue.Source: §2.1.2 · p. 17

2.1.1. Measurements and conditioning.

• The conditioning argument follows Berta et al. [BBFS22] and uses a measurement comparison to transfer information bounds back to the unmeasured quantum states.For the chosen POVM, closeness of the classical–quantum states retaining both outcomes and the unmeasured system implies closeness of the original states up to a finite distortion factor.Source: §2.1.3 · p. 19

2.1.3. Conditioning with a measurement budget.

• With a prescribed measurement budget, the proof selects a conditioning depth and telescopes conditional states to obtain a fully separable approximation with controlled averaged local error.The selected depth is among 0 through m⋆, where m⋆ bounds the number of measured qubits.Source: §2.1.3 · pp. 18, 19, 21
• Conditioning is compatible with adjoining and then discarding an auxiliary system: outcome probabilities agree, and rank-one measurements preserve purity of conditioned joint states for pure inputs.This property supports the later treatment of circuits with ancillas.Source: §2.1.3 · p. 22

2.1.4. Profile approximation and conditioning benchmarks.

• For every state, conditioning yields a fully separable approximation whose p-qubit Pauli-profile error is bounded after excluding at most m⋆ sites, so product states form a benchmark for every class.The approximation preserves the original normalization for interactions supported entirely on the retained sites.Source: §2.1.4 · p. 23

2.2. Uniform energy comparison.

• The uniform energy comparison bounds a class’s advantage over its benchmark by residual-profile complexity and interactions touching excluded qubits.For a general conditioning benchmark, the approximation radius is Ap,α/√n at fixed p and α.Source: §2.2 · p. 26

2.3. Ground-state separation at quadratic profile complexity.

• At quadratic profile complexity, an entropy-based residual bound compares the class’s energy with the product-state benchmark, providing the estimate used for ground-state separation.The corollary assumes an entropy bound on the class’s Pauli-profile complexity.Source: §2.3 · p. 26

2.4. Energy benchmarks.

• The product-state optimum converges after √n normalization to eprod(p), while the unrestricted ground-state energy is Ω(√n) for each fixed p ≥ 3.The product-state limit also identifies the same limiting energy for classes containing product states when Γn,p = o(n²) under the stated entropy assumptions.Source: §2.4 · p. 28

2.5. Completing the quadratic ground-state argument.

• For profile complexity bounded at quadratic scale, sufficiently large fixed p yields a positive-multiple-√n gap between the class’s attainable energy and the ground-state energy.The class’s energy upper bound is a strict fraction of the ground-state scale with high probability.Source: §2.5 · p. 28

2.6. Benchmark comparison at subquadratic profile complexity.

• When Γn,p = o(n²), a class cannot outperform any conditioning benchmark at leading √n scale, with the normalized comparison converging in L1 and in probability.The benchmark need not be the product-state class.Source: §2.6 · p. 29

3.1. Circuit size.

• Pruning reduces any n-qubit output prepared with G gates and arbitrary discardable ancillas to a circuit on at most n+G qubits, preserving the retained output.This removes dependence on the ambient ancilla workspace and supports the gate-count energy bounds.Source: §3.1 · p. 30
• At gate count O(n^2/log n), sufficiently large fixed p gives ground-state separation; o(n^2/log n) gates cannot beat product states at leading order.Both conclusions hold uniformly over the number of discardable ancillas, with no restriction on circuit depth or geometry.Source: §3.1 · p. 32

3.2. Circuit depth and width.

• For effective width c_Mn = min{M_n, n2^D_n}, the depth-width thresholds are D_n c_Mn = O(n^2/log n) for separation and o(n^2/log n) for product-state comparison.At linear width, these correspond to depths O(n/log n) and o(n/log n), respectively; with unrestricted width, product-state comparison holds when D_n ≤ c log2 n for fixed c in (0, 1).Source: §3.2 · pp. 33–34
• Depth-width bounds use backward-lightcone pruning to limit effective gate count, then apply profile complexity; at linear width, pruning is unnecessary for the larger depth range.The argument uses the same pruning mechanism as [AGG26] but applies it to effective gate count rather than a lightcone-localized residual process.Source: §3.2 · p. 34

3.3. Block-product states.

• Block-product states confine entanglement to blocks of at most b qubits, allow arbitrary states within each block, and remain mixtures of such states after discarding ancillas.The section develops profile-entropy bounds for this class without restricting how the block states are prepared.Source: §3.3 · pp. 34–35
• For b_n ≤ c log_2 n with fixed 0 < c < 1, block-product states satisfy both stated energy conclusions, including the product-state comparison.The conclusions hold even when each block uses an arbitrary number of discardable ancillas.Source: §3.3 · p. 36

3.4. Matrix product states.

• When the MPS bond dimensions satisfy the stated linear profile-complexity bound, their energies remain separated from the ground-state energy for sufficiently large fixed p.The bound is stated as n log(nχ_n) ≤ L n for all sufficiently large n; the separation also holds for convex mixtures and unions over one-dimensional orderings.Source: §3.4 · p. 37
• If χ_n^2 log(nχ_n) = o(n), MPS cannot outperform product states at leading order for every fixed p.This comparison also holds for convex mixtures and when the physical-qubit ordering varies.Source: §3.4 · p. 37
• Fixed-bond-dimension MERA have no asymptotic energy advantage over product states.The extension applies to tensor networks with fixed architectures via the same telescoping argument.Source: §3.4 · pp. 37–38

4.1. Stabilizer background and magic classes.

• The k-round classes alternate shallow blocks with Clifford blocks in either orientation, and permit discarding all r ancillas from total width M = n + r.Here k counts the shallow blocks; setting a shallow block to the identity includes stabilizer states.Source: §4.1 · p. 39

4.2. Fixed levels of the magic hierarchy.

• At every fixed level, both magic-hierarchy orientations are separated from the ground state under a linear total-width assumption.The stated results allow linearly many discardable ancillas.Source: §4 · p. 38, §4.2 · pp. 41–42

4.3. Forward magic with arbitrary discardable ancillas.

• Pruning forward-magic circuits to the retained outputs’ backward lightcone leaves a mixed stabilizer input, even when the original Clifford entangles outputs with arbitrarily many ancillas.The reduced input is mixed but remains a reduction of a pure stabilizer state.Source: §4.3 · p. 42
• The forward-magic profile-entropy bound is independent of the original discardable-ancilla count, using c_M = min{M, n2D} or c_M = n2D across widths.For fixed total width M, pruning represents the output using a depth-D circuit on c_M qubits; the n2D representation does not depend on the original ancilla count.Source: §4.3 · pp. 42, 44
• For M_n ≤ K n and D_n ≤ L n/log n, forward-magic states remain a positive energy distance from the ground state for sufficiently large fixed p, uniformly over discardable ancillas.The gap constant may depend on p, K, and L.Source: §4.3 · pp. 44–45
• For every fixed p ≥ 2, when M_n = O(n) and 2^D_n = o(n), forward-magic energies converge to the product-state benchmark; with arbitrary discardable ancillas, this holds if 4^D_n = o(n).The conclusions are uniform over the number of discardable ancillas.Source: §4.3 · pp. 44–45
• Mixed stabilizer-state profiles take values in {−1, 0, 1}, and the positive- and negative-sign profile classes each have VC dimension at most M.The restriction-growth bound follows by applying Sauer’s lemma to those classes.Source: §4.3 · pp. 45, 47
• Conjugation by one layer of disjoint one- and two-qubit gates at most doubles an observable’s support, so depth D expands a p-qubit support to at most 2^D p qubits.The support is also capped by the circuit’s total qubit count.Source: §4.3 · p. 48
• For forward magic with arbitrary discardable ancillas, the class is covered uniformly over ancilla count using a common width cM = n2^D and s = p2^D.Substituting these values into the preceding estimate proves the stated second estimate for the class.Source: §4.3 · p. 51

4.4. Reverse magic with arbitrary clean ancillas.

• If every logical Pauli class has a representative supported on E, a Clifford acting only on E recovers the logical state on a set of t qubits within E.This recovery principle is applied to the intermediate state from the shallow preparation, whose stabilizer nullity is unchanged by the final Clifford and by appending clean zero-state qubits.Source: §4.4 · pp. 53–54
• For reverse magic with clean outputs, an ancilla-independent reduction represents the prepared state using a depth-D matching circuit and Clifford on O_D(t) qubits, where t is its stabilizer nullity.For fixed D, the reduced circuit width is O(n), regardless of the original number of clean ancillas; the reduction uses a depth-bounded support for logical Pauli classes, recovers the logical state, and prunes its preparation.Source: §4.4 · p. 54

1. Choosing the logical state to recover.

• Vglob is defined by combining the output decoder with the preparation circuit, and the clean-output identity is then applied.Source: §1 · p. 55
• The operators Vglob†ZjVglob stabilize η, and their independent labels form a basis of S that generates Gη.Source: §1 · p. 55
• Although this specifies the logical state, Vglob may act on all M qubits, so it does not locate the state on a small physical set.Source: §1 · p. 55
• The operators Ai = QZiQ† are Hermitian unitaries fixing η, whose unique common +1 eigenstate is η up to global phase.Source: §1 · p. 55

2. Finding a small set supporting the logical Pauli operations.

• Each Ai is supported on at most 2D qubits, so every Pauli term in its expansion is supported within supp(Ai).Source: §2 · p. 55
• The logical classes of Pauli terms commuting with every stabilizer form a span equal to WS.Source: §2 · p. 55
• If a class outside S were orthogonal to that span, its representative would preserve every Ai expectation, forcing it to stabilize η and contradicting its class being outside S.Source: §2 · p. 55
• Because dim WS = 2t, 2t selected Pauli classes can form a basis of WS.Source: §2 · p. 55
• Each logical Pauli class has a signed Hermitian representative supported on E.Source: §2 · p. 56
• Applying Lemma 4.13 to E yields a Clifford VE and an ordered set T of t qubits whose retained state recovers the selected pure state ϕ, even if ηE is mixed.Source: §2 · p. 56
• Keeping the gates in E’s backward lightcone through Q produces a depth-D circuit Q′ on m qubits, with each backward layer increasing the included set by at most a factor of two.Source: §4 · p. 56

4. Pruning the preparation circuit.

• Every output is represented on a common width m*=2^(2D+1)n, then Clifford choices and discretized shallow circuits yield a finite profile cover.The profile approximation is transferred using trace-norm contraction under partial trace and the unit operator norm of Pauli operators.Source: §4 · pp. 56–58
• The cover bound applies to every original ancillary width, so its profile-entropy estimate is independent of how many clean ancillas are used.The construction represents the retained input qubits together with the final Clifford operation on a common number of qubits.Source: §4 · pp. 56, 58
• For fixed depth D and sufficiently large fixed p, Theorem 4.16 gives a reverse-magic lower-bound conclusion that is uniform over the number of clean ancillas.The theorem’s threshold p0 and positive constant cp,D depend on D and p, respectively.Source: §4 · pp. 58–59
• The stated corollaries also cover both orientations for every fixed number of shallow blocks, with linear-width conclusions and a fixed-depth clean-ancilla result.Depth-zero cases are included by enlarging to depth one; the product-state comparison passes to subclasses by monotonicity.Source: §4 · p. 59

5. Stabilizer states and Clifford+T circuits

• With t T-gates, conditioning leaves all but at most t one-qubit marginals as mixtures of pure stabilizer states, yielding product states with at most t arbitrary factors.The full output may be mixed because T-gates can act on discarded qubits.Source: §5 · p. 60, §5.1 · p. 61

5.1. Overview of the argument.

• When t=o(n), Clifford+T outputs have no leading-order energy advantage over product stabilizer states; allowing t exceptional factors changes expected optimal energy by only o(√n) for fixed p.The product-stabilizer benchmark’s normalized energy has sharp large-p limit √2 log 6.Source: §5.1 · pp. 60–61

5.2. Pauli conditioning and sharper benchmarks.

• Pauli conditioning and stabilizer nullity provide the approximation: nullity is bounded by T-count, and conditioning does not increase it, enabling approximation by mixtures with at most t non-stabilizer factors.The lemma approximates the state on a set J of at least n−m⋆ qubits.Source: §5.2 · pp. 61–62, §1 · p. 62

1. Construct the conditioning approximation.

• For each positive-probability outcome z, the conditional marginals on J define a product state θJ,z.The outcome probabilities q(z) weight the conditional product states.Source: §1 · p. 62
• Retaining the extra qubits during the same rank-one Pauli measurement preserves outcome probabilities and produces a pure joint conditional state.The conditional marginals agree with those obtained by conditioning the reduced state directly.Source: §2 · p. 62

2. Identify the exceptional factors.

• Pauli conditioning does not increase stabilizer nullity, preserving the bound needed to control exceptional sites.The input pure state's stabilizer nullity is at most t.Source: §2 · p. 62
• Fz identifies retained sites whose conditional marginals cannot be expressed as mixtures of pure one-qubit stabilizer states.These are precisely the sites requiring non-stabilizer factors in the decomposition.Source: §2 · p. 62
• Decomposing ordinary marginals into stabilizer states and exceptional ones spectrally yields product terms with at most t non-stabilizer factors.The resulting terms belong to BJ,t, and their coefficients form a probability mixture.Source: §2 · pp. 62–63

3. Extend the approximation and bound the profile error.

• Clifford+T outputs with at most t_n T-gates have conditioning approximations by mixtures of product states, each with at most t_n non-stabilizer factors.The resulting classes form a conditioning benchmark for Clifford+T outputs for every sequence of nonnegative T-gate budgets.Source: §3 · p. 63
• The approximation bound is uniform over ρ and independent of t_n, verifying the conditioning-benchmark property.Source: §3 · p. 63, §5.3 · p. 64

5.3. Profile entropy of Clifford+T circuits.

• A Clifford+T output profile is obtained as a fixed projection of a mixed stabilizer state on n+t qubits, enabling profile counting independently of the original ancilla count.The construction reformulates the postselected T-gate method in [BG16, Section IV].Source: §5.3 · p. 64

• Tracing out the original ancillary qubits from the pure stabilizer state yields a mixed stabilizer state on the first n qubits and all t extra qubits.The partial trace and the contractions act on disjoint sets of qubits.Source: §3 · p. 65
• The representation is then used to control the profile entropy of Clifford+T outputs.Source: §3 · p. 66
• Lemma 5.4 states a universal-constant bound for n ≥ p ≥ 2, integer t ≥ 0, and 0 < ε < 1.The supplied passage does not specify the bound's formula.Source: §3 · p. 66

• Only Pauli strings with factors in {I, X, Y} on the added qubits have nonzero coefficients, giving 3^t candidate strings per query.Source: §1 · p. 66
• For each queried output Pauli, the expectation is expressed through a linear combination of stabilizer-state Pauli expectations.Source: §1 · p. 66
• The selected stabilizer Pauli expectations determine all queried output expectations because the strings and coefficients are fixed by t and the queries.Source: §1 · p. 66, §2 · p. 66

• The number of possible queried response vectors is at most the number of corresponding mixed-stabilizer response vectors.The argument applies the mixed-stabilizer counting bound of Lemma 4.10.Source: §2 · p. 67
• For q ≥ 2m, a binomial bound verifies the restriction-growth hypothesis of Lemma A.1 with d = 2m and A = 2e3^t.Source: §2 · p. 67
• Every output-profile value lies in [-1, 1] because the state is normalized and each Pauli operator has norm one.Source: §2 · p. 67

3. Converting the growth bound to profile entropy.

• The growth-bound conversion turns an L2(µn,p) cover into an ε-cover in profile norm, then substitutes m = n + t to obtain the stated bound.Source: §3 · p. 67

5.4. Energy bounds for Clifford+T states.

• If t_n ≤ κn eventually, then for every sufficiently large fixed p the Clifford+T class remains separated from ground-state energy by a positive multiple of √n.The sufficiently large p may depend on κ.Source: §5.4 · p. 67
• For t_n = o(n), Clifford+T states have no leading-order energy advantage over product stabilizers, in L1 and in probability.The comparison applies for each fixed p and allows the exceptional factors’ energy contribution to vanish after normalization by √n.Source: §5.4 · pp. 68–69

5.5. Product-stabilizer energy.

• For each fixed p ≥ 2, the normalized product-stabilizer optimum has a thermodynamic limit; as p grows, its limit is √2 log 6.The proof compares Gaussian processes and reduces a lower bound to the expected maximum of independent Gaussian variables, as in the Random Energy Model.Source: §5.5 · pp. 69, 71
• The unrestricted product-state value [AGK25] grows with p, unlike product stabilizer states, which have only six local choices per qubit.Arbitrary product states can choose continuously many Bloch-sphere directions.Source: §5.5 · p. 74

Use of AI

• AI helped develop the clean-ancilla reverse-magic proof after an incorrect discardable-ancilla proof, suggested studying Clifford+T circuits, and assisted with proof checking; the authors take responsibility for the paper.The authors say all results were developed by them.Source: Use of AI · p. 75

Appendix A. Profile entropy from restriction growth

• Polynomial restriction growth yields a metric-entropy bound of log M ≤ Cd log(eA/ε) for an ε-net of the profile class.The proof uses a maximal ε-separated family and a sample that distinguishes every pair.Source: Appendix A · p. 75

B.1. Pauli operators and binary labels.

• Phase-free Pauli operators have binary labels whose symplectic inner product records commutation, and Clifford conjugation preserves these relations.A symplectic change of labels can be implemented by a Clifford unitary [DDM03, Sections II–IV].Source: §B.1 · pp. 76–77

Appendix B. Pauli and stabilizer preliminaries

• The Pauli operators form an orthogonal operator basis, and a Pauli operator’s support is the set of qubits on which it is not identity.Source: §B.1 · p. 76

B.2. Isotropic subspaces and commuting Pauli groups.

• A commuting stabilizer group defines a common +1 eigenspace, and tracing out qubits from a pure stabilizer state leaves a mixture of pure stabilizer states.The partial trace retains precisely the stabilizers acting trivially on the discarded qubits.Source: §B.2 · p. 78

B.3. Stabilizer nullity and logical Pauli spaces.

• A Clifford decoder maps a state’s M−t independent Pauli constraints to Z constraints on M−t qubits, leaving t unrestricted logical qubits.The constrained space becomes an arbitrary t-qubit state tensored with |0⟩ on the other qubits.Source: §B.3 · pp. 79–80
• Logical Pauli actions on the constrained space are represented by the quotient S⊥/S, a 2t-dimensional symplectic label space.Physical Paulis outside S⊥ annihilate the constrained space under projection; those inside S⊥ preserve it.Source: §B.3 · p. 80
• Clifford+T circuits with at most s T-gates have nullity at most s, and positive-probability Pauli postselection leaves at most s one-qubit marginals outside conv(pstab1).The marginal bound is independent of the number of Clifford gates or pure stabilizer ancillas.Source: §B.3 · pp. 81–82
• Measuring one qubit in a Pauli basis and conditioning on any positive-probability outcome does not increase stabilizer nullity after discarding that qubit.The conditional measured qubit is a pure Pauli eigenstate with nullity zero.Source: §B.3 · pp. 81–82

B.4. Exact workspace compression for Clifford+T circuits.

• The compressed preparation uses at most 2n+t qubits and at most s T-gates when the original representation uses s≤t rotations.The construction decodes stabilizers supported on discarded workspace and removes rotations that become identity.Source: §B.4 · pp. 82–84
• A Clifford+T state with at most t T-gates has a normal form as at most t Pauli rotations applied to a pure stabilizer state, and its nullity is at most t.Each nonidentity Pauli rotation costs one T-gate.Source: §B.4 · p. 83
• Every state prepared with at most t T-gates and unrestricted Clifford operations can be prepared using at most t T-gates on at most 2n+t total qubits.The compressed preparation preserves the retained n-qubit state after discarding ancillas.Source: §B.4 · pp. 83–84