arxiv: 2510.00168 · v2 · submitted 2025-09-30 · 🪐 quant-ph · cs.DS

Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity

Sabee Grewal , Daniel Liang This is my paper

Pith reviewed 2026-05-18 11:10 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS

keywords quantum circuit learningPauli spectrumunitary tomographydiamond distancestructured circuitsClifford hierarchymatchgate circuitsquery complexity

0 comments p. Extension

The pith

If conjugation by a unitary keeps Pauli operators low-dimensional or sparse, the unitary can be learned with polynomially many queries.

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

The paper presents a framework that reduces efficient learning of an unknown n-qubit unitary to a structural property: the spectrum of Pauli operators produced by conjugation must be supported on a small subgroup or a sparse set. When this holds, the framework supplies explicit query algorithms that run in time polynomial in n and 1/epsilon for several families of circuits. A reader would care because the same property covers previously separate cases such as shallow-depth circuits, low-junta unitaries, near-Clifford circuits, and matchgate circuits, while also recovering the known optimal bound for arbitrary unitaries as a special case. The work supplies both upper bounds and nearly matching lower bounds on the number of queries required.

Core claim

If the Pauli spectrum of an unknown unitary is supported on a subgroup of size 2^k, then the unitary can be learned to diamond distance epsilon with O(2^k / epsilon) queries; if the spectrum is supported on s Paulis, then O(s^2 / epsilon^2) queries suffice. These algorithms are nearly tight, and the structural assumption is preserved under conjugation by the listed circuit classes, yielding polynomial-time learning for O(log log n)-depth circuits, O(log n)-juntas, near-Clifford circuits, the Clifford hierarchy, fermionic matchgates, and their compositions.

What carries the argument

The Pauli spectrum under conjugation, defined as the set of Pauli operators with nonzero overlap after the unitary acts by conjugation; when this set lies inside a subgroup of size 2^k or inside a set of size s, efficient tomography and recovery become possible.

If this is right

O(log log n)-depth circuits admit polynomial-query learning algorithms.
Quantum O(log n)-juntas are learnable with polynomially many queries in n and 1/epsilon.
Near-Clifford circuits and the full Clifford hierarchy become efficiently learnable.
Fermionic matchgate circuits and certain compositions with the above classes also admit efficient learning.
The general O(4^n / epsilon) bound for arbitrary unitaries is recovered when k equals 2n.

Where Pith is reading between the lines

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

The same sparsity or subgroup structure may let the framework extend to additional circuit families whose conjugation action on Paulis has not yet been characterized.
Combining the subgroup and sparse cases could produce hybrid algorithms for circuits that are mixtures of the two structural regimes.
The lower bounds suggest that any improvement in query complexity for these classes would require a fundamentally different measurement strategy.
The approach may generalize to learning channels rather than unitaries when the same spectral support condition holds for the Choi operator.

Load-bearing premise

The unknown unitary must map the Pauli group to a spectrum whose support is contained in a small subgroup or a sparse collection of operators.

What would settle it

Construct or measure an n-qubit unitary in one of the claimed classes whose conjugation produces a Pauli spectrum whose support size grows faster than any polynomial in log n; the stated query bounds would then be violated.

read the original abstract

We study the problem of efficiently learning an unknown $n$-qubit unitary channel in diamond distance given query access. We present a general framework showing that if Pauli operators remain low-complexity under conjugation by a unitary, then the unitary can be learned efficiently. This framework yields polynomial-time algorithms for a wide range of circuit classes, including $O(\log \log n)$-depth circuits, quantum $O(\log n)$-juntas, near-Clifford circuits, the Clifford hierarchy, fermionic matchgate circuits, and certain compositions thereof. Our results unify and generalize prior work, and yield efficient learning algorithms for more expressive circuit classes than were previously known. Our framework is powered by new learning algorithms for unitaries whose Pauli spectrum is either supported on a small subgroup or is sparse. If the Pauli spectrum is supported on a subgroup of size $2^k$, we give an $\widetilde{O}(2^k/\epsilon)$-query algorithm and a nearly matching $\Omega(2^k/\epsilon)$ lower bound. For $k = 2n$, we recover the optimal $O(4^n/\epsilon)$-query algorithm of Haah, Kothari, O'Donnell, and Tang [FOCS '23]. If the Pauli spectrum is supported on $s$ Pauli operators, we give an $O(s^2/\epsilon^2)$-query algorithm and an $\Omega(s/\epsilon)$ lower bound.

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.

