PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Bayesian Phase Estimation

Nathan Wiebe, Christopher E Granade

arXiv:1508.00869v1quant-ph

TL;DR

Phase estimation needs efficient, robust eigenphase inference under experimental constraints, while iterative methods infer eigenvalue bits through classical processing. The paper develops a particle-filter-inspired rejection-filtering Bayesian method that directly updates phase distributions and supports recovery from imperfections. The method reduces experimental requirements relative to Kitaev’s method, remains informative under decoherence, and improves experimental relevance, though its error distribution can have substantial tails.

  • Problem

    Phase estimation must remain efficient and reliable despite decoherence and other experimental imperfections that constrain quantum experiments.

  • Method

    Rejection Filtering Phase Estimation uses Bayesian updates on sampled phase hypotheses and refits them to a Gaussian posterior model.

  • Results

    The number of experiments scales as O(log(1/ϵ)), and after 150 experiments Kitaev’s phase-estimation median error is roughly 10 million times RFPE’s.

  • Takeaways & Limitations

    RFPE reduces experimental time and remains usable with decoherence, including settings where restarting can help recover from depolarization or unsuitable incoming data.

  • Takeaways & Limitations

    RFPE can produce fat error tails: after 100 updates, median error is roughly 10^-10 radians while some errors are on the order of 1.

Abstract

from arXiv · show

We provide a new efficient adaptive algorithm for performing phase estimation that does not require that the user infer the bits of the eigenphase in reverse order; rather it directly infers the phase and estimates the uncertainty in the phase directly from experimental data. Our method is highly flexible, recovers from failures, and can be run in the presence of substantial decoherence and other experimental imperfections and is as fast or faster than existing algorithms.

I. INTRODUCTION

Phase estimation uses quantum-information methods to estimate eigenvalues efficiently, while iterative phase estimation relies on classical inference from experimental data. The paper introduces a tailored classical inference method to improve speed and robustness against experimental imperfections.

  • Motivation: Phase estimation estimates eigenvalues using exponentially fewer experiments than statistical sampling and can saturate the Heisenberg-limit scaling.The approach is important for quantum-computing speedups, but decoherence can severely limit executable quantum gates.
  • Existing approach: Iterative phase estimation replaces quantum resources for eigenvalue inference with a classical inference algorithm applied to experimental data.Most phase-estimation algorithms infer binary-expansion bits from least significant to most significant.
  • Research question: The paper asks whether improved classical inference can accelerate phase estimation or increase its robustness to experimental error.
  • Contribution: The proposed classical inference method is inspired by particle filters and is tailored to phase estimation.The method is presented as outperforming existing iterative methods while tolerating depolarizing noise and small systematic errors.
  • Approach: Rejection sampling efficiently approximates Bayesian inference, allowing phase estimation to use Bayesian speed and robustness while retaining traditional-method efficiency.

II. BAYESIAN PHASE ESTIMATION

Bayesian phase estimation updates a prior over the eigenphase using experimental outcomes and returns both an estimate and its uncertainty. The section presents the posterior as the basis for adaptive experiment design and stopping decisions.

  • Bayesian update: Bayesian phase estimation updates the prior distribution over the eigenphase using Bayes’ rule after each experimental outcome.The posterior becomes the prior for the next random experiment.
  • Bayesian update: The likelihood function P(0|φ; θ, M) supplies the experiment-dependent probability needed for each Bayesian update.
  • Posterior estimates: The posterior mean estimates the true eigenvalue, while its standard deviation estimates uncertainty in that value.Credible regions can also be extracted from the posterior distribution.
  • Adaptive control: Posterior uncertainty guides the design of informative experiments and allows the protocol to stop once a threshold accuracy is reached.

III. APPROXIMATE BAYESIAN PHASE ESTIMATION

