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

Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers

Zhiyan Ding, Lin Lin

Published Oct 11, 2023• 54 citations
arXivHTMLPDF

Abstract

We introduce a multi-modal, multi-level quantum complex exponential least squares (MM-QCELS) method to simultaneously estimate multiple eigenvalues of a quantum Hamiltonian on early fault-tolerant quantum computers. Our theoretical analysis demonstrates that the algorithm exhibits Heisenberg-limited scaling in terms of circuit depth and total cost. Notably, the proposed quantum circuit utilizes just one ancilla qubit, and with appropriate initial state conditions, it achieves significantly shorter circuit depths compared to circuits based on quantum phase estimation (QPE). Numerical results suggest that compared to QPE, the circuit depth can be reduced by around two orders of magnitude under several settings for estimating ground-state and excited-state energies of certain quantum systems.

DOI
10.22331/q-2023-10-11-1136

Related papers

Even Shorter Quantum Circuit for Phase Estimation on Early Fault-Tolerant Quantum Computers with Applications to Ground-State Energy Estimation

Zhiyan Ding, Lin Lin

We develop a phase-estimation method with a distinct feature: its maximal run time (which determines the circuit depth) is δ/ , where is the target precision, and the preconstant δ can be arbitrarily close to 0 as the initial state approaches the target eigenstate.The total cost of the algorithm satisfies the Heisenberg-limited scaling O( -1 ).As a result, our algorithm may significantly reduce the circuit depth for performing phase-estimation tasks on early fault-tolerant quantum computers.The key technique is a simple subroutine called quantum complex exponential least squares (QCELS).Our algorithm can be readily applied to reduce the circuit depth for estimating the ground-state energy of a quantum Hamiltonian, when the overlap between the initial state and the ground state is large.If this initial overlap is small, we can combine our method with the Fourier-filtering method developed in [Lin and Tong, PRX Quantum 3, 010318, 2022], and the resulting algorithm provably reduces the circuit depth in the presence of a large relative overlap compared to .The relative-overlap condition is similar to a spectral-gap assumption but it is aware of the information in the initial state and is therefore applicable to certain Hamiltonians with small spectral gaps.We observe that the circuit depth can be reduced by around 2 orders of magnitude in numerical experiments under various settings.

arXiv:2211.11973•PRX Quantum•May 26, 2023•102 citations

Heisenberg-Limited Ground-State Energy Estimation for Early Fault-Tolerant Quantum Computers

Lin Lin, Yu Tong

Under suitable assumptions, the quantum-phase-estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground-state energy.However, QPE requires a large number of ancilla qubits and a large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer.We propose an alternative method to estimate the ground-state energy of a Hamiltonian with Heisenberglimited precision scaling, which employs a simple quantum circuit with one ancilla qubit, and a classical postprocessing procedure.Besides the ground-state energy, our algorithm also produces an approximate cumulative distribution function of the spectral measure, which can be used to compute other spectral properties of the Hamiltonian.

arXiv:2102.11340•PRX Quantum•Feb 2, 2022•215 citations

Study of nuclear magnetic resonance spectra with the multi-modal multi-level quantum complex exponential least squares algorithm

A. M. Romero, Josh J. M. Kirsopp, Giuseppe Buonaiuto +1 more

We present a novel application of the multi-modal, multi-level quantum complex exponential least squares (MM-QCELS) algorithm, a state-of-the-art, early fault-tolerant quantum phase estimation (QPE) technique, to the simulation and analysis of nuclear magnetic resonance (NMR) of spin systems. By leveraging the robustness and precision of MM-QCELS, we demonstrate enhanced phase resolution in quantum simulations of spin dynamics, also in systems with complex coupling topologies. Our approach enables accurate extraction of spectral features with up to an order of magnitude fewer evaluations of the time series signal in comparison with the conventional Fourier transform, making a significant step toward scalable quantum simulations of NMR Hamiltonians. This work bridges an advanced quantum algorithm design with a practical spectroscopic application, offering a promising new approach for a quantum-based chemical analysis.

arXiv:2509.24664•Physical Chemistry Chemical Physics•Jan 1, 2026•2 citations

