PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient quantum-enhanced classical simulation for patches of quantum landscapes

Sacha Lerch, Ricard Puig, Manuel S. Rudolph, Armando Angrisani, Tyson Jones, M. Cerezo, Supanut Thanasilp, Zoë Holmes

arXiv:2411.19896v2quant-phcs.LGstat.ML

TL;DR

The paper asks how hard it is to simulate fundamentally interesting circuits, including Trotter circuits with perfectly correlated parameters, across average-case and worst-case settings. The paper studies patch surrogation with progressively different quantum-resource requirements and extends the surrogate approach to gradient-based training. Surrogate-based approaches and GD show no clear performance distinction in shot and iteration comparisons, while the heavy-hex expectation landscape with 50 Trotter steps and m = 13550 gates was surrogated in under 30 seconds.

  • Problem

    The paper asks how hard it is to simulate fundamentally interesting circuits, including Trotter circuits with perfectly correlated parameters, across average-case and worst-case settings.

    Source: §4 · p. 57

  • Method

    The paper studies patch surrogation with progressively different quantum-resource requirements and extends the surrogate approach to gradient-based training.

    Source: §V · p. 11, §1 · p. 45

  • Results

    Surrogate-based approaches and GD show no clear performance distinction in shot and iteration comparisons, while the heavy-hex expectation landscape with 50 Trotter steps and m = 13550 gates was surrogated in under 30 seconds.

    Source: §V · p. 11, b. Results discussion · p. 46

  • Takeaways & Limitations

    The surrogate spends more quantum resources up front and reuses the acquired information across iterations, unlike gradient descent, which uses quantum resources at every step.

    Source: b. Results discussion · p. 46

    Generic polynomial resource guarantees were proved only for patch radius r ∈ O(1/√m).

    Source: g. How the polynomial guarantees break… · p. 30

Abstract

from arXiv · show

Understanding the capabilities of classical simulation methods is key to identifying where quantum computers are advantageous. Not only does this ensure that quantum computers are used only where necessary, but also one can potentially identify subroutines that can be offloaded onto a classical device. In this work, we show that it is always possible to generate a classical surrogate of a sub-region (dubbed a "patch") of an expectation landscape produced by a parameterized quantum circuit. That is, we provide a quantum-enhanced classical algorithm which, after simple measurements on a quantum device, allows one to classically simulate approximate expectation values of a subregion of a landscape. We provide time and sample complexity guarantees for a range of families of circuits of interest, and further numerically demonstrate our simulation algorithms on an exactly verifiable simulation of a Hamiltonian variational ansatz and long-time dynamics simulation on a 127-qubit heavy-hex topology.

I. INTRODUCTION

The paper develops classical and quantum-enhanced methods for simulating patches of quantum expectation landscapes, addressing the gap between whole-landscape surrogates for restricted circuits and mostly heuristic approaches for general circuits in restricted regions. Quantum resources can supply data for the surrogate, though preliminary training comparisons show no definitive winner between it and standard gradient descent.

I. INTRODUCTION

  • The framework spans fully classical simulation, quantum measurements of initial states, and quantum data collection for constructing a classical surrogate of a landscape patch.The quantum computer can be limited to collecting data for the surrogate, which can then be used for classical simulation.Source: §I · p. 1
  • Prior surrogate proposals addressed entire landscapes for restricted circuit families, while surrogating restricted regions of more general circuits had received little study beyond heuristic work.The paper also shows that surrogates are possible for previously proposed reduced-angle initialization strategies.Source: §I · p. 1
  • The surrogate approach does not generally eliminate quantum-device use: in generic settings, the device must generate the data unless that data is efficiently classically simulable.The paper frames this as a hybrid quantum-classical simulation framework.Source: §I · p. 1
  • Preliminary training comparisons are inconclusive, with regimes in which each of the surrogate and standard gradient-descent methods outperforms the other.The authors identify noise drift and cloud-hardware queuing times as potential practical benefits of surrogates.Source: §I · p. 2
  • The authors demonstrate applications beyond variational computing, including a long-time dynamics simulation of a 127-qubit transverse-field Ising model on a heavy-hex topology.The numerical simulations are presented as demonstrating utility beyond the regimes with strict analytic guarantees.Source: §I · p. 2

II. BACKGROUND

The background formulates expectation landscapes for parameterized quantum channels and places the paper’s approach within classical simulation and Pauli propagation methods.

