Quantum phase estimation (QPE) is a key ingredient to some of the most important results of quantum computing. In this paper we examine the QPE algorithm through the looking glass of signal processing. This perspective helps to reveal a relation between the distribution of quantum phase estimates and the shape of the discrete Fourier transform (DFT) of a pure complex sinusoid. Guided by spectral shaping theory, we design a class of quantum circuits that are the quantum equivalents to classical windowing operators, for a family of window functions that have compact support in the DFT. These circuits have complexity linear in the number of target qubits, strictly lower than QPE itself. Using these circuits we are able to reshape QPE's performance characteristics. In particular, the asymptotic marginal cost for 2x reduction in fail rate (2x improvement in reliability) is reduced from one qubit to 1/3 qubit or lower, which can help reduce the qubit budget for a preset accuracy-reliability target, especially in high-reliability scenarios. This makes a demonstration of the value of signal processing principles in designing quantum algorithms.
Quantum phase estimation (QPE) is a key ingredient to some of the most important results of quantum computing. In this paper we examine the QPE algorithm through the looking glass of signal processing. This perspective helps to reveal a relation between the distribution of quantum phase estimates and the shape of the discrete Fourier transform (DFT) of a pure complex sinusoid. Guided by spectral shaping theory, we design a class of quantum circuits that are the quantum equivalents to classical windowing operators, for a family of window functions that have compact support in the DFT. These circuits have complexity linear in the number of target qubits, strictly lower than QPE itself. Using these circuits we are able to reshape QPE's performance characteristics. In particular, the asymptotic marginal cost for 2x reduction in fail rate (2x improvement in reliability) is reduced from one qubit to 1/3 qubit or lower, which can help reduce the qubit budget for a preset accuracy-reliability target, especially in high-reliability scenarios. This makes a demonstration of the value of signal processing principles in designing quantum algorithms.
Quantum Phase Estimation (QPE) routines are known to fail probabilistically even with perfect gates and input states. This effect stems from an incompatibility of finite-sized quantum registers to capture a phase within QPE with phase angles of infinite precision, and the effect extend even beyond what would be reasonably expected from rounding. This effect can be partially mitigated by biasing the phase register with a window, or taper state, from classical signal processing. This paper focuses on how windowing a coherent QPE used as a subroutine can improve the accuracy of the overall algorithm. Specifically we study the quantum task of estimating observables where window-assisted coherent QPE is used as a subroutine to implement a reflection about an eigenstate. Quantum resource estimates show over 2-orders-of-magnitude reduction in Toffoli counts over the previous costed techniques -- also assisted by the use of improved block encoding techniques -- demonstrating an encouraging decrease in resources for quantum computation of molecular observables. Since QPE, as one of only a few quantum building blocks, appears as a subroutine in many algorithms; this analysis also provides a model for understanding how window functions propagate to an improved error in composite algorithms.
In recent years, quantum algorithms have been proposed which use quantum phase estimation (QPE) coherently as a subroutine without measurement. In order to do this effectively, the routine must be able to distinguish eigenstates with success probability close to unity. In this paper, we provide the first systematic comparison between two approaches towards maximizing this success probability, one using the quantum singular value transform and the other leveraging window functions, which have been previously studied as priors of the phase value distribution. We find that the quantum singular value transform is significantly outclassed by the window function approach, with the latter able to achieve between 3 and 5 orders of magnitude improvement in the success probability with approximately 1/4 the query cost. Our circuit simulation results indicate that QPE is not a domain which benefits from the integration of QSVT and we show that the use of the Kaiser window function is currently the most practical choice for realizing QPE with high success probability.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on one of the most important breakthroughs in quantum computing: the quantum phase estimation (QPE) algorithm and its application to Shor’s factoring algorithm. The lesson begins with the phase estimation problem, Solving this problem efficiently is a cornerstone of many quantum algorithms. Spectral Theorem and Mathematical Foundations The discussion starts with the spectral theorem from linear algebra. In the context of this lesson, it is applied to unitary matrices, which can be diagonalized in an orthonormal eigenbasis. This property makes it possible to extract phase information using interference effects and controlled unitary operations. Later, the same mathematical framework extends to Hermitian operators, which are central to quantum mechanics and Hamiltonian simulation. Quantum Phase Estimation (QPE) The Quantum Phase Estimation algorithm combines: Controlled unitary operations Superposition and interference The Quantum Fourier Transform (QFT) The QFT plays a crucial role by transforming phase information encoded in amplitudes into measurable computational basis states. Importantly, the QFT can be implemented efficiently with a quantum circuit whose complexity scales polynomially with the number of qubits. From Phase Estimation to Shor’s Algorithm By applying QPE to a specific modular exponentiation operator, one obtains Shor’s algorithm, an efficient quantum algorithm for integer factorization. Shor’s algorithm demonstrates an exponential speedup over the best-known classical factoring algorithms and has profound implications for cryptography, particularly for RSA-based systems. Significance This lesson illustrates a major milestone in quantum computing: It connects abstract linear algebra (spectral theorem) to concrete algorithmic advantage. It shows how quantum interference enables extraction of hidden periodicity. It demonstrates a real-world cryptographic impact through efficient factorization. Through hands-on experimentation on IBM Q, theoretical concepts are translated into working quantum circuits, reinforcing the deep relationship between mathematics, algorithm design, and quantum computational power.
Quantum phase estimation (QPE) is fundamental to quantum algorithms for eigenvalue problems, chemistry simulation, and number-theoretic applications. However, canonical QPE implementations employ controlled unitary operations and quantum Fourier transform, incurring substantial circuit depth and control overhead that severely limit applicability on nearterm quantum hardware. This work develops a novel class of control-free phase estimation algorithms that eliminate both controlled unitaries and QFT by leveraging signal processing principles. Our approach applies uncontrolled powers of the unitary U = e −iHτ to an eigenstate or eigenstate-rich state, measures in multiple bases to capture interference patterns, and reconstructs eigenphases via classical post-processing techniques including Prony's method, compressed sensing, and harmonic inversion. We establish that for eigenstates or states with sparse eigendecomposition, our algorithms achieve phase estimation precision ϵ using Õ(1/ϵ) applications of U , matching standard QPE query complexity up to logarithmic factors while dramatically reducing circuit depth and eliminating control overhead. We provide detailed error analysis characterizing robustness to measurement noise, finite sampling, and state preparation errors. Applications to electronic structure estimation in small molecules and variational quantum eigensolvers demonstrate the practical viability of control-free QPE on both NISQ and early fault-tolerant quantum computers. Our results suggest that signal-processing-based phase estimation may offer more efficient implementations of quantum algorithms on realistic hardware.
We present several refinements and extensions of the statistical quantum phase estimation (SQPE) framework to address some of its key practical limitations, improving its applicability to realistic cases. Recently, a family of statistical approaches for QPE have been proposed where each run uses only a few ancillae and shorter circuits than standard QPE and thus is better suited for early fault-tolerant quantum computers that are qubit-and depth-limited. SQPE method within that family estimates the cumulative distribution function (CDF) associated with spectral density of the Hamiltonian for a given trial state by using its Fourier approximation and then identifies the first jump discontinuity of the CDF to determine the ground state energy (GSE) of the Hamiltonian. It relies on random compilation procedure based on linear combination of unitaries (LCU) decomposition of the Hamiltonian assuming positive Pauli weights and requires a good estimate of lower bound on the overlap between the trial and true ground state, both of which may be difficult to achieve in practice. We address these limitations by generalizing the random compilation procedure for negative Pauli weights and employing a changepoint detection method for determining GSE which does not rely on an estimate of this overlap. We also show that by exploiting symmetry of the Fourier series one can reduce number of circuit runs/samples by a factor of 2x while keeping the GSE estimation accuracy the same. We illustrate these new developments numerically via a quantum simulator in Qiskit.
ABSTRACT Quantum Phase Estimation (QPE) is a cornerstone algorithm in quantum computing, with applications ranging from integer factorization to quantum chemistry simulations. However, the resource demands of standard QPE, which require a large number of coherent qubits and deep circuits, pose significant challenges for current Noisy Intermediate Scale Quantum (NISQ) devices. In this work, we introduce the Adaptive Windowed Quantum Phase Estimation (AWQPE) algorithm, a novel method designed to address the limitations of standard QPE. AWQPE utilizes small, independent blocks of control qubits to estimate multiple phase bits simultaneously within a “window,” thereby significantly reducing the number of coherent qubits required to achieve a desired precision. These independent blocks are amenable to parallelization and, when combined with a robust least‐significant‐bit (LSB) to most‐significant‐bit (MSB) ambiguity resolution mechanism, enhance the algorithm's accuracy while mitigating the risk of error propagation. Our numerical simulations demonstrate AWQPE's accuracy and improved robustness relative to standard QPE under representative noise models, showcasing a favorable balance between resource efficiency and computational speed. This makes AWQPE particularly well‐suited for near‐term quantum platforms.