Bayesian quantum phase estimation beyond the eigenstate approximation: sample complexity, Cramér–Rao bounds, and adaptive measurement design for non-eigenstate and mixed-state inputs on NISQ devices

Akoramurthy Balasubramaniam, B. Surendiran, Xiaochun Cheng +1 more

Frontiers in Quantum Science and TechnologyAug 11, 20260 citations

arXiv:2303.01517

An adaptive Bayesian quantum algorithm for phase estimation

Joseph G. Smith, C. H. W. Barnes, David R. M. Arvidsson-Shukur

Published Mar 2, 2023• 0 citations

arXiv HTML PDF

Abstract

N_{\mathrm{tot}}

times, the variance of the estimates can scale as

O(1/{N^2_{\mathrm{tot}}})

, compared to the best ``classical'' strategy with

O(1/{N_{\mathrm{tot}}})

. The original algorithm for quantum phase estimation cannot be implemented on near-term hardware as it requires large-scale entangled probes and fault-tolerant quantum computing. Therefore, alternative algorithms have been introduced that rely on coherence and statistical inference. These algorithms produce quantum-boosted phase estimates without inter-probe entanglement. This family of phase-estimation algorithms have, until now, never exhibited the possibility of achieving optimal scaling

O(1/{N^2_{\mathrm{tot}}})

. Moreover, previous works have not considered the effect of noise on these algorithms. Here, we present a coherence-based phase-estimation algorithm which can achieve the optimal quadratic scaling in the mean absolute error and the mean squared error. In the presence of noise, our algorithm produces errors that approach the theoretical lower bound. The optimality of our algorithm stems from its adaptive nature: Each step is determined, iteratively, using a Bayesian protocol that analyses the results of previous steps.

DOI: 10.48550/arxiv.2303.01517

Related papers

Adaptive Bayesian quantum algorithm for phase estimation

Joseph G. Smith, C. H. W. Barnes, David R. M. Arvidsson-Shukur

Quantum-phase-estimation algorithms are critical subroutines in many applications for quantum computers and in quantum-metrology protocols. These algorithms estimate the unknown strength of a unitary evolution. By using coherence or entanglement to sample the unitary N tot times, the variance of the estimates can scale as O ( 1 / N tot 2 ) , compared to the best “classical” strategy with O ( 1 / N tot ) . The original algorithm for quantum phase estimation cannot be implemented on near-term hardware as it requires large-scale entangled probes and fault-tolerant quantum computing. Therefore, alternative algorithms have been introduced that rely on coherence and statistical inference. These algorithms produce quantum-boosted phase estimates without interprobe entanglement. This family of phase-estimation algorithms have, until now, never exhibited the possibility of achieving optimal scaling O ( 1 / N tot 2 ) . Moreover, previous works have not considered the effect of noise on these algorithms. Here, we present a coherence-based phase-estimation algorithm which can achieve the optimal quadratic scaling in the mean absolute error and the mean squared error. In the presence of noise, our algorithm produces errors that approach the theoretical lower bound. The optimality of our algorithm stems from its adaptive nature: Each step is determined, iteratively, using a Bayesian protocol that analizes the results of previous steps. Published by the American Physical Society 2024Quantum-phase-estimation algorithms are critical subroutines in many applications for quantum computers and in quantum-metrology protocols. These algorithms estimate the unknown strength of a unitary evolution. By using coherence or entanglement to sample the unitary N tot times, the variance of the estimates can scale as O ( 1 / N tot 2 ) , compared to the best “classical” strategy with O ( 1 / N tot ) . The original algorithm for quantum phase estimation cannot be implemented on near-term hardware as it requires large-scale entangled probes and fault-tolerant quantum computing. Therefore, alternative algorithms have been introduced that rely on coherence and statistical inference. These algorithms produce quantum-boosted phase estimates without interprobe entanglement. This family of phase-estimation algorithms have, until now, never exhibited the possibility of achieving optimal scaling O ( 1 / N tot 2 ) . Moreover, previous works have not considered the effect of noise on these algorithms. Here, we present a coherence-based phase-estimation algorithm which can achieve the optimal quadratic scaling in the mean absolute error and the mean squared error. In the presence of noise, our algorithm produces errors that approach the theoretical lower bound. The optimality of our algorithm stems from its adaptive nature: Each step is determined, iteratively, using a Bayesian protocol that analizes the results of previous steps. Published by the American Physical Society 2024

