Hamiltonian simulation with random inputs

I. INTRODUCTION

• Although digital simulation algorithms have optimal or nearly optimal gate complexity for several key parameters, implementing them on current hardware remains challenging because many qubits must be controlled accurately.Prior work has tightened error bounds for particular input states, subspaces, observables, and time-dependent Hamiltonians.Source: §I · p. 1
• The analysis treats average error for random initial states and relates it to the Frobenius norm of the multiplicative error, which captures its root-mean-square eigenvalue behavior.The paper notes that many easily prepared ensembles, including locally random single-qubit states and uniform orthonormal-basis ensembles, have the 1-design property required by its analysis.Source: §I · p. 1
• For the nearest-neighbor Heisenberg chain with n spins, average error is O(√n) for both product-formula and Taylor-series methods, versus O(n) worst-case error.The average-case scaling is quadratically smaller than the worst-case scaling.Source: §I · pp. 1–2
• The paper also studies general k-local and power-law Hamiltonians, with numerical results suggesting the analytical bounds are not far from tight in typical examples.The techniques are also applied to tighten Trotter-error analysis and reduce gate complexity for out-of-time-order correlators in scrambling physics.Source: §I · p. 2

II. WORST- AND AVERAGE-CASE ERROR

• The paper defines typical error by averaging the distance between ideal and approximate evolution over an input-state ensemble, rather than using only the worst-case spectral norm.The distance measures considered are the ℓ2 norm and trace norm.Source: §II · p. 2
• For an input drawn from a 1-design in a 2^n-dimensional Hilbert space, Theorem 1 bounds average ℓ2 error using the Frobenius norm of the multiplicative error.The multiplicative error is defined by U = U0(I + M).Source: §II · p. 2
• For 2-design inputs, the variance of the squared error S(ψ) is bounded by 4∥M∥2, and Chebyshev's inequality bounds the probability of deviation from its mean.The supplied passage gives the variance bound in terms of the operator norm of M.Source: §II · p. 2
• The framework extends to inputs drawn at random from a subsystem and to average error with random inputs and random projections.For a subsystem of dimension d1, the stated bound is RΠ(U, U0) ≤ ∥MΠ∥F/√d1.Source: §II · p. 2

III. AVERAGE ERROR IN HAMILTONIAN SIMULATION ALGORITHMS

• For PFp simulation, the average error in the ℓ2 norm for a 1-design input ensemble has an asymptotic upper bound under the specified simulation parameters.For an n-qubit nearest-neighbor Hamiltonian, αcomm,p = O(n) and Tp = O(√n).Source: §III · pp. 2–3
• For PF1 and PF2, triangle bounds move some sums inside the Frobenius norm and give concrete prefactors.Numerics suggest these tighter bounds can be close to optimal for PF2, while a gap remains for PF1 with nearest-neighbor interactions.Source: §III · p. 3
• For nearest-neighbor PF1, destructive error interference between segments tightens the average-error time dependence beyond the triangle bound.The interference bound applies when ∥[A, B]∥t^2/(2r) is at most a constant smaller than 1.Source: §III · p. 3
• The paper also bounds average error for the Kth-order truncated Taylor-series method, but the gate reduction is mild because LCU gate complexity is logarithmic in 1/ε.The stated average-case analysis compares with a worst-case error scaling involving αt and the truncation order K.Source: §III · p. 3

a. Lattice Hamiltonians

• For nearest-neighbor lattice Hamiltonians, T_p = O(√n) versus α_comm,p = O(n), reducing PF1 gate complexity from O(n^2t^2) to O(n^1.5t^2) and PF2 from O(n^1.5t^1.5) to O(n^1.25t^1.5).The theoretical bounds agree well with the empirical results shown in Fig. 1.Source: §IV · p. 3

b. k-local Hamiltonians

• For k-local Hamiltonians, average error depends on Frobenius, induced permutation, and induced one-norms; the paper summarizes PF1 and PF2 errors in Table I.For terms of norm at most 1, the text gives ∥H∥_1 ≤ n^k and |||H|||_1 = O(n^(k−1)).Source: §IV · p. 3, Table I · p. 3

c. Power-law interactions

