Reale Anwendungen des Quantencomputers (außer für Sicherheitszwecke)

17

Nehmen wir an, wir haben einen universellen Quantencomputer gebaut.

Abgesehen von sicherheitsrelevanten Problemen (Kryptografie, Datenschutz, ...), welche aktuellen Probleme der realen Welt können davon profitieren?

Ich interessiere mich für beides:

  • Probleme, die derzeit für einen praktischen Einstieg nicht lösbar sind,
  • Probleme, die derzeit gelöst werden, aber eine erhebliche Beschleunigung würde ihre Benutzerfreundlichkeit erheblich verbessern.
Piotr Migdal
quelle
8
Vielleicht dies hilft.
Aelguindy
Im IIRC stellte sich die Frage, mit welchen Quantencomputern effizient gerechnet werden kann. Vielleicht möchten Sie einen Blick darauf werfen.
Kaveh
Ist das hilfreich?
Kaveh
1
@ Kevah: Nicht viel, um ehrlich zu sein. Der Schwerpunkt meiner Frage liegt auf den realen Anwendungen (also nicht nur dort, wo es eine Beschleunigung für einen bestimmten Algorithmus gibt, sondern wenn eine Beschleunigung ein bestimmtes praktisches Problem löst).
Piotr Migdal
1
Konstruktion eines optimalen phylogenetischen Baumes .
Saeed,

Antworten:

17

Quantenmechanik effizient simulieren.

Tyson Williams
quelle
Dies ist die Antwort auf std / folklore / ironic / glib / near-joke & ich frage mich, wer sie stammt. Hat jemand eine aktuelle Referenz? Ich frage es als nicht nec trivial wie folgt möglich. qm computing konzentriert sich hauptsächlich auf paarweise Qubit-Interaktionen (Gates). um zu beweisen, dass man QM generell effizient simulieren kann, müsste man anscheinend zeigen, dass man alle möglichen n-weise Wechselwirkungen mit paarweisen Wechselwirkungen effizient simulieren kann . habe dies nicht in einem Papier nachgewiesen gesehen.
vzn
2
@vzn: Bei den meisten physikalischen Wechselwirkungen ist die Beschränkung auf 2-Teilchen-Wechselwirkungen eine gute Annäherung, die für Simulationen, die nur auf lokalen 2-Körper-Wechselwirkungen basieren, sinnvoll ist (Wechselwirkungen mit mehreren Begriffen klingen normalerweise sehr schnell ab). Das Vorhandensein allgemeiner n-Körper-Wechselwirkungen macht die Simulationsidee also nicht ungültig.
Marcin Kotowski
@vzn Ich habe keine Referenz auf Papier, aber Scott Aaronson sagt dies und erwähnte es in seinem kürzlich erschienenen Artikel in der Times .
Tyson Williams
2
@vzn, dies war die ursprüngliche Anwendung, als Richard Feynman das Quantencomputing konzipierte. Dies ist der Link zu dem Artikel, in dem er die Idee von Quantencomputern vorschlug ( springerlink.com/content/t2x8115127841630 ). Sie können dies auch überprüfen ( wisdom.weizmann.ac.il/~naor/COURSE/feynman-simulating.pdf) )
Marcos Villagra
1
@vzn Die Antwort ist gültig, aber die Literatur zur digitalen Quantensimulation ist durchaus ausreichend, um sie nur durch Kommentare zusammenzufassen. Ich würde empfehlen, eine neue Diskussion zu eröffnen, da das Thema interessant ist.
Juan Bermejo Vega
8

Brassard, Hoyer, Mosca und Tapp haben gezeigt, dass die verallgemeinerte Grover-Suche, Amplitudenverstärkung genannt, verwendet werden kann, um eine quadratische Beschleunigung für eine große Klasse klassischer Heuristiken zu erzielen. Die Intuition hinter ihrer Idee ist, dass klassische Heuristiken die Zufälligkeit verwenden, um nach einer Lösung für ein bestimmtes Problem zu suchen, sodass wir die Amplitudenverstärkung verwenden können, um den Satz zufälliger Zeichenfolgen nach einer zu durchsuchen, mit der die Heuristik eine gute Lösung findet. Dies ergibt eine quadratische Beschleunigung in der Laufzeit des Algorithmus. Weitere Informationen finden Sie in Abschnitt 3 des oben verlinkten Dokuments.

