Quantum Computation

The model of computation defined by the one- and two-qubit gates and the operations of adding ($\mathbf{add}$), measuring ($\mathbf{meas}$) and discarding ( $\mathbf{discard}$) qubits is called the ``quantum network model''. A sequence of instructions for applying these operations is called a ``quantum network''. Quantum computation extends the network model by providing a means for repeating blocks of instructions. Such means can be specified by a formal machine model of computation. There are several such models of classical and quantum computers. One of the best known is the Turing machine, which has a quantum analogue, the quantum Turing machine. This model has its uses for formal studies of computation and complexity, but is difficult to program. Fortunately, as mentioned in Sect. 1, there is no loss of computational power if the means for repeating instructions is provided by a classical computer that can apply gates and other operations to qubits. A general quantum algorithm is a program written for such a computer.

There are three practical methods that can be used to write quantum networks and algorithms. The first is to use the names for the different operations and algebraically multiply them. The second is to draw quantum networks, which are pictorial representations of the sequence of steps in time, somewhat like flowcharts without loops. The third is to use a generic programming language enhanced with statements for accessing and modifying quantum bits. The first two methods work well as long as the sequence is short and we do not use many operations that depend on measurement outcomes or require loops. They are often used to describe subroutines of longer algorithms presented either in words or by use of the third method.

To see how to use the different methods and also to illustrate the power of quantum computation, we work out a short quantum algorithm that solves the following problem:

The Parity Problem: Given is a ``black box'' quantum operation ${\mathbf{BB}}^{({\mathsf {ABC}})}$ that has the following effect when applied to a logical basis state:

$${\mathbf{BB}}^{({\mathsf {ABC}})}\mbox{$\vert\hspace*{-3pt}\... ...3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}},$$ (42)

where $b_{\mathsf {A}}$ and $b_{\mathsf {B}}$ are $0$ or $1$. The actual values of $b_{\mathsf {A}}$ and $b_{\mathsf {B}}$ are unknown. The problem is to determine what ${b}_{\mathsf {A}}$ and ${b}_{\mathsf {B}}$ are by using the black box only once.

The terminology and the definition of the operation ${\mathbf{BB}}^{({\mathsf {ABC}})}$ require explanation. In computation, we say that an operation is a black box or an ``oracle'' if we have no access whatsoever to how the operation is implemented. In a black box problem, we are promised that the black box implements an operation from a specified set of operations. In the case of the parity problem, we know that the operation is to add one of four possible parities (see below). The problem is to determine which parity is added by using the black box in a network. Black box problems serve many purposes. One is to study the differences between models of computation, just as we are about to do. In fact, black box problems played a crucial role in the development of quantum algorithms by providing the first and most convincing examples of the power of quantum computers [13,14]. Some of these examples involve generalizations of the parity problem. Another purpose of black box problems is to enable us to focus on what can be learned from the ``input/output'' behavior of an operation without having to analyze its implementation. This is useful because in many cases of interest, it is very difficult to exploit knowledge of the implementation to determine a desirable property of the operation. A classical example is the well-known satisfiability problem, in which we are given a classical circuit with one output bit and we need to determine whether there is an input for which the output is $\mathfrak{1}$. Instead of trying to analyze the circuit, one can look for and use a general purpose black-box search algorithm to find the ``satisfying'' input.

In the definition of the effect of ${\mathbf{BB}}^{({\mathsf {ABC}})}$, the operation ``$\oplus$'' is addition modulo $2$, so $1\oplus 1=0$, and all the other sums are as expected. As the state symbols now have a numeric meaning, we use the number font for states. To see what $\mathbf{BB}$ does, suppose that ${b}_{\mathsf {A}}$ and ${b}_{\mathsf {B}}$ are both $1$. Then $\mathbf{BB}$ adds (modulo $2$) the parity of the logical state in $\mathsf {AB}$ to the logical state of $\mathsf {C}$. The parity of a logical state is $0$ if the number of $1$'s is even and $1$ if it is odd. The action of $\mathbf{BB}$ for this example is given by:

$${\mathbf{BB}}^{({\mathsf {ABC}})}\mbox{$\vert\hspace*{-3pt}\vert\... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}} = \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{{00}}\mbox{$... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}}$$

$${\mathbf{BB}}^{({\mathsf {ABC}})}\mbox{$\vert\hspace*{-3pt}\vert\... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}} = \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{{01}}\mbox{$... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}}$$

