Quantum PAC learning

Question

Background

Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If there is no $2^{n^{o(1)}}$ factoring algorithm then this this is optimal [2]. Of course, on a quantum computer we know how to factor, so this lower bound does not help. Further, the optimal classical algorithm uses the Fourier spectrum of the function thus screaming "quantumize me!"

[1] N. Linial, Y. Mansour, and N. Nisan. [1993] "Constant depth circuits, Fourier transform, and learnability", Journal of the ACM 40(3):607-620.

[2] M. Kharitonov. [1993] "Cryptographic hardness of distribution-specific learning", Proceedings of ACM STOC'93, pp. 372-381.

In fact, 6 years ago, Scott Aaronson put the learnability of $AC^0$ as one of his Ten Semi-Grand Challanges for Quantum Computing Theory.

---

Question

My question is three-fold:

1) Are there examples of natural function families that quantum computers can learn faster than classical computers given cryptographic assumptions?

2) Has there been any progress on the learnability of $AC^0$ in particular? (or the slightly more ambitious $TC^0$)

3) In regards to the learnability of $TC^0$, Aaronson comments: "then quantum computers would have an enormous advantage over classical computers in learning close-to-optimal weights for neural networks." Can somebody provide a reference on how weight updating for neural nets and $TC^0$ circuits relate? (apart from the fact that threshold gates look like sigmoid neurons) (This question was asked and answered already)

Answer 1

I'll take a shot at your first question:

Are there examples of natural function families that quantum computers can learn faster than classical computers given cryptographic assumptions?

Well, it depends on the exact model and the resource being minimized. One option is to compare the sample complexity (for distribution-independent PAC learning) of the standard classical model with a quantum model that is given quantum samples (i.e., instead of being given a random input and the corresponding function value, the algorithm is provided with a quantum superposition over inputs and their functions values). In this setting, quantum PAC learning and classical PAC learning are basically equivalent. The classical upper bound on sample complexity and the quantum lower bound on sample complexity are almost the same, as shown by the following sequence of papers:

[1] R. Servedio and S. Gortler, “Equivalences and separations between quantum and classical learnability,” SIAM Journal on Computing, vol. 02138, pp. 1–26, 2004.

[2] A. Atici and R. Servedio, “Improved bounds on quantum learning algorithms,” Quantum Information Processing, pp. 1–18, 2005.

[3] C. Zhang, “An improved lower bound on query complexity for quantum PAC learning,” Information Processing Letters, vol. 111, no. 1, pp. 40–45, Dec. 2010.

Moving on to time complexity, using the same quantum PAC model, Bshouty and Jackson showed that DNFs can be quantum PAC learnt in polynomial time over the uniform distribution [4], further improved in [5]. The best known classical algorithm for this runs in $O(n^{\log n})$ time. Atici and Servedio [6] also show improved results for learning and testing juntas.

[4] N. Bshouty and J. Jackson, “Learning DNF over the uniform distribution using a quantum example oracle,” SIAM Journal on Computing, vol. 28, no. 3, pp. 1136–1153, 1998.

[5] J. Jackson, C. Tamon, and T. Yamakami, “Quantum DNF learnability revisited,” Computing and Combinatorics, pp. 595–604, 2002.

[6] A. Atıcı and R. Servedio, “Quantum Algorithms for Learning and Testing Juntas,” Quantum Information Processing, vol. 6, no. 5, pp. 323–348, Sep. 2007.

On the other hand, if you're interested in the standard classical PAC model only, using quantum computing as a post-processing tool (i.e., no quantum samples), then Servedio and Gortler [1] observed that there is a concept class due to Kearns and Valiant that cannot be classically PAC learnt assuming the hardness of factoring Blum integers, but can be quantumly PAC learnt using Shor's algorithm.

The situation for Angluin's model of exact learning through membership queries is somewhat similar. Quantum queries can only give a polynomial speedup in terms of query complexity. However, there is an exponential speedup in time complexity assuming the existence of one-way functions [1].

I have no idea about the second question. I'd be happy to hear more about that too.

Answer 2

This is certainly not a full answer to your question, but hopefully helps with the first part. There seems to have been quite an amount of interest in using quantum algorithms to identify unknown oracles. One example of this is a recent paper from Floess, Andersson and Hillery (arXiv:1006.1423) which adapts the Bernstein-Vazirani algorithm to identify Boolean functions which depend on only a small subset of the input variables (juntas). They use this approach to determine the oracle function for low-degree polynomials (they explicitly deal with linear, quadratic and cubic cases).