Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1902.11168 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Iterative quantum phase estimation with optimized sample complexity

E. van den Berg

Published Oct 1, 2020• 5 citations
arXivHTMLPDF

Abstract

In this work we consider Kitaev's algorithm for quantum phase estimation. We analyze the use of phase shifts that simplify the estimation of successive bits in the estimation of unknown phase φ, By using increasingly accurate shifts we reduce the number of measurements to the point where only a single measurement is needed for each additional bit. This results in an algorithm that can estimate φ to m + 2 bits of accuracy with probability at least 1- ϵ using Nϵ+ m measurements, where Nϵis a quantity that depends only on ϵ and the particular sampling algorithm. We present different sampling algorithms and study the exact number of measurements needed through careful numerical evaluation, and provide theoretical bounds and numerical values for Nϵ.

DOI
10.1109/qce49297.2020.00011

Related papers

Tight Bounds for Quantum Phase Estimation and Related Problems

Nikhil S. Mande, Ronald de Wolf

Phase estimation, due to Kitaev \cite{Kit95}, is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary U , and an eigenstate | ψ ⟩ of U with unknown eigenvalue e i θ , and the task is to estimate the eigenphase θ within ± δ , with high probability. The cost of an algorithm for us is the number of applications of U and U − 1 .We tightly characterize the cost of several variants of phase estimation where we are no longer given an eigenstate, but are required to estimate the maximum eigenphase of U , aided by advice in the form of states (or a unitary preparing those states) which are promised to have at least a certain overlap γ with the top eigenspace.We give algorithms and nearly matching lower bounds for all ranges of parameters.We show that a small number of copies of the advice state (or of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having lots of advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of U . We immediately obtain a lower bound on the complexity of the Unitary recurrence time problem, resolving an open question of She and Yuen \cite{SY23}.Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that a phase-estimation algorithm with precision δ and error probability ϵ has cost Ω ( 1 δ log ⁡ 1 ϵ ) , matching an easy upper bound. This contrasts with some other scenarios in quantum computing (e.g., search) where error-probability reduction costs only a factor O ( log ⁡ ( 1 / ϵ ) ) . Our lower bound uses a variant of the polynomial method with trigonometric polynomials.

arXiv:2305.04908•Quantum•Jun 15, 2026•7 citations

Iterative quantum phase estimation on an IBM quantum processor

N.A. Zhuravlev, Ilya I. Beterov

Abstract An elementary algorithm of quantum phase estimation based on the modified Kitaev algorithm is implemented on two qubits of an IBM quantum processor. This algorithm includes adiabatic preparation of the initial state, controlled phase shift with allowance for the results of previous measurements of qubit states, and single measurement of the qubit quantum state in order to obtain each significant bit of the measured phase. Classical error correction is applied to determine the correct sequence of bits, which makes it possible to eliminate the influence of limited accuracy of two-qubit gates.

Quantum Electronics•May 19, 2021•1 citation

Phase estimation with randomized Hamiltonians

Ian Kivlichan, Christopher Granade, Nathan Wiebe

Iterative phase estimation has long been used in quantum computing to estimate Hamiltonian eigenvalues. This is done by applying many repetitions of the same fundamental simulation circuit to an initial state, and using statistical inference to glean estimates of the eigenvalues from the resulting data. Here, we show a generalization of this framework where each of the steps in the simulation uses a different Hamiltonian. This allows the precision of the Hamiltonian to be changed as the phase estimation precision increases. Additionally, through the use of importance sampling, we can exploit knowledge about the ground state to decide how frequently each Hamiltonian term should appear in the evolution, and minimize the variance of our estimate. We rigorously show, if the Hamiltonian is gapped and the sample variance in the ground state expectation values of the Hamiltonian terms sufficiently small, that this process has a negligible impact on the resultant estimate and the success probability for phase estimation. We demonstrate this process numerically for two chemical Hamiltonians, and observe substantial reductions in the number of terms in the Hamiltonian; in one case, we even observe a reduction in the number of qubits needed for the simulation. Our results are agnostic to the particular simulation algorithm, and we expect these methods to be applicable to a range of approaches.

arXiv:1907.10070•Jul 23, 2019•4 citations

Experimental Challenges of Implementing Quantum Phase Estimation Algorithms on IBM Quantum Computer

Hamed Mohammadbagherpoor, Young-Hyun Oh, Anand Singh +2 more

Many researchers have been heavily investigated on quantum phase estimation (QPE) algorithms to find the unknown phase, since QPE is the core building block of the most quantum algorithms such as the Shor's factoring algorithm, quantum sampling algorithms, and finding the eigenvalues of unitary matrices. Kitaev's algorithm and QPE algorithms using inverse Quantum Fourier transform were proposed and widely used by researchers as a key component for their quantum algorithms. In this paper, we explore the experimental challenges of QPE algorithms on Noisy Intermediate-Scale Quantum (NISQ) computers by implementing various QPE algorithms on the state-of-the-art IBM quantum computer. Our experimental results demonstrate that the accuracy of finding the phase using these algorithms are severely constrained by NISQ's physical characteristics such as coherence time and error rates. To mitigate such physical limitations, we propose modified solutions of these algorithms by reducing the number of control gates and phase shift operations. Our experimental results showed that our solutions can significantly increase the accuracy of the finding phase in near-term quantum computers.

arXiv:1903.07605•Mar 18, 2019•7 citations

Quantum Phase Estimation and Arbitrary Accuracy Iterative Phase Estimation Using Multivalued Logic

Vamsi Parasa, Marek A. Perkowski

This papers presents the generalization of the quantum phase estimation (QPE) algorithm to multivalued logic. QPE is a very important subroutine used in many quantum algorithms of practical importance. The QPE using qudits has certain advantages when compared to the version using qubits. The QPE using qudits is more accurate and requires lesser number of qudits (as the value of the radix d increases) to estimate the phase up to a given accuracy with a given success probability. Since the existing quantum computer implementations use only few qubits, it is important to have alternative versions of the QPE which use as few qubits as possible. In this regard, the iterative quantum phase estimation algorithm (IQPE) which uses only single qubit to store the phase information has been developed. The number of iterations involved in the IQPE is directly proportional to the required accuracy in the estimated phase. In this regard, IQPE using qudits requires (logarithmically) lesser number of iterations (and hence is faster) compared to the one using qubits. In this paper, we also develop the multivalued logic version of the IQPE and describe its implementation.

•Jan 1, 2015•0 citations

Iterative phase estimation

Caleb J O'Loan

We give an iterative algorithm for phase estimation of a parameter θ, which is within a logarithmic factor of the Heisenberg limit. Unlike other methods, we do not need any entanglement or an extra rotation gate which can perform arbitrary rotations with almost perfect accuracy: only a single copy of the unitary channel and basic measurements are needed. Simulations show that the algorithm is successful. We also look at iterative phase estimation when depolarizing noise is present. It is seen that the algorithm is still successful provided the number of iterative stages is below a certain threshold.

arXiv:0904.3426•Journal of Physics A Mathematical and Theoretical•Dec 4, 2009•18 citations
In this work we consider Kitaev's algorithm for quantum phase estimation. We analyze the use of phase shifts that simplify the estimation of successive bits in the estimation of unknown phase φ, By using increasingly accurate shifts we reduce the number of measurements to the point where only a single measurement is needed for each additional bit. This results in an algorithm that can estimate φ to m + 2 bits of accuracy with probability at least 1- ϵ using Nϵ+ m measurements, where Nϵis a quantity that depends only on ϵ and the particular sampling algorithm. We present different sampling algorithms and study the exact number of measurements needed through careful numerical evaluation, and provide theoretical bounds and numerical values for Nϵ.
Phase estimation, due to Kitaev \cite{Kit95}, is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary U , and an eigenstate | ψ ⟩ of U with unknown eigenvalue e i θ , and the task is to estimate the eigenphase θ within ± δ , with high probability. The cost of an algorithm for us is the number of applications of U and U − 1 .We tightly characterize the cost of several variants of phase estimation where we are no longer given an eigenstate, but are required to estimate the maximum eigenphase of U , aided by advice in the form of states (or a unitary preparing those states) which are promised to have at least a certain overlap γ with the top eigenspace.We give algorithms and nearly matching lower bounds for all ranges of parameters.We show that a small number of copies of the advice state (or of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having lots of advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of U . We immediately obtain a lower bound on the complexity of the Unitary recurrence time problem, resolving an open question of She and Yuen \cite{SY23}.Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that a phase-estimation algorithm with precision δ and error probability ϵ has cost Ω ( 1 δ log ⁡ 1 ϵ ) , matching an easy upper bound. This contrasts with some other scenarios in quantum computing (e.g., search) where error-probability reduction costs only a factor O ( log ⁡ ( 1 / ϵ ) ) . Our lower bound uses a variant of the polynomial method with trigonometric polynomials.
Abstract An elementary algorithm of quantum phase estimation based on the modified Kitaev algorithm is implemented on two qubits of an IBM quantum processor. This algorithm includes adiabatic preparation of the initial state, controlled phase shift with allowance for the results of previous measurements of qubit states, and single measurement of the qubit quantum state in order to obtain each significant bit of the measured phase. Classical error correction is applied to determine the correct sequence of bits, which makes it possible to eliminate the influence of limited accuracy of two-qubit gates.
Iterative phase estimation has long been used in quantum computing to estimate Hamiltonian eigenvalues. This is done by applying many repetitions of the same fundamental simulation circuit to an initial state, and using statistical inference to glean estimates of the eigenvalues from the resulting data. Here, we show a generalization of this framework where each of the steps in the simulation uses a different Hamiltonian. This allows the precision of the Hamiltonian to be changed as the phase estimation precision increases. Additionally, through the use of importance sampling, we can exploit knowledge about the ground state to decide how frequently each Hamiltonian term should appear in the evolution, and minimize the variance of our estimate. We rigorously show, if the Hamiltonian is gapped and the sample variance in the ground state expectation values of the Hamiltonian terms sufficiently small, that this process has a negligible impact on the resultant estimate and the success probability for phase estimation. We demonstrate this process numerically for two chemical Hamiltonians, and observe substantial reductions in the number of terms in the Hamiltonian; in one case, we even observe a reduction in the number of qubits needed for the simulation. Our results are agnostic to the particular simulation algorithm, and we expect these methods to be applicable to a range of approaches.
Many researchers have been heavily investigated on quantum phase estimation (QPE) algorithms to find the unknown phase, since QPE is the core building block of the most quantum algorithms such as the Shor's factoring algorithm, quantum sampling algorithms, and finding the eigenvalues of unitary matrices. Kitaev's algorithm and QPE algorithms using inverse Quantum Fourier transform were proposed and widely used by researchers as a key component for their quantum algorithms. In this paper, we explore the experimental challenges of QPE algorithms on Noisy Intermediate-Scale Quantum (NISQ) computers by implementing various QPE algorithms on the state-of-the-art IBM quantum computer. Our experimental results demonstrate that the accuracy of finding the phase using these algorithms are severely constrained by NISQ's physical characteristics such as coherence time and error rates. To mitigate such physical limitations, we propose modified solutions of these algorithms by reducing the number of control gates and phase shift operations. Our experimental results showed that our solutions can significantly increase the accuracy of the finding phase in near-term quantum computers.
This papers presents the generalization of the quantum phase estimation (QPE) algorithm to multivalued logic. QPE is a very important subroutine used in many quantum algorithms of practical importance. The QPE using qudits has certain advantages when compared to the version using qubits. The QPE using qudits is more accurate and requires lesser number of qudits (as the value of the radix d increases) to estimate the phase up to a given accuracy with a given success probability. Since the existing quantum computer implementations use only few qubits, it is important to have alternative versions of the QPE which use as few qubits as possible. In this regard, the iterative quantum phase estimation algorithm (IQPE) which uses only single qubit to store the phase information has been developed. The number of iterations involved in the IQPE is directly proportional to the required accuracy in the estimated phase. In this regard, IQPE using qudits requires (logarithmically) lesser number of iterations (and hence is faster) compared to the one using qubits. In this paper, we also develop the multivalued logic version of the IQPE and describe its implementation.
We give an iterative algorithm for phase estimation of a parameter θ, which is within a logarithmic factor of the Heisenberg limit. Unlike other methods, we do not need any entanglement or an extra rotation gate which can perform arbitrary rotations with almost perfect accuracy: only a single copy of the unitary channel and basic measurements are needed. Simulations show that the algorithm is successful. We also look at iterative phase estimation when depolarizing noise is present. It is seen that the algorithm is still successful provided the number of iterative stages is below a certain threshold.