Physical Review AApr 11, 202423 citations

An iterative quantum-phase-estimation protocol for near-term quantum hardware

Smith, Joseph G., C. H. W. Barnes, David R. M. Arvidsson-Shukur

Given $N_{\textrm{tot}}$ applications of a unitary operation with an unknown phase $θ$ , a large-scale fault-tolerant quantum system can {reduce} an estimate's {error} scaling from $\mathcal{O} \left[ 1 / \sqrt{N_{\textrm{tot}}} \right]$ to $\mathcal{O} \left[ 1 / {N_{\textrm{tot}}} \right]$ . Owing to the limited resources available to near-term quantum devices, entanglement-free protocols have been developed, which achieve a $\mathcal{O} \left[ \log(N_{\textrm{tot}}) / N_{\textrm{tot}} \right]$ {mean-absolute-error} scaling. Here, we propose a new two-step protocol for near-term phase estimation, with an improved {error} scaling. Our protocol's first step produces several low-{standard-deviation} estimates of $θ$ , within $θ$ 's parameter range. The second step iteratively hones in on one of these estimates. Our protocol's {mean absolute error} scales as $\mathcal{O} \left[ \sqrt{\log (\log N_{\textrm{tot}})} / N_{\textrm{tot}} \right]$ . Furthermore, we demonstrate a reduction in the constant scaling factor and the required circuit depths: our protocol can outperform the asymptotically optimal quantum-phase estimation algorithm for realistic values of $N_{\textrm{tot}}$ .Given $N_{\textrm{tot}}$ applications of a unitary operation with an unknown phase $θ$, a large-scale fault-tolerant quantum system can {reduce} an estimate's {error} scaling from $\mathcal{O} \left[ 1 / \sqrt{N_{\textrm{tot}}} \right]$ to $\mathcal{O} \left[ 1 / {N_{\textrm{tot}}} \right]$. Owing to the limited resources available to near-term quantum devices, entanglement-free protocols have been developed, which achieve a $\mathcal{O} \left[ \log(N_{\textrm{tot}}) / N_{\textrm{tot}} \right]$ {mean-absolute-error} scaling. Here, we propose a new two-step protocol for near-term phase estimation, with an improved {error} scaling. Our protocol's first step produces several low-{standard-deviation} estimates of $θ$, within $θ$'s parameter range. The second step iteratively hones in on one of these estimates. Our protocol's {mean absolute error} scales as $\mathcal{O} \left[ \sqrt{\log (\log N_{\textrm{tot}})} / N_{\textrm{tot}} \right]$. Furthermore, we demonstrate a reduction in the constant scaling factor and the required circuit depths: our protocol can outperform the asymptotically optimal quantum-phase estimation algorithm for realistic values of $N_{\textrm{tot}}$.

arXiv:2206.06392Jun 13, 20220 citations

Iterative quantum-phase-estimation protocol for shallow circuits

Joseph G. Smith, C. H. W. Barnes, David R. M. Arvidsson-Shukur

