PaperlayerView exact revision on arXiv

Source-linked AI summary

A randomized quantum algorithm for statistical phase estimation

Kianna Wan, Mario Berta, Earl T. Campbell

arXiv:2110.12071v2quant-phcs.DS

TL;DR

Phase-estimation cost can depend on the number L of Hamiltonian terms, which can be large in electronic-structure problems. The paper combines statistical phase estimation with randomized decompositions of time evolution; for ground-state estimation it gives circuit and rotation costs, while its errors can be suppressed by collecting more samples.

  • Problem

    Phase-estimation cost often depends on Hamiltonian term count L, which can scale as O(N^4) for electronic structure and O(N^6) with transcorrelated orbitals.

    Source: §I · p. 1

  • Method

    The algorithm randomly samples runtimes and approximates each time evolution with a randomly sampled gate sequence.

    Source: §I · p. 1

  • Results

    For ground-state energy estimation, the stated costs are e O(η−2) randomly compiled circuits and at most e O(λ2∆−2) single-qubit Pauli rotations per circuit.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    Approximation and compilation errors can be suppressed by collecting more samples, allowing a trade-off between per-sample gate complexity and sample count.

    Source: §I · p. 1

Abstract

from arXiv · show

Phase estimation is a quantum algorithm for measuring the eigenvalues of a Hamiltonian. We propose and rigorously analyse a randomized phase estimation algorithm with two distinctive features. First, our algorithm has complexity independent of the number of terms L in the Hamiltonian. Second, unlike previous L-independent approaches, such as those based on qDRIFT, all sources of error in our algorithm can be suppressed by collecting more data samples, without increasing the circuit depth.

I. INTRODUCTION

The introduction frames phase estimation as a way to learn Hamiltonian spectra, while noting that Hamiltonian-term count can make implementation costly. The paper combines statistical phase estimation with randomized circuit compilation so approximation errors can be reduced through more samples rather than greater circuit depth.

I. INTRODUCTION

  • Standard phase estimation returns one eigenvalue per run, with precision and success probability depending on how often U is used.A trial state must have non-exponentially-small overlap η with the ground state for the stated ground-energy application.Source: §I · p. 1
  • Hamiltonian-term dependence can be costly: electronic-structure problems typically have L = O(N^4), rising to L = O(N^6) with transcorrelated orbitals.Simple Trotter implementations have O(L) gate complexity [10] [11].Source: §I · p. 1
  • Earlier randomized compilation enabled phase estimation with complexity independent of L, but its systematic energy-estimation error required greater gate complexity to suppress.That requirement led to high gate counts per run.Source: §I · p. 1
  • The algorithm combines random runtime sampling with random gate-sequence approximation, making its approximation and compilation errors suppressible by collecting more samples.This creates a tunable trade-off between gate complexity per sample and the number of samples required.Source: §I · p. 1
  • For ground-state energy estimation, the authors can choose e O(η−2) randomly compiled circuits when the ansatz overlap is at least η.The stated complexity hides polylogarithmic factors.Source: §I · p. 1
  • Each circuit uses one ancilla and at most e O(λ2∆−2) single-qubit Pauli rotations for additive error ∆.The passage presents this as a ground-state energy-estimation cost.Source: §I · p. 2

II. EIGENVALUE THRESHOLDING

Eigenvalue thresholding asks whether an ansatz has low-energy weight near a chosen threshold, allowing either answer when both conditions hold. The section constructs an approximate CDF estimator from a Fourier approximation and a randomized unitary decomposition, then uses Hadamard tests and sample-based decisions to solve the thresholding problem.

