Quantenalgorithmus für lineare Gleichungssysteme (HHL09): Schritt 1 - Anzahl der benötigten Qubits

8

Dies ist eine Fortsetzung des Quantenalgorithmus für lineare Gleichungssysteme (HHL09): Schritt 1 - Verwirrung hinsichtlich der Verwendung des Phasenschätzungsalgorithmus

Fragen (Forts.):

Teil 2: Ich bin mir nicht ganz sicher, wie viele Qubits für Schritt 1 des HHL09 benötigt werden .

In Nielsen und Chuang (Abschnitt 5.2.1, Ausgabe zum 10-jährigen Jubiläum) heißt es:

Um erfolgreich zu erhalten, das auf Bits mit einer Erfolgswahrscheinlichkeit von mindestens genau ist, wählen wirφn1ϵ

t=n+log(2+12ϵ)

Nehmen wir also an, wir wollen eine Genauigkeit von dh und eine Genauigkeit von Bit für oder wir würden brauchen90%1ϵ=0.9ϵ=0.13λjt2πλj

t=3+log2(2+12(0.1))=3+3=6

Abgesehen davon, da als eine Summe von linear unabhängigen Eigenvektoren einer dimensionalen Matrix , würden wir minimale Qubits , um a zu erzeugen Vektorraum mit mindestens - Dimensionen. Wir brauchen also für das zweite Register.N N × N A log 2 ( N ) N log 2 ( N ) |bNN×NAlog2(N)Nlog2(N)

Für das erste Register nicht nur Qubits aus , um die Eigenwerte , sondern wir benötigen mehr Bits für die Darstellung der einzelnen genau bis zu Bit. N | λ j| λ jnlog2(N)N|λj|λjn

Ich denke, wir sollten in diesem Fall wieder die Formel . Wenn jeder Eigenwert mit einer Genauigkeit von Bit und einer Genauigkeit von benötigen wir für das erste Register . Plus, noch ein Qubit, das für die Ancilla benötigt wird.| λi390%6×log2(N)

n+log(2+12ϵ)
|λi390%6×log2(N)

Wir sollten also insgesamt Qubits für Schritt 1 des HHL09-Algorithmus benötigen . Das ist ziemlich viel!(6+1)log2(N)+1

Angenommen, wir möchten ein lineares Gleichungssystem so lösen, dass ist und selbst Qubits benötigt! Falls nicht hermitisch ist, brauchen wir noch mehr Qubits. Habe ich recht?A 7 log 2 ( 2 ) + 1 = 8 A.2×2A7log2(2)+1=8A

In diesem [ ] -Papier auf Seite 6 behaupten sie jedoch, dass sie den HHL09-Algorithmus verwendet haben , um die Pseudoinverse von einer Größe von ~ zu schätzen . In diesem Papier,200 × 200 A.A200×200A definiert als:

A:=(WγIdPP0)

wobei , und alle Matrizen sind.W I d d × dPWIdd×d

Geben Sie hier die Bildbeschreibung ein

In der H1N1-bezogenen Simulation von Lloyd et al. haben behauptet gemacht zu haben, . Und sie behaupten weiter, dass sie den HHL09-Algorithmus verwendet haben , um die Pseudo-Inverse von (die die Größe ) zu schätzen . Das würde mindestens Qubits , um zu simulieren. Ich habe keine Ahnung, wie sie das möglicherweise mit den aktuellen Quantencomputern oder Quantencomputersimulationen tun könnten. Soweit ich weiß, unterstützt IBM Q Experience derzeit ~ Qubits (auch das ist nicht so vielseitig wie ihreA 200 × 200 7 log 2 ( 200 ) + 1 = 7 ( 8 ) + 1 = 57 15 5d=100A200×2007log2(200)+1=7(8)+1=57155 Qubit-Version).

Vermisse ich hier etwas? Benötigt dieser Schritt 1 tatsächlich weniger Qubits als ich geschätzt habe?

[ ]: Ein Quanten-Hopfield-Neuronales Netzwerk Lloyd et al. (2018)

