Quantum Computing

Part of a quantum computer designed by D-Wave

Quantum computing refers to using the principles of quantum mechanics to manipulate information and perform computations. Algorithms designed for quantum computers take advantage of the fact that quantum-mechanical systems may exist in a superposition of states to solve certain problems up to exponentially faster than classical computers. Once quantum computing becomes scalable, it will have enormous practical implications in a wide variety of fields including cryptography, computational chemistry, mathematics, and computer science. For example, quantum algorithms would be able to efficiently factor products of large prime numbers, thus breaking RSA encryption, which is widely used to protect online data. Quantum computers would also be superior at modeling quantum systems like the interactions of molecules.

The famous physicist Richard Feynman was one of the first to recognize the enormous potential of quantum computing. In the early 1980s, he observed that a classical computer would require $2^n$ states to describe a set of $n$ spin-$\frac12$ particles such as electrons, while a quantum computer requires only $n$ states. Quantum computers thus have the ability to perform some computations using exponentially fewer states than classical computers. This violates a well-known hypothesis in computing theory sometimes called the Strong Church-Turing thesis, which roughly asserts that if a computation can be performed efficiently by any means then a classical computer can also perform it efficiently.

An early barrier to the development and viability of quantum computing was the no-cloning theorem discovered in 1982 by William Wootters, Wojciech Zurek, and Dennis Dieks, which states that it is impossible to create a guaranteed identical copy of any quantum system. This prevents use of classical error correction techniques for quantum algorithms, since such techniques rely on making backup copies of states as templates to fix errors. Without error correction, thermal fluctuations and other sources of noise cause quantum systems to decohere and lose information. In 1995, however, Peter Shor and Andrew Steane discovered a method of quantum error correction that circumvents this problem.

Since 1994, a number of quantum algorithms (described below) that demonstrate dramatic speedup over classical algorithms have been discovered. The first experimental implementations of these algorithms began around 1998 and have continued into the twenty-first century. Most quantum computers invented so far have only been able to manipulate a small number of quantum states, on the order of tens at once. Since 2006, however, there has been an explosion in different types of quantum computing technology. Particularly well-publicized have been the commercially available quantum devices developed by the British Columbia-based company D-Wave Systems, which in 2015 claimed to have developed a quantum computer capable of manipulating over one thousand quantum states simultaneously [1]. These devices, however, are not computationally universal (they cannot execute generic quantum algorithms) but rather solve a particular kind of optimization problem called quantum annealing, of which only a particular subset can be solved more efficiently than classically. Popular implementations of more universal quantum computers currently under study include solid-state quantum computers involving nitrogen impurities in diamond, semiconductor quantum dot-based computers that isolate electron spins via electric fields, superconducting quantum computers, trapped ion quantum computers, and more.

Classical computers represent information in terms of bits, which can take one of two states: "0" or "1". Algorithms execute by manipulating bits with gates, which alter the states of the bits. Physically, a bit may be implemented by a switch between one of two voltage levels in a device, and a gate is a particular piece of circuitry.

Classically, some common gates are the NOT gate and the AND gate. The NOT gate acts on one bit to map "0" to "1" and vice versa. The AND gate takes two bits as input, mapping them to "1" if both input bits are "1" and otherwise mapping them to "0".

The NAND (not-AND) gate takes two bits $x$ and $y$, acts on them with AND, and acts on the result with NOT. Write down the outputs of the NAND gate for all possible choices of input bits $x$ and $y$.

---

The below table gives the output of the NAND gate for all possible choices of input bits $x$ and $y$: $$\begin{array}{c|c|c} x&y&x\: \text{NAND}\: y \\ \hline 0&0&1 \\ 0&1&1\\ 1&0&1\\ 1&1&0 \end{array}$$

To see how these results were generated, consider the two input bits $x = 0$ and $y=1$. The AND gate maps $(0,1)$ to $0$. The NOT gate then maps $0$ to $1$, as displayed in the table. The process for computing NAND for the other choices of input bits is similar. $_\square$

The NAND gate is computationally universal. This means that any function on any number of bits can be constructed using only NAND gates operating on two bits at once. However, the action of the NAND gate is not reversible, because it takes two inputs to one output and the outputs are not unique. Since any reversible gate can be implemented on a quantum computer, it is often convenient to work with reversible gates in quantum computing. The NAND gate can be simulated by a reversible gate that takes three bits as input called the Toffoli gate. The Toffoli gate maps $(x,y,z)$ to $\big(x,y,(z+x*y) \text{ mod}\: 2\big)$. When $z=1$, the Toffoli gate maps $(x,y,1)$ to $(x,y,x\:\text{NAND}\:y)$. Since quantum computers can implement the Toffoli gate, quantum computers are classically computationally universal, although the Toffoli gate alone is not sufficient to implement any function on quantum states.