Given ${N}_{\text{tot}}$ applications of a unitary operation, parametrized by an unknown phase, a phase-estimation protocol on a large-scale fault-tolerant quantum system can reduce the standard deviation of an estimate of the phase from scaling as $O[1/\sqrt{{N}_{\text{tot}}}]$ to scaling as $O[1/{N}_{\text{tot}}]$ . Owing to the limited resources available to near-term quantum devices, protocols that do not entangle probes have been developed. Their mean absolute error scales as $O[log({N}_{\text{tot}})/{N}_{\text{tot}}]$ . Here, we propose a two-step protocol for near-term phase estimation, with an improved error scaling. Our protocol's first step produces several low-standard-deviation estimates of $\ensuremath{\theta}$, within $\ensuremath{\theta}$'s parameter range. The second step iteratively homes in on one of these estimates. Our protocol achieves a mean-absolute-error scaling of $O[\sqrt{log(log{N}_{\text{tot}})}/{N}_{\text{tot}}]$ and a root-mean-square-error scaling of $O[\sqrt{log{N}_{\text{tot}}}/{N}_{\text{tot}}]$ . Furthermore, we demonstrate a reduction in the constant scaling factor and the required circuit depths. This allows our protocol to outperform the asymptotically optimal quantum-phase-estimation algorithm for realistic values of ${N}_{\text{tot}}$ .Given ${N}_{\text{tot}}$ applications of a unitary operation, parametrized by an unknown phase, a phase-estimation protocol on a large-scale fault-tolerant quantum system can reduce the standard deviation of an estimate of the phase from scaling as $O[1/\sqrt{{N}_{\text{tot}}}]$ to scaling as $O[1/{N}_{\text{tot}}]$. Owing to the limited resources available to near-term quantum devices, protocols that do not entangle probes have been developed. Their mean absolute error scales as $O[log({N}_{\text{tot}})/{N}_{\text{tot}}]$. Here, we propose a two-step protocol for near-term phase estimation, with an improved error scaling. Our protocol's first step produces several low-standard-deviation estimates of $\ensuremath{\theta}$, within $\ensuremath{\theta}$'s parameter range. The second step iteratively homes in on one of these estimates. Our protocol achieves a mean-absolute-error scaling of $O[\sqrt{log(log{N}_{\text{tot}})}/{N}_{\text{tot}}]$ and a root-mean-square-error scaling of $O[\sqrt{log{N}_{\text{tot}}}/{N}_{\text{tot}}]$. Furthermore, we demonstrate a reduction in the constant scaling factor and the required circuit depths. This allows our protocol to outperform the asymptotically optimal quantum-phase-estimation algorithm for realistic values of ${N}_{\text{tot}}$.

Physical Review ADec 19, 202216 citations

Optimal quantum phase estimation algorithms

Joseph T. Smith