II. BACKGROUND

  • The task is to simulate expectation values defined by an input state ρ, a Hermitian observable O, and a quantum channel Eα parameterized by an m-component real vector α.The expression can represent observables and losses in variational algorithms, real-time simulations, and quantum machine-learning tasks.Source: §II · p. 2
  • The paper’s classical-quantum surrogation techniques are a variant of LOWESA and belong to the broader family of Pauli propagation algorithms.The cited methods include Refs. [2] for LOWESA and [2, 4, 14, 26, 27, 47–55] for Pauli propagation.Source: §II · p. 2
  • The background introduces classical simulation and classical surrogatability before presenting the algorithmic approach.Source: §II · p. 2

A. Classical simulation and surrogation

Barren plateaus make typical expectation values concentrate around their average, but leave open whether small landscape regions retain substantial variance. The section connects polynomial variance lower bounds in reduced parameter regions with the possibility of classically surrogating those regions.

A. Classical simulation and surrogation

  • On a barren plateau, the probability of a randomly chosen parameter vector producing an expectation value that significantly deviates from its average vanishes exponentially with qubit count.The text notes that this is widely believed to hinder training with random initializations, while small regions may still have substantial variance.Source: A. Classical simulation and surrogation · p. 2
  • Across the reduced-parameter regimes considered, polynomial lower bounds on expectation-value variance imply that a classical surrogate can be constructed.The paper states this connection for variance lower bounds polynomial in n or m.Source: A. Classical simulation and surrogation · p. 2
  • Classical simulation approximates an expectation value in polynomial time with high probability over sampled parameters, or in the stronger version, for every parameter setting in a region.The stated approximation error and failure probability are arbitrarily small constants.Source: A. Classical simulation and surrogation · p. 2
  • A classical surrogate uses polynomial-time quantum data acquisition followed by classical simulation of expectation values over a parameter distribution.The discussion focuses on uniform distributions over hypercubes of width 2r around α*, and expects generalization to other reduced-range distributions.Source: A. Classical simulation and surrogation · pp. 2–3
  • Depending on the setting, quantum acquisition may use arbitrary polynomial-depth and -width circuits or only Pauli measurements on the initial state.The first option permits subsequent algorithms to run classically after an initial overhead; the second reduces quantum resources by offloading circuit simulation to a classical algorithm.Source: A. Classical simulation and surrogation · p. 3

B. Pauli Propagation

Pauli propagation back-propagates an observable through a circuit written as parameterized perturbations from Clifford operations, expressing its expectation through weighted Pauli terms. Because the raw number of paths can grow exponentially, the paper uses truncation, including a small-angle scheme for patches near Clifford circuits.

B. Pauli Propagation

  • Pauli propagation is most naturally applied to circuits expressed as parameterized perturbations from Clifford circuits, though the paper’s general complexity bounds also cover other circuit forms.The parameterized gates are rotations generated by Pauli operators; the analysis includes correlated and uncorrelated parameters.Source: B. Pauli Propagation · pp. 3–4
  • In the Heisenberg picture, the observable is back-propagated through the circuit and then overlapped with the initial state; Clifford gates map Pauli observables to Pauli observables.A non-Clifford Pauli rotation leaves a commuting Pauli unchanged and otherwise produces a weighted sum of two Paulis.Source: B. Pauli Propagation · p. 4
  • After propagation, the expectation is represented using coefficients for back-propagated Pauli operators, combining their observable weights with sine and cosine factors.Representing coefficients symbolically or graphically allows significant contributions to be reevaluated without recomputing every path, at the cost of initial time and memory overhead.Source: B. Pauli Propagation · p. 4
  • The raw number of Pauli paths grows exponentially with the number of Pauli rotations, so efficient simulation requires truncation.The paper gives guarantees for small-angle truncation on landscape patches corresponding to perturbations away from a Clifford circuit; weight truncation has also been used for noisy and random circuits.Source: B. Pauli Propagation · p. 4
  • The illustrated propagation evaluates the circuit in reverse, with Clifford CNOT gates contributing signs and non-Clifford rotations sometimes branching a Pauli string into two.The initial state need not be explicitly instantiated; only its traces against the final Pauli strings are evaluated.Source: Figure 2 · p. 4

A. Error guarantees

Theorem 1 guarantees classical surrogation of small patches under assumptions on derivatives and efficient estimation of low-order derivatives; it also gives a worst-case guarantee for a narrower patch. These results can support classical optimization within a patch, though obtaining the quantum measurements may itself require substantial circuit evaluations.

