(Sorry für eine etwas amateurhafte Frage)
Ich habe von 2004 bis 2007 Quantencomputer studiert, aber seitdem habe ich den Überblick verloren. Zu der Zeit gab es viel Hype und Gerede darüber, dass QC potenziell alle möglichen Probleme lösen könnte, indem es klassische Computer übertrifft, aber in der Praxis gab es nur zwei theoretische Durchbrüche:
- Shors Algorithmus, der eine signifikante Beschleunigung aufwies, jedoch nur eine eingeschränkte Anwendbarkeit aufwies und außerhalb der ganzzahligen Faktorisierung nicht wirklich nützlich war.
- Grovers Algorithmus, der auf eine breitere Kategorie von Problemen anwendbar war (da er zur Lösung von NP-Complete-Problemen verwendet werden konnte), der jedoch im Vergleich zu klassischen Computern nur eine polynomielle Beschleunigung aufwies.
Auch das Quantenglühen wurde diskutiert, aber es war nicht klar, ob es wirklich besser als das klassische simulierte Glühen war oder nicht. Auch die messungsbasierte Qualitätskontrolle und die grafische Zustandsdarstellung der Qualitätskontrolle waren wichtige Themen, aber auch in dieser Hinsicht konnte keine endgültige Aussage getroffen werden.
Wurden seitdem Fortschritte auf dem Gebiet der Quantenalgorithmen erzielt? Bestimmtes:
- Gab es wirklich bahnbrechende Algorithmen außer denen von Grover und Shor?
- Gab es irgendwelche Fortschritte bei der Definition der Beziehung von BQP zu P, BPP und NP?
- Haben wir Fortschritte beim Verständnis des Wesens der Quantenbeschleunigung erzielt, außer zu sagen, dass "es an der Verstrickung liegen muss"?
quelle
Antworten:
Es kommt darauf an, was Sie mit "wirklich bahnbrechend" meinen. Grovers und Shors sind besonders einzigartig, weil sie wirklich die ersten Instanzen waren, die besonders wertvolle Arten der Beschleunigung mit einem Quantencomputer zeigten (z. B. die vermutete exponentielle Verbesserung für Shor) und Killeranwendungen für bestimmte Communities hatten.
Seitdem wurden einige Quantenalgorithmen entwickelt, und ich denke, drei sind besonders erwähnenswert:
Der BQP-Complete- Algorithmus zur punktuellen Auswertung des Jones-Polynoms . Ich erwähne dies, weil es, abgesehen von offensichtlichen Dingen wie der Hamiltonschen Simulation, meiner Meinung nach der erste BQP-vollständige Algorithmus war, der wirklich die volle Leistung eines Quantencomputers zeigt.
Der HHL-Algorithmus zum Lösen linearer Gleichungen. Dies ist ein wenig lustig, weil es eher wie eine Quanten-Subroutine ist, mit Quanteneingängen und -ausgängen. Es ist jedoch auch BQP-vollständig und erhält aufgrund potenzieller Anwendungen beim maschinellen Lernen und dergleichen im Moment viel Aufmerksamkeit. Ich denke, dies ist der beste Kandidat für einen echten Spatenstich, aber das ist Ansichtssache.
Quantenchemie . Ich weiß sehr wenig darüber, aber die Algorithmen haben sich seit Ihrer Erwähnung erheblich weiterentwickelt, und es wurde immer als eine der nützlichen Anwendungen eines Quantencomputers angeführt.
Im Wesentlichen nein. Wir wissen, dass BQP BPP enthält, und wir kennen die Beziehung zwischen BQP und NP nicht.
Schon als Sie es ursprünglich studierten, würde ich sagen, dass es genauer definiert war. Es gibt (und gab) gute Vergleiche zwischen universellen Gate-Sets (die möglicherweise zu einer exponentiellen Beschleunigung führen können) und klassisch simulierbaren Gate-Sets. Denken Sie zum Beispiel daran, dass die Clifford-Tore Verwicklungen hervorrufen, aber klassisch simulierbar sind. Nicht, dass es einfach ist, auf pädagogischere Weise genau anzugeben, was erforderlich ist.
Möglicherweise wurden in Bezug auf andere Berechnungsmodelle einige Fortschritte erzielt. Zum Beispiel ist das Modell DQC1 besser zu verstehen - dies ist ein Modell, das gegenüber klassischen Algorithmen anscheinend eine gewisse Beschleunigung aufweist, aber wahrscheinlich nicht in der Lage ist, BQP-vollständige Berechnungen durchzuführen (aber bevor Sie sich auf den Hype einlassen, den Sie möglicherweise online finden ( während der Berechnung ist eine Verstrickung vorhanden).
Andererseits ist die Aussage "Es liegt an der Verstrickung" immer noch nicht vollständig geklärt. Ja, für reine Zustandsquantenberechnungen muss es eine gewisse Verschränkung geben, da das System ansonsten leicht zu simulieren ist. Für gemischte trennbare Zustände wissen wir jedoch nicht, ob sie für Berechnungen verwendet werden können oder ob sie effizient simuliert werden können.
Man könnte auch versuchen, eine aufschlussreichere Frage zu stellen: Haben wir Fortschritte gemacht, um zu verstehen, welche Probleme einer Quantenbeschleunigung zugänglich sein werden? Dies ist ein subtiler Unterschied, denn wenn Sie der Meinung sind, dass ein Quantencomputer Ihnen neue Logikgatter bietet, die ein klassischer Computer nicht hat, müssen Sie diese neuen Tore verwenden, um eine Beschleunigung zu erzielen. Es ist jedoch nicht klar, dass jedes Problem mit solchen Vorteilen verbunden ist. Welche sind Es gibt Problemklassen, bei denen man auf eine Beschleunigung hoffen könnte, aber ich denke, das hängt immer noch von der individuellen Intuition ab. Das kann man wohl noch über klassische Algorithmen sagen. Sie haben einen Algorithmus x geschrieben. Gibt es eine bessere klassische Version? Vielleicht nicht, oder vielleicht sehen Sie es einfach nicht. Deshalb wissen wir nicht, ob P = NP ist.
quelle
Der Kerenidis-Prakash-Algorithmus war bahnbrechend, bis Ewin Tang den Grund wieder herstellte:
Quanta Magazine: Große Fortschritte im Bereich Quantum Computing, die von Teenagern überholt wurden .
quelle