Click here to Skip to main content
14,328,292 members

Quantum Computation Primer - Part 3

Rate this:
5.00 (4 votes)
Please Sign up or sign in to vote.
5.00 (4 votes)
27 Jun 2019CPOL
Part 3 in a series where you learn the fundamentals of quantum computation. In this part we see how to rotate and swap qubits, and we delve further into controlled gates.

Article header, wavy lines

$ \newcommand{\bra}[1]{\left< #1 \right|} \newcommand{\ket}[1]{\left| #1 \right>} \newcommand{\bk}[2]{\left< #1 \middle| #2 \right>} \newcommand{\bke}[3]{\left< #1 \middle| #2 \middle| #3 \right>} \newcommand{\mzero}[0]{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} \newcommand{\mone}[0]{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} \newcommand{\ostwo}[0]{\frac{1}{\sqrt{2}}} \newcommand{\mhadamard}[0]{\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}} \newcommand{\msnot}[0]{\begin{bmatrix} 1 + i & 1 - i \\ 1 - i & 1 + i \end{bmatrix}} \newcommand{\mswap}[0]{\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}} \newcommand{\rb}[0]{\color{red}{1}} \newcommand{\vc}[1]{\color{red}{#1}} $

Table of Contents

Introduction

In the previous article, we explored several of the gates commonly used in quantum computation, and looked at using some of these gates to create various quantum states. In this article, we continue exploring gates and examine some of the more complex gates. You see how to rotate and swap qubits, and we delve into controlled gates, which enable you to apply a gate depending on its input.

If you haven't already, I highly encourage you to read the first and second parts in this series before continuing.

Flipping and Rotating Qubits

We saw in Part 2 how the Pauli-X gate is used to flip a computational basis state. It does this by rotating the qubit to the opposite (antipodal) side of the Bloch sphere. Mutually orthogonal states correspond to antipodal points on the Bloch sphere.

There are two other Pauli gates that perform the same action on different axes. They are the Pauli-Y, and Pauli-Z gates.

NOTE: When the Pauli gates are presented as operators in state equations, they are sometimes written differently, as shown:

$ X = \sigma_x = \sigma_1 \\ Y = \sigma_y = \sigma_2 \\ Z = \sigma_z = \sigma_3 $

Each rotates a state by π radians (180°) around the indicated access of the Bloch sphere.

Along with rotation, each gate produces a particular and notable change to a quantum state. Previously we saw how the Pauli-X gate is used to flip a qubit from |0⟩ to |1⟩ and vice versa.

The Pauli Z gate causes a sign flip, so that if a qubit is the state:

$ \ket{\psi} = \alpha \ket{0} + \beta \ket{1} $

Then applying a Pauli-Z gate produces the following:

$ Z \ket{\psi} = \alpha \ket{0} \color{red}{-} \beta \ket{1} $

To transform the |+⟩ state into |-⟩ or vice versa, we apply a Pauli-Z gate. The matrix for the Pauli-Z gate is shown below:

$ Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} $

The result of applying the Pauli-Y gate is a qubit flip and a phase shift. σy = I The Pauli-Y gate maps the state |0⟩ to i|1⟩, and the state |1⟩ to -i|0⟩.

The matrix for the Pauli-Y gate is:

$ Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} $

If we have two qubits in superposition, such as the \(\Phi^+\) state:

$ \ket{\Phi^+} = \frac{\ket{00} + \ket{11}}{\sqrt{2}} $

We can transform \(\ket{\Phi^+}\) to \(\ket{\Psi^-}\) just by using a Pauli-Y gate:

$ Y \ket{\Phi^+} = \ket{\Psi^-} $

Rotating Phase with S and T Gates

Like the Pauli-Z gate (a.k.a., Z gate), the S and T gates also change a qubit's phase by rotating around the z-access of the Bloch sphere. The rotation angles are as follows:

$ \begin{array}{c|l} \text{Gate} & \text{Z-Axis Rotation} \\ \hline Z & \pi \text{ radians } (180^\circ ) \\ S & \frac{\pi}{2} \text{ radians } (90^\circ ) \\ T & \frac{\pi}{4} \text{ radians } (45^\circ ) \end{array} $

Since the Z, S, and T gates don't change the vertical position on the Bloch sphere, the probability distribution is unaffected.

