PaperlayerView exact revision on arXiv

Source-linked AI summary

Average-case Speedup for Product Formulas

Chi-Fang, Chen, Fernando G. S. L. Brandão

arXiv:2111.05324v2quant-phmath-phmath.FAmath.MPmath.PR

TL;DR

Worst-case gate-complexity estimates may not describe typical product-formula inputs, motivating an average-case analysis of Trotter error. The paper derives typical-input bounds and finds 2-norm scaling for most basis-drawn states, with substantial improvement over worst-case estimates for large-connectivity systems.

  • Problem

    Existing product-formula gate-complexity estimates capture worst-case scaling, leaving open whether typical inputs have milder Trotter error.

    Source: §I · p. 3

  • Method

    The paper analyzes the distribution of Trotter error across inputs drawn from an orthogonal basis to derive average-case gate-complexity bounds.

    Source: §I · p. 3

  • Results

    For large-connectivity Hamiltonians, the local 2-norm estimate substantially improves typical-case gate complexity over worst-case results.

    Source: §I · p. 3

  • Takeaways & Limitations

    Analytic and numerical evidence indicates that average-case and worst-case estimates can both be tight because they address different questions.

    Source: §I · p. 3

Abstract

from arXiv · show

Quantum simulation is a promising application of future quantum computers. Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. For an accurate product formula approximation, the state-of-the-art gate complexity depends on the number of terms in the Hamiltonian and a local energy estimate. In this work, we give evidence that product formulas, in practice, may work much better than expected. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states, while the existing estimate is for the worst states. For general $k$-local Hamiltonians and higher-order product formulas, we obtain gate count estimates for input states drawn from any orthogonal basis. The gate complexity significantly improves over the worst case for systems with large connectivity. Our typical-case results generalize to Hamiltonians with Fermionic terms, with input states drawn from a fixed-particle number subspace, and with Gaussian coefficients (e.g., the SYK models). Technically, we employ a family of simple but versatile inequalities from non-commutative martingales called $\textit{uniform smoothness}$, which leads to $\textit{Hypercontractivity}$, namely $p$-norm estimates for $k$-local operators. This delivers concentration bounds via Markov's inequality. For optimality, we give analytic and numerical examples that simultaneously match our typical-case estimates and the existing worst-case estimates. Therefore, our improvement is due to asking a qualitatively different question, and our results open doors to the study of quantum algorithms in the average case.

I. INTRODUCTION

Existing product-formula gate-complexity guarantees reflect worst-case coherent scaling, prompting the question of whether typical inputs instead exhibit milder scaling. The paper finds that most basis-drawn inputs have root-mean-square scaling, with larger-connectivity systems showing substantial gains over worst-case estimates.

I. INTRODUCTION

  • Product formulas remain attractive for constrained near-term or early-fault-tolerant simulation because their simple prescription requires no controlled ancilla.Numerical case studies suggest they may outperform more advanced methods.Source: §I · p. 2
  • With high probability, inputs drawn from any orthogonal basis exhibit root-mean-square, or 2-norm, gate-complexity scaling, unlike the existing worst-case estimate.The paper describes Trotter error as a high-dimensional object whose distribution across inputs cannot be captured by a single bound.Source: §I · p. 3, Figure 1 · p. 3
  • For large-connectivity Hamiltonians, the local 2-norm estimate yields substantial improvement over the worst-case bound; with random coefficients, even worst-case inputs have 2-norm scaling.The local estimate sums squared term strengths over supports overlapping each site; the paper notes resource reductions for simulation tasks.Source: §I · p. 3
  • Analytic and numerical examples show that average-case and worst-case estimates can be simultaneously tight, because they address qualitatively different questions.The paper presents this as evidence that product formulas may work better in practice than worst-case estimates suggest.Source: §I · p. 3
  • The average-case analysis combines matrix concentration inequalities, including uniform smoothness and hypercontractivity, with a commutator expansion of exponential products.The authors describe this framework as simple and robust.Source: §I · p. 3
  • Compared with, the paper claims stronger typicality than a variance-only analysis, tighter gate complexity for non-spatially local models, and results for random Hamiltonians.Its typicality statement uses higher moments and holds for all but exponentially rare inputs.Source: §I · p. 4

