Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

This paper gives a matrix learning-from-expert-advice algorithm whose regret is O(sqrt(T S(X||d^{-1}I_d))) for every comparator X, at the same time and memory cost as the standard matrix multiplicative weight update.

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 ↗

A new potential-based algorithm achieves instance-optimal O(sqrt(T·S(X||I/d))) regret for matrix LEA with the same complexity as MMWU, using a one-sided Jensen trace inequality.

T0 review reviewed 2026-08-04 challenge →

load-bearing objection Novel technique, but the central reduction is broken by a normalization mismatch; likely fixable, but not publishable as is. the 2 major comments →

arxiv 2509.08911 v1 pith:X54CEM5B submitted 2025-09-10 cs.LG cs.AIcs.DSquant-phstat.ML

Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications

Weiyuan Gong , Tongyang Li , Xinzhao Wang , Zhiyu Zhang This is my paper
classification cs.LG cs.AIcs.DSquant-phstat.ML
keywords matrix multiplicative weight updateinstance-optimal regretpotential methodone-sided Jensen's trace inequalityLaplace transformquantum relative entropyonline learning of quantum statesparameter-free online learning
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.

The reading

The paper targets the matrix analogue of the classic "learning from expert advice" problem, played on the spectraplex of unit-trace positive semidefinite matrices. The standard matrix multiplicative weight update (MMWU) achieves worst-case optimal regret O(sqrt(T log d)), independent of the comparator X. This paper constructs an algorithm whose regret is instead O(sqrt(T S(X||d^{-1}I_d))), where S(·||·) is quantum relative entropy, so comparators closer to the maximally mixed state are learned faster. The improvement is "free" in that time and memory complexity match MMWU, and the paper proves a matching regret lower bound up to constants. The technique extends potential-based parameter-free online learning to noncommuting matrices through a new one-sided Jensen trace inequality.

Core claim

The central result (Theorem 23) is that a potential-based algorithm, using the imaginary-error-function potential and a reduction from the spectraplex to all Hermitian matrices, achieves regret at most l sqrt(T)[sqrt(8 S(X||d^{-1}I_d)) + 6 + 2 sqrt(2)] for every T>=1 and every unit-trace PSD comparator X, where l bounds the operator norm of each loss matrix. Since S(X||d^{-1}I_d) <= log d, this is never worse than the minimax-optimal O(sqrt(T log d)) bound and improves when X is close to the maximally mixed state. The paper also gives a matching regret lower bound up to constants, a memory lower bound of Omega(d^2) for sublinear regret, and shows that the algorithm's time and memory complexi

What carries the argument

The load-bearing device is a one-sided Jensen trace inequality: for a function Phi whose second derivative is a two-sided Laplace transform of a nonnegative function, Tr[Phi(S-G)] <= Tr[((epsilon I-G)/2epsilon)Phi(S+epsilon I) + ((epsilon I+G)/2epsilon)Phi(S-epsilon I)] for Hermitian S,G with ||G||_op <= epsilon. The standard two-sided Jensen trace inequality does not imply this; |x| is a counterexample. The paper proves the erfi potential satisfies the condition because its second derivative is the exp-square potential, and that potential is the Gaussian Laplace transform of a nonnegative density. The Fenchel conjugate of the erfi potential then converts the potential bound into the relativ

Load-bearing premise

