## Introduction to quantum computing with Q# – Part 4, multi-qubit gates

In the previous post of this series, we discussed single qubit gates. In this next instalment, we are going to explore gates that act on multiple qubits at once, thus completing the exploration of quantum circuit building. We are also going to slowly, but diligently uncover the underlying theoretical scheme towards one of the most bizarre concepts in quantum mechanics – entanglement, which is something that will be dedicating the next part to.

### Mathematics and philosophy of multi qubit registers

Once the quantum computational system grows from a single to multiple qubits, we arrive at a concept of a compound quantum system. Greg Jaeger, in his excellent study of entanglement, reminds us of a mathematical framework in which such systems are embedded:

The Hilbert space of a compound quantum system is the tensor product of the Hilbert spaces of the subsystems. The pure-state space for a system of $N$ two-level systems is the Hilbert space $\mathcal{H}^{(N)} = \mathbb{C}^2\otimes\mathbb{C}^2\otimes…\otimes\mathbb{C}^2$.

As such, from the quantum information theory point of view, when dealing with multiple qubits, the overall state of the system is described not by a sum, but by a tensor product of all the individual qubit constituents (or, to be more formal, subsystems), represented below by $\psi_n$.

$$\ket{\psi} = \ket{\psi_1}\otimes\ket{\psi_2} … \otimes\ket{\psi_n}$$

As it was determined in the earlier parts of this series, quantum gates are represented by $2^n * 2^n$ sized unitary matrices, where $n$ stands for the number of qubits the gate acts on. This definition naturally implies that while single qubit matrices are $2$x$2$ in size, two-qubit gates are going to be $4$x$4$ matrices, representing a 4-dimensional abstract complex vector spaces, or more specifically, after Jaeger, Hilbert spaces. The tensor product qualification is an important one, because that is what gives rise to the $n$ dimensions. For example, for single qubits, the computational basis consists of two basic unit vectors

$$\ket{0} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$
$$\ket{1} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$$

Applying the tensor product between them, we get four dimensional standard basis vectors for two qubit systems

$$\ket{00} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} \ket{01} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}$$
$$\ket{10} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} \ket{11} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}$$

We could extrapolate this calculations onto larger qubit registers using the exact same mathematics. At the time of writing, the largest available quantum computer was constructed by Google and consists of 53 qubits. Describing a complete state of such a system requires $2^{53}$ dimensional Hilbert space, and $2^{53}$ is a really large number – $9,007,199,254,740,992$. And that’s not even the end – in quantum mechanics in general, in case of continuous variables, the mathematical structure is actually infinite-dimensional.

Of course such rigorous mathematical formalism – contrary to classical physics – makes it impossible to directly infer any structure of reality from the quantum mechanical equations, something that Einstein had lots of trouble with. Arkady Plotnitsky summarizes this situation in The Principles of Quantum Theory, From Planck’s Quanta to the Higgs Boson:

His [Heisenberg’s] new theory offers the possibility of predicting, in general probabilistically, the outcomes of quantum experiments, at the cost of abandoning the physical description or representation, however idealized, of the ultimate objects and processes considered. This cost was unacceptable to some, event to most, beginning with Einstein (…). The nature of the mathematics used, that of the infinite-dimensional Hilbert spaces over complex numbers, already makes it difficult to establish realist representations of physical processes.

A similar sentiment, along the lines of completely detaching this strange, complicated mathematical form of expression from the underlying reality, by the way something that falls in line with the “spirit of Copenhagen” (which we briefly mentioned in the earlier part of this series), has been also expressed by David Mermin in his contribution to Elegance and Enigma:

Quantum states, in other words, are bookkeeping tools that enable one to calculate, from a knowledge of the initial preparation and the fields acting on the system, the probability of the outcomes of the measurements on that system. (…) The Copenhagen view fits quantum computation so well that I am persuaded that quantum states are, even in the broader physical contexts, calculational tools, invented and used by physicists to enable them to predict correlations among their perceptions.