II. EIGENVALUE THRESHOLDING

  • Eigenvalue thresholding decides whether the ansatz has less than η weight below X−∆ or nonzero weight below X+∆; either answer is acceptable when both hold.The problem is used later to estimate ground-state energy given a suitable ansatz.Source: §II · p. 2
  • The method estimates an approximate CDF by replacing the Heaviside function with a finite Fourier series that controls approximation error, coefficient weight, and maximum time parameter.The series is constructed to approximate the Heaviside function away from its jump discontinuities.Source: §II · p. 2
  • The paper's Fourier approximation improves on Lin & Tong's parameter scaling, and the authors state that this also improves the asymptotic complexity of their phase-estimation algorithm.The comparison gives Lin & Tong's degree as d = O(δ−1 log(δ−1ε−1)) [6, Lemma 6].Source: §II · pp. 2–3
  • A decomposition of each time-evolution operator into sampled unitaries enables a trade-off between sample complexity and gate complexity per sample.Its coefficient weight is bounded by exp(t2/r), so increasing r can reduce sample complexity at the cost of more gates per sample.Source: §II · p. 3
  • Sampling decomposition terms by coefficient magnitude and estimating them with Hadamard tests gives an unbiased estimate of the approximate CDF; Hoeffding's inequality bounds the samples needed for error probability at most ϑ.The threshold decision compares Re[Z] with η/2, with Csample ≥ 4A(r)^2(η/2 − ε)^−2 ln(ϑ−1).Source: §II · pp. 3–4
  • The runtime-vector optimization reduces to an efficiently solvable one-dimensional problem, including when minimizing sample cost under gate-cost constraints.The section also gives e O(δ−2η−2) as the total complexity for a simple asymptotic choice.Source: §II · p. 4
  • The eigenvalue-thresholding algorithm has total complexity e O(δ−2η−2) when δ = τ∆, with δ−1 = O(λ/∆).For this runtime-vector choice, the sample-weight and gate-cost bounds yield the stated asymptotic total complexity.Source: §II · p. 4

III. GROUND STATE ENERGY ESTIMATION

The section adapts CDF estimation to locate the ground-state energy under a ground-space overlap promise. It gives an additive-error guarantee with high probability and quantum complexity independent of Hamiltonian sparsity L, while allowing a gate-versus-sample trade-off.

III. GROUND STATE ENERGY ESTIMATION

  • A binary-search-like procedure locates the ground-state energy by solving the threshold problem at O(log(δ^-1)) values of x, reusing samples across those values.Setting the per-threshold failure probability to ξ/s gives overall success probability at least 1−ξ by a union bound.Source: §III · p. 4
  • The ground-state energy can be estimated within additive error ∆ with probability at least 1−ξ, with complexity independent of L and total gate count scaling as eO(λ^2∆^-2η^-2).Each circuit acts on n+1 qubits and uses one copy of ρ.Source: §III · pp. 4–5
  • Tuning the runtime vector can reduce gate complexity per circuit by running more circuits for the same problem parameters.The theorem's stated complexity uses a specific runtime-vector choice.Source: §III · p. 5

IV. EXAMPLES IN QUANTUM CHEMISTRY

The chemistry examples compare resource costs for hydrogen chains and FeMoco, highlighting trade-offs with qubitization and qDRIFT-based estimates. The appendix passage states that the Fourier series can approximate the Heaviside function arbitrarily well on [−π, π] with suitable parameters.

IV. EXAMPLES IN QUANTUM CHEMISTRY

  • The resource analysis is rigorous and uses no Hamiltonian truncation, unlike the cited heuristic truncation approaches.The paper notes that the rigorous estimates may overstate resources and that heuristic Hamiltonian rescaling can further reduce costs.Source: §IV · p. 5
  • For hydrogen chains with extensive-property precision ∆∝N, the algorithm scales as eO(N^0.68), outperforming all qubitization algorithms.At constant ∆, qubitization has better scaling than this algorithm if the proposed truncation schemes are accurate.Source: §IV · p. 5
  • For FeMoco, the qDRIFT random compiler combined with phase estimation has a reported Toffoli count per sample much larger than 2Cgate from Fig. 2.The estimates use λ = 1511 Hartree and chemical accuracy ∆ = 0.0016 Hartree; each circuit uses 153 qubits.Source: §IV · p. 5, Figure 2 · p. 5

Appendix A: Fourier series approximation to the Heaviside function (Lemma 1)

  • With suitable β and d, the Fourier series can approximate the Heaviside function arbitrarily well on [−π, π].I_n(·) denotes the nth modified Bessel function of the first kind.Source: Appendix A · p. 7

1. Chebyshev approximation

The section builds a Chebyshev-polynomial approximation to the Heaviside function, converts it into a Fourier series, and establishes bounds used to control the approximation.

3. Technical lemmas

  • The technical bounds control the Chebyshev truncation error and the error-function approximation to the sign function.The latter is bounded by erfc(kν) ≤ e^(−k²ν²).Source: §1 · p. 8, §3 · p. 13

