Pith. sign in

REVIEW 3 major objections 4 minor 44 references

For odd-prime qudits, stabilizer states can be agnostically learned with quasi-polynomial overhead, even when the input is noisy.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 23:00 UTC pith:MK2KWVVE

load-bearing objection First qudit agnostic stabilizer learning algorithm with a plausible but under-proven bootstrap step; the proof has a few unaddressed gaps but the core looks right. the 3 major comments →

arxiv 2607.15559 v1 pith:MK2KWVVE submitted 2026-07-17 quant-ph

Agnostic learning of qudit stabilizer states

Wentao Qi , Boyan Xu , Shiguang Feng , Lvzhou Li This is my paper
classification quant-ph MSC 81P6868Q12
keywords agnostic learningstabilizer statesquditBell difference samplingstabilizer fidelitymagic estimationanti-concentrationClifford group
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper establishes that agnostic learning of stabilizer states—finding the closest stabilizer state to an unknown pure state without assuming the state is a stabilizer state—does not require the local dimension to be 2. It gives the first efficient quantum algorithm for odd-prime qudit systems, matching the quasi-polynomial complexity previously achieved for qubits. The algorithm works by repeatedly sampling from a skewed Bell difference distribution, using a new anti-concentration bound to guarantee that each round finds a stabilizer element outside the currently known subgroup, and then measuring and post-selecting to amplify the fidelity toward the target. A separate threshold argument covers the high-fidelity regime with polynomial complexity. If the algorithm's hidden assumption about the stability of the maximum-fidelity state across post-selection holds, the result also yields efficient estimation of stabilizer fidelity, a standard measure of quantum magic.

Core claim

The central discovery is a quantitative anti-concentration theorem for the marginal distribution obtained from skewed Bell difference sampling on qudit states: for any proper subspace T of the stabilizer group of the state's nearest stabilizer state, the distribution places at least (d-1)F^6/(4d^3) mass on S\T. This single bound makes the stabilizer bootstrapping approach work over F_d^{2n} despite two obstacles that break the qubit proof: the skew map J is no longer the identity, and Weyl operators are non-Hermitian. The authors prove the bound by reducing to a single-qudit statement and showing that the d(d+1) single-qudit stabilizer states form a complex projective 2-design, yielding a un

What carries the argument

Skewed Bell difference sampling (a four-copy protocol that entangles two pairs of qudits and takes differences of Bell measurement outcomes) produces a marginal distribution B_ψ that, unlike naive Bell sampling, retains the uniform-over-stabilizer-group property for stabilizer states. The load-bearing object is Theorem 7's anti-concentration bound, which guarantees that B_ψ puts appreciable mass on stabilizer elements outside any proper subspace; combined with SWAP-test correlation estimation and Clifford-circuit synthesis, it drives the bootstrapping loop that amplifies fidelity by a constant factor each round.

Load-bearing premise

The load-bearing premise is that the identity of the maximum-fidelity stabilizer state does not change after the bootstrap's post-selection steps; the paper proves its key bound only for states with a fixed maximizer, and the preservation of the maximizer is not established.

What would settle it

Construct a concrete pure state |ψ⟩ and a post-selection projector M_x that stabilizes one of its maximum-fidelity stabilizer states |φ⟩ such that, after post-selection, the state |ψ'⟩ has a different stabilizer state |φ'⟩ with strictly higher fidelity than |φ⟩; then the bound in Theorem 7 cannot be invoked for |ψ'⟩ with respect to |φ⟩, and the fidelity-amplification argument of Lemma 13 would break. This could be done numerically for small n and d by optimizing the fidelity ratios.

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

If this is right

  • If correct, the algorithm gives the first efficient agnostic learner for qudit stabilizer states in odd prime dimension, closing the gap with the qubit case.
  • It yields an efficient estimator of stabilizer fidelity (magic) for n-qudit pure states, with quasi-polynomial complexity when the target error is inverse-polynomial.
  • In the high-fidelity regime (fidelity ≥ cos²(π/8)+γ), a streamlined single-round algorithm identifies the stabilizer state with polynomial sample and time complexity.
  • The sample and time complexity scale as poly(n) when τ is constant, and become quasi-polynomial when τ = 1/poly(n), matching the known qubit behaviour.