Leaving the philosophical debates about the nature of reality aside for now, let’s consider the following two qubit system, where the two qubits are in states $\ket{\psi_1}$ and $\ket{\psi_2}$ and the probability amplitudes are $\alpha_1$, $\beta_1$ and $\alpha_2$, $\beta_2$ respectively. As thoroughly analyzed in the earlier parts of this series, each qubit can written as a linear combination of two basis states.

$$\ket{\psi_1} = \alpha_1\ket{0} + \beta_1\ket{1}$$
$$\ket{\psi_2} = \alpha_2\ket{0} + \beta_2\ket{1}$$

The state of this two qubit system is then expressed by the tensor product of $\ket{\psi_1}$ and $\ket{\psi_2}$:

$$\ket{\psi_1}\otimes\ket{\psi_2} = \alpha_1\alpha_2\ket{0}\ket{0} + \alpha_1\beta_2\ket{0}\ket{1}\\ + \beta_1\alpha_2\ket{1}\ket{0} + \beta_1\beta_2\ket{1}\ket{1}$$

Additionally, in the Dirac braket notation, it is customary to merge the neighbouring kets into a single ket, to make the entire equation more succinct and readable:

$$\ket{\psi_1}\otimes\ket{\psi_2} = \alpha_1\alpha_2\ket{00} + \alpha_1\beta_2\ket{01}\\ + \beta_1\alpha_2\ket{10} + \beta_1\beta_2\ket{11}$$

The above equation is also important because we will return to it when we look at entanglement. When working with multi-qubit registers, we can always combine single-qubit unitary transformations to produce a multi-qubit transformation (gate). This is done by expressing those transformations as tensor products of single qubit transformations. Following this rule, $X \otimes Z$ is the same as $X \otimes I$ followed by $I \otimes Z$, where $I$ is the identity gate.

The opposite, however, is not always possible – not every multi-qubit transformation can be decomposed into a set of single qubit ones. The reason behind this is, again, the embodiment of the weirdness of quantum phenomena – some of the subsystems (qubits) may be entangled, and thus their states are not possible to be expressed individually anymore. However, as mentioned, for now we are going to attempt to steer away from the depths of entanglement though, as we are going to dedicate the entire next post to it.

### The CNOT Gate

By far the most fundamental, commonly used, and the most powerful two-qubit gate is the CNOT gate. CNOT stands for a “controlled NOT”, which means it acts like the single qubit NOT ($X$) gate but in a conditional way, where the condition spans onto the second qubit. The gate is also often referred to as “controlled bitflip”. CNOT treats the first qubit as a so-called “control qubit” and the second one as a “target qubit”. Upon application of CNOT, the value of the control qubit doesn’t change, while target qubit may change conditionally – depending on the value of the control qubit. A partial counterpart to the logic behind CNOT in classical computing is the XOR operation, or the so called exclusive OR, because the change in the target qubit value upon measurement would correspond to the XOR logic.

For two classic bit inputs XOR logic returns $0$ when the two inputs are both $0$ or both $1$, and $1$ when the two input values differ – one is a $0$ and the other a $1$. Similarly, if we leave aside the quantum mechanical concept of a superposition and the complexities arising from that, and only imagine that the qubit can only be in one of the two basis states $\ket{0}$ and $\ket{1}$ (thus behaving like a classical bit), we can summarize the effect of CNOT gate accordingly – when the control qubit is $\ket{0}$, then the target qubit doesn’t change its value. However, when the control qubit is $\ket{1}$, the value of the target swapped is swapped – from $\ket{0}$ to $\ket{1}$ and vice versa.

$$\ket{00}\rightarrow\ket{00}$$
$$\ket{01}\rightarrow\ket{01}$$
$$\ket{10}\rightarrow\ket{11}$$
$$\ket{11}\rightarrow\ket{10}$$

CNOT is mathematically expressed using the following matrix:

$$CNOT=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

The CNOT gate is unitary and is its own inverse and thus can be applied twice in a row to reverse its result. In other words, given an initial quantum state $\ket{\psi}$, the following relation holds:

$$CNOT(CNOT\ket{\psi}) = \ket{\psi}$$

