Antecedentes
Las funciones en son PAC que se pueden aprender en tiempo cuasipolinomial con un algoritmo clásico que requiere consultas elegidas al azar para aprender un circuito de profundidad d [1]. Si no hay un algoritmo de factorización , entonces esto es óptimo [2]. Por supuesto, en una computadora cuántica sabemos cómo factorizar, por lo que este límite inferior no ayuda. Además, el algoritmo clásico óptimo utiliza el espectro de Fourier de la función gritando "¡cuantifícame!"
[1] N. Linial, Y. Mansour y N. Nisan. [1993] "Circuitos de profundidad constante, transformada de Fourier y capacidad de aprendizaje", Journal of the ACM 40 (3): 607-620.
[2] M. Kharitonov. [1993] "Dureza criptográfica del aprendizaje de distribución específica", Actas de ACM STOC'93, pp. 372-381.
De hecho, hace 6 años, Scott Aaronson puso la capacidad de aprendizaje de como uno de sus Diez Semi-Grandes Desafíos para la teoría de la computación cuántica .
Pregunta
Mi pregunta es triple:
1) ¿Hay ejemplos de familias de funciones naturales que las computadoras cuánticas pueden aprender más rápido que las computadoras clásicas dadas las suposiciones criptográficas?
2) ¿Ha habido algún progreso en la capacidad de aprendizaje de en particular? (o el poco más ambicioso )
3) Con respecto a la capacidad de aprendizaje de , Aaronson comenta: "entonces las computadoras cuánticas tendrían una enorme ventaja sobre las computadoras clásicas en el aprendizaje de pesos cercanos a los óptimos para redes neuronales". ¿Alguien puede proporcionar una referencia sobre cómo se relacionan la actualización de peso para redes neuronales y circuitos ? (aparte del hecho de que las puertas de umbral se parecen a las neuronas sigmoide) (Esta pregunta se le preguntó y respondió ya )
fuente