Die Matrixmultiplikation ist in der Anzahl der Matrixelemente polynomisch.Bei der Quantenberechnung ist die Anzahl der Matrixelemente im Wesentlichen die Anzahl der Elemente im Quantenzustandsvektor, die in der Größe der Eingabe (der Anzahl der Qubits) exponentiell ist.

Der falsche Punkt in der Prämisse ist, dass eine Zusammensetzung von Einzel-Qubit- und Zwei-Qubit-Gates durch eine Art Zusammensetzung von 2 × 2- und 4 × 4-Matrizen dargestellt wird. Wenn ein Single-Qubit-Gate (für zwei Qubits ist dies ähnlich) auf das $ i $ -te Qubit von $ n $ einwirkt, muss die Matrix in umgewandelt werden $$ (Id_2) ^ {\ otimes (i-1)} \ otimes A \ otimes (Id_2) ^ {\ otimes (n-i)}, $$ Dabei ist $ A $ die ursprüngliche $ 2 × 2 $ -Matrix, um ihre Wirkung auf den $ n $ -Qubit-Zustand zu beschreiben. Dies ist eine Matrix mit den Dimensionen $ 2 ^ n × 2 ^ n $, unabhängig vom Typ des Gates.

Während das Tensorprodukt mit Identitäten trivial aussieht, erinnern wir uns einfach daran, was es für eine Anwendung auf einen Zustandsvektor mit dem einfachsten Algorithmus bedeutet:

  für jeden Index u, 0 ≤ u < 2 ^ n:
  definiere u_i = Bitwert des i-ten Bits von u
  definiere v = u XOR 2 ^ i
  wenn u_i = 0:
    neu (psi [u], psi [v]) = a * psi [u] + b * psi [v]
  sonst:
    neu (psi [u], psi [v]) = d * psi [u] + c * psi [v]
 

Ja, im Kern dieses Pseudo-Algorithmus gibt es nur eine zweidimensionale Multiplikation. Aber es wird $ 2 ^ n $ mal gemacht.

Noch bevor man die eigentliche klassische Simulation ausführen kann, kann der verfügbare Speicher knapp werden, selbst wenn der Zustand zu einem bestimmten Zeitpunkt gespeichert wird. Nehmen Sie $ n = 100 $ Qubits, das sind $ 2 ^ {100} $ komplexe Amplituden mit doppelter Genauigkeit (jeweils 128 Bit). Ich erhalte eine Schätzung, die die Datenspeicherkapazität aller Computer auf der Erde um etwa 14 Größenordnungen übersteigt, sodass wir das nicht so bald sehen werden. In der Zwischenzeit würde ein Quantencomputer mit 100 Bit für Anwendungen gerade erst interessant werden. Theoretisch ist es nicht ungewöhnlich, viel mehr als das vorgesehene zu sehen.

Um es etwas anders auszudrücken: Der Hilbert-Raum (H) für Ihre Quantenschaltung wächst exponentiell ($ \ text {dim H} = 2 ^ n $), wobei n die Anzahl der Qubits ist.Es gibt eine Klasse von Quantenschaltungen, die in Polynomzeit implementiert werden können, aber sie erfordern, dass die Gatter in der Quantenschaltung auf die Pauli-Gruppe und / oder den Normalisierer der Pauli-Gruppe beschränkt sind (Gottesman-Knill-Theorem).Dies schränkt auch ein, welche Art von Fehlermodellen man in der Quantenschaltung verwendet.Der Hauptgrund ist, dass es einen Isomorphismus gibt, den man zwischen der Pauli-Gruppe und dem Vektorraum über dem endlichen Feld mit Elementen definieren kann.Die Multiplikation der Pauli-Gruppenelemente wird zu einem symplektischen Produkt der Vektorraumelemente.

Weil die Matrizen größer sind als Sie denken.

Betrachten Sie eine einfache Schaltung mit 8 Qubits. vielleicht eine Fourier-Transformation. Es werden ~ 40 Gates verwendet, und jedes Gate multipliziert den 8-Qubit-Systemzustandsvektor mit einer Matrix. Dieses System klassisch simulieren. Sie könnten erwarten, dass wir so etwas wie $ 40 \ cdot 8 = 320 $ willkürliche Einheiten der Computerarbeit (AUCW) investieren müssen.

Der Systemzustandsvektor hat jedoch eine Amplitude für jeden möglichen klassischen Zustand des Systems. Acht Bits können $ 2 ^ 8 = 256 $ mögliche Werte zugewiesen werden, daher muss unser Zustandsvektor 256 Einträge haben, nicht acht oder sechzehn. Dementsprechend muss eine Matrix, die dieses System transformiert, die Größe $ 256 \ mal 256 $ haben, obwohl nur $ 256 $ eine viel bessere grobe Schätzung der "Arbeitsgröße" ist, da die Matrix eines einzelnen Gates spärlich ist. Unsere Vermutung von $ 40 \ cdot 8 = 320 $ AUCW war weit entfernt! Eine viel bessere Vermutung ist $ 40 \ cdot 2 ^ 8 = 40 \ cdot 256 = 10240 $. Also $ 10 $ kiloAUCW.

Dieses Problem wird viel viel schlimmer, wenn die Anzahl der Qubits größer wird. Mit 50 Qubits hat der Zustandsvektor $ 2 ^ {50} $ Einträge, die Matrizen sind $ 2 ^ {50} \ mal 2 ^ {50} $, die Fourier-Transformation verwendet ~ 1250 Gates und wir müssen eine Million ausgeben Millionen million AUCWs für die klassische Simulation. Während der Quantencomputer nur 1250 AUQW leistet.