PaperlayerView exact revision on arXiv

Source-linked AI summary

Classically estimating observables of noiseless quantum circuits

Armando Angrisani, Alexander Schmidhuber, Manuel S. Rudolph, M. Cerezo, Zoë Holmes, Hsin-Yuan Huang

arXiv:2409.01706v2quant-phcs.CCmath-phmath.MP

TL;DR

Classical simulation is tractable for some restricted quantum systems, but the paper examines estimation on unstructured circuits across architectures. It uses low-weight Pauli propagation and proves that scrambling suppresses high-weight contributions, while the analysis remains average-case and has circuit-family boundaries.

  • Problem

    Classical simulation methods exploit restricted system properties, leaving the regimes where they can estimate observables on unstructured circuits an important question.

    Source: p. 1

  • Method

    The paper back-propagates observables in the Heisenberg picture and truncates the resulting Pauli expansion to low-weight terms.

    Source: pp. 1–2

  • Results

    Locally scrambling unitaries suppress high-weight Pauli contributions on average, supporting low-weight propagation for estimating expectation values without noise.

    Source: pp. 1–2

  • Takeaways & Limitations

    The results indicate that low-weight Pauli propagation can outperform brute-force light-cone methods on unstructured circuits, which are generally efficient only for very shallow, geometrically local circuits.

    Source: p. 2

    The guarantees are average-case, so some circuits within qualifying parameterized families can still defeat the algorithm.

    Source: p. 5

Abstract

from arXiv · show

We present a classical algorithm based on Pauli propagation for estimating expectation values of arbitrary observables on random unstructured quantum circuits across all circuit architectures and depths, including those with all-to-all connectivity. We prove that for any architecture where each circuit layer is randomly sampled from a distribution invariant under single-qubit rotations, our algorithm achieves a small error $\varepsilon$ on all circuits except for a small fraction $\delta$. The computational time is polynomial in qubit count and circuit depth for any small constant $\varepsilon, \delta$, and quasi-polynomial for inverse-polynomially small $\varepsilon, \delta$. Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries. We further conduct numerical experiments beyond our average-case assumptions, demonstrating the potential utility of Pauli propagation methods for simulating real-time dynamics and finding low-energy states of physical Hamiltonians.

I. End matter

The paper expresses Heisenberg-evolved observables as sums over Pauli paths and approximates expectation values by retaining low-weight terms. Locally scrambling unitaries suppress high-weight contributions on average and make distinct Pauli paths orthogonal.

Locally scrambling unitaries

  • Truncating the observable to Pauli terms of weight at most k approximates its expectation value because high-weight contributions are exponentially suppressed on average.The analysis uses properties of locally scrambling unitaries to bound the error of this low-weight approximation.Source: §I · pp. 5–6

Pauli path integral

  • The Pauli path integral sums over paths labeled by sequences of Pauli operators, with coefficients from layer transitions and a final projection onto the initial state.The path labels are γ = (s0, …, sL); the initial Pauli is sγ, and the projection coefficient is dγ = Tr[sγρ].Source: §I · p. 6

Low-weight Pauli Propagation.

Low-weight Pauli propagation approximates the Pauli path integral by restricting intermediate Pauli operators to weight at most k. Locally scrambling properties support error bounds, while a Monte Carlo estimate extends to ensembles with orthogonal Pauli paths.

Low-weight Pauli Propagation.

  • Restricting intermediate Pauli operators to weight at most k gives a truncated path integral that can be computed in polynomial time for polynomial depth and constant error and failure parameters.The method bounds the number of allowed Pauli pairs per layer and the total transition amplitudes needed.Source: Low-weight Pauli Propagation · pp. 6–7
  • High-weight Pauli terms have negligible expectation values after locally scrambling layers, while orthogonal paths have uncorrelated Fourier coefficients, supporting the truncation error bound.The total error is bounded by applying per-layer bounds iteratively with a telescoping sum.Source: Low-weight Pauli Propagation · p. 6
  • A Monte Carlo error-estimation method applies to ensembles with orthogonal Pauli paths, including some random single-axis rotation circuits beyond the locally scrambling setting.The text gives parameterized RZ(θ)-only rotations as an example.Source: Low-weight Pauli Propagation · p. 7

