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

Selecting Efficient Phase Estimation With Constant-Precision Phase Shift Operators

Chen-Fu Chiang

Published Jan 1, 2014• 3 citations
OpenAlex

Abstract

We investigate the cost of three phase estimation procedures that require only constant-precision phase shift operators. The cost is in terms of the number of elementary gates, not just the number of measurements. Faster phase estimation requires the minimal number of measurements with a \log * factor of reduction when the required precision n is large. The arbitrary constant-precision approach (ACPA) requires the minimal number of elementary gates with a minimal factor of 14 of reduction in comparison to Kitaev's approach. The reduction factor increases as the precision gets higher in ACPA. Kitaev's approach is with a reduction factor of 14 in comparison to the faster phase estimation in terms of elementary gate counts.

Related papers

Quantum phase estimation with arbitrary constant-precision phase shift operators

Hamed Ahmadi, Chen-Fu Chiang

While Quantum phase estimation (QPE) is at the core of many quantum algorithms known to date, its physical implementation (algorithms based on quantum Fourier transform (QFT) ) is highly constrained by the requirement of high-precision controlled phase shift operators, which remain difficult to realize. In this paper, we introduce an alternative approach to approximately implement QPE with arbitrary constant-precision controlled phase shift operators. The new quantum algorithm bridges the gap between QPE algorithms based on QFT and Kitaev's original approach. For approximating the eigenphase precise to the nth bit, Kitaev's original approach does not require any controlled phase shift operator. In contrast, QPE algorithms based on QFT or approximate QFT require controlled phase shift operators with precision of at least Pi/2n. The new approach fills the gap and requires only arbitrary constant-precision controlled phase shift operators. From a physical implementation viewpoint, the new algorithm outperforms Kitaev's approach.

arXiv:1012.4727•Quantum Information and Computation•Sep 1, 2012•10 citations

Faster phase estimation

Krysta M. Svore, Matthew B. Hastings, Michael Hartley Freedman

We develop several algorithms for performing quantum phase estimation based on basic measurements and classical post-processing. We present a pedagogical review of quantum phase estimation and simulate the algorithm to numerically determine its scaling in circuit depth and width. We show that the use of purely random measurements requires a number of measurements that is optimal up to constant factors, albeit at the cost of exponential classical post-processing; the method can also be used to improve classical signal processing. We then develop a quantum algorithm for phase estimation that yields an asymptotic improvement in runtime, coming within a factor of $\log^*$ of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.

Quantum Information and Computation•Mar 1, 2014•47 citations

Faster Phase Estimation

Krysta M. Svore, Matthew B. Hastings, Michael Hartley Freedman

We develop several algorithms for performing quantum phase estimation based on basic measurements and classical post-processing. We present a pedagogical review of quantum phase estimation and simulate the algorithm to numerically determine its scaling in circuit depth and width. We show that the use of purely random measurements requires a number of measurements that is optimal up to constant factors, albeit at the cost of exponential classical post-processing; the method can also be used to improve classical signal processing. We then develop a quantum algorithm for phase estimation that yields an asymptotic improvement in runtime, coming within a factor of log* of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.

arXiv:1304.0741•Apr 2, 2013•3 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•7 citations

Selecting efficient phase estimation with constant-precision phase shift operators

Chen-Fu Chiang

arXiv:1306.2715•Quantum Information Processing•Oct 26, 2013•2 citations

Demonstrating Heisenberg-limited unambiguous phase estimation without adaptive measurements

Brendon L. Higgins, Dominic William Berry, Stephen D. Bartlett +3 more