A. Error guarantees

  • A patch of width ∼1/√m can be classically surrogated for any expectation landscape meeting the stated derivative and measurement assumptions.The guarantee applies to random parameter settings with high probability; low-order partial derivatives must be efficiently estimable on a quantum computer.Source: A. Error guarantees · pp. 4–5
  • The proof uses a low-order Taylor truncation around α∗, under mild assumptions on partial derivatives that hold for many parameterized circuits, including arbitrarily deep circuits.The cited examples include uncorrelated Pauli-rotation ansätze and gates using Givens rotations.Source: A. Error guarantees · pp. 4–5
  • In regions where barren plateaus can be ruled out, the result permits preparing a surrogate quantumly and then optimizing it fully classically, rather than running the VQA adaptively.The average-case patch scale aligns with prior barren-plateau-free region results at r ∈ O(1/√m) [39].Source: A. Error guarantees · p. 5
  • For the smaller width O(1/m) patch, the algorithm guarantees worst-case error no greater than the chosen arbitrarily small constant.The average-case guarantee instead concerns random parameter settings in the broader patch.Source: A. Error guarantees · p. 5
  • For general circuits, constructing the surrogate may require quantum evaluations of the loss at multiple parameter settings to reconstruct a multivariate Taylor expansion.This can amount to measuring higher-order derivatives, making surrogate generation resemble higher-order gradient optimization.Source: A. Error guarantees · p. 5
  • A surrogate can support a few classical training iterations within its patch, but must be reconstructed once the trajectory leaves that region.The preliminary iterative strategy surrogates the loss gradient directly and compares measurement-shot requirements with standard gradient descent.Source: A. Error guarantees · p. 5

B. Numerical tests

In the numerical test, surrogate training continued to reduce the true loss over distances that scaled better with parameter count than Theorem 1’s bounds predict. Preliminary iterative-training comparisons are inconclusive, with each method outperforming the other in some regimes.

B. Numerical tests

  • The measured training distance scales roughly m^0.2 to m^0.3 better than the theoretical bounds, suggesting the surrogate remains useful over longer optimization distances than predicted.The experiment averages 20 random initializations and compares fitted lines with Theorem 1 scalings.Source: B. Numerical tests · p. 6
  • Standard gradient descent is operationally simpler, while iterative surrogate training adds hyperparameter choices such as how often to reconstruct the surrogate.The comparison is difficult to make fairly because the benchmark has many hyperparameters.Source: B. Numerical tests · p. 6
  • The fitted distances are ∥α∗−α0∥∞ = 1.10m−0.15, ∥α∗−α0∥2 = 0.80m0.20, and ∥α∗−α0∥1 = 0.63m0.70.The test uses a Heisenberg Hamiltonian, a zero initial state, and a variational ansatz with m = 3nL parameters.Source: Figure 3 · p. 6, B. Numerical tests · p. 6
  • The preliminary iterative-surrogate comparison is not definitive: the surrogate and standard gradient-descent methods each outperform the other in some regimes.The standard approach uses unbiased hardware-estimated gradients; numerical results suggest Taylor bias can sometimes be balanced by repeated-estimation noise, but this is not claimed generally.Source: B. Numerical tests · p. 6

IV. NEAR-CLIFFORD PATCHES

The near-Clifford method specializes Pauli propagation to patches centered on a Clifford circuit.

IV. NEAR-CLIFFORD PATCHES

  • The approach uses a truncation method specialized to near-Clifford patches centered on a Clifford circuit, reducing the quantum-computer requirements relative to the Taylor-surrogate approach.Source: §IV · p. 7

A. Error guarantees

For small-angle patches around zero, the method prunes Pauli paths with many sine terms.

A. Error guarantees

  • In a width-2r hypercube around zero, the method exploits smaller sine than cosine contributions and retains a chosen number of sine terms.The resulting average error decreases exponentially with the sine expansion order κ.Source: A. Error guarantees · p. 7

1. Classical time complexity

The paper gives time-complexity guarantees for small-angle Pauli propagation, distinguishing average-case simulation over random parameters from worst-case simulation throughout a parameter region. With a classically tractable initial state, it applies to arbitrary circuits in the stated family and to sufficiently small parameter regions.