Ground-State Preparation and Energy Estimation on Early Fault-Tolerant Quantum Computers via Quantum Eigenvalue Transformation of Unitary Matrices

Yulong Dong, Lin Lin, Yu Tong

Under suitable assumptions, the algorithms in [Lin, Tong, Quantum 2020] can estimate the ground state energy and prepare the ground state of a quantum Hamiltonian with near-optimal query complexities. However, this is based on a block encoding input model of the Hamiltonian, whose implementation is known to require a large resource overhead. We develop a tool called quantum eigenvalue transformation of unitary matrices with real polynomials (QET-U), which uses a controlled Hamiltonian evolution as the input model, a single ancilla qubit and no multi-qubit control operations, and is thus suitable for early fault-tolerant quantum devices. This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. For a class of quantum spin Hamiltonians, we propose a new method that exploits certain anti-commutation relations and further removes the need of implementing the controlled Hamiltonian evolution. Coupled with Trotter based approximation of the Hamiltonian evolution, the resulting algorithm can be very suitable for early fault-tolerant quantum devices. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model. If we are further allowed to use multi-qubit Toffoli gates, we can then implement amplitude amplification and a new binary amplitude estimation algorithm, which increases the circuit depth but decreases the total query complexity. The resulting algorithm saturates the near-optimal complexity for ground state preparation and energy estimating using a constant number of ancilla qubits (no more than 3).

arXiv:2204.05955•PRX Quantum•Oct 12, 2022•193 citations

Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments

Thomas E. O’Brien, Brian Tarasinski, Barbara M. Terhal

Quantum phase estimation (QPE) is the workhorse behind any quantum algorithm and a promising method for determining ground state energies of strongly correlated quantum systems. Low-cost QPE techniques make use of circuits which only use a single ancilla qubit, requiring classical post-processing to extract eigenvalue details of the system. We investigate choices for phase estimation for a unitary matrix with low-depth noise-free or noisy circuits, varying both the phase estimation circuits themselves as well as the classical post-processing to determine the eigenvalue phases. We work in the scenario when the input state is not an eigenstate of the unitary matrix. We develop a new post-processing technique to extract eigenvalues from phase estimation data based on a classical time-series (or frequency) analysis and contrast this to an analysis via Bayesian methods. We calculate the variance in estimating single eigenvalues via the time-series analysis analytically, finding that it scales to first order in the number of experiments performed, and to first or second order (depending on the experiment design) in the circuit depth. Numerical simulations confirm this scaling for both estimators. We attempt to compensate for the noise with both classical post-processing techniques, finding good results in the presence of depolarizing noise, but smaller improvements in 9-qubit circuit-level simulations of superconducting qubits aimed at resolving the electronic ground state of a H 4 -molecule.