A. Summary of Results

The results section considers Lie-Trotter and Suzuki product formulas, including recursively constructed higher-order Suzuki formulas.

A. Summary of Results

  • The analysis considers the first-order Lie-Trotter formula and the second-order Suzuki formula.These are introduced as the main Hamiltonian simulation methods studied in the section.Source: A. Summary of Results · p. 4
  • Higher-order Suzuki formulas are considered for even orders ℓ = 4, 6, …, 2p, ….The formulas are constructed recursively.Source: A. Summary of Results · p. 4
  • The recursive construction defines S2p(τ) from three S2p−2 factors with time parameters qpτ and (1−4qp)τ, where qp = 1/(4−41/(2p−1)).The outer factors use qpτ and the middle factor uses (1−4qp)τ.Source: A. Summary of Results · p. 4

1. Non-random Hamiltonians

For non-random k-local Hamiltonians, the section gives higher-order Suzuki gate-count bounds and typical-input results, including for states drawn from a 1-design. The improvement over worst-case estimates depends on the Hamiltonian model and connectivity.

1. Non-random Hamiltonians

  • Corollary I.1.1 applies the gate-count result to states drawn from a 1-design, including an orthonormal basis, with high probability.The section presents Theorem I.1 as a gate-count result for simulating a k-local Hamiltonian with an ℓth-order Suzuki formula.Source: §1 · p. 4
  • Spatially local models have no average-case speedup at higher formula orders because their connectivity is constant and their local 1-norm and 2-norm are independent of system size.The caption states that speedup occurs only at low orders for these models, through the global norm comparison.Source: Table I · p. 5
  • Large-connectivity models, including the discussed power-law regime, show substantial typical-case improvement over worst-case results.The power-law models are defined on a d-dimensional lattice with interaction strengths bounded by |x−y|^-α, focusing on d/2 ≤ α ≤ d.Source: §1 · p. 5
  • For a constructed Hamiltonian, the Schatten p-norm saturates the typical-case estimates while the operator norm saturates the state-of-the-art worst-case bound.The example separates the two estimates by addressing different input-state questions.Source: §1 · p. 5
  • At large subsystem sizes, the example’s first- and second-order Trotter formulas match the paper’s p-norm estimates and the spectral-norm estimates up to constant factors.The example uses a 2-local Hamiltonian on three subsystems of qubits.Source: §1 · p. 5
  • The dependence on the number of terms Γ is not optimal for non-uniform term strengths; truncation can improve gate complexity at early times.The paper also notes that truncation error enjoys concentration.Source: §1 · p. 5
  • Numerics for disordered two-body models with all-to-all or nearest-neighbor interactions appear to match predicted dependence on system size, time, and formula order.The errors are averaged over disorder realizations, which the authors say illustrates the robustness of their bounds.Source: §1 · p. 5

2. Random Hamiltonians

For Gaussian-coefficient random Hamiltonians, the paper gives higher-order Suzuki gate-count results that hold with high probability for arbitrary fixed input states. Numerical studies also compare observed Trotter-error scaling with theoretical bounds across system sizes and formula orders.

