Improved Measurement Cost Scaling in the Nonorthogonal Quantum Eigensolver

AI summary

Overview

Research area: Quantum algorithms for quantum chemistry — specifically quantum subspace diagonalization methods and the nonorthogonal quantum eigensolver (NOQE), analyzed through matrix perturbation theory and numerical electronic-structure simulation.

Technical level: Advanced. The paper combines finite-shot perturbation bounds for generalized eigenvalue problems, overlap-matrix condition numbers, and thresholding schemes with STO-3G hydrogen-chain and hydrogen-ring numerics.

Scope (one sentence): The paper proves that, with a properly chosen overlap-thresholding scheme, the number of shots per matrix element needed by NOQE to reach a target accuracy scales as 𝒪(M) in the number M of reference states instead of the previously known 𝒪(M³), and supports this with hydrogen-chain and hydrogen-ring simulations.

What This Paper Is About

Quantum subspace diagonalization methods estimate molecular energies using shallow quantum circuits, but they require many circuit repetitions to estimate the entries of the projected Hamiltonian and overlap matrices. Because the classical step solves a generalized eigenvalue problem, small errors in those matrix elements can be amplified into much larger eigenvalue errors when the overlap matrix is ill-conditioned. This paper asks how many shots per matrix element NOQE really needs, and shows that thresholding the overlap matrix replaces a pessimistic worst-case dimension factor with the condition number of the retained overlap matrix, lowering the shot-cost bound from 𝒪(M³) to 𝒪(M).

Key Contributions

1. A finite-shot perturbation framework for thresholded NOQE. The authors model finite-shot errors Δ𝐇 and Δ𝐒 as zero-mean Gaussian random matrices with variance σ² = 𝒪(1/N_shots), use random-matrix concentration to obtain χ = 𝒪(√(M/N_shots)) for the perturbation size, and analyze the perturbed generalized eigenvalue problem in the Mathias–Li geometric (eigenangle) formulation.

2. Lemma 1: an overlap condition-number bound. They prove that the unit-column diagonalizing matrix X of the Mathias–Li formulation satisfies ‖X‖² ≤ κ(𝐒) = λ_max(𝐒)/λ_min(𝐒), replacing the worst-case dimension bound ‖X‖² ≤ M that is the source of the cubic scaling.

3. Formal definitions of thresholding. They define a thresholding scheme (discarding overlap eigen-directions with eigenvalue below ε) and a scalable (and η-scalable) thresholding scheme, requiring κ(𝐒_{>ε_N}) = 𝒪(1) and a thresholding bias |E_{j,>ε_N}^{(N)} − E_j^{(N)}| = 𝒪(1) uniformly in system size N.

4. Corollary 2: the improved per-element shot cost. Under a scalable thresholding scheme, the sufficient shot count per matrix element is N_shots = 𝒪(M/(d²_{min,>ε} ℰ²)) = 𝒪(M/ℰ²), with an explicit total error bound combining thresholding bias and finite-shot error.

5. Numerical evidence on hydrogen chains and rings. Simulations using PySCF for integrals and OpenFermion for second-quantized Hamiltonians (code publicly available) show that a scalable thresholding scheme exists for these systems and that the practical cost may grow even more slowly than the linear bound.

Main Findings

