Pith. sign in

REVIEW 5 minor 2 cited by

Predicting Features of Quantum Systems from Very Few Measurements

T0 review · 0 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Random Clifford measurements, stored as a classical shadow, predict an exponential number of quantum features from only logarithmically many copies.

desk verdict The classical-shadow protocol is solid: the sample-complexity proof checks out, the lower bound is right up to a presentation-level overstatement, and the paper deserves a full referee. read the letter →

arxiv 1908.08909 v2 pith:TDAMYZMW submitted 2019-08-23 quant-ph cs.CLcs.ITcs.LGmath.ITmath.PR

Hsin-Yuan Huang , Richard Kueng This is my paper · ORCID
classification quant-phcs.CLcs.ITcs.LGmath.ITmath.PR MSC 81P6881P45 PACS 03.67.-a03.65.Wj
keywords classicalshadowsshadowtomographystabilizerstatesCliffordgroupmedianofmeansfidelityestimationentanglementwitnessesquantumstate
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

This paper establishes that a fixed, measurement-agnostic classical sketch of an unknown quantum state can predict exponentially many linear features of that state. The sketch, called the classical shadow, is built from random Clifford rotations followed by computational-basis measurements, and its size scales as log(M) times the largest Hilbert-Schmidt norm of the target observables, divided by epsilon squared. This sample count is independent of the system dimension and matches a fundamental information-theoretic lower bound for any procedure that uses fixed independent measurements. The paper also demonstrates numerically that classical shadows accurately estimate fidelities, entanglement witnesses, and other features for systems with up to 162 qubits.

What carries the argument

The central object is the classical shadow: a list of stabilizer states obtained from random Clifford measurements. The load-bearing identity is that qubit stabilizer states form a complex projective 3-design, which means sampling uniformly from them reproduces the first three moments of the Haar measure on pure states. This makes the mean and variance of the single-copy estimator exactly computable: for any observable O, the estimator o_hat = (2^n + 1)<s|O|s> - tr(O) has expectation tr(O rho) and variance at most 3 tr($O^{2}$). Median-of-means estimation then converts this bounded variance into a high-probability guarantee with only logarithmic dependence on the number of target functions.

What would settle it

Numerically sample the single-copy estimator (2^n + 1)<s|O|s> - tr(O) over uniformly random Clifford unitaries for a fixed traceless observable with tr($O^{2}$) = 1; if the empirical variance ever exceeds 3, Lemma 1 fails and the sample-complexity bound collapses. More directly, run the median-of-means protocol for M random rank-one projectors and test whether accuracy epsilon is reached with C log(M)/$epsilon^{2}$ copies for a fixed constant C.

Watch

Extended reading notes

Core claim

The central claim is that a classical shadow of size O(log(M) max_i tr($O_i^{2}$)/$epsilon^{2}$) suffices to predict M linear target functions tr(O_i rho) up to accuracy epsilon, for any n-qubit state rho. Each measurement is performed by applying a random Clifford circuit, measuring in the computational basis, and storing the resulting stabilizer state; prediction is then done by splitting the shadow into batches and taking the median of linear inversion estimates. Because the shadow size is independent of the dimension D = 2^n, the paper achieves an exponential compression in both the system size and the number of target functions for observables with bounded Hilbert-Schmidt norm. A matching lower bound shows that no prediction procedure based on fixed independent measurements can do substantially better, so the scaling is not an artifact of the method but a fundamental restriction.

Load-bearing premise

The entire sample-count guarantee rests on the mathematical fact that Clifford orbits reproduce the first three moments of the uniform Haar measure on pure states, so the variance of a single shadow estimate is bounded by 3 tr($O^{2}$); if that 3-design property failed, the advertised scaling would not hold.

Editorial extensions

If this is right

  • Fidelity to an exponentially large set of pure target states can be estimated simultaneously from O(log(M)/epsilon^2) copies, independent of the number of qubits.
  • Entanglement verification can check exponentially many witnesses at once without adapting the measurement procedure to any specific witness.
  • The sample complexity O(log(M) max tr(O_i^2)/epsilon^2) is optimal: any prediction method that uses fixed independent measurements must use at least that many copies.
  • For observables with exponentially large Hilbert-Schmidt norm, such as global Pauli strings, classical shadows require exponentially many copies, though they still give a square-root improvement over direct measurement of every Pauli term.
  • The protocol is classically tractable because stabilizer states are stored with O(n^2) bits and overlaps between stabilizer states are computed in O(n^2) time.

