Srinivasan Arunachalam

In a recent breakthrough in additive combinatorics, Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) resolved the polynomial Freiman-Ruzsa conjecture. Here, we algorithmize their main result by dequantizing the stabilizer learning algorithm of Chen et al. [QIP'25]

We consider the following task: suppose an algorithm is given copies of an unknown $n$-qubit quantum state $\ket{\psi}$ promised $(i)$ $\ket{\psi}$ is $\varepsilon_1$-close to a stabilizer state in fidelity or $(ii)$ $\ket{\psi}$ is $\varepsilon_2$-far from all stabilizer states, decide which is the case. We show that for every $\varepsilon_1>0$ and $\varepsilon_2\leq \varepsilon_1^C$, there is a $\poly(1/\varepsilon_1)$-sample and $n\cdot \poly(1/\varepsilon_1)$-time algorithm that decides which is the case (where $C>1$ is a universal constant). Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of quantum states and new bounds on stabilizer covering for structured subsets of Paulis using results in additive~combinatorics.

We initiate the study of \emph{quantum agnostic learning} of phase states with respect to a function class $\mathcal{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}$: given copies of an unknown $n$-qubit state $|\psi\rangle$ which has fidelity $\textsf{opt}$ with a phase state $|\phi_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle$ for some $c\in \mathcal{C}$, output $|\phi\rangle$ which has fidelity $|\langle \phi | \psi \rangle|^2 \geq \textsf{opt}-\varepsilon$. To this end, we give agnostic learning protocols for the following classes: \begin{enumerate} \item Size-$t$ decision trees which runs in time $\textsf{poly}(n,t,1/\varepsilon)$. This also implies $k$-juntas can be agnostically learned in time $\textsf{poly}(n,2^k,1/\varepsilon)$. \item $s$-term DNF formulas in near-polynomial time $\textsf{poly}(n,(s/\varepsilon)^{\log \log s/\varepsilon})$. \end{enumerate} Our main technical contribution is a \emph{quantum agnostic boosting} protocol which converts a ``weak'' agnostic learner (which outputs a \emph{parity state} $|\phi\rangle$ such that $|\langle \phi|\psi\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)$) into a ``strong'' learner (which outputs a sum of parity states $|\phi'\rangle$ such that $|\langle \phi'|\psi\rangle|^2\geq \textsf{opt} - \varepsilon$). Using quantum agnostic boosting, we obtain the first ``near'' polynomial-time $n^{O(\log \log n)}$ algorithm for learning $\textsf{poly}(n)$-sized depth-$3$ circuits (consisting of $\textsf{AND}$, $\textsf{OR}$, $\textsf{NOT}$ gates) in the uniform quantum $\textsf{PAC}$ model using quantum examples. Classically, the analogue of efficient learning depth-$3$ circuits (and even depth-$2$ circuits) in the uniform $\textsf{PAC}$ model has been a longstanding open question in computational learning theory. Our work nearly settles this question, when the learner is given quantum examples.

We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(log N) in this model, however, every interactive randomized protocol has cost Ømega(sqrtN), settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least Ømega(log N) clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost O(log N). We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.

We make progress in understanding the relationship between learning models with access to entangled, separable and statistical measurements in the quantum statistical query (QSQ) model. We show the following results. Entangled versus separable measurements: The goal is to learn an unknown f from the concept class C containing functions from 0,1^n to [k] given copies of a uniform superposition over |x,f(x)>. We show that, if T copies suffice to learn f using entangled measurements, O(nT^2) copies suffice to learn f using only separable measurements. Entangled versus statistical measurements: The goal is to learn a function f in C given access to separable measurements or statistical measurements. We exhibit a concept class C based of degree-2 functions with exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise). This proves the ""quantum analogue"" of the seminal result of Blum et al. that separates classical SQ learning from classical PAC learning with classification noise. QSQ lower bounds for learning states: We introduce a quantum statistical query dimension (QSD), and use it to give lower bounds on the QSQ complexity of learning. We prove superpolynomial QSQ lower bounds for testing purity of quantum states, shadow tomography, learning coset states for the Abelian hidden subgroup problem, degree-2 functions, planted biclique states, and learning output states of Clifford circuits of depth polylog(n). We also show that an extension of QSD characterizes the complexity of general search problems. Further applications: We give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model. Prior works by Quek et al., Hinsche et al., and Nietner et al. proved analogous results assuming diagonal measurements and our work removes this assumption.

We consider the problem of learning low-degree quantum objects up to ε-error in l_2-distance. We show the following results: (I) unknown n-qubit degree-d (in the Pauli basis) quantum channels and unitaries can be learned using O(1/ε^d) queries (which is independent of n), (II) polynomials p:-1,1^n -> [-1,1] arising from d-query quantum algorithms can be learned from O((1/ε)^d log n) many random examples (x,p(x)) (which implies learnability even for d=O(log n)), and (III) degree-d polynomials p:-1,1^n -> [-1,1] can be learned through O(1/ε^d) queries to a quantum unitary Up that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded polynomials.

Abstract We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.

Abstract We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let C be a class of polynomial-size concepts, and suppose that C can be learned in the PAC model under the uniform distribution with membership queries, and with error 1/2 - c by a time T quantum algorithm. We prove that if (c^2 * T) << 2^n/n, then BQE is not contained in C, where BQE = BQTIME[2^{O(n)}] is an exponential-time analogue of BQP. This result is optimal in both c and T since it is not hard to learn any class C of functions in (classical) time T = 2^n (with no error) or in quantum time T = poly(n) with error at most 1/2 - \Omega(2^{-n/2}) via Fourier sampling. In other words, even a marginal improvement on these generic learning algorithms would lead to major consequences in complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and crucially, on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.