Pith. sign in

REVIEW 1 major objections 4 minor 82 references

Quantum online shadow tomography now matches classical sample rates in all parameters.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 01:49 UTC pith:5FM7CT6J

load-bearing objection Strong paper with a real gap: the dimension-free protocol holds up, but Theorem 1.2 relies on a faulty inequality in Lemma 4.9 that is likely fixable but not fixed. the 1 major comments →

arxiv 2607.29686 v1 pith:5FM7CT6J submitted 2026-07-31 quant-ph cs.DS

Online Shadow Tomography Matching the Classical Bounds

Sitan Chen , Ryan O'Donnell , Angelos Pelecanos , John Wright This is my paper
classification quant-ph cs.DS
keywords online shadow tomographyquantum state learningadaptive data analysisquantum Efron-Stein decompositiongentle measurementssample complexitypost-measurement damage
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper tries to establish that Online Shadow Tomography—estimating the expectation values of an adaptively chosen sequence of quantum observables from copies of an unknown state—can be solved with the same number of copies as the classical problem of adaptive data analysis. The authors propose two protocols: one using O(log m sqrt(log d)/eps^3) copies, the other using O(sqrt(m)/eps^2) copies. If correct, these match the best known classical rates and close a gap that had been open in all three parameters m, d, and eps. The proofs rest on a new way to quantify how much a gentle measurement damages the state, based on the quantum Efron–Stein decomposition.

Core claim

The central claim is that the sample complexity of Online Shadow Tomography matches the classical adaptive-data-analysis rates. Theorem 1.2 gives a protocol using n = O(sqrt(K) log(m+K)/eps^2) copies with K = Theta(log d/eps^2), i.e., n = O(log m sqrt(log d)/eps^3); Theorem 1.3 gives a protocol using n = O(sqrt m/eps^2) copies, independent of d. The authors prove these by tracking the 'energy' of the n-copy state under a decomposition into excitations relative to a purification of rho, and showing that each round's measurement increases this energy only in proportion to how likely the protocol is to make a mistake. The logistic-based soft measurement yields the logarithmic-in-m rate; a compa

What carries the argument

The key object is the excitation decomposition of the n-copy state |phi> = sum_{S subset [n]} |phi_S> where |phi_S> is the component with excitations on S, together with the energy E[tau] = (1/n) Tr(N tau) for the number operator N = sum_i (1 - |psi><psi|)_i. Lemma 3.4 bounds the probability of a 'bad' event by O(E[tau]/eps^2). The per-step damage controls (Corollary 4.6 and Lemma 5.3) bound the expected energy increase of a soft measurement: for the logistic measurement, O(lambda^2/n^2) Tr(F tau); for the compact-noise measurement, O(1/(n^2 eps^2)) Tr(tau).

Load-bearing premise

The proof of the logarithmic-in-m rate relies on the per-step damage bound (Corollary 4.6), whose derivation uses an inequality (Eq. (10) in Lemma 4.9) that may not hold for the logistic function; if that inequality cannot be repaired, the O(log m sqrt(log d)/eps^3) rate is not established as written.

What would settle it

