PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantifying quantum speedups: improved classical simulation from tighter magic monotones

James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, Earl T. Campbell

arXiv:2002.06181v4quant-ph

TL;DR

Different simulators for nearly-stabilizer circuits use different magic monotones, leaving their runtime scalings without a precise comparison. This paper connects three simulation algorithms to corresponding monotones and characterizes them, showing that for tensor products of single-qubit mixed states the monotones coincide and are multiplicative.

  • Problem

    Quasiprobability and stabilizer-rank simulators use different magic monotones, and their runtime scalings had not been precisely compared.

    Source: §I · p. 1

  • Method

    The paper introduces three resource monotones linked to classical simulation algorithms and characterizes their behavior, including for pure states and tensor products of single-qubit mixed states.

    Source: §IX · pp. 23–24

  • Results

    For tensor products of single-qubit mixed states, the three monotones coincide and are multiplicative.

    Source: B. Summary of results · p. 3, §IX · p. 23

  • Takeaways & Limitations

    The generalized robustness Λ+ provides bounds for imperfect conversion and asymptotic distillation rates under general probabilistic protocols.

    Source: §VI · p. 12

    The mixed-state stabilizer-rank simulator has a probabilistic runtime; a deterministic runtime is shown for an important subset of magic states.

    Source: B. Summary of results · p. 3

Abstract

from arXiv · show

Consumption of magic states promotes the stabilizer model of computation to universal quantum computation. Here, we propose three different classical algorithms for simulating such universal quantum circuits, and characterize them by establishing precise connections with a family of magic monotones. Our first simulator introduces a new class of quasiprobability distributions and connects its runtime to a generalized notion of negativity. We prove that this algorithm has significantly improved exponential scaling compared to all prior quasiprobability simulators for qubits. Our second simulator is a new variant of the stabilizer-rank simulation algorithm, extended to work with mixed states and with significantly improved runtime bounds. Our third simulator trades precision for speed by discarding negative quasiprobabilities. We connect each algorithm's performance to a corresponding magic monotone and, by comprehensively characterizing the monotones, we obtain a precise understanding of the simulation runtime and error bounds. Our analysis reveals a deep connection between all three seemingly unrelated simulation techniques and their associated monotones. For tensor products of single-qubit states, we prove that our monotones are all equal to each other, multiplicative and efficiently computable, allowing us to make clear-cut comparisons of the simulators' performance scaling. Furthermore, our monotones establish several asymptotic and non-asymptotic bounds on state interconversion and distillation rates. Beyond the theory of magic states, our classical simulators can be adapted to other resource theories under certain axioms, which we demonstrate through an explicit application to the theory of quantum coherence.

I. INTRODUCTION

The introduction presents classical simulators for magic-state circuits and relates their performance to magic monotones, including mixed-state extensions and an application to quantum coherence. It also examines the monotones’ behavior under stabilizer-preserving operations and practical approximation, including how logarithms affect their properties.

A. Review of prior art

  • Qubit phase-point-frame simulators inherit frame limitations; quasiprobability simulators are slower than stabilizer-rank simulators, and robustness of magic is non-multiplicative and extremely difficult to compute even asymptotically for products of relevant single-qubit states.Source: A. Review of prior art · p. 2