There is an easy way to prove this. Let’s consider that we start in an initial quantum system state $\ket{\varphi_1,\varphi_2}$, where the control qubit is in the state $\varphi_1$ and the target qubit is in the state $\varphi_2$. Applying CNOT gate once will transform the system state to $\ket{\varphi_1,\varphi_1\oplus\varphi_2}$. Applying CNOT again will further transform that to $\ket{\varphi_1,\varphi_1\oplus(\varphi_1\oplus\varphi_2)}$. Since the XOR logic is commutative and associative, we can actually replace $\varphi_1\oplus\varphi_1$ with $0$ (recall that XOR returns $0$ when both inputs are the same), which leads to $\ket{\varphi_1,0\oplus\varphi_2}$ and that is really equivalent to the initial state $\ket{\varphi_1,\varphi_2}$.

At this point, it’s going to be beneficial to abandon purely theoretical deliberations and look at some Q# code. A word of qualification is in order though. In the three earlier posts of this series, we used a particular construct for our Q# programs – more specifically, a hybrid C# + Q# model, where C# provided a shell driver applications, and Q# contained quantum logic invoked from that application. Since then, the QDK, in one of the recent updates, shipped a new feature – standalone Q# command line applications. This feature allows us to use pure Q# programs, making the entire journey through quantum coding much more straight forward, as it eliminates the extra baggage of having to deal with an extra separate programming language. I blogged about this feature in detail on the Q# community blog recently, so I will skip the introduction to it here – I recommend however that you have a short look there.

A full example of a simmple Q# program that uses CNOT (from the $Microsoft.Quantum.Intrinsic$ namespace) against two qubits, and then measures the qubits to verify the results is shown below:

