Quantenschaltung

Mit Quantenschaltung wird in der Quanteninformatik ein abstraktes Modell für Quantencomputer bezeichnet. Die darin stattfindende Berechnung ist eine Folge von Quantengattern, welche reversible Transformationen auf dem quantenmechanischen Gegenstück eines n-Bit Registers durchführt. Diese Register wird hier n-Qubit genannt.

Reversible Logikgatter

Im klassischen Computer sind die Logikgatter mit mehr als einem Eingang (alle außer dem Nicht-Gatter und einem Ausgang nicht reversibel. Beispielsweise kann man für ein Und-Gatter aus dem Ausgangs-Bit 0 nicht ableiten, ob die Eingangswerte 0,1 oder 1,0 oder 0,0 waren. Es ist jedoch auch in einem klassischen Computer theoretisch möglich, für Eingangswerte beliebiger Länge reversible Gatter zu konstruieren. Ein reversibles Gatter ist eine umkehrbare Funktion, die n-Bit auf n-Bit abbildet, wobei das n-Bit-Datum eine Zeichenkette der Länge n mit den Bits x₁,x₂, …,x_n.

Das n-Bit-Datum ist Element der Menge {0,1}ⁿ. Diese enthält 2ⁿ Elemente.

Ein reversibles n-Bit-Gatter ist eine bijektive Abbildung f aus der Menge {0,1}ⁿ von n-Bit-Daten auf sich selbst.

Ein Beispiel für ein derartiges Gatter f ist eine Abbildung, welche das erste Bit verneint.

Aus praktischen Erwägungen werden hier nur Gatter für kleine Werte von n betrachtet, also n = 1, n = 2 oder n = 3. Diese Gatter können leicht als Tabellen beschrieben werden. Ein Beispiel n = 2 ist das kontrollierte Nicht-Gatter, das Toffoli-Gatter und das Fredkin-Gatter.

Für die Betrachtung von Quantengattern muss man die quantenmechanische Ersetzung eines n-Bit-Datums definieren.

Die quantisierte Version eines klassischen n-Bit-Zustandsraums {0,1}ⁿ ist

$H_{\operatorname{QB}(n)}= \ell^2(\{0,1\}^n).$

Dies ist definitionsgemäß der Raum von komplexwertigen Funktionen von {0,1}ⁿ und ist ein Prähilbertraum. Dieser Raum kann auch als Überlagerung von klassischen Bit-Zeichenkeitten betrachtet werden. Man beachte, dass H_QB(n) ein Vektorraum über den komplexen Zahlen der Dimension 2ⁿ ist. Die Elemente dieses Raums werden n-Qubit genannt.

Beschreibt x₁,x₂, …,x_n in der Bra-Ket-Notation die klassische Bit-Zeichenkette, dann ist

$| x_1, x_2, \cdots,x_n \rangle \quad$

ein spezielles n-Qubit korrespondierend zu der Funktion, die die klassische Bit-Zeichenkette auf 1 abbildet und alle anderen Zeichenketten auf 0. Diese 2ⁿ speziellen n-Qubits sind die Berechnungszustandsbasis der Funktion. Alle n-Qubits sind komplexe Linearkombinationen dieser Basis.

Für ein Quantengatter benötigt man eine spezielle Art einer reversiblen Funktion, nämlich eine Unitäre Abbildung. Diese ist eine Abbildung auf H_QB(n), bei der die Inneren Produkte erhalten bleiben.

Ein reversibles n-Qubit Quantengatter ist eine unitäre Abbildung U aus dem Raum H_QB(n) auf sich selbst.

Wiederum ist nur die Unitäre Abbildungen U für kleine n von Interesse. Aus einem reversiblen n-Bit-Gatter f lässt sich ein reversibles n-Bit-Quantengatter W_f bilden, das wie folgt definiert ist:

$W_f( | x_1, x_2, \cdots,x_n \rangle) = |f(x_1, x_2, \cdots, x_n) \rangle.$

Man beachte, das W_f die Berechnungszustandsbasis permutiert.

Von speziellem Interesse ist das 2-Qubit-CNOT-Gatter W_CNOT. Mit diesem Gatter wird deutlich, dass es über die Permutation der Basis hinaus viele weitere Quanten-Gatter gibt. Beispielsweise ist eine Verschiebung der Phase durch Multiplikation mit folgender unitärer Matrix ebenfalls zulässig:

$U_\theta =\begin{bmatrix} e^{i \theta} & 0 \\ 0 & 1 \end{bmatrix},$

also

$U_\theta | 0 \rangle = e^{i \theta} | 0 \rangle \quad U_\theta | 1 \rangle = | 1 \rangle.$

Reversible Schaltungen

→ Hauptartikel: Reversibles Computing

Wiederum betrachten wir zunächst die reversible klassische Berechnung. Grundsätzlich gibt es keinen Unterschied zwischen einer reversiblen n-Bit Schaltung und einem reversiblen n-Bit-Gatter. Es ist lediglich eine umkehrbare Funktion im Raum der n-Bit-Daten. Wie bereits im vorherigen Abschnitt beschrieben, möchte man aus praktischen Erwägungen eine kleine Anzahl reversibler Gatter haben, die zu einer reversiblen Schaltung zusammengesetzt werden können. Der Zusammenbau einer Schaltung wird an folgendem Beispiel deutlich. Angenommen man hat ein reversibles n-Bit-Gatter f und ein reversible m-Bit-Gatter g. Zusammenbau heißt, eine neue Schaltung herzustellen, indem man eine Teilmenge der k < n der Ausgänge von f mit einer Teilmenge k der Eingänge von g verbindet, wie im Bild unten dargestellt. In diesem Bild ist n = 5, k = 3 und m = 7. Die resultierende Schaltung ist ebenfalls reversibel und verarbeitet n + m − k Bits.

Im Folgenden wird diese Schema als klassischer Verbund bezeichnet. Beim Zusammenbau dieser reversibler Maschinen, ist es wichtig, dass die Zwischenstufen ebenfalls reversibel sind. Mit dieser Bedingung wird sichergestellt, dass sich innerhalb der Maschine die Entropie nicht erhöht (Abfall). Damit ist es möglich, zu zeigen, dass das Toffoli-Gatter ein Quantengatter ist. Das bedeutet, dass zu einer beliebigen reversiblen klassischen n-Bit-Schaltung h in oben beschriebener Weise ein klassischer Verbund aus Toffoli-Gattern eine n+m-Bit-Schaltung f erzeugen werden kann, so dass gilt.

$f(x_1, \ldots, x_n, \underbrace{0, \dots, 0}) = (y_1, \ldots, y_n, \underbrace{0, \ldots , 0})$

Darin sind die Bereiche oberhalb der spitzen Klammern m 0-Eingaben und es gilt

$(y_1, \ldots, y_n) = h(x_1, \ldots, x_n)$.

Man beachte, dass das Endergebnis immer eine Kette von m Nullen als Hilfbits enthält. Es wird an keiner Stelle Abfall produziert, so dass die Berechnung tatsächlich im physikalischen Sinne keine Entropie erzeugt. ^[1] Daraus folgt sofort, dass jede Funktion f (ob bijektiv oder nicht) durch eine Schaltung von Toffoli-Gattern simuliert werden kann. Wenn die Abbildung jedoch nicht injektiv ist, muss die Simulation an irgendeiner Stelle Abfall produzieren, z. B. beim letzten Schritt.

Für Quantenschaltungen kann eine ähnliche Verbindung von Qubit-Gattern definiert werden. Diese lässt sich mit dem klassischen Verbund oben assoziieren, indem man anstelle von f ein n-Qubit-Gatter U und statt g das m-Qubit-Gatter W verwendet. Daraus erhält man eine reversible Quantenschaltung, wie in der folgenden Abbildung dargestellt.

Es lässt sich leicht zeigen, dass sich durch Verbindung der Gatter eine unitäre Abbildung auf dem n+m−k-Qubit-Raum entsteht. Außerdem sei noch angemerkt, dass in realen Quantencomputern die physikalische Verbindung zwischen den Gattern eines der Hauptprobleme darstellt, da sie eine der Stellen ist, wo Dekohärenz auftreten kann.

Außerdem bilden einige Mengen wohlbekannter Gatter universelle Gatter. So ist das oben erwähnte Einzel-Qubit-Phasengatter U_Θ für sinnvolle Werte von Θ zusammen mit dem 2-Qubit-CNOT-Gatter W_CNOT) universell. Allerdings ist die Universalität im Falle der Quantenberechnung etwas schwächer. Jede reversible n-Qubit-Schaltung kann durch beliebig durch diese beiden elementaren Gatter approximiert werden. Man beachte dass es überabzählbar viele mögliche Einzel-Qubit-Phasengatter gibt (eines für jeden möglichen Winkel Θ). Damit können überabzählbar viele dieser Gatter nicht durch endliche Schaltungen aus {U_?, W_CNOT)} konstruiert werden.