B. Summary of results

  • The dyadic-frame and density-operator stabilizer-rank methods simulate noisy stabilizer circuits with mixed magic-state inputs, while constrained-path simulation trades accuracy for runtime efficiency as magic grows.The first two estimate Born-rule probabilities and Pauli observables; the density-operator stabilizer-rank method approximately samples measurement outcomes.Source: B. Summary of results · p. 2
  • For n T states, dyadic-frame runtime is O(40.228443n), versus robustness-based simulators’ lower bound Ω(40.271553n).The dyadic frame samples stabilizer dyads rather than stabilizer states or phase-point operators, and its resource monotone is smaller than robustness of magic.Source: B. Summary of results · pp. 2–3
  • The density-operator stabilizer-rank method extends stabilizer-rank simulation to mixed states, offers deterministic runtime for an important subset, and improves bounds even for pure-state simulation.The mixed-state generalization has probabilistic runtime before the deterministic improvement for that subset.Source: B. Summary of results · p. 3
  • Dyadic negativity, mixed-state extent, and generalized robustness govern the three simulators; they coincide and multiply for tensor products of single-qubit states and bound distillation rates.The monotones reduce to stabilizer extent for pure states, and the paper reports tighter bounds than other recent results [47] across a wide parameter range for example distillation tasks.Source: B. Summary of results · p. 3
  • The simulator-to-monotone framework also applies beyond magic: in quantum coherence, the ℓ1-norm of coherence quantifies classical simulation runtime.The paper presents a recipe for applying its methodology to general quantum resources.Source: B. Summary of results · p. 4

A. The stabilizer formalism

  • Magic states supplied to stabilizer operations enable universal computation, and the computational power of restricted supplies depends on their type and quantity.The introduction identifies state injection from |H⟩ or |T⟩ as a route to implementing the T gate.Source: A. The stabilizer formalism · p. 5

B. Magic monotone definitions

  • The paper treats magic monotones within a broader resource-theory framework and defines mixed-state extensions of pure-state stabilizer extent, including quantities evaluated by convex optimization.The introduction notes that tensor products of single-qubit states simplify computation of all the monotones.Source: B. Magic monotone definitions · pp. 5–6
  • Strong monotonicity and stabilizer-preserving Kraus decompositions imply that Λ and Ξ are monotone under completely stabilizer-preserving operations.For logarithmic monotones, multiplicativity becomes additivity; they remain strongly monotone but are no longer convex.Source: B. Magic monotone definitions · p. 6
  • The monotones can be interpreted as mixed-state extensions of ξ.The supplied passage does not specify the related lemma’s precise statement.Source: B. Magic monotone definitions · p. 6
  • Λ+ is often easier to evaluate than Λ, and Λ+ ≤ Λ, so Λ+ can be used to approximate Λ.The authors provide alternative proofs of these results in Appendix A 1.Source: B. Magic monotone definitions · p. 6

C. Connecting monotones with simulation

The paper links each of three simulation algorithms to a magic monotone that characterizes its runtime or precision. The dyadic-frame method improves quasiprobability scaling, while the other methods extend simulation to mixed states or trade accuracy for runtime.

C. Connecting monotones with simulation

  • The dyadic-frame algorithm estimates Born-rule probabilities from a known dyad decomposition, with runtime characterized by the dyadic negativity Λ.For a product of single-qubit states, sampling has no runtime variance; the method also improves runtime by a factor 1/δ over previous simulators of this type.Source: C. Connecting monotones with simulation · pp. 6–7
  • For single-qubit states and their tensor products, the paper proves that Λ+, Λ, and Ξ are equal and multiplicative, making Ξ—which is generally hard to compute—evaluable in this setting.The monotones' multiplicativity gives straight-line scaling on a logarithmic plot.Source: C. Connecting monotones with simulation · p. 7, Figure 1 · p. 7
  • The authors state that the simulation algorithm of Thm. 14 is polynomially faster than previous quasiprobability simulators, as illustrated by the example in Fig. 1.Source: C. Connecting monotones with simulation · p. 7
  • The density-operator stabilizer-rank method extends stabilizer-rank simulation to mixed states and supports both probability estimation and approximate output sampling.Its runtime improves by a factor 1/δ over previous simulators of this type, even for pure states.Source: C. Connecting monotones with simulation · p. 7
  • The constrained-path simulator keeps runtime efficient but sacrifices precision, which has an inverse-polynomial dependence on generalized robustness Λ+.This connects the simulator's accuracy to a magic monotone.Source: C. Connecting monotones with simulation · p. 7

III. SINGLE-QUBIT MAGIC STATES

For single-qubit states, the section establishes equality among the paper's magic monotones by characterizing optimal witnesses and decompositions. It also identifies the scope of this equality: it extends to products of single-qubit states, but not generally to multi-qubit states.

