We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and O ( log n ) non-Clifford gates. Specifically, for an n -qubit state | ψ ⟩ prepared with at most t non-Clifford gates, our algorithms use p o l y ( n , 2 t , 1 / ε ) time and copies of | ψ ⟩ to learn | ψ ⟩ to trace distance at most ε .The first algorithm for this task is more efficient, but requires entangled measurements across two copies of | ψ ⟩ . The second algorithm uses only single-copy measurements at the cost of polynomial factors in runtime and sample complexity. Our algorithms more generally learn any state with sufficiently large stabilizer dimension, where a quantum state has stabilizer dimension k if it is stabilized by an abelian group of 2 k Pauli operators. We also develop an efficient property testing algorithm for stabilizer dimension, which may be of independent interest.
Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an
n-qubit stabilizer state can be learned from
Θ(n) copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require
Ω(n2) copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary
n-qubit stabilizer state from
Θ(n) single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with
k qubits of quantum memory, the optimal testing tradeoff
Θ(n−k+1/ε) at infidelity
ε. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most
r, including states prepared by Clifford circuits with a bounded number of
T gates, can be learned using
O(n2r) single-copy measurements.
One of the primary objectives in the field of quantum state learning is to develop algorithms that are time-efficient for learning states generated from quantum circuits. Earlier investigations have demonstrated time-efficient algorithms for states generated from Clifford circuits with at most log(n) non-Clifford gates. However, these algorithms necessitate multi-copy measurements, posing implementation challenges in the near term due to the requisite quantum memory. On the contrary, using solely single-qubit measurements in the computational basis is insufficient in learning even the output distribution of a Clifford circuit with one additional T gate under reasonable post-quantum cryptographic assumptions. In this work, we introduce an efficient quantum algorithm that employs only nonadaptive single-copy measurement to learn states produced by Clifford circuits with a maximum of O(logn) non-Clifford gates, filling a gap between the previous positive and negative results.
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.
The experimental realization of increasingly complex quantum states underscores the pressing need for new methods of state learning and verification. In one such framework, quantum state tomography, the aim is to learn the full quantum state from data obtained by measurements. Without prior assumptions on the state, this task is prohibitively hard. Here, we present an efficient algorithm for learning states on n fermion modes prepared by any number of Gaussian and at most t non-Gaussian gates. By Jordan-Wigner mapping, this also includes n -qubit states prepared by nearest-neighbor matchgate circuits with at most t gates. Our algorithm is based exclusively on single-copy measurements and produces a classical representation of a state, guaranteed to be close in trace distance to the target state. The sample and time complexity of our algorithm is poly ( n , 2 t ) ; thus if t = O ( log ( n ) ) , it is efficient. We also show that, if t scales more than logarithmically, any learning algorithm to solve the same task must be inefficient, under common cryptographic assumptions. We also provide an efficient property-testing algorithm that, given access to copies of a state, determines whether such a state is far or close to the set of states for which our learning algorithm works. In addition to the outputs of quantum circuits, our tomography algorithm is efficient for some physical target states, such as those arising in time dynamics and low-energy physics of impurity models. Beyond tomography, our work sheds light on the structure of states prepared with few non-Gaussian gates and offers an improved upper bound on their circuit complexity, enabling an efficient circuit-compilation method.
We study single-copy stabilizer learning, the problem of identifying a stabilizer group of dimension
n−t from an
n-qubit quantum state
ρ. We obtain two complementary results. First, in the average case, logarithmic-depth local Clifford circuits suffice to efficiently learn almost all stabilizer groups with
t=O(logn), instead of the linear-depth measurements required in previous approaches. We support this result with numerical simulations for systems of up to 100 qubits. Second, we show that, in the worst case, any adaptive single-copy measurement scheme requires a number of samples that scales exponentially in
t. Together with existing results on two-copy learning, our findings suggest that, for large
t, identifying Pauli symmetries of a quantum system exhibits a quantum advantage in the learning setting.