Quantum computers, like classical computers, rely on gates acting on states in a two-state system. A simple physical prototype for this two-state system is the electron, which can have a spin pointing up or down. As a convention in quantum mechanics, these states are typically written as $|0\rangle$ and $|1\rangle$. Unlike classical computers, quantum computers are not confined to manipulate solely these two states. Superpositions of states, such as $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$, are also possible. Because superposition is a quantum property, these two-state systems are called quantum bits or more commonly qubits.

States of qubits can also be represented as two-dimensional vectors, e.g.

$$|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad |1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}.$$

This is important because it is easy to mathematically represent gates as $2\times 2$ matrices acting on qubits by multiplying the corresponding vectors.

An arbitrary state $|\Psi\rangle$ of a qubit can be written as a linear combination of $|0\rangle$ and $|1\rangle$ with complex coefficients, that is

$$|\Psi\rangle = a|0\rangle + b|1\rangle, \quad a,b \in \mathbb{C}.$$

For a classical computer to describe an arbitrary quantum state requires two complex numbers; similarly, to model $n$ arbitrary quantum states on a classical computer requires $2^n$ complex numbers and therefore a minimum of $2^n$ bits. A quantum computer requires only $n$ qubits to describe $n$ states, by definition. Modeling quantum systems such as those useful for chemistry on a classical computer thus will require time growing exponentially with the number of states $n$ that one wants to model, while modeling the same system on a quantum computer only requires time growing linearly with $n$. For this basic example, the difference in computation time is commonly denoted by saying the classical computer takes $\mathcal{O}(2^n)$ time while the quantum computer takes $\mathcal{O}(n)$ time. This is an example of big O notation, which roughly communicates how the computation time grows with an increasing number of inputs $n$.

An important gate in quantum computing is the Hadamard gate. This gate, denoted by $H$, has the representations both in matrix form and state notation as below:

$$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \frac{1}{\sqrt{2}} \sum_{x,y\, \in \{0,1\}} (-1)^{xy} |x\rangle\langle y|.$$

Show that the Hadamard gate rotates both of the states $|0\rangle$ and $|1\rangle$ into an equal superposition of the two.

---

Acting directly on the vector representation of each state with the matrix representation of the Hadamard gate,

$$\begin{aligned} H|0\rangle &= \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \frac{|0\rangle + |1\rangle}{\sqrt{2}} \\\\ H|1\rangle &= \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ -1 \end{pmatrix} = \frac{|0\rangle - |1\rangle}{\sqrt{2}}. \end{aligned}$$

Both are equal superpositions of $|0\rangle$ and $|1\rangle$ as claimed. $_\square$

In general, the Hadamard gate maps $n$ qubits all in the same state to an equal superposition of every possible state of the $n$ qubits. This makes the Hadamard gate an essential component of quantum algorithms such as those described below.

Quantum algorithms are often (though not always) inherently probabilistic in that they are guaranteed to obtain the correct answer only a certain percentage of the time. However, they can be iterated repeatedly to obtain greater confidence in a predicted answer. The benefit of quantum algorithms is their enormous increase in computational efficiency for certain problems. Below are summarized some of the major quantum algorithms in terms of historical significance and practical importance.

Grover's Algorithm:

Grover's algorithm is designed to solve the unstructured search problem. This problem can be expressed formally as follows: given a function that maps $N$-digit binary values to either $0$ or $1$ such that one unique binary value $x$ is mapped to $1$, find $x$. More simply, the problem asks to identify the unique input corresponding to a given output of any function, i.e. to invert that function.

The implementation of Grover's algorithm is relatively simple. First, apply the Hadamard gate to a set of $n$ qubits to achieve a uniform superposition of states, where $N=2^n$. Next, a certain gate is constructed that rotates the uniform superposition towards the state $|x\rangle$ corresponding to $x$. After $\mathcal{O}\big(\sqrt{N}\big)$ applications of this gate, measuring the state will yield $|x\rangle$ with high probability. This is an improvement on the $\mathcal{O}(N)$ steps that a random classical algorithm would take in the best-case scenario to find $x$.

Applications of Grover's algorithm include finding the minimum of an unsorted list of integers, determining whether or not a graph is connected, and pattern matching strings within a text [3].

In Grover's algorithm, a gate $R$ is constructed that rotates the uniform superposition of states towards $|x\rangle$, where

$$R = \begin{pmatrix} 1 - \frac{2}{N} & \frac{2\sqrt{N-1}}{N} \\ - \frac{2\sqrt{N-1}}{N} & 1 - \frac{2}{N}\end{pmatrix} .$$

Show that $R$ is in fact a rotation matrix.

---

