pith. sign in

arxiv: 2410.16220 · v2 · pith:2AXDSIPYnew · submitted 2024-10-21 · 🪐 quant-ph

Sample Optimal and Memory Efficient Quantum State Tomography

Yanglin Hu , Enrique Cervero-Mart\'in , Elias Theil , Laura Man\v{c}inska , Marco Tomamichel This is my paper

Pith reviewed 2026-05-25 08:03 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum state tomographysample complexitymemory efficiencyunitary Schur samplingstreaming accessquantum algorithmsquantum information
0
0 comments X

The pith

A quantum state tomography algorithm matches the optimal sample count while needing only streaming access to copies instead of full storage.

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

The paper seeks to establish that tomography of an unknown quantum state can reach the information-theoretic minimum number of samples without the massive memory cost of storing many copies at once. It constructs the procedure around unitary Schur sampling so that each copy is processed as it arrives and then discarded. A reader would care because earlier sample-optimal methods become impractical once the number of qubits grows, as they require quantum memory that scales with the full set of samples. The new approach removes that barrier while preserving the sample bound.

Core claim

The authors introduce and analyze a tomography procedure based on unitary Schur sampling that attains the known optimal sample complexity for reconstructing an n-qubit state to a target precision while requiring only streaming access to the input copies, thereby reducing memory requirements relative to naive optimal algorithms that store all copies simultaneously.

What carries the argument

unitary Schur sampling, the sampling primitive that extracts the necessary statistics from arriving copies without retaining them all in memory.

If this is right

  • The procedure matches the sample complexity lower bound established for general quantum state tomography.
  • Memory usage drops to a level compatible with devices that cannot hold large numbers of quantum states at once.
  • Samples arrive and are processed sequentially, eliminating the need to prepare and retain a batch of copies.
  • The method applies to arbitrary unknown states without requiring additional structure or prior knowledge.

Where Pith is reading between the lines

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

  • The streaming property could make the algorithm compatible with experimental setups where copies are generated one at a time rather than in parallel.
  • The same sampling primitive might be adapted to other quantum learning tasks that currently face similar memory bottlenecks.
  • Classical post-processing steps after the sampling phase could be further optimized to reduce overall runtime without changing the sample or memory guarantees.

Load-bearing premise

The analysis of the unitary Schur sampling step shows that streaming access alone is enough to reach sample optimality without extra sample overhead or unaccounted memory costs.

What would settle it

An explicit implementation or simulation in which the algorithm either exceeds the optimal sample bound or requires simultaneous storage of more than a constant number of copies while still reaching the target reconstruction precision would refute the central claim.

read the original abstract

Quantum state tomography is the fundamental physical task of learning a complete classical description of an unknown state of a quantum system given coherent access to many identical samples of it. The complexity of this task is commonly characterised by its sample-complexity: the minimal number of samples needed to reach a certain target precision of the description. While the sample complexity of quantum state tomography has been well studied, the memory complexity has not been investigated in depth. Indeed, the bottleneck in the implementation of na\"ive sample-optimal quantum state tomography is its massive quantum memory requirements. In this work, we propose and analyse a quantum state tomography algorithm which retains sample-optimality but is also memory-efficient. Our work is built on a form of unitary Schur sampling and only requires streaming access to the samples.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper proposes and analyzes a quantum state tomography algorithm that achieves sample optimality while also being memory-efficient. The construction relies on a form of unitary Schur sampling and requires only streaming access to the samples rather than storing all of them simultaneously.

Significance. If the analysis is correct, the result would be significant because it removes the massive quantum memory bottleneck that prevents practical implementation of known sample-optimal tomography protocols. This could enable experimental realization of optimal tomography on near-term devices with limited memory resources.