2. Random Hamiltonians

  • The random-Hamiltonian gate-count result is motivated by ensembles such as SYK with random coefficients.The passage introduces random Hamiltonians as an ensemble of interest, particularly for SYK models.Source: §2 · p. 5
  • With high probability, random Gaussian-coefficient k-local models have 2-norm Trotter-error scaling for an arbitrary fixed input state.The complete bounds depend on finite formula order and failure probability.Source: §2 · p. 6
  • A gate count larger by a factor of √n controls worst inputs that may correlate with the random Hamiltonian.The typical-input result applies to an arbitrary fixed state; the stronger guarantee addresses worst inputs.Source: §2 · p. 6
  • For the spatially local Heisenberg model, the empirical size exponents are 0.46 ± 0.01 for average inputs and 1.18 ± 0.02 for worst inputs.The average-input exponent matches the stated bound of 1; the worst-input exponent is described as consistent with its bound of 1.Source: Figure 6 · p. 7
  • An analytic construction gives e^Ω(Γ) distinct k-local Hamiltonians whose pairwise separation is at least Ω(√n).If their matrix exponentials are also distinct, a circuit-complexity lower bound matches the stated fixed-input and typical-input gate complexity at early times.Source: §2 · pp. 7–8
  • For random all-to-all Heisenberg models, the worst-input empirical system-size exponent is 2.56 ± 0.1, below the theoretical bounds of 3.5 and 4.The comparison is with the stated random-Hamiltonian and non-random-Hamiltonian bounds, respectively.Source: Figure 7 · p. 8

B. Proof ingredients

The proof must control both higher-order terms in the Trotter error and concentration of the commutator. The paper notes that higher-order product formulas have leading errors that are polynomials of commutators.

B. Proof ingredients

  • The Trotter error is a complicated matrix-valued function, with a commutator as the leading-order error in the first-order formula.Source: B. Proof ingredients · p. 8
  • For an ℓ-th order product formula, the leading-order error is a degree ℓ + 1 polynomial of commutators.Source: B. Proof ingredients · p. 8
  • The proof faces two technical tasks: controlling the infinite series of higher-order terms and obtaining concentration bounds for the commutator.Source: B. Proof ingredients · p. 8

1. A Good Presentation of Error

The error analysis represents product-formula error through nested commutators and expands those commutators in time. This provides a polynomial form to which the paper applies matrix concentration tools and combinatorial bounds.

1. A Good Presentation of Error

  • Higher-order Suzuki formulas use Υ stages, each passing through every Hamiltonian term once, for a total of J = Γ · Υ exponentials.For the first-order Lie-Trotter formula, each term appears once and Υ = 1.Source: §1 · p. 9
  • The product-formula error is represented in time-ordered exponential form and then as a sum of nested commutators.Source: §1 · p. 9
  • A Taylor expansion in time turns each order of the nested-commutator error into a polynomial of matrices.The proof does not require the particular orderings of product formulas.Source: §1 · p. 9
  • The resulting polynomial error is analyzed with matrix concentration tools and a combinatorial bound.The passage says this combinatorial step is more involved than obtaining the 1-norm quantity in.Source: §1 · p. 9

2. Uniform Smoothness, Matrix Martingales, and Hypercontractivity

The proof uses recursive p-norm inequalities and non-commutative martingale structure to obtain sum-of-squares bounds for local operators. These bounds support hypercontractivity and concentration estimates, including versions for Gaussian randomness.

2. Uniform Smoothness, Matrix Martingales, and Hypercontractivity

  • The scalar example interprets a trace as an expectation over independent Rademacher variables, whose typical eigenvalue magnitude is O(√n), below the largest eigenvalue.Source: §2 · p. 9
  • Recursive inequalities for p-norms lead to concentration through Markov's inequality.The paper introduces the scalar two-point, or Bonami, inequality as an ancestral version.Source: §2 · p. 10
  • Uniform smoothness for k-local operators leads to hypercontractivity, or concentration bounds for those operators.Source: §2 · p. 10
  • The paper relates k-local operators to non-commutative martingales and develops subsystem forms of uniform smoothness for that structure.Source: §2 · p. 10
  • For k-local operators, subsystem uniform smoothness uses a non-commutative martingale condition and yields sum-of-squares behavior rather than linear growth.Source: §2 · p. 10
  • For Gaussian coefficients, the paper uses uniform smoothness for expected p-norms to control the spectral norm and worst input states.Source: §2 · pp. 10–11

C. Discussion

For many non-random k-local Hamiltonians, the paper gives average-case gate complexity that is qualitatively better than the worst-case and directly reduces resources for quantum simulation. It leaves open whether other quantum algorithms also have average-case speedups.