Where Pith is reading between the lines

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

  • The anti-concentration theorem is stated and proved for a state whose maximum-fidelity stabilizer state is fixed; the bootstrap applies it to post-selected states without proving that the same |φ⟩ remains optimal after each post-selection. If this hidden lemma fails, the amplification argument would need repair, though the post-selection projectors are designed to respect |φ⟩.
  • The 2/(d+1) single-qudit stabilizer fidelity bound, derived from the 2-design property, suggests that the dependence of the sample complexity on d may be close to optimal among methods based on Bell-difference-type sampling.
  • A natural testable extension would be to check whether the same anti-concentration bound holds for the full joint distribution of the two output strings rather than the marginal; the paper notes the two strings are independent for stabilizer states, so exploiting their correlation could reduce the constant-factor overhead.
  • The framework's reliance on the marginal distribution rather than the joint one leaves room to improve sample complexity if a joint anti-concentration bound can be established.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper presents the first claimed efficient quantum algorithm for agnostic learning of n-qudit stabilizer states for odd prime dimension d. The main result, Theorem 1, is an algorithm that, given copies of an unknown pure state |ψ⟩ with stabilizer fidelity at least τ, outputs a stabilizer state whose fidelity with |ψ⟩ is within ε of optimal, using (d/τ)^{O(d^2 log(1/τ))}·poly(n,1/ε) samples and time. The algorithm generalizes the qubit stabilizer-bootstrapping framework of Chen et al. [20] by using the skewed Bell difference sampling protocol of Allcock et al. [23], proving a new anti-concentration bound for its marginal distribution, and replacing Hermitian-Pauli correlation estimation with SWAP-test estimation. A streamlined polynomial-time algorithm is also claimed for the high-fidelity regime τ > cos^2(π/8). Applications to stabilizer-fidelity (magic) estimation are given.

Significance. If the proof is correct, this is a substantial result: it resolves a natural open problem left by the qubit work of Chen et al. and extends agnostic stabilizer learning to all odd prime local dimensions. The technical core — the anti-concentration bound for the marginal of skewed Bell difference sampling, proved via a new single-qudit stabilizer-fidelity lower bound — is novel and appears to be a genuine contribution. The paper is also explicit about the algorithmic primitives and complexity, and the claimed single-copy and four-copy measurement structure is potentially useful for implementations. However, the current proof has two load-bearing gaps: an overclaim in Theorem 12 about outputting arbitrary high-fidelity stabilizer states, and an unproved invariant about the fidelity maximizer under post-selection. These issues affect the correctness of the bootstrap induction and of the list-decoding step used for the final theorem.