Classical time complexity

  • Theorem 2 gives separate runtime guarantees for random parameter settings and for all settings in a hypercube, under assumptions on the observable and circuit.The stated assumptions include polynomially many nonzero Pauli coefficients with bounded 1-norm and m independent parameters; the runtime expressions are not specified in the supplied passages.Source: §1 · p. 7
  • Pauli propagation can efficiently simulate Pauli expectations for arbitrary circuits in the stated family across hypercubes of width O(1/√m), and smaller hypercubes of width O(1/m).The result assumes the initial-state Pauli expectations can be computed efficiently classically.Source: §1 · p. 7
  • For maximally correlated angles, average-case simulation is asymptotically as hard as worst-case simulation as a function of m, though the authors cannot distinguish a proof artifact from intrinsic difficulty.They specifically note that the issue may affect real-time quantum dynamics.Source: §1 · p. 7
  • For Hamiltonians with O(n) Pauli terms and O(1)-sized coefficients, the worst-case analysis guarantees efficient dynamics simulation on any geometry up to a stated time bound.The supplied passages do not preserve the value of that time bound.Source: §1 · p. 7

2. Sample complexity

When the initial state is not classically simulable, the method estimates its Pauli overlaps using quantum measurements and then constructs a classical surrogate. The section presents direct-measurement, coefficient-weighted, and classical-shadow approaches, with guarantees subject to their respective circuit and parameter-region conditions.

Sample complexity

  • For a non-classically simulable initial state, estimating Pauli overlaps requires quantum measurements, and the sampling step uses only polynomially many Pauli measurements.If the initial-state overlaps are classically computable, the previous section's time complexity fully quantifies the patch simulation instead.Source: §2 · p. 8
  • Direct Pauli measurements provide a shot-budget guarantee for surrogating the expectation function at random parameters in the stated hypercube regime.The theorem assumes polynomially many observable Pauli terms with bounded coefficient 1-norm; the supplied passages omit the shot-budget expression.Source: §2 · p. 8
  • Allocating shots in proportion to average Pauli contributions can make sample complexity depend on the effective 1-norm of averaged coefficients rather than the number of Pauli terms.The text identifies equal shots per term as generally suboptimal when terms contribute unequally across the patch.Source: §2 · p. 8
  • Pauli classical shadows have a guarantee for single-qubit Clifford layers and O(1)-local rotations, with random Pauli measurements over a uniformly sampled hypercube.The supplied theorem fragment omits the full shot-budget expression; the text notes that multi-qubit Clifford gates may make shadows underperform, while their measurements can estimate other quantities.Source: §2 · p. 8
  • In the 16-qubit TFI example at κ=6 and r=0.1, Pauli classical shadows are on par with effective 1-norm allocation, while uniform allocation underperforms.The figure compares total RMSE against quantum measurement count and compares allocation approaches at the stated setting.Source: Figure 4 · p. 9

B. Numerical resource and error scalings

The numerical experiments examine truncation error and measurement noise in a verifiable 16-qubit TFI Hamiltonian variational ansatz, then compare measurement allocations and a Heisenberg-model variant. Small-angle truncation can yield low RMSE, while shot noise and circuit structure affect the total error and allocation performance.

B. Numerical resource and error scalings

  • The test uses a middle-grid Z observable and an initial state obtained by exactly evolving the all-zero state for four Trotter layers.The 16-qubit TFI model uses a 4×4 nearest-neighbor grid and dt = 0.1.Source: B. Numerical resource and error scalings · p. 9
  • For angle range r = 0.1, the truncated-simulation root mean square error (RMSE), shown against the number of Pauli operators computed at increasing sine-truncation order κ, goes below 10^-6.Source: B. Numerical resource and error scalings · p. 9
  • For r ≤ 0.5, shot noise dominates total error even with 10^7 measurements, and the error scales approximately as 1/√Ns.At r = 0, a single operator perfectly reconstructs the landscape, yet total error still follows the measurement-noise scaling.Source: B. Numerical resource and error scalings · p. 9
  • In this example, uniform allocation understandably underperforms, while Pauli classical shadows and effective 1-norm allocation are on par; this setup is among the best-case scenarios for Pauli classical shadows.More global observables or patches around non-Identity unitaries deteriorate their relative performance.Source: B. Numerical resource and error scalings · pp. 9–10
  • In the Heisenberg HVA variant, more generated Pauli strings increase surrogation and measurement errors at the same resources, and 1-norm allocation underperforms without grouping.The authors identify pairing commuting observables and allocating resources as an open problem.Source: B. Numerical resource and error scalings · p. 10

C. Large-scale small-angle Pauli Propagation