Quantenberechnungen

Da viele wichtige numerische Probleme sich auf die Berechnung einer unitären Transformation U auf einem endlich-dimensionalen Raum reduzieren lassen (als prominenteste Beispiel sei die Diskrete Fourier-Transformation genannt), könnte man erwarten, das man eine Quantenschaltung für die Transformation U bauen kann. Im Prinzip muss man nur einen n-Qubit-Zustand Ψ als zugehörige Superposition der Berechnungszustandsbasis für den Eingang präparieren und den die Ausgänge von UΨ messen. Leider gibt es damit zwei Probleme:

• Man kann die Phase von Ψ nicht für jeden Basiszustand messen. Daher gibt es keine Möglichkeit, das vollständige Ergebnis zu messen. Dies liegt in der Natur der quantenmechanischen Messung.
• Es ist nicht möglich, den Eingangszustand Ψ effizient zu präparieren.

Trotzdem können Quantenschaltungen für die diskrete Fouriertransformation als Zwischenschritt in anderen Quantenschaltungen benutzt werden. Die Verwendung ist jedoch etwas komplizierter. Tatsächlich sind Quantenberechnungen probabilistisch.

Es wird nun ein mathematisches Modell für die Simulation von probabilistischen statt klassischen Berechnungen erstellt. Man betrachte eine r-Qubit-Schaltung U mit dem Registerraum H_QB(r). Damit ist U eine unitäre Abbildung

