REVIEW 1 major objections 4 minor 47 references
Improved Measurement Cost Scaling in the Nonorthogonal Quantum Eigensolver
T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Overlap thresholding reduces the quantum eigensolver measurement cost from cubic to linear in the number of reference states.
desk verdict A useful condition-number bound and a credible O(M) shot-count improvement, but the thresholding proof uses the exact overlap matrix while the protocol sees noise, leaving a gap that should be fixed. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the Mathias-Li eigenangle perturbation bound, which measures eigenvalue errors of a definite Hermitian pair $(H,S)$ through the generalized eigenangle $\theta_j = \tan^{-1}(1/E_j)$: the error is at most $\sin^{-1}\big(\chi \|X\|_2 / d_{\min}\big)$, where $X$ is the unit-column matrix diagonalizing $H+iS$, $\chi$ is the size of the matrix perturbation, and $d_{\min}$ is the smallest magnitude among the normalized eigenvalue pairs. The paper's key move is Lemma 1, which replaces the crude bound $\|X\|_2 \le M$ by $\|X\|_2 \le \kappa(S)$, where $\kappa(S)$ is the overlap condition number. Thresholding (Definition 1) deletes the overlap directions with eigenvalues below $\varepsilon$, and a scalable thresholding scheme (Definition 2) is one that keeps $\kappa(S_{>\varepsilon}) = \mathcal{O}(1)$ while introducing only bounded bias in the target eigenvalue. Corollary 2 then combines these ingredients to give the $\mathcal{O}(M)$ shot-count bound. The thresholding step is what converts a nearly singular overlap matrix into a well-conditioned retained one, and that conversion is what removes the cubic dimension factor from the cost.
What would settle it
Run the thresholding rule $\varepsilon_N = cM(N)$ on a strongly correlated molecular family beyond the tested hydrogen chains and rings, scanning $c$: if for every $c$ the retained condition number $\kappa(S_{>\varepsilon_N})$ grows with $N$ while the thresholding bias stays below chemical accuracy, then the $\mathcal{O}(M)$ bound does not hold for that family. A sharper check is to build the thresholding projector from the noisy measured overlap matrix rather than the exact one and test whether the retained eigenvalues or the final energy error diverge as $N$ grows.
Extended reading notes
Core claim
The discovery is a perturbation-theoretic reduction of the measurement cost of thresholded NOQE. For a definite Hermitian pair $(H,S)$, the paper proves that the sensitivity of generalized eigenvalues to finite-shot noise is controlled by $\kappa(S_{>\varepsilon})$, the condition number of the overlap matrix after removing eigenvectors whose overlap eigenvalues fall below a threshold $\varepsilon$, rather than by the worst-case dimension factor $M$. With a scalable thresholding scheme, defined as one where $\kappa(S_{>\varepsilon}) = \mathcal{O}(1)$ and the thresholding bias on the target eigenvalue stays $\mathcal{O}(1)$, the sufficient number of shots per matrix element to reach eigenangle accuracy $\mathcal{E}$ is $N_{\mathrm{shots}} = \mathcal{O}\big(M/(d_{\min,\varepsilon}^2 \mathcal{E}^2)\big) = \mathcal{O}(M/\mathcal{E}^2)$. This replaces the previously known $\mathcal{O}(M^3)$ upper bound. Numerical experiments on linear hydrogen chains and rings in a strongly correlated regime show that the retained condition number remains controlled as the number of reference states grows, while the thresholding bias does not visibly increase, and the ground-state energy error stays close to full configuration interaction.
Load-bearing premise
The entire linear shot-cost bound rests on the existence of a scalable thresholding scheme: a threshold that keeps the retained overlap matrix well-conditioned without shifting the target eigenvalue by more than a bounded amount at every system size, something the paper demonstrates numerically for hydrogen chains and rings but does not prove in general.
Editorial extensions
If this is right
- For any NOQE instance that admits a scalable thresholding scheme, the per-matrix-element shot count sufficient to reach a fixed eigenangle accuracy grows at most linearly with the number of reference states $M$, rather than cubically.
- Because the perturbation bound and thresholding machinery treat only the pair $(H,S)$, the same linear improvement carries over to any quantum subspace diagonalization method whose projected matrix elements are estimated from quantum circuits.
- For an $\eta$-scalable thresholding scheme, the final energy error is bounded by the thresholding bias $\eta$ plus a contribution proportional to the eigenangle tolerance, so the two error sources combine additively rather than multiplicatively.
- In the hydrogen-chain and hydrogen-ring families tested, the raw overlap condition number grows with $M$, but the thresholded condition number stays controlled, showing that the discarded small-overlap directions are not needed for ground-state energy accuracy.
- The numerics further suggest that for the ground state the relevant sensitivity scale is the ground state's own eigenvalue magnitude rather than the worst-case $d_{\min,\varepsilon}$, which would make the practical cost grow even more slowly than linear; the paper identifies the stronger perturbation assumption needed to prove this.
Reading between the lines
- The proof's thresholding projector is built from the exact overlap matrix, whereas a real protocol only has a noisy estimate; an extension that tracks how noise in the eigenvectors used for thresholding changes the retained subspace would be needed before the bound applies verbatim to hardware data.
- The linear scaling counts the number of reference states $M$ as the resource, but in the tested construction $M(N) = \binom{N}{\lceil N/2\rceil}$ grows exponentially with the number of atoms, so reaping the benefit in practice requires a compact reference-subspace selection rule that avoids enumerating all spin assignments.
- A natural stress test is to run the same fixed-$c$ thresholding rule $\varepsilon_N = cM(N)$ on other strongly correlated systems, such as spin defects or transition-metal clusters; if the retained condition number starts growing there while the bias stays bounded, the scalable regime is not universal.
- Using quantum amplitude estimation to reduce the per-element variance from $\mathcal{O}(1/N_{\mathrm{shots}})$ to $\mathcal{O}(1/N_{\mathrm{shots}}^2)$ would likely convert the $1/\mathcal{E}^2$ factor in the bound into $1/\mathcal{E}$ while keeping the linear dependence on $M$, a direction the paper notes but does not develop.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper analyzes the finite-shot measurement cost of the nonorthogonal quantum eigensolver (NOQE). For a projected Hamiltonian-overlap pair (H,S), it uses the Mathias-Li perturbation theory for definite generalized eigenvalue problems, proves Lemma 1 that the unit-column diagonalizing matrix X satisfies ||X||^2 <= kappa(S), and then, under a formal 'scalable thresholding scheme' (Definition 2), derives in Corollary 2 that the per-matrix-element shot count sufficient for eigenangle accuracy E is O(M/(d_min^2 E^2)) = O(M/E^2), improving on the previously known O(M^3) bound. Numerical experiments on linear hydrogen chains and rings with N=2..9 and M up to 126 show controlled thresholded condition numbers and small thresholding bias, and the paper suggests the practical cost may grow even more slowly than linear.
Significance. If the central claim holds for an implementable protocol, this is a significant improvement: it replaces a cubic dependence on the number of reference states with a linear dependence for the per-element shot budget, which directly addresses a known bottleneck of quantum subspace diagonalization. The conditional theorem is mathematically coherent: Lemma 1 is a clean and correct replacement of the dimension factor by the overlap condition number, and the proof of Corollary 2 is internally consistent under the stated definitions. The manuscript also ships reproducible code and gives a concrete noise model, which are strengths. The main weakness is that the theorem is proven for thresholding with the exact overlap matrix, while any real finite-shot protocol must threshold with a noisy overlap matrix; this gap is not analyzed and is load-bearing for the claimed O(M) scaling.
major comments (1)
- [Definition 2 / Numerical evidence] The O(M) improvement is conditional on the existence of a scalable thresholding scheme (Definition 2), and the manuscript does not prove that such a scheme exists for any nontrivial family; it offers numerical evidence only for hydrogen chains and rings with N=2..9, M(N) up to 126, and hand-chosen constants c=10^{-3}, 3x10^{-3}, 5x10^{-3} (Figure 2). The condition-number and bias plots therefore do not demonstrate the asymptotic O(1) requirements of Definition 2, and the abstract's phrase 'with a scalable thresholding scheme' could be read as an existence claim. The paper should state explicitly that the existence of scalable thresholding schemes is an empirical conjecture supported by small-system numerics, not a theorem proven here.
minor comments (4)
- [End Matter title] The End Matter section title is misspelled as 'END MA TTER' (p. 6) and should be corrected to 'END MATTER'.
- [Figure 2 caption] Figure 2's caption should specify whether the thresholding projector is built from the exact overlap matrix S or from the noisy matrix S + Delta S; this is essential for interpreting the numerical evidence in light of the proof gap described above.
- [Equation (4)] The 'with high probability' statement after Eq. (4) is informal; a tail bound specifying the failure probability would help readers assess the claimed O(M/N_shots) scaling.
- [Abstract] The abstract's phrase 'structured NOQE instances' is undefined; the numerical evidence covers only the two hydrogen families, so the scope of the empirical claim should be stated more precisely.
Circularity Check
No significant circularity: Corollary 2 is a conditional theorem whose O(M) shot bound is derived from the external Mathias-Li bound and a concentration inequality; the scalable-thresholding condition is an explicit input assumption, not the conclusion.
full rationale
The paper's central claim is a conditional theorem: Corollary 2 assumes Definition 2 (scalable thresholding) and derives N_shots = O(M/E^2) via the Mathias-Li bound (Theorem 1), Lemma 1's ||X||^2 ≤ kappa(S), and the random-matrix concentration chi = O(sqrt(M/N_shots)). The condition kappa(S_{>epsilon}) = O(1) is an input assumption, not the output; the output is a shot-count scaling that follows only after applying the external perturbation theorem and the concentration bound. No fitted constant is reused as a prediction: the numerical c values are varied and reported as evidence, and the paper explicitly labels the sublinear growth as 'suggest,' not as a derived result. The O(M^3) comparison cites [23] by the same group, but the identical bound is also attributed to [20] with independent authors, so the self-citation is not load-bearing. The unanalyzed issue that finite-shot thresholding uses eigenvectors of S + Delta S rather than exact S is a correctness/scope gap, not a circular reduction: Definition 1 and Corollary 2 explicitly define thresholding via the exact S, so the theorem does not secretly assume its own conclusion. Overall, the derivation chain is self-contained and no load-bearing step reduces to its inputs by construction.
Assumptions & free parameters
free parameters (2)
- Thresholding coefficient c in epsilon_N=cM(N) =
c = 1e-3, 3e-3, 5e-3 (per family)
- Matrix-element noise standard deviation sigma =
sigma = 1e-3 (Ha for H, dimensionless for S)
assumptions (5)
- standard math Mathias-Li perturbation theorem (Ref. [18]) bounds eigenangle error via arcsin(chi||X||^2/d_min) under chi||X||^2 < min_j beta_j.
- domain assumption Finite-shot matrix-element errors are unbiased zero-mean Gaussians with variance sigma^2 = O(1/N_shots), giving chi = O(sqrt(M/N_shots)).
- domain assumption Reference states are normalized so S has unit diagonal, giving lambda_max(S_>epsilon) >= 1.
- ad hoc to paper A scalable thresholding scheme exists (kappa(S_>epsilon)=O(1) and thresholding bias=O(1)) for the NOQE families considered.
- ad hoc to paper Thresholding is performed with eigenvectors of the exact overlap matrix S.
Cite this review
Pith. "Pith review of Improved Measurement Cost Scaling in the Nonorthogonal Quantum Eigensolver." pith.science (2026). https://pith.science/paper/U4XFZ4UU
@misc{pith2026260812830,
author = {Pith},
title = {Pith review of: Improved Measurement Cost Scaling in the Nonorthogonal Quantum Eigensolver},
year = {2026},
howpublished = {\url{https://pith.science/paper/U4XFZ4UU}},
note = {Machine review of arXiv:2608.12830}
}
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.
Figures
Reference graph
Works this paper leans on
-
[20]
G. Lee, D. Lee, and J. Huh, Quantum8, 1477 (2024)
2024
-
[23]
H. Ren, Y. Zhang, W. M. Billings, R. Tomann, N. V. Tkachenko, M. Kang, M. Head-Gordon, and K. B. Wha- ley, Physical Review Research8, 013268 (2026)
work page 2026
-
[1]
McArdle, S
S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan, Reviews of Modern Physics92, 015003 (2020)
2020
-
[2]
A. Y. Kitaev, arXiv preprint quant-ph/9511026 10.48550/arXiv.quant-ph/9511026 (1995)
-
[3]
D. S. Abrams and S. Lloyd, Physical Review Letters83, 5162 (1999)
1999
-
[4]
V. von Burg, G. H. Low, T. H¨ aner, D. S. Steiger, M. Rei- her, M. Roetteler, and M. Troyer, Physical Review Re- search3, 033055 (2021)
work page 2021
-
[5]
J. Lee, D. W. Berry, C. Gidney, W. J. Huggins, J. R. McClean, N. Wiebe, and R. Babbush, PRX Quantum2, 030305 (2021). 8
work page 2021
-
[6]
G. H. Low, R. King, D. W. Berry, Q. Han, A. E. De- Prince III, A. F. White, R. Babbush, R. D. Somma, and N. C. Rubin, Physical Review X15, 041016 (2025)
2025
Show all 47 references
-
[7]
J. R. McClean, M. E. Kimchi-Schwartz, J. Carter, and W. A. de Jong, Physical Review A95, 042308 (2017)
2017
-
[8]
J. I. Colless, V. V. Ramasesh, D. Dahlen, M. S. Blok, M. E. Kimchi-Schwartz, J. R. McClean, J. Carter, W. A. de Jong, and I. Siddiqi, Physical Review X8, 011021 (2018)
2018
-
[9]
Patel, P
S. Patel, P. Jayakumar, R. Huang, T. Zeng, and A. F. Izmaylov, Journal of Chemical Theory and Computation 22, 3937 (2026)
2026
-
[10]
N. H. Stair, R. Huang, and F. A. Evangelista, Journal of Chemical Theory and Computation16, 2236 (2020)
2020
-
[11]
C. L. Cortes, A. E. DePrince III, and S. K. Gray, Physical Review A106, 042409 (2022)
2022
-
[12]
Y. Shen, K. Klymko, J. Sud, D. B. Williams-Young, W. A. de Jong, and N. M. Tubman, Quantum7, 1066 (2023)
2023
-
[13]
Seki and S
K. Seki and S. Yunoki, PRX Quantum2, 010333 (2021)
2021
- [14]
-
[15]
T. A. Bespalova and O. Kyriienko, PRX Quantum2, 030318 (2021)
2021
-
[16]
Leimkuhler and K
O. Leimkuhler and K. B. Whaley, npj Quantum Infor- mation11, 184 (2025)
2025
-
[17]
Leimkuhler and K
O. Leimkuhler and K. B. Whaley, arXiv preprint arXiv:2503.21041 10.48550/arXiv.2503.21041 (2025)
2025 doi
-
[18]
Mathias and C.-K
R. Mathias and C.-K. Li,The definite generalized eigen- value problem: A new perturbation theory, T-NAREP No. 457 (Manchester Centre for Computational Mathematics, Manchester, UK, 2004) Oct. 2004
2004
-
[19]
E. N. Epperly, L. Lin, and Y. Nakatsukasa, SIAM Journal on Matrix Analysis and Applications43, 1263 (2022)
2022
-
[21]
Kirby, Quantum8, 1457 (2024)
W. Kirby, Quantum8, 1457 (2024)
2024
-
[22]
U. Baek, D. Hait, J. Shee, O. Leimkuhler, W. J. Huggins, T. F. Stetina, M. Head-Gordon, and K. B. Whaley, PRX Quantum4, 030307 (2023)
2023
-
[24]
Romero, R
J. Romero, R. Babbush, J. R. McClean, C. Hempel, P. J. Love, and A. Aspuru-Guzik, Quantum Science and Tech- nology4, 014008 (2018)
2018
-
[25]
J. Lee, W. J. Huggins, M. Head-Gordon, and K. B. Wha- ley, Journal of Chemical Theory and Computation15, 311 (2019)
2019
-
[26]
Matsuzawa and Y
Y. Matsuzawa and Y. Kurashige, Journal of Chemical Theory and Computation16, 944 (2020)
2020
-
[27]
N. V. Tkachenko, H. Ren, W. M. Billings, R. Tomann, K. B. Whaley, and M. Head-Gordon, Chemical Science 16, 22299 (2025)
2025
-
[28]
W. J. Huggins, J. Lee, U. Baek, B. O’Gorman, and K. B. Whaley, New Journal of Physics22, 073009 (2020)
2020
-
[29]
Vershynin, inCompressed Sensing: Theory and Appli- cations(Cambridge University Press, 2012) pp
R. Vershynin, inCompressed Sensing: Theory and Appli- cations(Cambridge University Press, 2012) pp. 210–268
2012
-
[30]
Verteletskyi, T.-C
V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov, The Jour- nal of chemical physics152, 10.1063/1.5141458 (2020)
2020 doi
-
[31]
T.-C. Yen, A. Ganeshram, and A. F. Izmaylov, npj Quan- tum Information9, 14 (2023)
2023
-
[32]
Shlosberg, A
A. Shlosberg, A. J. Jena, P. Mukhopadhyay, J. F. Haase, F. Leditzky, and L. Dellantonio, Quantum7, 906 (2023)
2023
-
[33]
W. J. Huggins, J. R. McClean, N. C. Rubin, Z. Jiang, N. Wiebe, K. B. Whaley, and R. Babbush, npj Quantum Information7, 23 (2021), arXiv:1907.13117 [quant-ph]
2021 arXiv
-
[34]
Grinko, J
D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, npj Quantum Information7, 52 (2021)
2021
- [35]
-
[36]
Q. Sun, X. Zhang, S. Banerjee, P. Bao, M. Barbry, N. S. Blunt, N. A. Bogdanov, G. H. Booth, J. Chen, Z.-H. Cui,et al., The Journal of chemical physics153, 024109 (2020)
2020
-
[37]
J. R. McClean, N. C. Rubin, K. J. Sung, I. D. Kivlichan, X. Bonet-Monroig, Y. Cao, C. Dai, E. S. Fried, C. Gid- ney, B. Gimby,et al., Quantum Science & Technology5, 034014 (2020)
2020
-
[38]
Improved Measurement Cost Scal- ing in the Nonorthogonal Quantum Eigensolver
M. Kang, Code for “Improved Measurement Cost Scal- ing in the Nonorthogonal Quantum Eigensolver”,https: //github.com/mkangquantum/noqe.git(2026), gitHub repository
2026
-
[39]
W. J. Hehre, R. F. Stewart, and J. A. Pople, The Journal of Chemical Physics51, 2657 (1969)
1969
-
[40]
Ganoe and J
B. Ganoe and J. Shee, Faraday Discussions254, 53 (2024)
2024
-
[41]
Møller and M
C. Møller and M. S. Plesset, Physical Review46, 618 (1934)
1934
-
[42]
A. J. W. Thom and M. Head-Gordon, The Journal of Chemical Physics131, 124113 (2009)
2009
-
[43]
E. J. Sundstrom and M. Head-Gordon, The Journal of Chemical Physics140, 114103 (2014)
2014
-
[44]
De Vriendt, J
X. De Vriendt, J. Bringewatt, N. O. Gjonbalaj, S. Ostermann, D. Vodola, J. Borregaard, M. K¨ uhn, and S. F. Yelin, arXiv preprint arXiv:2602.11985 10.48550/arXiv.2602.11985 (2026)
2026 doi
-
[45]
Giuliani, J
C. Giuliani, J. Nys, R. Martinazzo, G. Carleo, and R. Rossi, Nature Communications17, 5613 (2026)
2026
-
[46]
Reiher, N
M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Proceedings of the National Academy of Sci- ences114, 7555 (2017)
2017
-
[47]
A. Shee, M. Loipersberger, D. Hait, J. Lee, and M. Head- Gordon, The Journal of Chemical Physics154, 194109 (2021)
2021
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.