fundo
As funções em são aprendidas pelo PAC em tempo quase-polinomial com um algoritmo clássico que requer O ( 2 l o g ( n ) O ( d ) ) consultas escolhidas aleatoriamente para aprender um circuito de profundidade d [1]. Se não houver um algoritmo de fatoração 2 n o ( 1 ) , então isso é ótimo [2]. Obviamente, em um computador quântico sabemos como fatorar, portanto esse limite inferior não ajuda. Além disso, o algoritmo clássico ideal usa o espectro de Fourier da função gritando "quantumize-me!"
[1] N. Linial, Y. Mansour e N. Nisan. [1993] "Circuitos de profundidade constante, transformada de Fourier e capacidade de aprendizado", Journal of the ACM 40 (3): 607-620.
[2] M. Kharitonov. [1993] "Dureza criptográfica da aprendizagem específica da distribuição", Proceedings of ACM STOC'93, pp. 372-381.
De fato, há 6 anos, Scott Aaronson colocou o aprendizado de como um de seus dez semi-grandes desafios para a teoria da computação quântica .
Questão
Minha pergunta é tripla:
1) Existem exemplos de famílias de funções naturais que os computadores quânticos podem aprender mais rápido do que os computadores clássicos, dadas as suposições criptográficas?
2) Houve algum progresso na aprendizagem de em particular? (ou o T C 0 ligeiramente mais ambicioso )
3) No que diz respeito à capacidade de aprendizado de , Aaronson comenta: "os computadores quânticos teriam uma enorme vantagem sobre os computadores clássicos na aprendizagem de pesos próximos ao ideal para redes neurais". Alguém pode fornecer uma referência sobre como a atualização de peso para redes neurais e circuitos T C 0 se relaciona? (além do fato de que portas limiar parecer neurônios sigmóide) (Esta pergunta foi feita e respondida já )
fonte