In this sample, as mentioned, we only deal with qubits in the two orthogonal basis states $\ket{0}$ to $\ket{1}$. We always borrow (“allocate”, in the C# language) two qubits, and use them to apply the CNOT gate. The sample runs 4 times – for four different starting states $\ket{00}$, $\ket{01}$, $\ket{10}$ and $\ket{11}$. The $Message$ function prints the output to the console, and we keep track of the state transformations. What we should see is the following:

This is of course as expected – the states $\ket{00}$ and $\ket{01}$ are left intact, while the states $\ket{10}$ and $\ket{11}$ result in the change in the target qubit value, along the lines of the classical XOR logic.

At this point it also worth mentioning that the notion of a “control qubit” and a “target qubit” is only an approximation of the real behavior of CNOT in quantum computing, and while helpful for high-level understanding, it should not be taken too literally. As it was discussed in part 1 of this series, measurements in quantum computing are basis dependent. Situation is the same with the effects of the CNOT gate. So far we were only discussing its behavior in the standard computational basis ($\ket{0},\ket{1}$), however, we could use the gate in a different basis, say, Hadamard basis ($\ket{+} ,\ket{-}$). In Hadamard basis, the notions of control and target qubits would appear to be effectively flipped, as it is the second qubit that remains unchanged, and the first one changes – conditionally – its state. The state transformations (without going into the mathematical proof) look the following:

$$\ket{++}\rightarrow\ket{++}$$
$$\ket{+-}\rightarrow\ket{–}$$
$$\ket{-+}\rightarrow\ket{-+}$$
$$\ket{–}\rightarrow\ket{+-}$$

### Gate universality

In classical computation theory, we often speak of the so-called “universal gates” (e.g. OR, AND and NOT) – a set of gates that can be arranged to represent any logical algorithm, without involving any other gates. Such arrangement would likely not be optimal from the performance standpoint, but it would be functionally complete. In fact, a single classical gate, the NAND gate, on its own is already a universal gate – as any boolean logic function can be represented by a combination of NAND gates. In quantum computing, the concept of gate universality is a little more challenging. Nielsen and Chuang define quantum universality as follows:

A set of gates is said to be universal for quantum computation if any unitary operation may be approximated to arbitrary accuracy by a quantum circuit involving only those gates.

Such definition contains an important qualification – “approximated to arbitrary accuracy”. Quantum computing, due to its inherently different nature compared to classical boolean algebra, does not allow for a perfect set of universal gates. The main reason behind it, is that any unitary transformation can become a gate acting on a qubit. This is explained in a very logical and intuitive way by Chris Bernhardt:

As we have seen there are infinitely many possible gates that can act on just one qubit. If we take a finite number of gates and connect them in a finite number of ways, we will end up with a finite number of circuits. So, it is just not possible to have a finite number of gates that generates and infinite number of circuits.

Despite this sobering assessment, Nielsen and Chuang do identify a set of universal quantum gates – universal according to their quantum definition, not according to the classical universality definition. Those gates are $H$ gate, phase gate, ${\pi/8}$ gate and the $CNOT$ gate; the rationale behind that is that in principle unitary transformations can be decomposed into a series of two qubit rotations. This emphasizes yet again the critical importance of the CNOT gate in the quantum algorithm building. We will soon see how one multi qubit gate can actually be replaced by aa series of CNOTs.

### CNOT generalization

An intuitive way of thinking about CNOT is that it is made up of the $I$ (top left corner) and the $X$ matrices (bottom right corner). Such observation is very helpful, as it allows to naturally generalize the behavior of CNOT into a common class of “controlled” qubit transformations, where a given transformation is applied conditionally, when the first control qubit is $\ket{1}$. If we follow this generalization path, it is possible to define any generic single qubit transformation $U$ such that:

$$U=\begin{bmatrix} U_{11} & U_{12} \\ U_{21} & U_{22} \end{bmatrix}$$

We can then use the observation we already made about the composition of the CNOT gate, and combine the $I$ gate and $U$, thus creating a hypothetical controlled $U$ two-qubit gate (“$CU$”), which is shown below.

$$CU=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & U_{11} & U_{12} \\ 0 & 0 & U_{21} & U_{22} \end{bmatrix}$$

We can now classify the effects of this $CU$ gate in the following way:

$$\ket{00}\rightarrow\ket{00}$$
$$\ket{01}\rightarrow\ket{01}$$
$$\ket{10}\rightarrow\ket{1} \otimes U\ket{0}$$
$$\ket{11}\rightarrow\ket{1} \otimes U\ket{1}$$

Such generalizations are common in the quantum computing literature – for example Bob Sutor in his recent book Dancing with Qubits provides exhaustive information about constructing $CY$, $CZ$ or even $CR^Z_\phi$ gates. Q# does not intrinsically implement those gates, however it does provide a general purpose mechanism of creating general controlled unitary transformations via the $Controlled$ functor. A simple example of achieving CNOT functionality via $Controlled$ functor and a single qubit $X$ gate in Q# is shown below:

The output of this code is identical to the earlier one when we used the built-in $CNOT$ gate.

### SWAP gate

Another useful two-qubit gate is the SWAP gate. As the name suggests, it can be used to swap the states of two qubits. This is a feature that can be very useful in quantum algorithms, especially in the absence of copying (we have not touched on that subject yet, but we will return to that later in this series). SWAP gate is described by the following matrix:

$$SWAP=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

SWAP state transformations are summarized below:

$$\ket{00}\rightarrow\ket{00}$$
$$\ket{01}\rightarrow\ket{10}$$
$$\ket{10}\rightarrow\ket{01}$$
$$\ket{11}\rightarrow\ket{11}$$

Just like the CNOT gate, SWAP function in Q# can be found in the $Microsoft.Quantum.Intrinsic$ namespace, and not surprisingly, takes two qubits as arguments. An example of using the SWAP gate in Q# is shown in the snippet below.

The code is actually identical to our earlier CNOT sample – with the only exception being that we (no pun intended) swapped CNOT with SWAP. The output is inline with our expectations:

Fittingly enough to the earlier discussion about the CNOT universality, the SWAP gate can be accurately reconstructed using a series of three CNOT transformations, applied in the order shown on the circuit below.

While such composition may not appear very intuitive at first, it is actually very easy to prove mathematically. I generally encourage everyone to try these proofs as often as possible, to develop sort of an intuition for the state transformations connected to the most common gate types. In this case, we can start the proof by imagining the initial state $\ket{\psi_1}$ of the compound two-qubit system as follows:

$$\ket{\psi_1} = \ket{a} \otimes \ket{b}$$

In $\ket{\psi_1}$, $\ket{a}$ and $\ket{b}$ are in computational basis, so either $\ket{0}$ or $\ket{1}$. After applying the first CNOT we end up with $\ket{\psi_2}$:

$$\ket{\psi_2} = \ket{a} \otimes \ket{a \oplus b}$$

Following with the second CNOT, this time with reversal of control qubit, we end up with $\ket{\psi_3}$. Notice that the reversal causes the state that was already described by XOR to stay intact.

$$\ket{\psi_3} = \ket{a \oplus (a \oplus b)} \otimes \ket{a \oplus b}$$

Due to associativity of XOR, $\ket{\psi_3}$ can then be reduced to:

$$\ket{\psi_3} = \ket{b} \otimes \ket{a \oplus b}$$

Finally, applying the final CNOT (reversing the control qubit again) leads us to state $\ket{\psi_4}$:

$$\ket{\psi_4} = \ket{b} \otimes \ket{(a \oplus b) \oplus b}$$

And just like before, this can be reduced to:

$$\ket{\psi_4} = \ket{b} \otimes \ket{a}$$

If we compare $\ket{\psi_1}$ and $\ket{\psi_4}$, we can obviously easily see that the qubit states have been swapped. Of course we do not need to only rely on algebraic proof – with Q# at our disposal, it is fairly easy to verify that this particular sequence of CNOTs is equivalent to a SWAP. This is shown in the snippet below.

It prints identical result to using the built-in SWAP gate:

### Toffoli gate

Toffoli gate, also known as CCNOT gate, is a three qubit gate that is an extrapolation of the CNOT gate logic onto three qubits. Logically, it follows similar XOR rules – with the first two qubits are both treated as control qubits, while the third plays the role of the target qubit. The first experimental realization of the gate in a trapped ion quantum computer was done in 2008 by a group at University of Innsbruck.

Since the CCNOT gate operates on three qubits, the matrix used to express it is $8$x$8$ ($2^3$) in size:

$$CNOT=\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix}$$