The regret bound rests on the one-sided Jensen trace inequality holding for the erfi potential; the paper verifies it through a sufficient condition (the potential's second derivative is a nonnegative Laplace transform) but does not prove necessity, and the inequality fails for some convex functions such as |x|.

What would settle it

Search the 2x2 Hermitian space for S and G with ||G||_op <= 2l and fixed t such that Tr[Phi_erfi_t(S-G)] exceeds Tr[((2lI-G)/4l)Phi_erfi_t(S+2lI) + ((2lI+G)/4l)Phi_erfi_t(S-2lI)]. The paper's Theorem 14 guarantees no such pair exists; any concrete violation is a direct computational refutation of the main regret bound.

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

If this is right

  • For comparators with S(X||d^{-1}I_d)=O(1), regret becomes O(sqrt(T)) instead of O(sqrt(T log d)), a saving that can be exponential in auxiliary parameters when d is large, as in quantum information.
  • The algorithm is parameter-free: no learning rate eta needs to be tuned, unlike the standard MMWU bound which would require oracle knowledge of the comparator to reach the same guarantee.
  • Applied to online convex optimization with Lipschitz losses, the algorithm gives relative-entropy-dependent regret for online quantum state learning, including improved rates for depolarized states, random product states, subsystems of Haar random states, and Gibbs states.
  • Nonlinear predictions such as purity/quantum virtual cooling and Renyi-2 correlation inherit the same relative-entropy regret bound.
  • The Omega(d^2) memory lower bound for sublinear regret means the algorithm's d^2 memory cost is optimal among all matrix LEA algorithms.

Where Pith is reading between the lines

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

  • Editorial inference: if the conjecture that the one-sided inequality holds for all even-degree monomials is true, the Laplace-transform sufficient condition is not necessary, and many more potentials such as exp(x^2) would become admissible, likely simplifying parameter-free matrix algorithms and connecting them to disentanglement inequalities.
  • Editorial inference: the Gaussian-ensemble interpretation suggests a testable design principle: replace the Gaussian prior over learning rates by other priors to obtain different comparator-dependent regret tradeoffs, a direction the paper leaves open.
  • Editorial inference: the packing-based memory lower bound should transfer to constrained quantum state classes, such as rank-r states or bounded-gate states, giving memory-regret tradeoffs in those settings beyond the two examples the paper lists.
  • Editorial inference: because noise and randomness reduce quantum relative entropy, the same algorithm likely gives instance-dependent benefits for online learning of quantum processes under depolarizing or average-case noise, not only states.
Share X Bluesky LinkedIn Reddit HN

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

2 major / 4 minor

Summary. The paper proposes a potential-based algorithm for matrix LEA on the spectraplex, claiming an instance-optimal regret bound O(sqrt(T S(X || d^{-1} I_d))) while retaining the computational complexity of MMWU. The main technical novelty is a one-sided Jensen trace inequality, proved under a Laplace-transform condition on the potential's second derivative, and applied to the erfi potential from the vector parameter-free online learning literature. The paper also gives a regret lower bound, a memory lower bound, and applications to online learning of noisy, random, and Gibbs quantum states, as well as nonlinear quantum properties.

Significance. If the main theorem were established, this would be a significant contribution: it would give the first comparator-adaptive matrix LEA algorithm with the same per-iteration cost as MMWU, introduce a useful new matrix trace inequality, and yield a suite of improved guarantees for quantum state learning. The paper is also unusually careful in several places: Theorem 14 and the master regret bound Theorem 20 are clean and self-contained, and the paper explicitly identifies the nontriviality of the one-sided Jensen inequality with a counterexample. However, the claimed reduction behind the main theorem is not proved for the algorithm as stated; this is a load-bearing issue that must be fixed before the central claim can be accepted.

major comments (2)
  1. [§4 (Algorithm 1) and Appendix B.1 (Lemma 19)] The reduction lemma is not proved for the algorithm as published. Algorithm 1 defines U_t with trace normalization (denominator |Σ_i min{0,λ_i}|), while the proof of Lemma 19 in Appendix B.1 uses U_t = (\tilde X_t - X_t^+)/||\tilde X_t - X_t^+||_F. The reader's 3×3 example is valid: with \tilde X_t = diag(-1,-2,3) and G_t = diag(1,1,-1), one gets X_t = diag(0,0,1), \bar G_t = diag(2,2,0), U_t = diag(-1/3,-2/3,0), and \tilde G_t = diag(4/3,2/3,0). For X = diag(1/3,1/3,1/3), Lemma 19 would require -4/3 ≤ -10/3, which is false. Thus Theorem 23's bound, which relies on Lemma 19 to lift the unconstrained regret to the spectraplex, is not established for the algorithm as stated. The natural fix is to normalize U_t by the Frobenius norm and then reprove Lemma 19; the authors should state and verify this explicitly.
  2. [Appendix B.1, Lemma 19, first condition] The proof of the first condition asserts that \|\tilde G_t\|_{op} ≤ \|\bar G_t\|_{op} because \tilde G_t is either \bar G_t or its projection to a subspace. This is not justified: the projection is in the Frobenius inner product, so it gives a Frobenius-norm bound, not an operator-norm bound. The bound \|\tilde G_t\|_{op} ≤ 2\|G_t\|_{op} is load-bearing, since the unconstrained algorithm (Algorithm 2) is run with ε = 2l. This step needs a genuine argument, especially after renormalizing U_t by the Frobenius norm, where one only has \|U_t\|_F = 1 and \|U_t\|_{op} ≤ 1.
minor comments (4)
  1. [§5.2, proof of Theorem 27] The union bound appears to be misstated: the text says 'with probability at least 1 − 2^m |P| ≥ 0.9', but the correct expression is 1 − 2^m / |P| ≥ 0.9. As written, 2^m |P| is enormous and gives a meaningless probability.
  2. [§4, Algorithm 1] The denominator |Σ_i min{0,λ_i}| should be identified as the trace norm of the negative part; the absolute-value-of-scalar notation is ambiguous and contributes to the normalization confusion.
  3. [Theorem 20] The statement contains the typo 'for all T∈≥ 2'; it should read 'for all T ≥ 2'.
  4. [§4.2, around Eq. (20)] The erfi potential is attributed to Ref. [53], but its first-condition verification is attributed to Ref. [52, Lemma 3.10]. A one-line clarification of the relation between these references would help the reader.

Circularity Check

0 steps flagged

No circularity found: the matrix LEA regret bound is derived from a new trace inequality and independently published scalar potential analysis.

full rationale

The paper's central claim (Theorem 23) is not an input renamed as an output. The potential-method master theorem (Theorem 20) derives a regret bound from two conditions: a scalar evanescent condition (17) and the one-sided Jensen trace inequality (18). The scalar condition and the Fenchel conjugate for the erfi potential are imported from prior published work ([52, 53, 114]); although [114] shares a coauthor, those are external theorems with scalar assumptions that do not include the matrix LEA result, so they are independent support rather than circular input. The matrix-specific content — Theorem 14's Laplace-transform sufficient condition, Lemma 21's Gaussian representation, and the reduction in Lemma 19 — is proved in the paper from Golden-Thompson, Fubini, and elementary trace identities; it does not assume the regret bound. The final bound then follows by summing and convex duality, with no step where the predicted quantity is defined in terms of itself or fitted to the comparator. I note for completeness an internal normalization mismatch in the proof of Lemma 19 (Algorithm 1 uses trace-normalized U_t while the proof substitutes a Frobenius-normalized version); this is a correctness/rigor concern, not a circularity, and does not change the circularity score.

Axiom & Free-Parameter Ledger

0 free parameters · 7 axioms · 0 invented entities

The central theorem relies on standard matrix analysis and on two external results for the erfi potential (propagation inequality and Fenchel conjugate). The quantum applications add standard quantum-information facts (strong data processing inequality, Page formula, random matrix bounds). No fitted parameters or invented entities appear.

axioms (7)
  • standard math Golden-Thompson inequality: Tr[exp(A+B)] <= Tr[exp A exp B] for Hermitian A,B.
    Used in Lemma 13 to establish the one-sided Jensen inequality for exponential functions.
  • standard math von Neumann trace inequality: for Hermitian A,B with sorted eigenvalues, Tr[AB] <= sum lambda_i lambda'_i.
    Used in Theorem 20 to convert a matrix supremum into a sum of scalar Fenchel conjugates.
  • standard math The erfi and exp-square potentials satisfy the one-dimensional propagation inequality 1/2[Phi_{t+1}(s+eps)+Phi_{t+1}(s-eps)] <= Phi_t(s).
    Taken from Ref. [52, Lemma 3.10] and [114, Lemma B.3]; required by Theorem 20.
  • standard math Fenchel conjugate bound for the erfi potential: Phi_T^{erfi,*}(lambda) <= eps sqrt(T)[d^{-1} + sqrt(2 lambda)(sqrt(log(1+lambda/(sqrt(2) d^{-1}))) + 1)].
    Quoted from Ref. [114, Theorem 4]; it converts the potential bound into the final regret expression.
  • domain assumption Strong data processing inequality for depolarizing channels: S(Phi(rho)||I/d) <= (1-gamma)^2 S(rho||I/d) per layer of local depolarizing noise with rate gamma.
    Used in Corollary 29 to bound the regret for noisy quantum circuits; cited to Refs. [56,93].
  • domain assumption Page formula: a d-dimensional subsystem of a Haar random state of dimension d' has average von Neumann entropy log d - O(d/d') for d << d'.
    Used in Corollary 30 for random states; standard quantum information result.
  • domain assumption Random Hamiltonian norm bounds: ||H_gue|| <= 3 and ||H_RSPS|| <= 3 with probability 1-exp(-Theta(n)).
    Used in Corollary 33 to bound relative entropy of Gibbs states; cited to Refs. [31,28].

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications." pith.science (2026). https://pith.science/paper/X54CEM5B