• The previous best bound was cubic. Combining the Mathias–Li eigenangle bound with the random-matrix scaling gives N_shots = 𝒪(M³/(d_min² ℰ²)) (Corollary 1), because the analysis only uses ‖X‖² ≤ Tr(X†X) = M.
• Conditioning replaces dimension. Lemma 1 establishes ‖X‖² ≤ κ(𝐒), so under scalable thresholding the bound becomes N_shots = 𝒪(M/(d²_{min,>ε} ℰ²)) = 𝒪(M/ℰ²), provided the validity condition χ κ(𝐒_{>ε}) < ε holds.
• Explicit combined error. If the scheme is η-scalable, the finite-shot retained-pair energy deviates from the unthresholded eigenvalue by at most η + √((1+E²_{j,>ε})(1+Ẽ²_{j,>ε})) ℰ; the multiplicative factor can be made 𝒪(1) by rescaling (𝐇, 𝐒) → (𝐇/α, 𝐒) with α ≥ ‖Ĥ‖, e.g. the Pauli coefficient 1-norm.
• Noiseless NOQE is accurate and spin-purified. Across the tested hydrogen chains and rings (STO-3G, nearest-neighbor distance 1.5 Å), NOQE stays close to FCI and improves over NOCI by roughly a factor of three, with substantially smaller spin contamination ⟨Ŝ²⟩ − S(S+1) than NOCI.
• Bare overlap matrices are ill-conditioned. Before thresholding, κ(𝐒) increases with system size for both NOCI and NOQE, with NOQE slightly more ill-conditioned, for M(N) = binom(N, ⌈N/2⌉) reference states.
• Thresholding controls both requirements. With ε_N = cM(N), using c = 3×10⁻³ for hydrogen chains and c = 5×10⁻³ for hydrogen rings (also tested: c = 10⁻³), the thresholded condition number κ(𝐒_{>ε_N}) stays controlled and the bias relative to the noiseless unthresholded NOQE energy does not grow with N over the tested range; spin contamination also remains small after thresholding.
• Practice beats the proven bound. With σ = 10⁻³ (Ha for diagonal 𝐇 entries, and σ = 10⁻³/√2 per real and imaginary part for off-diagonal 𝐇 and 𝐒 entries, averaged over 300 noise realizations), both the sampling standard deviation and the bias remain bounded as N grows, suggesting measurement cost may grow more slowly than 𝒪(M).
• Why the gap exists (heuristic). The bound is governed by the worst-case d_min,>ε, but ground-state sensitivity is set by its own d_{0,>ε} = |α_{0,>ε} + iβ_{0,>ε}|, which grows extensively with N because α_{0,>ε}/β_{0,>ε} is the ground-state energy and β_{0,>ε} ≥ λ_min(𝐒_{>ε}) = Ω(1). Proving a bound with d_{0,>ε} would require a stronger assumption: the perturbation must be small enough that no less robust eigenvalue crosses the ground state.
• Scope caveats stated by the authors. The analysis tracks scaling with M only; Hamiltonian- and grouping-dependent prefactors (Pauli-word grouping or basis-rotation grouping) and additional system-size-dependent measurement overheads are not modeled. Iterative quantum amplitude estimation would give σ² = 𝒪(1/N²_shots) when N_shots counts coherent oracle queries.

Methodology in Plain English

The authors build the NOQE subspace from unrestricted Hartree–Fock (UHF) states obtained by starting self-consistent-field calculations from localized spin patterns on the hydrogen sites. In the spin sector m_s = 0 (1) for even (odd) N, this yields N_α = ⌈N/2⌉ spin-up sites and M(N) = binom(N, ⌈N/2⌉) reference states. Each UHF state is then "dressed" by a shallow correlating operator using classically supplied coupled-cluster amplitudes (the coupled-cluster operator with MP2 amplitudes), so the UHF states carry static correlation and the dressing adds dynamic correlation.

On the quantum side, the Hamiltonian and overlap matrix elements between these nonorthogonal dressed states are estimated with a modified-Hadamard-test protocol using two N_SO-qubit registers and one control qubit (a single-register variant is possible at roughly double the circuit depth), including orbital-basis rotations that map the different UHF orbital bases to a common qubit representation. In this STO-3G setting N_SO = N.

To study the effect of finite sampling, the authors add random perturbations to the exact projected matrices, drawn as zero-mean Gaussian noise matching the statistics of shot noise, then threshold the overlap matrix by discarding eigen-directions with eigenvalue below ε, and finally solve the small generalized eigenvalue problem classically. The error analysis is done in the Mathias–Li geometric picture, where each generalized eigenvalue is a point (α_j, β_j) with eigenangle θ_j = tan⁻¹(1/E_j), so that perturbation bounds become statements about how much these angles can rotate. The numerics average 300 random noise realizations per system.

Why This Matters