III. SINGLE-QUBIT MAGIC STATES

  • The section establishes equimagical decompositions for single-qubit states, including mixtures whose pure components have the same amount of magic.Such decompositions support the mixed-state characterization.Source: §III · pp. 7, 10
  • The equality does not generally extend to arbitrary states of two or more qubits; numerically, Λ+ is below Λ for most random states examined.The section states that the equivalence persists for tensor products of single-qubit states.Source: §III · p. 7
  • The inequalities among Ξ, Λ, and Λ+ collapse to equalities for single-qubit states.The section characterizes this equality through optimal ω-witnesses and mixed-state decompositions.Source: §III · pp. 7–8
  • For pure non-stabilizer states in PY, an optimal ω-witness has the stated parameterized form; q is 2/3 on the region's boundaries and for most pure states there.Between the majority region and the geodesic through |0⟩, |H⟩, and |+⟩, q varies continuously from 1 to 2/3.Source: §III · pp. 8–9
  • Every single-qubit non-stabilizer mixed state lies in a set Bω for an appropriate ω-witness, enabling the monotone-equality lemma to apply.The proof constructs the relevant witness using pure states in Bloch-sphere slices and their convex combinations.Source: §III · pp. 8–9

IV. MULTIPLICATIVITY

For tensor products of single-qubit states, the section proves strict multiplicativity of the mixed-state monotones and equality among them. It contrasts this result with the known behavior of other qubit magic monotones.

IV. MULTIPLICATIVITY

  • The result establishes strict multiplicativity for mixed-state monotones in qubit magic theory, which had not been known before this work.The section notes that robustness of magic can be strictly sub-multiplicative, while qubit phase-space robustness can be strictly super-multiplicative.Source: §IV · pp. 10–11
  • The strict multiplicativity result is not established for arbitrary-dimensional tensor factors; whether it holds for low numbers of qubits remains open.The section reports numerical evidence suggesting Λ+ is multiplicative for mixed two-qubit states.Source: §IV · p. 11
  • The proof obtains a matching lower bound for Λ+ by tensoring single-qubit optimal witnesses, complementing Ξ's manifest sub-multiplicativity.The single-qubit witness structure is supplied by the earlier characterization.Source: §IV · p. 11
  • For products of single-qubit states, Ξ, Λ, and Λ+ are equal and strictly multiplicative.The product states also admit equimagical decompositions.Source: §IV · pp. 10–11

V. COMPARISON WITH ROBUSTNESS

The section compares the new monotones with robustness of magic and shows an exponential gap for single-qubit non-stabilizer states. The comparison also highlights why robustness provides a less precise account of product-state scaling.

V. COMPARISON WITH ROBUSTNESS

  • The robustness of magic is not multiplicative, so its single-state value does not directly determine how it scales on tensor powers.For single-qubit states, the section derives R(ρ) = 2D(ρ) − 1 and uses this relation in comparing bounds.Source: §V · pp. 11–12
  • For any single-qubit non-stabilizer state, the paper establishes positive exponents α > β separating the robustness lower bound from the new monotones' scaling.For the Hadamard state, α = 0.271553 and β = 0.228443.Source: §V · p. 11
  • The new monotones' multiplicative scaling and their exponential separation from robustness establish polynomially faster scaling for the dyadic-frame simulator.The comparison is presented for the single-qubit setting.Source: §V · p. 12
  • For Hadamard states, the robustness upper bound is O(2^0.368601n), while the lower bound in Eq. (58) is smaller.The authors describe the known upper bounds as loose relative to the lower bound.Source: §V · p. 12

VI. DISTILLATION AND ASYMPTOTIC RATES

The section derives bounds on probabilistic distillation and asymptotic state-conversion rates from magic monotones, then presents three classical simulation approaches tied to those monotones. The approaches trade runtime, sampling guarantees, and precision in different ways.

