论文标题
量子学习算法意味着电路下限
Quantum learning algorithms imply circuit lower bounds
论文作者
论文摘要
我们在量子算法的设计和电路下限之间建立了第一个一般连接。具体来说，令$ \ mathfrak {c} $为一类多项式大小的概念，假设$ \ mathfrak {c} $可以在均匀分布的下方使用会员查询，而错误的$ 1/2-γ$，则可以在时间$ t $ t $ task ungorithm。我们证明，如果$γ^2 \ cdot t \ ll 2^n/n $，则$ \ Mathsf {bqe} \ nsubseteq \ Mathfrak {c} $，其中$ \ Mathsf {bqe} $ \ mathsf {bqp} $。此结果在$γ$和$ t $中都是最佳的，因为在（经典）时间$ t = 2^n $（无错误）中或量子时间$ t = \ mathsf {poly}（poly}（poly}（n）$中，最多有错误的$ 1/2--ω（tour）$ 1/2--ω（2^n} $ nire，它不难学习（经典）时间$ t = 2^n $（无错误）中的任何类$ \ mathfrak {c} $的函数$ t = 2^n $（没有错误）。换句话说，即使对这些通用学习算法的边际改进也会导致复杂性理论的重大后果。 我们的证明是基于学习理论，伪随机性和计算复杂性的几项作品，以及至关重要的，基于Oliveira和Santhanam建立的非平凡的古典学习算法与电路下限之间的联系（CCC 2017）。扩展他们的量子学习算法的方法来提出重大挑战。 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 establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathfrak{C}$ be a class of polynomial-size concepts, and suppose that $\mathfrak{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 \cdot T \ll 2^n/n$, then $\mathsf{BQE} \nsubseteq \mathfrak{C}$, where $\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]$ is an exponential-time analogue of $\mathsf{BQP}$. This result is optimal in both $γ$ and $T$, since it is not hard to learn any class $\mathfrak{C}$ of functions in (classical) time $T = 2^n$ (with no error), or in quantum time $T = \mathsf{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.
