3.1.6 Die kontrollierte-NOT-Operation

NOT\mathrm{NOT} und SWAP\mathrm{SWAP} kann man nutzen, um einzelne Bits und deren Reihenfolge zu ändern. Die Bits interagieren dabei aber nicht miteinander. Um sinnvolle Algorithmen zu Bauen brauchen wir eine Operation, die ein Bit in Abhängigkeit eines anderen verändert. Die CNOT\mathrm{CNOT}-Operation, oder auch kontrollierte-NOT (engl. controlled-NOT), ist die einfachste Operation, die genau das macht. Sie flippt das Zielbit (engl. target) genau dann, wenn das Steuerbit (engl. control) auf 1 gesetzt ist.

Wenn das erste Bit das Steuer- und das zweite das Zielbit ist, schreiben wir CNOT1→2\mathrm{CNOT}_{1\to 2}. In diesem Fall gilt:

CNOT1→2⁢[00]\displaystyle\mathrm{CNOT}_{1\to 2}\,[00] =[00],\displaystyle=[00], (3.19)
CNOT1→2⁢[01]\displaystyle\mathrm{CNOT}_{1\to 2}\,[01] =[01],\displaystyle=[01],
CNOT1→2⁢[10]\displaystyle\mathrm{CNOT}_{1\to 2}\,[10] =[11],\displaystyle=[11],
CNOT1→2⁢[11]\displaystyle\mathrm{CNOT}_{1\to 2}\,[11] =[10].\displaystyle=[10].

Das entspricht also einem vertauschen der beiden strings [10][10] und [11][11] während die anderen beiden unverändert bleiben.

Man kann sich CNOT1→2\mathrm{CNOT}_{1\to 2} auch als Addition vorstellen: die beiden bits werden aufaddiert (modulo 22) und das Ergebnis wird im zweiten Bit gespeichert. Das lässt sich so zusammenfassen:

CNOT1→2⁢[a,b]=[a,a⊕b],\mathrm{CNOT}_{1\to 2}\,[a,b]=[a,a\oplus b], (3.20)

für jedes a,b∈{0,1}a,b\in\{0,1\} wobei “⊕\oplus” die Addition modulo 22 darstellt und das Komma die beiden Bits trennt. Die Addition modulo 22 funktioniert wie folgt:

0⊕0=1⊕1=0,\displaystyle 0\oplus 0=1\oplus 1=0, 0⊕1=1⊕0=1.\displaystyle 0\oplus 1=1\oplus 0=1. (3.21)

Manchmal nennt man “⊕\oplus” auch XOR oder exklusives Oder (engl. exclusive or), also “entweder-oder”, da das Ergebnis nur dann 11 ist, wenn genau eins der beiden Bits 11 ist. Wie üblich kann man CNOT1→2\mathrm{CNOT}_{1\to 2} durch Linearität von deterministischen Bits auf probabilistische erweitern.

Wir werden auch kontrollierte-NOT Operationen sehen, bei denen das zweite Bit das Steuer- und das erste das erste das Zielbit ist. Analog schreiben wir diese Operation CNOT2→1\mathrm{CNOT}_{2\to 1}.

Übungsaufgabe 3.4 ( Steuer- und Zielbit vertauschen ).
  1. 1.
    ​

    Schreibe die Operation CNOT2→1\mathrm{CNOT}_{2\to 1} in einer Formel wie in Gl. 3.20.

  2. 2.
    ​

    Wie kann man CNOT2→1\mathrm{CNOT}_{2\to 1} durch SWAP\mathrm{SWAP} und CNOT1→2\mathrm{CNOT}_{1\to 2} implementieren?

Lösung.
  1. 1.
    ​

    CNOT2→1⁢[a,b]=[a⊕b,b]=[b⊕a,b]\mathrm{CNOT}_{2\to 1}[a,b]=[a\oplus b,b]=[b\oplus a,b].

  2. 2.
    ​

    Dies kann getan werden, indem man zuerst eine SWAP\mathrm{SWAP}-Operation ausführt, dann CNOT1→2\mathrm{CNOT}_{1\to 2}, und am Ende wieder SWAP\mathrm{SWAP}. Tatsächlich, wenn wir Gl. 3.18 und 3.20 nutzen, gilt

    SWAP⁢(CNOT1→2⁢(SWAP⁢[a,b]))=SWAP⁢(CNOT1→2⁢[b,a])\displaystyle\quad\mathrm{SWAP}(\mathrm{CNOT}_{1\to 2}(\mathrm{SWAP}[a,b]))=% \mathrm{SWAP}(\mathrm{CNOT}_{1\to 2}[b,a])
    =SWAP⁢[b,b⊕a]=[b⊕a,b].\displaystyle=\mathrm{SWAP}[b,b\oplus a]=[b\oplus a,b].