@misc{pith2026250908911,
  author       = {Pith},
  title        = {Pith review of: Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X54CEM5B}},
  note         = {Machine review of arXiv:2509.08911}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The Matrix Multiplicative Weight Update (MMWU) is a seminal online learning algorithm with numerous applications. Applied to the matrix version of the Learning from Expert Advice (LEA) problem on the $d$-dimensional spectraplex, it is well known that MMWU achieves the minimax-optimal regret bound of $O(\sqrt{T\log d})$, where $T$ is the time horizon. In this paper, we present an improved algorithm achieving the instance-optimal regret bound of $O(\sqrt{T\cdot S(X||d^{-1}I_d)})$, where $X$ is the comparator in the regret, $I_d$ is the identity matrix, and $S(\cdot||\cdot)$ denotes the quantum relative entropy. Furthermore, our algorithm has the same computational complexity as MMWU, indicating that the improvement in the regret bound is ``free''. Technically, we first develop a general potential-based framework for matrix LEA, with MMWU being its special case induced by the standard exponential potential. Then, the crux of our analysis is a new ``one-sided'' Jensen's trace inequality built on a Laplace transform technique, which allows the application of general potential functions beyond exponential to matrix LEA. Our algorithm is finally induced by an optimal potential function from the vector LEA problem, based on the imaginary error function. Complementing the above, we provide a memory lower bound for matrix LEA, and explore the applications of our algorithm in quantum learning theory. We show that it outperforms the state of the art for learning quantum states corrupted by depolarization noise, random quantum states, and Gibbs states. In addition, applying our algorithm to linearized convex losses enables predicting nonlinear quantum properties, such as purity, quantum virtual cooling, and R\'{e}nyi-$2$ correlation.

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Coherent Swap Regret and Channel-Proof Learning

    quant-ph 2026-06 unverdicted novelty 7.0

    Introduces coherent swap regret against local CPTP maps and proves a three-level landscape where non-unital measurement-preparation channels force Theta(sqrt(d T log d)) minimax regret while unital channels have zero regret.

