Quantenparallelismus

Der Quantenparallelismus ist der Grund für die höhere Rechenleistung eines Quantencomputers gegenüber einem klassischen Computer, da bei der einmaligen Anwendung eines Gatters auf einen Zustand von $n$ Qubits insgesamt $2^n$ Manipulationen durchgeführt werden, im Gegensatz zu lediglich einer Manipulation in einem klassischen Computer.

Ein klassischer Computer verarbeitet Informationen durch Manipulation von Bits mit Gattern. Beispielsweise ergibt die Anwendung eines NOT-Gatters auf die Bitfolge [010111] die Bitfolge [101000].

Quantencomputer machen sich die Superposition von Quantenzuständen zunutze. So befindet sich ein Qubit (vor jeglicher Messung) in einem Superpositionszustand

$|\psi\rangle = a \, |0\rangle + b \, |1\rangle$

mit

$|a|^2 + |b|^2=1$

Die Anwendung einer Gatteroperation (z. B. NOT) auf diesen Zustand ergibt dann

$|\psi'\rangle = a \, |1\rangle + b \, |0\rangle$

Es wurden also bei einmaliger Anwendung von einer Gatteroperation bereits zwei Manipulationen durchgeführt. Führt man das Ganze weiter und betrachtet einen (verschränkten) Zustand zweier Qubits

$|\psi\rangle = a \, |00\rangle + b \, |10\rangle + c \, |01\rangle + d \, |11\rangle$

so ergibt NOT das Ergebnis

$|\psi'\rangle = a \, |11\rangle + b \, |01\rangle + c \, |10\rangle + d \, |00\rangle$

Man sieht also, dass bei der Nutzung zweier Qubits insgesamt vier Manipulationen durch eine einzige Gatteroperation durchgeführt wurden. Verallgemeinert ergibt sich, dass bei der Nutzung von $n$ verschränkten Qubits durch eine Gatteroperation $2^n$ Manipulationen vorgenommen werden.