2020/12/03 by Srinivasan Arunachalam, Alex B. Grilo, Arunachalam, Srinivasan +8 · 1 citation
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #cs.LG #quant-ph
paper · pdf · doi:10.48550/arxiv.2012.01920
openalex publication_date 2020/12/03 · arxiv created 2021/12/01 · arxiv updated 2021/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let \mathfrakC be a class of polynomial-size concepts, and suppose that \mathfrakC can be PAC-learned with membership queries under the uniform distribution with error 1/2 - γ by a time T quantum algorithm. We prove that if γ2 ⋅ T ≪ 2n/n, then BQE \nsubseteq \mathfrakC, where BQE = BQTIME[2O(n)] is an exponential-time analogue of BQP. This result is optimal in both γ and T, since it is not hard to learn any class \mathfrakC of functions in (classical) time T = 2n (with no error), or in quantum time T = poly(n) with error at most 1/2 - Ω(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.