{"id":"7e10ee03-a6df-44ad-b27b-172a3564ebe4","arxiv_id":"2608.12830","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For thresholded NOQE, the per-matrix-element shot count needed for a target accuracy drops from O(M^3) to O(M).","lead":"This paper proves that, after overlap thresholding, the number of measurements needed per matrix element in the nonorthogonal quantum eigensolver scales linearly with the subspace size M instead of cubically. The result lowers a key resource estimate for near-term quantum chemistry simulations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 2's proof thresholds with eigenvectors of the exact S, while the finite-shot protocol must threshold with noisy S+ΔS; the unanalyzed subspace perturbation can break the O(M) shot bound.","rationale":"The strongest claim, Corollary 2, is a conditional statement: under a scalable thresholding scheme, the per-element shot count is O(M/E²). The derivation from Theorem 1 and Lemma 1 is mathematically sound for a thresholded pair built from the exact overlap matrix. The load-bearing gap is the transition from this idealized thresholded pair to the actual finite-shot protocol, where only S+ΔS is known and the retained subspace itself becomes data-dependent. The manuscript explicitly limits Def. 2's bias to the noiseless thresholded pair, which confirms that the noisy-thresholding effect is outside the proven bound. This concern does not invalidate the conditional theorem, but it narrows the practical claim: without an additional analysis of the subspace error or a proof that a spectral gap protects the retained subspace, the O(M) scaling cannot be claimed for the implementable algorithm. The reader's conditional verdict already captures this fragility, so no verdict change is needed. The proposed numerical test directly separates the idealized and implementable protocols and would reveal whether the missing term is benign or destructive.","tokens_in":11750,"tokens_out":7124,"duration_ms":77756,"concrete_test":"Re-run the public NOQE code with the Fig. 2 noise model for N=2..9 and each c, using two thresholding rules: (a) eigenvectors of the exact S (the proof's assumption) and (b) eigenvectors of the measured S̃ = S+ΔS, with identical ε_N = cM(N). Compare the ground-state bias and sample standard deviation against the noiseless thresholded energy. If rule (b) shows additional error that grows with M/σ or is not uniformly bounded, Corollary 2 does not bound the implementable protocol; also tabulate min |λ_retained − λ_discarded| near ε to test whether a Davis–Kahan gap factor is the missing correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The conditional theorem is internally coherent, but it does not cover the protocol it is meant to analyze. In Def. 1 and the End Matter proof of Corollary 2, the retained pair (8) is built from V_>ε, the exact eigenvectors of S, and the perturbed retained pair is written as V†_>ε(H+ΔH)V_>ε. This lets the proof pass the perturbation through unchanged (||ΔH_>ε|| ≤ ||ΔH||). In any finite-shot implementation, only S̃ = S+ΔS is available, so the projector is instead Ṽ_>ε from S̃. The actual retained pair is Ṽ†_>ε(H+ΔH)Ṽ_>ε, and its deviation from the noiseless retained pair contains Ṽ−V terms. Those are governed by the spectral gap of S around ε (Davis–Kahan), not by χ; if any retained eigenvalue lies near ε, the retained subspace can change discontinuously. This extra subspace error is absent from the quantity χκ(S_>ε) that Corollary 2 bounds, and Def. 2's bias condition (9) applies only to the noiseless thresholded pair, as the text itself emphasizes. The numerics in Fig. 2 do not settle the point, since the caption does not say whether thresholding is applied using eigenvectors of S or of S+ΔS.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12020,"tokens_out":9706,"duration_ms":97572,"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":[{"comment":"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.","section":"Definition 2 / Numerical evidence"}],"minor_comments":[{"comment":"The End Matter section title is misspelled as 'END MA TTER' (p. 6) and should be corrected to 'END MATTER'.","section":"End Matter title"},{"comment":"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.","section":"Figure 2 caption"},{"comment":"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.","section":"Equation (4)"},{"comment":"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.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The decisive issue is the mismatch between thresholding with the exact overlap matrix in the proof and thresholding with a noisy overlap matrix in any finite-shot implementation. If the authors can either close this gap with a Davis-Kahan-type subspace perturbation analysis or clearly restrict the claim to idealized exact-S thresholding, the paper would be publishable; the conditional theorem and numerical evidence are otherwise valuable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: the paper has a real idea. Lemma 1 replaces the crude dimension bound ||X||^2 ≤ M in the Mathias-Li perturbation theory with ||X||^2 ≤ κ(S), where κ is the overlap condition number. That is one clean observation, and it is what lets the paper claim O(M) per-matrix-element shot count under thresholding, instead of the O(M^3) bound from [20,23]. I verified the proof of Lemma 1; it is short and correct. Corollary 2's algebra checks out under its stated definitions. The numerics on hydrogen chains and rings, with public code, support the claim that practical thresholding can keep the retained condition number controlled while the bias stays flat.\n\nThe soft spot is exactly the one the stress-test flags. The theory thresholds using the exact overlap matrix S: in Def. 1 and the proof of Corollary 2, the retained pair is built from V_>ε, the eigenvectors of S. A finite-shot protocol only has S+ΔS, so the thresholding eigenvectors are themselves noisy. The proof passes the perturbation through a fixed subspace, but in reality the subspace moves, and the unaccounted error involves Ṽ−V, governed by the spectral gap of S near ε (Davis–Kahan), not by χκ(S_>ε). That term is absent from the bound. So the O(M) result is not actually proved for the protocol as executed. Fig. 2's caption doesn't say which S was used for thresholding, which weakens the empirical support. This is an addressable gap, not a fatal one: either analyze the subspace perturbation under a separation assumption, or test numerically whether thresholding with the noisy S changes the scaling. I'd like to see either before the claim is stated as proven.\n\nTwo smaller points. The scalable-thresholding definition requires existence of constants c with bias O(1), and the evidence is only small-system numerics (M up to 126, per-family c). The paper is honest about that. And the bound is per matrix element, so total measurement cost is O(M^3), not O(M); the abstract does say per-element, but it's easy to misread.\n\nThe citation pattern is fine: the old bound is attributed to both [20] and [23], and the new step is clearly marked. Given the clean math, public code, and a genuinely useful bound, this deserves serious peer review. The gap between the theorem and the protocol should be closed before publication, but the paper is well worth engaging with.","headline":"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.","tokens_in":12573,"tokens_out":4589,"would_cite":true,"duration_ms":44628,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F15","15A42","81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"Overlap thresholding reduces the quantum eigensolver measurement cost from cubic to linear in the number of reference states.","keywords":["nonorthogonal quantum eigensolver","quantum subspace diagonalization","measurement cost","overlap thresholding","condition number","finite-shot perturbation theory","generalized eigenvalue problem","hydrogen chains and rings"],"falsifier":"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.","tokens_in":11489,"feed_emoji":"⚛️","tokens_out":11140,"duration_ms":105760,"temperature":0.7,"pith_summary":"The paper sets out to remove a measurement bottleneck in the nonorthogonal quantum eigensolver (NOQE), a quantum-chemistry algorithm that builds a small Hamiltonian in a subspace of dressed nonorthogonal reference states and diagonalizes it classically after estimating the matrix elements with a quantum computer. The known bottleneck is that finite-shot noise in those matrix elements is magnified by an overlap matrix that is nearly singular, so the number of circuit repetitions per matrix element can grow steeply with the number of reference states $M$. The paper's central claim is that thresholding away small-overlap directions makes the eigenvalue error depend on the condition number of the retained overlap matrix instead of on the subspace dimension, and that under a scalable thresholding scheme the per-element shot count sufficient for a target eigenangle error $\\mathcal{E}$ is $\\mathcal{O}(M/\\mathcal{E}^2)$, improving the previously known $\\mathcal{O}(M^3)$ bound. Numerical experiments on hydrogen chains and rings show the retained condition number staying controlled and the thresholding bias not growing with system size, indicating that the linear bound is realized in practice and may even be beaten.","feed_headline":"Overlap thresholding cuts quantum eigensolver shot cost to linear","feed_subtitle":"A perturbation bound shows O(M) shots per matrix element suffice, beating the old O(M^3) bound for NOQE.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Mathias-Li eigenangle perturbation bound stated as Theorem 1, the starting point of the finite-shot error analysis.","marker":"[18]"},{"why":"One of the two sources of the earlier cubic shot-cost bound that Corollary 2 improves.","marker":"[20]"},{"why":"Defines the NOQE algorithm, its dressed UHF reference states, and the overlap thresholding practice whose measurement cost is analyzed.","marker":"[22]"},{"why":"The other source of the earlier cubic shot-cost bound and of the NOQE cost model this paper improves.","marker":"[23]"},{"why":"Supplies the modified-Hadamard-test measurement protocol that maps circuit repetitions to the matrix-element noise model.","marker":"[28]"},{"why":"Provides the random-matrix concentration result used to write the perturbation norm as $\\mathcal{O}(\\sqrt{M/N_{\\mathrm{shots}}})$.","marker":"[29]"}],"fun_headline_variants":["NOQE shot count drops from cubic to linear via overlap thresholding","Linear shot scaling for NOQE via overlap thresholding","How to cut NOQE measurement cost from M^3 to M","Condition number, not dimension, dictates NOQE shot budget"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["NOQE shot count drops from cubic to linear via overlap thresholding","Linear shot scaling for NOQE via overlap thresholding","How to cut NOQE measurement cost from M^3 to M","Condition number, not dimension, dictates NOQE shot budget"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00056,"raw_usage":{"total_tokens":2686,"prompt_tokens":997,"completion_tokens":1689,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":1619}},"tokens_in":613,"tokens_out":1689,"duration_ms":11569,"temperature":1.0,"reasoning_tokens":1619,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:27:12.276547+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Mathias and C.-K","cited_arxiv_id":null,"evidence_quote":"Supplies the Mathias-Li eigenangle perturbation bound stated as Theorem 1, the starting point of the finite-shot error analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The other source of the earlier cubic shot-cost bound and of the NOQE cost model this paper improves."},{"cited_title":"Vershynin, inCompressed Sensing: Theory and Appli- cations(Cambridge University Press, 2012) pp","cited_arxiv_id":null,"evidence_quote":"Provides the random-matrix concentration result used to write the perturbation norm as $\\mathcal{O}(\\sqrt{M/N_{\\mathrm{shots}}})$."}],"review_version":1}