The Library
Quantum learning algorithms imply circuit lower bounds
Tools
Tools
Tools
Arunachalam, Srinivasan, Grilo, Alex B., Gur, Tom, Carboni Oliveira, Igor and Sundaram, Aarthi (2021) Quantum learning algorithms imply circuit lower bounds. In: The 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), Denver, Colorado, 7-10 Feb 2022. Published in: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) doi:10.1109/FOCS52979.2021.00062 ISSN 2575-8454.
|
PDF
WRAP-quantum-learning-algorithms-imply-circuit-lower-bounds-Gur-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1327Kb) | Preview |
Official URL: https://doi.org/10.1109/FOCS52979.2021.00062
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 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⊄C , 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 C 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 quantum speedup over these generic learning algorithms would lead to major consequences in complexity lower bounds. As a consequence, our result shows that the study of quantum learning speedups is intimately connected to fundamental open problems about algorithms, quantum computing, and complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and 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, since extracting computational hardness from a quantum computation is inherently more complicated. 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 delic...
| Item Type: | Conference Item (Paper) | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Quantum computers -- Mathematical models, Computer algorithms, Computational complexity | |||||||||||||||||||||
| Journal or Publication Title: | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) | |||||||||||||||||||||
| Publisher: | IEEE | |||||||||||||||||||||
| ISSN: | 2575-8454 | |||||||||||||||||||||
| Official Date: | 4 March 2021 | |||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||
| DOI: | 10.1109/FOCS52979.2021.00062 | |||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||
| Reuse Statement (publisher, data, author rights): | © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | |||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||
| Date of first compliant deposit: | 20 August 2021 | |||||||||||||||||||||
| Date of first compliant Open Access: | 23 August 2021 | |||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||||||||
| Title of Event: | The 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021) | |||||||||||||||||||||
| Type of Event: | Conference | |||||||||||||||||||||
| Location of Event: | Denver, Colorado | |||||||||||||||||||||
| Date(s) of Event: | 7-10 Feb 2022 | |||||||||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