The S gate (a.k.a., the Phase gate or Z90 gate or \(\sqrt{Z}\) gate) maps the state α |0⟩ + β |1⟩ to α |0⟩ + iβ |1⟩. Since i becomes a coefficient of the |1⟩ component, and i2 = -1, the phase of |1⟩ is flipped on the Bloch sphere.

The matrix representation for the S gate is shown below:

$ S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix} $

The reason why the S gate is sometimes refereed to as the \(\sqrt{Z}\) gate is that S2 = Z, as shown:

$ S^2 = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} = Z $

The matrix representation of the T gate is shown below:

$ T = \begin{bmatrix} 1 & 0 \\ 0 & e^{-i \frac{\pi}{4}} \end{bmatrix} $

The S gate is related to the T gate in that S = T2. This is because \(\left( e^{-i \frac{\pi}{4}} \right)^2 = i\).

Rotating State with the R Gates

The Pauli matrices flip a state to the opposite side of the Bloch sphere, while the S and T gates perform a 90° and 45° rotation, respectively. There may be times, however, when you need to rotate a qubit by an arbitrary angle. For this we turn to the R family of gates.

Rx, Ry, and Rz, each rotate state by a specified angle around their respective axes.

The matrix representation of the Rx gate, is shown below:

$ R_x\left(\theta \right) = \begin{bmatrix} \cos{\frac{\theta}{2}} & -i \sin{\frac{\theta}{2}} \\ -i \sin{\frac{\theta}{2}} & \cos{\frac{\theta}{2}} \end{bmatrix} $

The matrix representation of the Ry gate, is shown below:

$ R_y\left(\theta \right) = \begin{bmatrix} \cos{\frac{\theta}{2}} & -\sin{\frac{\theta}{2}} \\ \sin{\frac{\theta}{2}} & \cos{\frac{\theta}{2}} \end{bmatrix} $

Like the S, T, and Z gates, the Rz gate serves to change a state's phase.

The matrix representation of the Rz gate, is shown below:

$ R_z\left(\theta \right) = \begin{bmatrix} e^{-i \frac{\theta}{2}} & 0 \\ 0 & e^{i \frac{\theta}{2}} \end{bmatrix} $

It's worth noting that, as Williams (2011, p.83) points out, you can perform a rotation on the X axis without the use of the Rx gate by combining Ry gate and Rz gate rotations, as the following identities demonstrate:

$ \begin{align} R_x\left( \theta \right) & \equiv R_z\left( - \frac{\pi}{2} \right) \cdot R_y\left( \theta \right) \cdot R_z\left( \frac{\pi}{2} \right) \\[10pt] & \equiv R_y\left( \frac{\pi}{2} \right) \cdot R_z\left( \theta \right) \cdot R_y\left( - \frac{\pi}{2} \right) \end{align} $

There's another gate that could be used for rotating state. I say 'could be' because it has yet to be successfully realized on a real qubit. It's known as the Deutsch gate. The beauty of the gate is that it promises to allow rotation around a vector, projecting from the origin of the Bloch sphere. As Yanofsky & Mannucci (2010, p.182) describe, the Deutsch gate accepts three arguments: dx, dy, and dz, describing the axis of the Bloch sphere where the rotation is to occur.

Swapping Qubits with the Swap Gate

The purpose of the Swap gate is to swap the states of two qubits. So that, for example, |10⟩ becomes |01⟩.

There's a terrific post by Craig Gidney that covers the Quantum Swap gate in depth.

In it Craig Gidney shows how a classical swap operation is reversible.

In a programming language like C# or Java, you can swap the values of variables a and b using a temporary variable, as shown:

int temp = a;
a = b;
b = temp;

An alternative solution that doesn't require a temporary variable, is to XOR the variables three times, like so:

a ^= b;
b ^= a;
a ^= a;

It's not immediately obvious how this works, so let's work through an example. Say a = 810 (which is 10002) and b = 210 (or 00102). The subscript specifies the base. Let's look at how XOR performs the swap:

a ^= b; // a = 1000 ^ 0010 = 1010
b ^= a; // b = 0010 ^ 1010 = 1000
a ^= b; // a = 1010 ^ 1000 = 0010

The swap is made without a temporary variable.

The nice thing about this approach is that the operations are reversible. If we run through the steps again, the values are swapped back. Recall that reversibility is a requirement of quantum gates.