C. Discussion

  • Average-case gate complexity is qualitatively better than worst-case for many physical systems, directly reducing quantum-simulation resources without changing the product formula.The result holds with high probability for inputs drawn from any orthonormal basis.Source: C. Discussion · p. 11
  • The probabilistic argument does not identify exceptional states, leaving the behavior of practical states such as ground states unresolved.The authors suggest that low-energy states need not align with states extremizing Trotter error, and call for small-scale numerics.Source: C. Discussion · p. 11
  • Whether other simulation methods or quantum algorithms enjoy average-case speedups remains an open question.The paper notes that such speedups, if present, could improve the feasibility of quantum-computing applications.Source: C. Discussion · p. 11

II. PRELIMINARY: k-LOCALITY, UNIFORM SMOOTHNESS, AND HYPERCONTRACTIVITY

This section develops tools for estimating the strength of local operators on typical states, using uniform smoothness to derive moment bounds and generalize them to subalgebras.

II. PRELIMINARY: k-LOCALITY, UNIFORM SMOOTHNESS, AND HYPERCONTRACTIVITY

  • A k-local operator has Pauli strings of length at most k; typical-state strength is framed through concentration and Schatten p-norm estimates.The weighted 2-norm corresponds to variance, while the weighted p-norm governs tail bounds.Source: §II · pp. 11–12

A. Uniform Smoothness for Subsystems

  • Uniform smoothness for subsystems uses a partially traceless martingale condition, with partial trace acting as conditional expectation.The framework is presented as a versatile route to Hypercontractivity.Source: §II · p. 12

1. Subalgebras

  • The subsystem argument extends to finite-dimensional subalgebras using a projection or trace-preserving conditional expectation.The section also establishes monotonicity of p-norm under projection to a subalgebra.Source: §1 · p. 14

B. Deriving Hypercontractivity

Recursive uniform smoothness yields Hypercontractivity-style moment estimates for local operators, which support concentration bounds and extensions to product-state and low-particle settings.

B. Deriving Hypercontractivity

  • Recursive uniform smoothness yields Hypercontractivity and p-moment estimates for local operators, with the martingale formulation facilitating extensions to other settings.For 4-local Paulis, the sum-of-squares behavior persists with heavier tails that still decay super-polynomially.Source: B. Deriving Hypercontractivity · pp. 14–15

C. Product Background States

1. Low-particle number subspace

  • A low-particle-subspace p-norm is controlled through a product-state bound, with Poly(n,m) overhead mild when p ≳ log(Poly(n,m)).The discussion motivates this comparison as a way to use product-state estimates for fixed-particle-number settings.Source: §1 · p. 17

D. Fermionic Operators

This section extends uniform smoothness and hypercontractivity to fermionic operators and applies hypercontractivity to Trotter error bounds for non-random k-local Hamiltonians. It develops commutator and combinatorial estimates, including overlap decompositions and bounds for higher-order Taylor remainders.

D. Fermionic Operators

  • Jordan-Wigner strings make fermionic operators nonlocal, but their conditionally zero-mean martingale structure still permits uniform smoothness and a related 2-norm-like bound.The derivation tweaks the bound to account for Jordan-Wigner strings.Source: D. Fermionic Operators · p. 18
  • For p ≥ 2, Corollary II.7.1 gives fermionic hypercontractivity with Cp = p − 1, and Corollary II.7.2 extends it to the stated product-state background Oη.The latter background is diagonal in the computational basis with identical single-qubit states parameterized by η.Source: D. Fermionic Operators · p. 18

III. NON-RANDOM k-LOCAL HAMILTONIANS

  • Theorem III.1 gives a gate-complexity estimate for simulating a k-local Hamiltonian with an ℓ-th order Suzuki formula.The section evaluates hypercontractivity for Trotter error in non-random Hamiltonians; the supplied theorem passage does not include the bound's full expression.Source: §III · p. 19
  • Drawing an input state from an orthonormal basis converts the p-norm estimate into a typical-state concentration bound via Markov’s inequality.The corollary assumes a basis distribution with average state I/Tr[I].Source: §III · p. 19