Subspace diagonalization methods are among the most plausible routes to useful quantum chemistry on near-term and early fault-tolerant hardware, but their measurement cost has been a serious practical objection: if shot counts grew cubically with subspace size, many chemically interesting systems would be out of reach. Showing that a properly thresholded scheme needs only linearly growing per-element shot counts — and that real hydrogen systems behave even better — substantially lowers the resource estimates for this class of algorithms. The result applies to any quantum subspace diagonalization method whose matrix elements are estimated from quantum circuits, not just NOQE.

Real-world applications implied by the paper:

• Strongly correlated molecular energetics, where unrestricted spin-symmetry-broken determinants provide a compact multireference starting point, such as the hydrogen chains and rings used here.
• Spin-state energetics in transition-metal clusters, explicitly named by the authors as a motivating target for quantum computation.
• Multireference chemistry more broadly, where static and dynamic correlation must be captured simultaneously and single-reference methods fail.
• Benchmarking and resource estimation for quantum-chemistry algorithms on early fault-tolerant devices, since the bound is phrased in terms of shots per matrix element and target accuracy.

Industry relevance: the work informs hardware and algorithm roadmaps for quantum-chemistry applications, because it converts a subspace-size scaling question into a concrete circuit-repetition budget. The paper does not report industrial benchmarks, dollar costs, or hardware demonstrations; all results are theoretical bounds plus classical numerical simulation.

Future Directions

• Prove the sharper bound. Replacing d_min,>ε with the individual d_{0,>ε} in the shot-cost formula would justify the sublinear-in-M behavior seen numerically, but requires a stronger validity assumption ensuring that no less robust retained eigenvalue crosses the ground-state eigenvalue.
• Design better thresholding schemes. The threshold must balance improved conditioning against the bias from discarding overlap directions; a systematic theory for choosing ε_N (beyond the tested ε_N = cM(N) with c = 10⁻³, 3×10⁻³, 5×10⁻³) is left open.
• Shrink the subspace before thresholding. Constructing compact multireference subspaces that preserve ground-state accuracy would reduce M itself, which the authors identify as a complementary and active research direction, since the present M(N) = binom(N, ⌈N/2⌉) grows exponentially with N.
• Extend and refine the cost model. Incorporation of Hamiltonian-dependent prefactors, Pauli-word or basis-rotation grouping overheads, and possible Heisenberg scaling from iterative quantum amplitude estimation remain outside the present analysis, as does testing beyond hydrogen chains and rings.

Target Audience

Quantum-algorithm researchers working on near-term and early fault-tolerant quantum chemistry; quantum-chemistry method developers interested in multireference and nonorthogonal approaches; and resource-estimation specialists who need rigorous shot-count bounds for subspace diagonalization algorithms. Readers should be comfortable with generalized eigenvalue problems, matrix condition numbers, and second-quantized electronic-structure notation; the numerical sections are accessible to computational chemists familiar with UHF, NOCI, MP2, and FCI comparisons.

Authors’ abstract

Quantum subspace diagonalization methods are promising algorithms for quantum chemistry on near-term quantum computers. These methods can estimate low-lying energies of molecular systems using shallow quantum circuits, at the cost of many circuit repetitions to estimate the projected matrix elements. Errors in these matrix elements can be converted into much larger eigenvalue errors by an ill-conditioned overlap matrix. We study this bottleneck for the nonorthogonal quantum eigensolver (NOQE), which constructs a compact multireference subspace from dressed unrestricted Hartree-Fock states. We prove a finite-shot perturbation bound showing that, after overlap thresholding, the eigenvalue sensitivity is controlled by the condition number of the retained overlap matrix rather than by a worst-case dimension factor. With a scalable thresholding scheme, the upper bound on the per-matrix-element shot count required to reach a target accuracy scales as $\mathcal{O}(M)$, improving on the previously known $\mathcal{O}(M^3)$ bound, where $M$ is the number of reference states. Numerical experiments on hydrogen chains and rings suggest that, in practice, the measurement cost of structured NOQE instances can grow even more slowly than this linear bound.