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].
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].
In this paper, we study the problem of learning an unknown quantum circuit of a certain structure. If the unknown target is ann-qubit Clifford circuit, we devise an efficient algorithm to reconstruct its circuit representation by usingO(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 ofT-depth one on the computational basis. We show that the output state of aT-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 ofTgates of the target is of the orderO(logn), our algorithm requiresO(n2)queries to it and produces its equivalent circuit representation on the computational basis in timeO(n3). Using further additionalO(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.
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.
In this paper, we present a learning algorithm aimed at learning states obtained from computational basis states by Clifford circuits doped with a finite number t of T -gates. The algorithm learns an exact tomographic description of t -doped stabilizer states in terms of Pauli observables. This is possible because such states are countable and form a discrete set. To tackle the problem, we introduce a novel algebraic framework for t -doped stabilizer states, which extends beyond T -gates and includes doping with any kind of local non-Clifford gate. The algorithm requires resources of complexity poly(n,2t) and exhibits an exponentially small probability of failure.
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.
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.