A. An instructive example

  • The leading-order O(t^2) Trotter error is a sum of 3-local and 1-local terms; the 1-local terms are equally important despite having a single sum over i2.The 1-local terms come from terms that overlap on both sites, with constructive interference over site i1 yielding a comparable contribution.Source: A. An instructive example · p. 19

B. Proof Outline

  • The proof expands the time-dependent commutator error in powers of time, bounds each order using hypercontractivity, then truncates the expansion before applying Markov’s inequality.For 2ℓ-th order Suzuki formulas, it uses a uniform coefficient bound |ak| ≤ 1 and a stage count Υ = 2 · 5ℓ/2−1.Source: B. Proof Outline · p. 20

C. Bounds on the g-th Order

  • Expression (3.3) gives the desired estimate for the g-th-order error term, but the power series is not summable due to the super-exponential factor g2gk; the expansion is later truncated at a properly chosen order g′.Source: C. Bounds on the g-th Order · p. 21

1. “Greedy growth” :Overlapping at 1 site; 2. Cancellation and collision due to larger overlap

  • When supports overlap at one site, commutator terms grow greedily by taking the union of supports; larger overlaps can instead cancel sites while adding new ones.For Pauli strings, at least one site remains occupied after cancellation, whereas the fixed subset may be empty for Fermions.Source: C. Bounds on the g-th Order · p. 21, §2 · p. 23

2. Cancellation and collision due to larger overlap

  • The larger-overlap analysis decomposes sets into S_f, S_−, S_+, and S_0 and organizes the bound by summing over |S_f|.The derivation also uses triangle and Cauchy–Schwarz inequalities to control the resulting sums.Source: §2 · pp. 24–25

D. Bounds for g′-th Order and Beyond.

E. Proof of Theorem III.1

The proof develops norm, hypercontractive, and matrix-martingale tools to establish concentration and error bounds for product formulas under random Hamiltonians, including Gaussian and repeated-term cases. It also extends typical-case analyses to fixed-particle spin and fermionic systems and treats higher-order error terms.

E. Proof of Theorem III.1

  • For large time, system size, and error at fixed failure probability, the first term dominates and the gate complexity is G = r · Υ · Γ.The proof bounds long-time Trotter error by a telescoping sum and obtains concentration for singular values or 1-design inputs via Markov’s inequality.Source: E. Proof of Theorem III.1 · pp. 27–29

1. Constant overhead improvement from another Hypercontractivity

  • Using another hypercontractivity bound requires the same combinatorial estimates and yields only minor constant improvements; the local 2-norm still involves a spectral norm and further accounting.The proof presents its gate-count expressions for numerical evaluation and suppresses functions of k and ℓ with Ω(·) for comprehension.Source: E. Proof of Theorem III.1 · p. 28, §1 · p. 29

F. Spin Models at a Low Particle Number

  • For number-preserving k-local spin Hamiltonians, Proposition III.5.1 gives gate complexity on the m-particle subspace, and Corollary III.5.1 gives concentration for randomly drawn states from that subspace.The proof uses an auxiliary product state with filling ratio η = m/n to convert to weighted p-norms.Source: F. Spin Models at a Low Particle Number · pp. 29–30

G. k-locality for Fermions

  • For particle-number-preserving k-local fermionic Hamiltonians, Proposition III.5.2 gives gate complexity on the m-particle subspace, and Corollary III.5.2 gives concentration for randomly drawn states from it.Fermionic terms can produce an identity at an overlapping site, adding a term to the effective 2-2 norm calculation.Source: G. k-locality for Fermions · pp. 30–31

IV. OPTIMALITY FOR FIRST-ORDER AND SECOND-ORDER FORMULAS

  • For first-order formulas, the constructed example saturates the p-norm upper bound and matches the spectral-norm triangle-inequality bound; for second-order formulas, the p-norm and spectral norm likewise match their bounds in.The first-order saturation uses |S1| = |S2| = |S3| = θ(n); the second-order p-norm limit is a function of three independent Gaussians.Source: §IV · p. 32, A. Second-order Suzuki Formulas · p. 32