Abstract. We derive, and experimentally demonstrate, an interferometric scheme for unambiguous phase estimation with precision scaling at the Heisenberg limit that does not require adaptive measurements. That is, with no prior knowledge of the phase, we can obtain an estimate of the phase with a standard deviation that is only a small constant factor larger than the minimum physically allowed value. Our scheme resolves the phase ambiguity that exists when multiple passes through a phase shift, or NOON states, are used to obtain improved phase resolution. Like a recently introduced adaptive technique [Higgins et al 2007 Nature 450 393], our experiment uses multiple applications of the phase shift on single photons. By not requiring adaptive measurements, but rather using a predetermined measurement sequence, the present scheme is both conceptually simpler and significantly easier to implement. Additionally, we demonstrate a simplified adaptive scheme that also surpasses the standard quantum limit for single passes. PACS numbers: 03.67.-a, 42.50.St, 03.65.TaHeisenberg-limited phase estimation without adaptive measts 2 1.

•Jan 1, 2009•56 citations
We investigate the cost of three phase estimation procedures that require only constant-precision phase shift operators. The cost is in terms of the number of elementary gates, not just the number of measurements. Faster phase estimation requires the minimal number of measurements with a \log * factor of reduction when the required precision n is large. The arbitrary constant-precision approach (ACPA) requires the minimal number of elementary gates with a minimal factor of 14 of reduction in comparison to Kitaev's approach. The reduction factor increases as the precision gets higher in ACPA. Kitaev's approach is with a reduction factor of 14 in comparison to the faster phase estimation in terms of elementary gate counts.
While Quantum phase estimation (QPE) is at the core of many quantum algorithms known to date, its physical implementation (algorithms based on quantum Fourier transform (QFT) ) is highly constrained by the requirement of high-precision controlled phase shift operators, which remain difficult to realize. In this paper, we introduce an alternative approach to approximately implement QPE with arbitrary constant-precision controlled phase shift operators. The new quantum algorithm bridges the gap between QPE algorithms based on QFT and Kitaev's original approach. For approximating the eigenphase precise to the nth bit, Kitaev's original approach does not require any controlled phase shift operator. In contrast, QPE algorithms based on QFT or approximate QFT require controlled phase shift operators with precision of at least Pi/2n. The new approach fills the gap and requires only arbitrary constant-precision controlled phase shift operators. From a physical implementation viewpoint, the new algorithm outperforms Kitaev's approach.
We develop several algorithms for performing quantum phase estimation based on basic measurements and classical post-processing. We present a pedagogical review of quantum phase estimation and simulate the algorithm to numerically determine its scaling in circuit depth and width. We show that the use of purely random measurements requires a number of measurements that is optimal up to constant factors, albeit at the cost of exponential classical post-processing; the method can also be used to improve classical signal processing. We then develop a quantum algorithm for phase estimation that yields an asymptotic improvement in runtime, coming within a factor of log⁡∗\log^*log∗ of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.
We develop several algorithms for performing quantum phase estimation based on basic measurements and classical post-processing. We present a pedagogical review of quantum phase estimation and simulate the algorithm to numerically determine its scaling in circuit depth and width. We show that the use of purely random measurements requires a number of measurements that is optimal up to constant factors, albeit at the cost of exponential classical post-processing; the method can also be used to improve classical signal processing. We then develop a quantum algorithm for phase estimation that yields an asymptotic improvement in runtime, coming within a factor of log* of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.
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. We derive, and experimentally demonstrate, an interferometric scheme for unambiguous phase estimation with precision scaling at the Heisenberg limit that does not require adaptive measurements. That is, with no prior knowledge of the phase, we can obtain an estimate of the phase with a standard deviation that is only a small constant factor larger than the minimum physically allowed value. Our scheme resolves the phase ambiguity that exists when multiple passes through a phase shift, or NOON states, are used to obtain improved phase resolution. Like a recently introduced adaptive technique [Higgins et al 2007 Nature 450 393], our experiment uses multiple applications of the phase shift on single photons. By not requiring adaptive measurements, but rather using a predetermined measurement sequence, the present scheme is both conceptually simpler and significantly easier to implement. Additionally, we demonstrate a simplified adaptive scheme that also surpasses the standard quantum limit for single passes. PACS numbers: 03.67.-a, 42.50.St, 03.65.TaHeisenberg-limited phase estimation without adaptive measts 2 1.