⚛️ quantum physics

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

This paper introduces a quantum spectral estimation method leveraging multiple initial states and independent evolution time sampling within the QFAMES framework, which achieves fixed-accuracy eigenvalue and observable estimation with a total Hamiltonian simulation cost that is independent of the number of initial states (up to logarithmic factors) while maintaining Heisenberg-limited scaling.

Original authors: Lingwei Zhang, Zhiyan Ding

Published 2026-10-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lingwei Zhang, Zhiyan Ding

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quantum world, the behavior of matter is dictated by a mathematical object called a Hamiltonian. One can think of this as a master blueprint that determines the possible energy levels a system can hold, much like the specific notes a musical instrument is capable of playing. To understand how a quantum system works, whether it is a molecule in a chemical reaction or a material exhibiting exotic magnetic properties, scientists must first read this blueprint. They need to know not just what the energy levels are, but also how many distinct states exist at each level and what physical properties those states possess. This process is known as spectral estimation. It is a fundamental task in physics and chemistry, yet it is notoriously difficult because the number of possible states grows explosively as the system gets larger, making it impossible to check every possibility one by one.

To solve this, researchers have developed algorithms that use quantum computers to probe these energy levels. A recent method, known as QFAMES, allows scientists to extract this information by preparing a collection of starting states and observing how they evolve over time. The method works by measuring how these starting states overlap with the system's true energy states. However, a significant bottleneck has emerged: to ensure the algorithm finds all the relevant energy levels, especially in complex systems with many identical or nearly identical states, scientists often need to use a very large number of different starting states. In the original version of the algorithm, increasing the number of starting states to improve accuracy came at a steep price. Every time a new starting state was added, the total amount of time the quantum computer needed to run increased proportionally to the product of the number of starting state pairs, quickly making the process too expensive to be practical for large-scale problems.

In a new study, researchers Lingwei Zhang and Zhiyan Ding have proposed a way to break this bottleneck. They introduced a modified strategy for how the algorithm gathers its data. Instead of using the same set of time measurements for every pair of starting states, their new method samples the evolution times independently for each pair. This change might seem minor, but it fundamentally alters how errors behave as the number of starting states grows. By treating each measurement pair as an independent source of information, the statistical noise inherent in the quantum measurements begins to cancel itself out more effectively as more states are added. The researchers demonstrated that under this new scheme, the total time required to achieve a fixed level of accuracy no longer depends on the number of starting states used for estimating energy levels and physical properties, provided that number is not excessively large.

The paper presents rigorous mathematical proofs and numerical simulations to support this claim. For the task of estimating the energy levels themselves, the authors show that the cost of the simulation becomes independent of the number of initial states, up to very small logarithmic factors. This means that a scientist can use a large library of starting states to thoroughly explore a complex quantum system without paying a proportional penalty in computing time. The same improvement extends to estimating the properties of the system, such as the values of physical observables within a specific energy level, particularly when the number of left and right starting states are equal and the desired error is sufficiently small. In these cases, the total simulation time required to reach a desired precision remains constant even as the number of starting states increases, a stark contrast to the original method where the cost would rise linearly with the number of pairs.

The study also addresses the challenge of determining the multiplicity of energy levels, which refers to counting how many distinct states share the same energy value. This is crucial for identifying quantum phases of matter. The original algorithm's cost for this task grew with the product of the number of starting states. The new method reduces this dependence significantly, making the cost grow only linearly with the larger of the two sets of starting states used, rather than their product. This improvement is particularly valuable for systems where many starting states are required to ensure that the entire relevant space of possibilities is covered. The researchers verified these theoretical predictions through numerical experiments, which showed that the error in their estimates decreased as expected when more starting states were added, confirming that the independent sampling strategy successfully mitigates the statistical noise that previously limited the algorithm's scalability.

By decoupling the computational cost from the number of starting states for energy and property estimation, and significantly reducing the scaling for multiplicity counting, this work opens the door to more robust and efficient spectral analysis of complex quantum systems. It suggests that researchers can now afford to use richer collections of initial states to probe difficult problems, such as those involving degenerate energy levels or topological order, without hitting a wall of computational expense. The findings offer a practical path forward for quantum algorithms that rely on multiple initial states, ensuring that the promise of quantum simulation can be realized for the large, intricate systems that are most interesting to physicists and chemists.

Technical Summary: Quantum Spectral Estimation with Multiple Initial States

Problem Statement

The paper addresses the challenge of characterizing the spectrum and eigenstate properties of a Hamiltonian $H$ using quantum algorithms. Specifically, it focuses on two fundamental tasks:

Density-of-Dominant-Eigenstates (DODS) Estimation: Estimating the dominant eigenvalues $\{\lambda_m\}$ and their multiplicities (including near-degenerate clusters).
Degenerate Eigenstate Property Estimation: Estimating the expectation values of observables restricted to these dominant (possibly degenerate) eigenspaces.

While the recently proposed QFAMES (Quantum Filtering and Analysis of Multiplicities in Eigenvalue Spectra) framework can efficiently solve these problems, its resource scaling with respect to the number of initial states ( $L$ and $R$ ) is suboptimal. In the original QFAMES algorithm, the total Hamiltonian simulation cost scales linearly with the product $LR$ . This creates a bottleneck because a large collection of initial states is often required to ensure sufficient overlap with target eigenspaces, particularly for degenerate or nearly degenerate systems. The authors ask whether a more efficient algorithm can be designed to improve the scaling with respect to $L$ and $R$ .

Methodology

The authors propose a modification to the data generation strategy within the QFAMES framework, introducing Independent Time Sampling as an alternative to the original Shared Time Sampling.