VI. DISTILLATION AND ASYMPTOTIC RATES

  • Theorem 13 bounds probabilistic conversion of k input copies into m nearly pure copies of a target, with the constraints depending on Λ+(ρ) and the target’s stabilizer fidelity.The two bounds on required input copies can perform differently depending on the parameters.Source: §VI · pp. 12–13
  • For |H⟩ distillation, the paper’s bounds outperform Ref. [47] down to ε ≈ 10^-21 at m = 4, improve as m increases, and apply also when α = 1.The comparison uses success probability p = 0.9; the figure also reports better performance near α = 1 for ε = 10^-20 and m = 24.Source: Figure 4 · p. 13, §VI · p. 13
  • The monotone bounds give computable upper bounds on transformation rates to pure targets of at most three qubits, including Clifford-symmetric targets such as |H⟩ and |F⟩.The section also derives no-go results without requiring difficult monotone calculations for many copies.Source: §VI · pp. 12–13
  • Known magic-state distillation protocols perform many orders of magnitude worse than the paper’s best bounds, leaving a substantial gap to close.The authors identify closing this gap as a considerable challenge.Source: §VI · p. 14

VII. CLASSICAL SIMULATION ALGORITHMS

  • The dyadic-frame simulator estimates Born probabilities with sampling overhead governed by dyadic negativity, and its new frame improves the runtime’s exponential scaling over prior qubit quasiprobability simulators.For an optimal dyadic decomposition, the stated worst-case runtime is O(Λ(ρ)^2).Source: §VII · p. 14
  • The density-operator stabilizer-rank simulator handles mixed-state bit-string sampling, with average runtime O(Ξ(ρ)/δ^3) per string under modest assumptions and a factor δ^-1 improvement over Ref..An equimagical decomposition makes this a worst-case runtime.Source: §VII · p. 14
  • The constrained-path simulator estimates Pauli expectations or Born probabilities efficiently by discarding negative quasiprobabilities, with unavoidable additive error lower bounded as O(Λ+(ρ)).The error is on E(ρ) for a stabilizer channel E and non-stabilizer state ρ.Source: §VII · p. 14

1. Quasiprobability simulators

  • The Howard–Campbell quasiprobability method samples from a stabilizer-state decomposition, with worst-case runtime scaling at least as R(ρ)^2; the dyadic-frame approach instead uses stabilizer dyads.The dyadic simulator expresses non-free states using complex-valued quasiprobabilities over dyads.Source: §1 · p. 15

2. Dyadic frame simulator

The dyadic-frame simulator estimates Born probabilities using known dyadic decompositions and stabilizer-preserving circuit operations, with runtime linked to dyadic negativity. The section also contrasts this approach with the pure-state BBCCGH stabilizer-rank method and its improved density-operator successor.

2. Dyadic frame simulator

  • With an optimal dyadic decomposition, the dyadic-frame simulator’s worst-case runtime is O(Λ(ρ)^2), and exploiting the dyadic frame improves exponential scaling over previous work.The simulator assumes a known decomposition that can be efficiently sampled; the general-channel result requires known simulable channel decompositions.Source: §2 · p. 16
  • The simplified simulator is limited to convex mixtures of unitary Clifford operations, whereas the extension admits completely stabilizer-preserving channels.The restricted setting therefore covers only unital channels.Source: §2 · p. 16
  • The generalized dyadic-frame algorithm estimates Born probabilities for a known dyadic input decomposition and stabilizer projector when each circuit operation has a known simulable decomposition.Such decompositions restrict the number of unitary and non-unitary Kraus operators to be polynomial in n.Source: §2 · p. 16