$H_{\operatorname{QB}(r)} \rightarrow H_{\operatorname{QB}(r)}.$

Um diese Schaltung mit der klassischen Abbildung von Bit-Zeichenketten zu assoziieren, spezifiziert man

• Ein Eingangsregister X = {0,1}^m von m (klassischen) Bits.
• Ein Ausgangsregister Y = {0,1}ⁿ von n (klassischen) Bits.

Der Inhalt x = x₁, …, x_m des klassischen Eingangsregisters wird irgendwie für die Initialisierung des Qubit-Registers verwendet. Idealerweise wird das mit der Berechnungszustandsbasis gemacht.

$|\vec{x},0\rangle= | x_1, x_2, \cdots, x_{m}, \underbrace{0, \dots, 0} \rangle$

Dabei gibt es unter der Klammer r − m 0-Eingänge.

Dennoch ist die perfekte Initialisierung absolut unrealistisch. Man nehme daher an, dass die Initialisierung ein Mischzustand ist, der durch den Dichteoperator S gegeben ist. Dieser ist in einer geeigneten Metrik dem idealen Eingangszustand sehr ähnlich, z. B.

$\operatorname{Tr}\left(\big||\vec{x},0\rangle \langle \vec{x},0 | - S\big|\right) \leq \delta$

Ebenso steht der Ausgangsregister-Raum mit dem Qubit-Register über die durch ein Y angenäherte Observable A in Beziehung. mEs sei angemerkt, dass Observable in der Quantenmechanik üblicherweise durch projizierte Größenwerte ausgedrückt werden. Wenn die Variable diskret ist, dann reduziert sich der projizierte Größenwert auf eine Familie {E_λ}. Dabei ist λ ein Parameter über einer abzählbaren Menge. Analog kann eine Observable Y mit einer Familie von paarweisen orthogonalen Projektionen {E_y} indexiert durch Y assoziiert werden. Damit ist

