Quantum Information Processing: Foundations - Part 3

Having laid out some mathematical foundations in the previous part , we will proceed to discussing quantum gates and circuits in depth here. As usual, we will drive home the theories with worked examples from (Rieffel, E. G. & Polak, W. H., 2014) and check their accuracies with qiskit and/or cirq code.

Understanding quantum gates and circuits will be greatly aided by the knowledge of classical gates (AND, OR, NOT, XOR and the universal gates: NAND and NOR). Also, some familiarity with the Python programming language will help you understand qiskit and/or cirq code.

A classical computer, possibly the one you're reading this with, is a sophisticated engineering piece, no doubt. However, the underlying "magic" comprises logic gates. The National Institute of Standards and Technology (NIST) gives this incredible analogical description of classical computers in relation to logic gates (Quantum Logic Gates., 2018):

Traditional computers are like microscopic cities. The roads of these cities are wires with electricity coursing through them. These roads have lots of gates, known as logic gates, which enable computers to do their job. Like physical gates that allow or block cars, logic gates allow or block electricity. Electricity that goes through the gates represents a “1” of digital data, and blocked electricity is a “0.”

When you pick up a motherboard, for instance, you may not see the said gates as they are made of tiny transistors (in modern systems, MOSFETs) in specific combinations. Also, the $0$ and $1$ referred to in the analogy mean low and high voltage ranges, respectively. Their actual voltage values depend on the hardware.

Since we will be realizing some classical circuits using quantum gates, it's necessary to get familiar with common logic gates.

NOT ($\neg$) Gate

This gate takes a single classical bit and flips it. For instance, if $0$ is the input to this gate, $1$ will be seen in the output, vice versa. Just like a flip of a coin. Below, you find both the IEEE symbol of the gate and its truth table:

AND ($\land$) Gate

Borrowing NIST's analogy again (Quantum Logic Gates., 2018):

One kind of logic gate, known as the AND gate, could, for example, quickly determine whether two people agree to a business deal. It takes in two bits of information, and generates a 1 if both incoming bits are 1s. So, if both business people say “yes” (1) to the deal, the AND gate will output 1. If one or both say “no” (0), the AND gate generates a 0 or a no.

From the analogy, the gate usually takes 2 bits (2 people who want to deal). It has the truth table and symbol shown below.

OR ($\lor$) Gate

This logic gate also takes 2 bits and functions based on the analogy that if two founders are deciding whether to launch a product, OR says “launch if at least one says yes.” Only when both say no does the result become no. Its symbol and truth table are as follows:

XOR ($\oplus$) Gate

Exclusive OR (XOR) gate is a core part of an adder circuit and, in algorithms, we use it for bitwise manipulation in problems including finding a number that does not have a duplicate in an array. For a 2-bit input, its output is $1$ if and only if the bits are of opposite values. Its truth table sheds more light on this:

XOR gate's symbol is as follows:

NAND

NAND (Not AND) is one of the universal gates in digital circuits; the other is NOR (Not OR). It is universal because, with only this single gate, all other gates and circuits can be designed. Its behavior is simply as its name sounds: invert the output of an AND gate!

NAND gate's symbol is as follows:

NOR

NOR does the same thing to an OR gate: it inverts its output. Therefore, it only returns $1$ when both inputs are $0$. Like NAND, it is universal.

Just as classical gates are the foundations of classical computers, quantum gates are those of quantum computers. They make it possible for quantum algorithms to run. The fundamental difference between them is that classical gates work on bits whose state is either $0$ or $1$ (and not both at the same time), whereas quantum gates operate on qubits where $0$ and $1$ can be superposed and even entangled (this will be discussed in the next part).

Quantum gates can either be single-qubit or multiple-qubit gates (Gopalan College of Engineering & Management., 2022). As with almost anything in quantum computing, these gates can be mathematically expressed as matrices, and we will explore this heavily to understand how they work. One thing to keep in mind is that their matrices must be unitary. As discussed in the first part of this series, it means their inverses are the same as their Hermitian (conjugate transpose). It also means that the gate operations are reversible.

We will explore the X-, Y-, Z-, H-, S- and T- gates as examples of single-qubit gates. Though there are many multiple-qubit gates, we will only discuss the CNOT gate here. The reason is that the set of H-, CNOT, and T- gates is universal and can approximate any quantum computation to arbitrary precision (MathWorks., n.d.). In simple terms, they can get as close as needed to any quantum operation.