Reading between the lines

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

  • The 3-design argument suggests that classical shadows can be built from any unitary 3-design, not necessarily the full Clifford group, with the constant in the sample bound depending on the design's fourth-moment properties.
  • The classical shadow is a convenient data format for downstream machine-learning tasks: once the shadow is stored, predicting any linear feature is just a median of linear functions of stabilizer overlaps, which could be combined with trained models.
  • For few-body observables, a shadow based on random single-qubit Clifford rotations may achieve logarithmic scaling in the number of target features with a smaller constant than global Clifford measurements, though this is not analyzed here.
  • The lower-bound proof technique, which uses a random rotation inserted between the state preparation and the measurement, likely extends to other estimation tasks where the measurement is agnostic to the target function.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper introduces and analyzes a 'classical shadow' protocol for predicting linear features tr(O_i rho) of an unknown n-qubit state rho from independent random Clifford measurements. The protocol stores the classical descriptions of the resulting stabilizer states and uses median-of-means estimation to predict M features. The main formal result (Theorem 4, Appendix A) states that N = O(log(M/delta) max_i tr(O_i^2)/eps^2) single-copy measurements suffice to predict all M features to accuracy eps with failure probability at most delta, a bound independent of the Hilbert space dimension D = 2^n. Theorem 5 gives improved bounds for very large M, and Theorem 6 (Appendix B) provides a matching information-theoretic lower bound for any prediction procedure based on a fixed set of independent measurements, up to logarithmic factors. The paper also reports numerical experiments for GHZ states, toric-code ground states, and tripartite entanglement witnesses, comparing favorably with neural-network quantum state tomography.

Significance. If the central claim holds, the paper establishes an exponential compression in both the system dimension and the number of target functions for observables with bounded Hilbert-Schmidt norm, while using only tractable Clifford measurements. The main proof is complete and verifiable: Lemma 1 derives unbiasedness and the variance bound Var <= 3 tr(O^2) from the stabilizer-state 3-design property, and the median-of-means argument with a union bound yields the advertised scaling. The lower bound in Appendix B is a careful adaptation of the Flammia et al. communication argument to feature prediction, and it is not circular: it does not rely on the upper-bound construction. The paper is also commendably honest about limitations, explicitly discussing the unfavorable scaling for observables such as Pauli strings and the distinction between classical and quantum fidelity in the numerical comparisons. The numerical experiments extend to 162 qubits and support the theoretical claims in the tested regimes.

minor comments (5)
  1. [Section I.E, Theorem 2 (informal)] The informal statement that any prediction procedure based on a fixed set of independent measurements 'requires at least log(M) max_i tr(O_i^2)/eps^2 state copies' overstates the formal Theorem 6, whose proven bound is the minimum of three terms. The B log(M)/eps^2 term is not the operative bound when M is super-exponential in D, so the informal statement should be qualified to match Theorem 6.
  2. [Appendix B, case 1 (around Eq. (B1) and Lemma 2)] The case-1 construction assumes M <= exp(D/32), but Lemma 2 requires M <= exp(rD/32) = exp(BD/128); for B < 4 these assumptions differ. Since cases 2 and 3 alone cover all parameter regimes, this gap does not affect the formal theorem, but the exposition should either impose the stronger condition or explicitly note that the gap is covered by cases 2 and 3.
  3. [Theorem 5 proof, Appendix A] There is a typo in the error-bound chain: '|ˆo = tr(Oρ)|' should read '|\hat o - tr(Oρ)|'.
  4. [Abstract and Introduction] The phrase 'order of log(M) measurements' could be misread as a statement about distinct measurement settings; it refers to the number of single-copy measurements, i.e., state copies, and should be made explicit.
  5. [Theorem 6, Appendix B] The formal lower-bound statement says the machine predicts 'with high probability' without specifying the failure probability or explicitly stating that the epsilon guarantee is uniform over the M features and all states. The proof assumes such a uniform guarantee; the statement should be aligned with the proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the classical-shadow sample-complexity bound and matching lower bound are derived from independent mathematical facts, with no fitted inputs or self-citational forcing.

