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 Nicht-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.