Könnte ein Quantencomputer eine lineare Algebra schneller ausführen als ein klassischer Computer?

8

Angenommen, wir hätten einen Quantencomputer mit einer ausreichenden Anzahl von Qubits. Könnten wir damit die lineare Algebra schneller ausführen als mit einem klassischen Computer? Welche Art von Beschleunigung können wir erwarten? Hat jemand einen Quantenalgorithmus für die lineare Algebra erstellt und wie lange läuft er? Theoretisch ist eine Operation wie die Matrix-Matrix-Multiplikation stark parallelisierbar, in der Praxis erfordert sie jedoch viel Arbeit, um eine schnell laufende parallele Matrix-Matrix-Multiplikation zu implementieren. Würde ein Quantencomputer einen praktischen Vorteil bieten?

J. Antonio Perez
quelle

Antworten:

3

Hier sind einige Hinweise:

Yuval Filmus
quelle
Diese Hinweise gehörten übrigens zu den ersten Ergebnissen bei Google.
Yuval Filmus
Ihre Antwort basiert auf Links. Ist das richtig?
Tatsächlich so. Ich gebe zu, dass ich die Zeitungen nicht wirklich gelesen habe.
Yuval Filmus
Es ist okay, mindestens eine Antwort.
1
Ich würde auch Scott Aaronsons Zusammenfassung dieser Algorithmen empfehlen: Quantum Machine Learning-Algorithmen: Lesen Sie das Kleingedruckte
Craig Gidney
1

Mathematisches Modell mit Matrix

Der HHL-Algorithmus befindet sich in den bereits erwähnten Links. Implementieren wir ihn auf einem Quantencomputer. Wir wollen ein lineares Gleichungssystem lösen x > = | b > Von diesem | x > = A - 1 | b >A|x>=|b>|x>=A1|b>

A=[1.50.50.51.5]b=[10]

A1.|b>=[0.750.25]

Quantenschaltungsdesign

Wir verwenden die Quantenschaltung in arXiv 1302.1210 mit 2 Qubits, ein Qubit mit Eingang b. Das zweite Qubit ist ein Ancilla-Bit und eine Eins am Ausgang bedeutet, dass die Ausgabe bereit ist. Geben Sie hier die Bildbeschreibung ein Die Schaltung verwendet eine PEA-Schaltung (Gate R) als Eingang und eine inverse PEA-Schaltung am Ausgang. Die Phasenschätzung oder PEA wird verwendet, um den Quantenzustand von | b> auf einer bestimmten Basis zu zerlegen, und die Eigenwerte von A werden in einem Eigenwertregister gespeichert. Das Rotationstor R (y) transformiert sich mit einem Winkel in Abhängigkeit vom Wert im Eigenwertregister. Dann führen wir eine umgekehrte PEA durch, um den Eigenwert zu berechnen und die Antwort zu finden. Im Quantencomputer kann nur die Möglichkeit gemessen werden, eine 1 oder 0 zu finden.

Gate-Parameter

λ1=1λ2=2θ=2arccosλ1λ2

θ=2arccos(1/2)=2π3

quantumexperience.ng.bluemix.net/qx/editor?codeId=9da9d545772273118671911e1078ac42 Geben Sie hier die Bildbeschreibung ein

Bram
quelle
Das sieht eher aus wie ein Blog-Beitrag. Wie beantwortet es die Frage?
Yuval Filmus
Der erste Teil der Frage zum Algorithmus wurde bereits von den Zeigern mit den Links zum HHL-Algorithmus beantwortet. Der zweite Teil der Frage befasst sich mit dem Kompromiss zwischen Theorie und praktischen Implikationen bei Matrixmultiplikationen. Ich habe das nicht beantwortet, aber zumindest habe ich eine mögliche Implementierung gezeigt und daher etwas zu analysieren und eine Schlussfolgerung zu ziehen.
Bram