1. Prior art: the BBCCGH simulator

  • BBCCGH samples bit strings from pure magic states using SPARSIFY and FASTNORM, with runtime linear in pure-state extent for an optimal decomposition.Its multiplicative probability estimates keep the output distribution close in ℓ1-norm to the quantum distribution.Source: §1 · pp. 16–17
  • The density-operator successor extends stabilizer-rank sampling to mixed inputs and improves the prior runtime by a factor of 1/δS, with modest caveats.The improvement comes from working in the density-operator picture, including when the input magic state is pure.Source: §1 · p. 17
  • SPARSIFY approximates an exact state |ψ⟩ by an unnormalized random vector |Ω⟩ containing k stabilizer terms.The figure caption states an average approximation-error relation involving δ² and 1/k.Source: Figure 5 · p. 17

2. Sparsification lemma

The refined sparsification lemma approximates a pure magic state through a normalized ensemble of random sparse states, rather than post-selecting individual approximations. Above a critical precision it improves the prior stabilizer-rank sparsification scaling by a factor of 1/δS; below that threshold, a sharper bound remains available.

2. Sparsification lemma

  • The sparsification input is a pure state with a known stabilizer decomposition, and SPARSIFY returns a randomly chosen k-term approximation.The theorem’s guarantee concerns an ensemble of sampled pure states whose stabilizer rank is bounded by the sparsification size.Source: §2 · pp. 17–18
  • The method normalizes each random sparsification and bounds the error between the target and the full ensemble, avoiding post-selection of individual states.The authors motivate this ensemble comparison by observing that coherent errors in individual samples can smooth into less harmful stochastic error.Source: §2 · p. 17
  • Figure 6 plots trace-norm error against sparsification size for two product-state choices, distinguishing the exact bound from the leading-order expression.The caption states that the exact bound applies for all δS, whereas the leading-order expression is the theorem’s asymptotic form.Source: Figure 6 · p. 18, §2 · p. 18
  • For δS ≥ δc, the lemma achieves trace-norm error δS with k = 4∥c∥2_1/δS stabilizer terms, improving the prior k = 4∥c∥2_1/δS² scaling by a factor of 1/δS.For Clifford magic states, δc = 0, so the improvement applies at all precisions.Source: §2 · pp. 18–19
  • Below δc, the δS^-2 scaling returns, but direct bounds using C can give a substantially smaller prefactor than the prior lemma.The exact bound remains valid for all δS; the leading-order expression is not valid below δc.Source: §2 · pp. 18–19, Figure 6 · p. 18

3. Bit-string sampling from mixed magic states

The section develops mixed-state bit-string sampling using improved sparsification and fast norm estimation, then presents a constrained-path estimator that trades accuracy for runtime. The sampling guarantee applies above a critical precision, while the constrained-path runtime is constant in the robustness parameter and its error depends on that parameter.

3. Bit-string sampling from mixed magic states

  • The sampler extends the pure-state stabilizer-rank method to mixed states, using improved sparsification and avoiding the prior algorithm’s post-selection step.It samples a pure component of the input mixture, sparsifies it, then uses conditional probabilities estimated with FASTNORM.Source: §3 · p. 19, Figure 7 · p. 19
  • When sparsification error δS ≥ δc, runtime scales as O(δ^-3); at arbitrary precision the leading scaling becomes O(δ^-4), typically with a much smaller prefactor than prior work.The critical threshold is δc = 8(C − 1)/∥c∥2_1.Source: §3 · p. 20
  • With an optimal mixed-state decomposition, the bit-string sampler has expected runtime O(Ξ(ρ)); for equimagical decompositions, this also bounds worst-case runtime.The stated sampling guarantee requires δ ≥ 24D, and the output distribution is δ-close in ℓ1 norm with the theorem’s stated success probability.Source: §3 · p. 20

C. Constrained path simulator

  • The constrained-path simulator samples only the positive path, approximating ρ by λσ and incurring systematic error tied to the omitted negative contribution.Because the negative-path state need not be efficiently simulable, this approach can use any density operator there; σ is a mixed stabilizer state.Source: C. Constrained path simulator · p. 21
  • For some large-λ and small-Eσ regimes, the constrained-path algorithm returns only the trivial expectation-value range, though other regimes yield non-trivial biased estimates.Source: C. Constrained path simulator · p. 21
  • Its runtime is constant with respect to λ, while the error bound Δ scales with the magic monotone represented by λ.The trade-off arises because increasing sampling runtime cannot remove the systematic error from ignorance of the negative component.Source: C. Constrained path simulator · p. 22