RFPE approximates Bayesian phase estimation with particle-filter ideas and rejection sampling, directly updating a compact posterior model. It achieves efficient phase inference while trading experimental, computational, and memory resources differently from existing methods.

  • RFPE method: RFPE models the prior as a Gaussian, updates samples using Bayesian likelihoods, and refits the accepted samples to a Gaussian posterior.Rejection sampling approximates the Bayesian update by accepting each sample with probability P(E|φ_j; θ, M)/κ_E.
  • RFPE method: RFPE reduces memory requirements by a factor of 1 000 or more by considering one rejection-sampling sample at a time.The supplied passage attributes this reduction to the rejection-sampling implementation.
  • RFPE method: Accepted samples are distributed according to the posterior P(φ|E; M, θ), making rejection filtering an approximation to Bayesian inference.The acceptance probability is proportional to the likelihood times the prior density.
  • Performance: The median error shrinks exponentially with experiment number for m > 100, with roughly 150 experiments needed for 32 bits of accuracy.The experiment count is proportional to the evolution time under the particle guess heuristic.
  • Performance: RFPE needs O(log(1/ϵ)) experiments, while Kitaev’s method needs O(log(1/ϵ) log log(1/ϵ)); after 150 experiments, Kitaev’s median error is roughly 10 million times larger.RFPE’s experimental time scales as O(1/ϵ), saturating the Heisenberg limit up to a multiplicative constant, with λ ≈ 0.17.
  • Comparisons: Compared with ITPE, RFPE uses fewer applications of U in the stated t = 10 000 setting, while the methods trade experimental and computational resources differently.ITPE requires nearly five times the applications of U for φ = 2πk/t with integer k < t.

A. Phase estimation with depolarizing noise

RFPE adapts phase-estimation experiments to decoherence by incorporating a known T2 limit, while retaining useful learning as coherence degrades. Its error transitions from exponential scaling at short times to polynomial scaling under significant decoherence.

  • Decoherence model: Known T2 is incorporated into the decoherence model used to modify the phase-estimation procedure.The model is appropriate when controlled-U implementation dominates the time cost, and T2 is assumed known.
  • Experiment selection: Equation (6) chooses experiments near the coherence limit because decoherence increases posterior variance while longer evolution otherwise improves frequency precision.The competing scalings are O(M^-2) without decoherence and O(exp(2M/T2)) for decoherence-induced posterior variance.
  • Experiment selection: Nearly 100-fold less computing time is required to select the experiments from (6) than for locally optimized solutions.
  • Performance under decoherence: Figure 3 shows that RFPE smoothly transitions from exponential error scaling at short times to roughly 1/N^0.6 scaling when decoherence becomes significant.Restricting experiments to a more coherent regime can hurt phase inference.

IV. TRACKING EIGENPHASES

RFPE tracks changing eigenphases by testing whether its current posterior remains consistent with the quantum state and restarting when learning fails. The restart preserves previously learned spectral information and enables real-time tracking after state transitions.

  • Restart detection: RFPE uses inexpensive experiments to detect when a depolarized state makes its current learning process inconsistent.The procedure performs a one-sided consistency test between the prior distribution and the current state.
  • Restart procedure: After a detected failure, RFPE prepares the initial state, resets σ, and resumes learning until the estimate can be matched to the closest known eigenvalue.The restart retains spectral information by reusing the identified eigenvalue and its uncertainty.
  • Restart detection: For τ = 0.1, measuring 1 rejects the hypothesis that the prior is correct at p ≤ 0.002.
  • Real-time tracking: The restarting algorithm rapidly detects transitions away from an instantaneous eigenstate and begins inferring the new instantaneous eigenvalue.

V. CONCLUSION

The paper presents RFPE as making phase estimation more experimentally relevant by reducing experimental time and providing resilience to decoherence. It positions decoherence-tolerant phase estimation as an efficient alternative to variational eigensolvers in current experiments.

  • RFPE substantially reduces required experimental time and remains resilient to decoherence, improving phase estimation’s experimental relevance.
  • The algorithm’s ability to learn under decoherence provides an efficient alternative to variational eigensolvers used in present-day experiments.

Appendix A: Variance Reduction Strategies

RFPE can suffer from heavy-tailed phase errors, so the paper introduces restarting and uncertainty-aware strategies to reduce the impact of large failures. Restarting substantially lowers mean error, while traditional phase-estimation restarting is less compatible with expensive experiments performed first.

  • Error tails: After 100 updates for m > 50, RFPE’s median error is roughly 10^-10 radians, but some experiments have errors on the order of 1.The authors identify these fat error tails as an important drawback in typical applications.
  • Variance reduction: RFPE outputs σ as an uncertainty estimate, allowing repeated majority voting to be avoided or experiments to be made less aggressive.The paper also mentions multimodal prior models as an alternative strategy.
  • Restarting: Restarting is triggered by detecting insufficient decay of log(σ) with experiment number, then selecting the estimate associated with the smallest observed σ.The selected model is the one for which the inference algorithm has greatest certainty.
  • Restarting: The restarting strategy reduces mean error from 0.0513 radians to 1.08 × 10^-6 radians.The authors report that this substantially reduces the probability of a large eigenphase-estimation error.
  • Comparison with traditional PE: Restarting cannot be easily transferred to Kitaev’s phase-estimation algorithm because its most expensive experiments are performed first.

