Tom Gur

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 revisit the problem of characterising the complexity of Quantum PAC learning, as introduced by Bshouty and Jackson [1]. Several quantum advantages have been demonstrated in this setting, however, none are generic: they apply to particular concept classes and typically only work when the distribution that generates the data is known. In the general case, it was recently shown by Arunachalam and de Wolf [2] that quantum PAC learners can only achieve constant factor advantages over classical PAC learners. We show that with a natural extension of the definition of quantum PAC learning used by Arunachalam and de Wolf, we can achieve a generic advantage in quantum learning. To be precise, for any concept class C of VC dimension d, we show there is an (ϵ,δ)-quantum PAC learner with sample complexity O(1/√ϵ[d+log(1/δ)]log^9(1/ϵ)). Up to polylogarithmic factors, this is a square root improvement over the classical learning sample complexity. We show the tightness of our result by proving an Ω(d/√ϵ) lower bound that matches our upper bound up to polylogarithmic factors. [1] SIAM J. Comput. 1998, 28, 1136-1153 [2] JMLR, 19 (2018) 1-36

Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum mutual information quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.

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.

We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: 1. We exhibit a problem, {Avoid One Encrypted String} (\AOES), whose classical randomized query complexity is O(1) but is maximally hard for pseudo-deterministic quantum algorithms (\Omega(N) query complexity). 2.We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(\log(N)) vs. \Theta(\sqrt{N})), while the randomized query complexity is O(1). Complementing these separations, we show that for any total problem R, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., \D(R) = \tilde O(\psQ(R)^5). On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, k-sum, and graph collision.