PaperlayerView exact revision on arXiv

Source-linked AI summary

Hamiltonian Simulation Using Linear Combinations of Unitary Operations

Andrew M. Childs, Nathan Wiebe

arXiv:1202.5822v1quant-ph

TL;DR

Quantum Hamiltonian simulation seeks efficient approximations to quantum dynamics, but product formulas require costly high-order unitary products. The paper implements linear combinations of nearby unitaries and applies them to multi-product formulas, obtaining better scaling with simulation error than previous algorithms while leaving favorable poly(n, log 1/ϵ) scaling unresolved.

  • Problem

    Product-formula Hamiltonian simulation has costly high-order approximations, motivating methods with improved dependence on simulation error.

  • Method

    The paper nearly deterministically implements weighted sums of nearby unitaries and uses this procedure to implement linear combinations of product formulas.

  • Results

    The resulting Hamiltonian simulation has better scaling with error ϵ than any previously known algorithm and improves scaling with all parameters over product-formula methods.

  • Takeaways & Limitations

    Coherently averaging different approximations provides a quantum-simulation approach beyond the Lie–Trotter–Suzuki paradigm.

  • Takeaways & Limitations

    The algorithms do not provide favorable scaling in 1/ϵ because of the sign problem.

Abstract

from arXiv · show

We present a new approach to simulating Hamiltonian dynamics based on implementing linear combinations of unitary operations rather than products of unitary operations. The resulting algorithm has superior performance to existing simulation algorithms based on product formulas and, most notably, scales better with the simulation error than any known Hamiltonian simulation technique. Our main tool is a general method to nearly deterministically implement linear combinations of nearby unitary operations, which we show is optimal among a large class of methods.

I. INTRODUCTION

The paper introduces quantum Hamiltonian simulation through linear combinations of unitary operations, addressing limitations of product-formula methods. The approach improves simulation complexity and offers better scaling with error than prior techniques.

  • Quantum simulation is a major potential application of quantum computers and supports quantum-algorithm development before fault tolerance.
  • Product-formula methods require high-order approximations whose unitary-product length scales exponentially with formula order.
  • The paper presents a non-deterministic algorithm for linear combinations of nearby unitary operators, achieving high success probabilities when the operators are close.
  • The resulting Hamiltonian simulation uses products of linear combinations of unitary operations and exponentials of the component Hamiltonians, with failure probability and error at most ϵ.
  • The simulation improves the product-formula coefficient from 2.54 or 2.06 to 1.6 in the stated scaling comparison.
  • The approach establishes a simulation paradigm beyond Lie–Trotter–Suzuki formulas, while efficient dependence on error ϵ remains open.

II. ADDING AND SUBTRACTING UNITARY OPERATIONS USING QUANTUM COMPUTERS

This section develops protocols for implementing weighted sums, differences, and general linear combinations of unitary operators. The constructions succeed with high probability when coefficient imbalance is large and the combined operators are nearby.

  • General linear combinations are constructed iteratively by adding terms and performing one subtraction, with failure probabilities bounded for the resulting protocol.
  • Lemma 2 implements an operator proportional to κU_a + U_b with failure probability at most ∆^2κ/(κ + 1)^2 ≤ 4κ/(κ + 1)^2.
  • The weighted-sum circuit applies controlled unitaries, uncomputes an ancilla transformation, and accepts when the measured control qubit is zero.
  • Replacing U_b with −U_b implements subtraction, and phases can produce complex weights.
  • High-probability implementation occurs when κ ≫ 1 and ∆ ≪ 1.
  • The protocol cannot improve its success probability by replacing the single-qubit unitary V_κ with a more general ancilla unitary.

III. IMPLEMENTING MULTI-PRODUCT FORMULAS ON QUANTUM COMPUTERS

The paper applies its linear-combination method to Hamiltonian simulation by implementing sequences of multi-product formulas rather than only products of unitary approximations.

  • Hamiltonian time evolution is approximated by a sequence of non-unitary operators, each formed as a linear combination of product formulas.

A. Review of Lie–Trotter–Suzuki and Multi-Product Formulas

Lie–Trotter–Suzuki formulas provide accurate, directly implementable unitary products but require many exponentials. Multi-product formulas reduce this count through sums, at the cost of implementation and numerical-stability challenges.

  • Lie–Trotter–Suzuki formulas recursively approximate e^−iHt with unitary operations whose Taylor series matches the target through O(t^(2χ+1)).
  • Constructing an O(t^(2k+1)) product-formula approximation requires O(5^k) exponentials, producing complexity (∥H∥t)^(1+o(1)).
  • Multi-product formulas use sums of product formulas and require only O(k^2) exponentials for an O(t^(2k+1)) approximation.
  • For classical simulations, the most numerically efficient formulas use ℓ_q = q and χ = 1.
  • Multi-product formulas can lie within O(t^10) of a unitary operator and are practically indistinguishable from unitary operations in many applications.
  • Their principal numerical drawback is instability from substantial roundoff errors caused by nearly cancelling sums.
  • Negative coefficients create a sign problem that lowers implementation success probability, and high-order formulas cannot avoid negative coefficients under the stated form.

B. Implementing Multi-Product Formulas Using Quantum Computers

