arXiv:2609.27128
Efficient Learning of Clifford-Scrambled Product States
Tobias Haug
Abstract
Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn $n$-qubit states prepared by random $T$-doped Clifford circuits with $T$-gate density below one via $O(n^2)$ Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn $T$-depth-one circuits using $O(n^2)$ queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.
AI Summary
The paper studies learning pure states whose independent small subsystems are hidden by an unknown global Clifford. Such states can have extensive magic and volume-law entanglement, so low stabilizer nullity is not required. It defines Clifford-product width as the smallest achievable largest block size over Clifford frames. The method uses two-copy Bell measurements. Affine equations on Bell outcomes identify Pauli stabilizers; after removing them, all exact quadratic equations correspond to hidden product cuts. Polarization yields commuting symplectic projectors whose joint eigenspaces give a unique irreducible subsystem decomposition. Binary linear algebra constructs a Clifford decoder without searching over circuits. Exact structure recovery needs $O((n^2+\log(1/\delta))/\gamma_2)$ Bell samples, where $\gamma_2$ is the minimum positive violation probability of a quadratic equation. Block tomography then learns the state. For blocks of size $k$, approximate learning takes resources polynomial in $n,2^k,1/\varepsilon,1/\gamma_1,\log(1/\delta)$, independently of $\gamma_2$; $\gamma_1$ measures separation from additional Pauli stabilizers. Applications include learning $C|T\rangle^{\otimes n}$, whose quadratic gap is $1/16$, and random globally Clifford-scrambled circuits with $t<n$ interspersed $T$ gates, with success at least $1-2^{t-n}-\delta$. Any $T$-depth-one unitary is exactly identified using $O(n^2+\log(1/\delta))$ forward queries via Choi states and subsequent circuit reconstruction. A quadratic-kernel rank test rules out state or unitary pseudorandomness whenever a Clifford-hidden product cut occurs with nonnegligible probability. The guarantees assume exactly pure, promised-class inputs. Noise robustness, nearly Pauli-stabilized subsystems, and general entangled residual MPSs remain open. The random-circuit guarantee requires independent uniform global Cliffords; general Choi learning does not guarantee diamond-norm accuracy or a unitary-circuit hypothesis.
Central claim may not hold: The abstract overstates efficient exact recovery of hidden product subsystems: the proved guarantee requires an inverse-polynomial quadratic support gap, whereas the gap-independent approximate learner need not recover the exact subsystems.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 7 + 25 pages