A random compiler for fast Hamiltonian simulation

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

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

• The appendix reproduces prior Trotter and Suzuki results from Childs, Ostrander and Su.Source: Appendix C · p. 7

Trotter decomposition

• Deterministic and randomized Trotter decompositions have error bounds whose comparison depends on coefficients a_TROTT and b_TROTT.Source: Appendix C · p. 7
• When b_TROTT ≪ a_TROTT, the randomized Trotter approach has a significant advantage; its gate count is Lr.Source: Appendix C · p. 7

Suzuki decompositions

• Deterministic and randomized 2k-order Suzuki decompositions are bounded by analogous coefficient pairs a_2k−SUZUKI and b_2k−SUZUKI.Source: Appendix C · p. 7
• As k →∞, the randomized Suzuki advantage disappears because both error coefficients approach a similar order of magnitude.Source: Appendix C · p. 7

Chemistry approximations

• For chemistry problems with ϵ < 10−2, the approximation is very close to the exact upper bound, while numerics use exact expressions.Source: Appendix C · p. 7

Gate counts

• Higher Suzuki order improves scaling with Λ, t, and ϵ, but large constant prefactors make k = 3 uncommon and k = 1 often optimal.Source: Appendix C · p. 7

• Phase estimation requires implementing a controlled-exp(iHt) gate.Source: Appendix D · p. 7

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

• 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.Source: Appendix E · p. 8
• Chemical accuracy requires estimating energies to additive error δE ≤ 10^-4, with the required precision determining the number of phase-estimation bits.Source: Appendix E · p. 8
• The protocol applies a sequence of controlled-U^(2j−1) unitaries, equivalently written as exp(iAtj) with tj = 2jπ.Source: Appendix E · p. 8
• Finite Trotter error can increase the probability of incorrect measurement outcomes.Source: Appendix E · p. 8
• The total failure probability is bounded using the summed Trotter error ϵtot and the individual errors ϵj for each controlled unitary.Source: Appendix E · p. 9

• 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.Source: §1 · p. 9

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

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

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