It is suggested that computers exploiting quantum phenomena can solve tasks with an efficiency surpassing that achievable by classical computers. One example of this quantum advantage arises in the task of phase estimation. Here, an unknown eigenvalue of a unitary evolution is estimated, a critical subroutine for many quantum algorithms and quantum metrology protocols. For a fixed amount of resources, the utilisation of quantum coherence and entanglement can lead to a quadratic increase in precision of the final estimate compared to classical statistical limits. In systems affected by depolarising noise, including current quantum hardware, this improvement becomes a constant factor. While numerous phase estimation algorithms have been proposed claiming to achieve these theoretical limits, the lack of well-defined criteria for both precision and resource utilisation casts doubt on these results. Further issues arise due to a lack of point identification (the existence of multiple equally likely estimates) that some algorithms have. I aim to address these issues in this thesis. I employ statistical inference, the theoretical foundation for interpreting any quantum measurement, in order to find rigorous definitions for precision and resource use. By combining these definitions with previous work in the field of quantum metrology, I am able to derive theoretical precision limits that one can hope to achieve. I then outline several phase estimation algorithms that can achieve these limits in different contexts. These algorithms that I describe are split into three major groups. Algorithms in the first group focus on the process of point identification; one set of measurements provides a precise estimate of the unknown phase before an additional set of measurements removes any ambiguities present. This second set of measurements can be either decided before any measurement is taken or during measurements in an iterative fashion. I show that the balancing of resources used in each set of measurements can lead to optimally scaling precision both with and without depolarising noise. These algorithms are based upon two of my peer-reviewed articles, [Phys. Rev. A 106, 062615 (2022)] and [Phys. Rev. A 109, 042412 (2024)]. The second group of algorithms that I introduce use the principles of Bayesian experimental design. Here, previous measurement outcomes are used to select future measurements recursively. These algorithms require large classical computing times to select each measurement but boast high precision in certain metrics. The final group of algorithms exploit the oscillating nature of phases by using a discrete Fourier transform (DFT). The DFT can be implemented using either classical or quantum hardware, the latter of which leads to the famous quantum phase estimation algorithm (QPEA). In this thesis, I show that the QPEA performs worse than some classical precision limits. However, I also suggest some modifications to the QPEA circuit that can lead to optimal precision scaling. These results and modifications are described in one of my articles awaiting publication [arXiv:2505.00764].It is suggested that computers exploiting quantum phenomena can solve tasks with an efficiency surpassing that achievable by classical computers. One example of this quantum advantage arises in the task of phase estimation. Here, an unknown eigenvalue of a unitary evolution is estimated, a critical subroutine for many quantum algorithms and quantum metrology protocols. For a fixed amount of resources, the utilisation of quantum coherence and entanglement can lead to a quadratic increase in precision of the final estimate compared to classical statistical limits. In systems affected by depolarising noise, including current quantum hardware, this improvement becomes a constant factor. While numerous phase estimation algorithms have been proposed claiming to achieve these theoretical limits, the lack of well-defined criteria for both precision and resource utilisation casts doubt on these results. Further issues arise due to a lack of point identification (the existence of multiple equally likely estimates) that some algorithms have. I aim to address these issues in this thesis. I employ statistical inference, the theoretical foundation for interpreting any quantum measurement, in order to find rigorous definitions for precision and resource use. By combining these definitions with previous work in the field of quantum metrology, I am able to derive theoretical precision limits that one can hope to achieve. I then outline several phase estimation algorithms that can achieve these limits in different contexts. These algorithms that I describe are split into three major groups. Algorithms in the first group focus on the process of point identification; one set of measurements provides a precise estimate of the unknown phase before an additional set of measurements removes any ambiguities present. This second set of measurements can be either decided before any measurement is taken or during measurements in an iterative fashion. I show that the balancing of resources used in each set of measurements can lead to optimally scaling precision both with and without depolarising noise. These algorithms are based upon two of my peer-reviewed articles, [Phys. Rev. A 106, 062615 (2022)] and [Phys. Rev. A 109, 042412 (2024)]. The second group of algorithms that I introduce use the principles of Bayesian experimental design. Here, previous measurement outcomes are used to select future measurements recursively. These algorithms require large classical computing times to select each measurement but boast high precision in certain metrics. The final group of algorithms exploit the oscillating nature of phases by using a discrete Fourier transform (DFT). The DFT can be implemented using either classical or quantum hardware, the latter of which leads to the famous quantum phase estimation algorithm (QPEA). In this thesis, I show that the QPEA performs worse than some classical precision limits. However, I also suggest some modifications to the QPEA circuit that can lead to optimal precision scaling. These results and modifications are described in one of my articles awaiting publication [arXiv:2505.00764].

Sep 12, 20250 citations

Time-adaptive phase estimation

Brennan de Neeve, A. V. Lebedev, Vlad Negnevitsky +1 more