1. Chebyshev approximation

  • The paper constructs Pβ,d as a Chebyshev-polynomial approximation to the Heaviside function, with error controlled by its parameters and domain.The approximation is built through a Chebyshev expansion of a scaled error function.Source: §1 · pp. 7, 9

2. Fourier approximation

  • The Fourier approximation Fβ,d(x) is obtained by substituting sin x into Pβ,d, using Θ(x) = Θ(sin x) on [−π, π].The resulting series approximates the Heaviside function away from the interval endpoints and has an explicit coefficient-sum bound.Source: §2 · pp. 10–11

Appendix B: Proof of Eq. (5)

The appendix proves that convolving the chosen Fourier approximation with the Hamiltonian’s density yields the approximate CDF guarantees used in the main text.

Appendix B: Proof of Eq. (5)

  • The convolution bound applies when p is supported within [−(π − δ)/2, (π − δ)/2] and F approximates Θ outside the δ-neighborhood of the endpoints.Under the stated setup, the proof bounds the convolved approximation against the shifted CDF with error ε.Source: Appendix B · p. 14
  • The chosen normalization gives p support [−τλ, τλ], so Proposition 12 applies when δ ≤ τΔ.Source: Appendix B · p. 14
  • The approximate CDF eC(x) = (p ∗ F)(x) satisfies the stated guarantees for ε > 0 and δ ∈ (0, λτ], when F is chosen appropriately.The proof allows −ε ≤ F(x) ≤ 1 + ε, rather than requiring F to stay between zero and one.Source: Appendix B · pp. 13–14

Appendix C: LCU decomposition of the time evolution operator (Lemma 2)

The appendix constructs an LCU decomposition of time evolution that can be sampled as random unitaries, trading gate complexity against sample complexity.

Appendix C: LCU decomposition of the time evolution operator (Lemma 2)

  • The decomposition expresses e^(iHt) as a product of r decompositions for e^(iHt/r), with each sampled unitary implementable using r controlled single-qubit rotations.The coefficient weight is bounded by exp(t²/r), and reducing r can sharply increase the sample requirement.Source: Appendix C · pp. 14–15
  • Algorithm 2 samples a random unitary whose expectation is proportional to e^(iHt), by sampling an even integer and Pauli indices.The sampled unitary uses the selected Pauli operators and a phase determined by the integer and sign of t.Source: Appendix C · p. 16
  • The algorithm’s infinite distribution over even integers can be truncated because the probability of large integers decreases super-exponentially.The appendix states that truncation can approximate the distribution very precisely.Source: Appendix C · p. 16

Appendix D: Optimising the runtime vector for arbitrary Fourier series

The appendix optimizes runtime allocations to trade sample and gate costs, and shows that the optimization can be reduced to one dimension for arbitrary Fourier coefficients.

Appendix D: Optimising the runtime vector for arbitrary Fourier series

  • The optimization results apply to arbitrary Fourier coefficients, not only the specific series used by Algorithm 1.The appendix considers minimizing total gate complexity or minimizing sample complexity subject to a per-sample gate bound.Source: Appendix D · p. 17
  • The appendix approximates the complexity expressions, removes the sample-count ceiling, and rounds real-valued runtime choices to integers.The resulting complexities are valid but only near-optimal in general; the authors expect rounding error to be negligible when runtimes are typically large.Source: Appendix D · p. 17
  • The stated optimization omits ansatz-state preparation cost, assuming it is small relative to random-unitary implementation cost.The authors say the techniques can be adapted to include state-preparation costs.Source: Appendix D · p. 17

1. Minimising the total complexity

  • The multivariate runtime-vector optimization reduces to a one-dimensional problem that can be solved numerically.The reduction follows because the minimizing runtime vector is described by a single free parameter.Source: §1 · p. 18

2. Minimising the sample complexity given constraints on gate complexity

The section considers minimizing sample complexity under a gate-complexity ceiling, a trade-off motivated by settings where shorter circuits are preferable. The constrained runtime-vector optimization reduces to a one-dimensional problem.