1. Notation and basic definitions

  • Here, k-local means an operator contains only Pauli terms of weight at most k; it does not mean the operator is geometrically local.The Pauli-2 norm is the normalized Hilbert-Schmidt norm and is bounded above by the operator norm.Source: §1 · p. 10

2. Properties of locally scrambling unitaries

This section defines locally scrambling circuits and develops properties for analyzing observable approximation, expressing circuit expectations as Pauli paths and introducing low-weight propagation as a truncated-path estimator. It derives a high-probability additive-error guarantee for this estimator and notes that the proof extends to suitable channels, including dynamic operations.

2. Properties of locally scrambling unitaries

  • Locally scrambling distributions are invariant under independent random single-qubit Clifford post-processing up to the second moment, with layered circuits also requiring independent layers and efficient, sparse Pauli evolution.The initial layer is allowed to act globally for convenience, while the final sparsity and computability condition is used only for complexity analysis and corresponds intuitively to sufficiently shallow layers.Source: §2 · p. 11
  • Locally scrambling unitaries yield orthogonality and Pauli-mixing properties, which eliminate cross terms and support mean-squared-error bounds for observable approximation.The section also relates Pauli-weight-dependent second moments to exponentially decreasing inner products, and shows that low-weight components can approximate observables on average over locally scrambled inputs.Source: §2 · pp. 12–14

B. The Pauli path integral

  • The Pauli path integral expands a circuit expectation using paths of Pauli operators and their associated Fourier coefficients, which are uncorrelated for locally scrambling circuits.Orthogonality of distinct paths is the property that makes truncating the path sum amenable to mean-squared-error analysis.Source: B. The Pauli path integral · p. 15

C. Low-weight Pauli propagation

  • Low-weight Pauli propagation restricts every intermediate Pauli on a path to weight at most k, and the section establishes an error bound for each iteration.The single-iteration bound applies to locally scrambling prefixes and is used iteratively to bound the estimator's mean-squared error.Source: C. Low-weight Pauli propagation · pp. 17–18

1. Then we obtain

  • The proof does not require unitary layers: it extends to locally scrambling channels that do not increase operators’ 2-norm on average under Heisenberg evolution, including feedforwards or probabilistic resets.The passage identifies dynamic operations considered in Ref. [69] as examples.Source: §1 · p. 18
  • For locally scrambling circuits, Corollary 18 gives a low-additive-error guarantee with probability at least 1 − δ over the circuit randomness.The corollary is obtained by combining Theorem 17 with Markov’s inequality.Source: §1 · p. 18

D. Time complexity

The runtime analysis counts Pauli transition amplitudes and tightens the bounds for circuit structures with limited gate size or geometric spread. It also gives a shallow-circuit bound for all-to-all connectivity.

General case

  • For general circuits, upper-bounding M by n gives runtime O(nk+O(1)L); invoking Corollary 18, runtime L·n^O(log(ϵ^-1δ^-1)) suffices to estimate the expectation value with precision ϵ∥O∥ and success probability 1−δ.Source: D. Time complexity · p. 20

Circuits with O(1)-qubit gates

  • With non-overlapping O(1)-qubit gates, at most O(n^kL) transition amplitudes are needed for a depth-L circuit.The bound assumes k is a sufficiently large constant.Source: D. Time complexity · p. 20

Circuits with constant geometric locality

  • For geometric dimension D, a weight-k observable’s evolved support is bounded by O(kL^D) qubits, enabling tighter transition-amplitude bounds.For non-overlapping O(1)-qubit gates, the text gives a further tightened bound.Source: D. Time complexity · p. 20

Circuits with all-to-all connectivity

  • For shallow all-to-all circuits with non-overlapping O(1)-qubit gates, the evolved support is at most 2^O(L) qubits and constant k requires at most 2^O(L) transition amplitudes.The bound is stated for Pauli observables of weight at most k.Source: D. Time complexity · pp. 20–21

E. Sample complexity of quantum-enhanced classical simulation

The section extends Pauli propagation to quantum-enhanced classical simulation, using randomized measurements when the initial state is unknown or not classically simulable. For an unknown state, the shadow-state procedure estimates the Pauli expectations needed for the low-weight observable approximation.

