Source-linked AI summary
Faster quantum simulation by randomization
Andrew M. Childs, Aaron Ostrander, Yuan Su
TL;DR
Product-formula simulation is simple and effective, but existing analyses can substantially overestimate its error and rely on structural information such as commutation. This paper randomizes the ordering of Hamiltonian summands, proves stronger bounds for higher-order formulas, and finds asymptotic and sometimes empirical improvements, including against a commutator-based bound. The improvements use less Hamiltonian structure and require little additional complexity.
Problem
Existing product-formula bounds can fall far short of empirical performance, while structure-based improvements apply only to Hamiltonians with many commuting summands and may remain weak.
Method
The paper analyzes higher-order product formulas obtained by randomly permuting the Hamiltonian summands, using a mixing lemma and combinatorial cancellation of nondegenerate terms.
Results
Randomization yields stronger asymptotic bounds, always improves dependence on L, can outperform a commutator bound over a significant parameter range, and sometimes improves empirical performance.
Takeaways & Limitations
A randomized product-formula algorithm can be nearly as simple as the deterministic version while using less Hamiltonian structure and no ancilla qubits.
Takeaways & Limitations
The strengthened bounds remain far from apparent empirical performance and improve over the commutator bound asymptotically only for sufficiently large systems.
Abstract
from arXiv · showhide
Product formulas can be used to simulate Hamiltonian dynamics on a quantum computer by approximating the exponential of a sum of operators by a product of exponentials of the individual summands. This approach is both straightforward and surprisingly efficient. We show that by simply randomizing how the summands are ordered, one can prove stronger bounds on the quality of approximation for product formulas of any given order, and thereby give more efficient simulations. Indeed, we show that these bounds can be asymptotically better than previous bounds that exploit commutation between the summands, despite using much less information about the structure of the Hamiltonian. Numerical evidence suggests that the randomized approach has better empirical performance as well.
1 Introduction
Product formulas offer a simple, practical route to quantum simulation, but their proven error bounds lag behind empirical performance. The paper shows that randomizing summand order strengthens higher-order analyses and can improve simulation complexity, sometimes even beyond structure-aware commutator bounds.
- 1 Introduction: Product formulas approximate Hamiltonian evolution by replacing an exponential of a sum with products of exponentials of individual summands.They are widely used because of their simplicity and because they require no ancilla qubits.
- 1 Introduction: The central challenge is choosing the number of segments r so that simulation error remains below the allowed threshold ϵ.Existing deterministic bounds depend on the number and norm of the summands, but numerical studies indicate substantially better practical performance.
- 1 Introduction: Randomly permuting summands extends randomization to higher-order product formulas and yields substantially improved asymptotic performance with little added algorithmic complexity.The analysis combines a mixing lemma with bounds for the average evolution and individual product-formula terms.
- 1 Introduction: Nondegenerate Taylor-expansion terms cancel completely in the randomized product formula, supplying the combinatorial basis for its stronger error bounds.The paper computes the relevant average-evolution terms in closed form before establishing this cancellation.
- 1 Introduction: The randomized approach always improves dependence on L and sometimes also improves dependence on t and ϵ relative to the deterministic case.The comparison is stated for fixed k and constant Λ in the higher-order setting.
- 1 Introduction: For a one-dimensional Heisenberg model in a random magnetic field, the randomized bound outperforms a commutator-based deterministic bound over a significant parameter range despite using less Hamiltonian structure.Numerical comparisons also show that randomization can sometimes improve empirical performance.
2 The power of randomization
Randomly ordering Hamiltonian summands improves product-formula simulation by averaging complementary errors, effectively raising first-order accuracy and reducing gate complexity. The approach extends to higher-order formulas, lowering error dependence on the number of summands.
- First-order formulas: Averaging forward and reverse orderings supplies both H1H2 and H2H1 second-order products, making the randomized first-order formula effectively second order.The construction applies one ordering uniformly at random per segment and implements a quantum channel.
- First-order formulas: Randomization is analyzed with a mixing lemma whose channel error is linear in average-operation error but quadratic in individual-operation error.The analysis uses diamond-norm distance, which accounts for entanglement with a reference system.
- First-order formulas: For first-order formulas, the randomized algorithm improves gate complexity over the deterministic algorithm with respect to all parameters of interest.The stated randomized complexity scales as t^1.5L^2.5/ϵ^0.5, while the deterministic comparison is given in the cited bound.
- Higher-order formulas: Higher-order randomization lowers simulation error and its dependence on the number of summands, although it does not improve the formula’s order.Higher-order formulas use random permutations of the summands and Θ(L log L) random bits per segment.
3 Randomization lemma
The randomization lemma evaluates dominant nondegenerate Taylor terms in the average evolution created by permuting summands. These terms scale with the number of distinct summand choices and can cancel under product-formula coefficients.
- Average evolution: The average evolution is formed by permuting the L Hamiltonian summands across the product-formula factors.Appropriate coefficients and forward or backward orderings represent any (2k)th-order product formula in the required form.
- Nondegenerate terms: Nondegenerate sth-order terms contain pairwise distinct summands and contribute Θ(L^s) to the error, while degenerate terms contribute only O(L^(s−1)).This distinction identifies the dominant contribution that the lemma must evaluate.
- Nondegenerate terms: The lemma computes the sth-order nondegenerate term of the average evolution as a coefficient-weighted sum over products H_m1 ··· H_ms with pairwise different indices.The combinatorial proof counts distinct column choices and corrects for repeated row selections.
- Cancellation: For a first-order-accurate product formula, the coefficient sum equals one, enabling cancellation of the sth-order nondegenerate term in the averaged expansion.The cancellation follows from the computed form of the nondegenerate term and the condition q1 + ··· + qκ = 1.
4 Error bounds
The error analysis combines bounds on averaged evolution with the mixing lemma and standard product-formula estimates. For higher-order formulas, randomization cancels dominant nondegenerate terms while bounding the remaining degenerate and tail contributions.
- Termwise analysis: The norm of an sth-order ideal-evolution term is bounded by (LΛ|λ|)^s/s!, while its nondegenerate contribution is L(L−1)···(L−s+1)(Λ|λ|)^s/s!.Subtracting these quantities bounds the degenerate contribution.
- Termwise analysis: Terms of order s ≤ 2k have zero error because the (2k)th-order formula is exact through order 2k.For 2k < s ≤ L, the nondegenerate contribution cancels and only degenerate terms need bounding.
- Tail regime: For s > L, the randomization lemma does not apply, so the error is bounded using a separate higher-order tail estimate.The proof uses a standard exponential tail bound for this regime.
- Main error bound: The main higher-order error bound combines an average-evolution error bound, standard individual-term product-formula bounds, and the mixing lemma.The resulting bound is stated in diamond norm for quantum channels associated with the ideal and permuted formulas.
5 Algorithm performance and comparisons
Randomized product formulas can improve asymptotic complexity in the number of Hamiltonian summands and sometimes outperform commutator-based deterministic bounds. The advantage depends on the relationship between evolution time and summand count.
- Deterministic comparisons: The randomized (2k)th-order approach strictly improves complexity as a function of L, either improving all parameters or improving L-dependence over deterministic formulas.Which case applies depends on which term dominates the deterministic complexity bound.
- Asymptotic comparisons: The randomized approach changes the commutator-bound exponent from 1/(2k+1) to 1/(4k+1), enabling slightly faster algorithms with less Hamiltonian-structure information.The comparison concerns corresponding (2k)th-order randomized and deterministic formulas.
- Asymptotic comparisons: If t = o(L^(2k)), the randomized formula is advantageous; when t = Ω(L^(2k)), the asymptotic comparison can instead favor the commutator-based bound.The relationship between t and L determines which approach improves the complexity.
6 Empirical performance
The empirical study estimates randomized product-formula performance and compares its simulation cost with deterministic formulas, rigorous bounds, and empirical error estimates. Randomization helps most at first and fourth order, while sixth-order performance is nearly unchanged.
- Empirical methodology: Monte Carlo estimates use randomly permuted summands in each segment; three samples suffice because standard deviations are about 10^-5.The resulting estimate is used to bound diamond-norm error.
- Empirical methodology: Binary search finds the smallest segment count r achieving error at most 10^-3 across five random instances for each n.The resulting data for first-, fourth-, and sixth-order formulas are well approximated by power laws.
- Results: Randomization gives significantly better empirical performance at first order, with fourth order improving both the exponent and constant factor slightly.The fourth-order gain is notable because it requires only a minor algorithmic change.
- Results: At sixth order, randomized and deterministic empirical performance is almost the same, so randomized data points are obscured in Figure 2.This agrees with the reported negligible sixth-order improvement.
- Results: For Heisenberg-model sizes up to n = 100, randomization improves the deterministic minimized bound, but the commutator bound is better at shown sizes.The randomized bound becomes lower-complexity only for sufficiently large n, while empirical estimates improve costs by several orders of magnitude.
- Results: For systems larger than about n = 25, the sixth-order bound prevails and randomization offers no significant advantage.This comparison uses fourth- and sixth-order formulas with both rigorous and empirical error bounds.
7 Discussion
The discussion attributes the improvement to randomizing summand order, which changes the average evolution beyond deterministic formulas of the same order. It also identifies scope limits: the bounds remain weaker than empirical performance and help over commutator bounds mainly for sufficiently large systems.
- 7 Discussion: Randomly ordering Hamiltonian summands introduces average-evolution terms unavailable to deterministic product formulas of the same order, yielding a more efficient algorithm.The randomized algorithm requires O(L log L) random bits per segment and no ancilla qubits.
- 7 Discussion: Randomization can outperform the commutator bound despite using less structural information about the Hamiltonian.The paper also reports improved empirical performance in some cases.
- 7 Discussion: The strengthened randomized bounds remain far from the apparent empirical performance, and their asymptotic advantage over commutator bounds appears only for sufficiently large systems.The discussion suggests exploiting Hamiltonian structure as a possible route to better small-system and asymptotic performance.