Phase estimation is known to be a robust method for single-qubit gate calibration in quantum computers, while Bayesian estimation is widely used in devising optimal methods for learning in quantum systems. We present a Bayesian method that adaptively chooses a control phase and the time of coherent evolution. The uniqueness of the approach is to use analytics to implement an efficient numerical algorithm that offers exact calculation of the Bayesian probability and associated utility functions, even in the presence of noise. We determine the utility of control parameter values using functions of the prior probability of the phase that quantify expected knowledge gain in terms of either expected narrowing of the posterior or expected information gain. We find that by maximizing the of expected gain we obtain phase estimates having standard deviation a factor of 1.43 larger than the Heisenberg limit using a classical sequential strategy for noise-free experiments. In the presence of dephasing, we find near-optimal performance with respect to the Cramér-Rao bound. We also demonstrate some robustness of the estimates to noise that is not accounted for in the model of the estimator, making the methods suitable for calibrating operations in quantum computers. The rate of gain can be adjusted to account for times in the experiment other than the coherent evolution of the unknown phase, such as times required for state preparation or readout. The combined features of the method make it well suited to single-qubit gate calibration in trapped-ion or neutral atom experiments and promises a wide range of other applications by offering near-optimal phase estimation that straightforwardly accounts for experimental imperfections.Phase estimation is known to be a robust method for single-qubit gate calibration in quantum computers, while Bayesian estimation is widely used in devising optimal methods for learning in quantum systems. We present a Bayesian method that adaptively chooses a control phase and the time of coherent evolution. The uniqueness of the approach is to use analytics to implement an efficient numerical algorithm that offers exact calculation of the Bayesian probability and associated utility functions, even in the presence of noise. We determine the utility of control parameter values using functions of the prior probability of the phase that quantify expected knowledge gain in terms of either expected narrowing of the posterior or expected information gain. We find that by maximizing the of expected gain we obtain phase estimates having standard deviation a factor of 1.43 larger than the Heisenberg limit using a classical sequential strategy for noise-free experiments. In the presence of dephasing, we find near-optimal performance with respect to the Cramér-Rao bound. We also demonstrate some robustness of the estimates to noise that is not accounted for in the model of the estimator, making the methods suitable for calibrating operations in quantum computers. The rate of gain can be adjusted to account for times in the experiment other than the coherent evolution of the unknown phase, such as times required for state preparation or readout. The combined features of the method make it well suited to single-qubit gate calibration in trapped-ion or neutral atom experiments and promises a wide range of other applications by offering near-optimal phase estimation that straightforwardly accounts for experimental imperfections.

arXiv:2405.08930Physical Review ResearchApr 21, 20252 citations

Akoramurthy Balasubramaniam, B. Surendiran, Xiaochun Cheng +1 more

Background Quantum phase estimation (QPE) is a foundational subroutine in quantum algorithms that ranges from Shor’s factoring scheme to variational quantum eigensolvers and quantum metrology protocols. Classical post-processing replacements for the inverse quantum Fourier transform (iQFT) —specifically Kitaev-style iterative estimation and Bayesian update schemes—substantially reduce circuit depth, making them practical for noisy intermediate-scale quantum (NISQ) hardware. Despite this promise, the statistical performance of these methods under the conditions that actually arise in practice—non-eigenstate inputs characterised by eigenstate overlap p ≡ O = | ψ | ϕ | 2 < 1 and mixed-state purity γ ≡ P = Tr ( ρ 2 ) < 1 —remains uncharacterised in the literature. Methods We develop a rigorous information-theoretic framework for Bayesian QPE (BQPE) beyond the eigenstate assumption. Starting from the binary measurement likelihood attenuated by the joint factor O P , we derive exact classical Fisher information expressions and apply the Cramér–Rao inequality to obtain tight variance lower bounds. We then construct an adaptive measurement protocol based on von Mises posterior updates, prove its asymptotic efficiency in the frequentist sense, and establish matching upper and lower bounds on sample complexity. All theoretical results are validated against 2,000 -trial Monte Carlo simulations and cross-checked against published nitrogen-vacancy (NV) centre and photonic experimental data. Results We prove that the fundamental variance floor for any unbiased frequentist estimator is ( 1 − p γ ) / ( N p γ n ̄ 2 ) 1 / ( N ( p γ ) 2 n ̄ 2 ) , where NBackground Quantum phase estimation (QPE) is a foundational subroutine in quantum algorithms that ranges from Shor’s factoring scheme to variational quantum eigensolvers and quantum metrology protocols. Classical post-processing replacements for the inverse quantum Fourier transform (iQFT) —specifically Kitaev-style iterative estimation and Bayesian update schemes—substantially reduce circuit depth, making them practical for noisy intermediate-scale quantum (NISQ) hardware. Despite this promise, the statistical performance of these methods under the conditions that actually arise in practice—non-eigenstate inputs characterised by eigenstate overlap p ≡ O = | ψ | ϕ | 2 < 1 and mixed-state purity γ ≡ P = Tr ( ρ 2 ) < 1 —remains uncharacterised in the literature. Methods We develop a rigorous information-theoretic framework for Bayesian QPE (BQPE) beyond the eigenstate assumption. Starting from the binary measurement likelihood attenuated by the joint factor O P , we derive exact classical Fisher information expressions and apply the Cramér–Rao inequality to obtain tight variance lower bounds. We then construct an adaptive measurement protocol based on von Mises posterior updates, prove its asymptotic efficiency in the frequentist sense, and establish matching upper and lower bounds on sample complexity. All theoretical results are validated against 2,000 -trial Monte Carlo simulations and cross-checked against published nitrogen-vacancy (NV) centre and photonic experimental data. Results We prove that the fundamental variance floor for any unbiased frequentist estimator is ( 1 − p γ ) / ( N p γ n ̄ 2 ) 1 / ( N ( p γ ) 2 n ̄ 2 ) , where N

