Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Online Quantum State Tomography via Stochastic Gradient Descent

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper introduces online quantum state tomography, where a rank-r density matrix is recovered by updating a factored estimate with mini-batch SGD from a small batch of random local Pauli measurements per round; the main result is…

desk verdict Solid local convergence analysis, but the advertised sample complexity is wrong by a d/ε² factor once you count the shots required per Pauli setting. read the letter →

arxiv 2507.07601 v1 pith:RLMYSDUT submitted 2025-07-10 quant-ph

Jian-Feng Cai , Yuling Jiao , Yinan Li , Xiliang Lu , Jerry Zhijian Yang , Juntao You This is my paper · ORCID
classification quant-ph MSC 81P1881P4565K1090C26
keywords onlinequantumstatetomographylow-rankmini-batchstochasticgradientdescentlocalPaulimeasurementslinearconvergencenon-convexoptimizationsamplecomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Quantum state tomography usually waits until many copies of a state have been measured and then solves one large reconstruction problem. This paper asks whether a state can instead be reconstructed online: each round the experimenter performs a small batch of random local Pauli measurements and immediately updates a low-rank factored estimate by one stochastic gradient step. The paper proves that, provided the initial estimate lies in a small Frobenius-neighborhood of the true state, this online SGD converges linearly both in expectation and with high probability, reaching any target accuracy with nearly optimal sample complexity. The proof does not rely on restricted-isometry bounds; it works from local smoothness and local curvature of the factored squared-loss. The practical consequence is that measurement and classical computation can run simultaneously, and the total time complexity improves on offline non-convex QST algorithms in its rank and log-dimension dependence.

What carries the argument

The load-bearing object is the contraction region $E(\rho_*, \delta) = \{U : \|U U^\dagger - \rho_*\|_F \le \delta\}$ together with two local inequalities for the factored squared loss. Lemma 3 shows that inside this region the loss has positive curvature along the relevant directions: $\langle (U U^\dagger - \rho_*) U U^\dagger, U U^\dagger - \rho_* \rangle \ge \frac{1}{2}(1-\delta)^2\sigma_r^* \|U U^\dagger - \rho_*\|_F^2$, which yields the regularity term in the contraction. Lemma 2 supplies a local smoothness bound for the same loss, so the stochastic gradient variance can be controlled by the current error. The proof converts these local inequalities into a one-step contraction of the expected squared error, then uses a supermartingale argument with a variance bound to obtain the high-probability convergence theorem.

What would settle it

Run Algorithm 3 on a rank-$2$ state with $\kappa \le \sqrt{dr}$, initialize at $\|U_0 U_0^\dagger - \rho_*\|_F = 2\sigma_r^*/3$ (outside $E$), and use the paper's prescribed learning rate and batch size; if the error still decreases linearly from the first round, the local-region premise is not necessary for the observed behavior, whereas a plateau or slowdown until the iterate crosses into $E$ would confirm it.

Watch

Extended reading notes

Core claim

The central claim is that local regularity of the loss function $f(U) = \|U U^\dagger - \rho_*\|_F^2$ forces contraction of the mini-batch SGD iteration $U_t = U_{t-1} - \eta \nabla \ell_t(U_{t-1})$. The paper establishes a lower bound on the expected gradient alignment and an upper bound on the gradient variance inside the contraction region $E(\rho_*, \sigma_r^*/3)$, and then combines them into the conditional expectation bound $E[e_{t+1}^2 \mid \mathcal{F}_t] \le (1-\eta B/(2\kappa d)) e_t^2 + \eta B\varepsilon_0^2/(8\kappa d)$ and the high-probability bound $e_t^2 \le 2(1-\eta B/(4\kappa d))^t e_0^2 + [1-(1-\eta B/(4d\kappa))^t]\varepsilon_0^2$ for at least $1-3T/d^{10}$. In words, each round with $B$ random Pauli measurements shrinks the Frobenius error by a constant factor while accumulating a statistical-noise floor controlled by the number of shots. The paper reports per-round cost $O(B r d \log d)$, total rounds $O(B^{-1}\kappa^2 r d \log d \log(1/\varepsilon))$, and total time $O(\kappa^2 r^2 d^2 \log^2 d \log(1/\varepsilon))$, which it compares favorably with the ProjFGD/MiFGD and Riemannian gradient descent complexity of $O(\kappa^{2+\alpha} r^3 d^2 \log^7 d \log(1/\varepsilon))$ and $O(\kappa^2 r^3 d^2 \log^7 d \log(1/\kappa\varepsilon))$.

Load-bearing premise

The whole guarantee rests on the initial estimate already lying in the contraction region $E(\rho_*, \sigma_r^*/3)$, a constant-fraction-of-smallest-eigenvalue neighborhood of the true state; for rank $r>1$ the paper does not prove an online way to reach that region and instead cites an offline spectral initialization.

Editorial extensions