Philippe Lamontagne
quelle
8

Quantensysteme simulieren!

Mir ist aufgefallen, dass in der anderen Antwort, die dies erwähnte, mehrere Kommentare darüber eingingen, ob dies wahr ist, da es sich um eine nicht offensichtliche Behauptung handelt. Und die Leute baten um Referenzen. Hier einige Referenzen.

Ursprünglicher Vorschlag von Feynman:

Feynman, R .: Physik mit Computern simulieren. Int. J. Theor. Phys. 21 (6) (1982) 467–488

Effiziente Algorithmen für alle von "lokalen" Hamiltonianern definierten Quantensysteme. (Lloyd erklärt auch, dass sich jedes System, das mit der speziellen und allgemeinen Relativitätstheorie vereinbar ist, entsprechend den lokalen Interaktionen entwickelt.)

Lloyd, S .: Universelle Quantensimulatoren. Science 273 (5278) (1996) 1073–1078

Weitere Verallgemeinerung auf spärliche Hamiltonianer, die allgemeiner sind als lokale Hamiltonianer:

Aharonov, D., Ta-Shma, A .: Adiabatische Quantenzustandserzeugung und statistisches Nullwissen. In: Proc. 35th STOC, ACM (2003) 20–29

Weitere Lektüre:

Berry, D., Ahokas, G., Cleve, R., Sanders, B.: Effiziente Quantenalgorithmen zur Simulation von spärlichen Hamiltonianern. Kommun. Mathematik. Phys. 270 (2) (2007) 359–371

Childs, AM: Quanteninformationsverarbeitung in kontinuierlicher Zeit. Doktorarbeit, Massachusetts Institute of Technology (2004)

Robin Kothari
quelle
2

Das Sehen ist auf diesem Gebiet sowohl gefährlich als auch polemisch, daher sollten wir mit diesem Thema vorsichtig sein. Einige Q-Algorithmen mit polynomieller Beschleunigung bieten jedoch interessante Anwendungsmöglichkeiten.

Es ist bekannt, dass die Grover-Suche verwendet werden kann, um die Lösung von NP-vollständigen Problemen polynomiell zu erfassen [1] . Dies ist für 3-SAT in [2] bewiesen . Einige Anwendungen von SAT, die aus [3] entlehnt wurden , sind: Prüfung der Schaltungsäquivalenz , automatische Testmustererzeugung , Modellprüfung mit linearer Zeitlogik , Planung in künstlicher Intelligenz und Haplotypisierung in der Bioinformatik . Obwohl ich nicht viel über diese Themen weiß, erscheint mir diese Forschungsrichtung eher praktisch.

Es gibt auch einen Quantenalgorithmus zur Auswertung von NAND-Bäumen mit einer polynomiellen Beschleunigung gegenüber der klassischen Berechnung [ 8 , 10 , 11 ]. Der NAND-Baum ist ein Beispiel für einen Spielbaum, eine allgemeinere Datenstruktur, mit der Spiele von Brettspielen wie Schach und Go untersucht werden. Es klingt plausibel, dass diese Art der Beschleunigung verwendet werden könnte, um leistungsstärkere Software-Spieler zu entwickeln. Könnte dies einige Entwickler von Quantenvideospielen interessieren?

Leider ist das Spielen in der Realität nicht dasselbe wie das Bewerten von Bäumen: Es gibt Komplikationen, z. B. wenn Ihre Spieler keine optimalen Strategien verwenden [ 12 ]. Ich habe keine Studie über ein reales Szenario gesehen, daher ist es schwer zu sagen, wie vorteilhaft die Beschleunigung von [ 8 ] in der Praxis ist. Dies könnte ein gutes Diskussionsthema sein.

