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

Chapman & Hall/CRC eBooks

Phase Estimation

Andreas Wichert

Published Nov 28, 2023• 0 citations
Publisher

Abstract

The Kitaev's Phase Estimation Algorithm (also referred to as quantum eigenvalue estimation algorithm) is a quantum algorithm to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. We explain the algorithm and indicate an example of the determination of the eigenvalue of the T gate. Then we introduce the quantum counting algorithm that is based on the quantum phase estimation algorithm and on the Grover's search algorithm. Quantum counting algorithm is a quantum algorithm for counting the number of solutions for a given search problem.

DOI
10.1201/9781003374404-20

Related papers

Simulation of a quantum algorithm for phase estimation

Alexander N. Prokopenya

A quantum algorithm for estimating the phase, which determines the eigenvalue of a unitary operator, is discussed. It is assumed that the eigenvector of this operator and the corresponding quantum circuit are given. The memory register where the approximate phase value is stored consists of n qubits, which makes it possible to determine the phase accurate to 2 −n with the probability greater than 8/π 2 . By way of example, computations for the case of the quantum phase shift operator are performed. The simulation of the quantum algorithm and the computation of the eigenvalue are performed using the QuantumCircuit package written in the Wolfram Mathematica computer algebra system. This system is also used to perform all the computations and visualize the results.

Programming and Computer Software•Mar 1, 2015•7 citations

Implementation of phase estimation and quantum counting algorithms on an NMR quantum-information processor

Jae‐Seung Lee, Jae‐Hyun Kim, Yongwook Cheong +1 more

The quantum Fourier transform is a key factor in achieving exponential speedup relative to classical algorithms. We implemented the phase estimation algorithm, which is the very basic application example of the quantum Fourier transform, on a three-bit nuclear magnetic resonance quantum-information processor. The algorithm was applied to one-bit Grover operators to estimate eigenvalues. We also demonstrated the counting algorithm with the same operators to obtain the number of the marked states. The results of projective measurements required by the algorithms were obtained from the split peak positions in the spectra.

Physical Review A•Oct 23, 2002•19 citations

A Quantum Algorithm for Solving the Travelling Salesman Problem by Quantum Phase Estimation and Quantum Search

Ch. Tszyun'si, Ilya I. Beterov

Abstract A quantum algorithm for solving the traveling salesman problem by the quantum phase estimation and quantum search method is considered. An approach is developed that was previously proposed for solving this problem. A quantum register is used to encode the eigenstates of a unitary operator whose phase determines the length of each possible route. The quantum phase estimation algorithm is used to estimate the length of a route. Then, to find the minimum route length, the measured values of length are encoded into the states of the second quantum register, and the search for the optimal route is carried out using a modified Grover algorithm. Numerical simulation of the proposed quantum algorithm is carried out using the Qiskit library for one and two iterations of the modified Grover algorithm.

Journal of Experimental and Theoretical Physics•Aug 1, 2023•11 citations

A Quantum Algorithm for Solving the Travelling Salesman Problem by Quantum Phase Estimation and Quantum Search

Ch. Tszyun'si, Ilya I. Beterov

A quantum algorithm for solving the traveling salesman problem by the quantum phase estimation and quantum search method is considered. An approach is developed that was previously proposed for solving this problem. A quantum register is used to encode the eigenstates of a unitary operator whose phase determines the length of each possible route. The quantum phase estimation algorithm is used to estimate the length of a route. Then, to find the minimum route length, the measured values of length are encoded into the states of the second quantum register, and the search for the optimal route is carried out using a modified Grover algorithm. Numerical simulation of the proposed quantum algorithm is carried out using the Qiskit library for one and two iterations of the modified Grover algorithm.

Журнал Экспериментальной и Теоретической Физики•Dec 15, 2023•0 citations

Measurement-based quantum phase estimation algorithm for finding eigenvalues of non-unitary matrices

Hefeng Wang, Lian-Ao Wu, Yu-xi Liu +1 more

We propose a quantum algorithm for finding eigenvalues of non-unitary matrices. We show how to construct, through interactions in a quantum system and projective measurements, a non-Hermitian or non-unitary matrix and obtain its eigenvalues and eigenvectors. This proposal combines ideas of frequent measurement, measured quantum Fourier transform, and quantum state tomography. It provides a generalization of the conventional phase estimation algorithm, which is limited to Hermitian or unitary matrices.

arXiv:0906.2538•Physical Review A•Dec 3, 2010•37 citations

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•37 citations
The Kitaev's Phase Estimation Algorithm (also referred to as quantum eigenvalue estimation algorithm) is a quantum algorithm to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. We explain the algorithm and indicate an example of the determination of the eigenvalue of the T gate. Then we introduce the quantum counting algorithm that is based on the quantum phase estimation algorithm and on the Grover's search algorithm. Quantum counting algorithm is a quantum algorithm for counting the number of solutions for a given search problem.
A quantum algorithm for estimating the phase, which determines the eigenvalue of a unitary operator, is discussed. It is assumed that the eigenvector of this operator and the corresponding quantum circuit are given. The memory register where the approximate phase value is stored consists of n qubits, which makes it possible to determine the phase accurate to 2 −n with the probability greater than 8/π 2 . By way of example, computations for the case of the quantum phase shift operator are performed. The simulation of the quantum algorithm and the computation of the eigenvalue are performed using the QuantumCircuit package written in the Wolfram Mathematica computer algebra system. This system is also used to perform all the computations and visualize the results.
The quantum Fourier transform is a key factor in achieving exponential speedup relative to classical algorithms. We implemented the phase estimation algorithm, which is the very basic application example of the quantum Fourier transform, on a three-bit nuclear magnetic resonance quantum-information processor. The algorithm was applied to one-bit Grover operators to estimate eigenvalues. We also demonstrated the counting algorithm with the same operators to obtain the number of the marked states. The results of projective measurements required by the algorithms were obtained from the split peak positions in the spectra.
Abstract A quantum algorithm for solving the traveling salesman problem by the quantum phase estimation and quantum search method is considered. An approach is developed that was previously proposed for solving this problem. A quantum register is used to encode the eigenstates of a unitary operator whose phase determines the length of each possible route. The quantum phase estimation algorithm is used to estimate the length of a route. Then, to find the minimum route length, the measured values of length are encoded into the states of the second quantum register, and the search for the optimal route is carried out using a modified Grover algorithm. Numerical simulation of the proposed quantum algorithm is carried out using the Qiskit library for one and two iterations of the modified Grover algorithm.
A quantum algorithm for solving the traveling salesman problem by the quantum phase estimation and quantum search method is considered. An approach is developed that was previously proposed for solving this problem. A quantum register is used to encode the eigenstates of a unitary operator whose phase determines the length of each possible route. The quantum phase estimation algorithm is used to estimate the length of a route. Then, to find the minimum route length, the measured values of length are encoded into the states of the second quantum register, and the search for the optimal route is carried out using a modified Grover algorithm. Numerical simulation of the proposed quantum algorithm is carried out using the Qiskit library for one and two iterations of the modified Grover algorithm.
We propose a quantum algorithm for finding eigenvalues of non-unitary matrices. We show how to construct, through interactions in a quantum system and projective measurements, a non-Hermitian or non-unitary matrix and obtain its eigenvalues and eigenvectors. This proposal combines ideas of frequent measurement, measured quantum Fourier transform, and quantum state tomography. It provides a generalization of the conventional phase estimation algorithm, which is limited to Hermitian or unitary matrices.
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.