If this is right

  • Reconstruction can be interleaved with measurement: the classical update for round $t$ uses only the $B$ outcomes just collected, so the experimenter can prepare the next measurement setting while the computer updates the estimate.
  • No RIP-type batch condition is needed; the convergence proof works for batch sizes as small as $B=1$ and for all $B\le d$, and larger $B$ accelerates the iteration count by a factor of $B$.
  • The total sample complexity $O(\kappa^2 r d \log d \max\{r \log^5 d, \log(1/\varepsilon)\})$ is nearly optimal in the sense of the $\Theta(r^2 d)$ information-theoretic bound for single-copy measurements, while memory stays $O(rd)$.
  • For pure states, the paper also gives an online initialization via streaming projected SGD that reaches the contraction region with $O(\delta^{-2}d\log^2 d)$ iterations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, a fully online initialization for rank $r>1$ would make the entire pipeline streaming; the paper only sketches how to repeat the pure-state method when the top-$r$ eigenvalues have constant gaps.
  • The same local-curvature-plus-variance argument is likely to extend to other measurement ensembles that form a tight frame over all matrices (for example, approximate 4-designs), not just local Pauli measurements.
  • One testable refinement is a decaying learning-rate schedule, which could convert the current fixed-noise floor $\varepsilon_0^2$ into a vanishing error at the cost of slower tail convergence; the paper does not analyze this variant.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. This paper proposes mini-batch SGD for online low-rank quantum state tomography with single-copy local Pauli measurements. The state is parameterized as ρ = UU†, and each round updates U by one gradient step on the empirical squared loss. Under an initialization condition U0 ∈ E(ρ*, σ_r*/3), the authors prove local linear convergence in expectation (Theorem 3) and with high probability (Theorem 4), with a noise floor ε0 arising from finite measurement repetitions. They also analyze a streaming PCA initialization for pure states (Theorem 2) and report numerical experiments on a 7-qubit rank-1 state. The paper claims nearly optimal sample complexity and better time complexity than offline non-convex QST algorithms.

Significance. The proof chain in Lemmas 2–4 and Theorems 3–4 is the main strength: the contraction rate and the bias term are derived from explicit regularity and smoothness inequalities, without requiring a restricted isometry property, and the constants are not fitted to data. If accepted, the per-round FLOP count O(Brd log d) and the B-fold acceleration of mini-batching are legitimate contributions. The paper also gives a union-bound failure probability in Theorem 4. However, the central sample-complexity claim is not supported once the finite-shot noise model of Lemma 1 is accounted for, and the online rank-r initialization is missing a proof; these issues change the paper's main advertised advantage.

major comments (3)
  1. [Section III-B, Lemma 1 and Theorem 4] The advertised sample complexity omits the ℓ repetitions per Pauli setting required by Lemma 1. Lemma 1 requires ℓ ≥ 112 ε0^{-2} d log d to guarantee |z_{t,k}| ≤ ε0/√d with high probability. Theorem 4 inherits this condition, and because the recurrence (13) has a fixed point proportional to ε0², reaching target Frobenius error ε requires ε0 ≲ ε. Each of the T rounds consumes Bℓ copies, so the total copy count is T B ℓ = Ω(κ² r d² log² d log(1/ε)/ε²), independent of B. This contradicts the sample complexity O(κ² r d log d max{r log^5 d, log(1/ε)}) in Theorem 1 and in Tables I and II, and it changes the comparison with the offline baselines. Unless an additional round-to-round averaging step removes the ε0² floor, the 'nearly optimal sample complexity' claim fails as stated.
  2. [Section I-D and Corollary 2] The online rank-r initialization is not established. For r = 1, Algorithm 2 and Theorem 2 provide an online initialization, but for rank r > 1 the manuscript only states that the top-r eigenvectors can be computed sequentially by repeating the pure-state method when the eigenvalues admit constant gaps; no theorem statement or proof is supplied. Meanwhile, Theorems 3 and 4 assume U0 ∈ E(ρ*, σ_r*/3), and Corollary 2 obtains e0 ≤ σ_r*/3 from the offline spectral initialization of [29, Lemma 4] or [35, Lemma 2]. Consequently, for general rank r the advertised online algorithm depends on an offline initialization step, and the online nature of the algorithm is not fully supported. If the authors intend to restrict to pure states or to eigenvalue-gapped states, that restriction must appear in the main theorems and abstract.
  3. [Section V-B, Theorem 2] The initialization sample complexity in Theorem 2 undercounts copies in the same way as the main phase. The proof of Theorem 2 uses equation (18), which relies on Lemma 1 to bound the second moment of the noise by ε0²/d; this requires ℓ ≥ 112 ε0^{-2} d log d shots per round. The stated bound T0 = O(δ^{-2} d log² d) therefore counts rounds, not copies, and the true copy count for initialization is larger by a factor of Ω(d log d). With ℓ counted, the pure-state initialization cost is no longer O(δ^{-2} d log² d), again affecting the paper's complexity claims.
