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:2306.07008 · Quantum

Quantum Phase Estimation by Compressed Sensing

Changhao Yi, Cunlu Zhou, Jun Takahashi

Published Dec 27, 2024• 6 citations
arXivHTMLPDF

Abstract

As a signal recovery algorithm, compressed sensing is particularly effective when the data has low complexity and samples are scarce, which aligns natually with the task of quantum phase estimation (QPE) on early fault-tolerant quantum computers. In this work, we present a new Heisenberg-limited, robust QPE algorithm based on compressed sensing, which requires only sparse and discrete sampling of times. Specifically, given multiple copies of a suitable initial state and queries to a specific unitary matrix, our algorithm can recover the phase with a total runtime of O ( ϵ − 1 poly log ⁡ ( ϵ − 1 ) ) , where ϵ is the desired accuracy. Additionally, the maximum runtime satisfies T max ϵ ≪ π , making it comparable to state-of-the-art algorithms. Furthermore, our result resolves the basis mismatch problem in certain cases by introducing an additional parameter to the traditional compressed sensing framework.

DOI
10.22331/q-2024-12-27-1579

Related papers

Heisenberg limited multiple eigenvalue estimation via off-the-grid compressed sensing

Davide Castaldo, Stefano Corni

Quantum phase estimation is the flagship algorithm for quantum simulation on fault-tolerant quantum computers. We demonstrate that an \emph{off-grid} compressed sensing protocol, combined with a state-of-the-art signal classification method, enables the simultaneous estimation of multiple eigenvalues of a unitary matrix using the Hadamard test while sampling only a few percent of the full autocorrelation function. Our numerical evidence indicates that the proposed algorithm achieves the Heisenberg limit in both strongly and weakly correlated regimes and requires very short evolution times to obtain an $ε$-accurate estimate of multiple eigenvalues at once. Additionally -- and of independent interest -- we develop a modified off-grid protocol that leverages prior knowledge of the underlying signal for faster and more accurate recovery. Finally, we argue that this algorithm may offer a potential quantum advantage by analyzing its resilience with respect to the quality of the initial input state.

arXiv:2507.12438•Jul 16, 2025•1 citation

Control Free Quantum Phase Estimation for Efficient Eigenphase and Energy Estimation without Quantum Fourier Transform

Yalla Jnan Devi Satya Prasad

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.

•Feb 5, 2026•0 citations

On low-depth algorithms for quantum phase estimation

Hongkang Ni, Haoya Li, Lexing Ying B

Quantum phase estimation is one of the critical building blocks of quantum computing. For early fault-tolerant quantum devices, it is desirable for a quantum phase estimation algorithm to (1) use a minimal number of ancilla qubits, (2) allow for inexact initial states with a significant mismatch, (3) achieve the Heisenberg limit for the total resource used, and (4) have a diminishing prefactor for the maximum circuit length when the overlap between the initial state and the target state approaches one. In this paper, we prove that an existing algorithm from quantum metrology can achieve the first three requirements. As a second contribution, we propose a modified version of the algorithm that also meets the fourth requirement, which makes it particularly attractive for early fault-tolerant quantum devices.

arXiv:2302.02454•Quantum•Nov 6, 2023•46 citations

Measurement Complexity of Quantum Compressed Sensing

Jianyong Hu, Wei Li

Conventional compressed sensing (CS) has a measurement lower bound of M = Ω(K log(N/K)) under non-adaptive measurements. Recent experiments on quantum compressed sensing (QCS) have reported numbers of measurements below this classical lower bound. In this work, we establish lower bounds on the measurement complexity of QCS from an information-theoretic and quantum-physical perspective. QCS exploits quantum parallelism, enabling a unitary domain-alignment evolution to act on a superposition of all N basis states and map the sparse basis onto the measurement basis in a one-to-one manner. Consequently, the locations of nonzero components are explicitly carried by measurement-index labels. If only basic statistical information about the K nonzero components is required, the total number of effective index samples satisfies the coarse necessary condition Ms = Ω(K). Under independent single-index projective measurements, when the support is unknown, the nonzero probabilities satisfy pn = Θ(1/K), and exact support recovery is required with a fixed success probability, the sampling-coverage requirement leads to Ms = Θ(K ln K). If each nonzero amplitude coefficient is further required to achieve a coordinate-wise relative root-mean-square error ε, the optimal effective index sample complexity is Ms = Θ(K ln K + K/ε2), which reduces to Θ(K ln K) for fixed ε. Multimode photon-number-resolving detection can reduce the number of experimental rounds but not the total effective index sample complexity. These results show that quantum parallelism is not only a core resource for quantum computing but can also play a transformative role in measurement science.