Since $1 - \frac{2}{N}$ is between $0$ and $1$, let $\cos \theta = 1 - \frac{2}{N}$, which is true for some $\theta$. Then one must only show that $\sin \theta= \frac{2\sqrt{N-1}}{N}$ for the same $\theta$. This is true as long as both quantities satisfy the identity $\cos^2 \theta + \sin^2 \theta = 1$. Checking this directly,

$$\begin{aligned} \left( 1 - \frac{2}{N}\right)^2 + \left(\frac{2\sqrt{N-1}}{N}\right)^2 &= 1 + \frac{4}{N^2 } - \frac{4}{N} + \frac{4(N-1)}{N^2} \\ &= 1 + \frac{4}{N^2 } - \frac{4}{N} + \frac{4}{N} - \frac{4}{N^2} = 1. \end{aligned}$$

Therefore, $\sin \theta= \frac{2\sqrt{N-1}}{N}$ for this $\theta$. The matrix $R$ can then be written as

$$R = \begin{pmatrix} \cos \theta & \sin \theta \\ - \sin\theta & \cos\theta\end{pmatrix},$$

which is a rotation matrix as claimed. $_\square$

Simon's Algorithm:

Simon's algorithm solves the problem of period-finding, i.e. calculating the period $T$ of a function $f$ that satisfies $f(x) = f(x+T)$ for all $x$. This was an important subproblem in Shor's algorithm, and offered an exponential speedup: Simon's algorithm runs in $\mathcal{O}(n)$ on a quantum computer and $\mathcal{O}\big(2^{n/2}\big)$ on a classical computer.

The process by which Simon's algorithm works is as follows: beginning with a uniform superposition of states over $n$ qubits, compute the function $f$ on the superposition, measure the answer, and apply the Hadamard gate to the $n$ resulting qubit states. If the period $T$ is represented as a vector $\vec{T}$ that is $n$ bits in length, measuring the state after applying the Hadamard gate yields a vector orthogonal to $\vec{T}$ with high probability. After $\mathcal{O}(n)$ iterations of this process, one obtains $n-1$ vectors orthogonal to $\vec{T}$. Since $\vec{T}$ lives in an $n$-dimensional vector space, this is sufficient to identify the period $T$.

Shor's Algorithm:

Shor's algorithm is important in that it solves the difficult problem of integer factorization. Classically, the best existing algorithm for this problem is called the general number field sieve, which runs in $\mathcal{O}\big(\exp(\log(N)^{1/3} \text{poly} (\log \log N))\big)$, where $\text{poly}$ represents a complicated polynomial. Shor's algorithm demonstrates a remarkable speedup to $\mathcal{O}\big((\log N)^3]\big)$.

Shor's algorithm first takes advantage of the well-known Euclidean algorithm for computing the greatest common divisor (GCD), and then uses Simon's algorithm to obtain the exponential speedup. Given an integer $N$, one can pick a random number $k < N$ and compute $\text{gcd}(k,N)$. If $k$ is a factor of $N,$ the problem is solved; otherwise, $\text{gcd}(k,N)$ must equal one. Suppose $T$ is the order of $k$, that is, $T$ is the smallest positive integer such that $k^T \:\text{mod}\:N = 1$. Then as long as $T$ is even and $k^{T/2}+1$ is not a multiple of $N$ (which occurs with high probability), both $\text{gcd}\big(k^{T/2}+1,N\big)$ and $\text{gcd}\big(k^{T/2}-1,N\big)$ are factors of $N$.

The problem is thus solved as long as one can find the $T$ corresponding to a given $k$. To compute $T$, consider the function $f(x) = k^x\:\text{mod}\:N$. Since:

$$f(x+T) = k^{x+T}\:\text{mod}\:N = k^T k^{x}\:\text{mod}\:N = k^{x}\:\text{mod}\:N = f(x),$$

the problem of computing $T$ is thus reduced to period-finding for this function $f$. Applying Simon's algorithm solves the problem.

[1] D-Wave Systems Breaks the 1000 Qubit Quantum Computing Barrier. June 22, 2015. Accessed January 19, 2016. http://www.dwavesys.com/press-releases/d-wave-systems-breaks-1000-qubit-quantum-computing-barrier.

[2] Bone, Simon and Matias Castro. A Brief History of Quantum Computing. Surveys and Presentations in Information Systems Engineering, Volume 4, 1997. Accessed January 19, 2016. http://www.doc.ic.ac.uk/~nd/surprise_97/journal/vol4/spb3/#1.1%20Quantum%20computer%20basics.

[3] Montanaro, Ashley. Quantum algorithms: an overview. npj Quantum Information 2, 15023 (2016). Accessed January 19, 2016. http://www.nature.com/articles/npjqi201523.