major comments (3)
  1. [Section IV, Theorem 12 and Corollary 1] Theorem 12 states that for any stabilizer state |ϕ⟩ with F(|ψ⟩,|ϕ⟩)≥τ, the algorithm outputs |ϕ⟩ with probability (τ/d)^{O(d^2 log(1/τ))}. This is false as written. Take d=3, n=1, |ψ⟩=|+⟩, τ=1/3, and |ϕ⟩=|0⟩. Then F(|ψ⟩,|ϕ⟩)=1/3 but |ϕ⟩ is not a maximizer, since F_S(|ψ⟩)=1. For a stabilizer input, B_ψ is supported on Weyl(|ψ⟩), so B_{|+⟩} is supported on Weyl(|+⟩); Algorithm 2 will never sample an element of Weyl(|0⟩)\T, and the first high-correlation round already spans Weyl(|+⟩). The algorithm therefore outputs |+⟩, not |0⟩, contradicting the claimed lower bound. The proof of Theorem 12 relies on Theorem 11, which explicitly assumes |ϕ⟩ is a maximizer. Corollary 1 and the proof of Theorem 13 inherit this problem. The theorem should be restricted to a stabilizer state that maximizes F_S(|ψ⟩), and Corollary 1 should be weakened accordingly; a list containing the maximizer suffices for th
  2. [Section IV, Lemma 15 and Theorem 11] Theorem 7 is proved under the hypothesis that |ϕ⟩ maximizes F_S for the state being sampled; this maximality is used essentially in Lemma 8, for example in Eq. (53). In the bootstrap loop, Theorem 11 is applied to each post-selected state |ψ_t⟩ with the original maximizer |ϕ⟩, but the manuscript never proves that |ϕ⟩ remains a maximizer after the filters M_{s_i,y_i}. This is not a vacuous condition: for |ψ⟩=|+⟩ and |ϕ⟩=|0⟩ in d=3, n=1, the anti-concentration bound B_{|+⟩}(S\T)≥(d−1)F^6/(4d^3) fails because B_{|+⟩} is supported on Weyl(|+⟩), not on S=Weyl(|0⟩). The induction in Lemma 15 therefore needs an additional lemma: if M|ϕ⟩=|ϕ⟩ and |ϕ⟩ maximizes F_S(|ψ⟩), then |ϕ⟩ maximizes F_S(M|ψ⟩/||M|ψ⟩||). Without this, the application of Theorem 11 to |ψ_t⟩ is unjustified, and the bootstrap could in principle converge to a different stabilizer state. Please prove this invariant or modify the a
  3. [Table I vs. Theorem 14 / Section V] The high-fidelity regime has an internal complexity inconsistency. Table I reports sample complexity O(d^4/γ^2 · n log n), while Theorem 14 states and proves O((d^2/γ^2)(n+log(1/δ)) log(n/δ)). The proof's first phase takes m=8d^3/((d−1)cos^12(π/8))·(n+log(3/δ)) = O(d^2(n+log(1/δ))) samples, and the estimation step adds a 1/γ^2 factor. So the d^4 in Table I appears to be a typo, but as the table is part of the paper's advertised results it should be corrected in either the table or the theorem.
minor comments (4)
  1. [Abstract and Section II.D] The abstract says the algorithm uses 'single-copy and four-copy measurements', but skewed Bell difference sampling as defined in Definition 7 uses eight copies per sample (|ψ⟩^⊗8), and the proof of Theorem 12 counts 8 copies for each B_ψ sample (e.g., 'Line 6 requires 8 copies of |ψ_t⟩'). Please clarify whether the four-copy simplification means something different, or update the wording.
  2. [Section III.A, Lemma 5] Lemma 5 is stated without proof. A direct computation from the explicit eigenvectors in Lemma 4 would be a one-line addition and would make the mutually-unbiased-bases claim self-contained.
  3. [Section III.A, Eq. (37)] In Eq. (37) the symbol 'w' appears in the exponent; it should be '\omega' to match the surrounding notation.
  4. [Section V, Proposition 5 proof] In Eq. (93), the notation '∥ ... ∥ 2' is ambiguous: it appears to denote the Euclidean norm, not a squared norm, but the following equality suggests a norm-square is used. Please clean up the notation so the triangle-inequality step is unambiguous.

Circularity Check

0 steps flagged

No circularity found: the central anti-concentration theorem is proved from a new single-qudit bound, and all load-bearing citations are external background results, not self-citations or restatements of the target claim.

full rationale

