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:2507.12438

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

Davide Castaldo, Stefano Corni

Published Jul 16, 2025• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2507.12438

Related papers

Quantum Phase Estimation by Compressed Sensing

Changhao Yi, Cunlu Zhou, Jun Takahashi

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.

arXiv:2306.07008•Quantum•Dec 27, 2024•6 citations

Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits

Alicja Dutkiewicz, Barbara M. Terhal, Thomas E. O apos Brien

Quantum phase estimation is a cornerstone in quantum algorithm design, allowing for the inference of eigenvalues of exponentially-large sparse matrices.The maximum rate at which these eigenvalues may be learned, –known as the Heisenberg limit–, is constrained by bounds on the circuit complexity required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation that do not require coherence between experiments have garnered interest in recent years due to lower circuit depth and minimal qubit overhead. In this work we show that these methods can achieve the Heisenberg limit, a l s o when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a `phase function' g ( k ) = ∑ j A j e i ϕ j k with unknown eigenphases ϕ j and overlaps A j at quantum cost O ( k ) , we show how to estimate the phases { ϕ j } with (root-mean-square) error δ for total quantum cost T = O ( δ − 1 ) . Our scheme combines the idea of Heisenberg-limited multi-order quantum phase estimation for a single eigenvalue phase [Higgins et al (2009) and Kimmel et al (2015)] with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem [Somma (2019)] or the matrix pencil method. For our algorithm which adaptively fixes the choice for k in g ( k ) we prove Heisenberg-limited scaling when we use the time-series/QEEP subroutine. We present numerical evidence that using the matrix pencil technique the algorithm can achieve Heisenberg-limited scaling as well.

arXiv:2107.04605•Quantum•Oct 6, 2022•33 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

Quantum Spectral Estimation with Multiple Initial States: Improved Error and Cost Scaling

Lingwei Zhang, Zhiyan Ding

We study quantum spectrum and eigenstate property estimation using multiple initial states and generalized Hadamard tests. Building on the QFAMES (quantum filtering and analysis of multiplicities in eigenvalue spectra) framework, we introduce a new method that samples evolution times independently for each initial-state pair. Under the stated assumptions, when statistical error determines the sampling cost, the total Hamiltonian simulation cost required for fixed-accuracy eigenvalue and observable estimation is independent of the number of initial states, up to logarithmic factors. This improves scalability when many initial states are needed to explore the target eigenspaces. The method also reduces the cost of multiplicity recovery and retains Heisenberg-limited scaling for eigenvalue estimation. Numerical experiments support the predicted statistical error scalings.

quant-pharXiv:2610.20482•Oct 15, 2026•0 citations

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 integer-power model, where the unitary $U$ is given as a black box with only integer runtime accessible, and the real-power model, where $U$ is defined through a Hamiltonian $H$ by $U=exp(\ensuremath{-}2\ensuremath{\pi}\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).

Physical Review A•Dec 11, 2023•19 citations

Physics-Constrained Compressed Sensing for Quantum Sensing in the Data-Starved Regime

Amir Kalev

Quantum sensors promise measurement sensitivities that can scale at the Heisenberg limit, but in practice their performance is often degraded by noise, finite sampling, and implementation imperfections. In this work we present a general framework for improving parameter estimation in such settings by exploiting intrinsic structural constraints of time-domain correlation functions. Our approach builds on the observation of Kemper et al. [PRL 132, 160403 (2024)] that two-time correlation functions of Hermitian observables generate Gram matrices that are positive semidefinite, a property that can be violated in experimentally acquired data. We formulate signal reconstruction as a convex optimization problem that enforces positive semidefiniteness, Toeplitz structure, and low-rank priors motivated by the underlying dynamics. We show analytically that, under suitable conditions, the ground-truth signal can be uniquely identified in the noiseless case and recovered stably in the presence of noise. We further demonstrate numerically, in a GHZ-based magnetometry protocol, that enforcing these physical constraints can significantly improve frequency estimation from sparse and noisy data. In particular, we observe a clear advantage in the data-starved regime, where only a small number of time samples are available and standard spectral estimation methods, including matrix pencil techniques, provide limited or unstable improvement over direct fitting. While the reconstructed signals do not in general reach the shot-noise-limited performance, the proposed approach consistently reduces estimation error and recovers much of the underlying structure of the signal. These results indicate that incorporating universal physical constraints into data analysis can enhance the practical performance of quantum sensing protocols without requiring additional hardware resources or calibration.

quant-pharXiv:2608.11092•Quantum Science and Technology•Aug 12, 2026•0 citations
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.
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 a cornerstone in quantum algorithm design, allowing for the inference of eigenvalues of exponentially-large sparse matrices.The maximum rate at which these eigenvalues may be learned, –known as the Heisenberg limit–, is constrained by bounds on the circuit complexity required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation that do not require coherence between experiments have garnered interest in recent years due to lower circuit depth and minimal qubit overhead. In this work we show that these methods can achieve the Heisenberg limit, a l s o when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a `phase function' g ( k ) = ∑ j A j e i ϕ j k with unknown eigenphases ϕ j and overlaps A j at quantum cost O ( k ) , we show how to estimate the phases { ϕ j } with (root-mean-square) error δ for total quantum cost T = O ( δ − 1 ) . Our scheme combines the idea of Heisenberg-limited multi-order quantum phase estimation for a single eigenvalue phase [Higgins et al (2009) and Kimmel et al (2015)] with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem [Somma (2019)] or the matrix pencil method. For our algorithm which adaptively fixes the choice for k in g ( k ) we prove Heisenberg-limited scaling when we use the time-series/QEEP subroutine. We present numerical evidence that using the matrix pencil technique the algorithm can achieve Heisenberg-limited scaling as well.
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).
We study quantum spectrum and eigenstate property estimation using multiple initial states and generalized Hadamard tests. Building on the QFAMES (quantum filtering and analysis of multiplicities in eigenvalue spectra) framework, we introduce a new method that samples evolution times independently for each initial-state pair. Under the stated assumptions, when statistical error determines the sampling cost, the total Hamiltonian simulation cost required for fixed-accuracy eigenvalue and observable estimation is independent of the number of initial states, up to logarithmic factors. This improves scalability when many initial states are needed to explore the target eigenspaces. The method also reduces the cost of multiplicity recovery and retains Heisenberg-limited scaling for eigenvalue estimation. Numerical experiments support the predicted statistical error scalings.
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 integer-power model, where the unitary UUU is given as a black box with only integer runtime accessible, and the real-power model, where UUU is defined through a Hamiltonian HHH by $U=exp(\ensuremath{-}2\ensuremath{\pi}\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).
Quantum sensors promise measurement sensitivities that can scale at the Heisenberg limit, but in practice their performance is often degraded by noise, finite sampling, and implementation imperfections. In this work we present a general framework for improving parameter estimation in such settings by exploiting intrinsic structural constraints of time-domain correlation functions. Our approach builds on the observation of Kemper et al. [PRL 132, 160403 (2024)] that two-time correlation functions of Hermitian observables generate Gram matrices that are positive semidefinite, a property that can be violated in experimentally acquired data. We formulate signal reconstruction as a convex optimization problem that enforces positive semidefiniteness, Toeplitz structure, and low-rank priors motivated by the underlying dynamics. We show analytically that, under suitable conditions, the ground-truth signal can be uniquely identified in the noiseless case and recovered stably in the presence of noise. We further demonstrate numerically, in a GHZ-based magnetometry protocol, that enforcing these physical constraints can significantly improve frequency estimation from sparse and noisy data. In particular, we observe a clear advantage in the data-starved regime, where only a small number of time samples are available and standard spectral estimation methods, including matrix pencil techniques, provide limited or unstable improvement over direct fitting. While the reconstructed signals do not in general reach the shot-noise-limited performance, the proposed approach consistently reduces estimation error and recovers much of the underlying structure of the signal. These results indicate that incorporating universal physical constraints into data analysis can enhance the practical performance of quantum sensing protocols without requiring additional hardware resources or calibration.