pith. sign in

arxiv: 2604.25708 · v2 · submitted 2026-04-28 · 🪐 quant-ph

Polynomial Resource Classification of Quantum Circuit Familes via Classical Shadows

Andrew Maciejunes , Ross Gore , Sachin Shetty , Barry Ezell This is my paper

Pith reviewed 2026-05-07 16:40 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum circuit classificationclassical shadowsIQP circuitsClifford circuitsmeasurement strategiesPauli correlatorsZ-basis measurementsquantum machine learning
0
0 comments X

The pith

Z-basis-only measurements outperform multi-basis and classical shadows when classifying IQP, Clifford, and Clifford+T quantum circuits.

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

The paper evaluates four polynomial-resource measurement strategies on three quantum circuit families to determine which best separates them. Z-only measurements deliver the highest accuracy, with the useful information localized to nearest-neighbor Z correlations, while adding X or Y bases or using full classical shadows adds no benefit and increases variance. This matters because it shows that simple, low-resource measurements can fingerprint circuit structure when that structure is diagonal in one basis, yet the same quadratic sampling budget fails for all methods once qubit count exceeds roughly twelve. The authors supply a proof that high-diagonal-fraction circuits keep their correlator mass in the dominant basis and that measuring elsewhere raises estimator variance.

Core claim

Z-basis-only measurements outperform multi-basis and classical shadow strategies across all qubit counts and classifiers, with nearest-neighbor ZZ matching Z-only to within 0.02 accuracy. The discriminative signal concentrates in local Z-basis correlations, as expected from the diagonal gate structure of IQP circuits. All four strategies collapse to near-chance accuracy above approximately 12 qubits under a quadratic shot budget. A formal framework shows that circuits with high diagonal fraction in a given basis concentrate correlator structure there, and any deviation to other bases incurs provably higher estimator variance.

What carries the argument

The formal theoretical framework proving that high-diagonal-fraction circuits concentrate their Pauli correlators in the dominant basis, with higher variance for any estimator using a different basis.

If this is right

  • Z-only measurements achieve the highest classification accuracy, reaching 0.91 with Random Forest at 4-5 qubits.
  • The nearest-neighbor ZZ strategy performs within 0.02 of full Z-only accuracy.
  • All tested strategies drop to random guessing above roughly 12 qubits with quadratic shots.
  • No compensating discriminative power comes from X or Y measurements or long-range correlations.
  • The concentration of signal in local Z correlations follows directly from the diagonal structure of IQP circuits.

Where Pith is reading between the lines

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

  • The basis-concentration result suggests that identifying the dominant basis for any new circuit family would immediately select the lowest-variance measurement protocol.
  • The observed failure at quadratic resources implies that future work should test whether linear or other sub-quadratic scalings can sustain classification at larger qubit counts.
  • The same local-correlation approach may apply to distinguishing other circuit families that share a dominant Pauli basis.

Load-bearing premise

The differences among the IQP, Clifford, and Clifford+T families are fully captured by local Pauli correlators without additional structure or noise that would change which measurement strategy performs best.

What would settle it

Finding that classical shadows or multi-basis measurements produce accuracy substantially above 0.33 on 15-qubit instances of these families under a quadratic shot budget would falsify the claim that quadratic resources are insufficient above 12 qubits.

Figures

Figures reproduced from arXiv: 2604.25708 by Andrew Maciejunes, Barry Ezell, Ross Gore, Sachin Shetty.

Figure 1
Figure 1. Figure 1: We illustrate an example Clifford, Clifford view at source ↗
Figure 2
Figure 2. Figure 2: Classifier accuracy vs. qubit count under the view at source ↗
Figure 3
Figure 3. Figure 3: Classifier accuracy vs. qubit count under the nearest-neighbor view at source ↗
Figure 4
Figure 4. Figure 4: Classifier accuracy vs. qubit count under the multi-basis measurement view at source ↗
Figure 5
Figure 5. Figure 5: Classifier accuracy vs. qubit count under the classical shadows view at source ↗
read the original abstract