full rationale

The central claim (Theorem 4) is derived, not fitted: Lemma 1 bounds the single-copy estimator variance by 3 tr(O^2) using the stabilizer-state 3-design property, and Theorem 3's median-of-means concentration plus a union bound over M yields N = 204 log(2M/delta) max tr(O_i^2)/eps^2. No parameter is calibrated to data, and the 'predictions' are bounded from an a priori variance estimate rather than from any fitted value. The only self-citation is the 3-design fact [39], but the paper also cites independent proofs by Webb [56] and Zhu [58], and the fact is an external mathematical theorem whose assumptions do not include the target sample-complexity result. The lower bound (Theorem 6) is an independent communication argument via Fano and data-processing inequalities with an explicit codebook construction; it does not invoke the upper bound. The informal overstatement in Theorem 2 and the technical condition in the case-1 portion of Lemma 2 are presentation/correctness issues, not circularity. The numerical experiments are illustrative and not load-bearing. Thus the derivation chain is self-contained against external results and warrants a score of 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The upper bound rests on standard facts: Clifford group as a unitary 3-design, Chernoff bounds for median-of-means, and union bound. The lower bound uses Fano's inequality and data processing. No free parameters or invented entities are introduced. The main proof leans on a Clifford 3-design result co-authored by one of the present authors, but it is a prior theorem with independent proofs by Webb and Zhu, so the dependency is not circular. The LWE hardness conjecture appears only in the numerical discussion of why neural-network tomography may struggle on structured states; it is not used in the main theorem and is not needed to establish the central claim.

assumptions (5)
  • standard math Stabilizer states form a complex projective 3-design (equivalently, the Clifford group is a unitary 3-design).
    Used in Fact 1 and Eqs. (A2)-(A3) to obtain the mean and variance of the single-copy linear inversion estimator in Lemma 1. Without this property the variance bound Var <= 3 tr(O^2) would fail.
  • standard math Chernoff's inequality governs the median-of-means estimator.
    Theorem 3 uses it to convert bounded-variance estimates into a high-probability guarantee with failure probability 2 exp(-K/2), which is then union-bounded over M features.
  • standard math Fano's inequality and the data processing inequality for mutual information.
    Used in Appendix B to lower-bound the number of copies N by relating feature prediction to a communication task between Alice and Bob with an adversary (Loki).
  • standard math The probabilistic method guarantees the existence of rank-r subspace projectors with low overlap (Lemma 2).
    Used to construct the codebook in the lower-bound proof; relies on Grassmannian measure concentration and a union bound.
  • domain assumption Learning parity with error (LWE-type) is computationally hard.
    Invoked only in Appendix C to argue that neural-network tomography will struggle on certain structured states. Not needed for the main sample-complexity theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Predicting Features of Quantum Systems from Very Few Measurements." pith.science (2026). https://pith.science/paper/TDAMYZMW

@misc{pith2026190808909,
  author       = {Pith},
  title        = {Pith review of: Predicting Features of Quantum Systems from Very Few Measurements},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TDAMYZMW}},
  note         = {Machine review of arXiv:1908.08909}
}
read the original abstract

Predicting features of complex, large-scale quantum systems is essential to the characterization and engineering of quantum architectures. We present an efficient approach for constructing an approximate classical description, called the classical shadow, of a quantum system from very few quantum measurements that can later be used to predict a large collection of features. This approach is guaranteed to accurately predict M linear functions with bounded Hilbert-Schmidt norm from only order of log(M) measurements. This is completely independent of the system size and saturates fundamental lower bounds from information theory. We support our theoretical findings with numerical experiments over a wide range of problem sizes (2 to 162 qubits). These highlight advantages compared to existing machine learning approaches.

Figures

Figures reproduced from arXiv: 1908.08909 by the authors.