Compute, for the logistic f(x)=1/(1+e^{lambda(b-x)}) with parameters from Theorem 1.2, the quantity L_f R_f(1+sqrt(R_f))/n in Lemma 4.9 and test whether sup_{x in I} alpha'(x) <= sqrt(f_+) sup_{x in I} alpha'(x) sqrt(f(x)) holds for every interval I of width at most 1/n. A single numerical counterexample to this inequality would invalidate the energy-increase bound as stated, and with it the current proof of Theorem 1.2.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The quantum sample complexity for online shadow tomography now matches the classical adaptive data analysis rates in all parameters m, d, eps.
  • The O(log m sqrt(log d)/eps^3) protocol is the first online shadow tomography protocol with o(log^2 m) dependence together with poly(log d / eps) dependence.
  • The O(sqrt m/eps^2) protocol is optimal among dimension-independent protocols up to constants and improves the best prior dimension-independent bound by a sqrt(m) log m factor.
  • The same energy-accounting technique improves all three exponents even for the offline shadow tomography setting.
  • The proof gives a non-differential-privacy route to the classical adaptive data analysis rates, via Fourier analysis over product spaces.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The excitation-energy framework should extend to other adaptive quantum learning tasks where gentle measurements are used, such as online state certification or quantum channel learning, giving damage bounds in terms of a comparable 'influence' quantity.
  • The compact-noise protocol suggests a direct tradeoff: each measurement adds a fixed 'noise variance' to the state, so one might tune the noise width to control smoothness versus accuracy in other query models.
  • A natural testable extension is to replace the logistic function with a smoothed threshold kernel optimized for the damage bound, possibly removing the log(m+K) factor or reducing the eps-dependence in the logarithmic-in-m regime.
  • If the per-step damage bound fails as written, the logarithmic-in-m rate might still hold via a different per-step estimate; the framework itself may survive with a corrected inequality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper addresses Online Shadow Tomography, where an adversary adaptively chooses observables A^(t) and the learner estimates Tr(A^(t)ρ) from n copies of an unknown d-dimensional state ρ. It proposes two protocols and claims sample complexities n = O(√K log(m+K)/ε²) with K = Θ(log d/ε²) (Theorem 1.2) and n = O(√m/ε²) (Theorem 1.3), which match the classical adaptive-data-analysis rates. The technical framework is an 'excitation decomposition' of the n-copy state relative to a purification: the energy E[τ] = Tr(Nτ)/n is used to charge post-measurement damage. Section 5's dimension-free protocol uses a continuous POVM with compact cosine noise; Section 4's logarithmic-in-m protocol uses soft binary logistic measurements inside an MMW 'teacher-student' loop. The appendix gives an information-theoretic threshold-search result.

Significance. The claimed results, if established, would close the quantum-classical gap for online shadow tomography in all three parameters m, d, ε and would give the first o(log² m) online protocol with poly(log d/ε) dependence. Theorem 1.3 would also improve the previous dimension-free bound by a √m log m factor. The excitation-decomposition framework is a genuinely promising addition to the gentle-measurement toolbox, and the dimension-free half of the paper (Section 5) appears self-contained and correctly implemented. However, the logarithmic-in-m half has a specific proof gap described below, so the headline claim is not established as written.

major comments (1)
  1. [§4.3, Lemma 4.9, Eq. (10)] The displayed inequality ∆ ≤ (1/n)·sup_I α′ ≤ (1/n)·√f_+ · sup_I(α′√f) has the wrong direction. Since √f(x) ≤ √f_+, one gets sup_I(α′√f) ≤ √f_+ · sup_I α′, not the reverse; equivalently, sup_I α′ ≥ sup_I(α′√f)/√f_+. For the logistic f used in Corollary 4.6 the failure is severe: on a block where f_+ is small, L_f = sup(α′√f) ≈ (λ/2)f_+ while sup α′ ≈ (λ/2)√f_+, so Eq. (10) overestimates the bound by roughly 1/f_+. Consequently Lemma 4.9's operator bound, Corollary 4.6, and the telescoping Lemma 4.7 do not follow. Since Lemma 4.7 is the only argument bounding ∑ E[τ] by O(λ²K/n²), Theorem 1.2 is not established as written. The error is local and a repair may be possible using the explicit logistic identity α′ = (λ/2)√(f/(1−f)) and the ratio f_+/f_-, but no such repair appears in the manuscript.