major comments (1)
  1. [Abstract] The provided manuscript text consists only of the abstract; no sections, equations, proofs, or complexity derivations are supplied. Without these, it is impossible to verify whether the unitary Schur sampling procedure actually achieves both sample optimality and reduced memory with only streaming access, or whether hidden overheads appear in the analysis.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract] The provided manuscript text consists only of the abstract; no sections, equations, proofs, or complexity derivations are supplied. Without these, it is impossible to verify whether the unitary Schur sampling procedure actually achieves both sample optimality and reduced memory with only streaming access, or whether hidden overheads appear in the analysis.

    Authors: The complete manuscript, including all sections, equations, proofs, and complexity derivations, is available on arXiv:2410.16220. The abstract was excerpted for brevity in the initial presentation, but the full text provides a detailed construction and analysis of the unitary Schur sampling procedure. This analysis establishes sample optimality while ensuring memory efficiency under streaming access to samples, with explicit bounds showing no hidden overheads in the memory or sample requirements. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper constructs a tomography algorithm from unitary Schur sampling with streaming access, claiming sample optimality and memory efficiency. No quoted equations or steps reduce a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or definitional tautology. The central claim rests on analysis of an external sampling primitive rather than internal redefinition or renaming of known results. This matches the most common honest finding for papers whose core contribution is an algorithmic construction with independent verification potential.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger reflects the high-level description. No free parameters, invented entities, or non-standard axioms are mentioned.

axioms (1)
  • standard math Standard quantum information assumptions including the ability to perform coherent unitary operations and measurements on multiple copies of a quantum state.
    The algorithm is built on unitary Schur sampling, which presupposes these primitives.

pith-pipeline@v0.9.0 · 5668 in / 1236 out tokens · 36062 ms · 2026-05-25T08:03:41.813235+00:00 · methodology

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. An Exponential Sample-Complexity Advantage for Coherent Quantum Inference

    quant-ph 2026-05 unverdicted novelty 8.0

    Coherent quantum inference achieves O(1/ε) sample complexity for d-dimensional quantum purity amplification, exponentially better than the Ω(d/ε) required by any incoherent measurement-mediated protocol.

Reference graph

Works this paper leans on

