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.
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.
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.
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.
Characterizing a quantum system by learning its state or evolution is a fundamental problem in quantum physics and learning theory with a myriad of applications. Recently, as a new approach to this problem, the task of agnostic state tomography was defined, in which one aims to approximate an arbitrary quantum state by a simpler one in a given class. Generalizing this notion to quantum processes, we initiate the study of agnostic process tomography: given query access to an unknown quantum channel Φ and a known concept class C of channels, output a quantum channel that approximates Φ as well as any channel in the concept class C , up to some error. In this work, we propose several natural applications for this new task in quantum machine learning, quantum metrology, classical simulation, and error mitigation. In addition, we give efficient agnostic process tomography algorithms for a wide variety of concept classes, including Pauli strings, Pauli channels, quantum junta channels, low-degree channels, and a class of channels produced by Q A C 0 circuits. The main technical tool we use is Pauli spectrum analysis of operators and superoperators. We also prove that, using ancilla qubits, any agnostic state tomography algorithm can be extended to one solving agnostic process tomography for a compatible concept class of unitaries, immediately giving us efficient agnostic learning algorithms for Clifford circuits, Clifford circuits with few T gates, and circuits consisting of a tensor product of single-qubit gates. Together, our results provide insight into the conditions and new algorithms necessary to extend the learnability of a concept class from the standard tomographic setting to the agnostic one.
We give an algorithm for pure state tomography with near-optimal copy and time complexity using only single-qubit measurements. Specifically, given O(2n/ε) copies of an unknown n-qubit pure state ∣ψ⟩, the algorithm performs only nonadaptive Pauli measurements, runs in time O(2n/ε), and outputs ∣ψ⟩ with fidelity at least 1−ε with ∣ψ⟩ with high probability. This is the first algorithm for pure state tomography that achieves near-optimal running time.
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.
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning n-qubit quantum unitaries U and Hamiltonians H, given query access to U or the unitary evolution of H, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form U=∑iαiCi over Cliffords Ci with bounded Clifford extent ∑i∣αi∣. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary U with optimal Clifford fidelity opt, outputs a Clifford unitary witnessing fidelity ≥opt−ε for some error ε>0, in time poly(n,(1/ε)log(1/ε)). We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity Ω(2n)) in the Pauli basis but are Clifford structured.