Quantum Computation
| Jaden Pieper and Manuel E. Lladser (2018), Scholarpedia, 13(2):52499. | doi:10.4249/scholarpedia.52499 | revision #186567 [link to/cite this article] |
A quantum computer is a machine that exploits quantum phenomena to store information and perform computations.
The chief goal of this article is to provide a brief but comprehensive introduction to quantum computing. It overviews some mathematical underpinnings of quantum computation for readers with only a basic knowledge of linear algebra and probability. However, it does not attempt to be exhaustive nor make an exposition of quantum physics. It further does not attempt to stay current with physical implementations of quantum computers.
After providing a brief historical background, the article introduces the notion of a quantum bit (qubit) and the linear operators (gates) that act on these. It then addresses systems of multiple qubits and their corresponding gates. Along the way, the article covers the essential concepts of separable systems, as well quantum interference and decoherence. It also describes how to represent gates as quantum circuits. To conclude, it explains the underpinnings of two simple but insightful quantum algorithms. A final section suggests further readings for those who wish to delve deeper into quantum computing.
Contents |
Introduction
During a lecture in the early 1980s, Richard Feynman proposed the concept of simulating physics with a quantum computer (Feynman 1982). He postulated that by manipulating the properties of quantum mechanics and quantum particles one could develop an entirely new kind of computer, one that could not be described by the classical theory of computation with Turing machines. Nature does not explicitly perform the calculations to determine the speed of a ball dropped from a tall building; it does so implicitly. Extending this line of thinking, Feynman wondered if one could harness the complex calculations nature performs intrinsically in quantum mechanics to design a computer with more computational power.
New results about the advantages of quantum computers began to filter in soon after Feynman's lecture. By 1985, Deutsch had developed the concept of the Quantum Turing machine, which formalized the theory of quantum computation (Deutsch 1985), and introduced a first toy problem that a quantum computer could in principle solve faster than any known classical algorithm. By 1992, Deutsch and Jozsa proposed a generalized algorithm for this problem (Deutsch and Jozsa 1992) that further demonstrated the potential speed increases quantum computers could provide. Soon, algorithms were being developed for searching (Grover 1996) and integer factorization. In fact, with the exponential speed-up in integer factorization shown by Shor (Shor 1997), and its implications for cryptography and security, the theory of quantum computation had shown its true potential. Research into the development of physical quantum computers began in earnest.
Recently there have been many advancements in physical implementations of the Deutsch-Josza algorithm (Linden et al. 1998), (Gulde et al. 2003), quantum search (Brickman et al. 2005), quantum integer factorization (Vandersypen et al. 2001), (Monz et al. 2016), quantum Fourier Transform (Chiaverini et al. 2005), and programmable quantum computers (Debnath et al. 2016), (Koch et al. 2007). Further, with IBM's Quantum Experience, a programmable quantum computer is now available to the general public.
The Qubit
In classical computing, the unit of information is called a bit. A bit can be in states $0$ or $1$ and, at any moment in time, it is in either of these two states. Likewise, a quantum bit, also called qubit, must be in either of these states but only upon measurement.
The critical distinction between qubits and the classical bits, and what gives quantum computing its power, is that a qubit may be in a superposition of the states $0$ and $1$ before being measured. In a sense—before measurement—the qubit may have simultaneously the values $0$ and $1$. Only when it is measured, it adopts, or as it is more commonly described, collapses to one of these two values. The so-called ket notation is frequently used to describe this bizarre behavior of qubits. A ket is most generally an element of a Hilbert space but, in the case of a system of $n$ qubits, it is a unit vector with $2^n$ complex entries.
In what follows $(a_0,a_1)$, $(a_{00},a_{01},a_{10},a_{11})$, etc. denote column vectors with complex entries.
A qubit $\left|\psi\right\rangle$, which is read as "ket psi," can have different probabilities of being measured in state $0$ or state $1$. For this reason, it is described by a 2-dimensional complex vector, say $\left|\psi\right\rangle=(a_0, a_1)$. The entries in this vector are called amplitudes. By definition, the likelihood of $\left|\psi\right\rangle$ being measured in state $0$ is $|a_0|^2$. Similarly, the likelihood of $\left|\psi\right\rangle$ being measured in state $1$ is $|a_1|^2$. Since a qubit must collapse to one of these two states upon measurement, $|a_0|^2 + |a_1|^2 = 1$. Equivalently, $\left|\psi\right\rangle$ must be a unit vector with respect to the Euclidean norm. We note that quantum mechanics is inherently linear and stochastic; in particular, requiring that kets are unit vectors is just a way to normalize vectors so as to have a probabilistic interpretation.
By convention, $\left|0\right\rangle:=(1,0)$ and $\left|1\right\rangle:=(0,1)$. These are called the measurement or pure states of a single qubit. This is because the qubit $\left|0\right\rangle$ will be measured in state $0$ with probability one. Similarly, $\left|1\right\rangle$ will be measured in state $1$ with probability one. These states are sometimes also called basis states because, for a general qubit $\left|\psi\right\rangle=(a_0, a_1)$, we have \[\left|\psi\right\rangle=\begin{bmatrix} a_0 \\ a_1 \end{bmatrix}=a_0\,\left|0\right\rangle+a_1\,\left|1\right\rangle.\]
Since the amplitudes are complex numbers we can further represent them in polar form as $a_k = r_k e^{i \theta_k}$. Note that neither $\theta_0$ nor $\theta_1$ alone can affect the measurement probabilities of $\left|\psi\right\rangle$. In fact, from the point of view of quantum physics, only the relative phase $\phi:=(\theta_1-\theta_0)$, in short the phase of the qubit, is relevant to describe it. Because of this, it is customary to assume that $\theta_0=0$. In particular, since $(r_0^2+r_1^2)=1$, a general qubit can be uniquely described by a two-dimensional vector of the form: \begin{equation} \left|\psi\right\rangle = \cos\!\left(\frac{\theta}{2}\right)\,\left|0\right\rangle + e^{i\phi}\,\sin\!\left(\frac{\theta}{2}\right) \left|1\right\rangle = \begin{bmatrix} \cos(\theta/2) \\ e^{i\phi}\sin(\theta/2) \end{bmatrix}, \tag{1} \end{equation} for certain $0\le\theta\le\pi$ and $0\le\phi<2\pi$.
Due to the identity in equation (1), it is common to visualize a qubit as a point on the so-called Bloch Sphere (see Figure 1). This alternative representation offers a visual reference of both the phase and the probabilities of measuring a qubit as either of the basis states, represented here as the north and south poles of the sphere. In general, the probabilities of measurement in each state are controlled entirely by the parameter $\theta$, which describes the qubits proximity to either pole. Although the phase $\phi$ has no effect on measurement probabilities, it plays a key role for quantum interference (McIntyre et al. 2012), a phenomenon described in a later section.
Single-qubit Gates
Single-qubit gates are linear operators that transform a qubit into another (possibly the same) qubit; in particular, they may be represented as complex matrices of dimension $(2\times 2)$. As qubits must be unit vectors, quantum gates must be norm preserving and thus unitary. Said another way, all quantum gates can be visualized as rotations along the Bloch sphere.
In what follows, the operator $\oplus$ denotes addition modulo 2. In particular, in the context of bits, we have that: \[ \begin{array}{cccc} 0\oplus 0=0; & 0\oplus 1 =1;& 1\oplus 0 =1;& 1\oplus 1=0. \end{array}\]
A fundamental quantum gate is the so-called "$X$-gate": \[ X := \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}. \;\;\; \] This gate is analogous to the classical NOT operation over bits, which maps a bit $x_1$ to $(x_1 \oplus 1)$, effectively flipping a $0$ into a $1$ and vice versa. Instead, $X(a_0,a_1)=(a_1,a_0)$, for all $(a_0,a_1)$ i.e. the $X$-gate flips the amplitudes of a qubit. For this reason $X$ is also referred to as the NOT gate of quantum computing.
The twist gates form an important class of gates parametrized by a parameter $0\le\alpha\le\pi$ as follows: \[ T(\alpha) := \begin{bmatrix} 1 & 0 \\ 0 & e^{i\alpha} \end{bmatrix}. \] This gate shifts the phase of a quantum state by $\alpha$ radians; in particular, it can be visualized as a rotation about the $z$-axis of the Bloch sphere. Two twist gates are of particular historical relevance. The identity gate is defined as $I:=T(0)$. On the other hand, the so-called "$Z$-gate" is the twist gate associated with $\alpha=\pi$ i.e. $Z := T(\pi)$. The $I$, $X$ and $Z$ linear operators belong to a special family called the Pauli matrices (Kaye et al. 2007).
Another fundamental single-qubit gate is the $(2\times 2)$ Hadamard matrix: \[ H := \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix}. \] This gate maps $\left|0\right\rangle\to(1,1)/\sqrt{2}$ and $\left|1\right\rangle\to(1,-1)/\sqrt{2}$. In particular, upon measurement, $H\left|0\right\rangle$ and $H\left|1\right\rangle$ have a 50/50 chance of being in state $0$ or $1$. The Hadamard gate is therefore useful to generate a uniform superposition of the measurement states. This gate is a common initialization step in many quantum algorithms.
Systems of Multiple Qubits
In what follows, $n\ge1$ is a fixed integer.
A quantum system composed by $n$ distinguishable qubits is also represented as a ket, say $\left|\psi\right>$. Much like in the case of a single qubit, the qubits in the system may be in a superposition of $2^n$ states right until measurement, at which time each qubit collapses into either the state $0$ or $1$. Accordingly, $\left|\psi\right>$ denotes a $2^n$-dimensional complex vector. The entries in this vector are again complex numbers called amplitudes, and their squared magnitudes represent the probabilities of the system collapsing to different states (i.e. configurations of zeroes and ones).
To amplify on the above, let $(k)_2$ denote the $n$-bits binary expansion of an integer $0\le k<2^n$. For instance, when $n=2$, $(0)_2=00$, $(1)_2=01$, $(2)_2=10$, and $(3)_2=11$.
By convention, for each $1\le i\le 2^n$, the $i$-th coordinate of an $n$-qubits system $\left|\psi\right\rangle$ is the amplitude associated with the state $w=(i-1)_2$, which we denote in general as $a_w$. In particular, if we identify binary expansions of length $n$ as elements in $\{0,1\}^n$, and $\left|(i-1)_2\right\rangle$ denotes the $i$-th canonical vector in dimension $2^n$, then \[\left|\psi\right\rangle=\sum_{w\in\{0,1\}^n}a_w\,\left|w\right\rangle.\] The canonical vectors $\left|w\right\rangle$ are again called the measurement, pure, or basis states. This is because for a given $w=(w_1,\ldots,w_n)\in\{0,1\}^n$, $|a_w|^2$ is the probability that, for each $1\le j\le n$, the $j$-th qubit collapses to state $w_j$ upon observation. In particular, we must have $\sum_{w\in\{0,1\}^n}|a_w|^2=1$, i.e. the Euclidean norm of $\left|\psi\right\rangle$ is one.
To fix ideas, in a 2-qubits system, $\left|00\right\rangle=(1,0,0,0)$, $\left|01\right\rangle=(0,1,0,0)$, $\left|10\right\rangle=(0,0,1,0)$, and $\left|11\right\rangle=(0,0,0,1)$. Moreover, a general 2-qubits system is described by a vector of the form: \[\left|\psi\right\rangle =\begin{bmatrix} a_{00}\\ a_{01}\\ a_{10}\\ a_{11} \end{bmatrix} =a_{00}\,\left|00\right\rangle+a_{01}\,\left|01\right\rangle+a_{10}\,\left|10\right\rangle+a_{11}\,\left|11\right\rangle,\] where $|a_{00}|^2+|a_{01}|^2+|a_{10}|^2+|a_{11}|^2=1$. Here, for each $i,j\in\{0,1\}$, $|a_{ij}|^2$ is the probability that the first and second qubit collapse into state into states $i$ and $j$, respectively, upon measurement.
Separable Systems
Describing certain quantum systems with multiple qubits is facilitated by the use of Kronecker products. For given matrices $A\in\mathbb{C}^{r\times c}$ and $B$ of possibly different dimensions, their Kronecker product is the block matrix: \[ A \otimes B := \begin{bmatrix} a_{1,1}\!\cdot\!B & \ldots & a_{1,c}\!\cdot\!B \\ \vdots & \ddots & \vdots \\ a_{r,1}\!\cdot\!B & \ldots & a_{r,c}\!\cdot\!B \end{bmatrix}. \] Although this product is typically non-commutative, it is bilinear and associative. In particular, one may denote the product of several matrices $A_i$, with $1\le i\le n$, simply as $\otimes_{i=1}^n A_i$.
A useful property about Kronecker products is that for matrices $B_i$ of size such that the usual matrix multiplication $A_i\cdot B_i$ is well-defined for each $i$, it applies that: \begin{equation}\tag{2} (\otimes_{i=1}^n A_i)\cdot(\otimes_{i=1}^n B_i) = \otimes_{i=1}^n (A_i\cdot B_i). \end{equation}
A quantum system $\left|\psi\right\rangle$ of $n$ qubits is called separable if it can be represented as the Kronecker product of its qubits. Namely, if $\left|\psi_i\right\rangle$ denotes the $i$-th qubit in the system then $\left|\psi\right\rangle = \otimes_{i=1}^n\left|\psi_i\right\rangle$. This is equivalent to saying that the qubits collapse independently of each other—in a probabilistic sense—upon measurement.
To fix ideas, if $n = 2$ and $\left|\psi_1\right\rangle = (a_0, a_1)$ and $\left|\psi_2\right\rangle = (b_0, b_1)$, then $\left|\psi_1\right\rangle\otimes\left|\psi_2\right\rangle=(a_0b_0,a_0b_1,a_1b_0,a_1b_1)$. In particular, the probability that $\left|\psi_1\right\rangle$ and $\left|\psi_2\right\rangle$ collapse upon measurement to states $i$ and $j$, respectively, is $|a_i|^2\cdot|b_j|^2$ i.e. the product of the probabilities that $\left|\psi_1\right\rangle$ collapses to state $i$ and $\left|\psi_2\right\rangle$ collapses to state $j$. Since this is the case for each $i,j\in\{0,1\}$, the states to which the qubits collapse to upon measurement are independent. The same conclusion applies to systems of more qubits. Thus, in general, a separable quantum system can be thought of as a measurement of probabilistically independent qubits.
It follows that a separable system of $n$ qubits may be represented as a complex vector in a $2n$-dimensional subspace within the $2^n$-dimensional ambient space. In short, we sometimes write $\left|\psi_1\right\rangle\cdots\left|\psi_n\right\rangle$ instead of $\left|\psi_1\right\rangle\otimes\cdots\otimes\left|\psi_n\right\rangle$
A system of qubits that is not separable is called entangled. It is commonly assumed at the start of a quantum computation that all qubits are separable. As the quantum computation proceeds, however, these may become entangled as one performs special operations on pairs of them. We emphasize that separability and entanglement are properties of quantum systems with at least two qubits.
Multi-qubit Gates and Circuits
Quantum gates that act on systems of $n$ qubits can be thought of as $(2^n \times 2^n)$ unitary matrices.
A quantum gate is called separable if it can be represented as the Kronecker product of single-qubit gates. Separable gates keep separable qubits unentangled. A non-separable gate is called entangling.
To fix ideas, consider two unentangled qubits $\left|\psi_1\right\rangle$ and $\left|\psi_2\right\rangle$, and the gate $U:=(X\otimes H)$ which is by definition separable. Because the qubits are unentangled, the system is described by the state $\left|\psi_1\right\rangle\otimes\left|\psi_2\right\rangle$; in particular, from the identity in equation (2), we see that $U(\left|\psi_1\right\rangle\otimes\left|\psi_2\right\rangle)=X\left|\psi_1\right\rangle\otimes H\left|\psi_2\right\rangle$ i.e. the $U$ gate keeps the unentangled qubits separable.
In general, to interpret the action of a gate (separable or not), it is useful to view its columns as inputs and its rows as outputs. For example, displays the matrix associated withe the previous gate $U$, where for convenience we have labeled its columns and rows by the corresponding measurement states. It follows, for instance, that the column corresponding with the input $\left|00\right\rangle$ (i.e. the first column) is associated with the output $(0,0,1,1)/\sqrt{2}$ i.e. the quantum state $(\left|10\right\rangle + \left|11\right\rangle)/\sqrt{2}$.
When working with large systems of qubits, the matrix representation of a quantum gate can be challenging to work with due to an exponentially large number of rows and columns. Because of this, quantum gates are usually represented as diagrams called quantum circuits. These diagrams make it much easier to ascertain the operations as well as the order in which they are applied to each qubit in the system.
To fix ideas, consider the three-qubit circuit in . Each qubit has an associated qubit line, with quantum gates on each line acting on the corresponding qubit. Quantum circuits are read left to right, and due to their resemblance to musical scores, they are sometimes also called quantum scores. The input state for this circuit is $\left|x_1\right\rangle\left|x_2\right\rangle\left|x_3\right\rangle$. The output state is $\left|y\right\rangle$, an 8-dimensional complex vector. Single-qubit gates (such as $X$, $H$ and $I$) are represented as single and vertically aligned boxes along the qubit lines. Instead, gates that take multiple qubits as inputs (such as the previous gate $U$) are represented as boxes spanning multiple qubit lines. The quantum gate associated with this circuit is by definition $(I\otimes U)\cdot(U\otimes I)\cdot(X\otimes H \otimes H)$. Namely: $(I\otimes U)(U \otimes I)(X\otimes H \otimes H)\,\left|x_1\right\rangle\left|x_2\right\rangle\left|x_3\right\rangle=\left|y\right\rangle$.
The most common entangling gate is the controlled-not (CNOT) gate, also denoted as $\wedge_1 (X)$, which acts over two qubits. It is displayed in matrix form in Figure 4, where we have explicitly labeled its columns and rows to interpret its action better. It follows that when the control qubit is in state $\left|0\right\rangle$ the identity gate is applied to the target qubit, however, when the control is in state $\left|1\right\rangle$ the NOT gate is applied to the target. In other words, when $x_1,x_2\in\{0,1\}$, CNOT transforms $\left|x_1\right\rangle\left|x_2\right\rangle$ into $\left|x_1\right\rangle\left|x_1\oplus x_2\right\rangle$; in particular, it encodes the exclusive-or of the control and target qubits into the target qubit. The standard quantum circuit representation of the CNOT gate can be seen in Figure 5.
It turns out CNOT is the only entangling gate required for a quantum computer. This is because the gates $H$, $T(\pi/4)$, and $\wedge_1(X)$ are universal for quantum computing (Kaye et al. 2007). Namely, one can approximate any quantum gate using a quantum circuit composed only of these gates. (Since in finite dimension all norms are equivalent, there is no need to define the norm used for the approximation explicitly.)
We mention in passing that the notation of $\wedge_1(X)$ for the CNOT gate is part of a more general construct in quantum computing. Indeed, for any integer $k\ge1$ and single qubit gate $U$ of the form $U=V^{k+1}$, with $V$ a unitary operator, $\wedge_k(U)$ denotes a gate on $(k+1)$ qubits ($k$ controls and one target) such that the gate $U$ is applied to the target qubit if and only if all the control qubits are in state $\left|1\right\rangle$. Otherwise, the target qubit is left unchanged.
Quantum Interference and Decoherence
A fundamental idea in quantum computing is to control the probability a system of qubits collapses into particular measurement states. Quantum interference, a byproduct of superposition, is what allows us to bias the measurement of a qubit toward a desired state or set of states.
To fix ideas, consider the qubit in superposition $\left|\psi\right\rangle=(1,-1)/\sqrt{2}$ and note that $H\left|\psi\right\rangle=\left|1\right\rangle$. In other words, if the Hadamard gate is applied to $\left|\psi\right\rangle$ then it will be observed in the pure state $\left|1\right\rangle$ with theoretical certainty upon measurement. This is quantum interference at its purest.
Observe, however, that even though $\left|\psi\right\rangle$ may be measured in state $\left|0\right\rangle$ and $\left|1\right\rangle$ with equal probability, this is not the same as saying that $H\left|\psi\right\rangle=H\left|0\right\rangle$ with probability $1/2$, and $H\left|\psi\right\rangle=H\left|1\right\rangle$ with probability $1/2$. In fact, neither $H\left|0\right\rangle$ nor $H\left|1\right\rangle$ equals a pure state. Further, for $H\left|\psi\right\rangle=H\left|0\right\rangle$ and $H\left|\psi\right\rangle=H\left|1\right\rangle$ with equal probability, $\left|\psi\right\rangle$ should have been incidentally measured before the application of the Hadamard gate. (After an unintended measurement, a qubit is said to be in a mixed state.) Quantum interference may therefore be disrupted by an incidental measurement of a system qubit. This phenomenon is called quantum decoherence and can be a major source of error when working with physical quantum computers.
Quantum Algorithms
Deutsch's Algorithm
In 1985, a few years after Feynman's famous lectures on quantum computing (see Introduction), David Deutsch published a paper in which he formalized quantum complexity theory and quantum Turing machines (Deutsch 1985). This made it possible to compare the computational speed of classical computers against theoretical quantum machines. In the same paper, Deutsch posed a problem, and a quantum algorithm to solve it, that hinted at potential speedups of quantum computing in comparison to known classical algorithms.
Deutsch's algorithm is one of the most straightforward quantum algorithms. Thus, it serves as a prototype to how to think about and approach quantum algorithms. Its problem statement is as follows.
Problem: Given $f:\{0,1\}\rightarrow\{0,1\}$, determine if $f$ is a constant function with the least number of evaluations of this function.
Recall that $\oplus$ represents addition modulo 2 or, equivalently, the exclusive-or operation (XOR).
Whereas a classical computer could only solve this problem with two evaluations (i.e. by evaluating both $f(0)$ and $f(1)$), Deutsch showed that a quantum computer could in principle extract the value of $f(0) \oplus f(1)$ at once, taking advantage of superposition to evaluate $f(0)$ and $f(1)$ simultaneously. Since $f(0) \oplus f(1)=0$ if and only if $f$ is constant, the quantum algorithm should require just one evaluation of the function $f$ to determine whether it is constant or not.
The algorithm relies on the quantum gate $U_f\left|x\right\rangle\left|y\right\rangle:=\left|x\right\rangle\left|f(x)\oplus y\right\rangle$, for $x,y\in\{0,1\}$, which extends to arbitrary kets because of linearity. We note this gate is a particular instance of a more general class of gates that encode Boolean functions. In this context, $\left|x\right\rangle$ is called the control qubit. Although the definition of this quantum gate requires evaluating the function twice, Deutsch's algorithm demonstrates nonetheless how one could in principle determine if $f$ is constant or not, only through the manipulation of a single quantum gate.
Observe that if $\left|y\right\rangle=H\left|1\right\rangle$ then \begin{eqnarray*} U_f\left|0\right\rangle\left|y\right\rangle &=& \frac{U_f\left|0\right\rangle\left|0\right\rangle-U_f\left|0\right\rangle\left|1\right\rangle}{\sqrt{2}}=\frac{\left|0\right\rangle\left|f(0)\right\rangle-\left|0\right\rangle\left|f(0)\oplus1\right\rangle}{\sqrt{2}}=(-1)^{f(0)}\left|0\right\rangle\left|y\right\rangle;\\ U_f\left|1\right\rangle\left|y\right\rangle &=& \frac{U_f\left|1\right\rangle\left|0\right\rangle-U_f\left|1\right\rangle\left|1\right\rangle}{\sqrt{2}}=\frac{\left|1\right\rangle\left|f(1)\right\rangle-\left|1\right\rangle\left|f(1)\oplus1\right\rangle}{\sqrt{2}}=(-1)^{f(1)}\left|1\right\rangle\left|y\right\rangle. \end{eqnarray*} Consequently, if $\left|x\right\rangle=H\left|0\right\rangle$ then \[U_f\left|x\right\rangle\left|y\right\rangle=\frac{(-1)^{f(0)}\left|0\right\rangle+(-1)^{f(1)}\left|1\right\rangle}{\sqrt{2}}\left|y\right\rangle=(-1)^{f(0)}\frac{\left|0\right\rangle+(-1)^{f(0)\oplus f(1)}\left|1\right\rangle}{\sqrt{2}}\left|y\right\rangle.\] Thus, up to a phase shift, after the application of $U_f$ the control qubit will be in state $(1,1)/\sqrt{2}$ if $f$ is constant but state $(1,-1)/\sqrt{2}$ otherwise. Since these corresponds to the columns of the Hadamard gate, applying $H$ to the control qubit will then map it to $\left|0\right\rangle$ if $f$ is constant and to $\left|1\right\rangle$ otherwise. In other words: \[(H\otimes I)U_f\left|x\right\rangle\left|y\right\rangle=\left\{\begin{array}{lcl} \left|0\right\rangle\left|y\right\rangle &,& \hbox{ if } f(0)=f(1);\\ \left|1\right\rangle\left|y\right\rangle &,& \hbox{ if } f(0)\ne f(1).\\ \end{array}\right.\] Finally, since $\left|y\right\rangle=H\left|1\right\rangle=HX\left|0\right\rangle$, the circuit in Figure 6 implements the above procedure.
Grover's Algorithm
Grover's algorithm is often described as "finding a needle in a haystack.'' It is a remarkable algorithm in that it demonstrates a quantum computer's ability to find a particular item (the needle) in a large list of items (the haystack), with a quadratic speedup compared to the best-known classical algorithm. Much like Deutsch's algorithm, however, it is more of a theoretical than a practical exercise. We expand on this remark at the end.
In abstract terms, Grover's algorithm addresses the following problem.
Problem: Define $[N]:=\{0,\ldots,2^n-1\}$, for some integer $n\ge1$. Given a uniformly at random permutation $\sigma:[N]\to[N]$, determine the index $w\in[N]$ such that $\sigma(w)=1$.
With a traditional mindset, all one can do is to evaluate $\sigma$ sequentially until finding an index that evaluates it to $1$. Since $\sigma$ is random, the average number of queries is $N/2$ i.e. $O(N)$. In contrast, we explain ahead that Grover's quantum algorithm can perform the same task in $O(\sqrt{N})$ evaluations using $n$ qubits (Grover 1996). There is, however, an essential distinction between these approaches: whereas the classical algorithm is guaranteed to succeed, the quantum algorithm can only achieve a high probability of success but not guarantee it.
Identifying $[N]$ with $\{0,1\}^n$, Grover's algorithm exploits superposition to, in some sense, evaluate $\sigma$ at all $w\in[N]$ at once. Figure 7 displays the quantum circuit associated with it. The circuit is initialized with $n$ qubits that are put in uniform superposition using Hadamard gates. It then proceeds with repeated applications of an $n$-qubit gate $G$, called the Grover iterate. This is defined as $G=D\,S_w$, where $D$ is called the diffusion transform and $S_w$ the quantum oracle.
As mentioned earlier, Grover's algorithm is more of a theoretical than a practical exercise. This is because the definition of the quantum oracle necessitates knowing in advance the index $w$ such that $\sigma(w)=1$. Indeed, the quantum oracle flips the amplitude of the measurement state associated with the unique $w\in[N]$ such that $\sigma(w)=1$. Namely: \[S_w\left|x\right\rangle:=\left\{\begin{array}{ccl}-\left|x\right\rangle &,& \hbox{ if } \left|x\right\rangle=\left|w\right\rangle \\ \left|x\right\rangle &,& \hbox{ otherwise.}\end{array}\right.\] This operator is unitary because it corresponds to a diagonal matrix with $\pm 1$ entries along the diagonal.
On the other hand, the diffusion transform inverts the amplitudes of a ket about its average amplitude. More specifically, if $\left|\psi\right\rangle=\sum_{x\in\{0,1\}^n}a_x\left|x\right\rangle$ then \[D\left|\psi\right\rangle:=\sum_{x\in\{0,1\}^n}\big(\bar{a}+(\bar{a}-a_x)\big)\,\left|x\right\rangle,\hbox{ where }\bar a:=\frac{1}{2^n}\sum_{x\in\{0,1\}^n}a_x.\] This operator is also unitary because $\sum_{x\in\{0,1\}^n}|\bar{a}+(\bar{a}-a_x)|^2=\sum_{x\in\{0,1\}^n}|a_x|^2=1$. In fact, it can be represented in terms of other quantum gates as follows: $D=H^{\otimes n}\cdot S_{0^n}\cdot H^{\otimes n}$ (Grover 1996).
Together, the quantum oracle and diffusion transform amplify the amplitude of the unique measurement state associated with the index $w\in[N]$ such that $\sigma(w)=1$ (see Figure 8). We note, however, that running the quantum algorithm for too long my decrease its success probability, necessitating a bound for its optimal number of iterations. In fact, it is shown in (Boyer et al. 1998) that after $j$ iterations of the $G$-gate the amplitude associated with state $w$ is $\sin((2j+1)\theta)$, where $0\le\theta\le\pi/2$ is such that $\sin^2(\theta)=1/N$. When $N$ is large, $\theta\sim1/\sqrt{N}$. In particular, since the amplitude associated with $w$ is maximized for $j$ such that $(2j+1)\theta\sim\pi/2$, the optimal number of iterations is $j\sim\pi\sqrt{N}/4$ (Boyer et al. 1998). Thus, Grover's algorithm determines with high probability the index $w$ such that $\sigma(w)=1$ in $O(\sqrt{N})$ iterations.
As a closing remark, we note that despite not being practical, Groover's algorithm exemplifies how the sole manipulation of amplitudes may offer significant speed-ups on problems that become rapidly untractable in standard computational settings.
Final Remarks and Further Readings
The principal goal of this article is to introduce some of the most fundamental aspects of quantum computing in a concise and self-contained manner to facilitate their learning. By no means, however, does this represent a complete account of the subject. A more comprehensive, yet still not exhaustive introduction, including a brief prelude to quantum physics and on how to program IBM's public quantum computer, can be found in the recent MS thesis by Pieper (2017). We note that IBM's Quantum Experience allows users to experiment with and create their own quantum circuits, with a welcoming introduction to the theory. It also gives detailed references on a physical implementation of a quantum computer, and has an active community to answer questions.
Some excellent introductions, including helpful expositions of popular quantum algorithms, are the textbooks by Kaye et al. (2007), and Nielsen and Chuang (2011). On the other hand, the textbook by McIntyre et al. (2012) gives good examples and intuitions on the physics of quantum particles.
For somewhat informal yet fun expositions of this and other related subjects, the books by Baggott (2011), Aaronson (2013), and Gisin (2014) are highly recommended. Moreover, Scott Aaronson's blog provides an informal, yet nuanced perspective on quantum computing and addresses many common misconceptions about this increasingly popular topic.
In conclusion, we would like to note that there are other models of quantum computation not based on qubits, such as adiabatic quantum computation, one-way quantum computing, quantum annealing, and topological quantum computing, among others. Moreover, much controversy exists around the physical feasibility of building a quantum computer, and there has been much debate about the real quantum nature, or absence of it, of architectures such as D-wave.
Acknowledgements
This work is based on the MS thesis by Pieper (2017), which was partially funded by the NSF EXTREEMS-QED grant #1407340. The authors would also like to thank the two reviewers for their careful reading and valuable comments.
References
- S. Aaronson. Quantum Computing Since Democritus. Cambridge University Press, 2013.
- S. Aaronson's Blog. https://www.scottaaronson.com/blog/
- J. Baggott. The Quantum Story: A history in 40 moments. Oxford University Press, 2011.
- M. Boyer, G. Brassard, P. Hoyer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4-5):493–505, 1998.
- K.-A. Brickman, P. C. Haljan, P. J. Lee, M. Acton, L. Deslauriers, and C. Monroe. Implementation of Grover’s quantum search algorithm in a scalable system. Physical Review A, 72(5):050306, 2005.
- J. Chiaverini, J. Britton, D. Leibfried, E. Knill, M. D. Barrett, R. B. Blakestad, W. M. Itano, J. D. Jost, C. Langer, R. Ozeri, et al. Implementation of the semiclassical quantum Fourier transform in a scalable system. Science, 308(5724):997–1000, 2005.
- S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe. Demonstration of a small programmable quantum computer with atomic qubits. Nature, 536(7614):63–66, 2016.
- D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 400(1818):97–117, 1985.
- D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 439(1907):553–558, 1992.
- R. P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6):467–488, 1982.
- N. Gisin. Quantum Chance: Nonlocality, Teleportation and Other Quantum Marvels. Copernicus, New York, 2014.
- L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pages 212–219. ACM, 1996.
- S. Gulde, M. Riebe, G. P. T. Lancaster, C. Becher, J. Eschner, H. H ̈affner, F. Schmidt-Kaler, I. L. Chuang, and R. Blatt. Implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer. Nature, 421(6918):48–50, 2003.
- IBM Quantum Experience. https://quantumexperience.ng.bluemix.net/qstage/#/user-guide. Accessed: 2017-04-01.
- P. Kaye, R. Laflamme, and M. Mosca. An Introduction to Quantum Computing. Oxford University Press, 2007.
- J. Koch, T. M. Yu, J. Gambetta, A. A. Houck, D. I. Schuster, J. Majer, A. Blais, M. H. Devoret, S. M. Girvin, and R. J. Schoelkopf. Charge-insensitive qubit design derived from the Cooper pair box. Physical Review A, 76:042319, Oct 2007.
- N. Linden, H. Barjat, and R. Freeman. An implementation of the Deutsch-Jozsa algorithm on a three-qubit NMR quantum computer. Chemical Physics Letters, 296(12):61 – 67, 1998.
- D. H. McIntyre, C. A. Manogue, and J. Tate. Quantum Mechanics: A Paradigms Approach. Pearson, 2012.
- T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, and R. Blatt. Realization of a scalable Shor algorithm. Science, 351(6277):1068–1070, 2016.
- M. A. Nielsen, and I. L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2011.
- J. K. Pieper. Unentangling Quantum Algorithms for Mathematicians and Engineers. Master’s thesis, University of Colorado, Boulder, 2017.
- P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–26, 10 1997.
- L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature, 414(6866):883–887, 2001. and/or and/or and/or and/or