• For power-law interactions, the analysis covers α < D, α = D, and α > D, and comparison with empirical performance suggests the bounds are reasonably tight.The text also establishes |||H|||_per^2 ≤ |||H|||_1.Source: §IV · p. 4

d. Out-of-time-order correlators

• For OTOC measurement with nearest-neighbor PF2 and constant Trotter error ε, gate complexity falls from O(n^1.5t^1.5) under worst-case analysis to O(n^1.25t^1.5).The analysis treats the maximally mixed subsystem as a mixture of random states and bounds Trotter error by 1/√d1 ∥M∥F rather than ∥M∥.Source: §IV · p. 4

• The techniques also apply to estimating Tr(e^−iHt), including trace estimation in the one-clean-qubit model.Source: §IV · p. 4

• The empirical analysis uses t = n, ε = 10^−3, and 20 Haar-random inputs, and plots mean and standard deviation of empirical Trotter numbers.It also computes worst-case empirical Trotter numbers from spectral-norm error.Source: §V · pp. 4–5
• For PF1 on the random-field nearest-neighbor Heisenberg model, the interference bound matches empirical results for n ≤ 18, while its additional assumption can substantially increase r at large t and n.The assumption requires ∥[A, B]∥t^2/2r = O(nt^2/r) to remain below a constant smaller than 1.Source: §V · p. 5
• For power-law Heisenberg interactions, the bounds are reasonably tight in many cases but somewhat loose for PF1 with shorter-range interactions.The study compares α = 4 with the infinite-range case α = 0.Source: §V · p. 5
• PF4 and PF6 results align with the asymptotic results in Theorem 2, and the appendix also reports other 1-design inputs and input-state standard deviations.Source: §V · p. 5

• The paper develops a theory of average error for Hamiltonian simulation with random input states.Source: §VI · p. 5
• Average-case analysis further improves on methods already optimal in worst-case performance and reduces product-formula gate complexity for OTOC simulation.The paper also identifies imaginary-time evolution, quantum Monte Carlo, and error analysis in subspaces as possible extensions.Source: §VI · p. 5
• Direct calculation of average error without the Cauchy inequality could potentially yield tighter bounds.Source: §VI · p. 5

1. Average ℓ2 norm with random inputs

• For 1-design inputs, the expected squared ℓ2 error is expressed through the Frobenius norm of the multiplicative error, and Theorem 5 upper bounds average ℓ2 distance.For 2-designs, Lemma 1 also bounds the variance.Source: §1 · pp. 10–11

Appendix A: Average error and its variance

• A 1-design suffices for the average ℓ2 error result, while a 2-design supports the variance bound used to show the upper bound is typical and tight.The paper notes that computational-basis states with uniform sampling form a 1-design.Source: Appendix A · p. 9, §1 · p. 11

2. Average trace norm distance with random inputs

• For trace-norm error, the appendix gives bounds for 2-design inputs and a 1-design upper bound, using average fidelity to relate the quantities.For 4-design inputs with small ∥M(t)∥, the fidelity variance is O(1/d).Source: §2 · pp. 12–13

3. Average measurement error

• For random inputs and random projective measurements drawn from 2-design ensembles, Theorem 7 gives an upper bound on average measurement error.For measurements with norm at most one, the bound is no larger than the random-input-only bound, reflecting an additional average-case enhancement.Source: §3 · p. 15

4. Random inputs from subspaces and subsystems

• Inputs drawn from a subspace that form a 1-design admit an average ℓ2-error bound, with subsystem inputs as a special case.For subsystem inputs, the first k qubits may be fixed while the remaining n−k qubits are random; the bound is reasonably tight when k is small and may be improved using knowledge of the fixed state.Source: §4 · p. 16

5. Multi-segment performance via the triangle inequality

• For Haar-random inputs, average error is subadditive across evolution segments; an ℓ2 upper bound is also subadditive for 1-design inputs.This permits bounding total average error using the error in one segment.Source: §5 · pp. 16–17

Appendix B: General theory of average error in Hamiltonian simulation algorithms

• The appendix develops a general theory of average error for the pth-order product formula and truncated Taylor-series methods.For product formulas, the bounds use Frobenius norms of nested commutators; the analysis also treats PF1 and PF2 with detailed prefactors.Source: Appendix B · p. 18, §1 · pp. 19–20

1. Product formula method