VIII. APPLICATIONS TO OTHER RESOURCES

The paper extends its simulation framework to resource theories satisfying stated simulability criteria, giving resource monotones operational meaning through simulation costs. It applies the framework to coherence and concludes with comparisons of the magic-state simulators and their monotones.

VIII. APPLICATIONS TO OTHER RESOURCES

  • The framework extends to resource theories whose free states, operations, and observables meet the simulability criteria, with resource costs measured by the proposed monotones.The theorem connects Λ to sampling overhead, and an optimal dyadic decomposition allows ∥α∥1 to be replaced by Λ(ρ).Source: §VIII · p. 22
  • For coherence theory with either incoherent or strictly incoherent operations, the dyadic simulator gives the ℓ1-norm of coherence an operational meaning as sampling overhead.The constrained path simulator similarly connects generalized robustness Λ+ to robustness of coherence.Source: §VIII · p. 23
  • The dyadic frame simulator does not apply to every resource theory: separable states under LOCC fail the criteria because their infinitely many inequivalent pure product states cannot be indexed with poly(n) bits.The authors leave precise conditions for an approach using an ϵ-net over separable states for future work.Source: §VIII · p. 23

IX. CONCLUSIONS

  • For tensor products of single-qubit mixed states, the three monotones coincide and are multiplicative, and they often tighten previously known distillation-rate bounds.These properties simplify computing the monotones across copies and clarify their asymptotic behavior.Source: §IX · p. 23
  • The dyadic negativity simulator runs proportional to Λ(ρ)^2, and for tensor products of n single-qubit states, Λ is exponentially smaller than robustness R.The authors describe it as the fastest known quasiprobability simulator for qubit magic states; it also works with completely stabilizer-preserving operations.Source: §IX · p. 23
  • The mixed-state stabilizer-rank simulator has expected runtime proportional to Ξ(ρ); for Clifford magic-state sampling its bound improves from O(1/δ^4) to O(1/δ^3).For products of single-qubit states, the monotones coincide, and the authors conclude the advantage falls to stabilizer-rank methods.Source: §IX · p. 24
  • The authors present a recipe for adapting their simulators beyond magic states under suitable assumptions, including to quantum coherence.They frame this as an avenue for studying connections between resource theories and operational applications in quantum computation.Source: §VIII · p. 23, §IX · p. 24

Appendix A: Alternative proofs for previous results

The appendix supplies alternative proofs for monotone relations. It establishes equality of the monotones on pure states, proves their sandwich ordering, and gives an algebraic argument for inequalities concerning Φ±.

1. Monotone equivalence proof

  • For pure states, the dyadic negativity Λ, generalized robustness Λ+, mixed-state extent Ξ, and extent ξ are equal.The proof uses dual witnesses to establish the equality with ξ, then identifies Λ+, while Ξ has only one convex decomposition for a pure state.Source: §1 · p. 26

2. Sandwich theorem

  • The sandwich theorem gives Λ+(ρ) ≤ Λ(ρ) ≤ Ξ(ρ).The first inequality follows from the restricted set of witnesses for Λ+; the proof uses the pure-state equality for the remaining bound.Source: §2 · pp. 26–27, §1 · p. 26

Appendix B: Geometry of Φ±

  • The appendix also provides an algebraic argument for inequalities involving Φ±, using feasible Bloch-vector decompositions.The argument minimizes Tr[Yρ] over the stated feasible vectors to establish the first inequality, then treats the second and third similarly.Source: Appendix B · p. 27

Appendix C: Dyadic frame simulator technical details

This appendix details and analyzes the dyadic frame simulator for mixed magic states evolved by channels with known simulable decompositions, establishing its sampling and estimation properties and a runtime bound dependent on the frame coefficient norm, precision, failure probability, and circuit size.