quant-pharXiv:2610.08234•Oct 7, 2026•0 citations

On adaptive low-depth quantum algorithms for robust multiple-phase estimation

Haoya Li, Hongkang Ni, Lexing Ying B

This paper is an algorithmic study of quantum phase estimation with multiple eigenvalues. We present robust multiple-phase estimation (RMPE) algorithms with Heisenberg-limited scaling. The proposed algorithms improve significantly from the idea of single-phase estimation methods by combining carefully designed signal processing routines and an adaptive determination of runtime amplifying factors. They address both the {\em integer-power} model, where the unitary $U$ is given as a black box with only integer runtime accessible, and the {\em real-power} model, where $U$ is defined through a Hamiltonian $H$ by $U = \exp(-2π\mathrm{i} H)$ with any real runtime allowed. These algorithms are particularly suitable for early fault-tolerant quantum computers in the following senses: (1) a minimal number of ancilla qubits are used, (2) an imperfect initial state with a significant residual is allowed, (3) the prefactor in the maximum runtime can be arbitrarily small given that the residual is sufficiently small and a gap among the dominant eigenvalues is known in advance. Even if the eigenvalue gap does not exist, the proposed RMPE algorithms can achieve the Heisenberg limit while maintaining (1) and (2).

arXiv:2303.08099•Mar 14, 2023•3 citations

Adiabatic Quantum Phase Estimation

Alexander Schmidhuber, Seth Lloyd

Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision $ε$ in Heisenberg-limited time $T=Θ(1/ε)$. Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware. Here, we present a simple adiabatic protocol for QPE that achieves (up to logarithmic factors) the optimal Heisenberg-limited scaling $T = O\left( \frac{1}ε \log\left(δ^{-1}\right)\right)$ in both the precision $ε$ and failure probability $δ$. By encoding eigenvalues in populations of computational basis states rather than complex phases, our approach is naturally robust against certain dephasing errors. The adiabatic protocol only requires the ability to couple a single ancilla qubit to the system Hamiltonian as well as pairwise couplings within the ancilla register.