The derivation chain is self-contained with respect to the paper's own claims. Theorem 7 is not assumed; it is proved in Section III via Lemma 8, the single-qudit stabilizer-fidelity bound (Theorem 8), and Clifford invariance (Lemmas 9–10). The single-qudit bound is proved from the MUB/2-design identities (Lemmas 5–7), which are derived inside the paper, with Ref. [26] cited only as a related result rather than as load-bearing evidence. The bootstrap algorithm (Section IV) applies Theorem 7 through Theorem 11 and Lemma 15; although Lemma 15 does not explicitly restate the invariant that the original fidelity-maximizer |φ⟩ remains a maximizer after post-selection, this is a short unstated lemma (for any stabilizer |φ⟩, |⟨ψ'|φ⟩|² ≤ |⟨ψ'|φ*⟩|² follows from M†|φ⟩ being proportional to |φ⟩ with a factor of modulus at most 1), not a circular reduction. No parameter is fitted and renamed a prediction, and no prior result by the present authors is cited to carry a load-bearing step. Known qubit results [19], [20] and qudit sampling results [23], [24] are used as external tools, not as restatements of the target theorem. The acknowledged limitations (odd prime d, pure states, quasi-polynomial τ-dependence) are open problems, not hidden circularity. Score 0.

Axiom & Free-Parameter Ledger

1 free parameters · 6 axioms · 0 invented entities

No invented physical entities are introduced. The only hand-chosen constant is the high-correlation threshold; the remaining inputs are the standard model assumptions (odd prime qudit dimension, pure states, copy access) and prior theorems from the cited literature. The central new ingredient is the anti-concentration theorem, which is derived rather than assumed.

free parameters (1)
  • High-correlation threshold 1 - 1/(12d^2) = 1 - 1/(12d^2), with related estimation accuracy 1/(12d^2)
    Chosen by hand in Definition 8 to make Lemma 11's commutativity conclusion work; it also fixes the correlation-estimation accuracy and the bootstrap amplification factor Δ_d. It is not fitted to data, but it is an ad hoc proof constant.
axioms (6)
  • domain assumption d is an odd prime and the unknown state is an n-qudit pure state
    The skewed Bell difference sampling simplification, finite-field structure, and all stated theorems explicitly require this; the conclusion section lists composite and mixed-state generalizations as open.
  • domain assumption Propositions 1 and 2 from [23] (characteristic-distribution Fourier relation and stabilizer mass lower bound)
    Used in Lemma 1 and throughout the anti-concentration argument; accepted without proof as prior background.
  • domain assumption Lemma 11 from [24]: two Weyl operators with squared correlation at least 1 - 1/(4d^2) must commute
    Basis for the high-correlation family filter in Algorithm 1 and for the abort condition in Corollary 5.
  • domain assumption Lemma 12 from [23]: m independent samples from a distribution span a subspace carrying at least 1-ε mass
    Used in the proof of Theorem 10 to derive the ε-high-correlation basis guarantee from B_ψ sampling.
  • domain assumption Lemma 14 from [20]: post-selection can prepare N copies of an amplified state with overhead (2/τ)(N + log(1/δ))
    Used at every bootstrap round in Algorithm 2 to prepare copies of |ψ_t⟩ from copies of |ψ⟩; imported directly from the qubit stabilizer bootstrapping paper.
  • standard math Single-qudit stabilizer states split into d+1 mutually unbiased bases and form a complex projective 2-design
    Lemmas 4-7 in the paper give an elementary proof, but the classification of single-qudit stabilizer states and the 2-design property are standard background used to derive the universal lower bound F_S(|ψ1⟩) ≥ 2/(d+1).

pith-pipeline@v1.3.0-alltime-deepseek · 35391 in / 36611 out tokens · 365938 ms · 2026-08-01T23:00:33.298929+00:00 · methodology

0 comments
read the original abstract

Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown $n$-qudit pure state $|\psi\rangle$ that has fidelity $\tau$ with some stabilizer state, our algorithm outputs a stabilizer state $|\phi\rangle$ such that $\left| \braket{\phi|\psi} \right|^2 \geq \tau - \varepsilon$ with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as $(d/\tau)^{O(d^2 \log(1/\tau))} \cdot \mathrm{poly}(n, 1/\varepsilon)$, where the dimension $d$ is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime $\tau > \cos^2(\pi/8)$, establishing a qudit analogue of the threshold-based approach in prior qubit work.

Figures