X-Gate

This is the quantum equivalent of the classical NOT gate. In the quantum world, it is called the Pauli X-gate. Just like its classical counterpart, this gate flips its incoming qubit. If $\ket{0}$ is the input, $\ket{1}$ will be the output, vice versa. Mathematically, this gate can be expressed, in matrix form, as:

Now, let's look at the behaviour of this gate on a state, $\ket{\psi}$.

If

Then, in matrix form,

Feeding this into the Pauli X-gate, we have:

It got flipped!

Therefore, it can be demonstrated that if we feed $\ket{0}$ ($\begin{bmatrix}1 \\ 0\end{bmatrix}$ in matrix form) into an X-gate, we will have:

In the same vein, feeding $\ket{1}$ ($\begin{bmatrix}0 \\ 1\end{bmatrix}$ in matrix form) into the gate gives:

The truth table can easily be built from here:

Y-Gate

The Pauli Y-gate also flips a qubit. However, unlike the X-gate, it adds a phase to the result. Its matrix is:

Let's feed the same arbitrary state, $\ket{\psi}$, into it:

The amplitudes have been swapped, but they now carry the phases $-i$ and $i$. From here, feeding $\ket{0}$ into the gate gives:

In the same vein, feeding $\ket{1}$ into it gives:

The truth table can be built from here:

You may notice that $i\ket{1}$ and $-i\ket{0}$ still give the same measurement probabilities as $\ket{1}$ and $\ket{0}$, respectively, in the computational basis. This is because an overall phase does not affect the measurement probabilities. However, when the qubit is in a superposition, a phase on one part of the state matters. We will see this with the next gate.

Z-Gate

The Pauli Z-gate is also called the phase-flip gate. Unlike the X- and Y- gates, it does not swap the amplitudes. Instead, it changes the sign of the $\ket{1}$ amplitude. Its matrix is:

Feeding our arbitrary state into it, we have:

For the basis states:

You may ask: if $\ket{1}$ and $-\ket{1}$ produce the same measurement probability, what exactly changed? When $\ket{1}$ is by itself, the minus sign is a global phase and cannot be observed. However, in a superposition, it changes the relative phase between the amplitudes. For example:

Recall that $\frac{\ket{0}+\ket{1}}{\sqrt{2}}=\ket{+}$ and $\frac{\ket{0}-\ket{1}}{\sqrt{2}}=\ket{-}$. Therefore, $Z\ket{+}=\ket{-}$. Both states have a $50\%$ probability of returning $0$ or $1$ when measured in the computational basis. They are, however, different states and behave differently when another gate, such as H, acts on them.

H-Gate

The Hadamard gate, commonly written as H, takes a basis state and puts it in an equal superposition. Its matrix is:

Let's first see its action on our arbitrary qubit:

Now, if $\ket{0}$ is fed into the gate:

In the same vein:

From $H\ket{0}=\frac{1}{\sqrt{2}}\ket{0}+\frac{1}{\sqrt{2}}\ket{1}$, the probabilities of measuring $\ket{0}$ and $\ket{1}$ are:

and

Before moving on, there is another interesting property of this gate. Applying H twice returns the original state. Let's confirm that from its matrix:

Therefore, $H^2=I$. This also means that $H\ket{+}=\ket{0}$ and $H\ket{-}=\ket{1}$. The gate takes us from the computational basis, $\{\ket{0},\ket{1}\}$, to the Hadamard basis, $\{\ket{+},\ket{-}\}$, and vice versa.

S-Gate

The S-gate is another phase gate. It leaves $\ket{0}$ unchanged but adds a phase of $\frac{\pi}{2}$ to $\ket{1}$. Its matrix is:

Applying it to our arbitrary state gives:

Recall from Euler's formula that $e^{i\frac{\pi}{2}}=i$. Therefore:

The truth table can be built from here:

Also, applying S twice produces the Z-gate. From its matrix:

T-Gate

The T-gate works in a similar fashion to the S-gate. It is also called the $\frac{\pi}{8}$ gate, though the relative phase it adds to $\ket{1}$ is $\frac{\pi}{4}$. Its matrix is:

Recall Euler's formula, $e^{i\theta}=\cos\theta+i\sin\theta$. Substituting $\theta=\frac{\pi}{4}$, we have:

Now, let's apply T to our arbitrary state:

From here, applying T twice should give S. Let's confirm this from its matrix:

CNOT Gate

All the gates discussed thus far take a single qubit. The Controlled NOT (CNOT or CX) gate takes two: a control and a target. If the control is $\ket{0}$, the target remains unchanged. However, if the control is $\ket{1}$, an X-gate is applied to the target. The control itself does not change.

If we represent the control with $c$ and the target with $t$, the operation can be written as:

where $\oplus$ is XOR. Recall that XOR returns $1$ only when its two inputs differ. In the computational basis ordered as $\{\ket{00},\ket{01},\ket{10},\ket{11}\}$, the matrix of the gate is:

Let's work through all four computational basis states:

• $\ket{00}\rightarrow\ket{00}$: the control is $0$, so the target remains $0$;
• $\ket{01}\rightarrow\ket{01}$: the control is $0$, so the target remains $1$;
• $\ket{10}\rightarrow\ket{11}$: the control is $1$, so the target flips from $0$ to $1$; and
• $\ket{11}\rightarrow\ket{10}$: the control is $1$, so the target flips from $1$ to $0$.

Now, what happens if the control is in a superposition? Let's consider two qubits initialized to $\ket{00}$. First, we apply H to the first qubit while leaving the second unchanged:

From here, we apply CNOT using the first qubit as the control:

From here, both qubits are in one of the Bell states. Notice that we can no longer separate it into an independent state for the first qubit and another for the second. This is regarded as entanglement. We will properly unpack it in the next part.

Design a circuit that rearranges three arbitrary single-qubit states in this manner:

Solution

Given:

where the subscripts represent the wire positions.

To solve this, let's compare the initial and final positions of the states:

From the table:

• $\ket{\psi}: 1\rightarrow2$
• $\ket{\phi}: 2\rightarrow3$
• $\ket{\eta}: 3\rightarrow1$

Looking at the movements together, we see that they form a cycle. A SWAP gate exchanges the states in two positions, so we can complete this cycle with two of them.

First, swap the states in positions $2$ and $3$:

The states are now in the order $\ket{\psi}\ket{\eta}\ket{\phi}$. We only need to move $\ket{\eta}$ to the first position. So, let's swap the states in positions $1$ and $2$:

$\therefore$

The required circuit is:

Before going to the check, let's show how a SWAP gate can be built with three CNOT gates. Suppose the first and second qubits contain the basis values $a$ and $b$, respectively. The gates are applied in this order:

The first subscript denotes the control qubit while the second denotes the target. Also, recall these properties of XOR:

For the first CNOT, $a$ is the control. It remains unchanged while the target, $b$, becomes $a\oplus b$:

For the second CNOT, $a\oplus b$ is now the control and $a$ is the target. The new target is:

Therefore:

For the last CNOT, $b$ is the control and $a\oplus b$ is the target. The target becomes:

So:

$\therefore$

We started with $(a,b)$ and ended with $(b,a)$. The two values have been swapped! We used the basis values $a$ and $b$ to make the calculation easier. Since quantum gates are linear, the same result holds for arbitrary single-qubit states, including states in superposition.

Check

This is a Google Cirq code for checking the CNOT construction and the final permutation:

1import cirq
2import numpy as np
3​
4# Define three qubits
5q1, q2, q3 = cirq.LineQubit.range(3)
6​
7# Build the circuit with two SWAP gates
8swap_circuit = cirq.Circuit(
9    cirq.SWAP(q2, q3),
10    cirq.SWAP(q1, q2),
11)
12​
13# Build the same circuit using CNOT gates
14decomposed_circuit = cirq.Circuit(
15    # SWAP q2 and q3
16    cirq.CNOT(q2, q3),
17    cirq.CNOT(q3, q2),
18    cirq.CNOT(q2, q3),
19    # SWAP q1 and q2
20    cirq.CNOT(q1, q2),
21    cirq.CNOT(q2, q1),
22    cirq.CNOT(q1, q2),
23)
24​
25# Confirm that both circuits have the same unitary matrix
26np.testing.assert_allclose(
27    cirq.unitary(swap_circuit),
28    cirq.unitary(decomposed_circuit),
29    atol=1e-8,
30)
31​
32# Define arbitrary single-qubit states
33psi = np.array([1 + 1j, 2], dtype=complex)
34phi = np.array([1, -1j], dtype=complex)
35eta = np.array([2 - 1j, 1], dtype=complex)
36​
37# Normalize the states
38psi = psi / np.linalg.norm(psi)
39phi = phi / np.linalg.norm(phi)
40eta = eta / np.linalg.norm(eta)
41​
42# Form |psi>|phi>|eta> and the expected |eta>|psi>|phi>
43initial_state = np.kron(np.kron(psi, phi), eta)
44expected_state = np.kron(np.kron(eta, psi), phi)
45​
46# Simulate the SWAP circuit
47result = cirq.Simulator().simulate(
48    swap_circuit,
49    qubit_order=[q1, q2, q3],
50    initial_state=initial_state,
51)
52​
53# Confirm the final state
54np.testing.assert_allclose(
55    result.final_state_vector,
56    expected_state,
57    atol=1e-7,
58)
59​
60print(swap_circuit)
61print("The three-qubit permutation is correct!")

Find the $4\times4$ unitary matrix represented by each of the following two-qubit circuits:

(a) Apply the Hadamard gate to $x_1$ while leaving $x_2$ unchanged.

(b) Leave $x_1$ unchanged while applying the Hadamard gate to $x_2$.

Solution

Before going into the two circuits, let's lay out some foundations.

There are $2$ qubits in each circuit. Recall that an $n$-qubit gate has a $2^n\times2^n$ matrix. Therefore, the dimension of each matrix here is:

From the circuits, the matrices involved are the Hadamard matrix, $H$, and the identity matrix, $I$:

Also, recall that the tensor product of:

and another matrix, $B$, is:

(a) Hadamard on $x_1$

In circuit (a), $H$ is applied to $x_1$ while $x_2$ remains unchanged. The identity matrix, $I$, represents the unchanged qubit. Since $x_1$ comes before $x_2$, the overall operation is:

Now, substitute the matrices:

(b) Hadamard on $x_2$

In circuit (b), $x_1$ remains unchanged while $H$ is applied to $x_2$. This time, $I$ comes before $H$. Therefore, the operation is:

Substitute both matrices:

Check

This is another cirq code for checking both matrices:

1import cirq
2import numpy as np
3​
4# Define the two qubits
5x1, x2 = cirq.LineQubit.range(2)
6​
7# Circuit (a): H on x1 and I on x2
8circuit_a = cirq.Circuit(
9    cirq.H(x1),
10    cirq.I(x2),
11)
12​
13# Circuit (b): I on x1 and H on x2
14circuit_b = cirq.Circuit(
15    cirq.I(x1),
16    cirq.H(x2),
17)
18​
19# Define the matrix obtained for circuit (a)
20expected_a = np.array(
21    [
22        [1, 0, 1, 0],
23        [0, 1, 0, 1],
24        [1, 0, -1, 0],
25        [0, 1, 0, -1],
26    ],
27    dtype=complex,
28) / np.sqrt(2)
29​
30# Define the matrix obtained for circuit (b)
31expected_b = np.array(
32    [
33        [1, 1, 0, 0],
34        [1, -1, 0, 0],
35        [0, 0, 1, 1],
36        [0, 0, 1, -1],
37    ],
38    dtype=complex,
39) / np.sqrt(2)
40​
41# Let Cirq obtain the matrices directly from the circuits
42unitary_a = cirq.unitary(circuit_a)
43unitary_b = cirq.unitary(circuit_b)
44​
45# Compare Cirq's matrices with our answers
46np.testing.assert_allclose(unitary_a, expected_a, atol=1e-8)
47np.testing.assert_allclose(unitary_b, expected_b, atol=1e-8)
48​
49print("H tensor I:")
50print(np.round(unitary_a, 3))
51​
52print("\nI tensor H:")
53print(np.round(unitary_b, 3))

Enjoyed this article? I'm a Software Engineer and Technical Writer actively seeking new opportunities to impact and learn, particularly in areas related to web security, finance, healthcare, and education. If you think my expertise aligns with your team's needs, let's chat! You can find me on LinkedIn and X . I am also an email away.