Sanchayan Dutta
quelle
@Nelimee Diese stammt aus der Formel . Es gibt die Anzahl der Qubits im "ersten Register" an, die erforderlich sind, um jedes oder mit einer Genauigkeit von Bits und einer Genauigkeit von darzustellen . t = 3 + log 2 ( 2 + 16| λj| λjtt=3+log2(2+12(0.1))=3+3=6|λj390%|λjt2π390%
Sanchayan Dutta
Obwohl meine Antwort jetzt vielleicht trivial aussieht, habe ich tatsächlich gut drei Tage gebraucht, um alles herauszufinden, da unter anderem die Papiere nicht klar waren. Ich glaube, ich habe jetzt die richtige Anzahl von Qubits, und die resultierende Anzahl macht deutlich, warum die Autoren dieses H1N1-Papiers die erforderliche Anzahl von Qubits leicht simulieren konnten (zumindest für "Schritt 1").
user1271772

Antworten:

2

Die Berechnung der Umkehrung einer Matrix kann durch Anwenden von HHL mit verschiedenen (insbesondere wird HHL mal angewendet , einmal für jeden als verwendeten Berechnungsbasisvektor ).N b i N b iN×NNbiNbi

In jedem Fall muss eine Phasenschätzung für eine Matrix durchgeführt werden.N×N

Die Anzahl der für die Phasenschätzung erforderlichen Qubits ist auf Seite 249 der 10-jährigen Jubiläumsausgabe von N & C angegeben:

"Das Quantenphasenschätzungsverfahren verwendet zwei Register. Das erste Register enthält Qubits."t

"Das zweite Register [...] enthält so viele Qubits, wie zum Speichern von erforderlich sind ", wobei ein dimensionaler Vektor ist.| u N|u|uN

Sie haben also Recht, dass wir Qubits für das erste Register und Qubits für das zweite Register benötigen würden .log N = 86logN=8

Dies sind insgesamt 14 Qubits, um den Phasen-Esitmationsteil jeder HHL-Iteration durchzuführen, die an der Berechnung der Inversen einer Matrix beteiligt ist. 14 Qubits gehören zu den Fähigkeiten eines Laptops.

user1271772
quelle
Ich habe nicht viel Erfahrung mit Simulationen, außer ein bisschen mit der IBM Quantum Experience zu spielen. Was würden Sie zur Simulation von 14 Qubits verwenden? Bis jetzt habe ich das Schaltungsmodell für mehr als Matrizen noch nie gesehen . Die Hamilton-Simulation scheint der schwierigste Teil von HHL zu sein. 4×4
Sanchayan Dutta
In Ihrem Kommentar werden zwei verschiedene Bedeutungen von "Simulation" verwendet. „Hamilton - Simulation“ ist ein Teil der HHL, die mit Qubits durchgeführt wird, zum Beispiel in Abschnitt 4.2 dieses . "Was würden Sie für die Simulation von 14 Qubits verwenden?" Bezieht sich jedoch auf eine andere Art der Simulation, bei der keine Qubits, sondern klassische Bits verwendet werden. Dies haben die Autoren des H1N1-Papiers getan. Sie generierten die -Matrizen (wahrscheinlich in MATLAB mit der KRON-Funktion, die Tensorprodukte 214×214
ausführt
Ja, mir ist bewusst, dass die Hamilton-Simulation ein Teil von HHL ist. Ich habe mich jedoch gefragt, ob sie einen tatsächlichen Quantencomputer wie die IBM 16-Qubit- oder IBM 20-Qubit-Version verwenden. Diese KRON-Funktion in MATLAB klingt zwar interessant (ist aber klassisch), aber ich habe über die Möglichkeit nachgedacht, sie in der IBM 16-Qubit-Funktion (die leider nicht über alle erforderlichen Gates verfügt) auszuführen, und daher würden wir dies tun müssen die Tore approximieren (ich bin nicht ganz sicher, wie).
Sanchayan Dutta
Darüber hinaus denke ich, dass es ein weiteres Problem bei Ihrer Schätzung der Anzahl der Qubits gibt: "Hier kommt das Problem von der festen Genauigkeit gegenüber der nicht festen Dimension N. Da er eine feste Genauigkeit hat, reichen (oder ) Qubits aus, um zu codieren die Eigenwerte auf die gegebene Genauigkeit, aber er könnte mehr als (oder ) Eigenwerte haben "(siehe die diesbezügliche Diskussion im Chat). 6 2 3 2 6362326
Sanchayan Dutta
Wenn sie IBM verwenden würden, würde dies in der Zeitung angegeben. Wenn Sie nach "IBM" suchen, wird nichts angezeigt. Wenn Sie mehr Artikel lesen und mehr Erfahrung sammeln, wird es für Sie immer offensichtlicher, wenn jemand einen Quantencomputer verwendet oder nur einen simuliert hat. Hier simulierten sie es auf einem klassischen Computer (vielleicht mit MATLAB). Was das "Problem bei meiner Einschätzung der Anzahl der Qubits" betrifft, kann ich das Problem leider nicht verstehen. Ich habe gerade die Anzahl der Qubits angegeben, die für die Phasenschätzung einer 200 x 200-Matrix erforderlich sind. N & C sagen, es ist t Qubits für Register 1 und log_2 (N) für Register 2.
Benutzer1271772