2. Minimising the sample complexity given constraints on gate complexity

  • A gate-complexity ceiling can be useful when many shorter circuits are preferable, even if total complexity increases.The section frames this trade-off in the context of early fault-tolerance.Source: §2 · p. 19
  • The constrained optimization minimizes Csample(r) subject to a fixed Cgate(r), replacing the gate upper bound with equality.The text notes that allowing larger Cgate decreases the minimum required Csample.Source: §2 · p. 19
  • The runtime vector r(g)* can be found by solving a one-dimensional problem for λ* and then obtaining the corresponding entries.The derivation uses Lagrange multipliers under the condition that the optimized runtime entries are positive.Source: §2 · p. 19

Appendix E: Probabilistic analysis

The probabilistic analysis establishes that Algorithm 1 estimates the approximate CDF with an unbiased randomized estimator. Hoeffding’s inequality then bounds the error probability for its threshold decision.

1. Failure probability of Algorithm 1

  • Algorithm 1 samples runtime and unitary indices, then uses Hadamard-test outcomes to construct a randomized estimate of the approximate CDF.The sampling distribution over (j,k) is proportional to |a_jk|, with normalization A(r).Source: §1 · p. 20
  • The estimator Z is unbiased for eC(x), with its phase determined by arg(a_jk) = arg(F_j) + jx.The algorithm averages independent samples and compares the real part with η/2 to choose between the two threshold cases.Source: §1 · p. 20
  • Choosing Csample(r) as in Algorithm 1 bounds the probability of an incorrect answer by ϑ.The bound follows from Hoeffding’s inequality applied to the independent estimator samples.Source: §1 · p. 20

2. Truncating the infinite distribution

The appendix bounds the bias caused by truncating an infinite unitary distribution, then describes compilation costs for standard gates. The compilation discussion includes a lower-cost strategy for commuting, independent rotations with a shared angle.

2. Truncating the infinite distribution

  • In practice, truncating the infinite sum at a modest M has negligible effect because its coefficients decay very rapidly.The original distribution spans even non-negative integers.Source: §2 · pp. 20–21
  • Truncating the distribution makes the estimator generally biased, but the bias decreases superexponentially with truncation order M.The truncated estimator Z′ has bias B = E[Z] − E[Z′], which enters the error analysis.Source: §2 · p. 21
  • The truncation order M, which determines classical sampling complexity, scales logarithmically with the total quantum complexity A(r)Cgate(r).The bound assumes r_j ≥ |t_j| for all j.Source: §2 · pp. 21–22

Appendix F: Compiling to standard gates

  • A controlled Pauli rotation can be decomposed into Cliffords and two single-qubit Z rotations, adding a factor of 2 in non-Clifford complexity.The single-qubit rotations can be synthesized in Clifford+T, with an estimated synthesis overhead of about 100× at precision 10^-10, reducible to about 50× using randomized Ross-Selinger synthesis.Source: Appendix F · pp. 22–23
  • For commuting, independent controlled rotations with the same angle, Hamming-weight phasing reduces the large-w cost toward 2 Toffoli gates per rotation.The reported costs are about 4 Toffoli gates per rotation at w = 100 and about 6 at w = 40, assuming 25 Toffoli gates per Pauli Z rotation.Source: Appendix F · p. 23

Appendix G: Alternative rescaling factors

The section distinguishes the rescaling factor used for rigorous results from heuristic alternatives that may reduce resource overheads. It discusses how norm bounds and spectral support constrain those alternatives.

Appendix G: Alternative rescaling factors

  • The rigorous analysis assumes τ = π/(2λ + ∆), while heuristic modifications of τ can reduce resource overheads.The stated rigorous results follow under the specified rescaling assumption.Source: Appendix G · pp. 23–24
  • The bound ∥H∥ ≤ λ is often loose for frustrated systems, but computing ∥H∥ is hard and its value is typically unknown.This motivates using b = 1 in rigorous theorem statements.Source: Appendix G · p. 24
  • If p(x) has support outside the required interval with total weight at most ϵ′, a similar result holds with an additional ϵ′ additive error.The text says this error can be accommodated by slight parameter tuning when ϵ′ is small compared with η.Source: Appendix G · p. 24
  • For FeMoco at chemical accuracy, the resource plot fixes ε = 0.2 and compares b = 1, 10, and 100, with improvements possible for b > 1.It plots Csample(r)/ln(ϑ^-1) against Cgate(r); dots optimize total expected complexity and curves optimize sample complexity at fixed gate cost.Source: Figure 4 · p. 25
Loading 2110.12071v2…