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.
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.
Recent work has shown that
n-qubit quantum states output by circuits with at most
t single-qubit non-Clifford gates can be learned to trace distance
ε using
poly(n,2t,1/ε) time and samples. All prior algorithms achieving this runtime use entangled measurements across two copies of the input state. In this work, we give a similarly efficient algorithm that learns the same class of states using only single-copy measurements.
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.
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.
In this paper, we study the problem of learning an unknown quantum circuit of a certain structure. If the unknown target is an
n-qubit Clifford circuit, we devise an efficient algorithm to reconstruct its circuit representation by using
O(n2)queries to it. For decades, it has been unknown how to handle circuits beyond the Clifford group since the stabilizer formalism cannot be applied in this case. Herein, we study quantum circuits of
T-depth one on the computational basis. We show that the output state of a
T-depth one circuit can be represented by a stabilizer pseudomixture with a specific algebraic structure. Using Pauli and Bell measurements on copies of the output states, we can generate a hypothesis circuit that is equivalent to the unknown target circuit on computational basis states as input. If the number of
Tgates of the target is of the order
O(logn), our algorithm requires
O(n2)queries to it and produces its equivalent circuit representation on the computational basis in time
O(n3). Using further additional
O(43n)classical computations, we can derive an exact description of the target for arbitrary input states. Our results greatly extend the previously known facts that stabilizer states can be efficiently identified based on the stabilizer formalism.
In this paper, we study the problem of learning an unknown quantum circuit of a certain structure. If the unknown target is an n-qubit Clifford circuit, we devise an algorithm to reconstruct its circuit representation by using O(n2) queries to it. It is unknown for decades how to handle circuits beyond the Clifford group for which the stabilizer formalism cannot be applied. Herein, we study quantum circuits of T -depth one on the computational basis. We show that their output states can be represented by a certain stabilizer pseudomixture. By analyzing the algebraic structure of the stabilizer pseudomixture, we can generate a hypothesis circuit that is equivalent to the unknown target T -depth one quantum circuit U on computational basis states, using Pauli and Bell measurements. If the number of T gates in U is of the order O(log n), our algorithm requires O(n2) queries to U to produce its equivalent circuit representation on the computational basis in time O(n3). Using further additional O(43n) classical computations, we can derive an exact description of U for arbitrary input states. Our results greatly extend the previously known facts that stabilizer states can be efficiently identified based on the stabilizer formalism.The full manuscript can be found at [1].