minor comments (4)
  1. [§4.3, proof of Corollary 4.6] The displayed identity α′(x)√f(x) = (λ/2)√(1−f(x)) is algebraically incorrect; the correct derivative is α′(x)√f(x) = (λ/2) f(x)√(1−f(x)). The claimed bound L_f ≤ λ/2 still holds because f√(1−f) ≤ 1/2, but the derivation as written is wrong.
  2. [§5.3, Claim 5.5] 'Plancherel' should be 'Parseval' in the context of L² norm preservation, and the normalization convention for the Fourier transform should be stated explicitly. These are harmless presentation issues.
  3. [§5.2] The notation ∫_D Tr(τ_e) de for integration over the continuum tree is used before being formally defined. A short paragraph defining the measure on transcripts would improve readability.
  4. [Algorithm 1, line 19] The repeat–until structure is understandable but slightly ambiguous when 'failed' is set inside the loop. Clarifying that the next iteration checks 'failed' first would help.

Circularity Check

0 steps flagged

No significant circularity: the claimed rates are derived from an in-paper excitation framework and external benchmarks, not from fitted inputs or self-referential definitions. A separate, non-circular proof gap in Lemma 4.9 Eq. (10) affects correctness of Theorem 1.2 as written.

full rationale

I walked the derivation chains of Theorems 1.2 and 1.3. Theorem 1.2's proof chain is: Algorithm 1 (soft binary measurements with logistic f), Lemma 4.4 (matrix multiplicative weights regret), Lemma 4.5 (probability of a bad leaf via Lemma 3.4), Corollary 4.6 (per-step energy increase), Lemma 4.7 (telescoping energy), and the final choice of n and lambda. Each step is proved in-paper: Lemma 3.4 follows from Lemma 3.5, which is a direct calculation using Pickl's excitation decomposition [Pic11]; the logistic-function estimates L_f <= lambda/2 and R_f <= e^{lambda/n} are computed from f's form. The parameters K, lambda, and n are chosen after the bounds are derived, not fitted so as to force the target rates. Theorem 1.3's chain is similarly in-paper: Algorithm 2, Claim 5.5 (Fourier variance of the compact-noise kernel), Lemma 5.3 (per-step damage), and telescoping. The classical rates [BNS+21, NSS+18, LT25] are used only as external benchmarks/lower bounds, not as inputs to the proofs. The paper does cite works by its own authors, notably [PFMO25] in Remark 3.2, but that citation is explicitly a dual interpretation; the load-bearing excitation framework is attributed to Pickl and proved from the decomposition. Other self-citations ([BO24], [PSW26], [CGY24], [CLL24]) appear in related-work or prior-art context and are not used to establish the theorems. Thus the derivation does not reduce by construction to its inputs and no prediction is a renamed fit. I am not scoring higher because the self-citations are not load-bearing. One non-circular concern must be flagged per the reviewing rule: in Lemma 4.9, Eq. (10) states sup_{x in I} alpha'(x) <= sqrt(f_+) * sup_{x in I}(alpha'(x) sqrt(f(x))). This inequality has the wrong direction; for the logistic f used in Corollary 4.6 it can fail by a factor exponential in lambda/n on blocks where f is exponentially small. Consequently Corollary 4.6 and Theorem 1.2 are not established as written. This is a correctness/rigor gap, not a circularity, and does not change the circularity score.

Axiom & Free-Parameter Ledger

3 free parameters · 5 axioms · 1 invented entities

The central proof rests on standard quantum-information theorems and hand-set protocol parameters. The excitation energy is an invented analysis device, not an empirical entity. The main concern is not an extra axiom but the incorrect inequality in Lemma 4.9, which is tracked under red flags.

free parameters (3)
  • Logistic sharpness lambda = Theta(eps n / sqrt(K)) ~ Theta(log(m+K)/eps)
    Algorithm parameter chosen by hand to balance the flag-probability term and the per-step energy increase; not fitted to data.
  • Mistake budget K = Theta(log(d)/eps^2)
    Set from the matrix-multiplicative-weights regret bound; caps the number of flags before failure.
  • Noise width omega = eps/4
    Chosen in Algorithm 2 so that the compact noise stays within epsilon of the true value while maintaining a valid POVM; hand-set.