arXiv:1809.09697•New Journal of Physics•Jan 2, 2019•189 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
We introduce a multi-modal, multi-level quantum complex exponential least squares (MM-QCELS) method to simultaneously estimate multiple eigenvalues of a quantum Hamiltonian on early fault-tolerant quantum computers. Our theoretical analysis demonstrates that the algorithm exhibits Heisenberg-limited scaling in terms of circuit depth and total cost. Notably, the proposed quantum circuit utilizes just one ancilla qubit, and with appropriate initial state conditions, it achieves significantly shorter circuit depths compared to circuits based on quantum phase estimation (QPE). Numerical results suggest that compared to QPE, the circuit depth can be reduced by around two orders of magnitude under several settings for estimating ground-state and excited-state energies of certain quantum systems.
We develop a phase-estimation method with a distinct feature: its maximal run time (which determines the circuit depth) is δ/ , where is the target precision, and the preconstant δ can be arbitrarily close to 0 as the initial state approaches the target eigenstate.The total cost of the algorithm satisfies the Heisenberg-limited scaling O( -1 ).As a result, our algorithm may significantly reduce the circuit depth for performing phase-estimation tasks on early fault-tolerant quantum computers.The key technique is a simple subroutine called quantum complex exponential least squares (QCELS).Our algorithm can be readily applied to reduce the circuit depth for estimating the ground-state energy of a quantum Hamiltonian, when the overlap between the initial state and the ground state is large.If this initial overlap is small, we can combine our method with the Fourier-filtering method developed in [Lin and Tong, PRX Quantum 3, 010318, 2022], and the resulting algorithm provably reduces the circuit depth in the presence of a large relative overlap compared to .The relative-overlap condition is similar to a spectral-gap assumption but it is aware of the information in the initial state and is therefore applicable to certain Hamiltonians with small spectral gaps.We observe that the circuit depth can be reduced by around 2 orders of magnitude in numerical experiments under various settings.
Under suitable assumptions, the quantum-phase-estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground-state energy.However, QPE requires a large number of ancilla qubits and a large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer.We propose an alternative method to estimate the ground-state energy of a Hamiltonian with Heisenberglimited precision scaling, which employs a simple quantum circuit with one ancilla qubit, and a classical postprocessing procedure.Besides the ground-state energy, our algorithm also produces an approximate cumulative distribution function of the spectral measure, which can be used to compute other spectral properties of the Hamiltonian.
We present a novel application of the multi-modal, multi-level quantum complex exponential least squares (MM-QCELS) algorithm, a state-of-the-art, early fault-tolerant quantum phase estimation (QPE) technique, to the simulation and analysis of nuclear magnetic resonance (NMR) of spin systems. By leveraging the robustness and precision of MM-QCELS, we demonstrate enhanced phase resolution in quantum simulations of spin dynamics, also in systems with complex coupling topologies. Our approach enables accurate extraction of spectral features with up to an order of magnitude fewer evaluations of the time series signal in comparison with the conventional Fourier transform, making a significant step toward scalable quantum simulations of NMR Hamiltonians. This work bridges an advanced quantum algorithm design with a practical spectroscopic application, offering a promising new approach for a quantum-based chemical analysis.
Under suitable assumptions, the algorithms in [Lin, Tong, Quantum 2020] can estimate the ground state energy and prepare the ground state of a quantum Hamiltonian with near-optimal query complexities. However, this is based on a block encoding input model of the Hamiltonian, whose implementation is known to require a large resource overhead. We develop a tool called quantum eigenvalue transformation of unitary matrices with real polynomials (QET-U), which uses a controlled Hamiltonian evolution as the input model, a single ancilla qubit and no multi-qubit control operations, and is thus suitable for early fault-tolerant quantum devices. This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. For a class of quantum spin Hamiltonians, we propose a new method that exploits certain anti-commutation relations and further removes the need of implementing the controlled Hamiltonian evolution. Coupled with Trotter based approximation of the Hamiltonian evolution, the resulting algorithm can be very suitable for early fault-tolerant quantum devices. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model. If we are further allowed to use multi-qubit Toffoli gates, we can then implement amplitude amplification and a new binary amplitude estimation algorithm, which increases the circuit depth but decreases the total query complexity. The resulting algorithm saturates the near-optimal complexity for ground state preparation and energy estimating using a constant number of ancilla qubits (no more than 3).
Quantum phase estimation (QPE) is the workhorse behind any quantum algorithm and a promising method for determining ground state energies of strongly correlated quantum systems. Low-cost QPE techniques make use of circuits which only use a single ancilla qubit, requiring classical post-processing to extract eigenvalue details of the system. We investigate choices for phase estimation for a unitary matrix with low-depth noise-free or noisy circuits, varying both the phase estimation circuits themselves as well as the classical post-processing to determine the eigenvalue phases. We work in the scenario when the input state is not an eigenstate of the unitary matrix. We develop a new post-processing technique to extract eigenvalues from phase estimation data based on a classical time-series (or frequency) analysis and contrast this to an analysis via Bayesian methods. We calculate the variance in estimating single eigenvalues via the time-series analysis analytically, finding that it scales to first order in the number of experiments performed, and to first or second order (depending on the experiment design) in the circuit depth. Numerical simulations confirm this scaling for both estimators. We attempt to compensate for the noise with both classical post-processing techniques, finding good results in the presence of depolarizing noise, but smaller improvements in 9-qubit circuit-level simulations of superconducting qubits aimed at resolving the electronic ground state of a H 4 -molecule.
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.