We obtain a query lower bound for quantum algorithms solving the phase estimation problem. Our analysis generalizes existing lower-bound approaches to the case where the oracle $Q$ is given by controlled powers ${Q}^{p}$ of $Q$ , as it is, for example, in Shor's order-finding algorithm. In this setting we will prove a $\ensuremath{\Omega}(\mathrm{log}\phantom{\rule{0.2em}{0ex}}1∕ϵ)$ lower bound for the number of applications of ${Q}^{{p}_{1}}$ , ${Q}^{{p}_{2}},\dots{}$ . This bound is tight due to a matching upper bound. We obtain the lower bound using a technique based on frequency analysis.We obtain a query lower bound for quantum algorithms solving the phase estimation problem. Our analysis generalizes existing lower-bound approaches to the case where the oracle $Q$ is given by controlled powers ${Q}^{p}$ of $Q$, as it is, for example, in Shor's order-finding algorithm. In this setting we will prove a $\ensuremath{\Omega}(\mathrm{log}\phantom{\rule{0.2em}{0ex}}1∕ϵ)$ lower bound for the number of applications of ${Q}^{{p}_{1}}$, ${Q}^{{p}_{2}},\dots{}$. This bound is tight due to a matching upper bound. We obtain the lower bound using a technique based on frequency analysis.

arXiv:quant-ph/0412008Physical Review AApr 8, 200519 citations

Fisher information based lower bounds on the cost of quantum phase estimation

Ryosuke Kimura, Kosuke Mitarai

Quantum phase estimation (QPE) is a cornerstone of quantum algorithms designed to estimate the eigenvalues of a unitary operator. QPE is typically implemented through two paradigms with distinct circuit structures: quantum Fourier transform-based QPE (QFT-QPE) and Hadamard test-based QPE (HT-QPE). Existing performance assessments fail to separate the statistical information inherent in the quantum circuit from the efficiency of classical post-processing, thereby obscuring the limits intrinsic to the circuit structure itself. In this study, we employ Fisher information and the Cramer-Rao lower bound to formulate the performance limits of circuit designs independent of the efficiency of classical post-processing. Defining the circuit depth as $T$ and the total runtime as $t_{\rm total}$ , our results demonstrate that the achievable scaling is constrained by a non-trivial lower bound on their product $T\,t_{\rm total}$ , although previous studies have typically treated the circuit depth $T$ and the total runtime $t_{\rm total}$ as separate resources. Notably, QFT-QPE possesses a more favorable scaling with respect to the overlap between the input state and the target eigenstate corresponding to the desired eigenvalue than HT-QPE. Numerical simulations confirm these theoretical findings, demonstrating a clear performance crossover between the two paradigms depending on the overlap. Furthermore, we verify that practical algorithms, specifically the quantum multiple eigenvalue Gaussian filtered search (QMEGS) and curve-fitted QPE, achieve performance levels closely approaching our derived limits. By elucidating the performance limits inherent in quantum circuit structures, this work concludes that the optimal choice of circuit configuration depends significantly on the overlap.Quantum phase estimation (QPE) is a cornerstone of quantum algorithms designed to estimate the eigenvalues of a unitary operator. QPE is typically implemented through two paradigms with distinct circuit structures: quantum Fourier transform-based QPE (QFT-QPE) and Hadamard test-based QPE (HT-QPE). Existing performance assessments fail to separate the statistical information inherent in the quantum circuit from the efficiency of classical post-processing, thereby obscuring the limits intrinsic to the circuit structure itself. In this study, we employ Fisher information and the Cramer-Rao lower bound to formulate the performance limits of circuit designs independent of the efficiency of classical post-processing. Defining the circuit depth as $T$ and the total runtime as $t_{\rm total}$, our results demonstrate that the achievable scaling is constrained by a non-trivial lower bound on their product $T\,t_{\rm total}$, although previous studies have typically treated the circuit depth $T$ and the total runtime $t_{\rm total}$ as separate resources. Notably, QFT-QPE possesses a more favorable scaling with respect to the overlap between the input state and the target eigenstate corresponding to the desired eigenvalue than HT-QPE. Numerical simulations confirm these theoretical findings, demonstrating a clear performance crossover between the two paradigms depending on the overlap. Furthermore, we verify that practical algorithms, specifically the quantum multiple eigenvalue Gaussian filtered search (QMEGS) and curve-fitted QPE, achieve performance levels closely approaching our derived limits. By elucidating the performance limits inherent in quantum circuit structures, this work concludes that the optimal choice of circuit configuration depends significantly on the overlap.

quant-pharXiv:2603.12706Mar 16, 20260 citations

Curve-Fitted QPE: Extending Quantum Phase Estimation Results for a Higher Precision using Classical Post-Processing

Lim, S. M., Cristian E. Susa, Cohen, R.

Quantum Phase Estimation is a crucial component of several front-running quantum algorithms. Improving the efficiency and accuracy of QPE is currently a very active field of research. In this work, we present a hybrid quantum-classical approach that consists of the standard QPE circuit and classical post-processing using curve-fitting, where special attention is given to the latter. We show that our approach achieves high precision with optimal Cramér-Rao lower bound performance and is comparable in error resolution with the Variational Quantum Eigensolver and Maximum Likelihood Amplitude Estimation algorithms. Our method could potentially be further extended to the case of estimating multiple phases.Quantum Phase Estimation is a crucial component of several front-running quantum algorithms. Improving the efficiency and accuracy of QPE is currently a very active field of research. In this work, we present a hybrid quantum-classical approach that consists of the standard QPE circuit and classical post-processing using curve-fitting, where special attention is given to the latter. We show that our approach achieves high precision with optimal Cramér-Rao lower bound performance and is comparable in error resolution with the Variational Quantum Eigensolver and Maximum Likelihood Amplitude Estimation algorithms. Our method could potentially be further extended to the case of estimating multiple phases.

arXiv:2409.15752Sep 24, 20241 citation

Quantum Phase Estimation

Osama M. Raisuddin, Suvranu De

Springer eBooksNov 14, 20250 citations

Quantum Phase Estimation

Hiu Yung Wong

Springer eBooksJan 1, 20226 citations

We obtain a query lower bound for quantum algorithms solving the phase estimation problem. Our analysis generalizes existing lower-bound approaches to the case where the oracle

Q

is given by controlled powers

{Q}^{p}

Q

, as it is, for example, in Shor's order-finding algorithm. In this setting we will prove a $\ensuremath{\Omega}(\mathrm{log}\phantom{\rule{0.2em}{0ex}}1∕ϵ)$ lower bound for the number of applications of

{Q}^{{p}_{1}}

{Q}^{{p}_{2}},\dots{}

. This bound is tight due to a matching upper bound. We obtain the lower bound using a technique based on frequency analysis.

T

and the total runtime as

t_{\rm total}

, our results demonstrate that the achievable scaling is constrained by a non-trivial lower bound on their product

T\,t_{\rm total}

, although previous studies have typically treated the circuit depth

T

and the total runtime

t_{\rm total}

as separate resources. Notably, QFT-QPE possesses a more favorable scaling with respect to the overlap between the input state and the target eigenstate corresponding to the desired eigenvalue than HT-QPE. Numerical simulations confirm these theoretical findings, demonstrating a clear performance crossover between the two paradigms depending on the overlap. Furthermore, we verify that practical algorithms, specifically the quantum multiple eigenvalue Gaussian filtered search (QMEGS) and curve-fitted QPE, achieve performance levels closely approaching our derived limits. By elucidating the performance limits inherent in quantum circuit structures, this work concludes that the optimal choice of circuit configuration depends significantly on the overlap.