E. Sample complexity of quantum-enhanced classical simulation

  • Randomized measurements can be combined with low-weight Pauli propagation when the state or observable is unknown or not classically simulable.The section frames this as classical simulation enhanced by an initial quantum data-acquisition phase.Source: E. Sample complexity of… · p. 21

1. Unknown input state

  • For an unknown state, N = exp(O(k)) ϵ^-1 log(n/δ) random Pauli measurements suffice to construct a shadow state with the lemma’s stated error guarantee.The guarantee holds with probability at least 1 − δ.Source: §1 · p. 21
  • Randomized Pauli measurements estimate expectations of Pauli operators up to weight c·k, which are used to construct the shadow state.The proof uses non-overlapping c-qubit gates and estimates these expectations to additive error √ϵ with probability at least 1 − δ.Source: §1 · p. 21
  • Non-overlapping c-qubit gates ensure that evolving the low-weight observable approximation produces Pauli terms of weight at most c·k.This bounds which Pauli expectations the shadow state must match.Source: §1 · pp. 21–22

2. Unknown observable

For an unknown observable, the section uses randomized measurements on tensor products of single-qubit stabilizer states to estimate its low-weight Pauli components. It gives a general polynomial-measurement approach and a refined logarithmic-measurement approach for O(1)-local observables.

2. Unknown observable

  • The algorithms learn an approximate observable from measurements on tensor products of randomly chosen single-qubit stabilizer states.The approach is a modified version of an algorithm from Ref. and uses a Median-of-Means estimator.Source: §2 · p. 22
  • 68 · 9^k ϵ^-2 log(2/δ) measurements estimate a weight-k Pauli coefficient of an unknown observable with probability at least 1 − δ.Measurements are of the observable on tensor products of random single-qubit stabilizer states.Source: §2 · p. 22
  • The section gives two algorithms for estimating k-local components: one uses polynomially many randomized measurements for arbitrarily small constant error, while the O(1)-local specialization uses logarithmically many.The specialized algorithm is presented separately for observables containing only Pauli terms of weight O(1).Source: §2 · p. 23
  • The general procedure learns the low-weight component of the unknown observable, with the stated approximation guarantee holding with probability 1 − δ.It estimates the coefficients for Pauli operators of weight at most k and combines them into an observable estimate.Source: §2 · p. 23

a. Improved algorithm for O(1)-local observables

For O(1)-local observables, a specialized algorithm achieves arbitrarily small constant error with logarithmically many measurements. It filters estimated Pauli coefficients by a threshold, while the general guarantee can also benefit from a nontrivial bound on the low-weight component’s norm.

a. Improved algorithm for O(1)-local observables

  • The specialized algorithm achieves arbitrarily small constant error with logarithmically many measurements for O(1)-local observables.These observables contain only Pauli terms of weight at most O(1).Source: a. Improved algorithm for O(1)-local… · p. 24
  • The algorithm learns an approximate observable from measurements on tensor products of random single-qubit stabilizer states, with its stated guarantee holding with probability 1 − δ.The coefficient-estimation procedure covers Pauli operators of weight at most k.Source: a. Improved algorithm for O(1)-local… · p. 24
  • The algorithm filters out Pauli terms whose estimated coefficients fall below an appropriate threshold.The analysis bounds the contributions from filtered and unfiltered coefficients separately.Source: a. Improved algorithm for O(1)-local… · pp. 24–25
  • The first part of Lemma 28 applies even to possibly non-local observables and may outperform Lemma 26 when the low-weight component has a nontrivial norm bound.The text notes that using the general Minkowski bound instead yields sample complexity larger than Lemma 26’s.Source: a. Improved algorithm for O(1)-local… · p. 26

3. General case

For an unknown state and observable, the general theorem combines shadow-state and shadow-observable learning with low-weight Pauli propagation. Under its circuit and first-layer assumptions, the data-acquisition and classical runtime scale as n^O(log(ϵ^-1δ^-1)).