The authors apply truncated Pauli propagation to a 127-spin, time-dependent TFI model on a heavy-hex topology and report long-time defect-density scaling across three annealing ramps. The simulation uses a constructed surrogate for repeated evaluations and reports high retained observable norm after 50 layers.

C. Large-scale small-angle Pauli Propagation

  • The simulation provides numerical evidence for the conjecture that heavy-hex defect density follows a scaling similar to the 1D model.The authors simulate significantly longer times than those possible with the quantum device in Ref..Source: C. Large-scale small-angle Pauli… · p. 10
  • A surrogate for the middle-lattice Z62Z63 observable, using 50 Trotter layers, took under 30 seconds to construct on one laptop CPU thread and under one second per evaluation.The simulation used dt = 0.3, Pauli-weight truncation at W > 5, and sine-order truncation at κ > 21.Source: C. Large-scale small-angle Pauli… · p. 10
  • All three annealing ramps exhibit the analytically known defect-density scaling, while the evolved observable retains 84%–99% of its original 2-norm after 50 circuit layers.The authors use the retained norm to verify the quality of the results.Source: C. Large-scale small-angle Pauli… · p. 10
  • Fast surrogate re-evaluation can support exploration of whole protocol families, including regimes where heavy-hex scaling may transition from tree-like toward 2D.The authors identify this transition as a direction for further exploration and suggest later deployment of protocols on quantum devices.Source: C. Large-scale small-angle Pauli… · p. 10

V. DISCUSSION

The discussion examines patch surrogation as a way to use quantum resources in preparation and then evaluate expectation-landscape subregions classically, including progressively less demanding resource scenarios and coefficient-aware measurements for fixed and parametrized observables. It summarizes Taylor-surrogate guarantees and evaluation requirements, while noting that surrogation is not necessarily faster than direct quantum evaluation.

V. DISCUSSION

  • Under 30 seconds to surrogate a 50-step, 13,550-gate heavy-hex simulation, with each expectation evaluation under one second; the surrogate verifies defect scaling resembling t−1/2 across annealing protocols.The test uses a time-dependent transverse-field Ising model with 127 spins and Pauli propagation.Source: §V · p. 11, Figure 5 · p. 11
  • Patch surrogates can reduce quantum gate and measurement demands across variational algorithms, machine learning, dynamical simulation, and sensing, and can support symbolic or global-minimization methods.The discussion also notes potential usefulness when hardware has limited coherence times or gate fidelities, and says computations may be linked within a circuit as hardware improves.Source: §V · p. 11
  • The three scenarios range from arbitrary patches in general circuits to Clifford-centered patches, where Pauli propagation enables efficient simulation and may require only polynomially many measurements.For classically tractable initial states, Clifford-centered surrogates can be computed entirely classically.Source: §V · p. 11
  • The authors do not establish that surrogation is faster than direct quantum execution; constants may increase total measurements and operations, and quantum speedups may remain possible for quantum-prepared initial states.Their numerics indicate Taylor surrogation can outperform their bounds while remaining broadly compatible with vanilla variational quantum algorithms.Source: §V · p. 11

Appendix B: Shot noise analysis for estimating observables with restricted measurements

  • With restricted measurable observables and operator-norm bound Λ, a probabilistic estimator uses 2Λ^2 log(2/δ)/ϵ^2 measurements on copies of the unknown state.The observable is decomposed over efficiently measurable terms with nonzero sampling probabilities.Source: Appendix B · p. 21

1. Warm-up: estimating a single observable

  • For a concentrated observable, uniform shot allocation requires exponentially more measurements than coefficient-aware allocation.The cited comparison gives uniform-allocation complexity O(16^n log(1/δ)/ε̃^2) in the example, versus O(log(1/δ)/ε̃^2) for the coefficient-aware protocol.Source: §1 · p. 23

2. Estimating parametrized observables

  • For parametrized observables, sample complexity is governed by an effective 1-norm: the average-case norm bounds mean square error, while its worst-case counterpart bounds maximum error.The mean-square-error protocol uses Ns = Λ^2∥c∥^2_1,avg/ε^2 measurements; the maximum-error bound uses 2 log(2/δ)Λ^2∥c∥^2_1,worst/ε^2 measurements and holds with probability 1 − δ.Source: §2 · pp. 23–24

3. Optimal sampling distributions

  • The optimal sampling distributions are derived by minimizing the relevant loss or mean square error with Lagrange multipliers.For maximum-error estimation, the derivation minimizes the worst-case objective subject to the sampling probabilities summing to one.Source: §3 · p. 25

