3.1.6 De Controlled-NOT-bewerking

De bewerkingen NOT\mathrm{NOT} en SWAP\mathrm{SWAP} kunnen samen gebruikt worden om individuele bits te veranderen en ze in een andere volgorde te zetten. Maar ze zorgen er niet voor dat de bits met elkaar kunnen communiceren. Wat we willen is een nieuwe, meer geavanceerde bewerking die de waarde van een bit kan veranderen afhankelijk van de waarde van een andere bit. De eenvoudigste en belangrijkste van zulke bewerkingen is CNOT\mathrm{CNOT} of de controlled-NOT-bewerking. Deze draait het doelbit om als het controlebit op 11 staat.

Als het eerste bit de controle is en het tweede bit het doel, schrijven we deze bewerking als C⁢N⁢O⁢T1→2CNOT_{1\to 2}. In dit geval geldt dus:

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

Dit komt neer op het verwisselen van de strings [10][10] en [11][11], terwijl de andere twee strings met rust worden gelaten.

Een andere manier om over CNOT1→2\mathrm{CNOT}_{1\to 2} na te denken is als een optelling: het telt de twee bits op (modulo 22) en slaat het resultaat op in het tweede bit. Dit kan als volgt beknopt worden samengevat:

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

voor elke a,b∈{0,1}a,b\in\{0,1\}, waarbij ’⊕\oplus’ een optelling modulo 22 aangeeft en we een komma gebruiken om de waarden van de twee bits te scheiden. De regels voor optelling modulo 2 zijn als volgt:

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)

Soms wordt ’⊕\oplus’ ook wel XOR- of de exclusieve OR-bewerking genoemd, omdat het resultaat 11 is als precies een van de twee bits 11 is. Zoals gebruikelijk kunnen we CNOT1→2\mathrm{CNOT}_{1\to 2} uitbreiden van deterministische naar probabilistische bits door lineariteit.

Daarnaast zullen we ook gebruik maken van controlled-NOT-bewerkingen waarbij het tweede bit de controle is en het eerste bit het doel. Op vergelijkbare manier duiden we deze bewerking aan met C⁢N⁢O⁢T2→1CNOT_{2\to 1}.

Oefenopgave 3.4 ( Controle en doel omdraaien ).
  1. 1.
    ​

    Geef op dezelfde manier als in Vgl. 3.20 een formule voor CNOT2→1\mathrm{CNOT}_{2\to 1}.

  2. 2.
    ​

    Hoe kan je CNOT2→1\mathrm{CNOT}_{2\to 1} uitvoeren door alleen gebruik te maken van SWAP\mathrm{SWAP} en CNOT1→2\mathrm{CNOT}_{1\to 2}?

Solution.
  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.
    ​

    Dit kan gedaan worden door eerst een SWAP\mathrm{SWAP} toe te passen, dan een CNOT1→2\mathrm{CNOT}_{1\to 2} en tenslotte nog een SWAP\mathrm{SWAP}. Met behulp van Vgl. 3.18 en 3.20 kunnen we inderdaad zien dat

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

In Quirky kan je een controlled-NOT-bewerking maken door de volgende twee stappen uit te voeren. Sleep eerst het vakje ∙\bullet naar een van de draden - dit markeert de draad als het controle bit. Sleep vervolgens het vakje ⊕\oplus naar de overeenkomstige locatie op de andere draad, wat de draad markeert als doelbit. Er ontstaat een verbinding om aan te geven dat je met succes een controlled-NOT-bewerking hebt gemaakt. Als we bijvoorbeeld het onderste bit als controle en het bovenste bit als doel kiezen, krijgen we het volgende resultaat:

[Uncaptioned image]

Onthoud dat het onderste (!) bit het eerste bit is en het bovenste bit het tweede bit, dan zien we dat dit overeenkomt met de bewerking CNOT1→2\mathrm{CNOT}_{1\to 2}. Hier volgt een wat ingewikkelder voorbeeld, waarbij we eerst CNOT1→2\mathrm{CNOT}_{1\to 2} toepassen en daarna CNOT2→1\mathrm{CNOT}_{2\to 1}:

[Uncaptioned image]

Huiswerkopdracht 3.2 ( SWAP\mathrm{SWAP} vanuit CNOT\mathrm{CNOT}s ).
[Uncaptioned image]

Het probleem: Het is bijna middernacht, maar Bob is nog steeds aan het sleutelen aan zijn prototype van een probabilistische-bitcomputer die hij de volgende dag op school wil presenteren. Hij is zo druk bezig met het kalibreren van de randomness-generator dat hij vergeten is zijn papegaai Ziggy eten te geven. Om Bob’s aandacht te trekken, stoot Ziggy Bob’s koffiekopje om en morst de koffie over zijn op maat gemaakte toetsenbord, waarmee hij verschillende bewerkingen kan activeren. Bob is helemaal geschokt omdat de SWAP-knop niet meer werkt! Gelukkig werkt de CNOT-knop nog wel. De vraag: Hoe kan Bob de SWAP\mathrm{SWAP}-bewerking uitvoeren met alleen controlled-NOT-bewerkingen? (Als je wilt bewijzen dat twee bewerkingen hetzelfde zijn, hoef je dit alleen aan te tonen voor de basistoestanden vanwege uitbreiding door lineariteit).

Hint: Je hebt drie CNOT-bewerkingen nodig.

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 Vgl. 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!