Source-linked AI summary
Simulating Hamiltonian dynamics with a truncated Taylor series
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma
TL;DR
Hamiltonian simulation requires an efficient approximation of time evolution with favorable precision dependence. The paper directly implements a truncated Taylor series through linear combinations of unitaries and robust oblivious amplitude amplification, achieving the same complexity as the prior approach while simplifying its algorithm and analysis. The construction applies broadly to Hamiltonians with suitable unitary decompositions and also extends to time-dependent and sparse settings.
Problem
The paper addresses how to simulate Hamiltonian time evolution efficiently while retaining logarithmic dependence on the inverse desired precision.
Method
The method directly approximates each evolution segment with a truncated Taylor series implemented as a linear combination of unitary operations, using robust oblivious amplitude amplification.
Results
The algorithm achieves the same complexity as the prior Hamiltonian-simulation method while simplifying the algorithm and its analysis.
Takeaways & Limitations
The generic construction applies to Hamiltonians decomposable into implementable unitary terms, including sparse and time-dependent Hamiltonians.
Abstract
from arXiv · showhide
We describe a simple, efficient method for simulating Hamiltonian dynamics on a quantum computer by approximating the truncated Taylor series of the evolution operator. Our method can simulate the time evolution of a wide variety of physical systems. As in another recent algorithm, the cost of our method depends only logarithmically on the inverse of the desired precision, which is optimal. However, we simplify the algorithm and its analysis by using a method for implementing linear combinations of unitary operations to directly apply the truncated Taylor series.
Summary of method.
The method simulates Hamiltonian evolution by truncating its Taylor series into short segments and implementing each segment as a linear combination of unitaries. Oblivious amplitude amplification then realizes the segment operation using ancillary superpositions and controlled operations.
- Summary of method.: The evolution is divided into r short segments, each approximated by a Taylor series truncated at order K.Each segment requires accuracy ǫ/r, with K chosen accordingly.
- Summary of method.: The overall complexity is essentially the number of segments r multiplied by the Taylor truncation order K.This yields logarithmic dependence on the inverse precision through the required truncation order.
- Summary of method.: The truncated Taylor series is expanded into products of Hamiltonian terms, each represented as a positive coefficient βj multiplying a unitary Vj.The unitary factors correspond to products of the Hamiltonian components, including the phase factor (−i)^k.
- Summary of method.: Ancillary superpositions and controlled operations implement the linear combination of unitary terms for each Taylor-series segment.The construction prepares an ancillary state, applies controlled operations, and uses reflections around the ancilla subspace.
Effect of nonunitarity.
Taylor truncation produces an approximation that is close to, but not exactly, unitary. The paper develops robust oblivious amplitude amplification and bounds the resulting segment and total errors.
- Effect of nonunitarity.: The truncated Taylor approximation eU is generally nonunitary, so standard oblivious amplitude amplification cannot be applied directly.The paper instead proves a robust version that tolerates closeness to a unitary matrix.
- Effect of nonunitarity.: When the normalization and approximation conditions hold to order δ, eU eU† is within O(δ) of the identity.This supports an approximate analogue of the unitary amplification relation.
- Effect of nonunitarity.: After tracing out the ancilla, each segment contributes error O(δ), giving total error O(rδ) across r segments.Choosing δ = O(ǫ/r) makes the accumulated error meet the target precision.
Hamiltonian simulation algorithm.
The simulation represents each Taylor-series segment as a truncated linear combination of unitary products and chooses the segment count so the coefficient sum is near the amplification target. Truncation and segmentwise error bounds yield final error at most ǫ.
- Hamiltonian simulation algorithm.: The Taylor terms are indexed by order and Hamiltonian-component sequence, with coefficients β(k,ℓ1,...,ℓk) and unitary products V(k,ℓ1,...,ℓk).The truncated index set retains only sequences with k ≤ K.
- Hamiltonian simulation algorithm.: Choosing r so that T/r = ln(2) makes the sum of segment coefficients equal to 2.If T is not a multiple of ln(2), the final segment has s < 2 and can be compensated with an ancilla qubit.
- Hamiltonian simulation algorithm.: The algorithm initializes and discards the ancilla for each segment, while selecting K so the segment error is O(ǫ/r).Subadditivity then gives final error at most ǫ after all segments.
Circuit constructions and gate counts.
The circuit implementation uses ancillary registers for Taylor order and Hamiltonian-term indices, controlled selection of unitary products, and repeated segment operations. The construction also supports sparse Hamiltonians through oracle access.
- Circuit constructions and gate counts.: The basic unitary A uses two select(V) operations, one select(V)† operation, and three each of B and B†.Implementing select(V) costs K times the cost of implementing an individual Hamiltonian component.
- Circuit constructions and gate counts.: The ancillary state stores the Taylor order and K Hamiltonian-component indices, requiring O(log(T/ǫ)/log log(T/ǫ)) qubits for the order register.Each component-index register uses log(L) qubits.
- Circuit constructions and gate counts.: B prepares normalized order and component-index superpositions using controlled rotations and register states proportional to the coefficients αℓ.The stated preparation costs are O(K) for the order register and O(L) for the component registers.
- Circuit constructions and gate counts.: select(V) applies up to K controlled Hamiltonian operations, each conditioned on the unary-encoded Taylor order and its corresponding component index.This realizes the product (−i)^kHℓ1 ··· Hℓk on the system register.
- Circuit constructions and gate counts.: For Pauli-product decompositions, controlled-select(H) uses O(L(n+log L)) gates, and the full simulation multiplies the segment cost by r = O(T).For sparse oracle Hamiltonians, the method obtains the same overall gate scaling per segment as the earlier approach.
- Circuit constructions and gate counts.: Sparse Hamiltonians can be approximated by equal-weight unitary terms, with L = O(T/ǫ), while oracle access avoids explicitly applying all L controlled operations.The resulting gate complexity follows the sparse-oracle construction described in the paper.
Time-dependent Hamiltonians.
The time-dependent extension breaks evolution into short segments, discretizes each segment’s time-ordered expansion, and implements the resulting sum of unitaries. With sufficiently fine discretization and amplitude amplification, the final state reaches error ǫ with only logarithmic dependence on discretization accuracy.
- Time-dependent Hamiltonians.: Time-dependent evolution is divided into r segments, and each segment is approximated using a time-ordered expansion.The first segment is represented as U_r := U(t/r), with later segments treated analogously.
- Time-dependent Hamiltonians.: The continuous time-ordered integral is discretized into M steps, using discrete times t_j = (j/M)t/r.This converts the segment approximation into a finite sum involving Hamiltonians evaluated at discrete times.
- Time-dependent Hamiltonians.: Expanding each H(t_jℓ) into L unitaries makes the discretized approximation a sum of unitaries that can be implemented as in the time-independent case.Additional ancillas encode the Taylor order, unitary-term indices, and discrete times.
- Time-dependent Hamiltonians.: The discretization parameter M is polynomial in 1/ǫ and h′, but its contribution to complexity is only logarithmic in M.Here h′ := max_t ∥dH(t)/dt∥.
- Time-dependent Hamiltonians.: Oblivious amplitude amplification produces an O(ǫ/r)-accurate state per segment, and repeating the segments prepares U(t)|ψ⟩ within error ǫ.The condition is that the truncated approximation eU is sufficiently close to unitary.
Conclusions.
The paper presents a simple Hamiltonian-simulation algorithm that directly approximates the evolution operator’s Taylor series while matching the prior method’s complexity. Its generic construction requires no ordering or special structural relationships among Hamiltonian terms.
- Conclusions.: The algorithm achieves the same complexity as the prior Hamiltonian-simulation method by directly approximating the evolution operator’s Taylor series.The paper emphasizes that the approach is simple and that its logarithmic precision dependence follows from Taylor truncation.
- Conclusions.: The method is generic: it neither orders Hamiltonian terms specially nor requires structural relationships among them.The authors also identify robust oblivious amplitude amplification and linear combinations of unitaries as broadly useful tools for quantum algorithms.