PaperlayerView exact revision on arXiv

Source-linked AI summary

A random compiler for fast Hamiltonian simulation

Earl Campbell

arXiv:1811.08017v2quant-ph

TL;DR

The paper compares deterministic and randomized decompositions for Hamiltonian simulation and examines qDRIFT and second-order random Trotter in phase estimation. At Pf = 5%, reported speedups are ×1406, ×304, and ×789, while actual-performance analysis remains beyond scope.

  • Problem

    Deterministic and randomized Trotter decompositions require error bounds to determine the gate count needed for a target precision.

  • Method

    The paper analyzes qDRIFT and second-order random Trotter for Hamiltonian simulation and uses them in a simplified phase-estimation protocol.

  • Results

    At Pf = 5%, speedups are ×1406, ×304, and ×789, respectively.

  • Takeaways & Limitations

    For chemistry problems, the approximation is very close to the exact upper bound, supporting its use for intuition and phase-estimation analysis.

  • Takeaways & Limitations

    Actual performance is difficult to assess and beyond the present scope, while newer phase-estimation techniques could improve both protocols.

Abstract

from arXiv · show

The dynamics of a quantum system can be simulated using a quantum computer by breaking down the unitary into a quantum circuit of one and two qubit gates. The most established methods are the Trotter-Suzuki decompositions, for which rigorous bounds on the circuit size depend on the number of terms $L$ in the system Hamiltonian and the size of the largest term in the Hamiltonian $Λ$. Consequently, Trotter-Suzuki is only practical for sparse Hamiltonians. Trotter-Suzuki is a deterministic compiler but it was recently shown that randomised compiling offers lower overheads. Here we present and analyse a randomised compiler for Hamiltonian simulation where gate probabilities are proportional to the strength of a corresponding term in the Hamiltonian. This approach requires a circuit size independent of $L$ and $Λ$, but instead depending on $λ$ the absolute sum of Hamiltonian strengths (the $\ell_1$ norm). Therefore, it is especially suited to electronic structure Hamiltonians relevant to quantum chemistry. Considering propane, carbon dioxide and ethane, we observe speed-ups compared to standard Trotter-Suzuki of between $306\times$ and $1591\times$ for physically significant simulation times at precision $10^{-3}$. Performing phase estimation at chemical accuracy, we report that the savings are similar.

Appendix A: Error measures

The appendix defines operator, trace, and diamond-norm distances used to quantify simulation errors. Diamond distance between channels bounds trace-norm state error and measurement-probability deviations.

  • The operator norm is the largest singular value, while the trace norm is the sum of an operator’s singular values.
  • The diamond norm measures error between quantum channels and is used throughout the analysis.
  • An ϵ-close channel approximation produces a state within ϵ trace-norm distance of the ideal evolved state.
  • ϵ diamond-distance error bounds measurement probabilities to additive error 2ϵ.

Appendix B: Bounding higher order error terms

The appendix bounds qDRIFT’s random-channel approximation by comparing its expansion with the ideal unitary channel. Choosing τ = λt/N aligns the leading terms, while norm inequalities control higher-order errors.

  • The analysis uses the Liouvillian representation of a unitary channel and generators associated with the Hamiltonian terms.
  • qDRIFT selects one random gate per step, producing a random operator whose channel is compared with the ideal evolution.
  • τ = λt/N makes the first two expansion terms of the random and ideal channels match.
  • The higher-order error bound uses positivity, the triangle inequality, sub-multiplicativity, and bounds on composed Liouvillian terms.
  • The exponential tail bound and diamond-distance subadditivity yield the stated large-N approximation and main-text result.

Appendix C: Bounding higher order error terms

This appendix compares deterministic and randomized Trotter-Suzuki error bounds and derives gate-count estimates. Randomization helps when the randomized error coefficient is smaller, but its advantage diminishes for higher Suzuki orders.

  • The appendix reproduces prior Trotter and Suzuki results from Childs, Ostrander and Su.
  • Trotter decomposition: Deterministic and randomized Trotter decompositions have error bounds whose comparison depends on coefficients a_TROTT and b_TROTT.
  • Trotter decomposition: When b_TROTT ≪ a_TROTT, the randomized Trotter approach has a significant advantage; its gate count is Lr.
  • Suzuki decompositions: Deterministic and randomized 2k-order Suzuki decompositions are bounded by analogous coefficient pairs a_2k−SUZUKI and b_2k−SUZUKI.
  • Suzuki decompositions: As k →∞, the randomized Suzuki advantage disappears because both error coefficients approach a similar order of magnitude.
  • Chemistry approximations: For chemistry problems with ϵ < 10−2, the approximation is very close to the exact upper bound, while numerics use exact expressions.
  • Gate counts: Higher Suzuki order improves scaling with Λ, t, and ϵ, but large constant prefactors make k = 3 uncommon and k = 1 often optimal.