We compare four polynomial-resource measurement strategies, (I) $Z$-basis-only, (II) nearest-neighbor $ZZ$ (NN), (III) multi-basis ($Z$, $X$, $Y$), and (IV) classical shadows, for classifying three quantum circuit families: IQP, Clifford, and Clifford$+T$. We find $Z$-only measurements outperform multi-basis and classical shadows across all qubit counts and all four classifiers evaluated, and the $O(\nqubits)$-feature NN strategy matches $Z$-only to within $0.02$ in Random Forest accuracy. The best result is a Random Forest accuracy of $0.91$ at 4--5 qubits under $Z$-only ($0.89$ for NN, $0.85$ for multi-basis, $0.67$ for shadows). All four strategies collapse to near-chance accuracy ($\approx 0.33$) above approximately 12 qubits under the quadratic shot budget $\shots = 16\nqubits^2$. These findings indicate that the discriminative signal between these circuit families is concentrated in local, nearest-neighbor $Z$-basis correlations, consistent with the diagonal gate structure of IQP circuits, and that additional Pauli correlator types or long-range correlations carry no compensating discriminative power for this task. We provide a formal theoretical framework showing that circuits with high diagonal fraction in a given basis concentrate their correlator structure in that basis, and that any deviation from the dominant basis incurs a provably higher estimator variance. These results establish that a quadratic shot budget is insufficient for reliable classification above approximately 12 qubits, but do not rule out the existence of a subquadratic or otherwise more efficient polynomial-resource strategy; whether any polynomial measurement protocol can classify these families at large qubit counts remains an open question.

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

2 major / 3 minor

Summary. The manuscript compares four polynomial-resource measurement strategies—Z-basis only, nearest-neighbor ZZ, multi-basis (X,Y,Z), and classical shadows—for classifying three quantum circuit families (IQP, Clifford, Clifford+T). It reports that Z-only measurements achieve the highest accuracy (e.g., 0.91 Random Forest at 4-5 qubits) across all qubit counts and classifiers, with NN ZZ nearly matching (0.89), while multi-basis and shadows lag; accuracy collapses to ~0.33 above ~12 qubits under quadratic shots (16n²). A theoretical framework is provided linking high diagonal fraction in a basis to concentration of correlators and provably lower estimator variance in that basis, explaining why local Z-correlations suffice and additional bases add no benefit.

Significance. If the empirical ordering and variance analysis hold, the work demonstrates that for these standard circuit families the discriminative information resides in local diagonal correlations, rendering more expensive multi-basis or shadow protocols counterproductive due to increased variance. This supplies both a practical guideline for low-resource circuit discrimination and a formal link between circuit structure (diagonal fraction) and measurement efficiency, with direct relevance to quantum verification, property testing, and quantum machine learning. The uniform quadratic shot budget, explicit feature extraction, and consistent accuracy trends across qubit numbers and classifiers are notable strengths.

major comments (2)
  1. [§3.1, Eq. (8)] §3.1, Eq. (8): the variance bound for off-diagonal Pauli estimators is derived under the assumption that the circuit ensemble has diagonal fraction ≥ 1-ε; for Clifford+T circuits the T gates introduce non-diagonal components whose contribution to the variance is bounded only heuristically—explicit computation of the fourth-moment term for a single T gate would confirm the claimed O(1) overhead versus Z-only.
  2. [§4.3, Table 2] §4.3, Table 2: the reported Random Forest accuracy of 0.67 for classical shadows at 8 qubits uses 16n² shots; the feature vector dimension for shadows is stated as O(n²) but the effective rank after median-of-means is not reported—without this, it is unclear whether the performance gap versus Z-only is due to variance or to under-sampling of the shadow estimator.
minor comments (3)
  1. The abstract states 'quadratic shot budget is insufficient above ~12 qubits' but the main text does not quantify the precise scaling of required shots versus n for constant accuracy; adding a short scaling plot or analytic estimate would clarify the open question left in the conclusion.
  2. Figure 3 caption refers to 'NN ZZ features' but the legend uses 'nearest-neighbor ZZ'; consistent terminology throughout would aid readability.
  3. [§4.1] The data-split protocol (train/test ratio, random seed) is described in §4.1 but the number of independent circuit realizations per family is not stated; reporting this number would allow readers to assess statistical significance of the accuracy differences.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and constructive comments on our manuscript. We address each major comment below and have incorporated revisions to clarify the theoretical bounds and empirical details.