Figures reproduced from arXiv: 2607.15559 by Boyan Xu, Lvzhou Li, Shiguang Feng, Wentao Qi.

Figure 1
Figure 1. Figure 1: Quantum circuit for SWAP test of two n-qudit states. Based on the explicit expression for p(0) in Lemma 17, we can invert the linear relationship between the measurement outcome probability and the fidelity to estimate |⟨ψ|ϕ⟩|2 from repeated SWAP tests. The following theorem formalizes this procedure and analyzes its sample and time complexity. Theorem 15. For two n-qudit pure states |ψ⟩ and |ϕ⟩, and for ε… view at source ↗

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

44 extracted references · 4 linked inside Pith

  1. [1]

    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, ser. STOC ’16, New York, NY , USA, 2016, p. 913–925

    2016

  2. [2]

    Efficient quantum tomography,

    R. O’Donnell and J. Wright, “Efficient quantum tomography,” inProceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, ser. STOC ’16, New York, NY , USA, 2016, p. 899–912. JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015 25

    2016

  3. [3]

    Optimal algorithms for learning quantum phase states,

    S. Arunachalam, S. Bravyi, A. Dutt, and T. J. Yoder, “Optimal algorithms for learning quantum phase states,”Leibniz Int. Proc. Inf., vol. 266, pp. 3:1–3:24, 2023

    2023

  4. [4]

    Efficient direct tomography for matrix product states,

    O. Landon-Cardinal, Y .-K. Liu, and D. Poulin, “Efficient direct tomography for matrix product states,”arXiv, vol. 1002.4632, 2010

    Pith/arXiv arXiv 2010

  5. [5]

    Efficient quantum state tomography,

    C. Marcus, 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. Commun., vol. 1, p. 149, 2010

    2010

  6. [6]

    Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates,

    S. Grewal, V . Iyer, W. Kretschmer, and D. Liang, “Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates,”Quantum, vol. 9, p. 1907, 2025

    1907

  7. [7]

    Efficient learning oft-doped stabilizer states with single-copy measurements,

    N.-H. Chia, C.-Y . Lai, and H.-H. Lin, “Efficient learning oft-doped stabilizer states with single-copy measurements,”Quantum, vol. 8, p. 1250, 2024

    2024

  8. [8]

    Learning t-doped stabilizer states,

    L. Leone, S. F. E. Oliviero, and A. Hamma, “Learning t-doped stabilizer states,”Quantum, vol. 8, p. 1361, 2024

    2024

  9. [9]

    Scheme for reducing decoherence in quantum computer memory,

    P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,”Phys. Rev. A, vol. 52, pp. R2493–R2496, 1995

    1995

  10. [10]

    Good quantum error-correcting codes exist,

    A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,”Phys. Rev. A, vol. 54, pp. 1098–1105, 1996

    1996

  11. [11]

    Class of quantum error-correcting codes saturating the quantum hamming bound,

    D. Gottesman, “Class of quantum error-correcting codes saturating the quantum hamming bound,”Phys. Rev. A, vol. 54, pp. 1862–1868, 1996

    1996

  12. [12]

    Improved simulation of stabilizer circuits,

    S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits,”Phys. Rev. A, vol. 70, p. 052328, 2004

    2004

  13. [13]

    Trading classical and quantum computational resources,

    S. Bravyi, G. Smith, and J. A. Smolin, “Trading classical and quantum computational resources,”Phys. Rev. X, vol. 6, p. 021043, 2016

    2016

  14. [14]

    Simulation of quantum circuits by low-rank stabilizer decompositions,

    S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, “Simulation of quantum circuits by low-rank stabilizer decompositions,” Quantum, vol. 3, p. 181, 2019

    2019

  15. [15]

    Randomized benchmarking of quantum gates,

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

    2008

  16. [16]

    Scalable and robust randomized benchmarking of quantum processes,

    E. Magesan, J. M. Gambetta, and J. Emerson, “Scalable and robust randomized benchmarking of quantum processes,”Phys. Rev. Lett., vol. 106, p. 180504, 2011

    2011

  17. [17]

    Multiqubit randomized benchmarking using few samples,

    J. Helsen, J. J. Wallman, S. T. Flammia, and S. Wehner, “Multiqubit randomized benchmarking using few samples,”Phys. Rev. A, vol. 100, p. 032304, 2019

    2019

  18. [18]

    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,”Nat. Phys., vol. 16, p. 1050–1057, 2020

    2020

  19. [19]

    Improved stabilizer estimation via bell difference sampling,

    S. Grewal, V . Iyer, W. Kretschmer, and D. Liang, “Improved stabilizer estimation via bell difference sampling,” inProceedings of the 56th Annual ACM Symposium on Theory of Computing, ser. STOC 2024, New York, NY , USA, 2024, p. 1352–1363

    2024

  20. [20]

    Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation,

    S. Chen, W. Gong, Q. Ye, and Z. Zhang, “Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation,” inProceedings of the 57th Annual ACM Symposium on Theory of Computing, ser. STOC ’25, New York, NY , USA, 2025, p. 429–438

    2025

  21. [21]

    Identifying stabilizer states,

    S. Aaronson and D. Gottesman, “Identifying stabilizer states,” 2008, https://pirsa.org/08080052

    arXiv 2008

  22. [22]

    Learning stabilizer states by bell sampling,

    A. Montanaro, “Learning stabilizer states by bell sampling,”arXiv, vol. 1707.04012, 2017

    Pith/arXiv arXiv 2017

  23. [23]

    Reconquering bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more,

    J. Allcock, J. F. Doriguello, G. Ivanyos, and M. Santha, “Reconquering bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more,” 2025

    2025

  24. [24]

    Schur–weyl duality for the clifford group with applications: Property testing, a robust hudson theorem, and de finetti representations,

    D. Gross, S. Nezami, and M. Walter, “Schur–weyl duality for the clifford group with applications: Property testing, a robust hudson theorem, and de finetti representations,”Commun. Math. Phys., vol. 385, no. 3, p. 1325–1393, 2021

    2021

  25. [25]

    Beyond bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits,

    J. Allcock, J. F. Doriguello, G. Ivanyos, and M. Santha, “Beyond bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits,”arXiv, vol. 2405.06357, 2024

    Pith/arXiv arXiv 2024

  26. [26]

    Mutually unbiased bases are complex projective 2-designs,

    A. Klappenecker and M. Rotteler, “Mutually unbiased bases are complex projective 2-designs,” inProceedings. International Symposium on Information Theory, 2005. ISIT 2005., 2005, pp. 1740–1744

    2005

  27. [27]

    Information-theoretic bounds on quantum advantage in machine learning,

    H.-Y . Huang, R. Kueng, and J. Preskill, “Information-theoretic bounds on quantum advantage in machine learning,”Phys. Rev. Lett., vol. 126, p. 190505, 2021

    2021

  28. [28]

    Quantum fingerprinting,

    H. Buhrman, R. Cleve, J. Watrous, and R. De Wolf, “Quantum fingerprinting,”Phys. Rev. Lett., vol. 87, no. 16, p. 167902, 2001

    2001

  29. [29]

    Learning quantum circuits of some t gates,

    C.-Y . Lai and H.-C. Cheng, “Learning quantum circuits of some t gates,”IEEE Trans. Info. Theor., vol. 68, no. 6, pp. 3951–3964, 2022

    2022

  30. [30]

    Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom,

    S. Grewal, V . Iyer, W. Kretschmer, and D. Liang, “Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom,” in14th Innovations in Theoretical Computer Science Conference (ITCS 2023), ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 251, Dagstuhl, Germany, 2023, pp. 64:1– 64:20

    2023

  31. [31]

    Improved bounds for testing low stabilizer complexity states,

    S. Mehraban and M. Tahmasbi, “Improved bounds for testing low stabilizer complexity states,” inProceedings of the 57th Annual ACM Symposium on Theory of Computing, ser. STOC ’25. New York, NY , USA: Association for Computing Machinery, 2025, p. 1222–1233

    2025

  32. [32]

    The abelian state hidden subgroup problem: Learning stabilizer groups and beyond,

    M. Hinsche, J. Eisert, and J. Carrasco, “The abelian state hidden subgroup problem: Learning stabilizer groups and beyond,”arXiv, vol. 2505.15770, 2025

    Pith/arXiv arXiv 2025

  33. [33]

    A theory of the learnable,

    L. G. Valiant, “A theory of the learnable,”Communications of the ACM, vol. 27, no. 11, pp. 1134–1142, 1984

    1984

  34. [34]

    Toward efficient agnostic learning,

    M. J. Kearns, R. E. Schapire, and L. M. Sellie, “Toward efficient agnostic learning,” inProceedings of the fifth annual workshop on Computational learning theory, 1992, pp. 341–352

    1992

  35. [35]

    Agnostic tomography of stabilizer product states,

    S. Grewal, V . Iyer, W. Kretschmer, and D. Liang, “Agnostic tomography of stabilizer product states,”arXiv, vol. 2404.03813, 2024

    arXiv 2024

  36. [36]

    Learning the closest product state,

    A. Bakshi, J. Bostanci, W. Kretschmer, Z. Landau, J. Li, A. Liu, R. O’Donnell, and E. Tang, “Learning the closest product state,” inProceedings of the 57th Annual ACM Symposium on Theory of Computing, ser. STOC ’25, New York, NY , USA, 2025, p. 1212–1221

    2025

  37. [37]

    Efficiently learning depth-3 circuits via quantum agnostic boosting,

    S. Arunachalam, A. Dutt, A. Gheorghiu, and M. de Oliveira, “Efficiently learning depth-3 circuits via quantum agnostic boosting,” in26th Annual Quantum Information Processing Conference, ser. QIP ’26, 2026

    2026

  38. [38]

    Multivalued logic gates for quantum computation,

    A. Muthukrishnan and C. R. Stroud, “Multivalued logic gates for quantum computation,”Phys. Rev. A, vol. 62, p. 052309, 2000

    2000

  39. [39]

    Criteria for exact qudit universality,

    G. K. Brennen, D. P. O’Leary, and S. S. Bullock, “Criteria for exact qudit universality,”Phys. Rev. A, vol. 71, p. 052318, 2005

    2005

  40. [40]

    Efficient circuits for exact-universal computationwith qudits,

    G. K. Brennen, S. S. Bullock, and D. P. O’Leary, “Efficient circuits for exact-universal computationwith qudits,”Quantum Info. Comput., vol. 6, no. 4, p. 436–454, 2006

    2006

  41. [41]

    Qudit shadow estimation based on the clifford group and the power of a single magic gate,

    C. Mao, C. Yi, and H. Zhu, “Qudit shadow estimation based on the clifford group and the power of a single magic gate,”Phys. Rev. Lett., vol. 134, p. 160801, 2025

    2025

  42. [42]

    Gottesman

    D. Gottesman. (2024) Surviving as a quantum computer in a classical world. [Online]. Available: https://www.cs.umd.edu/class/spring2024/cmsc858G/

    2024

  43. [43]

    A linearized stabilizer formalism for systems of finite dimension,

    N. De Beaudrap, “A linearized stabilizer formalism for systems of finite dimension,”Quantum Info. Comput., vol. 13, no. 1–2, p. 73–115, 2013

    2013

  44. [44]

    Sdim: A qudit stabilizer simulator,

    A. Kabir, S. Nguyen, T. Kiran, A. Kumar, and Y . Huang, “Sdim: A qudit stabilizer simulator,” inFifth International Workshop on Programming Languages for Quantum Computing, ser. PLanQC 2025, 2025. Wentao Qireceived the M.S. degree in mathematics from Zhejiang University, China, in 2022. He is currently pursuing the Ph.D. degree with the Institute of Quant...

    2025