Similarly to how we did when looking at the CNOT gate, if we set aside the superposition states and only focus on the two computational basis states $\ket{0}$ and $\ket{1}$, the effects of the gate can be summarized in the following way:

$$\ket{000}\rightarrow\ket{000}$$
$$\ket{001}\rightarrow\ket{001}$$
$$\ket{010}\rightarrow\ket{010}$$
$$\ket{011}\rightarrow\ket{011}$$
$$\ket{100}\rightarrow\ket{100}$$
$$\ket{101}\rightarrow\ket{101}$$
$$\ket{110}\rightarrow\ket{111}$$
$$\ket{111}\rightarrow\ket{110}$$

In other words, the gate swaps the states $\ket{110}$ and $\ket{111}$ with each other and leaves all other states unchanged. In Q#, just like the CNOT, SWAP and other basic gates, CCNOT is part of the $Microsoft.Quantum.Intrinsic$ namespace and it actually happens to be the only built-in three-qubit gate in the language. However, other similar gates can always be manually constructed using the aforementioned $Controlled$ functor.

The output, of course, aligns perfectly with what we expected.

### Summary and entanglement

In this post we look at the mathematics behind multi-qubit gates, explored the CNOT, CCNOT and SWAP gates and identified a whole class of generic controlled gates. CNOT is definitely a very interesting gate from the algebraic perspective, and, as one of the universal quantum gates, is fundamentally important to the quantum information theory and quantum computing. However, since we explicitly qualified in the beginning of this post that we will ignore the superposition state of the control qubit, the CNOT behavior that we have seen so far is logical, deterministic and fully classical. Such context is useful to introduce the gate, but it also obfuscates the real reason why the gate is at the heart of quantum computing – and that’s the capability of the CNOT gate to entangle two qubits together. The next post in this series will be dedicated to entanglement, as we continue to dive deeper into the CNOT gate and the world of quantum computing.