minor comments (5)
  1. [Section I-B] The first sentence of Section I-B reads 'we initial the study'; it should be 'we initiate the study.'
  2. [Theorem 2 and Section V-B] The step size in Theorem 2 and Corollary 1 is η_t = log d/(40d log²d + t), but the proof in Section V-B uses η_t = log d/(80d log²d + t); the two should be reconciled.
  3. [Corollary 2] Equation (14) is typeset ambiguously as e_T² ≤ O(ǫ/9(σ_r*)^2 + ε0²); the intended parentheses and the role of ε should be clarified.
  4. [Section IV] The noisy experiment uses ℓ = 20d shots per setting; for d = 128 this is below the Lemma 1 threshold 112ε0^{-2}d log d for any ε0 < 1, so the right panel of Figure 1 does not instantiate the theorem's noisy event (12). It should be described as an empirical demonstration rather than a verification of the theorem's noise model.
  5. [Section I-D] The remark that rank-r initialization can be obtained by sequentially repeating the pure-state method presupposes constant gaps among the r largest eigenvalues; this condition should be stated explicitly if it is relied upon.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence proof is built from explicit inequalities, and the initialization relies on independent published tools rather than on the present theorem.

full rationale

The central claims are derived from self-contained local analysis: Lemma 1 bounds measurement noise by Hoeffding, Lemmas 2-4 establish local smoothness and regularity with explicit constants, Theorem 3 derives the one-step contraction in expectation, and Theorem 4 converts this into a high-probability bound using Azuma-Bernstein. The contraction factor and bias term arise algebraically from those inequalities, not from any fitted parameter or from assuming the desired error bound. The initialization hypothesis U0 in E(rho*, sigma_r*/3) is a genuine assumption: for pure states it is provided by Theorem 2, whose proof invokes the external streaming-PCA result [63]; for rank r>1 the paper cites independently published spectral initialization results, [29, Lemma 4] and [35, Lemma 2]. Although [35] shares an author with the present paper, it is paired with an independent reference and does not presuppose the present SGD convergence theorem, so it is not load-bearing circularity. The unproved statement that the rank-r initialization can be obtained by repeating the pure-state method is a gap/limitation rather than a circular reduction, and the concern about the omitted shot-count factor in the sample complexity is a correctness/accounting issue outside the definition of circularity. No step in the derivation chain is equivalent by construction to its own input.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard Pauli-basis linear algebra, an external streaming PCA guarantee for initialization, an offline spectral initialization result, and the local contraction-region assumption. No new physical entities are introduced and no parameter is fitted to data; the main gap is the rank-r online initialization, which is assumed rather than proven.

free parameters (3)
  • Learning rate η = O(1/(κ r log d)) or O(1/(κ r)) depending on theorem
    Chosen from theory and depends on the unknown rank and condition number; not fitted to measurement data, but a user must know or upper bound κ and r to set it.
  • Measurement noise tolerance ε0 = user-chosen constant in (0,1)
    Controls the number of shots ℓ = 112 ε0^-2 d log d and the final error floor; not fitted to data.
  • Batch size B = B ≤ min{40κ²/3,d}, typically small
    Algorithm hyperparameter; larger B speeds convergence up to a cap but increases per-round cost.
assumptions (6)
  • standard math The Pauli operators form a complete orthogonal basis with ⟨Wi,Wj⟩ = d δ_ij.
    Used in Preliminaries and throughout Lemma 4 to compute expectations of gradients; this is the standard Pauli-basis expansion.
  • domain assumption Each outcome is y_t,k = Tr(A_t,k ρ*) + z_t,k with z_t,k zero-mean and |z_t,k| ≤ ε0/√d after ℓ ≥ 112 ε0^-2 d log d shots.
    Derived in Lemma 1 from independent Bernoulli shots and Hoeffding's inequality; it underpins the noise terms in Theorems 3 and 4 and Lemma 4.
  • domain assumption Streaming PCA / Oja's algorithm converges as in Jain et al. (2016), reference [63], with probability at least 3/4.
    Used for the pure-state online initialization in Theorem 2; this is an external result, not proved in this paper.
  • domain assumption Spectral initialization from reference [29, Lemma 4] or reference [35, Lemma 2] yields e0 ≤ σ_r*/3 for rank-r states.
    Invoked in Section III-B and Corollary 2 to enter the contraction region; [35] includes a co-author of this paper, but it is an external published result.
  • domain assumption The condition number κ is known or upper bounded and satisfies κ ≤ sqrt(d r), and the rank r is known.
    Theorems 3 and 4 set the learning rate and batch size in terms of κ and r; in practice these quantities may be unknown.
  • domain assumption The initial estimate lies in E(ρ*, σ_r*/3), the local contraction region.
    This is the premise of Theorems 3 and 4; it is proven online only for r=1 and only sketched for r>1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Quantum State Tomography via Stochastic Gradient Descent." pith.science (2026). https://pith.science/paper/RLMYSDUT