1. Summary of the key results

  • The appendix gathers the key results underlying the general surrogatability guarantee and provides their proofs in subsequent sections.Source: §1 · p. 25

a. Taylor surrogate construction

c. Mean square error

  • For a uniform distribution over the hypercube, the κth-order surrogate also has a mean square error bound under the stated derivative conditions.The proposition assumes ∥O∥∞ ∈ O(1) and bounds derivatives of order greater than κ.Source: c. Mean square error · p. 27

d. Scaling of the number of expectation function evaluations with truncation order

  • Constructing the κ-order surrogate requires expectation-function evaluations for its partial derivatives, and quantum measurement estimates add statistical-fluctuation error.Proposition 3 bounds the number of required parameter settings in terms of the surrogate order and evaluations needed per derivative.Source: d. Scaling of the number of… · p. 28

e. General surrogation guarantee

This section establishes conditions and resource/error guarantees for quantum-measurement-assisted classical surrogates, including how surrogation order and patch size affect error and measurement costs. It describes applicable circuit families and surrogate methods, then outlines iterative gradient training and a shot-matched comparison with standard gradient descent for ground-state estimation.

e. General surrogation guarantee

  • For complex many-body observables, eigenbasis measurement may be impractical; expanding the observable into easier-to-measure terms, such as Paulis, is a straightforward generalization.The proof’s strategy estimates each surrogate term separately and distributes shots evenly, which is sub-optimal when terms commute or shot allocation could be more informative, but still achieves arbitrarily small constant error with high probability using polynomially many shots.Source: e. General surrogation guarantee · pp. 28–29
  • Under the theorem’s assumptions, increasing the Taylor order and using polynomially many measurement shots can make worst-case or mean-square surrogate error arbitrarily small for the stated perturbation regimes.The general guarantee assumes bounded observable norm and derivatives, efficient derivative estimation from expectation evaluations, and eigenbasis measurements; the worst-case discussion includes r ∈ O(1/m).Source: e. General surrogation guarantee · pp. 28–29

f. Guarantee that our assumptions are met by common parameterized quantum circuits

  • Parameterized unitary circuits with bounded generator and observable norms satisfy the derivative conditions, enabling efficient classical surrogation over uniformly sampled hypercubes around arbitrary parameter points.For uncorrelated Pauli rotations, parameter-shift derivatives use two evaluations with coefficient magnitude 1/2; derivatives across k distinct parameters use up to 2^k evaluations.Source: f. Guarantee that our assumptions are… · pp. 29–30

g. How the polynomial guarantees break down for larger patch sizes

  • Polynomial resource guarantees are proved only for patches with radius r ∈ O(1/√m); larger patches require super-polynomial resources, super-exponential at constant radius and sub-exponential when r ∈ O(1/m^β), 0 < β < 1/2.The authors do not rule out that other proof strategies could establish guarantees over larger regions.Source: g. How the polynomial guarantees break… · pp. 30–31

Pauli Propagation.

  • For Pauli propagation, the required number of terms is problem-dependent, while worst-case resources are exponential at constant radius and sub-exponential but super-polynomial for larger-than-polynomially-guaranteed patches.The maximal-splitting resource bound is an upper bound; r ∼ 1 is not meaningful in this framework, and setting κ = m removes truncation.Source: Pauli Propagation · p. 31

2. Absolute error: Proof of Proposition 1

  • The absolute-error proof bounds the Taylor remainder and shows that with r ∈ O(1/m), bounded γ and observable norm yield O(1) error that decreases with truncation order κ.Source: §2 · p. 32

3. Mean-square error: Proof of Proposition 2

  • The mean-square-error proof analyzes independent uniform parameter perturbations using the central limit theorem to bound moments of their normalized sum.The normalized sum approaches a standard normal distribution as the parameter count m grows, supporting the subsequent moment bound.Source: §3 · pp. 33–34
  • Increasing κ can make the mean-square error arbitrarily small; when ∥O∥∞ is in O(1), the proof gives a corresponding specialized bound.The supplied passage does not state the bound’s formula.Source: §3 · p. 36

4. Scaling of the number of expectation function terms for given surrogation order: Proof of Proposition 3

  • With b0 and Nd in O(poly(m)), polynomially many shots suffice to reduce empirical error, while increasing κ reduces truncation error.The worst-case analysis takes perturbation r in O(1/m) and bounds total error by truncation and shot-noise contributions.Source: §4 · pp. 38–39
  • For average-case perturbations r in O(1/√m), the effective norm scales polynomially with m when rm > κ, supporting a polynomially scaling error bound.Both measurement strategies can be used for this bound because the average-case effective 1-norm is upper-bounded by the worst-case one.Source: §4 · p. 39

