Active Sampling Sample-based Quantum Diagonalization from Finite-Shot Measurements

1. Problem Statement

The paper addresses a critical limitation in Noisy Intermediate-Scale Quantum (NISQ) devices: the inability to perform full state tomography or obtain exact ground states due to finite-shot measurements and state preparation and measurement (SPAM) errors.

• The Constraint: Quantum devices return a finite set of bitstrings (samples) from a computational basis measurement. These samples often miss low-probability but energetically important basis states and may be contaminated by excited states (e.g., an 80% ground state / 20% first excited state mixture).
• The Failure of Existing Methods:
  • Standard Sample-based Quantum Diagonalization (SQD): Constructs a low-dimensional effective Hamiltonian using only the observed basis states. Under finite shots and contamination, the initial subspace is often biased or too small, leading to large energy estimation errors.
  • Blind Subspace Expansion: Randomly adding connected basis states to the subspace is computationally inefficient and unstable as system size grows, wasting resources on irrelevant directions in the Hilbert space.
• The Goal: Develop an algorithm that can iteratively select the most valuable additional basis states to include in the subspace to recover the true ground-state energy ($E_0$) using only the initial finite samples and the Hamiltonian definition, without requiring new quantum measurements.

2. Methodology: Active Sampling SQD (AS-SQD)

The authors propose AS-SQD, which frames subspace expansion as an active learning problem. Instead of random exploration, the algorithm uses a physics-guided acquisition function to greedily select basis states that maximize the expected improvement in the ground-state energy estimate.

Core Algorithm Steps:

1. Initialization: Start with a subspace $S$ formed by the top-$K$ most frequent bitstrings from the initial quantum samples.
2. Diagonalization: Classically diagonalize the restricted Hamiltonian $H_S$ (projected onto $S$) to obtain an approximate ground state $|\psi_S\rangle$ and energy $E_S$.
3. Candidate Generation: Identify candidate basis states $C(S)$ that are "connected" to the current subspace via the Hamiltonian (i.e., states $|k\rangle$ where $\langle k|H|s\rangle \neq 0$ for some $s \in S$).
4. Acquisition Scoring (The Innovation): Rank candidates using an Epstein–Nesbet (EN) perturbation-theoretic score.
   • The score estimates the second-order energy correction if state $|k\rangle$ were added:
     $$a(k) = \frac{|\langle k|H|\psi_S\rangle|^2}{|E_S - H_{kk}|}$$
   • Numerator: Represents the coupling strength between the candidate and the current approximate ground state.
   • Denominator: Represents the energetic detuning (difference between the candidate's diagonal energy and the current subspace energy).
5. Expansion: Add the top-$B$ candidates with the highest scores to $S$ and repeat until convergence or a budget limit is reached.

Key Technical Details:

• Sparsity Exploitation: For Pauli-string Hamiltonians, the matrix elements are sparse. The algorithm efficiently computes scores by summing only over dominant components of $|\psi_S\rangle$, avoiding exponential scaling.
• Robustness Mechanism: The acquisition function naturally down-weights states affected by SPAM errors. Noisy states typically have weak coupling to the true low-energy manifold and high diagonal energies, resulting in near-zero scores.

3. Key Contributions

1. Formulation of Active Learning for SQD: The paper reframes sample-based diagonalization as a sequential decision-making problem, moving beyond static subspace construction.
2. Perturbation-Guided Acquisition Function: Introduction of a computable, physics-based scoring rule (based on EN theory) that prioritizes basis states offering the largest expected energy lowering.
3. Demonstration of Noise Robustness: The method is shown to be inherently robust against SPAM errors and excited-state contamination without needing external error mitigation techniques (like zero-noise extrapolation).
4. Hardware Validation: Successful execution on real IBM Quantum hardware, demonstrating the ability to filter physical noise and recover exact ground states.

4. Experimental Results

The authors evaluated AS-SQD on Disordered Heisenberg and Transverse-Field Ising (TFIM) spin chains up to 16 qubits (Hilbert space dimension $2^{16} = 65,536$).

• Simulation (Contaminated Sampling):
  • Setup: Simulated 80% ground state / 20% excited state mixture with finite shots ($N_{shots}=2000-3000$).
  • Performance: AS-SQD consistently achieved significantly lower median absolute energy errors compared to Standard SQD and Random SQD.
  • Scaling: While Standard SQD errors grew rapidly with system size ($n$), AS-SQD maintained high accuracy even at $n=16$. Random expansion showed limited improvement due to poor sample efficiency.
• Hardware Validation (IBM Quantum):
  • Setup: Samples generated directly from the ibmq_pittsburgh processor, suffering from gate infidelities and decoherence.
  • Result: At $n=8$, AS-SQD converged to the exact ground state (error $\sim 10^{-14}$), effectively filtering out the hardware noise that populated irrelevant basis states. It outperformed baselines across all tested hardware sizes.
• Ablation Studies:
  • Coupling vs. Energy: The "coupling-only" heuristic ($|\langle k|H|\psi_S\rangle|^2$) performed nearly as well as the full EN score, indicating that coupling strength is the dominant factor. However, the full score provided optimal balance.
  • Horizon Effect: Limiting candidate generation to 1-hop (immediate neighbors) was found to be superior to 2-hop expansions. The 1-hop restriction acted as a beneficial inductive bias, preventing the candidate pool from exploding and forcing the algorithm to focus on the most immediate, high-impact directions.

5. Significance and Conclusion

• Bypassing Combinatorial Bottlenecks: AS-SQD successfully navigates the exponential complexity of the Hilbert space by concentrating computational resources on energetically relevant directions, avoiding the need for exhaustive Hamiltonian measurement.
• NISQ Readiness: The method is specifically designed for the constraints of current quantum hardware (finite shots, noise, no full state access), making it a practical tool for near-term quantum advantage.
• General Principle: The paper establishes a paradigm for "Quantum AI" in the NISQ era: using physics-derived acquisition functions to intelligently decide what information to incorporate next, rather than relying on brute-force sampling or random exploration.

In summary, AS-SQD provides a robust, scalable, and efficient framework for estimating ground-state energies from imperfect quantum data, bridging the gap between noisy experimental outputs and accurate physical predictions.