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.
Comments
3 figures. Code and numerical results available at https://github.com/lingwei-z/qfames-error-scaling
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.
Fine-grained spectral properties of quantum Hamiltonians, including both eigenvalues and their multiplicities, provide useful information for characterizing many-body quantum systems as well as for understanding phenomena such as topological order. Extracting such information with small additive error is #-complete in the worst case. In this work, we introduce QFAMES (quantum filtering and analysis of multiplicities in eigenvalue spectra), a quantum algorithm that efficiently identifies clusters of closely spaced dominant eigenvalues and determines their multiplicities under physically motivated assumptions, which allows us to bypass worst-case complexity barriers. QFAMES also enables the estimation of observable expectation values within targeted energy clusters, providing a powerful tool for studying quantum phase transitions and other physical properties. We validate the effectiveness of QFAMES through numerical demonstrations, including its applications to characterizing quantum phases in the transverse-field Ising model and estimating the ground-state degeneracy of a topologically ordered phase in the two-dimensional toric code model. We also generalize QFAMES to the setting of mixed initial states. Our approach offers rigorous theoretical guarantees and significant advantages over existing subspace-based quantum spectral analysis methods, particularly in terms of the sample complexity and the ability to resolve degeneracies.
Quantum phase estimation is one of the most powerful quantum primitives. This work proposes a new approach for the problem of multiple eigenvalue estimation: Quantum Multiple Eigenvalue Gaussian filtered Search (QMEGS). QMEGS leverages the Hadamard test circuit structure and only requires simple classical postprocessing. QMEGS is the first algorithm to simultaneously satisfy the following two properties: (1) It can achieve the Heisenberg-limited scaling without relying on any spectral gap assumption. (2) With a positive energy gap and additional assumptions on the initial state, QMEGS can estimate all dominant eigenvalues to ϵ accuracy utilizing a significantly reduced circuit depth compared to the standard quantum phase estimation algorithm. In the most favorable scenario, the maximal runtime can be reduced to as low as log ( 1 / ϵ ) . This implies that QMEGS serves as an efficient and versatile approach, achieving the best-known results for both gapped and gapless systems. Numerical results validate the efficiency of our proposed algorithm in various regimes.
In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty that is quantified by variance or mean squared error of measurement outcome. While the uncertainty can be reduced by averaging several samples, the number of samples should be minimized when each sample is very costly. This is especially the case for fault-tolerant quantum computing that involves measurement of multiple observables of nontrivial states in large quantum systems that exceed the capabilities of classical computers. In this work, we provide an adaptive quantum algorithm for estimating the expectation values of M general observables within root mean squared error ε simultaneously, using O ( ε − 1 M log M ) queries to a state preparation oracle of a target state. This remarkably achieves the scaling of Heisenberg limit 1 / ε , a fundamental bound on the estimation precision in terms of mean squared error, together with the sublinear scaling of the number of observables M . The proposed method is an adaptive version of the quantum gradient-estimation algorithm and has a resource-efficient implementation due to its adaptiveness. Specifically, the space overhead in the proposed method is O ( M ) , which is independent from the estimation precision ε unlike noniterative algorithms. In addition, our method can avoid the numerical instability problem for constructing quantum circuits in a large-scale task (e.g., ε ≪ 1 in our case), which appears in the actual implementation of many algorithms relying on quantum signal processing techniques. Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
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 depth required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation 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, {\em also} when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a `phase function' g(k)=∑jAjeiϕjk with unknown eigenvalue phases ϕj and probabilities Aj at quantum cost O(k), we show how to estimate the phases {ϕj} with accuracy (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 \cite{Higgins09Demonstrating,Kimmel15Robust} with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem \cite{Somma19Quantum} 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.
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.
Iterative phase estimation has long been used in quantum computing to estimate Hamiltonian eigenvalues. This is done by applying many repetitions of the same fundamental simulation circuit to an initial state, and using statistical inference to glean estimates of the eigenvalues from the resulting data. Here, we show a generalization of this framework where each of the steps in the simulation uses a different Hamiltonian. This allows the precision of the Hamiltonian to be changed as the phase estimation precision increases. Additionally, through the use of importance sampling, we can exploit knowledge about the ground state to decide how frequently each Hamiltonian term should appear in the evolution, and minimize the variance of our estimate. We rigorously show, if the Hamiltonian is gapped and the sample variance in the ground state expectation values of the Hamiltonian terms sufficiently small, that this process has a negligible impact on the resultant estimate and the success probability for phase estimation. We demonstrate this process numerically for two chemical Hamiltonians, and observe substantial reductions in the number of terms in the Hamiltonian; in one case, we even observe a reduction in the number of qubits needed for the simulation. Our results are agnostic to the particular simulation algorithm, and we expect these methods to be applicable to a range of approaches.