6. Parametrised quantum circuits that satisfy assumptions: Proof of Proposition 4 and Corollary 2

  • If every generator has spectral norm in O(1) and the observable is bounded, the circuit satisfies Assumption 1 and the corollary follows.The proof bounds derivative norms using the largest generator norm.Source: §6 · p. 41
  • The Taylor and sine/cosine surrogates are roughly equivalent at a given order, with their difference arising from a term of order κ + 1.The passage attributes the equivalence to both methods dropping the same terms in the sine/cosine Taylor expansion.Source: §6 · p. 42
  • Pauli-propagation surrogates have errors of the same order as Taylor surrogates, so Theorem 1 indirectly bounds their efficiency; direct analysis can yield tighter bounds.The text says the tighter analysis follows in Appendix E.Source: §6 · p. 43

a. Fourier expansion

  • The expectation function is expanded in sine and cosine terms, with Fourier coefficients formed as products across circuit parameters.The expansion indexes each parameter by 0, 1, or 2.Source: a. Fourier expansion · p. 44

Appendix D: Iterative training strategy with patch surrogate

  • The iterative strategy builds a loss-gradient surrogate around a parameter point, takes several classical gradient steps, then re-surrogates around the updated point.The procedure is motivated as an alternative to estimating a loss gradient at every hybrid quantum-classical iteration.Source: Appendix D · p. 44

1. Description of a surrogate approach

  • A second-order Taylor model of the loss gradient is used, can be extended to higher orders, and is related to Quantum Analytic Descent [31].The passage notes that directly surrogating the loss gradient can be more appropriate for practical gradient-based training.Source: §1 · p. 45

a. Set-up

  • The experiment targets ground-state estimation for a rescaled Heisenberg chain using a variational ansatz with m = 3nL parameters.The setup compares shot-allocation strategies for the surrogate, including naive recomputation and an optimized approach that evaluates each loss once for repeated Hessian diagonal elements.Source: a. Set-up · p. 46

b. Results discussion

The tested surrogate strategies and standard gradient descent achieve comparable accuracy with similar quantum-resource use, without a clear overall winner. Surrogates shift more quantum work upfront for reuse across optimization iterations, while gradient descent uses quantum resources at every step.

b. Results discussion

  • The simulations used F2 = 600 shots per loss evaluation, 200 surrogate-training iterations, and 1,800 GD steps, with 10 runs sharing initial parameters.The learning rate was fixed at η = 0.1.Source: b. Results discussion · p. 46
  • Across the tested tasks, gradient descent and surrogate approaches show comparable quantum-resource use and both achieve good accuracy, with no clear performance distinction.Standard gradient descent can outperform in some regimes, while surrogate strategies outperform in others.Source: b. Results discussion · p. 46
  • Surrogates spend a larger quantum budget upfront and reuse the information across iterations, whereas GD consumes quantum resources at every step.The authors describe this as potentially reducing exposure to calibration drift and repeated cloud-job delays.Source: b. Results discussion · p. 46
  • At L = 6, standard GD achieved the best final test loss, whereas Surrogate 2 did so at L = 3; differences were small, particularly in interquartile range.Figure 6 plots test loss against quantum shots and iterations for a 10-qubit Heisenberg Hamiltonian, with medians and interquartile ranges over 10 runs.Source: b. Results discussion · p. 46, Figure 6 · p. 47

c. Further numerical experiment: Training inside a single patch

This section examines Pauli-surrogate guarantees and resource requirements under different parameter and measurement assumptions, including comparisons of shot-allocation strategies. It also tests how many gradient-descent steps a single surrogate supports before test loss rises, while noting that the optimal stopping point remains unknown in practice.

c. Further numerical experiment: Training inside a single patch

  • The study used the naïve surrogate with F2 = 600 and η = 0.1, running 20 independent trials for each n = L from 2 through 10.Each trial began from random parameters and recorded the maximum Niters before test loss began to increase.Source: c. Further numerical experiment:… · p. 47
  • Because test loss is unavailable in practice, selecting optimal Niters remains open; restricting parameters to radius r ∈ O(1/√m) could be suboptimal because training can extend beyond the patch.The suggested radius is where theoretical guarantees exist, but Fig. 3 indicates the surrogate can be trained beyond it.Source: c. Further numerical experiment:… · p. 47
  • Niters reached a minimum observed value of 9, supporting the earlier heuristic choice of Niters = 8–10; Fig. 8 shows means and min–max ranges across 20 initializations.The plot varies the number of parameters m; its solid curve is a power-law fit.Source: c. Further numerical experiment:… · p. 47, Figure 8 · p. 48