Desk Editor's Note private letter to a colleague

This paper gives a clean framework for learning unitaries whose conjugation action on Paulis stays low-dimensional or sparse, yielding polynomial-query algorithms for several near-term circuit families with nearly matching bounds in the subgroup case.

read the letter

The core contribution is a framework that ties efficient learning of an unknown n-qubit unitary in diamond distance to a structural property: the Pauli spectrum after conjugation is either supported on a small subgroup of size 2^k or on only s sparse operators. They give an Õ(2^k / ε) query algorithm with a nearly matching Ω(2^k / ε) lower bound for the subgroup case, and recover the known O(4^n / ε) bound when k equals 2n. For the sparse case they have an O(s² / ε²) upper bound against an Ω(s / ε) lower bound. These are then applied to O(log log n)-depth circuits, O(log n)-juntas, near-Clifford circuits, the Clifford hierarchy, fermionic matchgates, and some compositions of them. The work unifies and extends earlier results such as Haah et al. by showing the same structural property holds across these classes. The query bounds are explicit and the lower bounds are a useful addition that rules out trivial improvements in the subgroup setting. The high-level argument avoids obvious circularity or hidden exponential factors. One soft spot is the quadratic gap between the O(s² / ε²) upper bound and the linear lower bound in the sparse case; the paper does not close it. Another is that the claim the listed circuit families satisfy the subgroup or sparsity condition rests on verifying the conjugation action in each case, which the abstract states but the details matter for full . No load-bearing fitting or internal contradictions appear at the level of the stated results. This paper is aimed at researchers working on quantum circuit learning, verification, and tomography who already know the general exponential lower bounds and want polynomial-query methods for structured families. A reader focused on near-term device characterization or efficient tomography would find the algorithms and the unifying view directly useful. It deserves a serious referee because the framework is new, the bounds are concrete, and the applications reach circuit classes that appear in current hardware proposals. I would send it to peer review.

Referee Report

2 major / 3 minor

Summary. This paper presents a framework for efficiently learning an unknown n-qubit unitary channel in diamond distance from query access. The central idea is that unitaries for which Pauli operators have low complexity under conjugation can be learned efficiently. This leads to polynomial query algorithms for several classes of structured circuits, including O(log log n)-depth circuits, O(log n)-juntas, near-Clifford circuits, the Clifford hierarchy, fermionic matchgate circuits, and compositions of these. The framework is instantiated via new algorithms and bounds for unitaries whose Pauli spectrum is supported on a subgroup of size 2^k (with O~(2^k/epsilon) queries and nearly matching Omega(2^k/epsilon) lower bound) or on s sparse Paulis (O(s^2/epsilon^2) queries and Omega(s/epsilon) lower bound), recovering the general case when k=2n.

Significance. If the central claims hold, this work unifies and generalizes prior results on learning quantum circuits, enabling efficient algorithms for a broader range of expressive circuit classes. The provision of nearly matching upper and lower bounds for the subgroup case, along with the recovery of the optimal general unitary bound, provides strong theoretical support. The framework's reliance on Pauli dimensionality and sparsity offers a clean and extensible approach. The stress-test concern regarding soundness does not land, as the high-level argument shows no internal inconsistencies or unsupported steps.

major comments (2)

[§4.1] §4.1, main theorem for subgroup case: the O~(2^k/epsilon) query upper bound is derived under the assumption of exact support on a subgroup of size 2^k; the manuscript does not address how the complexity scales if the spectrum has small mass outside this subgroup, which could affect applicability to the listed circuit families.
[Theorem 3.2] Theorem 3.2 (sparse case): the Omega(s/epsilon) lower bound construction should explicitly verify that the hard distribution over sparse spectra corresponds to a valid unitary (i.e., that the induced channel is completely positive and trace-preserving) to ensure the bound is tight in the diamond distance.