axioms (5)
  • standard math Matrix multiplicative weights regret bound for the Gibbs-state updates [Kal07]
    Used in Lemma 4.4 to bound the number of non-bad flags by O(log d/eps^2).
  • domain assumption Purification WLOG: analyzing |psi>^⊗n on H^n ⊗ R^n while measurements act only on H^n
    Invoked at the start of Section 2; standard and lossless because the protocol never touches the purification register.
  • domain assumption Bounded observables 0 ⪯ A ⪯ 1
    Part of Definition 1.1; used throughout for operator-norm bounds and POVM validity.
  • standard math Fawzi-Renner state reconstruction theorem and sharpened measured-relative-entropy version [FR15, BHOS15]
    Used only in Appendix A for the side result on Best Observable Selection; not needed for Theorems 1.2 and 1.3.
  • standard math Sion minimax theorem and Pinsker's inequality
    Used only in Appendix A to convert the Bayesian information-theoretic argument into a worst-case regret bound.
invented entities (1)
  • Excitation energy E[tau] = Tr(N tau)/n, defined relative to the unknown purification |psi> no independent evidence
    purpose: Potential function for tracking cumulative post-measurement damage; the key charging argument is built on it.
    Analysis-only construct: the protocol never measures or estimates N or E. It has no falsifiable handle outside the paper and serves purely as a proof device.

pith-pipeline@v1.3.0-daily-deepseek · 22325 in / 33715 out tokens · 347466 ms · 2026-08-03T01:49:19.363875+00:00 · methodology

0 comments
read the original abstract

In \emph{Online Shadow Tomography}, we are given copies of an unknown $d$-dimensional quantum state $\rho$, an adversary (adaptively) proposes a sequence of bounded observables $A^{(1)},\ldots,A^{(m)}$, and after each $A^{(t)}$ is given we must estimate $\Tr(A^{(t)}\rho)$ to within $\pm \epsilon$. This is the direct quantum generalization of the classical problem of \emph{Adaptive Data Analysis}. %The ``offline'' case, in which $A^{(1)}, \ldots, A^{(m)}$ are given upfront, is also a well-studied problem. The main goal is to minimize the number of copies, $n$, required. Prior results for online Shadow Tomography were suboptimal in all three parameters $m, d, \epsilon$, lagging behind the best known and classical rates~\cite{bassily2021algorithmic}, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. The bound on the left is the first to achieve $o(\log^2 m)$-dependence together with $\poly(\log(d)/\eps)$; moreover, it improves all three exponents even in the \emph{Offline} Shadow Tomography setting. The bound on the right is known to be optimal among bounds independent of~$d$, and improves the best prior result by a $\sqrt{m} \log m$ factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron--Stein decomposition.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