The swap gate can be implemented with three CNOT gates, because, if you recall from Part 2, a CNOT gate is analogous to a classical XOR.

Thus the implementation of the Swap gate, could look like that shown in Figure 1. The quantum circuit symbol is on the left; it's implementation is on the right.

Quantum Swap gate implementation
Figure 1. Quantum Swap gate implementation

In fact, as Craig Gidney points out, the Swap gate can be implemented in a number of ways, including with Z gates and Y gates. I recommend taking a look at his blog post for more depth.

The matrix representing the Swap gate is shown below.

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

We can see that applying the Swap operator to the two qubit state |10⟩ produces the desired result: |01⟩:

$ \begin{align} SWAP \ket{10} &= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \left( \mone \otimes \mzero \right) \\[10pt] & = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} = \ket{01} \end{align} $

Square Root of NOT Gate

The 'Square Root of Not' (\(\sqrt{NOT}\)) gate, is so named because the square of its matrix representation equals that of a NOT gate.

The matrix representation of the \(\sqrt{NOT}\) gate is shown below:

$ \sqrt{NOT} = \ostwo \begin{bmatrix} 1 + i & 1 - i \\ 1 - i & 1 + i \end{bmatrix} $

The \(\sqrt{NOT}\) gate is a single qubit gate. It maps the basis state |0⟩ as shown:

$ \begin{align} \sqrt{NOT} \ket{0} &= \ostwo \begin{bmatrix} 1 + i & 1 - i \\ 1 - i & 1 + i \end{bmatrix} \mzero = \ostwo \begin{bmatrix} 1 + i \\ 1 - i \end{bmatrix} \\[10pt] & = \ostwo \left( \left(1 + i\right) \mzero \otimes \left(1 - i\right) \mone \right) \\[10pt] & = \frac{\left(1 + i\right) \ket{0} + \left(1 - i\right) \ket{1}}{2} \end{align} $

\(\sqrt{NOT} \ket{1}\) is calculated in the same way:

$ \sqrt{NOT} \ket{1} = \frac{\left(1 - i\right) \ket{0} + \left(1 + i\right) \ket{1}}{2} $

To calculate the square of \(\sqrt{NOT}\) matrix, we use our knowledge of complex number multiplication from Part 1.

Squaring √NOT

Multiplying the elements of the \(\sqrt{NOT}\) matrix produces the following products:

$ \begin{align} \left(i + 1\right)\left(i + 1\right) &= 0, \\ \left(i - 1\right)\left(i - 1\right) &= 0, \\ \text{and } \left(i + 1\right)\left(i - 1\right) &= 4 \end{align} $

We use these results to square the \(\sqrt{NOT}\) matrix representation:

$ \begin{align} \left( \sqrt{NOT} \right)^2 &= \ostwo \msnot \ostwo \msnot \\[10pt] & = \frac{1}{4} \begin{bmatrix} 0 & 4 \\ 4 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = NOT \end{align} $

As expected, it produces the NOT gate's matrix:

The circuit diagram symbol for the \(\sqrt{NOT}\) gate is shown in Figure 2.

Square Root Not Gate
Figure 2. Square Root Not Gate circuit symbol

Swapping Half a Qubit's State with the √SWAP Gate

We saw earlier that the SWAP gate is used to interchange the bit values of two qubits. In particular:

$ \begin{align} SWAP \ket{01} &= \ket{10} \\ \text{and } SWAP \ket{10} &= \ket{01} \end{align} $

The \(\sqrt{SWAP}\) gate is also a 2-qubit gate that swaps half the state of one qubit with another's. Its matrix representation is shown below:

$ \sqrt{SWAP} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{2}\left(1 + i\right) & \frac{1}{2}\left(1 - i\right) & 0 \\ 0 & \frac{1}{2}\left(1 - i\right) & \frac{1}{2}\left(1 + i\right) & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $

The \(\sqrt{SWAP}\) gate places the input state |10⟩ half-way to the swapped state |01⟩, effectively creating a superposition at the midpoint between |10⟩ and |01⟩.

Two \(\sqrt{SWAP}\) gates in series is equivalent to a single SWAP gate. We can verify that by squaring the matrix representation:

$ \begin{align} \sqrt{SWAP} \sqrt{SWAP} &= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{2}\left(1 + i\right) & \frac{1}{2}\left(1 - i\right) & 0 \\ 0 & \frac{1}{2}\left(1 - i\right) & \frac{1}{2}\left(1 + i\right) & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}^2 \\[10pt] & = \mswap = SWAP \end{align} $

No working was shown there for squaring the matrix. If you'd like to check for yourself, the following products are used to calculate the final matrix:

$ \left(\frac{1}{2}\left(1 + i\right)\right)^2 = \frac{1}{2}i \\[10pt] \left(\frac{1}{2}\left(1 - i\right)\right)^2 = - \frac{1}{2}i \\[10pt] \left(\frac{1}{2}\left(1 + i\right)\right)\left(\frac{1}{2}\left(1 - i\right)\right) = \frac{1}{2} $

Working with Controlled Gates

All controlled gates have an input that determines whether the gate has any affect on state. We saw this earlier when we looked at the CNOT gate. If the control qubit state is |1⟩ then the gate is applied to the target qubit; otherwise the target qubit is unchanged.

This is evident if we examine the structure of a controlled gate's matrix representation. First off, let's re-examine the CNOT matrix. It looks like this:

CNOT Matrix is applied if control equals 1

The bottom right 2 × 2 matrix is the Pauli-X matrix, and it is applied to the target qubit if the control qubit is 1. Otherwise, the top left 2 × 2 matrix is applied, which you'll notice is an Identity matrix; it has no effect on the target qubit.

This structure is the same for controlled versions of all 2 × 2 gates. We just switch out the bottom right (green) 2 × 2 values with the gate at hand.

For clarity, here's another example. Recall that the Pauli-Y matrix is:

$ Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} $

So, the matrix representing the Controlled Y gate is:

Controlled Pauli-Y Matrix is applied if control equals 1

By the way, the CNOT gate is actually the controlled version of the Pauli-X gate. They're the same thing.

Figure 3 shows the quantum circuit symbols for the Pauli-X (CNOT), Pauli-Y, and Pauli-Z gates.

The control qubit is connected to the target qubit via a vertical line.

Circuit symbols for CNOT gate, Controlled X gate, and Controlled Z gateControlled Y GateControlled Z Gate
Figure 3. Circuit symbols for CNOT gate, Controlled X gate, and Controlled Z gate

NOTE: You may sometimes see a CNOT depicted as a controlled X gate (a square with an X in it).

We can generalize this control mechanism to allow any single qubit gate to be enabled via a control input. This is known as the Controlled-U gate. It is used alongside an existing gate. It's an operator that transforms a 2 × 2 matrix into a controlled matrix.

Observe from its matrix below that a single qubit gate needs to be plugged into it.

$ C(U) = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & u_{00} & u_{01} \\ 0 & 0 & u_{10} & u_{11} \\ \end{bmatrix} $

The way this is employed depends on the environment you're working in. For example, the Q# programming language achieves this with a Controlled statement, allowing it to be applied to any unitary operator that supports it.

Two-Qubit Controlled Gates

So far we've looked at control inputs on single qubit gates. The Controlled-Swap (CSWAP) gate (a.k.a. the Fredkin gate) is a 3-bit gate that adds a control input to a 2-qubit Swap gate.

The CSWAP gate circuit diagram symbol is shown below:

Controlled-Swap Gate Circuit symbol

The CSWAP's matrix is presented below:

$ \newcommand{\mcswap}[0]{\begin{bmatrix} \rb & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \rb & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & \rb & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \rb & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \rb & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \rb & 0 \\ 0 & 0 & 0 & 0 & 0 & \rb & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \rb \end{bmatrix}} CSWAP = \mcswap $

Let's examine the effects of a CSWAP on the state |101⟩, as shown below. The CSWAP maps |101⟩ to |110⟩, as you would expect.

$ CSWAP \ket{101} = \mcswap \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \rb \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \rb \\ 0 \end{bmatrix} $

Working with Doubly-Controlled Gates

In addition to the CNOT, we also have the CCNOT gate (a.k.a. the Toffoli gate) at our disposal. Comparing it to the CNOT gate, the CCNOT gate, has an extra control input; hence the extra 'C' in the name.

It's a three qubit gate that inverts the target qubit if both control qubits are |1⟩. If either of the control qubits are |0⟩, the gate does nothing.