3. General case

  • The theorem covers unknown states and observables for locally scrambling circuit ensembles, assuming the first layer consists of non-overlapping O(1)-qubit gates.The theorem combines shadow-state learning, shadow-observable learning, and low-weight Pauli propagation.Source: §3 · pp. 26–27
  • Given ϵ, δ ∈ (0, 1), after n^O(log(ϵ^-1δ^-1)) randomized measurements, a classical algorithm runs in time n^O(log(ϵ^-1δ^-1)) and outputs a value α.Source: §3 · p. 26
  • The procedure learns shadow states and shadow observables, then runs the k-weight Pauli propagation algorithm on those estimates.The estimates are combined under simultaneous error events before applying the propagation guarantee.Source: §3 · pp. 26–27
  • The sample complexity can be considerably tightened when the observable is known or O(1)-local; for constant error, shadow-state and shadow-observable learning each require logarithmically many measurements in n when O is O(1)-local.The text identifies this as an exponential improvement.Source: §3 · p. 27

F. Comparison with light-cone simulation

The section compares low-weight Pauli propagation with light-cone simulation and the trivial estimator. Its advantages depend on the error and circuit-depth regime.

F. Comparison with light-cone simulation

  • For constant error and failure probability, light-cone simulation costs 2^O(L^D), while weight truncation costs poly(L^D), yielding an exponential-in-L reduction in computation time.This comparison concerns depth-L geometrically local circuits and a local observable.Source: F. Comparison with light-cone simulation · pp. 27–28
  • For inverse-polynomial error and failure probability at L = log^c(n), the stated costs are n^O(log^(cD−1)(n)) for statevector light-cone simulation and n^O(cD log log(n)) for weight truncation.The passage notes that for cD ≥ 2, the scaling is n^poly log(n) versus n^O(log log(n)).Source: F. Comparison with light-cone simulation · p. 28
  • For near-exact simulation, both methods cost 2^O(L^D), but statevector simulation may be faster on specialized hardware.The passage also compares memory scaling and notes that structural truncations could make the comparison more subtle.Source: F. Comparison with light-cone simulation · p. 28

G. Comparison with the trivial estimator

  • Low-weight Pauli propagation consistently outperforms the trivial estimator in mean squared error, but at high depths becomes indistinguishable from it on typical random circuits.The section connects this high-depth limitation to the inability to refute XQUATH or spoof linear XEB on circuits of linear depth.Source: G. Comparison with the trivial estimator · p. 28

1. Improvement over the trivial estimator

The section establishes that low-weight Pauli propagation improves on the trivial estimator for circuits with independent locally scrambling layers. The improvement is expressed through the estimators’ variances.

1. Improvement over the trivial estimator

  • Low-weight Pauli propagation always outperforms the trivial estimator under the stated circuit and observable setting.The proposition assumes independent locally scrambling layers, an observable, and a quantum state.Source: §1 · p. 28
  • For locally scrambling circuits, the trivial estimator’s mean squared error is the variance of the expectation value.The passage identifies this variance as the benchmark for comparison.Source: §1 · p. 29
  • The difference between the expectation-value variance and the truncated estimator’s variance quantifies the improvement over the trivial estimator.The stated relation is the mean squared error of the low-weight Pauli propagation estimator.Source: §1 · p. 29

2. Improvement of weight-1 Pauli propagation over the trivial estimator

The section gives consequences of the variance comparison for weight-1 propagation. Under local 2-design assumptions, it connects accuracy and runtime advantages with the behavior of local observables.

2. Improvement of weight-1 Pauli propagation over the trivial estimator

  • The variance result is stated for random circuits with local 2-designs in arbitrary geometric dimension.The broader proposition considers locally scrambling layers composed of non-overlapping single- and two-qubit gates sampled from local 2-designs.Source: §2 · p. 29
  • For brickwork circuits, the proof’s “case 2” does not occur, allowing the improvement of weight-1 propagation over the trivial estimator to be quantified precisely.The supplied passage does not state the resulting numerical value.Source: §2 · p. 31
  • Local observables do not suffer from barren plateaus on logarithmic-depth circuits under the stated local 2-design assumptions, independently of geometric dimension.The corollary assumes non-overlapping single-qubit and two-qubit gates sampled from local 2-designs.Source: §2 · p. 31
  • For logarithmic-depth circuits with geometric dimension D > 1, weight-1 propagation can be both significantly more accurate than the trivial estimator and super-polynomially faster than brute-force simulation.The stated setting is a weight-1 Pauli observable and circuits satisfying Proposition 32’s assumptions.Source: §2 · p. 31

3. Implications for the XQUATH conjecture