The section develops multi-product formulas that achieve higher-order Hamiltonian-evolution approximations, then adapts them for quantum computers by controlling coefficient-dependent success probabilities. It also identifies parameter choices that avoid exponentially small success while exposing a tradeoff between accuracy and implementation complexity.

  • The quantum implementation uses a linear-combination protocol, but standard classical multi-product formulas can have exponentially small success probability because κ approaches 1 exponentially quickly with k.
  • The paper defines M_k,χ by combining symmetric product-formula approximations at different scales, with coefficients chosen to cancel low-order error terms.The resulting construction extrapolates an O(λ^2χ+1) symmetric product formula into an O(λ^2(k+χ)+1) multi-product formula.
  • Choosing the scale parameters so that C_k+1 dominates the other coefficients increases κ and therefore supports a high success probability for the subtraction step.The construction selects ℓ_q so that C_k+1 is much larger in absolute value than the remaining coefficients.
  • The lower bound on γ is tight up to O(k^-1 log k): small deviations around γ_c produce either exponential growth of κ or exponential convergence of κ to 1.

IV. ANALYSIS OF SIMULATION AND ERRORS IN MULTI-PRODUCT FORMULAS

The analysis bounds approximation errors, implementation failure probabilities, and exponential-operation costs for multi-product Hamiltonian simulation. It identifies a parameter trade-off: increasing formula order improves accuracy but increases implementation complexity, while carefully choosing γ controls κ and success probability.

  • Approximation-error bounds: The error analysis bounds multi-product-formula remainders using Taylor-series estimates for operator exponentials and higher-order integrators.The analysis compares the approximation errors of Mk,k and U after canceling matching Taylor terms.
  • Failure-probability control: The implementation repeats Mk,k(t/r) for r iterations, combining error bounds with a Chernoff bound to control cumulative simulation error and failure probability.With suitable conditions, the simulation achieves error at most ϵ with probability at least 1 − e^-r/13 and uses no more than 5r subtraction attempts and approximate inversions.
  • Overall simulation cost: Theorem 1 gives a simulation of U(t) = e^-iHt with error at most ϵ and failure probability at most β, using a product of implemented multi-product formulas.The construction counts the unitary operations through subtraction, inversion, Suzuki-integrator, and exponential layers.
  • Complexity trade-off: The operation count reflects a trade-off between exponential accuracy improvement with k and exponential growth of Mk,k, with a more favorable trade-off than earlier approaches.The asymptotic result is obtained by optimizing k and dropping poly-logarithmic factors.
  • Operational limitations: Reducing ϵ and β improves fidelity and success probability, but the resulting cost is not poly-logarithmic in 1/ϵ and 1/β.When state preparation and output checking are cheap, repetition can achieve high success with a logarithmic number of iterations; this may fail for subroutine use.

V. CONCLUSIONS

The paper introduces Hamiltonian simulation through linear combinations rather than products of unitary operations. It reports better error scaling than prior algorithms while leaving improved error dependence and broader time-dependent generalization as open challenges.

  • The approach implements Hamiltonian dynamics using linear combinations of unitary operators rather than products.
  • The resulting simulation has better scaling with simulation error ϵ than previously known algorithms and more favorable scaling with all parameters than product-formula methods.
  • Coherently averaging different approximations reduces approximation errors and may have applications beyond quantum simulation.
  • It remains open whether n-qubit Hamiltonians can be simulated with complexity polynomial in n and log 1/ϵ.
  • The algorithms do not achieve the favorable polynomial-in-log(1/ϵ) scaling of classical multi-product formulas because of the sign problem.
  • The results focus on time-independent Hamiltonians; extending them to time-dependent evolution is nontrivial when the Hamiltonian is not sufficiently smooth in time.

Appendix A: Optimality of the linear combination procedure

The appendix proves a lower bound on failure probability for a broad circuit family implementing linear combinations of unitaries, and shows the Theorem 3 protocol is optimal when the unitaries are nearby. It also identifies limitations of this optimality result and of the corresponding correction strategy.

  • Optimality: Theorem 3 is optimal among Figure 3 protocols in the small-∆ limit, when the combined unitary operations are all similar.The appendix considers the circuit family with ancilla preparation and measurement implemented by arbitrary unitary operations A and B.
  • Lower bound: Theorem 13 shows that any Figure 3 protocol implementing the target linear combination must fail with probability at least 4κ/(κ + 1)2.The circuit prepares ancillas using A, applies controlled unitaries, and measures in a basis specified by B.
  • Lower bound: The success-probability optimization reduces to maximizing a normalization factor over unitary A and B, with the bound tight by Cauchy–Schwarz saturation.The saturation choice is am,0 = b0,m = √Cm.
  • Lower bound: Orthogonality of B prevents different measurement outcomes from producing the same multi-product formula, so one successful outcome suffices for the lower-bound analysis.If two outcomes succeeded, their coefficient vectors would need to be proportional, contradicting orthonormality of B's columns.
  • Scope and limitations: The proof's implicitly optimal protocol is not used in Theorem 3 because failures may require correction operations that are difficult to implement.Theorem 3 instead uses Lemma 2, whose failed difference operation has a correction expressible as a sum of nearby unitaries; other protocol forms might improve success probability, but this remains open.
Loading 1202.5822v1…