REVIEW 3 major objections 3 minor 41 references
Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information
T0 review · 3 major / 3 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read Adaptive variance-aware stopping can cut quantum energy readout shots by up to 10x
desk verdict The central tail-bound claim has a concrete off-by-Ng flaw in the fallback cap, but the core EBS-for-grouped-measurement idea is sound and repairable. 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 mechanism is the empirical Bernstein stopping algorithm combined with a grouped Pauli measurement scheme. EBS repeatedly evaluates the empirical Bernstein inequality, replacing the unknown variance with the running empirical variance, and stops when the resulting confidence interval width falls below the target accuracy. Geometric sampling checks the stopping condition only at times floor($\beta$^k) to reduce computational overhead, and a martingale-based mid-interval stopping rule prevents overshooting. The paper caps total measurement rounds at the Hoeffding number NHoeff to guarantee termination, and distributes the failure probability delta over a finite schedule of per-check inconfidences d_i. The grouped estimator is what makes EBS compatible with practical commuting-group measurements: each group is measured once per round, producing one energy sample per Ng state preparations.
What would settle it
A direct tail calculation for the grouped estimator after NHoeff total measurement rounds shows its effective sample size is NHoeff/Ng; for any Ng > 1 there exists a state (e.g., one with maximal variance on each group) whose Hoeffding confidence interval has width exceeding epsilon, so the claimed 1-delta guarantee fails unless an additional argument is supplied. A simulation of the capped algorithm on such a state should show a failure rate above delta.
Extended reading notes
Core claim
The paper's central claim is that an adaptive estimator built on the empirical Bernstein stopping rule can replace the non-adaptive Hoeffding readout guarantee without sacrificing the (epsilon, delta) accuracy promise. The construction combines a grouped energy estimator, where measuring every commuting Pauli group once yields one unbiased energy sample, with EBS running on those i.i.d. samples. The stopping rule uses the empirical Bernstein inequality, so a state with small actual variance is detected through its small empirical variance and the procedure terminates early; the paper proves the associated tail bound and verifies numerically that the number of measurement rounds is 10–30 percent of the Hoeffding baseline for the ground states of H2, LiH, BeH2, H2O, and NH3 Hamiltonians under several fermion-to-qubit encodings.
Load-bearing premise
The guarantee relies on the unproven assertion that stopping after NHoeff total measurement rounds still delivers the promised accuracy, even though the grouped estimator consumes Ng state preparations per energy sample and therefore has only NHoeff/Ng samples by that point.
Editorial extensions
If this is right
- For low-variance states, the expected sample complexity scales as $\max(\sigma^2/\epsilon^2, R/\epsilon)$ up to logarithmic factors, giving up to a quadratic improvement over the Hoeffding scaling $(\sum_i |h_i|)^2/\epsilon^2$.
- The numerical benchmarks show EBS uses 10–30 percent of the Hoeffding measurement rounds to reach chemical accuracy for several small molecules, with the advantage persisting as the qubit count grows to 16.
- The advantage appears only at high precision (epsilon below about $10^{-2}$ Hartree); at moderate precision the constant overhead of the grouped estimator cancels the benefit.
- Because the guarantee degrades to the Hoeffding bound in the worst case, the method is safe to use as a drop-in readout subroutine for hybrid quantum-classical algorithms such as VQE.
Reading between the lines
- Allocating measurements among groups according to per-group empirical variance could lower the variance of the grouped estimator and further reduce total rounds; the paper mentions this as future work.
- The equal division of the failure probability $\delta$ among checks is a design choice; alternative schedules may reduce the expected sample count without changing the tail bound.
- The same empirical-Bernstein machinery could apply to other readout strategies, such as randomized classical shadows, if a suitable empirical Bernstein inequality is derived for the estimator.
- For highly mixed states the adaptive estimator offers little over the simple bound, so a practical user should measure the state's concentration before choosing between EBS and a fixed-sample strategy.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an adaptive energy estimation method for quantum many-body systems that combines the empirical Bernstein stopping (EBS) algorithm with Pauli grouping. The central claim is that the resulting estimator has a rigorous (1−δ) tail bound that exploits the empirical variance of the state, and the authors present numerical benchmarks on small molecular Hamiltonians showing that EBS requires roughly 10–30% of the number of measurement rounds mandated by a Hoeffding-based single-shot estimator.
Significance. If the rigorous tail bound were established, the work would be a valuable contribution to quantum energy estimation, as it offers a principled way to exploit low empirical variance to reduce sampling overhead. The paper includes reproducible numerical experiments and a public code repository, which are strengths. However, the main correctness claim is undermined by a flaw in the fallback cap described in Section IIIA, so the algorithm as stated does not deliver the promised (1−δ) guarantee.
major comments (3)
- [Section IIIA, Eq. (6) and surrounding text] The cap at N_Hoeff total measurement rounds does not preserve the (1−δ) accuracy guarantee for the grouped energy estimator. Each execution of Algorithm 1 requires Ng state preparations (one per group) to yield a single energy sample, so after N_Hoeff total measurement rounds the algorithm has only N_Hoeff/Ng independent samples. The Hoeffding bound (3), derived in Appendix B for the single-shot estimator where one sample costs one state preparation, requires n ≥ N_Hoeff samples to achieve error ε with probability at least 1−δ. Substituting n = N_Hoeff/Ng into the Hoeffding bound gives a failure probability of 2 exp(−N_Hoeff ε²/(2 Ng S²)) = 2^{1−1/Ng} δ^{1/Ng}, which exceeds δ for every Ng > 1 (e.g., about 0.464 for Ng = 3 and δ = 0.1). Thus the claimed worst-case guarantee fails on the non-termination event; the empirical Bernstein bound in Eq. (4) only covers runs that stop at a check. This invalidates the abstract's claim of a rigorous tail bound for the algorithm as described.
- [Section IIIA, finite inconfidence sequence] Even if the cap were changed to Ng·N_Hoeff total measurement rounds, the paper does not account for the union of failure probabilities. The EBS stopping rule allocates an inconfidence sequence (d_i) summing to δ for the checks, while the Hoeffding fallback at the cap is a separate probabilistic statement that carries its own failure probability. Simply stopping at the cap and invoking Hoeffding with the same δ leads to a total failure probability that can be as large as 2δ. The authors need to specify how the overall failure probability δ is partitioned between the EBS stopping rule and the Hoeffding fallback.
- [Section IIIB, Figures 1 and 2] The numerical benchmarks are presented as support for the rigorous guarantee, but because the cap is flawed, the experiments do not substantiate the central claim. For the tested low-variance states the algorithm may terminate before reaching the cap, so the reported improvements could remain valid after a correction, but this needs to be verified. The authors should rerun the benchmarks with a correctly capped algorithm (e.g., with the cap at Ng·N_Hoeff and a proper split of the failure probability) and state whether the claimed reductions in measurement rounds persist.
minor comments (3)
- [Section IIIA, Eq. (6)] The notation 'NHoeff !≥ Ng⌊βK⌋' contains a typographical artifact; it should be written as a clear inequality. Also, the text should explicitly define whether 'measurement round' means one state preparation or one execution of Algorithm 1, since the paper uses both notions in different places.
- [Section IIIB, Figure 1 inset] The sentence 'we find that EBS consistently yields |Ê − E| ≤ ε/4 empirically' reports an observed property, not a rigorous guarantee. It would help to label this explicitly as an empirical observation so readers do not conflate it with the proven tail bound.
- [Throughout] The term 'inconfidence' is nonstandard; consider using 'failure probability' or 'confidence parameter' consistently to improve readability.
Circularity Check
No circular derivation: the EBS tail bound is an external result and the grouped-estimator adaptation does not reduce to its inputs; the Hoeffding-cap concern is a correctness issue, not circularity.
full rationale
The derivation chain for the central claim is self-contained. The adaptive tail bound is imported from the external empirical Bernstein stopping algorithm of Mnih et al. [20] and the empirical Bernstein inequality of Audibert et al. [21]; the paper applies these to the grouped energy estimator without defining the target energy in terms of the estimator. The Hoeffding baseline (Eq. (3)) is derived in Appendix B for the single-shot estimator of Ref. [11], an external benchmark, and is used as a comparison and as a fallback cap. The self-citations to ShadowGrouping [18] and its code [38] are used as a numerical grouping tool, not as the source of the tail-bound guarantee, so they are not load-bearing. The only notable issue is in Section IIIA around Eq. (6): the fallback cap appears to compare total measurement rounds with energy samples, missing a factor of N_g for the grouped estimator; this is a correctness flaw in the claimed guarantee, not a circularity, because the flawed step is not equivalent to its inputs by construction. Therefore, no circular step is exhibited and the circularity score is 0.
Assumptions & free parameters
free parameters (3)
- beta (geometric sampling factor) =
1.1
- k0 (minimum sample count before first check) =
ceil(log_beta(10))
- inconfidence sequence d_i =
delta / (K - k0 + 1) for each check
assumptions (4)
- standard math Empirical Bernstein inequality (Audibert et al. 2007) holds for iid bounded samples.
- standard math EBS algorithm guarantee (Mnih et al. 2008) provides a rigorous stopping rule.
- domain assumption Energy samples from Algorithm 1 are iid and bounded in [-sum|h_i|, sum|h_i|].
- ad hoc to paper The cap at N_Hoeff preserves the 1-delta accuracy guarantee for the grouped estimator.
Cite this review
Pith. "Pith review of Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information." pith.science (2026). https://pith.science/paper/BAI7HAZQ
@misc{pith2026250201730,
author = {Pith},
title = {Pith review of: Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information},
year = {2026},
howpublished = {\url{https://pith.science/paper/BAI7HAZQ}},
note = {Machine review of arXiv:2502.01730}
}
read the original abstract
We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition. For various quantum algorithms, in particular in the context of quantum chemistry, it is crucial to have energy estimates with error bounds, as captured by guarantees on the problem's sampling complexity. In particular, when limited to Pauli basis measurements, the smallest sampling complexity guarantee comes from a simple single-shot estimator via a straightforward argument based on Hoeffding's inequality. In this work, we construct an adaptive estimator using the state's actual variance. Technically, our estimation method is based on the Empirical Bernstein stopping (EBS) algorithm and grouping schemes, and we provide a rigorous tail bound, which leverages the state's empirical variance. In a numerical benchmark of estimating ground-state energies of several Hamiltonians, we demonstrate that EBS consistently improves upon elementary readout guarantees up to one order of magnitude.
Figures
Reference graph
Works this paper leans on
-
[1]
R. P. Feynman,Simulating physics with computers, Int. J. Theor. Phys.21, 467 (1982)
work page 1982
-
[2]
T. Hoefler, T. Häner, and M. Troyer, Disentangling hype from practicality: On realistically achieving quan- tum advantage, Commun. ACM 66, 82–87 (2023), arXiv:2307.00523 [quant-ph]
arXiv 2023
-
[3]
H. Liu, G. H. Low, D. S. Steiger, T. Häner, M. Reiher, and M. Troyer,Prospects of quantum computing for molecular sciences, Mater. Theor. 6, 11 (2022), arXiv:2102.10081 [quant-ph]
work page Pith review arXiv 2022
-
[4]
Emerging quantum computing algorithms for quantum chemistry
M. Motta and J. E. Rice,Emerging quantum computing algorithms for quantum chemistry, WIREs Comput. Mol. Sci. 12, e1580 (2022), arXiv:2109.02873
work page Pith review arXiv 2022
-
[5]
J. F. Gonthier, M. D. Radin, C. Buda, E. J. Doskocil, C. M. Abuan, and J. Romero,Measurements as a road- block to near-term practical quantum advantage in chem- istry: Resource analysis, Phys. Rev. Res.4, 033154 (2022), arXiv:2012.04001
arXiv 2022
-
[6]
P. Gokhale, O. Angiuli, Y. Ding, K. Gui, T. Tomesh, M. Suchara, M. Martonosi, and F. T. Chong, Mini- mizing state preparations in variational quantum eigen- solver by partitioning into commuting families (2019), arXiv:1907.13623 [quant-ph]
arXiv 2019
-
[7]
A. Jena, S. Genin, and M. Mosca,Pauli partitioning with respect to gate sets, arXiv:1907.07859 [quant-ph]
arXiv 1907
-
[8]
V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov,Measure- ment optimization in the variational quantum eigensolver using a minimum clique cover,J.Chem.Phys. 152,124114 (2020), arXiv:1907.03358 [quant-ph]
arXiv 2020
Show all 41 references
-
[9]
Crawford, B
O. Crawford, B. van Straaten, D. Wang, T. Parks, E. Campbell, and S. Brierley,Efficient quantum mea- surement of Pauli operators in the presence of finite sam- pling error, Quantum 5, 385 (2021), arXiv:1908.06942 [quant-ph]
2021 arXiv
-
[10]
A. Zhao, A. Tranter, W. M. Kirby, S. F. Ung, A. Miyake, and P. J. Love,Measurement reduction in variational quantum algorithms, Phys. Rev. A101, 062322 (2020), arXiv:1908.08067 [quant-ph]
2020 arXiv
-
[11]
Arrasmith, L
A. Arrasmith, L. Cincio, R. D. Somma, and P. J. Coles, Operator sampling for shot-frugal optimization in varia- tional algorithms(2020), arXiv:2004.06252 [quant-ph]
2020 arXiv
-
[12]
Huang and R
H.-Y. Huang and R. Kueng, Predicting features of quantum systems from very few measurements , arXiv:1908.08909 (2019)
2019 arXiv
-
[13]
Huang, R
H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nature Physics 16, 1050–1057 (2020), arXiv:2002.08953 [quant-ph]
2020 arXiv
-
[14]
Elben, S
A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller,The random- ized measurement toolbox, Nat. Rev. Phys.5, 9 (2023), arXiv:2203.11374
2023 arXiv
-
[15]
Hadfield, S
C. Hadfield, S. Bravyi, R. Raymond, and A. Mezzacapo, Measurements of quantum Hamiltonians with locally- biased classical shadows, Commun. Math. Phys.391, 951 (2022), arXiv:2006.15788
2022 arXiv
-
[16]
Shlosberg, A
A. Shlosberg, A. J. Jena, P. Mukhopadhyay, J. F. Haase, F. Leditzky, and L. Dellantonio,Adaptive esti- mation of quantum observables, Quantum 7, 906 (2023), arXiv:2110.15339
2023 arXiv
-
[17]
B. Wu, J. Sun, Q. Huang, and X. Yuan, Over- lapped grouping measurement: A unified framework for measuring quantum states, Quantum 7, 896 (2023), arXiv:2105.13091
2023 arXiv
-
[18]
Gresch and M
A. Gresch and M. Kliesch, Guaranteed efficient en- ergy estimation of quantum many-body Hamiltonians using ShadowGrouping, Nat. Comms. 16, 689 (2025), arXiv:2301.03385 [quant-ph]
2025 arXiv
-
[19]
L. Zhu, S. Liang, C. Yang, and X. Li,Optimizing shot assignment in variational quantum eigensolver measure- ment, Journal of Chemical Theory and Computation20, 2390 (2024), arXiv:2307.06504 [quant-ph]
2024 arXiv
-
[20]
V. Mnih, C. Szepesvári, and J.-Y. Audibert,Empirical Bernstein stopping, in Proceedings of the 25th Interna- tional Conference on Machine Learning, ICML ’08 (Asso- ciation for Computing Machinery, New York, NY, USA,
-
[21]
Audibert, R
J.-Y. Audibert, R. Munos, and C. Szepesvári,Tuning ban- dit algorithms in stochastic environments, inAlgorithmic Learning Theory(Springer, 2007) pp. 150–165
2007
-
[22]
Mnih,Efficient stopping rules, Master’s thesis, Univer- sity of Alberta (2008)
V. Mnih,Efficient stopping rules, Master’s thesis, Univer- sity of Alberta (2008)
2008
-
[23]
Reiher, N
M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating reaction mechanisms on quantum computers, PNAS 114, 7555–7560 (2017), arXiv:1605.03590 [quant-ph]
2017 arXiv
-
[24]
von Burg, G
V. von Burg, G. H. Low, T. Häner, D. S. Steiger, M. Rei- her, M. Roetteler, and M. Troyer,Quantum computing en- hanced computational catalysis, Phys. Rev. Res.3, 033055 (2021), arXiv:2007.14460 [quant-ph]
2021 arXiv
-
[25]
Kandala, A
A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta,Hardware- efficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017), arXiv:1704.05018 [quant-ph]
2017 arXiv
-
[26]
Hempel, C
C. Hempel, C. Maier, J. Romero, J. McClean, T. Monz, H. Shen, P. Jurcevic, B. P. Lanyon, P. Love, R. Babbush, A. Aspuru-Guzik, R. Blatt, and C. F. Roos,Quantum chemistry calculations on a trapped-ion quantum simu- lator, Phys. Rev. X8, 031022 (2018), arXiv:1803.10238 [quant-ph]
2018 arXiv
-
[27]
Arute, K
F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buck- ley, D. A. Buell, B. Burkett, N. Bushnell, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, S. De- mura, A. Dunsworth, D. Eppens, E. Farhi, A. Fowler, B. Foxen, C. Gidne...
2020 arXiv
-
[28]
Kawashima, E
Y. Kawashima, E. Lloyd, M. P. Coons, Y. Nam, S. Mat- suura, A. J. Garza, S. Johri, L. Huntington, V. Senicourt, A. O. Maksymov, J. H. V. Nguyen, J. Kim, N. Alidoust, A. Zaribafiyan, and T. Yamazaki,Optimizing electronic structure simulations on a trapped-ion quantum computer u...
2021 arXiv
-
[29]
A. tA v, M. S. ANIS, and A.-M.et al., Qiskit: An open- source framework for quantum computing(2021)
2021
-
[30]
Efthymiou, S
S. Efthymiou, S. Ramos-Calderer, C. Bravo-Prieto, A. Pérez-Salinas, D. García-Martín, A. Garcia-Saez, J. I. Latorre, and S. Carrazza,Qibo: a framework for quan- tum simulation with hardware acceleration, Quantum Sci- ence and Technology7, 015018 (2021), arXiv:2009.01845 [quant-ph]
2021 arXiv
-
[31]
U. Tepe, A. Gresch, and M. Kliesch, EmpiricalBern- steinAlgorithm, GitHub repositoryhttps://github.com/ UgurTepe/EmpiricalBernsteinAlgorithm (2024)
2024
-
[32]
Peruzzo, J
A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nat. Commun.5, 4213 (2014), arXiv:1304.3061 [quant-ph]
2014 arXiv
-
[33]
Wecker, M
D. Wecker, M. B. Hastings, and M. Troyer,Progress towards practical quantum variational algorithms, Phys. Rev. A 92, 042303 (2015), arXiv:1507.08969 [quant-ph]
2015 arXiv
-
[34]
J. R. McClean, J. Romero, R. Babbush, and A. Aspuru- Guzik, The theory of variational hybrid quantum- classical algorithms, New J. Phys. 18, 023023 (2016), arXiv:1509.04279 [quant-ph]
2016 arXiv
-
[35]
Eckstein, R
T. Eckstein, R. Mansuroglu, S. Wolf, L. Nützel, S. Tasler, M. Kliesch, and M. J. Hartmann,Shot-noise reduction for lattice Hamiltonians, arXiv:2410.21251 [quant-ph] (2024)
2024 arXiv
-
[36]
P. J. J. O’Malley, R. Babbush, I. D. Kivlichan, J. Romero, J. R. McClean, R. Barends, J. Kelly, P. Roushan, A. Tran- ter, N. Ding, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. G. Fowler, E. Jeffrey, E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, C. Quin...
2016 arXiv
-
[37]
Hadfield, adaptiveshadows, GitHub repos- itory https://github.com/charleshadfield/ adaptiveshadows/tree/main/Hamiltonians (2021)
C. Hadfield, adaptiveshadows, GitHub repos- itory https://github.com/charleshadfield/ adaptiveshadows/tree/main/Hamiltonians (2021)
2021
-
[38]
Gresch and M
A. Gresch and M. Kliesch, ShadowGrouping, GitHub repository https://gitlab.com/GreschAI/ shadowgrouping (2022)
2022
-
[39]
Jordan and W
P. Jordan and W. Eugene,Über das paulische äquivalen- zverbot, Z. Physik47, 631 (1928)
1928
-
[40]
S. B. Bravyi and A. Y. Kitaev,Fermionic quantum compu- tation, Ann. Phys.298, 210 (2002), arXiv:0003137 [quant- ph]
2002
-
[41]
J. T. Seeley, M. J. Richard, and P. J. Love,The Bravyi- Kitaev transformation for quantum computation of elec- tronic structure, J. Comp. Phys. 137, 224109 (2012), arXiv:1208.5986 [quant-ph]. APPENDIX This appendix recaps relevant strategies for the direct readout of a quantum...
2012 arXiv
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.