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

• URL: http://arxiv.org/abs/2507.12438v1
• Date: Wed, 16 Jul 2025 17:27:01 GMT
• Title: Heisenberg limited multiple eigenvalue estimation via off-the-grid compressed sensing
• Authors: Davide Castaldo, Stefano Corni,
• Abstract summary: Quantum phase estimation is the flagship algorithm for quantum simulation on fault-tolerant quantum computers.<n>We demonstrate that an emphoff-grid compressed sensing protocol, combined with a state-of-the-art signal classification method, enables the simultaneous estimation of multiple eigenvalues.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\epsilon$-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.

Related papers

• Pulse-based optimization of quantum many-body states with Rydberg atoms in optical tweezer arrays [39.58317527488534]
  We explore a pulse-based variational quantum eigensolver algorithm for Rydberg atoms in optical tweezer arrays.<n>We numerically demonstrate that the ground states of the one-dimensional antiferromagnetic Heisenberg model and the mixed-field Ising model can be accurately prepared.
  arXiv  Detail & Related papers  (2025-07-25T10:51:49Z)
• Quantum block Krylov subspace projector algorithm for computing low-lying eigenenergies [0.0]
  QBKSP is a multireference quantum Lanczos method designed to accurately compute low-lying eigenenergies, including degenerate ones, of quantum systems.<n>We present three compact quantum circuits tailored to different problem settings for evaluating the required expectation values.
  arXiv  Detail & Related papers  (2025-06-11T17:47:22Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition.<n>We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation [39.20075231137991]
  We investigate the feasibility of early fault-tolerant quantum algorithms focusing on ground-state energy estimation problems.<n> scaling these methods to larger system sizes reveals three key challenges: the smoothness of the CDF for large supports, the lack of tight lower bounds on the overlap with the true ground state, and the difficulty of preparing high-quality initial states.
  arXiv  Detail & Related papers  (2024-05-06T18:00:03Z)
• Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method [13.34671442890838]
  This work proposes a new approach for the problem of multiple eigenvalue estimation: Quantum Multiple Eigenvalue Gaussian filtered Search (QMEGS) QMEGS is the first algorithm to simultaneously satisfy the Heisenberg-limited scaling without relying on any spectral gap assumption. Numerical results validate the efficiency of our proposed algorithm in various regimes.
  arXiv  Detail & Related papers  (2024-02-01T20:55:11Z)
• Quantum Phase Estimation by Compressed Sensing [0.0]
  We present a new Heisenberg-limited quantum phase estimation algorithm for early quantum computers based on compressed sensing.<n>Our algorithm is able to recover the frequency with a total runtime $mathcalO(epsilon-1textpolylog(epsilon-1))$, where $epsilon$ is the accuracy.<n>We also consider the more general quantum eigenvalue estimation problem (QEEP) and show numerically that the off-grid compressed sensing can be a strong candidate for solving the QEEP.
  arXiv  Detail & Related papers  (2023-06-12T10:21:59Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Dual-Frequency Quantum Phase Estimation Mitigates the Spectral Leakage of Quantum Algorithms [76.15799379604898]
  Quantum phase estimation suffers from spectral leakage when the reciprocal of the record length is not an integer multiple of the unknown phase. We propose a dual-frequency estimator, which approaches the Cramer-Rao bound, when multiple samples are available.
  arXiv  Detail & Related papers  (2022-01-23T17:20:34Z)
• Variational Quantum Algorithms for Trace Distance and Fidelity Estimation [7.247285982078057]
  We introduce hybrid quantum-classical algorithms for two distance measures on near-term quantum devices. First, we introduce the Variational Trace Distance Estimation (VTDE) algorithm. Second, we introduce the Variational Fidelity Estimation (VFE) algorithm.
  arXiv  Detail & Related papers  (2020-12-10T15:56:58Z)
• An Ensemble Approach for Compressive Sensing with Quantum [1.8477401359673713]
  We leverage the idea of a statistical ensemble to improve the quality of quantum annealing based binary compressive sensing. Our experiments, on a D-Wave 2000Q quantum processor, demonstrated that the proposed ensemble scheme is notably less sensitive to the calibration of the penalty parameter.
  arXiv  Detail & Related papers  (2020-06-08T15:32:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.