Juan Bermejo Vega
quelle
1
Bitte nehmen Sie meine Einladung zur Teilnahme an: quantumcomputing.stackexchange.com .
Rob
-6

Ich glaube, Sie haben eine ausgezeichnete Frage an den Grenzen der QM-Forschung aufgeworfen (was zum Teil daran liegt, dass Sie bisher keine Antworten gefunden haben), aber sie wurde nicht vollständig formal definiert oder als Problem erfasst. Die Frage lautet: "Was genau können QM-Algorithmen überhaupt effizient berechnen?" und eine vollständige Antwort ist nicht bekannt und wird aktiv verfolgt. Ein Teil davon hängt mit der (offenen) Komplexität von QM-bezogenen Klassen zusammen.

dies wäre der Fall, wenn eine etwas formale Frage definiert wäre. Wenn gezeigt werden kann, dass die QM-Klassen "erheblich leistungsfähigen" Nicht-QM-Klassen entsprechen, gibt es Ihre Antwort. Das allgemeine Thema dieses Ergebnistyps wäre eine "nicht so hart in QM" -Klasse, die einer "hart in Nicht-QM" -Klasse entspricht. Es gibt verschiedene offene Komplexitätsklassen-Trennungen dieses Typs (möglicherweise kann jemand anderes sie detaillierter vorschlagen).

Etwas Merkwürdiges am aktuellen QM-Wissen über Quantenalgorithmen ist, dass es eine Art seltsame Sammlung von Algorithmen gibt, von denen bekannt ist, dass sie in QM funktionieren, die jedoch anscheinend nicht viel Kohärenz / Kohäsion mit ihnen aufweisen. Sie wirken seltsam und irgendwie unzusammenhängend. Es gibt keine offensichtliche "Faustregel" für "Probleme, die im QM berechenbar sind, sind im Allgemeinen in dieser Form", trotz einer vernünftigen Erwartung, dass man dort sein könnte.

Vergleichen Sie dies zum Beispiel mit der Theorie der NP-Vollständigkeit, die im Vergleich viel schlüssiger ist. Es scheint, als würde die QM-Theorie, wenn sie besser entwickelt wäre, ein größeres Kohäsionsgefühl erhalten, das an die NP-Vollständigkeitstheorie erinnert.

Eine stärkere Idee könnte sein, dass irgendwann, wenn die QM-Komplexitätstheorie besser ausgearbeitet wird, die NP-Vollständigkeit "ordentlich" hineinpasst.

Für mich scheint die allgemeinste QM-Beschleunigung oder allgemein anwendbare Strategie, die ich gesehen habe, der Grovers-Algorithmus zu sein, weil so viel praktische Software mit Datenbankabfragen zusammenhängt. und in gewisser Weise zunehmend "unstrukturierte":

Ö(N)Ω(N)

vzn
quelle
3
"Die QM-Komplexitätstheorie ist besser ausgearbeitet, die NP-Vollständigkeit wird irgendwie" ordentlich "hineinpassen." Es gibt eine gut entwickelte Theorie für quanteninteraktive Beweissysteme (Komplexitätsklassen wie QMA usw.), die klassische Komplexitätsklassen wie NP, PSPACE usw. verallgemeinern. In diesem Sinne passt die NP-Vollständigkeit genau in die Theorie der Quantenkomplexität. (Andererseits stimme ich zu, dass das Gebiet der Quantenalgorithmen keine Kohäsion aufweist, aber Quantenalgorithmen und Quantenkomplexität unterschiedliche Teilfelder sind).
Marcin Kotowski
Ich bin mir einig, dass es gut definierte QM-Klassen und -Hierarchien gibt, die Nicht-QM-Klassen widerspiegeln, aber ihre Beziehung zu (Macht in Bezug auf) "klassischen" Nicht-QM-Klassen und insbesondere NP ist, wie bereits erwähnt, weitgehend offen.
vzn
1
Was meinen Sie mit "zunehmend unstrukturierten Datenbanken"? Eine Datenbank sieht per Definition nach etwas Ordnungsgemäßem aus.
Juan Bermejo Vega