$$= \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{{01}}\mbox{$... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}}$$

$${\mathbf{BB}}^{({\mathsf {ABC}})}\mbox{$\vert\hspace*{-3pt}\vert\... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}} = \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{10}\mbox{$\r... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}}$$

$$= \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{{10}}\mbox{$... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}}$$

$${\mathbf{BB}}^{({\mathsf {ABC}})}\mbox{$\vert\hspace*{-3pt}\vert\... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}} = \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{{11}}\mbox{$... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {C}}}}$$ (43)

The action of the black box is extended to superpositions by ``linear extension''. This means that to apply $\mathbf{BB}$ to a superposition of the logical states, simply apply it to each logical summand and add the results. Different values of $b_{\mathsf {A}}$ and $b_{\mathsf {B}}$ correspond to different parities. For example, if $b_{\mathsf {A}}=1$ and $b_{\mathsf {B}}=0$, then the parity of the state in $\mathsf {A}$ is added to the state in $\mathsf {C}$. In this sense, what is added is the parity of a subset of the two qubits $\mathsf {AB}$. Thus, one way of thinking about the problem is that we wish to find out which subset's parity the black box is using.

We can give an algorithm that solves the parity problem using each of the three methods for describing quantum networks. Here is an algebraic description of a solution, ${\mathbf{qparity}}^{({\mathsf {ABC}})}$, given as a product of quantum gates that involves one use of the black box. We defer the explanation of why this solution works until after we show how to represent the algorithm pictorially using quantum networks.

$${\mathbf{qparity}}^{({\mathsf {ABC}})} = {\mathbf{meas}}^{({\math... ...mathsf {B}})} {\mathbf{H}}^{({\mathsf {A}})} {\mathbf{add}}^{({\mathsf {A}})} .$$

$$\mbox{}$$ (44)

The output of the algorithm is given by the classical outputs of the measurements of qubit $\mathsf {A}$, which yields $b_{\mathsf {A}}$, and qubit $\mathsf {B}$, which yields $b_{\mathsf {B}}$. As is conventional, in writing products of linear operators, the order of application in Eq. 44 is right to left, as in a product of matrices applied to a column vector. This order of terms in a product is, however, counterintuitive, particularly for operations to be performed one after the other. It is therefore convenient to use left to right notation, as is done in describing laser or radio-frequency pulse sequences. One way to make it clear that left to right order is used involves putting dots between gates as in the following version of Eq. 44:

$${\mathbf{qparity}}^{({\mathsf {ABC}})} = {\mathbf{add}}^{({\maths... ...f {A}})} . {\mathbf{H}}^{({\mathsf {B}})} . {\mathbf{meas}}^{({\mathsf {B}})} .$$

$$\mbox{}$$ (45)

In this representation, the first operation is ${\mathbf{add}}^{({\mathsf {A}})}$, the second is ${\mathbf{H}}^{({\mathsf {A}})}$ (the Hadamard gate on qubit $\mathsf {A}$) and so on.

The algebraic specification of the algorithm as products of gates does not make it easy to see why the algorithm works. It is also difficult to see which operations depend on each other. Such dependencies are used to determine whether the operations can be ``parallelized''. Quantum networks make these tasks simpler. The quantum network for the above sequence is shown in Fig. 2.

FIG. 2: Quantum network for solving the parity problem. A quantum network has a (horizontal in this case) line for each qubit. The line can be thought of as the time-line for the qubit and is shown in blue. Each gate is drawn as a box, circle, or other element intercepting the lines of the qubits it acts on. In this case, time runs from left to right. Each qubit's time-line starts at the point where it is added. In this example, the qubits' time-lines end when they are measured, at which point a classical bit (brown time line) containing the measurement outcome is introduced. The operation $\mathbf{BB}$ is illustrated as a black box. The numbers underneath the network refer to checkpoints used to explain how the network solves the parity problem.

To understand how the quantum network of Fig 2 solves the parity problem, we can follow the states as the network is ``executed'' from left to right, using the indicated checkpoints. Using vector notation for the states, at checkpoint 1 the state is

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\m... ...ght)\otimes \left(\!\begin{array}{c}1\\ 0\end{array}\!\right),$$ (46)