• The product-formula analysis gives an asymptotic average ℓ2-error upper bound for PFp with 1-design inputs.It expresses the bound through nested-commutator Frobenius norms and considers long-time evolution by dividing it into segments.Source: §1 · pp. 19–20

2. Taylor series method

• The Taylor-series analysis gives an average-error upper bound, but the improvement does not significantly affect LCU gate complexity, which is logarithmic in 1/ε.The method truncates the Taylor expansion in each time segment.Source: §2 · pp. 21–22

Appendix C: Average error in first- and second-order product formula algorithms

• For a 1-design input ensemble, the appendix derives average ℓ2-error bounds for PF1 applied to multi-term Hamiltonians.The analysis first treats two-term Hamiltonians and then generalizes to multiple terms.Source: Appendix C · pp. 22–23
• For PF1 with r segments and t/r < 1, the average ℓ2-error bound applies to arbitrary-time evolution with 1-design inputs.The result combines the short-time PF1 bound with the multi-segment analysis.Source: Appendix C · p. 24
• The appendix also derives an average ℓ2-error upper bound for PF2 with 1-design inputs.The PF2 analysis follows a similar approach and extends the two-term result to Hamiltonians with multiple terms.Source: Appendix C · pp. 22, 24

Appendix D: Error interference with nearest-neighbor interacting Hamiltonians

• A bound that omits interference between different time steps can miss tighter error bounds for nearest-neighbor PF1.The section notes that such interference has also been used to improve worst-case bounds.Source: Appendix D · p. 25
• The analysis tightens the PF1 average-error bound by accounting for destructive interference between time steps.The section motivates this refinement with empirical average-error behavior and develops the interference analysis for a two-part Hamiltonian.Source: Appendix D · p. 25
• For nearest-neighbor Hamiltonians, the PF1 average ℓ2-error interference bound applies when nt^2/r is less than a small constant.The bound concerns 1-design input ensembles and the even-odd partition of the nearest-neighbor terms.Source: Appendix D · p. 25

Appendix E: Comparing bounds with and without the Cauchy-Schwarz inequality

• The exact Haar-averaged bound can be tighter than its Cauchy–Schwarz trace bound, which is easier to compute; for G = MM†, the inequality is an equality.The gap between the bounds depends on G’s eigenvalue distribution; when r∥G∥ is negligible relative to the target error resolution, the tighter formula adds little.Source: Appendix E · p. 30, §1 · p. 31

1. Numerics and conclusions

• For d ≈ 10^3, the single-nonzero-eigenvalue spectrum gives D ≲ 10^-2 and numerically yields the largest gap among the tested spectra, though maximality remains conjectural.The degenerate spectrum gives D = 0, while evenly spaced and randomly sampled spectra have smaller D; the random case plots the maximum over 1000 trials.Source: §1 · p. 31, Appendix E · p. 31, Figure 3 · p. 32

2. Average error in PF1 without the Cauchy-Schwarz inequality

• For the Heisenberg-model PF1 example, bounds with and without Cauchy–Schwarz are negligible in difference and agree to about 1%.With n ≈ 10, r ≳ 10^5, and target error 10^-3, the estimated difference is bounded by ≈10^-3/2; larger multiplicative-error norms could make the gap more relevant.Source: §2 · p. 33

Appendix F: Applications

• The applications estimate Tp for nearest-neighbor, general k-local, and power-law interaction Hamiltonians, and extend the techniques to more efficient OTOC-measurement protocols.OTOCs probe scrambling physics.Source: Appendix F · p. 33

1. Nearest-neighbor Hamiltonians

• For nearest-neighbor Hamiltonians with even-odd ordering, PF1 has T1 = O(√n), and the analysis derives average-error and gate-complexity bounds for general PFp.The PFp commutator-support analysis treats p as constant; gate-complexity results for PF1 and PF2 are reported in Table III.Source: §1 · pp. 34–35, Table III · p. 35

2. k-local Hamiltonians