@misc{pith2026250707601,
  author       = {Pith},
  title        = {Pith review of: Online Quantum State Tomography via Stochastic Gradient Descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RLMYSDUT}},
  note         = {Machine review of arXiv:2507.07601}
}
read the original abstract

We initiate the study of online quantum state tomography (QST), where the matrix representation of an unknown quantum state is reconstructed by sequentially performing a batch of measurements and updating the state estimate using only the measurement statistics from the current round. Motivated by recent advances in non-convex optimization algorithms for solving low-rank QST, we propose non-convex mini-batch stochastic gradient descent (SGD) algorithms to tackle online QST, which leverage the low-rank structure of the unknown quantum state and are well-suited for practical applications. Our main technical contribution is a rigorous convergence analysis of these algorithms. With proper initialization, we demonstrate that the SGD algorithms for online low-rank QST achieve linear convergence both in expectation and with high probability. Our algorithms achieve nearly optimal sample complexity while remaining highly memory-efficient. In particular, their time complexities are better than the state-of-the-art non-convex QST algorithms, in terms of the rank and the logarithm of the dimension of the unknown quantum state.

Figures

Figures reproduced from arXiv: 2507.07601 by the authors.

Figure 1
Figure 1. Left: Exact Pauli measurement data, where [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Rank-Adaptive Matrix-Free Atomic Quantum State Tomography

    quant-ph 2026-07 conditional novelty 5.0 of 10

    Low-rank quantum states are reconstructed as simplex-weighted mixtures of pure-state atoms with rank-adaptive, matrix-free updates, cutting memory and runtime versus dense tomographic methods.

Reference graph

Works this paper leans on

68 extracted references · 48 canonical work pages · cited by 1 Pith paper

  1. [1]

    Experimental comparison of efficient tomog raphy schemes for a six- qubit state,

    C. Schwemmer, G. Tóth, A. Niggebaum, T. Moroder, D. Gross , O. Gühne, and H. Weinfurter, “Experimental comparison of efficient tomog raphy schemes for a six- qubit state,” Phys. Rev. Lett. , vol. 113, p. 040503, Jul 2014. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.113.040503

    work page doi:10.1103/physrevlett.113.040503 2014

  2. [2]

    Experimental quantum compressed sensing for a seven-qubit system,

    C. A. Riofrío, D. Gross, S. T. Flammia, T. Monz, D. Nigg, R. Blatt, and J. Eisert, “Experimental quantum compressed sensing for a seven-qubit system,” Nature Communications , vol. 8, no. 1, may

    work page

  3. [3]

    Sample-opti mal tomography of quantum states,

    J. Haah, A. W . Harrow, Z. Ji, X. Wu, and N. Y u, “Sample-opti mal tomography of quantum states,” IEEE Transactions on Information Theory , vol. 63, no. 9, pp. 5628–5641, 2017

    work page 2017

  4. [4]

    Efficient quantum tomograph y,

    R. O’Donnell and J. Wright, “Efficient quantum tomograph y,” in Proceedings of the F orty- Eighth Annual ACM Symposium on Theory of Computing , ser. STOC ’16. New Y ork, 26 NY , USA: Association for Computing Machinery, 2016, p. 899– 912. [Online]. Available: https://doi.org/10.1145/2897518.2897544

    arXiv 2016

  5. [5]

    How to learn a quantum state,

    J. Wright, “How to learn a quantum state,” Ph.D. Thesis, 2 016

    work page

  6. [6]

    An Improved Sample Complexity Lower Bound for ( Fidelity) Quantum State Tomography,

    H. Y uen, “An Improved Sample Complexity Lower Bound for ( Fidelity) Quantum State Tomography,” Quantum, vol. 7, p. 890, Jan. 2023. [Online]. Available: https://do i.org/10.22331/q-2023-01-03-890

    work page doi:10.22331/q-2023-01-03-890 2023

  7. [7]

    Quantum tomography using state-preparation unitaries,

    J. van Apeldoorn, A. Cornelissen, A. Gilyén, and G. Nanni cini, “Quantum tomography using state-preparation unitaries,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2023, pp. 1265–1318. [Online]. Available: https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch47

    doi:10.1137/1.9781611977554.ch47 2023

  8. [8]

    An optimal tradeoff between en tanglement and copy complexity for state tomography,

    S. Chen, J. Li, and A. Liu, “An optimal tradeoff between en tanglement and copy complexity for state tomography,” in Proceedings of the 56th Annual ACM Symposium on Theory of Com puting, ser. STOC 2024. New Y ork, NY , USA: Association for Computing Mach inery, 2024, p. 1331–1342. [Online]. Available: https://doi.org/10.1145/3618260. 3649704

    doi:10.1145/3618260 2024

Show all 68 references
  1. [9]

    Sample optimal and memory efficient quantum state tomography,

    Y . Hu, E. Cervero-Martín, E. Theil, L. Man ˇcinska, and M. Tomamichel, “Sample optimal and memory efficient quantum state tomography,” 2024. [Online]. Avail able: https://arxiv.org/abs/2410.16220

    2024 arXiv

  2. [10]

    Low rank matrix r ecovery from rank one measurements,

    R. Kueng, H. Rauhut, and U. Terstiege, “Low rank matrix r ecovery from rank one measurements,” Applied and Computational Harmonic Analysis , vol. 42, no. 1, pp. 88–116, 2017. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1063520315001037

    2017

  3. [11]

    Fast state tomography w ith optimal error bounds,

    M. Gu¸ t˘a, J. Kahn, R. Kueng, and J. A. Tropp, “Fast state tomography w ith optimal error bounds,” Journal of Physics A: Mathematical and Theoretical , vol. 53, no. 20, p. 204001, apr 2020. [Online]. Available: https://dx.doi.org/10.1088/1751-8121/ab81 11

    2020 doi

  4. [12]

    Lower bounds for learning quantum states with single-copy measurements,

    A. Lowe and A. Nayak, “Lower bounds for learning quantum states with single-copy measurements,”

  5. [13]

    When Does Adaptivity Help for Quantum State Learning? ,

    S. Chen, B. Huang, J. Li, A. Liu, and M. Sellke, “ When Does Adaptivity Help for Quantum State Learning? ,” in 2023 IEEE 64th Annual Symposium on F oundations of Computer S cience (FOCS) . Los Alamitos, CA, USA: IEEE Computer Society, Nov. 2023, pp. 391–404. [Online]. Availabl...

    2023

  6. [14]

    Quantum chi-squared to mography and mutual information testing,

    S. T. Flammia and R. O’Donnell, “Quantum chi-squared to mography and mutual information testing,” Quantum, vol. 8, p. 1381, Jun. 2024. [Online]. Available: https://d oi.org/10.22331/q-2024-06-20-1381

    2024 doi

  7. [15]

    Fast and Rob ust Quantum State Tomography from Few Basis Measurements,

    D. S. França, F. G. L. Brandão, and R. Kueng, “Fast and Rob ust Quantum State Tomography from Few Basis Measurements,” in 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) , ser. Leibniz International Proceedings in Informatics (LI...

    2021 doi

  8. [16]

    Quantum state tomography via compressed sensing,

    D. Gross, Y .-K. Liu, S. T. Flammia, S. Becker, and J. Eise rt, “Quantum state tomography via compressed sensing,” Phys. Rev. Lett. , vol. 105, p. 150401, Oct 2010. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.105.150401

    2010 doi

  9. [17]

    Universal low-rank matrix recovery from pa uli measurements,

    Y .-K. Liu, “Universal low-rank matrix recovery from pa uli measurements,” Advances in Neural Information Processing Systems , vol. 24, 2011

    2011

  10. [18]

    Direct fidelity estimation from few pauli measurements,

    S. T. Flammia and Y .-K. Liu, “Direct fidelity estimation from few pauli measurements,” Physical Review Letters , vol. 106, no. 23, p. 230501, 2011

    2011

  11. [19]

    Quant um tomography via compressed sensing: error bounds, sample complexity and efficient estimators,

    S. T. Flammia, D. Gross, Y .-K. Liu, and J. Eisert, “Quant um tomography via compressed sensing: error bounds, sample complexity and efficient estimators,” New Journal of Physics , vol. 14, no. 9, p. 095022, sep 2012. [Online]. Available: https://dx.doi. org/10.1088/1367-2630/1...

    2012 doi

  12. [20]

    Optimal l arge-scale quantum state 27 tomography with Pauli measurements,

    T. Cai, D. Kim, Y . Wang, M. Y uan, and H. H. Zhou, “Optimal l arge-scale quantum state 27 tomography with Pauli measurements,” The Annals of Statistics , vol. 44, no. 2, pp. 682 – 712,

  13. [21]

    Sample efficient tomography via pauli measureme nts,

    N. Y u, “Sample efficient tomography via pauli measureme nts,” 2020. [Online]. Available: https://arxiv.org/abs/2009.04610

    2020 arXiv

  14. [22]

    Compressed sensing,

    D. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory , vol. 52, no. 4, pp. 1289–1306, 2006

    2006

  15. [23]

    A nonconvex optimization f ramework for low rank matrix estimation,

    T. Zhao, Z. Wang, and H. Liu, “A nonconvex optimization f ramework for low rank matrix estimation,” in Advances in Neural Information Processing Systems , C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, Eds., vol. 28. Curran Associate s, Inc., 2015. [Online]. Avai...

    2015

  16. [24]

    Drop ping convexity for faster semi-definite optimization,

    S. Bhojanapalli, A. Kyrillidis, and S. Sanghavi, “Drop ping convexity for faster semi-definite optimization,” in 29th Annual Conference on Learning Theory , ser. Proceedings of Machine Learning Research, V . Feldman, A. Rakhlin, and O. Shamir, Ed s., vol. 49. Columbia Universit...

    2016

  17. [25]

    Guaranteed matrix completion via non-convex factorization,

    R. Sun and Z.-Q. Luo, “Guaranteed matrix completion via non-convex factorization,” IEEE Transactions on Information Theory , vol. 62, no. 11, pp. 6535–6579, 2016

    2016

  18. [26]

    Low-rank solutions of linear matrix equations via procrustes flow,

    S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, and B. Recht, “Low-rank solutions of linear matrix equations via procrustes flow,” in Proceedings of The 33rd International Conference on Machine Learning , ser. Proceedings of Machine Learning Research, M. F. Balca n and K. Q...

    2016

  19. [27]

    No spurious local minima in n onconvex low rank problems: A unified geometric analysis,

    R. Ge, C. Jin, and Y . Zheng, “No spurious local minima in n onconvex low rank problems: A unified geometric analysis,” in Proceedings of the 34th International Conference on Machin e Learning , ser. Proceedings of Machine Learning Research, D. Precup and Y . W . Teh, Eds., vol...

    2017

  20. [28]

    Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably,

    D. Park, A. Kyrillidis, C. Caramanis, and S. Sanghavi, “ Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably,” SIAM Journal on Imaging Sciences , vol. 11, no. 4, pp. 2165–2204, 2018. [Online]. Available: https://doi.or g/10.1137/17M1150189

    2018 doi

  21. [29]

    Provable compressed sensing quantum state tomography via non-conve x methods,

    A. Kyrillidis, A. Kalev, D. Park, S. Bhojanapalli, C. Ca ramanis, and S. Sanghavi, “Provable compressed sensing quantum state tomography via non-conve x methods,” npj Quantum Information , vol. 4, no. 1, p. 36, 2018

    2018

  22. [30]

    Fast quantum state reconstruction via accelerated non-convex programming,

    J. L. Kim, G. Kollias, A. Kalev, K. X. Wei, and A. Kyrillid is, “Fast quantum state reconstruction via accelerated non-convex programming,” Photonics, vol. 10, no. 2, 2023. [Online]. Available: https://www.mdpi.com/2304-6732/10/2/116

    2023

  23. [31]

    Local stochastic factored gradient descent for distributed quantum state tomography,

    J. L. Kim, M. T. Toghani, C. A. Uribe, and A. Kyrillidis, “ Local stochastic factored gradient descent for distributed quantum state tomography,” IEEE Control Systems Letters , vol. 7, pp. 199–204, 2023

    2023

  24. [32]

    Efficient representation of quan tum many-body states with deep neural networks,

    X. Gao and L.-M. Duan, “Efficient representation of quan tum many-body states with deep neural networks,” Nature Communications , vol. 8, no. 1, p. 662, Sep 2017. [Online]. Available: https://doi.org/10.1038/s41467-017-00705-2

    2017 doi

  25. [33]

    Neural-network quantum state tomography,

    G. Torlai, G. Mazzola, J. Carrasquilla, M. Troyer, R. Me lko, and G. Carleo, “Neural-network quantum state tomography,” Nature Physics , vol. 14, no. 5, pp. 447–450, May 2018. [Online]. Available: https://doi.org/10.1038/s41567-018-0048-5

    2018 doi

  26. [34]

    QuCumber: wavefunction reconstr uction with neural networks,

    M. J. S. Beach, I. D. Vlugt, A. Golubeva, P . Huembeli, B. K ulchytskyy, X. Luo, R. G. Melko, E. Merali, and G. Torlai, “QuCumber: wavefunction reconstr uction with neural networks,” SciPost Phys., vol. 7, p. 009, 2019. [Online]. Available: https://scipos t.org/10.21468/SciPos...

    2019 doi

  27. [35]

    Quantum state tomography via nonconvex riemannian gradient descent,

    M.-C. Hsu, E.-J. Kuo, W .-H. Y u, J.-F. Cai, and M.-H. Hsie h, “Quantum state tomography via nonconvex riemannian gradient descent,” Physical Review Letters , vol. 132, no. 24, p. 240804, 2024

    2024

  28. [36]

    On line learning of quantum states*,

    S. Aaronson, X. Chen, E. Hazan, S. Kale, and A. Nayak, “On line learning of quantum states*,” Journal of Statistical Mechanics: Theory and Experiment , vol. 2019, no. 12, p. 124019, dec 2019. [Online]. Available: https://dx.doi.org/10.1088/1742- 5468/ab3988

    2019 doi

  29. [37]

    More practical and adaptive algori thms for online quantum state learning,

    Y . Chen and X. Wang, “More practical and adaptive algori thms for online quantum state learning,”

  30. [38]

    Revisiting onli ne quantum state learning,

    F. Y ang, J. Jiang, J. Zhang, and X. Sun, “Revisiting onli ne quantum state learning,” in Proceedings of the AAAI Conference on Artificial Intelligence , vol. 34, 2020, pp. 6607–6614

    2020

  31. [39]

    Adap tive Online Learning of Quantum States,

    X. Chen, E. Hazan, T. Li, Z. Lu, X. Wang, and R. Y ang, “Adap tive Online Learning of Quantum States,” Quantum, vol. 8, p. 1471, Sep. 2024. [Online]. Available: https://doi.org/10.22331/q-2024-09-12-1471

    2024 doi

  32. [40]

    Onli ne learning quantum states with the logarithmic loss via vb-ftrl,

    W .-F. Tseng, K.-C. Chen, Z.-H. Xiao, and Y .-H. Li, “Onli ne learning quantum states with the logarithmic loss via vb-ftrl,” 2024. [Online]. Available: https://arxiv.org/abs/2311.04237

    2024 arXiv

  33. [41]

    Learnin g pure quantum states (almost) without regret,

    J. Lumbreras, M. Terekhov, and M. Tomamichel, “Learnin g pure quantum states (almost) without regret,” 2024. [Online]. Available: https://arxiv.org/a bs/2406.18370

    2024 arXiv

  34. [42]

    Learning properties of quantum states without the iid assumption,

    O. Fawzi, R. Kueng, D. Markham, and A. Oufkir, “Learning properties of quantum states without the iid assumption,” Nature Communications, vol. 15, no. 1, p. 9677, Nov 2024. [Online]. Available: https://doi.org/10.1038/s41467-024-53765-6

    2024 doi

  35. [43]

    Onlin e learning of pure states is as hard as mixed states,

    M. Meyer, S. Adhikary, N. Guo, and P . Rebentrost, “Onlin e learning of pure states is as hard as mixed states,” 2025. [Online]. Available: https://arxiv. org/abs/2502.00823

    2025

  36. [44]

    A survey on the complexity of learning quantum states,

    A. Anshu and S. Arunachalam, “A survey on the complexity of learning quantum states,” Nature Reviews Physics , vol. 6, no. 1, pp. 59–69, Jan 2024. [Online]. Available: https://doi.org/10.1038/s42254-023-00662-4

    2024 doi

  37. [45]

    Shadow tomography of quantum states,

    S. Aaronson, “Shadow tomography of quantum states,” SIAM Journal on Computing , vol. 49, no. 5, pp. STOC18–368–STOC18–394, 2020. [Online]. Available: ht tps://doi.org/10.1137/18M120275X

    2020 doi

  38. [46]

    Predicting man y properties of a quantum system from very few measurements,

    H.-Y . Huang, R. Kueng, and J. Preskill, “Predicting man y properties of a quantum system from very few measurements,” Nature Physics , vol. 16, no. 10, pp. 1050–1057, Oct 2020. [Online]. Available: https://doi.org/10.1038/s41567-020-0932-7

    2020 doi

  39. [47]

    Provably efficient machine learning for quantum many-body problems,

    H.-Y . Huang, R. Kueng, G. Torlai, V . V . Albert, and J. Pre skill, “Provably efficient machine learning for quantum many-body problems,” Science, vol. 377, no. 6613, p. eabk3333, 2022. [Online]. Available: https://www.science.org/doi/abs/10.1126/science.abk3333

    2022 doi

  40. [48]

    An online optimiza tion algorithm for the real-time quantum state tomography,

    K. Zhang, S. Cong, K. Li, and T. Wang, “An online optimiza tion algorithm for the real-time quantum state tomography,” Quantum Information Processing , vol. 19, no. 10, p. 361, Sep 2020. [Online]. Available: https://doi.org/10.1007/s11128-0 20-02866-4

    2020 doi

  41. [49]

    Fast minimizati on of expected logarithmic loss via stochastic dual averaging,

    C.-E. Tsai, H.-C. Cheng, and Y .-H. Li, “Fast minimizati on of expected logarithmic loss via stochastic dual averaging,” in Proceedings of The 27th International Conference on Artific ial Intelligence and Statistics , ser. Proceedings of Machine Learning Research, S. Dasgupt a,...

    2024

  42. [50]

    Maximum-likelih ood quantum state tomography by cover’s method with non-asymptotic analysis,

    C.-M. Lin, H.-C. Cheng, and Y .-H. Li, “Maximum-likelih ood quantum state tomography by cover’s method with non-asymptotic analysis,” 2021. [Online]. Ava ilable: https://arxiv.org/abs/2110.00747

    2021 arXiv

  43. [51]

    Maximum-likelihoo d quantum state tomography by soft-bayes,

    C.-M. Lin, Y .-M. Hsu, and Y .-H. Li, “Maximum-likelihoo d quantum state tomography by soft-bayes,” 2022. [Online]. Available: https://arxiv.o rg/abs/2012.15498

    2022 arXiv

  44. [52]

    Faster stochast ic first-order method for maximum-likelihood quantum state tomography,

    C.-E. Tsai, H.-C. Cheng, and Y .-H. Li, “Faster stochast ic first-order method for maximum-likelihood quantum state tomography,” 2022. [Online]. Available: htt ps://arxiv.org/abs/2211.12880 29

    2022 arXiv

  45. [53]

    Accelerated gradient method s for stochastic optimization and online learning,

    C. Hu, W . Pan, and J. Kwok, “Accelerated gradient method s for stochastic optimization and online learning,” Advances in Neural Information Processing Systems , vol. 22, 2009

    2009

  46. [54]

    Large-scale machine learning with stochas tic gradient descent,

    L. Bottou, “Large-scale machine learning with stochas tic gradient descent,” in Proceedings of COMPSTAT’2010: 19th International Conference on Computat ional StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers . Springer, 2010, pp. 177–186

    2010

  47. [55]

    Adaptive subgradien t methods for online learning and stochastic optimization

    J. Duchi, E. Hazan, and Y . Singer, “Adaptive subgradien t methods for online learning and stochastic optimization.” Journal of machine learning research , vol. 12, no. 7, 2011

    2011

  48. [56]

    Statist ical inference using sgd,

    T. Li, L. Liu, A. Kyrillidis, and C. Caramanis, “Statist ical inference using sgd,” in Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence a nd Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposi um on Education...

    2018

  49. [57]

    Provable effici ent online matrix completion via non-convex stochastic gradient descent,

    C. Jin, S. M. Kakade, and P . Netrapalli, “Provable effici ent online matrix completion via non-convex stochastic gradient descent,” Advances in Neural Information Processing Systems , vol. 29, 2016

    2016

  50. [58]

    Parallel stochastic gradient algor ithms for large-scale matrix completion,

    B. Recht and C. Ré, “Parallel stochastic gradient algor ithms for large-scale matrix completion,” Mathematical Programming Computation , vol. 5, no. 2, pp. 201–226, 2013

    2013

  51. [59]

    Lar ge-scale matrix factorization with distributed stochastic gradient descent,

    R. Gemulla, E. Nijkamp, P . J. Haas, and Y . Sismanis, “Lar ge-scale matrix factorization with distributed stochastic gradient descent,” in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , 2011, pp. 69–77

    2011

  52. [60]

    Global convergence of s tochastic gradient descent for some non-convex matrix problems,

    C. De Sa, C. Re, and K. Olukotun, “Global convergence of s tochastic gradient descent for some non-convex matrix problems,” in International Conference on Machine Learning . PMLR, 2015, pp. 2332–2341

    2015

  53. [61]

    Escaping from saddl e points—online stochastic gradient for tensor decomposition,

    R. Ge, F. Huang, C. Jin, and Y . Y uan, “Escaping from saddl e points—online stochastic gradient for tensor decomposition,” in Conference on Learning Theory . PMLR, 2015, pp. 797–842

    2015

  54. [62]

    Geometric median in nearly linear time,

    M. B. Cohen, Y . T. Lee, G. Miller, J. Pachocki, and A. Sidf ord, “Geometric median in nearly linear time,” in Proceedings of the forty-eighth annual ACM symposium on The ory of Computing , 2016, pp. 9–21

    2016

  55. [63]

    Streaming pca: Matching matrix bernstein and near-optimal finite sample guarantees for oja ’s algorithm,

    P . Jain, C. Jin, S. M. Kakade, P . Netrapalli, and A. Sidfo rd, “Streaming pca: Matching matrix bernstein and near-optimal finite sample guarantees for oja ’s algorithm,” in Conference on learning theory. PMLR, 2016, pp. 1147–1164

    2016

  56. [64]

    Angles between subspaces and t heir tangents,

    P . Zhu and A. V . Knyazev, “Angles between subspaces and t heir tangents,” Journal of Numerical Mathematics, vol. 21, no. 4, pp. 325–340, 2013

    2013

  57. [2016]

    Available: https://doi.org/10.1214/15- AOS1382

    [Online]. Available: https://doi.org/10.1214/15- AOS1382

    doi

  58. [2017]

    Available: http://dx.doi.org/10.1038/n comms15305

    [Online]. Available: http://dx.doi.org/10.1038/n comms15305

    doi

  59. [2020]

    Available: https://arxiv.org/abs/2006

    [Online]. Available: https://arxiv.org/abs/2006. 01013

    2006

  60. [2022]

    Available: https://arxiv.org/abs/2207

    [Online]. Available: https://arxiv.org/abs/2207. 14438

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.