where we used Kronecker product notation to denote the states of $\mathsf {A}$, $\mathsf {B}$ and $\mathsf {C}$, in this order. In the next time step, the network involves applying Hadamard gates (Eq. 13) to $\mathsf {A}$ and $\mathsf {B}$ and a $\mathbf{not}$ gate (Eq. 9) to $\mathsf {C}$. At checkpoint 2, this operation results in the state

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\m... ...ght)\otimes \left(\!\begin{array}{c}0\\ 1\end{array}\!\right).$$ (47)

Next, a Hadamard gate is applied to $\mathsf {C}$, so that at checkpoint 3 we have,

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\m... ...!\begin{array}{c}1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\!\right).$$ (48)

The next event involves applying the black box. To understand what happens, note that the effect of the black box can be described as ``conditional on each logical state of $\mathsf {AB}$, if the parity according to $b_{\mathsf {A}}$ and $b_{\mathsf {B}}$ is $1$, then apply $\mathbf{not}$ to $\mathsf {C}$'' The current state of $\mathsf {C}$ is such that if $\mathbf{not}$ is applied, only the sign changes:

$$\mathbf{not}\left(\!\begin{array}{c}1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\!\right) = \left(\begin{array}{cc}0&1\\ 1&0\end{array}\right)\left(\!\begin{array}{c}1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\!\right)$$

$$= -\left(\!\begin{array}{c}1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\!\right).$$ (49)

Now $\mathsf {AB}$ is in a superposition of each of the logical states, and conditional on the logical state and the (hidden) parity, the sign changes. As a result, although the state of $\mathsf {C}$ does not change, a phase is ``kicked back'' to $\mathsf {AB}$. A generalization of this effect is at the heart of A. Kitaev's version of P. Shor's quantum factoring algorithm (Sect. 2.10). At the next checkpoint, and after some arithmetic to check which logical states change sign, we can write the state as

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\m... ...!\begin{array}{c}1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\!\right).$$ (50)

Notice that qubits $\mathsf {A}$ and $\mathsf {B}$ are in orthogonal states for different values of $b_{\mathsf {A}},b_{\mathsf {B}}$. It suffices to apply the Hadamard transform again to $\mathsf {A}$ and $\mathsf {B}$ to get

$$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\m... ...!\begin{array}{c}1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\!\right).$$ (51)

Measurements of $\mathsf {A}$ and $\mathsf {B}$ now reveal the previously unknown $b_{\mathsf {A}}$ and $b_{\mathsf {B}}$.

As can be seen, the visual representation of a quantum network eases the tasks of following what happens. This is why it is used extensively for presenting basic subroutines and algorithms in quantum computation. A guide to the commonly used network elements is given in Fig. 3.

Name

Gate

Symbols

Algebraic

Matrix

Add/prepare

$\mathbf{add}$

	If applied to existing qubit:
	$\{\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mathfrak{0}}\mbox{$\ran... ...t}\langle$}{\mathfrak{1}}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}\}$
	(operator mixture)

$\left(\begin{array}{cc}1&0\\ 0&0\end{array}\right)$ , $\left(\begin{array}{cc}0&1\\ 0&0\end{array}\right)$

Measure

$\mathbf{meas}$

$\{\mathfrak{0}{:}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mathfrak... ...t}\langle$}{\mathfrak{1}}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}\}$

$\left(\begin{array}{cc}1&0\\ 0&0\end{array}\right)$ , $\left(\begin{array}{cc}0&0\\ 0&1\end{array}\right)$

Not

$\mathbf{not},\;\sigma_x$

$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mathfrak{0}}\mbox{$\rangl... ...3pt}\langle$}{\mathfrak{0}}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}$

$\left(\begin{array}{cc}0&1\\ 1&0\end{array}\right)$

Hadamard

$\mathbf{H}$

$e^{-i\sigma_y\pi/4}\sigma_z$

${1\over\sqrt{2}}\left(\begin{array}{cc}1&1\\ 1&-1\end{array}\right)$

Phase

change

$\mathbf{S}(e^{i\phi})$

$e^{i\phi/2}e^{-i\sigma_z\phi/2}$

$\left(\begin{array}{cc}1&0\\ 0&e^{i\phi}\end{array}\right)$

$z$-Rotation

$\mathbf{Z}_{\phi}$

$e^{-i\sigma_z\phi/2}$

$\left(\begin{array}{cc}e^{-i\phi/2}&0\\ 0&e^{i\phi/2}\end{array}\right)$