Frontiers in Quantum Science and TechnologyAug 11, 20260 citations

N_{\mathrm{tot}}

times, the variance of the estimates can scale as

O(1/{N^2_{\mathrm{tot}}})

, compared to the best ``classical'' strategy with

O(1/{N_{\mathrm{tot}}})

O(1/{N^2_{\mathrm{tot}}})

Given

N_{\textrm{tot}}

applications of a unitary operation with an unknown phase

θ

, a large-scale fault-tolerant quantum system can {reduce} an estimate's {error} scaling from

\mathcal{O} \left[ 1 / \sqrt{N_{\textrm{tot}}} \right]

\mathcal{O} \left[ 1 / {N_{\textrm{tot}}} \right]

. Owing to the limited resources available to near-term quantum devices, entanglement-free protocols have been developed, which achieve a

\mathcal{O} \left[ \log(N_{\textrm{tot}}) / N_{\textrm{tot}} \right]

{mean-absolute-error} scaling. Here, we propose a new two-step protocol for near-term phase estimation, with an improved {error} scaling. Our protocol's first step produces several low-{standard-deviation} estimates of

θ

, within

θ

's parameter range. The second step iteratively hones in on one of these estimates. Our protocol's {mean absolute error} scales as

\mathcal{O} \left[ \sqrt{\log (\log N_{\textrm{tot}})} / N_{\textrm{tot}} \right]

. Furthermore, we demonstrate a reduction in the constant scaling factor and the required circuit depths: our protocol can outperform the asymptotically optimal quantum-phase estimation algorithm for realistic values of

N_{\textrm{tot}}

Given

{N}_{\text{tot}}

applications of a unitary operation, parametrized by an unknown phase, a phase-estimation protocol on a large-scale fault-tolerant quantum system can reduce the standard deviation of an estimate of the phase from scaling as

O[1/\sqrt{{N}_{\text{tot}}}]

to scaling as

O[1/{N}_{\text{tot}}]

. Owing to the limited resources available to near-term quantum devices, protocols that do not entangle probes have been developed. Their mean absolute error scales as

O[log({N}_{\text{tot}})/{N}_{\text{tot}}]

. Here, we propose a two-step protocol for near-term phase estimation, with an improved error scaling. Our protocol's first step produces several low-standard-deviation estimates of $\ensuremath{\theta}$, within $\ensuremath{\theta}$'s parameter range. The second step iteratively homes in on one of these estimates. Our protocol achieves a mean-absolute-error scaling of

O[\sqrt{log(log{N}_{\text{tot}})}/{N}_{\text{tot}}]

and a root-mean-square-error scaling of

O[\sqrt{log{N}_{\text{tot}}}/{N}_{\text{tot}}]

. Furthermore, we demonstrate a reduction in the constant scaling factor and the required circuit depths. This allows our protocol to outperform the asymptotically optimal quantum-phase-estimation algorithm for realistic values of

{N}_{\text{tot}}