The section relates improvement over the trivial estimator to XQUATH, a conjecture about efficient classical estimation of random-circuit output probabilities. It concludes that low-weight Pauli propagation cannot refute the conjecture for random brickwork circuits at sufficiently large linear depth.

3. Implications for the XQUATH conjecture

  • XQUATH rules out an efficient classical algorithm that achieves a slightly better variance than the trivial estimator for estimating random-circuit output probabilities.The conjecture is described as central to the complexity-theoretic foundation of linear cross-entropy benchmarking.Source: §3 · p. 31
  • A previous single-Pauli-path algorithm refuted XQUATH for random brickwork circuits at sublinear depths, motivating the question of whether low-weight propagation extends that result.The cited prior result gives XQ = 15^-L and identifies depths smaller than approximately n/4.Source: §3 · p. 32
  • For random brickwork circuits of depth L ≥ c·n, low-weight Pauli propagation cannot be used to refute XQUATH for some constant c > 0.The section derives this boundary from a result for circuits built from two independently sampled approximate unitary 2-designs.Source: §3 · p. 34
  • The authors note that their upper bound is loose because it counts only the first truncation, while the algorithm truncates at every circuit layer.They suggest the proof technique could extend to virtually any efficiently computable Pauli propagation method.Source: §3 · p. 34

H. Numerical error certificates

The section uses the squared Fourier spectrum of Pauli paths to estimate mean-squared error by Monte Carlo sampling. Under its sampling assumptions, the procedure runs in time poly(n)Lϵ^-2 log(1/δ).

H. Numerical error certificates

  • The certified-error method estimates mean-squared error by Monte Carlo sampling, treating renormalized squared Fourier coefficients as probabilities.For random circuits with orthogonal Pauli paths, the Fourier coefficients of distinct paths are uncorrelated.Source: H. Numerical error certificates · p. 35
  • The error-estimation theorem assumes orthogonal Pauli paths and efficient sampling from the observable’s squared Pauli spectrum.The stated sampling assumption is that this spectrum can be sampled in time poly(n).Source: H. Numerical error certificates · p. 35
  • The algorithm samples Pauli-path strings iteratively, beginning from the observable’s Pauli spectrum and then sampling backward through the circuit layers.It returns the sampled path string after the sequence of layer-wise draws.Source: H. Numerical error certificates · p. 36
  • The sampling algorithm requires time poly(n)L, and the entire procedure runs in time poly(n)Lϵ−2 log(1/δ), with probability at least 1−δ.Source: H. Numerical error certificates · pp. 35–36

I. Further numerical experiments beyond our bounds

The further experiments test Pauli propagation beyond the paper’s average-case assumptions, including circuits with non-scrambling or correlated layers and variational ground-state optimization. They find that truncation accuracy can decline during optimization, while approximate training can still discover parameters yielding low exact energies.

I. Further numerical experiments beyond our bounds

  • For a 127-qubit heavy-hex circuit that is not locally scrambling, the general error bounds were nevertheless satisfied, and early layers were simulated quickly and nearly exactly.The circuit uses RX and RZZ rotations associated with transverse-field Ising evolution; its initial ease is attributed to simulation inside the entangling light cone.Source: §I · p. 36
  • The 16-qubit correlated-angle experiment compares independently randomized gate parameters with one shared random parameter and reports untruncated-loss variance as a concentration indicator.The caption associates exponential concentration with uncorrelated parameters and its absence with correlated parameters.Source: Figure 4 · p. 37
  • During exact-statevector optimization, Pauli-propagation accuracy gradually declined at constant weight truncation, limiting extension of the average-case bounds to low-energy circuits.The example is ground-state optimization for the Heisenberg model.Source: §I · pp. 37–38
  • Low-weight Pauli propagation optimization found parameters whose exact statevector energies were very low, comparable to those from statevector optimization, despite unphysical estimated energies.The optimization used a 10^-3 coefficient truncation; the truncated landscape could still identify good minima overlapping the exact-energy landscape.Source: §I · p. 38
  • The authors suggest hybrid strategies: use Pauli propagation for classical training or warm-starting, then use a quantum device to evaluate energies or finish training.They note that exact-simulator training may converge faster to a good solution.Source: §I · p. 38
Loading 2409.01706v2…