B. Fermionic Hamiltonians

  • A constructed fermionic Hamiltonian demonstrates the need for the extra term ∥Hferm∥(0),2 in the estimates.The passages show its commutator and state that the second-order Suzuki case is also considered.Source: B. Fermionic Hamiltonians · p. 32

A. Useful Norms and Recursive Bounds for Matrices

  • For matrix-valued martingales, uniform smoothness gives sum-of-square estimates sharper than the triangle inequality and applies when matrices are bounded or have Gaussian coefficients via the central limit theorem.The simulation error has both classical expectation and quantum trace sources of randomness.Source: A. Useful Norms and Recursive Bounds… · p. 33

1. The operator norm

  • The operator norm measures error for the worst input state, while a separate fixed-input metric changes the order of quantifiers; uniform smoothness supports concentration for both.For operator-norm concentration, the text controls moments using the expected Schatten p-norm; the fixed-input smoothness result has Cp = p −1.Source: §1 · p. 33, §2 · p. 34

2. Fixed input state

  • For a fixed input state, the proof uses a telescoping sum and the equality of operator and 1-norms for rank-1 matrices.Source: §2 · p. 34

B. Reminders of Useful Facts

  • Expected moments of the underlying norms satisfy a triangle inequality and therefore define valid norms.The reminders also state operator-ideal and unitary-invariance properties for these norms.Source: B. Reminders of Useful Facts · pp. 34–35

VI. FIRST-ORDER TROTTER FOR RANDOM HAMILTONIANS

  • For first-order Trotterization, gate-count estimates use 2-norm Hamiltonian quantities, and the fixed-input bound avoids the log-dimension factor appearing in the spectral-norm bound.The theorem’s estimates distinguish spectral-norm and arbitrary-fixed-input error control.Source: §VI · pp. 35–36
  • The first-order result extends to Hamiltonians with independent standard Gaussian coefficients, and the section gives a separate first-order Trotter corollary for SYK models.The Gaussian-coefficient case is obtained by representing Gaussian variables through sums of bounded zero-mean summands and applying the theorem.Source: §VI · pp. 35–37

A. Scalars

  • Scalar hypercontractivity relates polynomial p-norms to their 2-norms, so typical fluctuations are captured by variance for Rademacher and Gaussian polynomials.Source: A. Scalars · p. 38

B. Matrices

  • For multivariate matrix polynomials, recursive uniform smoothness yields concentration results, including bounds for multilinear polynomials of independent, zero-mean bounded matrices.The bounds exhibit sum-of-squares behavior across index sets and use a triangle inequality within each set.Source: B. Matrices · p. 39

1. Deterministic matrix with Gaussian coefficients

  • For a deterministic bounded matrix multiplied by an independent standard Gaussian coefficient, the analysis derives a moment bound and extends it to multilinear polynomials with Gaussian coefficients.The authors note that comparable results for merely subgaussian coefficients require sacrificing factors of p.Source: §1 · p. 40
  • Fixing the index pairs makes each j a function of i, so the deterministic-matrix argument needs only reorderings, with coefficients T independent of j.Source: §1 · p. 41

2. Beyond multi-linear function

  • For bounded matrices, the extension handles repeated terms; larger index sets S carry heavier tails and can dominate as the number of summands grows at fixed degree.The bound is qualitatively the same as in the multilinear case, with heavier notation for terms appearing more than twice.Source: §2 · p. 41
  • For Gaussian coefficients, the polynomial bound allows repeated indices and uses a variance proxy whose terms reflect Wick contractions.The theorem considers bounded matrix arguments multiplied by independent standard Gaussian coefficients.Source: §2 · pp. 42–43

