bloch-sphere-0
< Current Chapter (Qubits and Gates)< Previous Article (Multiple Qubits)

Multi Qubit Gates

Meaningful classical computation can be done only when we have the ability to act on multiple bits at the same time. We've seen previously that we have gates that can take 1 bit as input and produce 1 bit as output, but we also have gates that can take multiple bits as input and produce multiple bits as output.

The two most common of these gates are the AND\text{AND} and OR\text{OR} gates. Just like before, we can represent the way they behave through their truth tables:

AB A AND B
000
010
100
111
AB A OR B
000
011
101
111

And here's what the circuit symbols look like:

Classical circuit symbols for the AND and OR gates

As before, we can chain these gates together visually in a circuit diagram. Now we have 2 qubit gates, we're able to achieve more complex behaviour. Take a look at the circuit below:

A classical circuit implementation of the XOR operation using NOT, AND and OR gates

Woah, looks crazy right?

This circuit is implementing a famous gate calledXOR\text{XOR} which is short for eXclusive-OR. This gate outputs a 11 if only one of the inputs is 11 but not both. The truth table is therefore:

AB A XOR B
000
011
101
110

I encourage you to work through the diagram above to confirm that this circuit does implement this truth table.

But enough of classical computation already. We're here for quantum!

We can also define multi-qubit operators that act on multiple qubits at once. A common example of this is the CNOT\textmd{CNOT} gate (short for "Controlled-NOT"). The CNOT\textmd{CNOT} gate is a two-qubit gate that flips the second qubit only if the first qubit is a 1 and leaves it alone otherwise:

CNOT∣00⟩=∣00⟩CNOT∣01⟩=∣01⟩CNOT∣10⟩=∣11⟩CNOT∣11⟩=∣10⟩\textmd{CNOT}\ket{00} = \ket{00} \\[3ex] \textmd{CNOT}\ket{01} = \ket{01} \\[3ex] \textmd{CNOT}\ket{10} = \ket{11} \\[3ex] \textmd{CNOT}\ket{11} = \ket{10}

Just like with classical gates, we have a circuit symbol for this:

The quantum circuit symbol for a CNOT gate

In this representation the solid circle at the top represents the "control" qubit, and the crossed circle at the bottom represents the "target" qubit that flips if the control qubit is 1. This representation is useful because when we have more complicated circuits with more qubits we are able to more easily choose arbitrary controls and targets.

Previously, we represented our single qubit gates using the outer product. In order to understand how we can use the outer product when dealing with multiple qubits let's look at how the tensor product works here. We'll take an arbitrary 2 outer products tensored together: ∣a⟩⟨b∣⊗∣c⟩⟨d∣\ket{a}\bra{b} \otimes \ket{c}\bra{d} and see how it behaves on two qubits: ∣ψϕ⟩\ket{\psi \phi}:

(∣a⟩⟨b∣⊗∣c⟩⟨d∣)(∣ψ⟩⊗∣ϕ⟩)=(∣a⟩⟨b∣∣ψ⟩)⊗(∣c⟩⟨d∣∣ϕ⟩)=⟨b∣ψ⟩∣a⟩⊗⟨d∣ϕ⟩∣c⟩=(∣a⟩⊗∣c⟩)⟨b∣ψ⟩⟨d∣ϕ⟩=∣ac⟩(⟨b∣⊗⟨d∣)(∣ψ⟩⊗∣ϕ⟩)=∣ac⟩⟨bd∣∣ψϕ⟩(\ket{a}\bra{b} \otimes \ket{c}\bra{d})(\ket{\psi} \otimes \ket{\phi}) \\[3ex] = (\ket{a}\bra{b}\ket{\psi})\otimes(\ket{c}\bra{d}\ket{\phi}) \\[3ex] = \braket{b | \psi}\ket{a} \otimes \braket{d | \phi}\ket{c} \\[3ex] = (\ket{a} \otimes \ket{c})\braket{b|\psi}\braket{d|\phi} \\[3ex] = \ket{ac}(\bra{b} \otimes \bra{d})(\ket{\psi} \otimes \ket{\phi}) \\[3ex] = \ket{ac}\bra{bd}\ket{\psi\phi}

Comparing the first and last line shows us that ∣a⟩⟨b∣⊗∣c⟩⟨d∣=∣ac⟩⟨bd∣\ket{a}\bra{b} \otimes \ket{c}\bra{d} = \ket{ac}\bra{bd}

Equipped with this knowledge, we can now represent the CNOT\text{CNOT} gate using outer products:

CNOT=∣00⟩⟨00∣+∣01⟩⟨01∣+∣11⟩⟨10∣+∣10⟩⟨11∣\textmd{CNOT} = \ket{00}\bra{00} + \ket{01}\bra{01} + \ket{11}\bra{10} + \ket{10}\bra{11}

Using the same result we can factor this into a more useful form:

CNOT=∣0⟩⟨0∣⊗I+∣1⟩⟨1∣⊗X\textmd{CNOT} = \ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes X

Another example of a multi-qubit operator is the SWAP\textmd{SWAP} gate. TheSWAP\textmd{SWAP} gate swaps the values of two qubits:

SWAP∣00⟩=∣00⟩SWAP∣01⟩=∣10⟩SWAP∣10⟩=∣01⟩SWAP∣11⟩=∣11⟩\textmd{SWAP}\ket{00} = \ket{00} \\[3ex] \textmd{SWAP}\ket{01} = \ket{10} \\[3ex] \textmd{SWAP}\ket{10} = \ket{01} \\[3ex] \textmd{SWAP}\ket{11} = \ket{11}

The circuit symbol for this gate is:

The quantum circuit symbol for the SWAP gate

And can be defined similarly:

SWAP=∣00⟩⟨00∣+∣01⟩⟨10∣+∣10⟩⟨01∣+∣11⟩⟨11∣\textmd{SWAP} = \ket{00}\bra{00} + \ket{01}\bra{10} + \ket{10}\bra{01} + \ket{11}\bra{11}

A quite remarkable result is that the SWAP\text{SWAP} operation can be represented as:

SWAP=12(I⊗I+X⊗X+Y⊗Y+Z⊗Z)\text{SWAP}=\frac{1}{2}(I\otimes I + X\otimes X + Y\otimes Y + Z\otimes Z)

It's quite interesting how by adding and tensoring a few single qubit gates together we can get a multi-qubit gate! The proof of this fact is fairly mechanical, and will be left for the exercises.

No cloning

Take a look at the XOR\text{XOR} circuit above. Did you notice a hidden gate? We use it twice in these locations:

The classical XOR circuit again with the implicit FANOUTs highlighted

This part of the circuit essentially "copies" the bit so we can use it's value in more than one place. In classical circuits this is often called "fan-out". It begs the question: can we do the same thing with qubits?

We can actually answer this question with a bit of algebra. We'll start by thinking about what this operation might look like if it did exist. We'll define a new operation CLONE\text{CLONE} that behaves like this: CLONE∣ψ0⟩=∣ψψ⟩\text{CLONE}\ket{\psi 0} = \ket{\psi \psi}. So it is a gate that can take a qubit and a blank qubit and copy the first qubit into the second qubit.

Note that this is not a full definition of the gate because we haven't defined it in terms of 4 basis vectors. Our following proof will show that a gate of this description cannot be fully described as such.

We will prove that this circuit can't exist by proving that this gate doesn't obey linearity. Consider when ∣ψ⟩=a∣0⟩+b∣1⟩\ket{\psi} = a\ket{0} + b\ket{1}:

COPY∣ψ0⟩=COPY((a∣0⟩+b∣1⟩)⊗∣0⟩)=COPY(a∣00⟩+b∣10⟩)=aCOPY∣00⟩+bCOPY∣10⟩=a∣00⟩+b∣11⟩\text{COPY}\ket{\psi 0} = \text{COPY}\Bigl((a\ket{0} + b\ket{1})\otimes \ket{0}\Bigr) \\[3ex] =\text{COPY}(a\ket{00}+b\ket{10}) \\[3ex] =a\text{COPY}\ket{00} + b\text{COPY}\ket{10} \\[3ex] =a\ket{00} + b\ket{11}

However:

∣ψψ⟩=∣ψ⟩⊗∣ψ⟩=(a∣0⟩+b∣1⟩)⊗(a∣0⟩+b∣1⟩)=a2∣00⟩+ab∣01⟩+ba∣10⟩+b2∣11⟩\ket{\psi \psi} = \ket{\psi} \otimes \ket{\psi} \\[3ex] = (a\ket{0} + b\ket{1}) \otimes (a\ket{0} + b\ket{1}) \\[3ex] =a^2\ket{00} + ab\ket{01} + ba\ket{10} + b^2\ket{11}

This clearly doesn't equal the result from the previous box and so we have shown that an operator implementing this behaviour doesn't exist. This is an interesting find. Not being able to clone our qubits like classical bits will naturally change the way we build quantum circuits.

It reveals something interesting about how we measure quantum states as well. If we had a qubit in the state a∣0⟩+b∣1⟩a\ket{0} + b\ket{1}, we could clone the qubit 1,000,000 times, measure them all and then use the results to estimate the values of aa and bb. However we now know we can't do this. This gives some intuition as to how quantum states are often very "hidden". In quantum systems, the information is contained within the coefficients of the basis states, but these coefficients are impossible to obtain directly. The most interesting quantum algorithms are those that derive clever ways to extract the information from these coefficients.

Exercises

Exercise 1

Verify that the SWAP\text{SWAP} gate defined above does in fact "swap" the qubits even when the qubits are not in a basis state ∣0⟩\ket{0} or ∣1⟩\ket{1}.

Show solution

Exercise 2

Prove the earlier stated fact:

SWAP=12(I⊗I+X⊗X+Y⊗Y+Z⊗Z)\text{SWAP} = \frac{1}{2}(I \otimes I + X \otimes X + Y \otimes Y + Z \otimes Z)
Show solution

Exercise 3

Verify that the following circuit is equivalent to SWAP\text{SWAP}:

A quantum circuit consisting of 3 CNOT gates, the middle one is inverted
Show solution
> Next Chapter (Entanglement)