2. Uncorrelated parameters

  • For uniformly sampled parameters with r^2 ≤ 3κ/m, the mean-square error bound decreases faster than exponentially with κ; for arbitrary symmetric independent parameters, the variance condition is σ^2 ≤ κ/m.The uniform case follows by setting σ^2 = r^2/3 in the general uncorrelated-parameter bound.Source: §2 · pp. 55–56

3. Worst-case analysis

  • For worst-case parameter choices, the absolute error decreases faster than exponentially in κ whenever r ≤ 1/m, under the theorem’s condition r ≤ κ/m.The bound also applies when parameters are correlated and bounds the 1-norm of path coefficients.Source: §3 · pp. 56–57

4. Circuits with correlated parameters

  • For identical angles sampled uniformly from [−r, r], the average-error bound is the worst-case bound multiplied by 1/(κ+1), though whether their shared scaling reflects a deeper property remains open.This case models perfectly correlated angles, as in Trotter circuits when Hamiltonian coefficients are equal.Source: §4 · pp. 57–58

5. Time complexity of the Pauli Propagation algorithm

  • For observables with coefficient 1-norm O(1) and efficiently estimable Tr[ρP], small-angle Pauli propagation simulates zero-centered hypercube circuits with uncorrelated r ∈ O(1/√m) or worst-case r ∈ O(1/m).Each propagating-Pauli gate update takes time T, ranging from O(1) in the best case to O(n^3) in the worst case. Under worst-case guarantees, reducing Trotter error by shrinking time steps incurs only polynomial slowdown.Source: §5 · pp. 58–61

6. Sample complexity of the Pauli Propagation algorithm

  • For unknown input states, combining Pauli Propagation with randomized measurements gives polynomial sample complexity for constant error, and logarithmic system-size scaling when final back-propagated Paulis have low weight.The preceding time analysis instead assumes the input state is classically simulable.Source: §6 · p. 61

a. The truncated Heisenberg-evolved observable

  • The sample-complexity analysis bounds effective 1-norms for truncated Heisenberg-evolved observables, including general observables with bounded Pauli-basis coefficient 1-norm.The average-case effective norm is bounded by the worst-case effective norm.Source: a. The truncated Heisenberg-evolved… · pp. 61–62

b. Uncorrelated parameters

  • For independent uniform angles, the average-case Pauli surrogation theorem provides a randomized-measurement guarantee for observables with O(1) coefficient 1-norm and applies when r ∈ O(1/√m).The stated assumption can be relaxed to symmetric distributions satisfying the variance bound from the uncorrelated-parameter analysis.Source: b. Uncorrelated parameters · p. 62
  • For uncorrelated parameters, constant-weight terms in the truncated back-propagated observable allow classical shadows to reduce the required Pauli measurements.The guarantee assumes the hypotheses of Supplemental Theorem 8 and estimates the surrogate with probability at least 1 − δ.Source: b. Uncorrelated parameters · p. 64

c. Worst-case parameters

  • For worst-case parameters, an observable with bounded coefficient 1-norm and NPaulis terms admits a Pauli-propagation surrogate guarantee for r ∈ O(1/m).The guarantee holds with probability at least 1 − δ over both parameter and measurement randomness.Source: c. Worst-case parameters · p. 65

d. Even allocation of shots

  • Even shot allocation yields the surrogate guarantee for r ∈ O(1/√m), but its bound uses the coefficient 2-norm and an additional NPaulis factor.For the warm-up observable, the resulting bound is exponentially larger than effective 1-norm allocation; when the observable has polynomially many Pauli terms, both bounds remain polynomial in n and m.Source: d. Even allocation of shots · pp. 66, 68

7. Additional Numerical Results

  • For the 16-qubit Heisenberg HVA, Pauli shadow estimation outperforms 1-norm allocation, despite greater classical and quantum strain from generating more Pauli strings.The authors attribute the advantage likely to the ansatz’s increased structure and commuting terms: shadows implicitly group commuting strings for simultaneous estimation, unlike 1-norm allocation.Source: §7 · p. 68, Figure 9 · p. 69
Loading 2411.19896v2…