Du kannst eine kontrollierte-NOT-Operation in Quirky hinzufügen, indem du zunächst die ∙\bullet Box auf dein Steuerbit ziehst. Danach ziehst du die ⊕\oplus Box auf den Draht, der dem Zielbit entsprechen soll. Wenn alles klappt, verbinden sich die beiden Boxen und du hast erfolgreich eine kontrollierte-NOT-Operation erstellt. Hast du zum Beispiel das untere Bit als Steuer- und das obere als Zielbit ausgewählt, solltest du folgendes Ergebnis erhalten:

[Uncaptioned image]

Da das untere (!) Bit das erste, und das obere das zweite Bit ist, entspricht diese Abbildung der CNOT1→2\mathrm{CNOT}{1\to 2}-Operation. Hier siehst du ein komplexeres Beispiel, in dem zunächst CNOT1→2\mathrm{CNOT}_{1\to 2} und anschließend CNOT2→1\mathrm{CNOT}_{2\to 1} angewendet wird:

[Uncaptioned image]

Hausaufgabe 3.2 ( SWAP\mathrm{SWAP} aus CNOT\mathrm{CNOT}’s ).
[Uncaptioned image]

Problem: Es ist beinahe Mitternacht, aber Bob bastelt immer noch an dem Prototypen seines probabilistischen-Bit Computers herum, den er am nächsten Tag in der Schule vorstellen will. Er ist so beschäftigt damit, seinen Zufallszahlengenerator zu kalibreren, dass er vergisst seinen Papageien Ziggy zu füttern. Um auf sich aufmerksam zu machen, stößt Ziggy Bob’s Kaffetasse um und der ganze Kaffe fließt über Bob’s selbstgebastelte Tastatur, mit der er Operationen auslösen kann. Entsetzt stellt Bob fest, dass die SWAP\mathrm{SWAP}-Taste nicht mehr funktioniert! Zum Glück ist es der CNOT\mathrm{CNOT}-Taste besser ergangen, sie funktioniert noch immer. Fragen: Wie kann Bob die SWAP\mathrm{SWAP}-Operation nur durch CNOT\mathrm{CNOT}-Operationen implementieren? (Wenn du zeigen willst, dass zwei Operationen identisch sind, musst du das dank Linearität nur für die Basiszustände zeigen.)

Hinweis: Du solltest drei CNOT-Operationen benötigen.

Hack.

This can be done by three controlled-NOT operations, namely:

SWAP=CNOT1→2⁢CNOT2→1⁢CNOT1→2\mathrm{SWAP}=\mathrm{CNOT}_{1\to 2}\mathrm{CNOT}_{2\to 1}\mathrm{CNOT}_{1\to 2}

We can check that this works by checking that indeed these CNOT\mathrm{CNOT}’s send [a,b][a,b] to [b,a][b,a], for all a,b∈{0,1}a,b\in\{0,1\}:

CNOT1→2⁢(CNOT2→1⁢(CNOT1→2⁢[a,b]))\displaystyle\quad\mathrm{CNOT}_{1\to 2}(\mathrm{CNOT}_{2\to 1}(\mathrm{CNOT}_% {1\to 2}[a,b]))
=CNOT1→2⁢(CNOT2→1⁢[a,a⊕b])\displaystyle=\mathrm{CNOT}_{1\to 2}(\mathrm{CNOT}_{2\to 1}[a,a\oplus b])
=CNOT1→2⁢[a⊕a⊕b,a⊕b]\displaystyle=\mathrm{CNOT}_{1\to 2}[a\oplus a\oplus b,a\oplus b]
=CNOT1→2⁢[b,a⊕b]\displaystyle=\mathrm{CNOT}_{1\to 2}[b,a\oplus b]
=[b,a⊕b⊕b]=[b,a],\displaystyle=[b,a\oplus b\oplus b]=[b,a],

where we used the fact that a⊕a=0a\oplus a=0, for any a∈{0,1}a\in\{0,1\}, see Gl. 3.21. This construction is actually very similar to the XOR swap algorithm that one can run on a classical computer. This is a perfect example where knowing how to program a classical computer can help you develop quantum algorithms!