Algorithm and validity

  • The simulator samples an initial stabilizer dyad, propagates it by randomly selecting Kraus operators, and uses stabilizer-update and outer quasiprobability-sampling subroutines.The appendix establishes that the resulting estimate of Tr[ΠE(ρ)] is unbiased.Source: Appendix C · pp. 28, 30

Transition probabilities

  • Trace-norm transition probabilities are essential for general dyads: unlike Born-rule traces, they avoid zero-weight paths that would erase a nonzero estimator contribution.For the example, selecting K1 with certainty gives the correct contribution µm = −∥α∥1/2.Source: Appendix C · p. 28

Efficient updates

  • A stabilizer Kraus update runs in poly(n) time; when each channel acts on at most fixed b qubits, its runtime improves to O(b(4^b + 1)n^2) + O(b^2n^2/log(b)).The general-call bound is O(h(NK + 1)n^2) + O(n^4/log(n)); the fixed-locality bound follows from NK ≤ 4^b.Source: Appendix C · p. 29

Probability validity

  • Non-unitary Kraus transition probabilities may sum to less than one, so the update includes an abort outcome; the resulting probabilities are valid even for non-Hermitian dyads.The appendix bounds the sum of non-unitary transition probabilities by one and attributes the possible deficit to the initial dyad’s non-Hermiticity.Source: Appendix C · p. 29

Appendix C: Dyadic frame simulator technical details

  • The estimator is unbiased, and each sample has magnitude at most ∥α∥_1.Its expectation equals Tr[ΠE(ρ)].Source: Appendix C · p. 30
  • The total runtime scales as ∥α∥_1^2 ε^-2 log(1/p_fail) T poly(n).Each sample requires T calls to STABILIZERUPDATE, with each call computed in poly(n) time.Source: Appendix C · pp. 30–31

Appendix D: Trace norm error for BBCCGH sparsification

This appendix relates sparsification of stabilizer decompositions to trace-norm error for density operators. It states a sampled sparsification construction and outlines the proof approach.

Appendix D: Trace norm error for BBCCGH sparsification

  • The appendix translates the BBCCGH sparsification result for pure-state decompositions into a trace-norm statement for density operators.It presents this translation as a corollary to the earlier lemma.Source: Appendix D · p. 31
  • Given a stabilizer-state decomposition, one can sample a k-term sparsified vector from a distribution over such vectors.The displayed construction scales the sampled sum by ∥c∥1/k.Source: Appendix D · p. 31
  • The proof introduces the difference between the original and sparsified vectors, applies the triangle inequality, and invokes an expected squared-norm bound from BBCCGH.The excerpt does not state the resulting trace-norm bound.Source: Appendix D · p. 31

Appendix E: Post-selection, stabilizer fidelity and the sparsification tail bound in BBCCGH

The BBCCGH sparsification tail bound can be ineffective for intermediate-sized circuits, because its success guarantee depends strongly on stabilizer fidelity. The improved ensemble-based bound instead controls measurement statistics without requiring each sampled sparse vector to approximate the target state.

Post-selection and tail bound

  • The tail bound addresses the probability that a sparsified vector is close to the target, but its practical use also depends on the sampled vector having norm near or below 1.A post-selection step can estimate the norm and discard vectors that exceed 1 by much more than δ²; normalization alone does not resolve the bound’s limitation.Source: Appendix E · p. 31
  • For trace-norm error at most 10% and success probability above 1/2, the tail bound applies only when stabilizer fidelity is at most about 0.0009.This follows under the passage’s assumption that the sampled vector has norm close to 1.Source: Appendix E · p. 31

Tail-bound limitations

  • At least 45 copies of |T⟩ are needed for the bound’s condition, while about 1200 copies of |π/32⟩ are needed before it gives a non-trivial success-probability lower bound.The passage notes that improved accuracy or success probability increases the required copy count for |T⟩.Source: Appendix E · p. 32