$y$-Rotation

$\mathbf{Y}_{\theta}$

$e^{-i\sigma_y\theta/2}$

$\left(\begin{array}{cc}\cos(\theta/2)&-\sin(\theta/2)\\ \sin(\theta/2)&\cos(\theta/2)\end{array}\right)$

$x$-Rotation

$\mathbf{X}_{\theta}$

$e^{-i\sigma_x\theta/2}$

$\left(\begin{array}{cc}\cos(\theta/2)&-i\sin(\theta/2)\\ -i\sin(\theta/2)&\cos(\theta/2)\end{array}\right)$

Controlled

not

or

$\mathbf{cnot}$

$\begin{array}{c} \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mathfra... ...}- {\sigma_z}^{({\mathsf {A}})}){\sigma_x}^{({\mathsf {B}})}\pi/2} \end{array}$

$\left(\begin{array}{cccc} 1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{array}\right)$

$ZZ$

rotation

$(\mathbf{ZZ})_{\theta}$

$e^{-i{\sigma_z}^{({\mathsf {A}})}{\sigma_z}^{({\mathsf {B}})}\theta/2}$.

$\left(\!\begin{array}{cccc} e^{-i\theta/2}&0&0&0\\ 0&e^{i\theta/2}&0&0\\ 0&0&e^{i\theta/2}&0\\ 0&0&0&e^{-i\theta/2} \end{array}\!\right)$

Controlled

rotation

$\mathbf{cU}_\theta$

$\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mathfrak{0}}\mbox{$\rangl... ...pace*{-3pt}\vert\hspace*{-3pt}\vert$}e^{-i{\sigma_U}^{({\mathsf {B}})}\theta/2}$

$\left(\begin{array}{@{}cc@{}} \begin{array}{cc}1\;&\;0\\ 0\;&\;1\end{array}&\b... ...\\ 0\;&\;0\end{array}&\mbox{\Large$e^{-i\sigma_U\theta/2}$} \end{array}\right)$

Toffoli gate

$\mathbf{c^2not}$

${\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} {\rm 1\mskip-4.5mu l} {\rm... ...mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\sigma_x}^{({\mathsf {C}})}$

FIG. 3: Quantum network elements.

When designing or describing complicated algorithms for quantum computers, providing everything in terms of quantum networks can become difficult, particularly when an important part of the algorithm consists of computations that are best done on a classical computer. For example, a full description of Shor's algorithm for factoring whole numbers (see Sect. 2.10) includes a significant amount of classical preprocessing, which determines choices made in the quantum algorithm, and classical postprocessing, which computes a factor from the measured result by a continued fraction algorithm. For such algorithms, one can use a programming language similar to Pascal, BASIC or C enhanced with statements to access quantum bits and to apply quantum operations. For algorithm design, computer scientists often use a semi-formal language called ``pseudocode'' [8]. With a simple extension called ``quantum pseudocode'', the algorithm for the parity problem can be written as follows:

Any classical programming language can be extended with statements to access and manipulate quantum registers.

Now that we have looked at the quantum solution of the parity problem, let us consider the question of the least number of black-box applications required by a classical algorithm: Each classical use of the black box can only give us one bit of information. In particular, one use of the black box with input $a_{\mathsf {A}}a_{\mathsf {B}}$ reveals only the parity of $a_{\mathsf {A}}a_{\mathsf {B}}$ according to the hidden parameters $b_{\mathsf {A}}$ and $b_{\mathsf {B}}$. Each use of the black box can therefore only help us distinguish between two subsets of the four possible parities. At least two uses of the black box are therefore necessary. Two uses are also sufficient: To determine which of the four parities is involved, use the black box first with input $a_{\mathsf {A}}a_{\mathsf {B}}=10$ and then with input $a_{\mathsf {A}}a_{\mathsf {B}}=01$. As a result of this argument, one can consider the parity problem as a simple example of a case in which there is a more efficient quantum algorithm than is possible classically. However, it is worth noting that the comparison is not entirely fair: A truly classical oracle answering parity questions or implementing the black box on the states of classical bits is useless to a quantum algorithm. To take advantage of such an algorithm it must be possible to use superpositions that are not implicitly collapsed. Collapse can happen if the oracle makes a measurement or otherwise ``remembers'' the question that it was asked.