$I = \sum_{y \in Y} \operatorname{E}_y.$

Zu einem gegebenen Mischzustand S korrespondiert ein Wahrscheinlichkeitsmaß für Y

$\operatorname{Pr}\{y\} = \operatorname{Tr}(S \operatorname{E}_y )$

Die Funktion F:X → Y wird durch die Schaltung U:H_QB(r) → H_QB(r) innerhalb von ε berechnet genau dann, wenn für alle Bitzeichenkeitten x der Länge m gilt

$\left\langle \vec{x},0 \big| U^* \operatorname{E}_{F(x)} U \big|\vec{x},0 \right\rangle = \left\langle \operatorname{E}_{F(x)} U( |\vec{x},0\rangle) \big| U( |\vec{x},0\rangle) \right\rangle \geq 1 - \epsilon$

Damit gilt

$\left| \operatorname{Tr} (S U^* \operatorname{E}_{F(x)} U) - \left\langle \vec{x},0 \big| U^* \operatorname{E}_{F(x)} U \big|\vec{x},0 \right\rangle\right|\leq \operatorname{Tr} (\big||\vec{x},0\rangle \langle \vec{x},0 | - S\big|) \| U^* \operatorname{E}_{F(x)} U \| \leq \delta$

so dass

$\operatorname{Tr} (S U^* \operatorname{E}_{F(x)} U) \geq 1 - \epsilon - \delta$

Satz. Wenn $\epsilon + \delta < \frac1{2}$, dann kann die Wahrscheinlichkeitsverteilung

$\operatorname{Pr}\{y\} = \operatorname{Tr} (S U^* \operatorname{E}_{y} U)$

auf Y verwendet werden, um F(x) bei hinreichend vielen Stichproben mit einer beliebig kleinen Fehlerwahrscheinlichkeit zu bestimmen. Nimmt man k unabhängigen Stichproben aus der Wahrscheinlichkeitsverteilung Pr auf Y, dann ist die Wahrscheinlichkeit, das der Wert F(x) mehr als k/2-mal gemessen wird mindestens

$1 - e^{- 2 \gamma^2 k}$

wobei $\gamma = \frac1{2} - \epsilon - \delta$. Dies folgt aus der Chernoff-Ungleichung.

Siehe auch

• Quantengatter
• Liste der Quantengatter

Literatur

• Eli Biham, Gilles Brassard, Dan Kenigsberg, Tal Mor: Quantum computing without entanglement Quantum computing without entanglement. In: Theoretical Computer Science. Bd. 320, Nr. 1, 2004, S. 15–33, arXiv:quant-ph/0306182, doi:10.1016/j.tcs.2004.03.041.
• M.H. Freedman, A. Kitaev, M.J. Larsen, Z. Wang: Topological quantum computation Topological quantum computation. In: Bulletin of the AMS. Bd. 40, Nr. 1, 2003, S. 31–38 (PDF).
• Mika Hirvensalo: Quantum Computing. Springer, Berlin 2000, ISBN 3540667830.
• Michael A. Nielsen, Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000, ISBN 0521635039.

Weblinks

• Quantum circuit on arxiv.org (englisch)
• Q-circuit ist eine Makro-Bibliothek zum Zeichnen von Quantenschaltungen in LaTeX.

Einzelnachweise

1. ↑ A Yu Kitaev: In: Russian Mathematical Surveys. 52, 1997, S. 1191–1249, doi:10.1070/RM1997v052n06ABEH002155.