55 extracted references · 55 canonical work pages · cited by 1 Pith paper

  1. [1]

    states that SC F δ′ ln r δ′ , d, r = O dr2 δ′ , which is equivalent to our statement by properly scaling δ = δ′ ln r δ′ , as 1 δ′ ≤ 2 δ ln r δ asymptotically

    does not make any claims on the sample complexity with respect to fidelity, and it is unknown whether the same techniques can be used when learning in infidelity. states that SC F δ′ ln r δ′ , d, r = O dr2 δ′ , which is equivalent to our statement by properly scaling δ = δ′ ln r δ′ , as 1 δ′ ≤ 2 δ ln r δ asymptotically. 3 We remark that the logarithmic fa...

    work page

  2. [2]

    Using a similar argument as in the proof for Lemma 23, we can first perform 2 ln 2/ξ ln 2 repe- titions of such measurements, and with a probability of at least 1 − 1 2 ξ, there are ln 2/ξ ln 2 successful measurements, that is, Pr[enough success] ≥ 1 − 1 2 ξ. (129) Conditioned on enough successful measurements, using Lemma 24, we can use ln 2/ξ ln 2 repet...

    work page

  3. [3]

    Paris and J

    M. Paris and J. Rehacek, Quantum State Estimation , Lecture Notes in Physics (Springer Berlin Heidelberg, 2004)

    work page 2004

  4. [4]

    Banaszek, M

    K. Banaszek, M. Cramer, and D. Gross, Focus on quan- tum tomography, New Journal of Physics 15, 125020 (2013)

    work page 2013

  5. [5]

    Aaronson, Shadow tomography of quantum states, SIAM Journal on Computing 49, STOC18 (2020)

    S. Aaronson, Shadow tomography of quantum states, SIAM Journal on Computing 49, STOC18 (2020)

    work page 2020

  6. [6]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measure- ments, Nature Physics 16, 1050 (2020)

    work page 2020

  7. [7]

    Crouch, A

    M. Crouch, A. McGregor, G. Valiant, and D. P. Woodruff, Stochastic streams: sample complexity vs. space complexity, in 24th Annual European Symposium on Algorithms (ESA 2016) , Leibniz International Pro- ceedings in Informatics (LIPIcs), Vol. 57 (2016) pp. 32:1– 32:15

    work page 2016

  8. [8]

    F. Le Gall, Exponential separation of quantum and clas- sical online space complexity, in Proceedings of the Eigh- teenth Annual ACM Symposium on Parallelism in Al- gorithms and Architectures , SPAA ’06 (Association for Computing Machinery, New York, NY, USA, 2006) p. xv 67–73

    work page 2006

  9. [9]

    Kueng, H

    R. Kueng, H. Rauhut, and U. Terstiege, Low rank ma- trix recovery from rank one measurements, Applied and Computational Harmonic Analysis 42, 88 (2017)

    work page 2017

  10. [10]

    Gut ¸˘ a, J

    M. Gut ¸˘ a, J. Kahn, R. Kueng, and J. A. Tropp, Fast state tomography with optimal error bounds, Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020)

    work page 2020

  11. [11]

    O’Donnell and J

    R. O’Donnell and J. Wright, Efficient quantum tomog- raphy, in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing , STOC ’16 (Asso- ciation for Computing Machinery, New York, NY, USA,

    work page

  12. [12]

    O’Donnell and J

    R. O’Donnell and J. Wright, Efficient quantum tomogra- phy ii, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2017 (Asso- ciation for Computing Machinery, New York, NY, USA,

    work page 2017

  13. [13]

    J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, Sample- optimal tomography of quantum states, IEEE Transac- tions on Information Theory 63, 5628 (2017)

    work page 2017

  14. [14]

    S. Chen, J. Li, and A. Liu, An optimal tradeoff between entanglement and copy complexity for state tomogra- phy, in Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024 (Association for Computing Machinery, New York, NY, USA, 2024) p. 1331–1342

    work page 2024

  15. [15]

    Cervero, E

    E. Cervero, E. Theil, and L. Manˇ cinska, A memory and gate efficient algorithm for unitary mixed schur dampling (2024)

    work page 2024

  16. [16]

    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 Foundations of Computer Science (FOCS) (IEEE Computer Society, Los Alamitos, CA, USA, 2023) pp. 391–404

    work page 2023

  17. [17]

    O’Donnell and J

    R. O’Donnell and J. Wright, A note on the haah et al. tomography algorithm (2016)

    work page 2016

  18. [18]

    Yuen, An improved sample complexity lower bound for (fidelity) quantum state tomography, Quantum7, 890 (2023)

    H. Yuen, An improved sample complexity lower bound for (fidelity) quantum state tomography, Quantum7, 890 (2023)

    work page 2023

  19. [19]

    H¨ affner, W

    H. H¨ affner, W. H¨ ansel, C. Roos, J. Benhelm, D. Chek- al Kar, M. Chwalla, T. K¨ orber, U. Rapol, M. Riebe, P. Schmidt, et al. , Scalable multiparticle entanglement of trapped ions, Nature 438, 643 (2005)

    work page 2005

  20. [20]

    G. M. D’Ariano and P. Perinotti, Optimal data process- ing for quantum measurements, Physics Review Letters 98, 020403 (2007)

    work page 2007

  21. [21]

    Gross, Y.-K

    D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eis- ert, Quantum state tomography via compressed sensing, Physics Review Letters 105, 150401 (2010)

    work page 2010

  22. [22]

    Y. L. Lim, A. Beige, and L. C. Kwek, Repeat-until- success linear optics distributed quantum computing, Physics Review Letters 95, 030505 (2005)

    work page 2005

  23. [23]

    Halil Shah and D

    K. Halil Shah and D. K. Oi, Ancilla driven quantum com- putation with arbitrary entangling strength, in 8th Con- ference on the Theory of Quantum Computation, Com- munication and Cryptography (TQC 2013) , Leibniz In- ternational Proceedings in Informatics (LIPIcs), Vol. 22 (2013) pp. 1–19

    work page 2013

  24. [24]

    Goodman and N

    R. Goodman and N. R. Wallach, Representations and invariants of the classical groups (Cambridge University Press, 2000)

    work page 2000

  25. [25]

    A. W. Harrow, Applications of coherent classical com- munication and the Schur transform to quantum infor- mation theory , Ph.D. thesis, Massachusetts Institute of Technology (2005)

    work page 2005

  26. [26]

    Buhrman, N

    H. Buhrman, N. Linden, L. Manˇ cinska, A. Montanaro, and M. Ozols, Quantum majority vote, in 14th Innova- tions in Theoretical Computer Science Conference (ITCS 2023), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 251 (2023) pp. 29:1–29:1

    work page 2023

  27. [27]

    Q. T. Nguyen, The mixed Schur transform: ef- ficient quantum circuit and applications (2023), arXiv:2310.01613 [quant-ph]

    work page arXiv 2023

  28. [28]

    Grinko, A

    D. Grinko, A. Burchardt, and M. Ozols, Gelfand-tsetlin basis for partially transposed permutations, with applica- tions to quantum information (2023), arXiv:2310.02252 [quant-ph]

    work page arXiv 2023

  29. [29]

    Ahlswede and A

    R. Ahlswede and A. Winter, Strong converse for iden- tification via quantum channels, IEEE Transactions on Information Theory 48, 569 (2002)

    work page 2002

  30. [30]

    Manca, S

    D. Bacon, I. L. Chuang, and A. W. Harrow, Effi- cient quantum circuits for Schur and Clebsch-Gordan transforms, Physical Review Letters 97, 10.1103/phys- revlett.97.170502 (2006)

    work page doi:10.1103/phys- 2006

  31. [31]

    Bacon, I

    D. Bacon, I. L. Chuang, and A. W. Harrow, The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits, in Proceedings of the Eighteenth Annual ACM- SIAM Symposium on Discrete Algorithms , SODA ’07 (Society for Industrial and Applied Mathematics, USA,

    work page

  32. [32]

    Cervero and L

    E. Cervero and L. Manˇ cinska, Weak schur sampling with logarithmic quantum memory (2023), arXiv:2309.11947 [quant-ph]

    work page arXiv 2023

  33. [33]

    Haferkamp, Random quantum circuits are approxi- mate unitary t-designs in depth O nt5+o(1) , Quantum 6, 795 (2022)

    J. Haferkamp, Random quantum circuits are approxi- mate unitary t-designs in depth O nt5+o(1) , Quantum 6, 795 (2022)

    work page 2022

  34. [34]

    A. W. Harrow and S. Mehraban, Approximate uni- tary t-designs by short random quantum circuits using nearest-neighbor and long-range gates, Communications in Mathematical Physics 401, 1531 (2023)

    work page 2023

  35. [35]

    J. Haah, Y. Liu, and X. Tan, Efficient approximate unitary designs from random pauli rotations (2024), arXiv:2402.05239 [quant-ph]

    work page arXiv 2024

  36. [36]

    Metger, A

    T. Metger, A. Poremba, M. Sinha, and H. Yuen, Simple constructions of linear-depth t-designs and pseudoran- dom unitaries (2024), arXiv:2404.12647 [quant-ph]

    work page arXiv 2024

  37. [37]

    Schuster, J

    T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth (2024), arXiv:2407.07754 [quant-ph]

    work page arXiv 2024

  38. [38]

    S. T. Flammia and R. O’Donnell, Quantum chi-squared tomography and mutual information testing, Quantum 8, 1381 (2024)

    work page 2024

  39. [39]

    Lumbreras and M

    J. Lumbreras and M. Tomamichel, Linear bandits with polylogarithmic minimax regret, in Proceedings of Thirty Seventh Conference on Learning Theory , Proceedings of Machine Learning Research, Vol. 247 (PMLR, 2024) pp. 3644–3682

    work page 2024

  40. [40]

    Lumbreras, M

    J. Lumbreras, M. Terekhov, and M. Tomamichel, Learn- ing pure quantum states (almost) without regret (2024), arXiv:2406.18370 [quant-ph]

    work page arXiv 2024

  41. [41]

    Paulsen, Dilation theorems, in Completely Bounded Maps and Operator Algebras , Cambridge Studies in Ad- vanced Mathematics (Cambridge University Press, 2003) p

    V. Paulsen, Dilation theorems, in Completely Bounded Maps and Operator Algebras , Cambridge Studies in Ad- vanced Mathematics (Cambridge University Press, 2003) p. 43–57

    work page 2003

  42. [42]

    Shende, S

    V. Shende, S. Bullock, and I. Markov, Synthesis of quantum-logic circuits, IEEE Transactions on Computer- xvi Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006)

    work page 2006

  43. [43]

    R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Chri- standl, Quantum circuits for isometries, Physics Review A 93, 032318 (2016)

    work page 2016

  44. [44]

    M. A. Nielsen and I. L. Chuang, Quantum computa- tion and quantum information: 10th anniversary edition (Cambridge University Press, 2010)

    work page 2010

  45. [45]

    Selinger, Efficient Clifford+T approximation of single- qubit operators, Quantum Info

    P. Selinger, Efficient Clifford+T approximation of single- qubit operators, Quantum Info. Comput. 15, 159–180 (2015)

    work page 2015

  46. [46]

    extended

    A. Kay, When can a matrix be “extended” into a unitary? (2019)

    work page 2019

  47. [47]

    D. Lu, T. Xin, N. Yu, Z. Ji, J. Chen, G. Long, J. Baugh, X. Peng, B. Zeng, and R. Laflamme, Tomography is nec- essary for universal entanglement detection with single- copy observables, Physics Review Letters 116, 230501 (2016)

    work page 2016

  48. [48]

    Yu, Multipartite entanglement certification, with or without tomography, IEEE Transactions on Information Theory 66, 6369 (2020)

    N. Yu, Multipartite entanglement certification, with or without tomography, IEEE Transactions on Information Theory 66, 6369 (2020)

    work page 2020

  49. [49]

    J. T. Barreiro, M. M¨ uller, P. Schindler, D. Nigg, T. Monz, M. Chwalla, M. Hennrich, C. F. Roos, P. Zoller, and R. Blatt, An open-system quantum simulator with trapped ions, Nature 470, 486 (2011)

    work page 2011

  50. [50]

    Fl¨ uhmann and J

    C. Fl¨ uhmann and J. P. Home, Direct characteristic- function tomography of quantum states of the trapped- ion motional oscillator, Physics Review Letters 125, 043602 (2020)

    work page 2020

  51. [51]

    S. Chen, J. Li, and A. Liu, Optimal high-precision shadow estimation (2024), arXiv:2407.13874 [quant-ph]

    work page arXiv 2024

  52. [52]

    Grier, H

    D. Grier, H. Pashayan, and L. Schaeffer, Sample-optimal classical shadows for pure states, Quantum 8, 1373 (2024)

    work page 2024

  53. [53]

    H. C. Nguyen, J. L. B¨ onsel, J. Steinberg, and O. G¨ uhne, Optimizing shadow tomography with generalized mea- surements, Physics Review Letters 129, 220502 (2022)

    work page 2022

  54. [54]

    Grier, S

    D. Grier, S. Liu, and G. Mahajan, Improved classical shadows from local symmetries in the schur basis (2024), arXiv:2405.09525 [quant-ph]

    work page arXiv 2024

  55. [55]

    Gross, M

    D. Gross, M. Cramer, and K. Banaszek, Focus on quan- tum tomography, New J. Phys. 15, 125020 (2013). Appendix A: Some combinatorics We first equip ourselves with the following lemma. Lemma 21. The number of ways to divide n boxes into r groups is upper bounded by (n + 1)r−1. Proof. Suppose that we put n boxes in a line and then place r − 1 dividers to the...

    work page 2013