quant-pharXiv:2605.22770•May 22, 2026•0 citations
As a signal recovery algorithm, compressed sensing is particularly effective when the data has low complexity and samples are scarce, which aligns natually with the task of quantum phase estimation (QPE) on early fault-tolerant quantum computers. In this work, we present a new Heisenberg-limited, robust QPE algorithm based on compressed sensing, which requires only sparse and discrete sampling of times. Specifically, given multiple copies of a suitable initial state and queries to a specific unitary matrix, our algorithm can recover the phase with a total runtime of O ( ϵ − 1 poly log ⁡ ( ϵ − 1 ) ) , where ϵ is the desired accuracy. Additionally, the maximum runtime satisfies T max ϵ ≪ π , making it comparable to state-of-the-art algorithms. Furthermore, our result resolves the basis mismatch problem in certain cases by introducing an additional parameter to the traditional compressed sensing framework.
Quantum phase estimation is the flagship algorithm for quantum simulation on fault-tolerant quantum computers. We demonstrate that an \emph{off-grid} compressed sensing protocol, combined with a state-of-the-art signal classification method, enables the simultaneous estimation of multiple eigenvalues of a unitary matrix using the Hadamard test while sampling only a few percent of the full autocorrelation function. Our numerical evidence indicates that the proposed algorithm achieves the Heisenberg limit in both strongly and weakly correlated regimes and requires very short evolution times to obtain an εεε-accurate estimate of multiple eigenvalues at once. Additionally -- and of independent interest -- we develop a modified off-grid protocol that leverages prior knowledge of the underlying signal for faster and more accurate recovery. Finally, we argue that this algorithm may offer a potential quantum advantage by analyzing its resilience with respect to the quality of the initial input state.
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.
Quantum phase estimation is one of the critical building blocks of quantum computing. For early fault-tolerant quantum devices, it is desirable for a quantum phase estimation algorithm to (1) use a minimal number of ancilla qubits, (2) allow for inexact initial states with a significant mismatch, (3) achieve the Heisenberg limit for the total resource used, and (4) have a diminishing prefactor for the maximum circuit length when the overlap between the initial state and the target state approaches one. In this paper, we prove that an existing algorithm from quantum metrology can achieve the first three requirements. As a second contribution, we propose a modified version of the algorithm that also meets the fourth requirement, which makes it particularly attractive for early fault-tolerant quantum devices.
Conventional compressed sensing (CS) has a measurement lower bound of M = Ω(K log(N/K)) under non-adaptive measurements. Recent experiments on quantum compressed sensing (QCS) have reported numbers of measurements below this classical lower bound. In this work, we establish lower bounds on the measurement complexity of QCS from an information-theoretic and quantum-physical perspective. QCS exploits quantum parallelism, enabling a unitary domain-alignment evolution to act on a superposition of all N basis states and map the sparse basis onto the measurement basis in a one-to-one manner. Consequently, the locations of nonzero components are explicitly carried by measurement-index labels. If only basic statistical information about the K nonzero components is required, the total number of effective index samples satisfies the coarse necessary condition Ms = Ω(K). Under independent single-index projective measurements, when the support is unknown, the nonzero probabilities satisfy pn = Θ(1/K), and exact support recovery is required with a fixed success probability, the sampling-coverage requirement leads to Ms = Θ(K ln K). If each nonzero amplitude coefficient is further required to achieve a coordinate-wise relative root-mean-square error ε, the optimal effective index sample complexity is Ms = Θ(K ln K + K/ε2), which reduces to Θ(K ln K) for fixed ε. Multimode photon-number-resolving detection can reduce the number of experimental rounds but not the total effective index sample complexity. These results show that quantum parallelism is not only a core resource for quantum computing but can also play a transformative role in measurement science.
This paper is an algorithmic study of quantum phase estimation with multiple eigenvalues. We present robust multiple-phase estimation (RMPE) algorithms with Heisenberg-limited scaling. The proposed algorithms improve significantly from the idea of single-phase estimation methods by combining carefully designed signal processing routines and an adaptive determination of runtime amplifying factors. They address both the {\em integer-power} model, where the unitary UUU is given as a black box with only integer runtime accessible, and the {\em real-power} model, where UUU is defined through a Hamiltonian HHH by U=exp⁡(−2πiH)U = \exp(-2π\mathrm{i} H)U=exp(−2πiH) with any real runtime allowed. These algorithms are particularly suitable for early fault-tolerant quantum computers in the following senses: (1) a minimal number of ancilla qubits are used, (2) an imperfect initial state with a significant residual is allowed, (3) the prefactor in the maximum runtime can be arbitrarily small given that the residual is sufficiently small and a gap among the dominant eigenvalues is known in advance. Even if the eigenvalue gap does not exist, the proposed RMPE algorithms can achieve the Heisenberg limit while maintaining (1) and (2).
Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision εεε in Heisenberg-limited time T=Θ(1/ε)T=Θ(1/ε)T=Θ(1/ε). Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware. Here, we present a simple adiabatic protocol for QPE that achieves (up to logarithmic factors) the optimal Heisenberg-limited scaling T=O(1εlog⁡(δ−1))T = O\left( \frac{1}ε \log\left(δ^{-1}\right)\right)T=O(ε1​log(δ−1)) in both the precision εεε and failure probability δδδ. By encoding eigenvalues in populations of computational basis states rather than complex phases, our approach is naturally robust against certain dephasing errors. The adiabatic protocol only requires the ability to couple a single ancilla qubit to the system Hamiltonian as well as pairwise couplings within the ancilla register.