Quantum learning algorithms imply circuit lower bounds

• URL: http://arxiv.org/abs/2012.01920v1
• Date: Thu, 3 Dec 2020 14:03:20 GMT
• Title: Quantum learning algorithms imply circuit lower bounds
• Authors: Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
• Abstract summary: We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
• Score: 7.970954821067043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 - \gamma$ by a time $T$ quantum algorithm. We prove that if $\gamma^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 $\gamma$ 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 - \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.

Related papers

• Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
  We construct a classical oracle relative to which $mathsfP = mathsfNP$ but quantum-computable quantum-secure trapdoor one-way functions exist. Our result implies multi-copy pseudorandom states and pseudorandom unitaries, but also classical-communication public-key encryption, signatures, and oblivious transfer schemes.
  arXiv  Detail & Related papers  (2024-11-04T19:40:01Z)
• Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
  We study classes of constant-depth circuits with bounds that compute restricted threshold functions. For large enough values of $mathsfbPTFC0[k]$, $mathsfbPTFC0[k] contains $mathsfTC0[k].
  arXiv  Detail & Related papers  (2024-08-29T09:40:55Z)
• Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
  We establish connections between state tomography, pseudorandomness, quantum state, circuit lower bounds. We show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis.
  arXiv  Detail & Related papers  (2024-05-16T16:46:27Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Quantum Speedups for Bayesian Network Structure Learning [0.0]
  For networks with $n$ nodes, the fastest known algorithms run in time $O(cn)$ in the worst case, with no improvement in two decades. Inspired by recent advances in quantum computing, we ask whether BNSL admits a quantum speedup. We give two algorithms achieving $c leq 1.817$ and $c leq 1.982$.
  arXiv  Detail & Related papers  (2023-05-31T09:15:28Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  We study the complexity of PAC learning halfspaces in the presence of Massart noise. We show that no-time Massart halfspace learners can achieve error better than $Omega(eta)$, even if the optimal 0-1 error is small.
  arXiv  Detail & Related papers  (2022-07-28T17:50:53Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  For a quantum circuit $C$ on $n$ qubits and a sample $z in 0,1n$, the benchmark involves computing $|langle z|C|0n rangle|2$. We show that for any $varepsilon ge frac1mathrmpoly(n)$, outputting a sample $z$ is the optimal 1-query for $|langle z|C|0nrangle|2$ on average.
  arXiv  Detail & Related papers  (2020-08-20T01:04:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.