Highly entangled and highly non-stabilizer quantum states need not be hard to learn. We give efficient algorithms for testing and recovering hidden tensor-product structure in unknown pure state vectors of the form $\lvertψ\rangle = U_C \bigotimes_i \lvertψ_i\rangle$, where $U_C$ is an arbitrary unknown Clifford unitary. Although the Clifford can thoroughly scramble the visible product structure, we prove that the Bell distribution retains a characteristic family of quadratic symmetries. By simultaneously block-diagonalising these symmetries, our algorithms linearize the problem and manage to recover both a disentangling Clifford and the hidden partitions with polynomial sample and computational complexity. This may be viewed as an extension of the abelian StateHSP paradigm in which classical post-processing exposes genuinely quadratic structure. Applied to Choi states, the method yields efficient proper learning algorithms for typical $t$-doped Clifford unitaries in regimes containing exponentially more $T$ gates than previously accessible: the required condition fails only for an exponentially small fraction of circuits when $t\sim n$, and continues to hold for a constant fraction even when $t=2n$. Our framework also provides tools for compressing structured many-body Hamiltonians and suggests benchmarking protocols for encoded logical product states in the early fault-tolerant regime.
AI Summary
The paper studies whether tensor-product structure hidden by an unknown Clifford can be efficiently detected and recovered from copies of a pure state $|\psi\rangle=C\bigotimes_i|\psi_i\rangle$, even when the resulting state has extensive entanglement and magic.
The method uses Bell measurements on pairs of copies. Hidden subsystem purities impose quadratic constraints on the Bell-outcome support, which remain quadratic under Clifford scrambling. Lifting outcomes to degree-two features makes constraint recovery a linear-algebra problem. After extracting stabilizers, simultaneous block-diagonalisation of the constraints, using finite-dimensional algebra decompositions, recovers a symplectic frame and a hidden partition. Testing requires $O(\lambda^{-2}[n^2+\log(1/\delta)])$ copies, with $\lambda=\min(\eta,\epsilon)$; partition and disentangler learning has the same bound with $\lambda=\min(\eta,\epsilon/\sqrt n)$, and polynomial runtime. Here $\eta$ is a promised gap separating non-stabilizer Pauli expectations from magnitude one. Full tomography additionally requires efficiently learnable factors, such as logarithmic-size blocks.
Applied to Choi states, the construction gives proper learning of $t$-doped Clifford unitaries when their conjugated Pauli-rotation labels are linearly independent. For independently uniform Clifford layers, this condition holds with probability $\prod_{j=0}^{t-1}(1-(2^j-1)/(4^n-1))$: exponentially close to one for $t\leq(2-c)n$, and constant at $t=2n$.
The guarantees assume exact Clifford-scrambled product structure and the stabilizer gap; they are not worst-case guarantees for linear-$t$ doping. Robust recovery under perturbations remains open: noisy quadratic constraints lead to a parity-learning problem resembling learning parity with noise. Benchmarking and Hamiltonian applications are proposed rather than experimentally demonstrated.
Little sign of AI-generated textStrong assumptionsOverclaims
Central claim may not hold: The abstract omits the stabilizer-gap promise required by the formal efficiency guarantees, whose costs depend polynomially on the inverse gap.
The polynomial-time reconstruction proof unjustifiably treats idempotents lifted from the centralizer's semisimple quotient as unique central idempotents of the full centralizer, leaving its adjoint-pairing and symplectic reconstruction steps unestablished.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Efficient learning of Clifford disentanglers and typical t-doped unitaries with exponentially more T gates
Highly entangled and highly non-stabilizer quantum states need not be hard to learn. We give efficient algorithms for testing and recovering hidden tensor-product structure in unknown pure state vectors of the form ∣ψ⟩=UC⨂i∣ψi⟩, where UC is an arbitrary unknown Clifford unitary. Although the Clifford can thoroughly scramble the visible product structure, we prove that the Bell distribution retains a characteristic family of quadratic symmetries. By simultaneously block-diagonalising these symmetries, our algorithms linearize the problem and manage to recover both a disentangling Clifford and the hidden partitions with polynomial sample and computational complexity. This may be viewed as an extension of the abelian StateHSP paradigm in which classical post-processing exposes genuinely quadratic structure. Applied to Choi states, the method yields efficient proper learning algorithms for typical t-doped Clifford unitaries in regimes containing exponentially more T gates than previously accessible: the required condition fails only for an exponentially small fraction of circuits when t∼n, and continues to hold for a constant fraction even when t=2n. Our framework also provides tools for compressing structured many-body Hamiltonians and suggests benchmarking protocols for encoded logical product states in the early fault-tolerant regime.
The paper studies whether tensor-product structure hidden by an unknown Clifford can be efficiently detected and recovered from copies of a pure state ∣ψ⟩=C⨂i∣ψi⟩, even when the resulting state has extensive entanglement and magic.
The method uses Bell measurements on pairs of copies. Hidden subsystem purities impose quadratic constraints on the Bell-outcome support, which remain quadratic under Clifford scrambling. Lifting outcomes to degree-two features makes constraint recovery a linear-algebra problem. After extracting stabilizers, simultaneous block-diagonalisation of the constraints, using finite-dimensional algebra decompositions, recovers a symplectic frame and a hidden partition. Testing requires O(λ−2[n2+log(1/δ)]) copies, with λ=min(η,ϵ); partition and disentangler learning has the same bound with λ=min(η,ϵ/n), and polynomial runtime. Here η is a promised gap separating non-stabilizer Pauli expectations from magnitude one. Full tomography additionally requires efficiently learnable factors, such as logarithmic-size blocks.
Applied to Choi states, the construction gives proper learning of t-doped Clifford unitaries when their conjugated Pauli-rotation labels are linearly independent. For independently uniform Clifford layers, this condition holds with probability ∏j=0t−1(1−(2j−1)/(4n−1)): exponentially close to one for t≤(2−c)n, and constant at t=2n.
The guarantees assume exact Clifford-scrambled product structure and the stabilizer gap; they are not worst-case guarantees for linear-t doping. Robust recovery under perturbations remains open: noisy quadratic constraints lead to a parity-learning problem resembling learning parity with noise. Benchmarking and Hamiltonian applications are proposed rather than experimentally demonstrated.
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(n2) 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(n2) queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.
Preparing complex quantum states is of limited value without efficient methods for extracting useful classical information from them. This thesis studies when such information can be extracted efficiently, given copies of an unknown quantum state or query access to an unknown unitary transformation. We begin with pure state tomography. We present an algorithm that uses only nonadaptive single-qubit Pauli measurements yet achieves optimal copy and time complexities up to logarithmic factors. This is the first full state tomography algorithm with near-optimal running time. We then show how additional structure can make tomography time-efficient, giving algorithms for two structured classes of quantum states: non-interacting fermions and near-stabilizer states. We also introduce a new learning task, agnostic tomography, where the goal is to find the best approximation to an arbitrary quantum state from a structured class of states, and give efficient algorithms in this model. Turning to property testing, we give an efficient tester for stabilizer dimension, which implies that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare n-qubit computationally pseudorandom states. We also prove copy-complexity lower bounds for testing low-degree phase states, showing that testing is nearly as hard as learning these states. More strongly, for every fixed degree d, ensembles of n-qubit degree-d phase states form exponentially accurate approximate state t-designs for t=Ω(n^{⌊(d-1)/2⌋}). Finally, we extend these questions from states to unitary transformations. We develop a general framework for learning unitary transformations by exploiting low-complexity Pauli spectra. This framework unifies and extends prior learning algorithms for Clifford and near-Clifford circuits, shallow circuits, quantum juntas, and fermionic matchgate circuits.
Full tomography of a generic many-qubit quantum state requires exponentially many copies, while suitable structural constraints can make reconstruction sample-efficient. Existing approaches exploit, for example, limited entanglement structure, low magic, or constrained state-preparation circuits. Here we consider a class of mixed states that can simultaneously exhibit extensive entanglement and extensive magic. Specifically, we introduce Clifford-encoded block-product (CEBP) states, obtained by applying an unknown global Clifford unitary to a tensor product of arbitrary mixed states supported on unknown blocks of bounded size. We show that, for a fixed block size, CEBP states can be reconstructed using polynomially many copies by exploiting Clifford-preserved Pauli correlations to recover the latent structure and reduce the remaining problem to local tomography. Our result demonstrates that sample-efficient tomography can arise from bounded complexity in a latent frame even when the physical state is highly entangled, highly magical, and mixed, and suggests complexity modulo structured transformations as a broader organizing principle for quantum-state learnability.
Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the Hidden Subgroup Problem (HSP). In this work, we study quantum algorithms for learning symmetries of \emph{quantum} objects. Existing work in this area centres on the recently introduced State Hidden Subgroup Problem (StateHSP), a quantum generalisation of HSP in which the task is to learn the symmetry subgroup of a quantum state. We develop efficient quantum algorithms for non-abelian StateHSP when the hidden subgroup is normal and the ambient group belongs to a broad class of non-abelian groups, extending the previous general theory beyond the abelian setting.
StateHSP learns \emph{Bose} symmetries, under which a state must be invariant exactly under the action of the symmetry group. In quantum mechanics, however, physically equivalent pure states are defined only up to global phase. Motivated by this, we introduce a natural notion of \emph{Anyonic} state symmetry learning, based on invariance up to global phase. We give an efficient quantum algorithm by reducing the problem to StateHSP, where the reduction rests on a new correspondence between linearisations of projective representations and linear error-correcting codes. As an application, we obtain an improved algorithm for learning stabiliser groups of mixed qudit states of arbitrary local dimension. Finally, we introduce symmetry learning problems for other quantum objects, including unitaries, Hamiltonians, and finite collections of states, and give efficient algorithms for them by reduction to state symmetry learning. Together, these results broaden the scope of state symmetry learning as a common algorithmic primitive for learning quantum symmetries.
Scrambling of quantum information is an important feature at the root of randomization and benchmarking protocols, the onset of quantum chaos, and black-hole physics. Unscrambling this information is possible given perfect knowledge of the scrambler [arXiv:1710.03363]. We show that one can retrieve the scrambled information even without any previous knowledge of the scrambler, by a learning algorithm that allows the building of an efficient decoder. Remarkably, the decoder is classical in the sense that it can be efficiently represented on a classical computer as a Clifford operator. It is striking that a classical decoder can retrieve with fidelity one all the information scrambled by a random unitary that cannot be efficiently simulated on a classical computer, as long as there is no full-fledged quantum chaos. This result shows that one can learn the salient properties of quantum unitaries in a classical form and sheds a new light on the meaning of quantum chaos. Furthermore, we obtain results concerning the algebraic structure of t-doped Clifford circuits, i.e., Clifford circuits containing t non-Clifford gates, their gate complexity, and learnability that are of independent interest. In particular, we show that a t-doped Clifford circuit Ut can be decomposed into two Clifford circuits ${U}_{0},{U}_{0}^{\ensuremath{'}}$ that sandwich a local unitary operator ut, i.e., ${U}_{t}={U}_{0}{u}_{t}{U}_{0}^{\ensuremath{'}}$. The local unitary operator ut contains t non-Clifford gates and acts nontrivially on at most t qubits. As simple corollaries, the gate complexity of the t-doped Clifford circuit Ut is O(n2+t3), and it admits a efficient process tomography using poly(n,2t) resources.
Determining the quantum-classical boundary between quantum circuits that can be efficiently simulated classically and those that cannot remains a fundamental question. One approach to classical simulation is to represent the output of a quantum circuit as a Clifford-augmented matrix product state (CAMPS), which, via a disentangling algorithm, decomposes the wave function into Clifford and MPS components, and from which Pauli expectation values can be computed in time polynomial in the MPS bond dimension. In this work, we develop an optimization-free disentangling (OFD) algorithm for Clifford circuits either doped with T gates or, equivalently, preceded by multiqubit gates of the form α I + β P . We give a simple and easily computed algebraic criterion that characterizes the individual quantum circuits for which OFD generates an efficient CAMPS—the bond dimension is exponential in the null space of a Galois binary field GF(2) matrix induced by a tableau of the twisted Pauli strings P . This significantly increases the number of circuits with rigorous polynomial-time classical simulations. We also give evidence that the typical N qubit random Clifford circuit doped with N uniformly distributed T gates of polylogarithmic depth or greater has a CAMPS with polynomial bond dimension. In addition, we compare OFD against disentangling by optimization. We further explore the representability of CAMPS for random Clifford circuits doped with more than N T gates. We also propose algorithms for sampling, probability, and amplitude estimation of bitstrings, and evaluation of entanglement Rényi entropy from CAMPS, which, though still having exponential complexity, are more efficient than standard MPS simulations. This work establishes a versatile framework for understanding classical simulatability of Clifford + T circuits and explores the interplay between quantum entanglement and quantum magic in quantum systems.