• For k-local Hamiltonians, the appendix derives average-error bounds for PF1, PF2, and general PFp; the higher-order analysis avoids introducing |||H|||per.The analysis assumes k = O(1).Source: §2 · pp. 36–37
• For k-local Hamiltonians, the improvement for product-formula orders p > 2 comes only from the difference between ∥H∥1,F and ∥H∥1; first- and second-order cases have a separate comparison.When each term is a tensor product of Pauli operators, the passage states d^1/2∥H∥1,F = ∥H∥1; for the first- and second-order cases, the improvement is attributed to the difference between |||H|||1 and |||H|||per.Source: §2 · p. 38

3. Power-law interactions

• For power-law interactions on a D-dimensional lattice, the appendix compares average-case and worst-case product-formula performance for first- and second-order formulas.The comparison uses d^1/2∥H∥1,F ≤ ∥H∥1 and the bound ∥H∥1 ≤ n|||H|||1.Source: §3 · p. 39

4. Out-of-time-order correlators

• The OTOC algorithmic-error bound uses the Frobenius norm of the multiplicative error; for nearest-neighbor Hamiltonians, that norm scales as O(√n d1 (t/r)^3), versus O(n(t/r)^3) for the operator norm.The OTOC measures scrambling and quantum chaotic behavior; the input state is pure on the first qubit and maximally mixed on the remaining qubits.Source: §4 · pp. 40–41
• O(n^1.25 t^1.5/ε) gates suffice for OTOC Trotter error at most ε, compared with O(n^1.5 t^1.5/ε) under worst-case analysis.The corresponding Trotter-step counts are O(n^0.25 t^1.5/ε) and O(n^0.5 t^1.5/ε), respectively.Source: §4 · pp. 41–42

5. Trace estimation

• For one-clean-qubit trace estimation, the product-formula error bound applies directly when approximating Hamiltonian evolution, and the preceding Hamiltonian-specific bounds can then be used.For nearest-neighbor Hamiltonians, the passage gives ε = O(√n 2^n t^(p+1)/r^p) for the trace-estimation error.Source: §5 · p. 42

Appendix G: Numerical results

• Theoretical PF1 and PF2 bounds track empirical performance for nearest-neighbor Heisenberg models, while power-law results show a substantial PF1 gap for α = 4.For α = 0, both PF1 and PF2 bounds agree well with empirical results; for α = 4, the PF2 bound agrees well.Source: Appendix G · p. 42

2. Power-law interactions

• For power-law interactions, the theoretical bounds are reasonably tight in many cases, but are somewhat loose for PF1 with shorter-range interactions.The analysis uses X-Y-Z ordering and calculates prefactors for comparison with empirical performance.Source: Appendix G · p. 42, §2 · p. 45

a. Interference bound

• The nearest-neighbor PF1 error scales linearly in t for small t and cubically for larger t, with a transition around t ≈ √r.The observed behavior agrees with Theorem 11.Source: a. Interference bound · p. 43

interference bound.

• For large t and n, the first term in the segment-count bound dominates, giving r = O(∥[A, B]∥t^2); for n ≤ 20, the second gives r = O(n^0.5t/ε).The latter is the classically tractable regime considered in the passage.Source: interference bound · p. 44

c. Counting bound

• For the nearest-neighbor counting bound, Pauli-string counting bounds the commutator trace without numerical evaluation.The triangle bound instead evaluates the relevant traces numerically.Source: c. Counting bound · pp. 44–45, b. Triangle bound · p. 44

b. Counting bound

• The power-law triangle bound requires numerical evaluation of commutator traces, which is classically intractable for large systems; the counting bound analytically bounds T′1 instead.The counting approach is introduced to explore bound performance at large n.Source: b. Counting bound · p. 45

a. Higher-order formulas

• PF4 and PF6 are tested empirically because concrete theoretical prefactors are unavailable, with empirical and theoretical asymptotic scalings compared in Table V.The tests cover nearest-neighbor and power-law models with α = 0 and 4.Source: §3 · p. 46, Table V · p. 46, Figure 6 · p. 47

b. Other 1-design inputs

• PF1 performs similarly with local Haar-random inputs and uniformly random computational-basis inputs as with Haar-random inputs.Both alternative ensembles are 1-designs.Source: §3 · p. 47, Figure 8 · p. 48

c. Statistical fluctuations

• At mean error 10^-3, the standard deviation decreases with system dimension, and its extrapolation curves match the predicted scaling.The fluctuations are tested using 20 Haar-random inputs.Source: §3 · p. 48