Appendix B: Stability Against Errors in the Likelihood Function

The algorithm remains effective with uncharacterized depolarizing noise omitted from its likelihood model, although stronger noise reduces the information learned per experiment.

  • Figure 6 compares error CDFs after 200 updates for m = 2000 under Γ = ∞ and Γ = 0.1, with τ = 0.1 and T2 = ∞.Each CDF uses 1000 random eigenphase inference problems.
  • Figure 7 reports inference errors across unmodeled-noise strengths γ for T2 = 1000, using a fixed unknown eigenstate and medians over 100 random eigenphases.
  • Unmodeled depolarizing noise does not prevent eigenphase estimation, but it reduces the number of bits inferred per experiment.With γ = 0.4, outcomes are replaced by random bits with probability 40%, despite this noise being excluded from the likelihood model.
  • The error decay exponent shrinks approximately as λ ≈ 0.17e^-3.1γ while the algorithm continues learning exponentially until depolarizing noise becomes significant.

Appendix C: Stability of Rejection Filtering PE

Rejection filtering can become unstable when the likelihood is too flat relative to the number of prior samples, because posterior-mean shifts become smaller than sampling fluctuations.

  • Rejection filtering may break down when likelihood flatness makes posterior-mean shifts much smaller than sample-variance fluctuations.The resulting mean dynamics can behave essentially as a random walk.
  • The maximum posterior-mean shift shrinks as the likelihood becomes increasingly flat.
  • m must scale at least as Ω(α^2/δ^2) to track small posterior changes under the theorem’s flat-likelihood conditions.
  • The stated sample-size condition is not sufficient because actual posterior-mean components may shift less than the theorem’s upper bounds.
  • Exact Bayesian inference can be preferable for extremely flat likelihoods, requiring O(log(1/δ)) bits with a fixed discrete hypothesis count.Batching experiments can reduce flatness, but is generally inefficient unless an appropriate κE is known for each datum.

Appendix D: Bayes Factors for Reset Rule

The reset rule can be evaluated with a likelihood ratio or Bayes factor, quantifying whether observed results favor the reset model over the current prior.

  • For a uniform prior over reset validity, the Bayes-factor formulation reduces to a likelihood ratio test.
  • L > 1 indicates increasing preference for the model proposed by the reset rule.
  • The test compares posterior odds for an invalid prior against a valid prior after observing result = 1.
  • When σ = σreset/100, µ = µreset, T2 = 100, and σreset = π/3, the likelihood ratio is approximately L ≈ 8000 for result 1.The initial prior is then 8,000 times as probably correct as the current prior in the stated example.
  • The threshold L = 1 assumes a uniform prior over whether the current prior is valid; other thresholds encode different prior beliefs.

Appendix E: Pseudocode for Algorithms

The appendices specify rejection-filtering, restart, and decoherence-aware procedures, including circular-statistics handling and evolution-time choices constrained by decoherence.

  • Bayes update: The heuristic rejection-filtering update estimates posterior mean and standard deviation incrementally using accepted samples.It avoids expensive trigonometric calls when the posterior is narrow.
  • Bayes update: The arithmetic wrap-around heuristic is correct for σ ≪ 1 but only approximate when σ is on the order of 1.Circular means are better justified in that regime, though the heuristic can remain acceptable.
  • Decoherent phase estimation: Experiments with M > T2 are expected to produce worse eigenphase estimates because decoherence can overwhelm their information.
  • Bayes update: Directional-statistics updating accumulates accepted samples in Cartesian coordinates and returns a circular mean with circular standard deviation.
  • Restarting algorithm: The restarting algorithm tests whether the current state estimate is suspect and either increments its counter or resets the uncertainty to σinit.It tests with M = τ/σ and θ = µ when the derivative and randomized restart conditions are met.
  • Decoherent phase estimation: The decoherence-aware particle-guess heuristic draws M from an exponential distribution with mean T2 and samples θ from the resampling kernel.
Loading 1508.00869v1…