Core Framework (QFAMES)

The algorithm relies on constructing a filtered data matrix $G(\theta)$ that approximates the ideal signal $F(\theta)$ , defined as:
$F(\theta) = \Phi \cdot \text{diag}\left(\{e^{-(\theta-\lambda_m)^2 T^2}\}_{m}\right) \cdot \Psi^\dagger$
where $\Phi$ and $\Psi$ are overlap matrices between the initial states and the exact eigenstates, and $T$ is a filter time scale. The matrix entries are estimated via generalized Hadamard tests using time-evolved correlations $\langle \phi_l | e^{-iHt} | \psi_r \rangle$ .

The Innovation: Independent Time Sampling

Shared Time Sampling (Original): The Hamiltonian evolution times $\{t_n\}_{n=1}^N$ are sampled once and shared across all initial-state pairs $(l, r)$ . Consequently, statistical fluctuations in the matrix entries are correlated.
Independent Time Sampling (Proposed): Evolution times $\{t_{l,r,n}\}_{n=1}^N$ are sampled independently for each initial-state pair $(l, r)$ .

This change alters the statistical properties of the error matrix $E(\theta) = G(\theta) - F(\theta)$ . Under independent sampling, the statistical errors across different matrix entries become uncorrelated, allowing them to average out more effectively as $L$ and $R$ increase.

Key Contributions and Theoretical Results

The paper establishes rigorous theoretical guarantees showing that independent sampling significantly improves the error and cost scaling compared to shared sampling, under specific structural assumptions (Cluster Separation, Dominant Signal, and Uniform Overlap).

1. Eigenvalue Estimation Scaling

Shared Sampling: The total simulation time $T_{\text{total}}$ required for $\epsilon$ -accuracy scales as $\tilde{O}(LR / (\bar{p}_{\text{tail}} \bar{p}_{\text{min}} \epsilon))$ .
Independent Sampling: The scaling improves to $\tilde{O}\left(\max\left(\frac{1}{\bar{p}_{\text{tail}} \bar{p}_{\text{min}} \epsilon}, \frac{\sqrt{LR}}{\bar{p}_{\text{min}}^2 \epsilon}, \frac{LR \bar{p}_{\text{tail}}}{\bar{p}_{\text{min}} \epsilon}\right)\right)$ .
Significance: In the practically relevant regime where the number of initial states is not excessively large (specifically $\sqrt{LR} \lesssim \bar{p}_{\text{min}}/\bar{p}_{\text{tail}}$ ), the total cost becomes independent of $L$ and $R$ (up to logarithmic factors). The statistical error scales as $1/\sqrt{LRN}$ , allowing the number of samples $N$ per pair to decrease as more pairs are added.

2. Multiplicity Recovery

Shared Sampling: The cost scales as $\tilde{O}(LR / (\bar{p}_{\text{min}}^2 \Delta))$ . Correlated noise prevents the signal-to-noise ratio from improving with more states.
Independent Sampling: The cost scales as $\tilde{O}(\max(L, R) / (\bar{p}_{\text{min}}^2 \Delta))$ .
Significance: The dependence on $LR$ is reduced to $\max(L, R)$ . Independent sampling allows the statistical perturbations to grow more slowly than the target signal, enabling better separation of singular values for multiplicity determination.

3. Observable Estimation

Shared Sampling: The cost scales as $\tilde{O}(LR \|O\|_2^2 / (\epsilon_O^2 \Delta))$ .
Independent Sampling: In the idealized regime ( $L=R$ , no tail support, exact degeneracy), the cost scales as $\tilde{O}(\|O\|_2^2 / (\epsilon_O^2 \Delta))$ , becoming independent of $L$ and $R$ .
Significance: Similar to eigenvalue estimation, the statistical error in observable estimation scales as $1/\sqrt{LRN}$ , decoupling the total cost from the number of initial states in the appropriate parameter regime.

Numerical Results

The authors provide numerical experiments on toy models to validate the theoretical scalings:

Eigenvalue Error: Plots show that under independent sampling, the error decays approximately as $L^{-1}$ (consistent with $1/\sqrt{LRN}$ ) before saturating due to bias, whereas shared sampling approaches an $L$ -independent error floor.
Multiplicity Recovery: Singular value analysis demonstrates that under independent sampling, non-target singular values decrease as $L$ increases, widening the gap for threshold selection. Under shared sampling, non-target singular values remain at an $L$ -independent level due to correlated fluctuations.
Observable Error: Similar to eigenvalues, independent sampling exhibits $L^{-1}$ error decay, while shared sampling retains a constant error level.

Significance and Claims

The paper claims that by simply changing the time-sampling strategy from shared to independent, the QFAMES framework can achieve:

Improved Scalability: The total Hamiltonian simulation cost for fixed-accuracy eigenvalue and observable estimation can be made independent of the number of initial states.
Resource Efficiency: A larger collection of initial states, which is often necessary to explore target eigenspaces (especially degenerate ones), no longer incurs a proportional increase in total simulation time. Instead, it allows for fewer samples per state pair.
Enhanced Multiplicity Recovery: The method reduces the overhead for recovering exact multiplicities from $O(LR)$ to $O(\max(L, R))$ .

The authors note that these improvements are particularly relevant for applications requiring many initial states, such as resolving ground-state degeneracies in topological models or using multireference methods in quantum chemistry. They conclude that while the theoretical bounds are established, further numerical studies on physical models are needed to assess practical utility. The paper does not claim to solve the general spectral estimation problem without assumptions but specifically targets the scaling bottleneck associated with the number of initial states within the QFAMES framework.