# On computationally efficient learning for stabilizers and beyond

## Access full-text files

## Date

## Authors

## Journal Title

## Journal ISSN

## Volume Title

## Publisher

## Abstract

Artificial intelligence, big data, machine learning, neural networks – look up any recent research proposal and with good probability at least one of these phrases will appear. It’s no secret that learning has taken this era of computer science by storm in our attempt to create software that perform extremely complicated tasks. As one of the most accurate models of our physical world currently known, it then makes sense to think about what kinds of quantum systems can or cannot be learned. As with many problems in quantum information and quantum computing, the simplest non-trivial versions of these problems start with the stabilizer formalism. In this dissertation, we examine learning problems centered around the stabilizer formalism in various different models from a theoretical standpoint using the tools of computer science and quantum information. Specifically, our focus will be on computational complexity, rather than sample complexity. We begin by looking at learning in the tomographical sense. Here, one has black-box access to copies of an unknown quantum state |ψ⟩ and want to learn properties of the state or outright given an approximation of |ψ⟩. In this setting, [Mon17] gave an efficient learning algorithm for stabilizer states. The key algorithmic tool was Bell difference sampling, which allows one to sample from the stabilizer group of a stabilizer state. [GNW21] extended the analysis of Bell difference sampling beyond just stabilizer states. Throughout Part I we turn to Bell difference sampling to improve upon learning algorithms for states with only a few (i.e., either O(log n) or strictly less than n depending on context) T gates. By using symplectic Fourier analysis, which is the generalization of Boolean Fourier analysis for a symplectic vector space over 𝔽 [superscript 2n over subscript 2], we derive powerful tools to understand the Bell difference sampling distribution. With these tools we first give a tolerant property testing algorithm for stabilizer states. That is, we give an algorithm that distinguishes whether a state is ε1 close to some stabilizer state or ε2 far from all stabilizer states for certain parameter regimes of ε1 and ε2. We use our improved knowledge of Bell difference sampling to improve upon the completeness and soundness analysis of the property tester given by [GNW21], which is not tolerant. A second application is stabilizer fidelity estimation and approximation. Given a state |ψ⟩ that is O(1) close to a stabilizer state, we output such a stabilizer state in time 2 [superscript O(n)]. This beats the previous 2 [superscript O(n²)] brute force search algorithm. Having such a stabilizer state also lets us figure out how close |ψ⟩ is to being stabilizer. A third application is extending Montanaro’s learning algorithm to the output of Clifford + O(log n) non-Clifford gate circuits. More generally, our algorithm interpolates between Montanaro’s algorithm and pure state tomography algorithms with runtime that is poly(n)∗exp(t) where t is the number of non-Clifford gates. This asymptotically matches the runtime of classical simulation algorithms for such circuits. A key algorithmic step in this work is the ability to “compress” the “stabilizer-ness” of a state onto a few qubits, allowing the “non-stabilizer-ness” to be brute-forced on the remaining qubits. Our final application is pseudorandomness lower bounds. Introduced by [JLS18], a pseudorandom quantum state ensemble is a set of quantum states that are computationally indistinguishable from Haar random. By re-purposing algorithms from above, we produce a test that behaves differently when given a state produced by less than n T gates in a Clifford + T circuit versus being given a Haar random state. We note that this is tight assuming the existence of linear-time quantum-secure One-Way Functions. Pivoting now, we also study the stabilizer formalism in the PAC learning framework proposed by [Val84]. Here one does not have control over the measurements, but must make do regardless (within information theoretic limits). We analyze the problem in two ways. First we show that, unlike stabilizer states, learning the associated Clifford unitaries in the proper PAC model is NP-hard. This is done by a reduction to the problem of finding a full rank matrix in an affine subspace of matrices over 𝔽₂. The second is studying stabilizer states in the presence of noise. We utilize the Statistical Query framework, a popular modification to the PAC learning framework that is inherently tolerant to noise. There, we also show hardness in this framework by a reduction to Learning Parities with Noise. This gives evidence that even in the PAC model stabilizer states are hard to learn with noise.