NTT-Wissenschaftler sagen, dass sie eine neue Möglichkeit haben, den Quantenvorteil zu verifizieren

Sunnyvale, Kalifornien – 26. Oktober 2022 – NTT Research gab bekannt, dass ein Wissenschaftler aus seinem Labor für Kryptografie und Informationssicherheit (CIS). und ein Kollege von der NTT Sozialinformatik-Labors (SIL) haben ein bahnbrechendes Papier zum Thema Quantenvorteil geschrieben. Das Papier wurde ausgewählt, um auf dem jährlichen IEEE Symposium on Foundations of Computer Science (FOCS) präsentiert zu werden, das vom 31. Oktober bis 3. November stattfindet. XNUMX in Denver.

Die Co-Autoren des Artikels mit dem Titel „Nachweisbarer Quantenvorteil ohne Struktur“, sind Dr. Takashi Yamakawa, angesehener Forscher bei NTT SIL, und Dr. Mark Zhandry, leitender Wissenschaftler in der NTT-Forschung CIS-Labor. Die Arbeit wurde teilweise an der Princeton University durchgeführt, wo Dr. Yamakawa Gastwissenschaftler war und Dr. Zhandry auch als Assistenzprofessor für Informatik tätig ist. 

Das Thema Quantenvorteil (oder Quantenbeschleunigung) bezieht sich auf die Arten von Problemen, die Quantencomputer schneller lösen können als klassische oder Nicht-Quantencomputer, und wie viel schneller sie sind. Die fraglichen Probleme werden üblicherweise als nicht deterministische Polynomzeit (NP)-Klasse beschrieben. Wie viel Vorteil kann sehr unterschiedlich sein. Ein Quantencomputer kann ein bestimmtes Problem möglicherweise in einer Minute oder einer Sekunde lösen, für die ein klassischer Computer eine Woche oder möglicherweise eine unvorstellbar exponentielle Zeit benötigt. In diesem Beitrag stellen sich die Autoren der Herausforderung, diese Überlegenheit effizient nachzuweisen. Bis heute beinhalteten Demonstrationen des Quantenvorteils eine erhebliche „Struktur“ oder Hin- und Her-Kommunikation zwischen zwei oder mehr Parteien. Der Durchbruch des Artikels von Yamakawa und Zhandry besteht darin, ein NP-schweres Problem zu demonstrieren, bei dem eine Verifikation ohne Struktur möglich ist.

"Dies ist das erste Mal, dass wir eine exponentielle Quantenbeschleunigung für ein NP-Suchproblem sehen, das nur ein zufälliges Orakel erfordert", sagte Dr. Scott Aaronson, Professor für Informatik an der Universität von Texas in Austin, der eine frühe Version kommentierte des Papers während eines Workshops am 13. Juni 2022 am Simons Institute for the Theory of Computing. Indem Yamakawa und Zhandry nur ein zufälliges Orakel benötigten, dh eine theoretische Blackbox, die zufällige Antworten auf jede Abfrage generiert, bauten Yamakawa und Zhandry ihr Problem auf unstrukturierten rechnerischen Annahmen auf. Als solches entspricht ihr Problem eher Einwegfunktionen als strukturierten, wie sie in der Public-Key-Kryptographie zu finden sind. Diese Ausrichtung in eine Richtung erleichtert eine effiziente Überprüfung.

„Es ist aufregend zu sehen, wie mit NTT verbundene Kryptografen an einer Forschung zusammenarbeiten, die erneut das Label „Durchbruch“ verdient, insbesondere in einem Papier, das unser Verständnis von Quantencomputern bereichert, einem weiteren Schwerpunktbereich für uns bei NTT Research“, sagte Kazuhiro Gomi , Präsident und CEO von NTT Research. „Herzlichen Glückwunsch und die besten Wünsche an alle Teilnehmer dieser renommierten IEEE-Konferenz.“ 

Das NP-Suchproblem, das Yamakawa und Zhandry entwickelt haben, war ein Zwei-in-Eins-Problem, bei dem 1) eine n-Symbol-Kette, die ein Codewort eines gegebenen Fehlerkorrekturcodes ist, und 2) eine n-Symbol-Kette gefunden werden muss, wo jeweils Das Symbol wird unter dem zufälligen Orakel auf Null abgebildet. Jedes Problem separat ist einfach. Aber eine einzelne Zeichenfolge zu finden, die sowohl ein Codewort ist als auch auf Null abgebildet wird, ist viel schwieriger, zumindest klassisch. „Wenn Sie Quanten sind, können Sie das in Polynomialzeit lösen“, sagte Dr. Zhandry, „aber wenn Sie klassisch sind, brauchen Sie zumindest in diesem Black-Box-Modell Exponentialzeit.“ Andererseits ist es einfach, eine mögliche Lösung zu verifizieren, indem überprüft wird, ob sie jedes der beiden Probleme separat löst. Beachten Sie, dass diese Arbeit, wie es sich für ein Papier für FOCS gehört, grundlegend oder grundlegend ist. Wie in Dr. Aaronsons Vortrag am Simons Institute (diskutiert in diesem NTT Research Blog-Artikel) fällt das Yamakawa-Zhandry-Argument in eine Klasse von Beschleunigungen, die mathematisch leicht überprüft, aber in absehbarer Zeit nicht durch einen tatsächlichen Quantencomputer praktisch demonstriert werden können. Abgesehen von seinem bahnbrechenden Verifikationsschema weist das Papier jedoch auch auf etwas Neues hin, was das Ausmaß der Quantenbeschleunigung betrifft.

„Vor unserer Arbeit hatten wir Beispiele für Quantenvorteile bei NP-Problemen, wie Faktorisierung oder, in der Black-Box-Umgebung, Periodenfindung. Aber es stellt sich heraus, dass der Quantenalgorithmus, der all diesen Beispielen zugrunde liegt, im Wesentlichen Periodenfindung war – obwohl es oft nicht trivial war, zu zeigen, wie Periodenfindung auf diese Beispiele angewendet werden kann“, sagte Dr. Zhandry. „Unser Papier zeigt, dass es mindestens einen zweiten Fall gibt. Man könnte das optimistisch so interpretieren, dass es Hoffnung gibt, dass der Quantenvorteil weiter verbreitet ist, als wir vielleicht bisher dachten.“

Die vom IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) gesponserte FOCS ist eine führende Konferenz auf dem Gebiet der theoretischen Informatik. Der Aufruf zur Einreichung von Beiträgen für FOCS 2022, das 63. derartige jährliche Treffen, führte Quantencomputing als eines von 17 allgemeinen Interessengebieten auf. Das Papier von Yamakawa-Zhandry soll am 31. Oktober 2022 um 10:15 Uhr MT präsentiert werden. Um mehr über diese Veranstaltung zu erfahren und sich dafür anzumelden, besuchen Sie die BAZL 2022 Webseite.