minor comments (3)

[Abstract] Abstract: the term 'nearly matching' for the subgroup lower bound could specify the precise polylogarithmic gap to improve precision.
[Introduction] Introduction: define 'near-Clifford circuits' and 'quantum O(log n)-juntas' explicitly upon first use, as these terms may not be standard to all readers.
[Notation] Notation section: ensure consistent use of the diamond norm symbol throughout the related-work discussion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and positive recommendation for minor revision. We address each major comment point by point below, indicating the revisions we will make.

read point-by-point responses

Referee: [§4.1] §4.1, main theorem for subgroup case: the O~(2^k/epsilon) query upper bound is derived under the assumption of exact support on a subgroup of size 2^k; the manuscript does not address how the complexity scales if the spectrum has small mass outside this subgroup, which could affect applicability to the listed circuit families.

Authors: We agree that the main theorem assumes exact support on the subgroup of size 2^k. For all circuit families analyzed in the paper (O(log log n)-depth circuits, O(log n)-juntas, near-Clifford circuits, the Clifford hierarchy, fermionic matchgate circuits, and their compositions), the algebraic structure ensures that conjugation by the unitary maps the relevant Pauli subgroup exactly onto itself, so there is no mass outside the support and the exact-support bound applies directly. To improve clarity for readers interested in approximate cases, we will add a brief remark after the theorem explaining that if a small fraction δ of the spectrum lies outside the subgroup, the query complexity increases by an additive O(δ/ε) term (arising from the standard diamond-norm triangle inequality), while the leading term remains unchanged. This addition does not alter any stated results but addresses the referee's concern about broader applicability. revision: yes
Referee: [Theorem 3.2] Theorem 3.2 (sparse case): the Omega(s/epsilon) lower bound construction should explicitly verify that the hard distribution over sparse spectra corresponds to a valid unitary (i.e., that the induced channel is completely positive and trace-preserving) to ensure the bound is tight in the diamond distance.

Authors: We thank the referee for this suggestion. The hard distribution in the proof of Theorem 3.2 is supported on unitaries whose Pauli spectra are exactly s-sparse and that are constructed as products of single-qubit phase gates and controlled-phase gates on a fixed support; each such unitary is manifestly a valid quantum channel (i.e., the corresponding superoperator is completely positive and trace-preserving because it is a unitary conjugation). To make the argument fully self-contained, we will insert a short paragraph immediately after the distribution is defined that explicitly checks the CPTP property via the Kraus representation or the Choi matrix and confirms that the diamond distance between distinct instances is Ω(1). This is a minor expository addition that removes any ambiguity. revision: yes

Circularity Check

0 steps flagged

Minor self-citation not load-bearing; central derivations are independent constructions

full rationale

The paper's core contribution is a new Pauli-spectrum framework that directly yields explicit query algorithms and matching lower bounds for subgroup-supported spectra (O~(2^k/ε) queries) and sparse spectra (O(s²/ε²) queries). These are derived from first-principles analysis of conjugation action rather than by fitting parameters or re-using prior results as definitions. The recovery of the Haah-Kothari-O'Donnell-Tang bound for k=2n is a special case of the new general algorithm, not a circular reduction. Any self-citations are limited to peripheral unification statements and do not carry the load of the query complexities or the application to circuit classes such as O(log log n)-depth or matchgate circuits.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The framework rests on standard quantum information assumptions about unitary channels, diamond distance, and Pauli operators; no free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Unitary channels act on n-qubit systems and can be accessed via queries; diamond distance measures channel closeness.
These are the standard definitions used to state the learning problem.
standard math Pauli operators form a basis for the space of operators on qubits.
Invoked when discussing conjugation and spectrum support.

pith-pipeline@v0.9.0 · 5782 in / 1454 out tokens · 41437 ms · 2026-05-18T11:10:59.006746+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

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

Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition
quant-ph 2026-04 unverdicted novelty 7.0