Stated more concisely by Yanofsky & Mannucci (2008, p.172), the CCNOT gate maps |x,y,z⟩ to |x,y,z⊗(x∧y)⟩

The circuit symbol for the CCNOT gate is shown in Figure 4.

CCNOT Gate circuit symbol
Figure 4. CCNOT Gate circuit symbol

The truth table for the CCNOT gate is shown below:

$ \begin{array}{cc|cc} Control & & Target & \\ \hline 1 & 2 & In & Out \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array} $

The matrix representation of the CCNOT gate is an 8 × 8 matrix.

The subject of this doubly-controlled gate is the Pauli-X matrix, seen down in the bottom right corner:

$ CCNOT = \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 & \vc{0} & \vc{1} \\ 0 & 0 & 0 & 0 & 0 & 0 & \vc{1} & \vc{0} \end{bmatrix} $

An example use of the CCNOT gate (demonstrated in Microsoft's Q# Katas), is to switch the probability amplitudes of a 3 qubit quantum state, which is in the following superposition:

$ \ket{\psi} = \alpha \ket{000} + \beta \ket{001} + \gamma \ket{010} + \delta \ket{011} + \epsilon \ket{100} + \zeta \ket{101} + \color{green}{\boldsymbol{\eta}} \ket{110} + \color{blue}{\boldsymbol{\theta}} \ket{111} $

If we apply the CCNOT, we effectively switch the probability amplitudes for |110⟩ and |111⟩, as shown:

$ CCNOT \ket{\psi} = \alpha \ket{000} + \beta \ket{001} + \gamma \ket{010} + \delta \ket{011} + \epsilon \ket{100} + \zeta \ket{101} + \color{blue}{\boldsymbol{\theta}} \ket{110} + \color{green}{\boldsymbol{\eta}} \ket{111} $

Universal Gates

In classical computing, some gates, such as the NOR gate, can be used to construct any other gate. You can use NOR to create AND, OR and NOT gates. The NAND gate is another with this property. NAND and NOR are said to be universal.

In quantum computing, while there is no single gate that is universal, there are sets of gates that are. One such set is:

  • Hadamard
  • Rz
  • CNOT

The Deutsch gate was briefly mentioned earlier in the article. It has the potential to be a universal gate by itself. Though, it doesn't yet exist in practical form.

As Anita Ramanan points out, since any quantum state is able to be achieved using a set of universal gates, it means that "any transformation permitted by quantum physics can be implemented on a quantum computer."

Being able to simulate the quantum universe is something classical computers are not capable of, and it offers the potential of exciting new avenues of research in many fields. This is one of the main motivators for quantum computing.

Conclusion

In this article, we continued our exploration of quantum gates and examined some of the more complex gates. You saw how to rotate and swap qubits, and we delved into controlled gates, which enable you to apply a gate depending on its input. Finally, we discussed the universality of quantum gates.

That concludes the final part in this series. I am, however, working on a new article that demonstrates how to implement a quantum algorithm and use it within a web application. In fact, it was that article that I had intended to write first until I realized that some introductory articles were in order. I'll update this page with a link when it is published.

Thanks for reading and I hope you found this article useful. If so, then I'd appreciate it if you would please rate it and/or leave feedback below.

References

History

  • 27 June 2019
    • Published

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Daniel Vaughan
President Outcoder
Switzerland Switzerland
Daniel Vaughan is a nine-time Microsoft MVP and co-founder of Outcoder, a Swiss software and consulting company dedicated to creating best-of-breed user experiences and leading-edge back-end solutions, using the Microsoft stack of technologies--in particular Xamarin, WPF, and the UWP.

Daniel is the author of Windows Phone 8 Unleashed and Windows Phone 7.5 Unleashed, both published by SAMS.

Daniel is the developer behind several acclaimed mobile apps including Surfy Browser for Android and Windows Phone. Daniel is the creator of a number of popular open-source projects, most notably Codon.

Would you like Daniel to bring value to your organisation? Please contact

Blog | MVP profile | Twitter


Xamarin Experts
Windows 10 Experts

Comments and Discussions

 
-- There are no messages in this forum --
Article
Posted 27 Jun 2019

Tagged as

Stats

3.6K views
7 bookmarked