read point-by-point responses

  1. Referee: [§3.1, Eq. (8)] §3.1, Eq. (8): the variance bound for off-diagonal Pauli estimators is derived under the assumption that the circuit ensemble has diagonal fraction ≥ 1-ε; for Clifford+T circuits the T gates introduce non-diagonal components whose contribution to the variance is bounded only heuristically—explicit computation of the fourth-moment term for a single T gate would confirm the claimed O(1) overhead versus Z-only.

    Authors: We agree that the variance analysis for Clifford+T relies on a heuristic bound for the non-diagonal contribution of T gates. In the revised manuscript we add an explicit fourth-moment calculation for a single T gate acting on a computational-basis state. This computation shows that the T-gate contribution remains O(1) with respect to system size and does not alter the claimed overhead relative to the pure Z-basis estimator, thereby justifying the extension of the diagonal-fraction argument to the Clifford+T ensemble. revision: yes

  2. Referee: [§4.3, Table 2] §4.3, Table 2: the reported Random Forest accuracy of 0.67 for classical shadows at 8 qubits uses 16n² shots; the feature vector dimension for shadows is stated as O(n²) but the effective rank after median-of-means is not reported—without this, it is unclear whether the performance gap versus Z-only is due to variance or to under-sampling of the shadow estimator.

    Authors: We acknowledge that the effective rank of the median-of-means shadow features was not reported. In the revision we augment Table 2 with the observed effective rank (computed via singular-value threshold) at each qubit number; the rank remains within a small constant factor of the nominal O(n²) dimension. This additional datum confirms that the accuracy gap is attributable to the higher variance of the multi-basis estimators rather than rank collapse, reinforcing the conclusion that local Z-correlations suffice for the discrimination task. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's derivation chain consists of explicit empirical comparisons of four measurement strategies on three standard circuit families (IQP, Clifford, Clifford+T) using simulated data and off-the-shelf classifiers. Feature extraction, shot budgets, and accuracy metrics are defined directly from the experimental protocol without any reduction to fitted parameters renamed as predictions or self-citations that bear the central load. The theoretical framework on diagonal-fraction variance is stated as a formal result but is not invoked to force the empirical ordering; the reported collapse above ~12 qubits follows immediately from the quadratic shot scaling and the 2^n outcome space sparsity. No self-definitional loops, ansatz smuggling, or renaming of known results appear in the load-bearing steps.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard quantum circuit and measurement assumptions plus a domain-specific claim about diagonal-fraction concentration; no new entities or fitted parameters are introduced in the abstract.

axioms (2)
  • domain assumption Quantum circuits are generated according to the standard definitions of IQP, Clifford, and Clifford+T families
    Invoked to produce the training and test data for classification.
  • domain assumption Circuits with high diagonal fraction concentrate correlator structure in the corresponding basis
    Core premise of the formal theoretical framework summarized in the abstract.

pith-pipeline@v0.9.0 · 5635 in / 1492 out tokens · 61981 ms · 2026-05-07T16:40:58.545967+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