Reference graph

Works this paper leans on

119 extracted references · 12 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Shadow tomography of quantum states

    Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 325--338, 2018

    2018

  2. [2]

    Online learning of quantum states

    Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. Online learning of quantum states. Advances in Neural Information Processing Systems , 31, 2018

    2018

  3. [3]

    Rothblum

    Scott Aaronson and Guy N. Rothblum. Gentle measurement of quantum states and differential privacy. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 322--333, 2019

    2019

  4. [4]

    A polynomial-time classical algorithm for noisy random circuit sampling

    Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 945--957, 2023

    2023

  5. [5]

    Some bounds for expected values of order statistics

    Mir M Ali and Lai K Chan. Some bounds for expected values of order statistics. The Annals of Mathematical Statistics , pages 1055--1057, 1965

    1965

  6. [6]

    Follow the compressed leader: Faster online learning of eigenvectors and faster MMWU

    Zeyuan Allen-Zhu and Yuanzhi Li. Follow the compressed leader: Faster online learning of eigenvectors and faster MMWU . In International Conference on Machine Learning , pages 116--125. PMLR, 2017

    2017

  7. [7]

    Spectral sparsification and regret minimization beyond matrix multiplicative updates

    Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the 47th Annual ACM SIGACT Symposium on Theory of Computing , pages 237--245, 2015

    2015

  8. [8]

    Anderson, Alice Guionnet, and Ofer Zeitouni

    Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction to random matrices . Cambridge University Press, 2010

    2010

  9. [9]

    A survey on the complexity of learning quantum states

    Anurag Anshu and Srinivasan Arunachalam. A survey on the complexity of learning quantum states. Nature Reviews Physics , 6(1):59--69, 2024

    2024

  10. [10]

    A combinatorial, primal-dual approach to semidefinite programs

    Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the 39th Annual ACM SIGACT Symposium on Theory of Computing , pages 227--236, 2007

    2007

  11. [11]

    Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G

    Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, St...

    2019

  12. [12]

    Improved quantum data analysis

    Costin B a descu and Ryan O'Donnell. Improved quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 1398--1411, 2021

    2021

  13. [13]

    Bandeira, March T

    Afonso S. Bandeira, March T. Boedihardjo, and Ramon van Handel. Matrix concentration inequalities and free probability. Inventiones Mathematicae , 234(1):419--487, 2023

    2023

  14. [14]

    Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time

    Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava. Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time. Foundations of Computational Mathematics , 23(6):1959--2047, 2023

    1959

  15. [15]

    Online learning of a panoply of quantum objects

    Akshay Bansal, Ian George, Soumik Ghosh, Jamie Sikora, and Alice Zheng. Online learning of a panoply of quantum objects. Quantum Machine Intelligence , 7(2):1--22, 2025

    2025

  16. [16]

    Boyd and Lieven Vandenberghe

    Stephen P. Boyd and Lieven Vandenberghe. Convex optimization . Cambridge University Press, 2004

    2004

  17. [17]

    Universality and sharp matrix concentration inequalities

    Tatiana Brailovskaya and Ramon van Handel. Universality and sharp matrix concentration inequalities. Geometric and Functional Analysis , 34(6):1734--1838, 2024

    2024

  18. [18]

    Brand \ a o, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M Svore, and Xiaodi Wu

    Fernando G.S.L. Brand \ a o, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M Svore, and Xiaodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming , pages 27--1, 2019

    2019

  19. [19]

    Brandao, Richard Kueng, and Daniel Stilck Fran c a

    Fernando G.S.L. Brandao, Richard Kueng, and Daniel Stilck Fran c a. Faster quantum and classical SDP approximations for quadratic binary optimization. Quantum , 6:625, 2022

    2022

  20. [20]

    Fernando GSL Brandao and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science , pages 415--426. IEEE, 2017

    2017

  21. [21]

    Lanyon, Peter Zoller, Rainer Blatt, and Christian F

    Tiff Brydges, Andreas Elben, Petar Jurcevic, Beno \^ t Vermersch, Christine Maier, Ben P. Lanyon, Peter Zoller, Rainer Blatt, and Christian F. Roos. Probing R \'e nyi entanglement entropy via randomized measurements. Science , 364(6437):260--263, 2019

    2019

  22. [22]

    Benjamin, Suguru Endo, William J

    Zhenyu Cai, Ryan Babbush, Simon C. Benjamin, Suguru Endo, William J. Huggins, Ying Li, Jarrod R. McClean, and Thomas E. O’Brien. Quantum error mitigation. Reviews of Modern Physics , 95(4):045005, 2023

    2023

  23. [23]

    Duchi, Sidford Aaron, and Tian Kevin

    Yair Carmon, John C. Duchi, Sidford Aaron, and Tian Kevin. A rank-1 sketch for matrix multiplicative weights. In Conference on Learning Theory , pages 589--623. PMLR, 2019

    2019

  24. [24]

    Helmbold, Robert E

    Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM , 44(3):427--485, 1997

    1997

  25. [25]

    Prediction, learning, and games

    Nicolo Cesa-Bianchi and G \'a bor Lugosi. Prediction, learning, and games . Cambridge University Press, 2006

    2006

  26. [26]

    A parameter-free hedging algorithm

    Kamalika Chaudhuri, Yoav Freund, and Daniel J Hsu. A parameter-free hedging algorithm. Advances in Neural Information Processing Systems , 22, 2009

    2009

  27. [27]

    Quantum G ibbs Sampling

    Chi-Fang Chen. Quantum G ibbs Sampling . PhD thesis, California Institute of Technology, 2025

    2025

  28. [28]

    Dalzell, Mario Berta, Fernando GSL Brand \ a o, and Joel A

    Chi-Fang Chen, Alexander M. Dalzell, Mario Berta, Fernando GSL Brand \ a o, and Joel A. Tropp. Sparse random H amiltonians are quantumly easy. Physical Review X , 14(1):011014, 2024

    2024

  29. [29]

    Impossible tuning made possible: A new expert algorithm and its applications

    Liyu Chen, Haipeng Luo, and Chen-Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory , pages 1216--1259. PMLR, 2021

    2021

  30. [30]

    Efficient P auli channel estimation with logarithmic quantum memory

    Sitan Chen and Weiyuan Gong. Efficient P auli channel estimation with logarithmic quantum memory. PRX Quantum , 6(2):020323, 2025

    2025

  31. [31]

    Information-computation gaps in quantum learning via low-degree likelihood

    Sitan Chen, Weiyuan Gong, Jonas Haferkamp, and Yihui Quek. Information-computation gaps in quantum learning via low-degree likelihood. arXiv:2505.22743 , 2025

    Pith/arXiv arXiv 2025

  32. [32]

    Adaptive online learning of quantum states

    Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang, and Rui Yang. Adaptive online learning of quantum states. Quantum , 8:1471, 2024

    2024

  33. [33]

    More practical and adaptive algorithms for online quantum state learning

    Yifang Chen and Xin Wang. More practical and adaptive algorithms for online quantum state learning. arXiv:2006.01013 , 2020

    Pith/arXiv arXiv 2006

  34. [34]

    Prediction with advice of unknown number of experts

    Alexey Chernov and Vladimir Vovk. Prediction with advice of unknown number of experts. In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence , pages 117--125, 2010

    2010

  35. [35]

    Quantum algorithms for gibbs sampling and hitting-time estimation

    Anirban Narayan Chowdhury and Rolando D Somma. Quantum algorithms for gibbs sampling and hitting-time estimation. Quantum Information & Computation , 17(1-2):41--64, 2017

    2017

  36. [36]

    Eric Tai, Matthew Rispoli, Robert Schittko, Philipp M

    Jordan Cotler, Soonwon Choi, Alexander Lukin, Hrant Gharibyan, Tarun Grover, M. Eric Tai, Matthew Rispoli, Robert Schittko, Philipp M. Preiss, Adam M. Kaufman, Markus Greiner, Hannes Pichler, and Patrick Hayden. Quantum virtual cooling. Physical Review X , 9(3):031013, 2019

    2019

  37. [37]

    Fully unconstrained online learning

    Ashok Cutkosky and Zak Mhammedi. Fully unconstrained online learning. Advances in Neural Information Processing Systems , 37:10148--10201, 2024

    2024

  38. [38]

    Black-box reductions for parameter-free online learning in B anach spaces

    Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in B anach spaces. In Conference on Learning Theory , pages 1493--1529. PMLR, 2018

    2018

  39. [39]

    Order statistics

    Herbert A David and Haikady N Nagaraja. Order statistics . John Wiley & Sons, 2004

    2004

  40. [40]

    Quantum certification and benchmarking

    Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking. Nature Reviews Physics , 2(7):382--390, 2020

    2020

  41. [41]

    Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Beno \^ t Vermersch, and Peter Zoller

    Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Beno \^ t Vermersch, and Peter Zoller. The randomized measurement toolbox. Nature Reviews Physics , 5(1):9--24, 2023

    2023

  42. [42]

    Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan

    Dylan J. Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter-free online learning via model selection. Advances in Neural Information Processing Systems , 30, 2017

    2017

  43. [43]

    Foster, Alexander Rakhlin, and Karthik Sridharan

    Dylan J. Foster, Alexander Rakhlin, and Karthik Sridharan. Adaptive online learning. Advances in Neural Information Processing Systems , 28, 2015

    2015

  44. [44]

    Online learning: Sufficient statistics and the B urkholder method

    Dylan J Foster, Alexander Rakhlin, and Karthik Sridharan. Online learning: Sufficient statistics and the B urkholder method. In Conference On Learning Theory , pages 3028--3064. PMLR, 2018

    2018

  45. [45]

    Advances in quantum metrology

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Advances in quantum metrology. Nature Photonics , 5(4):222--229, 2011

    2011

  46. [46]

    Lower bounds for the H elmholtz function

    Sidney Golden. Lower bounds for the H elmholtz function. Physical Review , 137(4B):B1127, 1965

    1965

  47. [47]

    Learning distributions over quantum measurement outcomes

    Weiyuan Gong and Scott Aaronson. Learning distributions over quantum measurement outcomes. In International Conference on Machine Learning , pages 11598--11613. PMLR, 2023

    2023

  48. [48]

    On the sample complexity of purity and inner product estimation

    Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. On the sample complexity of purity and inner product estimation. arXiv:2410.12712 , 2024

    Pith/arXiv arXiv 2024

  49. [49]

    Robert D. Gordon. Values of M ills' ratio of area to bounding ordinate and of the normal probability integral for large values of the argument. The Annals of Mathematical Statistics , 12(3):364--366, 1941

    1941

  50. [50]

    Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu

    Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing , pages 913--925, 2016

    2016

  51. [51]

    Pedersen

    Frank Hansen and Gert K. Pedersen. Jensen's operator inequality. Bulletin of the London Mathematical Society , 35(4):553--564, 2003

    2003

  52. [52]

    Optimal anytime regret with two experts

    Nicholas JA Harvey, Christopher Liaw, Edwin Perkins, and Sikander Randhawa. Optimal anytime regret with two experts. Mathematical Statistics and Learning , 6(1):87--142, 2023

    2023

  53. [53]

    Optimal anytime regret for two experts

    Nicholas JA Harvey, Christopher Liaw, Edwin A Perkins, and Sikander Randhawa. Optimal anytime regret for two experts. In Proceedings of the 61st Annual Symposium on Foundations of Computer Science , pages 1404--1415. IEEE, 2020

    2020

  54. [54]

    Continuous prediction with experts' advice

    Nicholas JA Harvey, Christopher Liaw, and Victor S Portella. Continuous prediction with experts' advice. Journal of Machine Learning Research , 25(228):1--32, 2024

    2024

  55. [55]

    Introduction to online convex optimization

    Elad Hazan. Introduction to online convex optimization. arXiv:1909.05207v3 , 2023

    Pith/arXiv arXiv 1909

  56. [56]

    On contraction coefficients, partial orders and approximation of capacities for quantum channels

    Christoph Hirche, Cambyse Rouz \' e , and Daniel Stilck Fran c a. On contraction coefficients, partial orders and approximation of capacities for quantum channels. Quantum , 6:862, 2022. https://doi.org/10.22331/q-2022-11-28-862 doi:10.22331/q-2022-11-28-862

    doi:10.22331/q-2022-11-28-862 2022

  57. [57]

    Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean. Quantum advantage in learning from experiments. Science , 376(6598):1182--1186, 2022

    2022

  58. [58]

    Predicting many properties of a quantum system from very few measurements

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics , 16(10):1050--1057, 2020

    2020

  59. [59]

    Huggins, Sam McArdle, Thomas E

    William J. Huggins, Sam McArdle, Thomas E. O’Brien, Joonho Lee, Nicholas C. Rubin, Sergio Boixo, K. Birgitta Whaley, Ryan Babbush, and Jarrod R. McClean. Virtual distillation for quantum error mitigation. Physical Review X , 11(4):041036, 2021

    2021

  60. [60]

    Preiss, M

    Rajibul Islam, Ruichao Ma, Philipp M. Preiss, M. Eric Tai, Alexander Lukin, Matthew Rispoli, and Markus Greiner. Measuring entanglement entropy in a quantum many-body system. Nature , 528(7580):77--83, 2015

    2015

  61. [61]

    Pseudorandom quantum states

    Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Annual International Cryptology Conference , pages 126--152. Springer, 2018

    2018

  62. [62]

    Kastoryano and Fernando G.S.L

    Michael J. Kastoryano and Fernando G.S.L. Brandao. Quantum gibbs samplers: The commuting case. Communications in Mathematical Physics , 344(3):915--957, 2016

    2016

  63. [63]

    Eric Tai, Alexander Lukin, Matthew Rispoli, Robert Schittko, Philipp M

    Adam M Kaufman, M. Eric Tai, Alexander Lukin, Matthew Rispoli, Robert Schittko, Philipp M. Preiss, and Markus Greiner. Quantum thermalization through entanglement in an isolated many-body system. Science , 353(6301):794--800, 2016

    2016

  64. [64]

    Exponential error suppression for near-term quantum devices

    B \'a lint Koczor. Exponential error suppression for near-term quantum devices. Physical Review X , 11(3):031057, 2021

    2021

  65. [65]

    Koolen and Tim Van Erven

    Wouter M. Koolen and Tim Van Erven. Second-order quantile methods for experts and combinatorial games. In Conference on Learning Theory , pages 1155--1175. PMLR, 2015

    2015

  66. [66]

    Dima Kuzmin and Manfred K. Warmuth. Online kernel PCA with entropic matrix updates. In International Conference on Machine Learning , pages 465--472, 2007

    2007

  67. [67]

    Lecture 3: Golden-thompson and the frobenius inner product

    James R Lee. Lecture 3: Golden-thompson and the frobenius inner product. https://homes.cs.washington.edu/ jrl/teaching/cse599Isp21/notes/lecture3.pdf, 2021

    2021

  68. [68]

    Lessa, Ruochen Ma, Jian-Hao Zhang, Zhen Bi, Meng Cheng, and Chong Wang

    Leonardo A. Lessa, Ruochen Ma, Jian-Hao Zhang, Zhen Bi, Meng Cheng, and Chong Wang. Strong-to-weak spontaneous symmetry breaking in mixed quantum states. PRX Quantum , 6(1):010344, 2025

    2025

  69. [69]

    Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation , 108(2):212--261, 1994

    1994

  70. [70]

    Exponential separations between quantum learning with and without purification

    Zhenhuan Liu, Weiyuan Gong, Zhenyu Du, and Zhenyu Cai. Exponential separations between quantum learning with and without purification. arXiv:2410.17718 , 2024

    Pith/arXiv arXiv 2024

  71. [71]

    Quantum principal component analysis

    Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics , 10(9):631--633, 2014

    2014

  72. [72]

    Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states

    Josep Lumbreras, Erkka Haapasalo, and Marco Tomamichel. Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states. Quantum , 6:749, 2022

    2022

  73. [73]

    Schapire

    Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: Adanormalhedge. In Conference on Learning Theory , pages 1286--1304. PMLR, 2015

    2015

  74. [74]

    Minimax optimal algorithms for unconstrained linear optimization

    Brendan McMahan and Jacob Abernethy. Minimax optimal algorithms for unconstrained linear optimization. Advances in Neural Information Processing Systems , 26:2724--2732, 2013

    2013

  75. [75]

    Unconstrained online linear learning in H ilbert spaces: Minimax algorithms and normal approximations

    Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in H ilbert spaces: Minimax algorithms and normal approximations. In Conference on Learning Theory , pages 1020--1039. PMLR, 2014

    2014

  76. [76]

    Introduction to H aar measure tools in quantum information: A beginner's tutorial

    Antonio Anna Mele. Introduction to H aar measure tools in quantum information: A beginner's tutorial. Quantum , 8:1340, 2024

    2024

  77. [77]

    Zakaria Mhammedi and Wouter M. Koolen. Lipschitz and comparator-norm adaptivity in online learning. In Conference on Learning Theory , pages 2858--2887. PMLR, 2020

    2020

  78. [78]

    A trace inequality of J ohn von N eumann

    Leon Mirsky. A trace inequality of J ohn von N eumann. Monatshefte f \"u r mathematik , 79(4):303--306, 1975

    1975

  79. [79]

    Quantum speedup of Monte Carlo methods

    Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 471(2181):20150301, 2015

    2015

  80. [80]

    Tan, Matthew J

    Mario Motta, Chong Sun, Adrian T.K. Tan, Matthew J. O’Rourke, Erika Ye, Austin J Minnich, Fernando G.S.L. Brandao, and Garnet Kin-Lic Chan. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics , 16(2):205--210, 2020

    2020

Showing first 80 references.

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.