Appendix D: Controlled evolution

The appendix introduces controlled evolution for phase estimation by relating a controlled Hamiltonian evolution to controlled versions of the Hamiltonian-term unitaries.

  • Phase estimation requires implementing a controlled-exp(iHt) gate.

QjQ†

Phase estimation uses controlled Hamiltonian rotations that can be decomposed into ordinary Hamiltonian rotations and simple controlled gates. For Pauli terms, this construction has constant-factor overhead.

  • Controlled-exp(iτHj) rotations can be implemented using two exp(±iτHj/2) rotations and two control-X or control-Z gates.
  • The controlled-evolution Hamiltonian is H′j = |1⟩⟨1| ⊗ Hj, preserving the term structure and norms assumed for Hj.
  • For fixed t and ϵ, controlled evolution requires exactly as many exp(iH′jτ) rotations as ordinary simulation requires exp(iHjτ) rotations.
  • If exp(iH′jτ) is not native, implementing controlled rotations introduces additional overhead.
  • When Hj are Pauli operators, the controlled rotations can be implemented with constant-factor overhead using the circuit construction.

Appendix E: Phase estimation

The phase-estimation procedure targets ground-state energy estimation from an ansatz with nonzero ground-state overlap. Its accuracy and failure probability depend on precision bits, repetitions, and accumulated Trotter error.

  • Phase estimation samples eigenenergies according to probabilities related to an ansatz state's overlaps, then uses the lowest reported energy to estimate the ground state.
  • Chemical accuracy requires estimating energies to additive error δE ≤ 10^-4, with the required precision determining the number of phase-estimation bits.
  • The protocol applies a sequence of controlled-U^(2j−1) unitaries, equivalently written as exp(iAtj) with tj = 2jπ.
  • Finite Trotter error can increase the probability of incorrect measurement outcomes.
  • The total failure probability is bounded using the summed Trotter error ϵtot and the individual errors ϵj for each controlled unitary.

1. Failure probabilities

Ground-state estimation is repeated because the prepared ansatz may yield the ground-state energy only probabilistically, and finite failure probability requires additional repetitions.

  • At least 1/f phase-estimation repetitions are needed to be confident of sampling the ground-state energy when f is the ansatz's ground-state overlap probability.

2. qDRIFT

The qDRIFT phase-estimation analysis allocates simulation errors across controlled evolutions and derives a total gate-cost bound while accounting for failure probability and chemical-accuracy scaling.

  • For each controlled-U^(2j−1) unitary, N(j) denotes the number of gates required to achieve its target error ϵj.
  • The analysis includes an extra factor of 2 from the controlled-rotation construction and uses λA = 1/2 for the operator A.
  • The individual errors ϵj are selected to minimize the total gate count subject to the constraint that their sum equals ϵtot.
  • The total qDRIFT cost is obtained by summing N(j) over all phase-estimation indices j from 1 to m.
  • For chemical accuracy, δE ≤ 10^-4 implies 2^m ≫ 1, allowing the approximation 2^m − 1 ∼ 2^m.
  • The resulting expression substitutes ϵtot in terms of Pf and collects constants to obtain the final rounded cost estimate.
  • In the small-Pf regime, the optimal per-run failure probability is pf = (2/3)Pf, yielding X2 ≤ 27/2 Pf^3.

3. Random Trotter

The second-order random-Trotter analysis derives bounds for controlled operations and optimizes parameters under small failure probabilities. These expressions provide the gate-count ingredients used for the phase-estimation comparison.

  • The analysis applies the preceding framework to second-order random Trotter and bounds the gate count for controlled-U operations.
  • The optimal choice of ε_j is selected subject to the relevant constraints.
  • For small P_f, choosing p_f = (3/4)P_f yields Y^(3/2) ∼ 4.35/P_f^2.

4. Comparison

The phase-estimation comparison plots rigorous upper bounds for qDRIFT and second-order Trotter as functions of failure probability. At moderate failure probability, qDRIFT shows large reported speedups, while actual performance and the effect of newer phase-estimation methods remain unresolved.

  • At P_f = 5%, the reported speedups are ×1406, ×304, and ×789, respectively.
  • The speedup advantage decreases as P_f becomes smaller and vanishes around P_f ∼ 10^-4–10^-5.
  • The plots use known rigorous upper bounds, while actual performance is expected to be many orders of magnitude better.
  • Second-order Trotter may regain the advantage for actual performance, and modern phase-estimation techniques could improve both protocols.
Loading 1811.08017v2…