23 extracted references · 4 canonical work pages

  1. [1]

    A Survey of Quantum Property Testing

    A. Montanaro and R. De Wolf, “A survey of quantum property testing,” arXiv preprint arXiv:1310.2035, 2013

    work page Pith review arXiv 2035

  2. [2]

    Determination of quasiprobability distributions in terms of probability distributions for the rotated quadrature phase,

    K. V ogel and H. Risken, “Determination of quasiprobability distributions in terms of probability distributions for the rotated quadrature phase,” Physical Review A, vol. 40, no. 5, p. 2847, 1989

    1989

  3. [3]

    Measurement of the wigner distribution and the density matrix of a light mode using optical homodyne tomography: Application to squeezed states and the vacuum,

    D. T. Smithey, M. Beck, M. G. Raymer, and A. Faridani, “Measurement of the wigner distribution and the density matrix of a light mode using optical homodyne tomography: Application to squeezed states and the vacuum,”Physical review letters, vol. 70, no. 9, p. 1244, 1993

    1993

  4. [4]

    Sample-optimal tomography of quantum states,

    J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, “Sample-optimal tomography of quantum states,” inProceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 913–925

    2016

  5. [5]

    Average-case complexity versus approximate simulation of commuting quantum com- putations,

    M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Average-case complexity versus approximate simulation of commuting quantum com- putations,”Physical review letters, vol. 117, no. 8, p. 080501, 2016

    2016

  6. [6]

    On universal and fault-tolerant quantum computing,

    P. O. Boykin, T. Mor, M. Pulver, V . Roychowdhury, and F. Vatan, “On universal and fault-tolerant quantum computing,”arXiv preprint quant- ph/9906054, 1999

    work page arXiv 1999

  7. [7]

    Universal quantum computation with ideal clifford gates and noisy ancillas,

    S. Bravyi and A. Kitaev, “Universal quantum computation with ideal clifford gates and noisy ancillas,”Physical Review A—Atomic, Molecu- lar, and Optical Physics, vol. 71, no. 2, p. 022316, 2005

    2005

  8. [8]

    Gottesman,Stabilizer codes and quantum error correction

    D. Gottesman,Stabilizer codes and quantum error correction. Califor- nia Institute of Technology, 1997

    1997

  9. [9]

    An ideal characterization of the clifford operators,

    J. Farinholt, “An ideal characterization of the clifford operators,”Journal of Physics A: Mathematical and Theoretical, vol. 47, no. 30, p. 305303, 2014

    2014

  10. [10]

    Instantaneous quantum computation,

    D. Shepherd and M. J. Bremner, “Instantaneous quantum computation,” arXiv preprint arXiv:0809.0847, 2008

    work page arXiv 2008

  11. [11]

    Predicting many properties of a quantum system from very few measurements,

    H.-Y . Huang, R. Kueng, and J. Preskill, “Predicting many properties of a quantum system from very few measurements,”Nature Physics, vol. 16, no. 10, pp. 1050–1057, 2020

    2020

  12. [12]

    Measure- ments of quantum hamiltonians with locally-biased classical shadows,

    C. Hadfield, S. Bravyi, R. Raymond, and A. Mezzacapo, “Measure- ments of quantum hamiltonians with locally-biased classical shadows,” Communications in Mathematical Physics, vol. 391, no. 3, pp. 951–967, 2022

    2022

  13. [13]

    Decision diagrams for quantum measurements with shallow circuits,

    S. Hillmich, C. Hadfield, R. Raymond, A. Mezzacapo, and R. Wille, “Decision diagrams for quantum measurements with shallow circuits,” in2021 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2021, pp. 24–34

    2021

  14. [14]

    A survey on distribution testing: Your data is big. but is it blue?

    C. L. Canonne, “A survey on distribution testing: Your data is big. but is it blue?”Theory of Computing, vol. 9, pp. 1–100, 2020

    2020

  15. [15]

    Quantum state discrimination,

    S. M. Barnett and S. Croke, “Quantum state discrimination,”Advances in Optics and Photonics, vol. 1, no. 2, pp. 238–278, 2009

    2009

  16. [16]

    Discriminating states: The quantum Chernoff bound,

    K. M. R. Audenaert, J. Calsamiglia, R. Mu ˜noz-Tapia, E. Bagan, L. Masanes, A. Acin, and F. Verstraete, “Discriminating states: The quantum Chernoff bound,”Physical Review Letters, vol. 98, no. 16, p. 160501, 2007

    2007

  17. [17]

    Complexity-theoretic foundations of quan- tum supremacy experiments,

    S. Aaronson and L. Chen, “Complexity-theoretic foundations of quan- tum supremacy experiments,” inProceedings of the 32nd Computational Complexity Conference (CCC), 2017, pp. 22:1–22:67

    2017

  18. [18]

    Barak, C.-N

    B. Barak, C.-N. Chou, and X. Gao, “Spoofing linear cross- entropy benchmarking in shallow quantum circuits,”arXiv preprint arXiv:2005.02421, 2021

    work page arXiv 2005

  19. [19]

    Anticoncen- tration theorems for schemes showing a quantum speedup,

    D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert, “Anticoncen- tration theorems for schemes showing a quantum speedup,”Quantum, vol. 2, p. 65, 2018

    2018

  20. [20]

    Quantum computing with Qiskit,

    A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, “Quantum computing with Qiskit,” 2024

    2024

  21. [21]

    Shannon entropy, renyi entropy, and information,

    P. Bromiley, N. Thacker, and E. Bouhova-Thacker, “Shannon entropy, renyi entropy, and information,”Statistics and Inf. Series (2004-004), vol. 9, no. 2004, pp. 2–8, 2004

    2004

  22. [22]

    Estimating renyi entropy of discrete distributions,

    J. Acharya, A. Orlitsky, A. T. Suresh, and H. Tyagi, “Estimating renyi entropy of discrete distributions,”IEEE Transactions on Information Theory, vol. 63, no. 1, pp. 38–56, 2017

    2017

  23. [23]

    The computational complexity of linear optics,

    S. Aaronson and A. Arkhipov, “The computational complexity of linear optics,” inProceedings of the forty-third annual ACM symposium on Theory of computing, 2011, pp. 333–342

    2011