Figure 1
Figure 1. Caricature of classical shadows: In the data acquisition phase, we perform random Clifford measure￾ments on independent copies of a n-qubit system to obtain a classical representation of the quantum system – the classical shadow. Such classical shadows facilitate accurate prediction of a large number of features using a simple median-of-means protocol. In this work, we combine the mindset of shadow tomography [1] (p… view at source ↗
Figure 2
Figure 2. Comparison between classical shadow and neural network tomography (NNQST); GHZ states. Left: Number of measurements required to identify an n-qubit GHZ state with 0.99 fidelity. The shaded regions are the standard deviation of the needed number of experiments over ten independent runs. Right: Estimated fidelity between a perfect GHZ target state and a noisy preparation, where Z-errors can occur with probability p ∈ … view at source ↗
Figure 3
Figure 3. Comparison between classical shadow and neural network tomography (NNQST); toric code: Left: Number of measurements required for neural network tomography to identify a particular toric-code ground state. We use classical fidelity for NNQST, which is an upper bound for quantum fidelity. Right: Performance of classical shadows for the same problem. We use quantum fidelity for classical shadows. The shaded regions are… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Detection of GHZ-type entanglement for 3-qubit states: Left: Schematic illustration of 3-partite entanglement. Entanglement witnesses are linear functions that separate part of one entanglement class from all other classes. Right: Number of entanglement witnesses vs. n…
Figure 5
Figure 5. Figure 5: Illustration of the communication protocol behind Theorem 6: Two parties – Alice and Bob – devise a protocol that allows them to communicate classical bit strings: Alice encodes a bit string X in a quantum state and sends N independent copies of the state to Bob. Bob p…
Figure 6
Figure 6. Figure 6: Stabilizers and de-stabilizers of toric code that encodes [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Efficiently learning fermionic unitaries with few non-Gaussian gates

    quant-ph 2025-04 accept novelty 7.0 of 10

    An efficient learning algorithm reconstructs fermionic circuits built from Gaussian unitaries plus a constant number of parity-preserving non-Gaussian gates, up to small diamond-norm error.

  2. Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information

    quant-ph 2025-02 reject novelty 6.0 of 10

    An adaptive estimator based on empirical Bernstein stopping reduces the number of measurements needed to estimate ground-state energies with rigorous error bounds, by up to an order of magnitude in numerical benchmarks.

Reference graph

Works this paper leans on

81 extracted references · 68 canonical work pages · cited by 2 Pith papers

  1. [1]

    In this case, a classical shadow of exponential size is required to accurately predict a single expectation value

    = tr (I⊗n) = 2n. In this case, a classical shadow of exponential size is required to accurately predict a single expectation value. In contrast, a direct spin measurement achieves the same accuracy with an order of1/ϵ2 copies of the stateρ only. 4 Figure 2: Comparison between classical shadow and neural network tomography (NNQST); GHZ states. Left: Number...

  2. [2]

    Applications range from quantum error correction [46], to measurement-based quantum computation [9, 49] and randomized benchmarking [15, 37, 43]

    The stabilizer formalism Clifford circuits were introduced by Gottesman [24] and form an indispensable tool in quantum in- formation processing. Applications range from quantum error correction [46], to measurement-based quantum computation [9, 49] and randomized benchmarking [15, 37, 43]. For systems comprised ofn qubits, the Clifford group is generated by...

    work page

  3. [3]

    A single stabilizer sam- ple, i.e

    Median of means estimation Lemma 1 sets the stage for successful feature estimation via classical shadows. A single stabilizer sam- ple, i.e. a classical shadow of sizeN = 1, correctly predicts any linear feature in expectation. Convergence to this desired expectation value can be boosted by forming empirical averages of multiple independent repetitions. ...

    work page

  4. [4]

    We choose to rephrase our first main result in this language to maintain coherence with the previous two subsections

    Feature prediction using classical shadows and median of means According to Fact 1, classical shadows are synonymous with independent repetitions of the stabilizer measurement (A1). We choose to rephrase our first main result in this language to maintain coherence with the previous two subsections. Theorem 4 (Detailed restatement of Theorem 1). Fix a colle...

    work page

  5. [5]

    Fix a sequence of POVMsF (1),...,F (N )

    Detailed statement and proof idea Theorem 6 (Detailed restatement of Theorem 2). Fix a sequence of POVMsF (1),...,F (N ). Suppose that given anyM features 0≼ O1,O 2,...,O M ≼ I with maxi ( ‖Oi‖2 2 ) ≤ B, there exists a machine (with arbitrary runtime as long as it always terminates) that can use the measurement outcomes of F (1),...,F (N ) on N copies of ...

    work page

  6. [6]

    Alice and Bob first agree on a codebook for encoding any integer selected from{1,...,M } in a quantum state of dimensionD

    Description of the communication protocol For now, assumeM≤ exp(D/32) and show how Alice can communicate any integer in{1,...,M } to Bob. Alice and Bob first agree on a codebook for encoding any integer selected from{1,...,M } in a quantum state of dimensionD. The quantum states in the codebook areρ1,...,ρ M. Alice and Bob also 13 … N copies … N copies … M...

    work page

  7. [7]

    Alice randomly selects an integerX from{1,...,M }

    work page

  8. [8]

    Alice preparesN copies of the code-stateρX according associated toX and sends them to Bob

    work page

Show all 81 references
  1. [9]

    Bob performs POVMsF (i) on individual states and receives a string of measurement outcomesY

  2. [10]

    Bob inputsY into the feature prediction machine to estimatetr(O1ρX),..., tr(OMρX)

  3. [11]

    The working assumption is that the feature prediction machine can estimatetr(O1ρX),..., tr(OMρX) withinϵ-error and high success probability

    Bob findsX that has the largesttr(OXρX). The working assumption is that the feature prediction machine can estimatetr(O1ρX),..., tr(OMρX) withinϵ-error and high success probability. This in turn ensures that this plain communication protocol is mostly successful, i.e.X =X with ...

  4. [12]

    We refer to standard textbooks for details

    Information-theoretic analysis The following arguments are based on basic concepts from information theory. We refer to standard textbooks for details. 14 Thecommunicationprotocolisguaranteedtoworkwithhighprobability, ensuringthatBob’srecovered message ˆX equals Alice’s inputX...

  5. [13]

    Detailed construction of quantum encoding and linear prediction decoding We now construct a codebook ρ1,...,ρ M and linear features 0 ≼ O1,O 2,...,O M ≼ I with maxi ( ‖Oi‖2 2 ) ≤B that obey two key properties:

  6. [14]

    (B1) holds

    the code statesρ1,...,ρ M obey the technical requirement displayed in Eq. (B1) holds

  7. [15]

    (B2) The second condition requires eachρi to be distinguishable fromρ1,...,ρ M via linear featuresOi

    the linear featuresO1,...,O M are capable of identifying concrete code states: tr(Oiρi)≥ max j⁄=i tr(Ojρi) + 3ϵ for all 1≤i≤M. (B2) The second condition requires eachρi to be distinguishable fromρ1,...,ρ M via linear featuresOi. The first condition, on the contrary, requiresρX ...

  8. [16]

    Sample a Clifford unitaryU from the Clifford group using the algorithm proposed in [38]. This Clifford unitary is parameterized by(α,β,γ,δ,r,s ) which fully characterize its action on Pauli operators: UXjU† = (−1)rjΠn i=1Xαji i Zβji i and UZjU† = (−1)sjΠn i=1Xγji i Zδji i for all...

  9. [17]

    Given a unitaryU parameterized by (α,β,γ,δ,r,s ), we can applyU on any stabilizer state by changing the stabilizer generators and the destabilizers as defined in [2]

  10. [18]

    The operational definition of mixed states allows us to extend this formalism

    Measurement in the Z-basis can be done using the standard algorithm provided in [2]. The operational definition of mixed states allows us to extend this formalism. Mixed states arise from sampling a pure state ensemble:ρ =∑ ipi|ψi⟩⟨ψi|. For neural network quantum state tomograp...

  11. [19]

    Aaronson

    S. Aaronson. Shadow tomography of quantum states. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 325–338, New York, NY, USA, 2018. ACM

    2018

  12. [20]

    Aaronson and D

    S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits.Phys. Rev. A, 70:052328, Nov 2004

    2004

  13. [21]

    Aaronson and G

    S. Aaronson and G. N. Rothblum. Gentle measurement of quantum states and differential privacy. InTo appear on the 51th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 2019. 19

    2019

  14. [22]

    A. Acín, D. Bruß, M. Lewenstein, and A. Sanpera. Classification of mixed three-qubit states.Phys. Rev. Lett., 87:040401, Jul 2001

    2001

  15. [23]

    Banaszek, M

    K. Banaszek, M. Cramer, and D. Gross. Focus on quantum tomography.New J. Phys., 15(12):125020, dec 2013

    2013

  16. [24]

    A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506–519, 2003

    2003

  17. [25]

    Blume-Kohout

    R. Blume-Kohout. Optimal, reliable estimation of quantum states.New J. Phys., 12(4):043034, apr 2010

    2010

  18. [26]

    F. G. Brandão, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore, and X. Wu. Quantum sdp solvers: Large speed-ups, optimality, and applications to quantum learning.arXiv preprint arXiv:1710.02581, 2017

    2017 arXiv

  19. [27]

    H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest. Measurement-based quantum computation. Nat. Phys., 5:19 EP –, Jan 2009

    2009

  20. [28]

    Carrasquilla, G

    J. Carrasquilla, G. Torlai, R. G. Melko, and L. Aolita. Reconstructing quantum states with generative models. Nat. Mach. Intell., 1(3):155, 2019

    2019

  21. [29]

    H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics, 23:493–507, 1952

    1952

  22. [30]

    M.Cramer, M.B.Plenio, S.T.Flammia, R.Somma, D.Gross, S.D.Bartlett, O.Landon-Cardinal, D.Poulin, and Y.-K. Liu. Efficient quantum state tomography.Nat. Comm., 1:149, 2010

    2010

  23. [31]

    Crawford, B

    O. Crawford, B. van Straaten, D. Wang, T. Parks, E. Campbell, and S. Brierley1. Efficient quantum measurement of pauli operators.arXiv preprint arXiv:1908.06942, 2019

    1908 arXiv

  24. [32]

    Dennis, A

    E. Dennis, A. Kitaev, and J. Preskill. Topological quantum memory. volume 43, pages 4452–4505. 2002. Quantum information theory

    2002

  25. [33]

    Emerson, R

    J. Emerson, R. Alicki, and K. Życzkowski. Scalable noise estimation with random unitary operators.J. Opt. B Quantum Semiclass. Opt., 7(10):S347–S352, 2005

    2005

  26. [34]

    R. M. Fano. Transmission of information: A statistical theory of communications. The M.I.T. Press, Cambridge, Mass.; John Wiley & Sons, Inc., New York-London, 1961

    1961

  27. [35]

    S. T. Flammia, D. Gross, Y.-K. Liu, and J. Eisert. Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators.New J. Phys., 14(9):095022, sep 2012

    2012

  28. [36]

    S. T. Flammia, D. Gross, Y.-K. Liu, and J. Eisert. Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators.New J. Phys., 14(9):095022, 2012

    2012

  29. [37]

    S. T. Flammia and Y.-K. Liu. Direct fidelity estimation from few pauli measurements.Phys. Rev. Lett., 106:230501, Jun 2011

    2011

  30. [38]

    Friis, G

    N. Friis, G. Vitagliano, M. Malik, and M. Huber. Entanglement certification from theory to experiment. Nat. Rev. Phys., 1(1):72–87, 2019

    2019

  31. [39]

    Gao and L.-M

    X. Gao and L.-M. Duan. Efficient representation of quantum many-body states with deep neural networks. Nat. Commun., 8(1):662, 2017

    2017

  32. [40]

    H. J. Garcia, I. L. Markov, and A. W. Cross. Efficient inner-product algorithm for stabilizer states.arXiv preprint arXiv:1210.6646, 2012

    2012 arXiv

  33. [41]

    Gosset and J

    D. Gosset and J. Smolin. A compressed classical description of quantum states. arXiv preprint arXiv:1801.05721, 2018

    2018 arXiv

  34. [42]

    Gottesman

    D. Gottesman. Stabilizer codes and quantum error correction. Caltech Ph. D. PhD thesis, Thesis, eprint: quant-ph/9705052, 1997

    1997 arXiv

  35. [43]

    D. M. Greenberger, M. A. Horne, and A. Zeilinger.Going Beyond Bell’s Theorem, pages 69–72. Springer Netherlands, Dordrecht, 1989

    1989

  36. [44]

    D. Gross. Hudson’s theorem for finite-dimensional quantum systems.J. Math. Phys., 47(12):122107, 25, 2006

    2006

  37. [45]

    Gross, F

    D. Gross, F. Krahmer, and R. Kueng. A partial derandomization of PhaseLift using spherical designs.J. Fourier Anal. Appl., 21(2):229–266, 2015

    2015

  38. [46]

    Gross, Y.-K

    D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert. Quantum state tomography via compressed sensing. Phys. Rev. Lett., 105:150401, Oct 2010

    2010

  39. [47]

    M. Guta, J. Kahn, R. Kueng, and J. A. Tropp. Fast state tomography with optimal error bounds.arXiv preprint arXiv:1809.11162, 2018

    2018 arXiv

  40. [48]

    Gühne and G

    O. Gühne and G. Tóth. Entanglement detection.Phys. Rep., 474(1):1 – 75, 2009

    2009

  41. [49]

    J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu. Sample-optimal tomography of quantum states.IEEE T. Inform. Theory, 63(9):5628–5641, 2017

    2017

  42. [50]

    M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, and H.-J. Briegel. Entanglement in graph states and its applications. In Quantum computers, algorithms and chaos, volume 162 ofProc. Internat. School Phys. Enrico Fermi, pages 115–218. IOS, Amsterdam, 2006

    2006

  43. [51]

    Z. Hradil. Quantum-state estimation.Phys. Rev. A, 55:R1561–R1564, Mar 1997

    1997

  44. [52]

    W. J. Huggins, J. McClean, N. Rubin, Z. Jiang, N. Wiebe, K. B. Whaley, and R. Babbush. Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers.arXiv preprint arXiv:1907.13117, 2019

    1907 arXiv

  45. [53]

    A. Jena, S. Genin, and M. Mosca. Pauli partitioning with respect to gate sets. arXiv preprint arXiv:1907.07859, 2019

    1907 arXiv

  46. [54]

    M. R. Jerrum, L. G. Valiant, and V. V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci., 43(2-3):169–188, 1986

    1986

  47. [55]

    Knill, D

    E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, 20 and D. J. Wineland. Randomized benchmarking of quantum gates.Phys. Rev. A, 77:012307, Jan 2008

    2008

  48. [56]

    Koenig and J

    R. Koenig and J. A. Smolin. How to efficiently select an arbitrary Clifford group element.J. Math. Phys., 55(12):122202, 12, 2014

    2014

  49. [57]

    Kueng and D

    R. Kueng and D. Gross. Qubit stabilizer states are complex projective 3-designs. arXiv preprint arXiv:1510.02767, 2015

    2015 arXiv

  50. [58]

    Kueng, H

    R. Kueng, H. Rauhut, and U. Terstiege. Low rank matrix recovery from rank one measurements.Appl. Comput. Harmon. Anal., 42(1):88–116, 2017

    2017

  51. [59]

    Kueng, H

    R. Kueng, H. Zhu, and D. Gross. Low rank matrix recovery from clifford orbits. arXiv preprint arXiv:1610.08070, 2016

    2016 arXiv

  52. [60]

    B. P. Lanyon, C. Maier, M. Holzäpfel, T. Baumgratz, C. Hempel, P. Jurcevic, I. Dhand, A. S. Buyskikh, A. J. Daley, M. Cramer, M. B. Plenio, R. Blatt, and C. F. Roos. Efficient tomography of a quantum many-body system. Nat. Phys., 13:1158 EP –, Sep 2017

    2017

  53. [61]

    Magesan, J

    E. Magesan, J. M. Gambetta, and J. Emerson. Scalable and robust randomized benchmarking of quantum processes. Phys. Rev. Lett., 106:180504, May 2011

    2011

  54. [62]

    A. S. Nemirovsky and D. B. a. Yudin.Problem complexity and method efficiency in optimization. A Wiley- Interscience Publication. John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson, Wiley-Interscience Series in Discrete Mathematics

    1983

  55. [63]

    M. A. Nielsen. Cluster-state quantum computation.Rep. Math. Phys., 57(1):147–161, 2006

    2006

  56. [64]

    M. A. Nielsen and I. L. Chuang.Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000

    2000

  57. [65]

    O’Donnell and J

    R. O’Donnell and J. Wright. Efficient quantum tomography. InProceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 899–912, New York, NY, USA, 2016. ACM

    2016

  58. [66]

    Preskill

    J. Preskill. Quantum computing in the nisq era and beyond.Quantum, 2:79, 2018

    2018

  59. [67]

    Raussendorf and H

    R. Raussendorf and H. J. Briegel. A one-way quantum computer.Phys. Rev. Lett., 86:5188–5191, May 2001

    2001

  60. [68]

    O. Regev. On lattices, learning with errors, random linear codes, and cryptography.Journal of the ACM (JACM), 56(6):34, 2009

    2009

  61. [69]

    J. M. Renes, R. Blume-Kohout, A. J. Scott, and C. M. Caves. Symmetric informationally complete quantum measurements. J. Math. Phys., 45(6):2171–2180, 2004

    2004

  62. [70]

    I. Roth, R. Kueng, S. Kimmel, Y.-K. Liu, D. Gross, J. Eisert, and M. Kliesch. Recovering quantum gates from few average gate fidelities.Phys. Rev. Lett., 121:170502, Oct 2018

    2018

  63. [71]

    Shalev-Shwartz, O

    S. Shalev-Shwartz, O. Shamir, and S. Shammah. Failures of gradient-based deep learning. InProceedings of the 34th International Conference on Machine Learning-Volume 70, pages 3067–3075. JMLR. org, 2017

    2017

  64. [72]

    Sugiyama, P

    T. Sugiyama, P. S. Turner, and M. Murao. Precision-guaranteed quantum tomography.Phys. Rev. Lett., 111:160406, Oct 2013

    2013

  65. [73]

    Torlai, G

    G. Torlai, G. Mazzola, J. Carrasquilla, M. Troyer, R. Melko, and G. Carleo. Neural-network quantum state tomography. Nat. Phys., 14(5):447, 2018

    2018

  66. [74]

    Z. Webb. The clifford group forms a unitary 3-design.arXiv preprint arXiv:1510.02769, 2015

    2015 arXiv

  67. [75]

    T.-C. Yen, V. Verteletsky, and A. F. Izmaylov. Measuring all compatible operators in one series of a single- qubit measurements using unitary transformations.arXiv preprint arXiv:1907.09386, 2019

    1907 arXiv

  68. [76]

    H. Zhu. Multiqubit clifford groups are unitary 3-designs.Phys. Rev. A, 96:062336, Dec 2017

    2017

  69. [77]

    [1] it was actually S.T.˜Flammia who originally suggested the name shadow tomography

    According to Ref. [1] it was actually S.T.˜Flammia who originally suggested the name shadow tomography

  70. [78]

    If|ψ⟩ is a stabilizer state, the Gottsman-Knill theorem allows for evaluation inO(n2)-time only

    The runtime of Algorithm 1 is dominated by the cost of computing squared inner products|⟨ψ|Ui|ˆbi⟩|2 in 2n dimensions. If|ψ⟩ is a stabilizer state, the Gottsman-Knill theorem allows for evaluation inO(n2)-time only

  71. [79]

    Av is the product of four Pauli-X operators around a vertexv, while Bp is the product of four Pauli-Z operators around the plaquettep

  72. [80]

    The scaling symbol ˜O suppresses logarithmic expressions in other problem-specific parameters

  73. [81]

    However, not entirely malicious, he often comes around and tries to remedy dire consequences of his actions in the last minute

    In Norse mythology, Loki is infamous for mischief and trickery. However, not entirely malicious, he often comes around and tries to remedy dire consequences of his actions in the last minute

Pith tools

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