VIII. RANDOM k-LOCAL HAMILTONIANS

  • For random k-local Hamiltonians, fixed input states have 2-norm scaling, while worst states correlated with the Hamiltonian retain concentration at a √n price.The failure-probability dependence has a lower power of log(1/δ), although the factor raised to 1/ℓ is slightly worse.Source: §VIII · pp. 43–44

A. Bounds on the g-th Order

  • For orders g ≥ ℓ+1 ≥ 3, the proof bounds each g-th order polynomial using the 2-norm local Hamiltonian quantity; first-order Trotter has a sharper bound.The comparison uses the 2-norm rather than the 1-norm local Hamiltonian quantity.Source: A. Bounds on the g-th Order · p. 45

B. Bounds for g′-th Order and Beyond

E. Proof of Theorem III.1

  • For m=2, the calculation makes minor tweaks; after pairing v, one choice of γ′ is lost, and the proof bounds the case where γg−1 may be in v before summing over m.The lost choice could occur at any γ′.Source: B. Bounds for g′-th Order and Beyond · p. 46

C. Proof of Theorem VIII.1

The proof derives concentration and required simulation rounds from bounds at each polynomial order. It also identifies an order-dependent cost caveat.

C. Proof of Theorem VIII.1

  • The proof follows the earlier Section III E argument, with minor changes and omitted numerical factors.It adapts the estimates to the present theorem’s orders and short-time integral.Source: C. Proof of Theorem VIII.1 · p. 46
  • Combining the order-by-order bounds yields the required rounds, as stated in the theorem’s advertised result.The proof proceeds from bounds for each g-th order and g′-th order, then evaluates the short-time integral and applies Markov’s inequality.Source: C. Proof of Theorem VIII.1 · pp. 46–47
  • For odd ℓ, a larger cost may arise at order g + 1.Here g = ℓ + 1 is even.Source: C. Proof of Theorem VIII.1 · p. 47
  • The spectral-norm route incurs a Hilbert-space-dimension factor from the Schatten p-norm trace, requiring higher cost.The passage does not provide the completed cost expression.Source: C. Proof of Theorem VIII.1 · p. 47

A. Comparing the random estimates with non-random estimates

The section compares random and non-random error estimates, gives an early-time counting argument for lower bounds, and discusses truncating Hamiltonians to reduce simulation cost. The comparisons also expose open questions about optimality and correlated coefficients.

A. Comparing the random estimates with non-random estimates

  • Random Hamiltonians have better p-dependence but worse system-size dependence than non-random estimates, reflecting external Gaussian versus intrinsic k-local randomness.The bounds use different norms, which capture different error notions.Source: A. Comparing the random estimates with… · p. 47
  • For typical basis inputs, the 2-norm differs from a fixed-input norm; optimizing over the fixed input makes the latter √n larger in the example.The 2-norm captures typical basis-input sizes, whereas the fixed norm may optimize over arbitrary fixed inputs.Source: A. Comparing the random estimates with… · pp. 47–48
  • Optimality of the operator-norm bounds, including extra √n factors, is less understood, and correlated coefficients leave an open problem.The coefficient expression resembles spin-glass Hamiltonians, including the Sherrington-Kirkpatrick model.Source: A. Comparing the random estimates with… · p. 48

B. Counting lower bounds at early times

  • The authors conjecture that typical random k-local Hamiltonian simulation requires ˜Ω(n^k t) gates.The stated conjecture uses SYK normalization.Source: B. Counting lower bounds at early times · p. 48
  • A counting argument uses collision probabilities among random Hamiltonian samples to build epsilon nets; early-time circuit bounds match Trotter bounds, though a rigorous Hamiltonian-to-unitary step is missing.The matching is stated for early times t = θ(1).Source: B. Counting lower bounds at early times · p. 49

Appendix A: Truncating the Hamiltonian

  • For power-law interactions with α < d, truncating terms beyond cutoff ℓ gives typical-input gate complexity slightly better than operator-norm estimates.The motivation is that directly simulating many weak terms can impose a considerable cost; hypercontractivity applies to the truncated part.Source: Appendix A · pp. 49–50

Related papers

Loading 2111.05324v2…