82 extracted references · 3 canonical work pages · 1 internal anchor

  1. [1]

    Proceedings IEEE International Symposium on Information Theory, , pages=

    A new proof of the channel coding theorem via hypothesis testing in quantum information theory , author=. Proceedings IEEE International Symposium on Information Theory, , pages=. 2002 , organization=

    2002

  2. [2]

    IEEE Transactions on information theory , volume=

    Coding theorem and strong converse for quantum channels , author=. IEEE Transactions on information theory , volume=. 1999 , publisher=

    1999

  3. [3]

    Annual international conference on the theory and applications of cryptographic techniques , pages=

    Our data, ourselves: Privacy via distributed noise generation , author=. Annual international conference on the theory and applications of cryptographic techniques , pages=. 2006 , organization=

    2006

  4. [4]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Gentle measurement of quantum states and differential privacy , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

  5. [6]

    SIAM Journal on Computing , volume=

    Algorithmic stability for adaptive data analysis , author=. SIAM Journal on Computing , volume=

  6. [8]

    Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis

    Lyu, Xin and Talwar, Kunal , title =. 2024 , eprint =. doi:10.48550/arXiv.2412.14396 , url =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2412.14396 2024

  7. [9]

    Letters in Mathematical Physics , volume=

    A simple derivation of mean field limits for quantum systems , author=. Letters in Mathematical Physics , volume=. 2011 , publisher=

    2011

  8. [10]

    2007 , publisher=

    Efficient algorithms using the multiplicative weights update method , author=. 2007 , publisher=

    2007

  9. [11]

    IEEE Transactions on Information Theory , volume=

    An information-theoretic view of stochastic localization , author=. IEEE Transactions on Information Theory , volume=. 2022 , publisher=

    2022

  10. [12]

    2014 , publisher=

    Analysis of boolean functions , author=. 2014 , publisher=

    2014

  11. [13]

    Communications in Mathematical Physics , volume=

    Making almost commuting matrices commute , author=. Communications in Mathematical Physics , volume=. 2009 , publisher=

    2009

  12. [14]

    Improved Quantum Data Analysis , journal =

    Costin B. Improved Quantum Data Analysis , journal =. 2024 , doi =

    2024

  13. [15]

    Pacific Journal of Mathematics , volume =

    Maurice Sion , title =. Pacific Journal of Mathematics , volume =. 1958 , doi =

    1958

  14. [16]

    Communications in Mathematical Physics , volume =

    Omar Fawzi and Renato Renner , title =. Communications in Mathematical Physics , volume =. 2015 , doi =

    2015

  15. [17]

    Quantum Conditional Mutual Information, Reconstructed States, and State Redistribution , journal =

    Fernando Brand. Quantum Conditional Mutual Information, Reconstructed States, and State Redistribution , journal =. 2015 , doi =

    2015

  16. [18]

    SIAM Journal on Computing , volume =

    Scott Aaronson , title =. SIAM Journal on Computing , volume =. 2020 , doi =

    2020

  17. [19]

    Journal of Statistical Mechanics: Theory and Experiment , volume =

    Scott Aaronson and Xinyi Chen and Elad Hazan and Satyen Kale and Ashwin Nayak , title =. Journal of Statistical Mechanics: Theory and Experiment , volume =. 2019 , doi =

    2019

  18. [20]

    Generalized private selection and testing with high confidence , BOOKTITLE =

    Cohen, Edith and Lyu, Xin and Nelson, Jelani and Sarl\'. Generalized private selection and testing with high confidence , BOOKTITLE =. 2023 , ISBN =. doi:10.4230/lipics.itcs.2023.39 , URL =

    work page doi:10.4230/lipics.itcs.2023.39 2023

  19. [21]

    Quantum event learning and gentle random measurements , BOOKTITLE =

    Bene. Quantum event learning and gentle random measurements , BOOKTITLE =. 2024 , ISBN =. doi:10.4230/lipics.itcs.2024.97 , URL =

    work page doi:10.4230/lipics.itcs.2024.97 2024

  20. [22]

    Sinha, Pulkit , TITLE =. S. [2025] 2025 , ISBN =. doi:10.1145/3717823.3718253 , URL =

    arXiv 2025

  21. [23]

    2016 , eprint=

    Preserving Statistical Validity in Adaptive Data Analysis , author=. 2016 , eprint=

    2016

  22. [24]

    arXiv preprint arXiv:1806.06100 , year=

    The limits of post-selection generalization , author=. arXiv preprint arXiv:1806.06100 , year=

    Pith/arXiv arXiv

  23. [25]

    Conference on Learning Theory , pages=

    A bounded-noise mechanism for differential privacy , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  24. [26]

    2016 , eprint=

    The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes , author=. 2016 , eprint=

    2016

  25. [27]

    and Ji, Zhengfeng and Wu, Xiaodi and Yu, Nengkun , TITLE =

    Haah, Jeongwan and Harrow, Aram W. and Ji, Zhengfeng and Wu, Xiaodi and Yu, Nengkun , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2017 , NUMBER =. doi:10.1109/tit.2017.2719044 , URL =

    arXiv 2017

  26. [28]

    O'Donnell, Ryan and Wright, John , TITLE =. S. 2016 , MRCLASS =. doi:10.1145/2897518.2897544 , URL =

    arXiv 2016

  27. [29]

    PRX Quantum , volume=

    Predicting adaptively chosen observables in quantum systems , author=. PRX Quantum , volume=. 2026 , publisher=

    2026

  28. [31]

    The debiased

    Pelecanos, Angelos and Spilecki, Jack and Wright, John , booktitle=. The debiased

  29. [32]

    The True Shape of Regret in Bandit Problems , journal =

    Aur. The True Shape of Regret in Bandit Problems , journal =. 2019 , doi =

    2019

  30. [33]

    McAllester , title =

    David A. McAllester , title =. Machine Learning , volume =

  31. [34]

    IEEE Transactions on Information Theory , volume =

    Xu, Aolin and Raginsky, Maxim , title =. IEEE Transactions on Information Theory , volume =. 2022 , month = dec, doi =

    2022

  32. [35]

    Advances in Neural Information Processing Systems , volume =

    Hafez-Kolahi, Hassan and Golgooni, Zeinab and Kasaei, Shohreh and Soleymani, Mahdieh , title =. Advances in Neural Information Processing Systems , volume =

  33. [36]

    Proceedings of the 38th International Conference on Machine Learning , series =

    Hafez-Kolahi, Hassan and Moniri, Behrad and Kasaei, Shohreh and Soleymani Baghshah, Mahdieh , title =. Proceedings of the 38th International Conference on Machine Learning , series =

  34. [37]

    IEEE Transactions on Information Theory , volume =

    Hafez-Kolahi, Hassan and Moniri, Behrad and Kasaei, Shohreh , title =. IEEE Transactions on Information Theory , volume =. 2023 , month = jul, doi =

    2023

  35. [38]

    Journal of Machine Learning Research , volume =

    Russo, Daniel and Van Roy, Benjamin , title =. Journal of Machine Learning Research , volume =

  36. [39]

    Nature Physics , volume =

    Huang, Hsin-Yuan and Kueng, Richard and Preskill, John , title =. Nature Physics , volume =. 2020 , doi =. 2002.08953 , archivePrefix =

    Pith/arXiv arXiv 2020

  37. [40]

    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Chen, Sitan and Gong, Weiyuan and Ye, Qi , title =. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2024 , doi =. 2404.19105 , archivePrefix =

    Pith/arXiv arXiv 2024

  38. [41]

    PRX Quantum , volume =

    King, Robbie and Gosset, David and Kothari, Robin and Babbush, Ryan , title =. PRX Quantum , volume =. 2025 , doi =. 2404.19211 , archivePrefix =

    Pith/arXiv arXiv 2025

  39. [42]

    Quantum , volume =

    Grier, Daniel and Pashayan, Hakop and Schaeffer, Luke , title =. Quantum , volume =. 2024 , doi =. 2211.11810 , archivePrefix =

    Pith/arXiv arXiv 2024

  40. [43]

    Efficient Shadow Tomography of Thermal States , year =

    Chen, Chi-Fang and Gily. Efficient Shadow Tomography of Thermal States , year =. 2603.16845 , archivePrefix =

    arXiv

  41. [44]

    American Journal of Mathematics , volume=

    Fluctuations around Hartree states in the mean-field regime , author=. American Journal of Mathematics , volume=. 2015 , publisher=

    2015

  42. [45]

    Communications on Pure and Applied Mathematics , volume=

    Bogoliubov spectrum of interacting Bose gases , author=. Communications on Pure and Applied Mathematics , volume=. 2015 , publisher=

    2015

  43. [46]

    Reviews in Mathematical Physics , volume=

    Derivation of the time dependent Gross--Pitaevskii equation with external fields , author=. Reviews in Mathematical Physics , volume=. 2015 , publisher=

    2015

  44. [47]

    Communications in Mathematical Physics , volume=

    Mean-field dynamics: singular potentials and rate of convergence , author=. Communications in Mathematical Physics , volume=. 2010 , publisher=

    2010

  45. [48]

    Proceedings of the 2002

    Tomohiro Ogawa and Hiroshi Nagaoka , title =. Proceedings of the 2002. 2002 , doi =

    2002

  46. [49]

    IEEE Transactions on Information Theory , volume =

    Andreas Winter , title =. IEEE Transactions on Information Theory , volume =. 1999 , doi =

    1999

  47. [50]

    Advances in Cryptology---

    Cynthia Dwork and Krishnaram Kenthapadi and Frank McSherry and Ilya Mironov and Moni Naor , title =. Advances in Cryptology---. 2006 , doi =

    2006

  48. [51]

    Proceedings of the 51st Annual

    Scott Aaronson and Guy Rothblum , title =. Proceedings of the 51st Annual. 2019 , doi =

    2019

  49. [52]

    Efficient shadow tomography of thermal states , journal =

    Chi-Fang Chen and Andr. Efficient shadow tomography of thermal states , journal =. 2026 , doi =

    2026

  50. [53]

    SIAM Journal on Computing , volume =

    Raef Bassily and Kobbi Nissim and Adam Smith and Thomas Steinke and Uri Stemmer and Jonathan Ullman , title =. SIAM Journal on Computing , volume =. 2021 , doi =

    2021

  51. [54]

    arXiv preprint arXiv:2510.06147 , year =

    Giacomo De Palma and Marco Fanizza and Connor Mowry and Ryan O'Donnell , title =. arXiv preprint arXiv:2510.06147 , year =

    arXiv

  52. [55]

    Proceedings of the 57th Annual

    Xin Lyu and Kunal Talwar , title =. Proceedings of the 57th Annual. 2025 , doi =

    2025

  53. [56]

    Letters in Mathematical Physics , volume =

    Peter Pickl , title =. Letters in Mathematical Physics , volume =. 2011 , doi =

    2011

  54. [57]

    Satyen Kale , title =

  55. [58]

    IEEE Transactions on Information Theory , volume =

    Ahmed El Alaoui and Andrea Montanari , title =. IEEE Transactions on Information Theory , volume =. 2022 , doi =

    2022

  56. [59]

    2014 , doi =

    Ryan O'Donnell , title =. 2014 , doi =

    2014

  57. [60]

    Communications in Mathematical Physics , volume =

    Matthew Hastings , title =. Communications in Mathematical Physics , volume =. 2009 , doi =

    2009

  58. [61]

    Improved quantum data analysis , journal =

    Costin B. Improved quantum data analysis , journal =. 2024 , doi =

    2024

  59. [62]

    Quantum conditional mutual information, reconstructed states, and state redistribution , journal =

    Fernando Brand. Quantum conditional mutual information, reconstructed states, and state redistribution , journal =. 2015 , doi =

    2015

  60. [63]

    Generalized private selection and testing with high confidence , booktitle =

    Edith Cohen and Xin Lyu and Jelani Nelson and Tam. Generalized private selection and testing with high confidence , booktitle =. 2023 , doi =

    2023

  61. [64]

    Quantum event learning and gentle random measurements , booktitle =

    Adam Bene. Quantum event learning and gentle random measurements , booktitle =. 2024 , doi =

    2024

  62. [65]

    Proceedings of the 57th Annual

    Pulkit Sinha , title =. Proceedings of the 57th Annual. 2025 , doi =

    2025

  63. [66]

    Proceedings of the 47th Annual

    Cynthia Dwork and Vitaly Feldman and Moritz Hardt and Toniann Pitassi and Omer Reingold and Aaron Roth , title =. Proceedings of the 47th Annual. 2015 , doi =

    2015

  64. [67]

    Advances in Neural Information Processing Systems 31 , pages =

    Kobbi Nissim and Adam Smith and Thomas Steinke and Uri Stemmer and Jonathan Ullman , title =. Advances in Neural Information Processing Systems 31 , pages =. 2018 , doi =

    2018

  65. [68]

    Proceedings of the 35th Conference on Learning Theory , series =

    Yuval Dagan and Gil Kur , title =. Proceedings of the 35th Conference on Learning Theory , series =

  66. [69]

    arXiv preprint arXiv:1607.05256 , year =

    Scott Aaronson , title =. arXiv preprint arXiv:1607.05256 , year =

    Pith/arXiv arXiv

  67. [70]

    IEEE Transactions on Information Theory , volume =

    Jeongwan Haah and Aram Harrow and Zhengfeng Ji and Xiaodi Wu and Nengkun Yu , title =. IEEE Transactions on Information Theory , volume =. 2017 , doi =

    2017

  68. [71]

    Proceedings of the 48th Annual

    Ryan O'Donnell and John Wright , title =. Proceedings of the 48th Annual. 2016 , doi =

    2016

  69. [72]

    PRX Quantum , volume =

    Jerry Huang and Laura Lewis and Hsin-Yuan Huang and John Preskill , title =. PRX Quantum , volume =. 2026 , doi =

    2026

  70. [73]

    arXiv preprint arXiv:2407.13874 , year =

    Sitan Chen and Jerry Li and Allen Liu , title =. arXiv preprint arXiv:2407.13874 , year =

    Pith/arXiv arXiv

  71. [74]

    Proceedings of the 58th Annual

    Angelos Pelecanos and Jack Spilecki and John Wright , title =. Proceedings of the 58th Annual. 2026 , doi =

    2026

  72. [75]

    Explore first, exploit next: The true shape of regret in bandit problems , journal =

    Aur. Explore first, exploit next: The true shape of regret in bandit problems , journal =. 2019 , doi =

    2019

  73. [76]

    Machine Learning , volume =

    David McAllester , title =. Machine Learning , volume =. 2003 , doi =

    2003

  74. [77]

    IEEE Transactions on Information Theory , volume =

    Aolin Xu and Maxim Raginsky , title =. IEEE Transactions on Information Theory , volume =. 2022 , doi =

    2022

  75. [78]

    Advances in Neural Information Processing Systems 33 , pages =

    Hassan Hafez-Kolahi and Zeinab Golgooni and Shohreh Kasaei and Mahdieh Soleymani , title =. Advances in Neural Information Processing Systems 33 , pages =. 2020 , doi =

    2020

  76. [79]

    Proceedings of the 38th International Conference on Machine Learning , series =

    Hassan Hafez-Kolahi and Behrad Moniri and Shohreh Kasaei and Mahdieh Soleymani Baghshah , title =. Proceedings of the 38th International Conference on Machine Learning , series =

  77. [80]

    IEEE Transactions on Information Theory , volume =

    Hassan Hafez-Kolahi and Behrad Moniri and Shohreh Kasaei , title =. IEEE Transactions on Information Theory , volume =. 2023 , doi =

    2023

  78. [81]

    Journal of Machine Learning Research , volume =

    Daniel Russo and Benjamin Van Roy , title =. Journal of Machine Learning Research , volume =

  79. [82]

    Nature Physics , volume =

    Hsin-Yuan Huang and Richard Kueng and John Preskill , title =. Nature Physics , volume =. 2020 , doi =

    2020

  80. [83]

    Proceedings of the 65th Annual

    Sitan Chen and Weiyuan Gong and Qi Ye , title =. Proceedings of the 65th Annual. 2024 , doi =

    2024

Showing first 80 references.