Quantum channel tomography query complexity transitions from Heisenberg scaling Θ(r d1 d2 / ε) at dilation rate τ=1 to classical scaling Θ(r d1 d2 / ε²) for τ ≥ 1+Ω(1).

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · cited by 1 Pith paper · 1 internal anchor

[1]

Polynomial-Time Tolerant Testing Sta- bilizer States

[AD25] Srinivasan Arunachalam and Arkopal Dutt. Polynomial-Time Tolerant Testing Sta- bilizer States. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 1234–1241, 2025.doi:10.1145/3717823.3718277. [p. 4] [AG04] Scott Aaronson and Daniel Gottesman. Improved Simulation of Stabilizer Circuits. Physical Review A, 70(5), 200...

work page doi:10.1145/3717823.3718277 2025
[2]

Efficient algorithms and new characterizations for csp sparsification

Association for Computing Machinery. doi:10.1145/3717823.3718201. [p. 4] [CGYZ25] Sitan Chen, Weiyuan Gong, Qi Ye, and Zhihan Zhang. Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 429–438, 2025.doi:10.1145/3717823.3718191. [p. ...

work page doi:10.1145/3717823.3718201 2025
[3]

URL: https://proceedings.mlr.press/v291/chia25a.html. [p. 3] [CNY23] Thomas Chen, Shivam Nadimpalli, and Henry Yuen. Testing and Learning Quantum Juntas Nearly Optimally. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1163–1185. SIAM, 2023.doi:10.1137/1. 9781611977554.ch43. [pp. 3, 4, 27] [CSBH25] Laura Cui, Thoma...

work page doi:10.1137/1 2023
[4]

doi:10.1145/3618260.3649738. [pp. 4, 9, 25, 33] [GIKL24c] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Pseudoentangle- ment Ain’t Cheap, 2024.arXiv:2404.00126. [p. 4] [GKKT20] 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(20):204001, apr

work page doi:10.1145/3618260.3649738 2024
[5]

doi:10.1088/1751-8121/ab8111. [pp. 4, 18] [GNW21] David Gross, Sepehr Nezami, and Michael Walter. Schur–Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations.Communications in Mathematical Physics, 385(3):1325–1393,

work page doi:10.1088/1751-8121/ab8111
[6]

doi:10.1007/s00220-021-04118-7. [p. 4] [GOL25] Andi Gu, Salvatore F.E. Oliviero, and Lorenzo Leone. Magic-Induced Computational Separation in Entanglement Theory.PRX Quantum, 6:020324, 2025.doi:10.1103/ PRXQuantum.6.020324. [p. 4] [GOS+11] Parikshit Gopalan, Ryan O’Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wim- mer. Testing Fourier Dimensionality...

work page doi:10.1007/s00220-021-04118-7 2025
[7]

Association for Computing Machinery.doi:10.1145/ 3717823.3718169. [p. 4] [HKOT23] Jeongwan Haah, Robin Kothari, Ryan O’Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 363–390,

work page arXiv
[8]

doi:10.1109/FOCS57990.2023.00028. [pp. 3, 4, 6, 7, 8, 11, 15, 17, 18, 20, 21, 27, 28, 31] [HKP21] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Information-Theoretic Bounds on Quantum Advantage in Machine Learning.Physical Review Letters, 126(19):190505, 2021.doi:10.1103/PhysRevLett.126.190505. [p. 5] [HLB+24] Hsin-Yuan Huang, Yunchao Liu, Michael Br...

work page doi:10.1109/focs57990.2023.00028 2023
[9]

doi:10.1103/PhysRevLett.130.200403. [p. 6] [IL25] Vishnu Iyer and Daniel Liang. Tolerant Testing of Stabilizer States with Mixed State Inputs,

work page doi:10.1103/physrevlett.130.200403
[10]

URL:https://arxiv.org/abs/2411.08765,arXiv:2411.08765. [p. 4] [Iye25] Vishnu Iyer. Mildly-Interacting Fermionic Unitaries are Efficiently Learnable,

work page arXiv
[11]

arXiv:2504.11318. [p. 3] [KL25] John Kallaugher and Daniel Liang. Hamiltonian Locality Testing via Trotterized Postselection, 2025.arXiv:2505.06478. [p. 8] [LC22] Ching-Yi Lai and Hao-Chung Cheng. Learning Quantum Circuits of SomeTGates. IEEE Transactions on Information Theory, 68(6):3951–3964, 2022.doi:10.1109/ TIT.2022.3151760. [pp. 3, 5] [LOH24] Lorenz...

work page doi:10.22331/q-2024-05-27-1361 2025
[12]

Association for Computing Machinery.doi:10.1145/ 3717823.3718254. [p. 3] [MO10] Ashley Montanaro and Tobias J. Osborne. Quantum boolean functions, 2010.arXiv: 0810.2435. [p. 22] [MT25] Saeed Mehraban and Mehrdad Tahmasbi. Improved Bounds for Testing Low Stabilizer Complexity States. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, ST...

work page arXiv 2010
[13]

Association for Computing Machinery.doi:10.1145/3717823.3718228. [p. 4] [MW16] Ashley Montanaro and Ronald de Wolf.A Survey of Quantum Property Testing. Number 7 in Graduate Surveys. Theory of Computing Library, 2016.doi:10.4086/ toc.gs.2016.007. [p. 11] [NPVY24] Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. On the Pauli Spectrum ofQAC

work page doi:10.1145/3717823.3718228 2016
[14]

InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1498–1506, 2024.doi:10.1145/3618260. 3649662. [p. 4] [ODMZ22] Micha l Oszmaniec, Ninnat Dangniam, Mauro E.S. Morales, and Zolt´ an Zimbor´ as. Fermion Sampling: A Robust Quantum Computational Advantage Scheme Using Fermionic Linear Optics and Magic Input States.PRX Quan...

work page doi:10.1145/3618260 2024
[15]

doi:10.1103/PRXQuantum.3.020328. [p. 3] [Par25] Natalie Parham. Quantum circuit lower bounds in the magic hierarchy, 2025.arXiv: 2504.19966. [pp. 5, 32] [Ral20] Patrick Rall. Quantum algorithms for estimating physical quantities using block en- codings.Phys. Rev. A, 102:022408, Aug 2020.doi:10.1103/PhysRevA.102.022408. [p. 12] [SHH25] Thomas Schuster, Jon...

work page doi:10.1103/prxquantum.3.020328 2025
[16]

URL:https://ewintang.com/assets/tang-pcmi-lectures.pdf. [p. 12] [TW25] Ewin Tang and John Wright. Amplitude amplification and estimation require inverses, 2025.arXiv:2507.23787. [p. 30] [vACGN23] Joran van Apeldoorn, Arjan Cornelissen, Andr´ as Gily´ en, and Giacomo Nannicini. Quantum tomography using state-preparation unitaries. InProceedings of the 2023...

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/1.9781611977554.ch47 2025
[17]

IEEE Computer Society.doi: 10.1109/QCE52317.2021.00021. [p. 25] [Ver18] Roman Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cam- bridge University Press, 1st edition, 2018.doi:10.1017/9781108231596. [p. 20] [VH25] Francisco Vasconcelos and Hsin-Yuan...

work page doi:10.1109/qce52317.2021.00021 2021
[18]

doi:10.1103/PhysRevLett.113.210501. [pp. 6, 23] A Proof of Lemma 5.6 Lemma 5.6.For subspacesT⊆S⊆F 2n 2 , there exist integersa ′ ≤aandb ′ ≤b, together with an integerℓ≤b ′, such that T=⟨z 1, x1, . . . , za′, xa′, za′+1, . . . , za′+b′⟩ and S=⟨T, x a′+1, . . . , xa′+ℓ, za′+b′+1, xa′+b′+1, . . . , za+b′−ℓ, xa+b′−ℓ, za+b′−ℓ+1, . . . , za+b⟩ where[x i, xj] = ...

work page doi:10.1103/physrevlett.113.210501