Improved sparsification

  • The improved bound compares the target state with the sparsification ensemble, allowing bit-string sampling within δ even when an individual sparse vector is a poor approximation.The measurement statistics of the ensemble mimic those of the target state, so individual-vector closeness is unnecessary.Source: Appendix E · p. 32

Appendix F: Proof of ensemble sampling lemma

The ensemble sampling lemma bounds how closely the average of randomly sparsified vectors reproduces the target state. Its proof separates diagonal and off-diagonal contributions and uses independence for samples with distinct indices.

Lemma setup

  • The lemma considers a target state expressed as a stabilizer-state decomposition and a random k-term sparsification formed by sampling decomposition terms.Each sampled stabilizer state carries the phase of its coefficient and is selected with probability proportional to the coefficient magnitude.Source: Appendix F · p. 32

Ensemble bound

  • The ensemble ρ1 is defined by averaging the normalized sparsified states, and the proof bounds its trace-norm deviation from the target state.The proof splits the deviation into two contributions and introduces an operator to evaluate them.Source: Appendix F · p. 32

Proof strategy

  • Independence of distinct samples and the expectation of each sampled state are used to evaluate the off-diagonal terms in the bound.The proof counts the terms in the two sums and then applies the triangle inequality to complete the lemma.Source: Appendix F · pp. 32–33

Appendix G: Sparsification variance bound

The variance analysis tracks the constant C in the sparsification bound and its effect on the critical precision. For product states, the threshold vanishes with the number of factors, while C = 1 gives the asymptotic O(1/k²) variance scaling.

Variance bound

  • The overlap-product expansion separates terms with all four indices distinct from remaining terms with at least two repeated indices; in the distinct-index case, the two overlap factors are independent.Source: Appendix G · p. 33
  • When C = 1, the variance scales asymptotically as O(1/k²), and this scaling is exact at θ = π/8.The figure identifies C − 1 as the variance-bound prefactor and notes that it vanishes at this angle.Source: Appendix G · p. 34, Figure 8 · p. 35

Critical precision

  • For a tensor product of N pure states, the critical precision δc vanishes as N grows.The passage states that this holds when the single-factor states are non-stabilizer states.Source: Appendix G · p. 35

Single-qubit examples

  • For the plotted single-qubit states, C − 1 is close to zero even when N is not large.At θ = 0.1187, C is maximal and the figure shows the largest deviation from O(1/k²) scaling.Source: Appendix G · p. 35, Figure 8 · p. 35

Appendix H: Bit-string sampling simulator technical details

The bit-string simulator sparsifies input states, then samples output strings through sequential conditional probabilities estimated with FASTNORM. Its error and runtime bounds depend on sparsification precision, FASTNORM accuracy, and the chosen state decomposition.

Distribution and error bounds

  • The simulator’s idealized version produces a distribution within δS + O(δS²) of the quantum distribution when the sparsification precision is at least the critical threshold.The algorithm approximates this idealized sampler using FASTNORM calls.Source: Appendix H · pp. 35–36

Conditional sampling

  • FASTNORM estimates squared norms used to construct successive conditional bit probabilities, with multiplicative error controlled by its accuracy parameter.For ϵFN ≤ 1/5, the accumulated error over w bits is bounded by 3wϵFN.Source: Appendix H · p. 36

Runtime

  • When the decomposition is optimal for Ξ, the average-case runtime is O(Ξ(ρ)); for equimagical states, this expression gives the worst-case runtime.The analysis also relates the expected runtime to the decomposition’s monotone value.Source: Appendix H · p. 36

Precision regimes

  • The bound using the original sparsification regime requires overall precision δ ≥ 24D, with D set by the largest critical-threshold contribution among the mixture components.For δ < 24D, the algorithm can be modified to reach the requested precision at somewhat poorer runtime scaling.Source: Appendix H · p. 37
  • At sufficiently small target precision, the required sparsification size can exceed the exact decomposition size, making sparsification unhelpful.In that case, the passage recommends using the exact decomposition instead.Source: Appendix H · p. 37
Loading 2002.06181v4…