Quanten-PAC-Lernen

Hintergrund

Funktionen in sind PAC, die in quasipolynomialer Zeit mit einem klassischen Algorithmus lernbar sind, der zufällig ausgewählte O ( 2 l o g ( n ) O ( d ) ) -Anfragen benötigt, um eine Schaltung mit der Tiefe d [1] zu lernen. Wenn es kein 2 n o ( 1 ) Faktorisierungsalgorithmus dann dies ist dies optimal [2]. Natürlich wissen wir auf einem Quantencomputer, wie man faktorisiert, daher hilft diese Untergrenze nicht. Ferner verwendet der optimale klassische Algorithmus das Fourier-Spektrum der Funktion und schreit so "Quantisiere mich!"$AC^0$$O(2^{log(n)^{O(d)}})$$2^{n^{o(1)}}$

[1] N. Linial, Y. Mansour und N. Nisan. [1993] "Schaltungen mit konstanter Tiefe, Fouriertransformation und Lernfähigkeit", Journal of the ACM 40 (3): 607-620.

[2] M. Kharitonov. [1993] "Cryptographic Hardness of Distribution-Specific Learning", Proceedings of ACM STOC'93, S. 372-381.

Tatsächlich hat Scott Aaronson vor 6 Jahren die Lernfähigkeit von als eine seiner zehn semi-großartigen Herausforderungen für die Quantencomputertheorie definiert .$AC^0$

Frage

Meine Frage ist dreifach:

1) Gibt es Beispiele für natürliche Funktionsfamilien, die Quantencomputer unter kryptografischen Voraussetzungen schneller lernen können als klassische Computer?

2) Gab es insbesondere Fortschritte in Bezug auf die Lernfähigkeit von ? (oder das etwas ehrgeizigere T C 0 )$AC^0$$TC^0$

3) In Bezug auf die Lernfähigkeit von kommentiert Aaronson: "Dann hätten Quantencomputer einen enormen Vorteil gegenüber klassischen Computern, wenn sie nahezu optimale Gewichte für neuronale Netze lernen." Kann jemand eine Referenz darüber liefern, wie sich die Gewichtsaktualisierung für neuronale Netze und T C 0 -Schaltungen verhält? (Abgesehen davon, dass Schwellwerttore wie Sigmoidneuronen aussehen)$TC^0$$TC^0$ (Diese Frage wurde bereits gestellt und beantwortet. )

Ich werde einen Versuch bei Ihrer ersten Frage machen:

Gibt es Beispiele für natürliche Funktionsfamilien, die Quantencomputer unter kryptografischen Voraussetzungen schneller lernen können als klassische Computer?

Nun, es hängt vom genauen Modell und der zu minimierenden Ressource ab. Eine Möglichkeit besteht darin, die Komplexität der Stichprobe (für ein verteilungsunabhängiges PAC-Lernen) des klassischen Standardmodells mit einem Quantenmodell zu vergleichen, das mit Quantenstichproben versehen ist (dh statt einer zufälligen Eingabe und des entsprechenden Funktionswerts wird der Algorithmus bereitgestellt) mit einer Quantenüberlagerung über Eingaben und deren Funktionswerten). In dieser Einstellung sind Quanten-PAC-Lernen und klassisches PAC-Lernen grundsätzlich gleichwertig. Die klassische Obergrenze für die Probenkomplexität und die Quantenuntergrenze für die Probenkomplexität sind fast gleich, wie die folgende Abfolge von Arbeiten zeigt:

[1] R. Servedio und S. Gortler, "Äquivalenzen und Trennungen zwischen Quanten- und klassischer Lernfähigkeit", SIAM Journal on Computing, vol. 02138, S. 1–26, 2004.

[2] A. Atici und R. Servedio, „Verbesserte Grenzen für Quantenlernalgorithmen“, Quantum Information Processing, S. 1–18, 2005.

[3] C. Zhang, "Eine verbesserte Untergrenze der Abfragekomplexität für das Quanten-PAC-Lernen", Information Processing Letters, vol. 111, nein. 1, S. 40–45, Dez. 2010.

$O(n^{\log n})$

[4] N. Bshouty und J. Jackson, "Lernen von DNF über die Gleichverteilung unter Verwendung eines Quanten-Beispiel-Orakels", SIAM Journal on Computing, vol. 28, nein. 3, S. 1136–1153, 1998.

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

[6] A. Atıcı und R. Servedio, „Quantenalgorithmen zum Lernen und Testen von Juntas“, Quantum Information Processing, vol. 6, nein. 5, S. 323–348, Sep. 2007.

Wenn Sie sich hingegen nur für das klassische PAC-Standardmodell interessieren, bei dem Quanten-Computing als Nachbearbeitungswerkzeug verwendet wird (dh keine Quanten-Samples), haben Servedio und Gortler [1] festgestellt, dass eine Konzeptklasse fällig ist für Kearns und Valiant, die unter der Annahme der Härte der Faktorisierung von Blum-Ganzzahlen nicht klassisch PAC-gelernt werden können, sondern mit Shors Algorithmus quantitativ PAC-gelernt werden können.

Die Situation für Angluins Modell des exakten Lernens durch Mitgliedschaftsabfragen ist ähnlich. Quantenabfragen können nur eine polynomielle Beschleunigung in Bezug auf die Komplexität von Abfragen bewirken. Es gibt jedoch eine exponentielle Beschleunigung der Zeitkomplexität, wenn man davon ausgeht, dass Einwegfunktionen existieren [1].

Ich habe keine Ahnung von der zweiten Frage. Ich würde auch gerne mehr darüber hören.

Dies ist sicherlich keine vollständige Antwort auf Ihre Frage, hilft aber hoffentlich beim ersten Teil. Es scheint ein großes Interesse an der Verwendung von Quantenalgorithmen zur Identifizierung unbekannter Orakel zu bestehen. Ein Beispiel hierfür ist eine kürzlich erschienene Veröffentlichung von Floess, Andersson und Hillery ( arXiv: 1006.1423 ), die den Bernstein-Vazirani-Algorithmus anpasst, um Boolesche Funktionen zu identifizieren, die nur von einer kleinen Teilmenge der Eingabevariablen (Juntas) abhängen. Sie verwenden diesen Ansatz, um die Orakelfunktion für Polynome niedrigen Grades zu bestimmen (sie befassen sich explizit mit linearen, quadratischen und kubischen Fällen).