# Basic concepts in quantum computation

{{ArticleInfo | title = Basic concepts in quantum computation | author = Artur Ekert, Patrick Hayden, Hitoshi Inamori | arxiv = quant-ph/0011013 | journal = lectures given at les Houches Summer School on "Coherent Matter Waves", July-August 1999 | keywords = basic concepts, quantum computing | comments = converted to wiki format by Burgarth 22:37, 8 Jun 2005 (BST) }} = Qubits, gates and networks = Consider the two binary strings, $011,$ $111.$ The first one can represent, for example, the number $3$ (in binary) and the second one the number $7.$ In general three physical bits can be prepared in $2^\left\{3\right\}=8$ different configurations that can represent, for example, the integers from $0$ to $7.$ However, a register composed of three classical bits can store only one number at a given moment of time. Enter qubits and quantum registers: A ''qubit'' is a quantum system in which the Boolean states $0$ and $1$ are represented by a prescribed pair of normalised and mutually orthogonal quantum states labeled as $\\left\{|0\rangle ,|1\rangle \\right\}$ Sch95. The two states form a `computational basis' and any other (pure) state of the qubit can be written as a superposition $\alpha |0\rangle +\beta |1\rangle$ for some $\alpha$ and $\beta$ such that $|\alpha |^\left\{2\right\}+|\beta |^\left\{2\right\}=1.$ A qubit is typically a microscopic system, such as an atom, a nuclear spin, or a polarised photon. A collection of $n$ qubits is called a ''quantum register'' of size $n$. We shall assume that information is stored in the registers in binary form. For example, the number $6$ is represented by a register in state $|1\rangle \otimes |1\rangle \otimes |0\rangle$. In more compact notation: $|a\rangle$ stands for the tensor product $|a_\left\{n-1\right\}\rangle \otimes |a_\left\{n-2\right\}\rangle \ldots |a_\left\{1\right\}\rangle \otimes |a_\left\{0\right\}\rangle$, where $a_i\in\\left\{0,1\\right\}$, and it represents a quantum register prepared with the value $a=2^\left\{0\right\}a_\left\{0\right\}+2^\left\{1\right\}a_\left\{1\right\}+\ldots2^\left\{n-1\right\}a_\left\{n-1\right\}$. There are $2^n$ states of this kind, representing all binary strings of length $n$ or numbers from $0$ to $2^n-1$, and they form a convenient computational basis. In the following $a\in \\left\{0,1\\right\}^n$ ($a$ is a binary string of length $n$) implies that $\left| a \right\rangle$ belongs to the computational basis. Thus a quantum register of size three can store individual numbers such as $3$ or $7$, $|0\rangle \otimes |1\rangle \otimes |1\rangle \equiv |011\rangle \equiv |3\rangle ,$ $|1\rangle \otimes |1\rangle \otimes |1\rangle \equiv |111\rangle \equiv |7\rangle ,$ but, it can also store the two of them simultaneously. For if we take the first qubit and instead of setting it to $|0\rangle$ or $|1\rangle$ we prepare a superposition $1/\sqrt\left\{2\right\}\left\left( |0\rangle +|1\rangle \right\right)$ then we obtain $\frac\left\{1\right\}\left\{\sqrt\left\{2\right\}\right\}\left\left( |0\rangle +|1\rangle \right\right) \otimes |1\rangle \otimes |1\rangle \equiv \frac\left\{1\right\}\left\{\sqrt\left\{2\right\}\right\}\left\left( |011\rangle +|111\rangle \right\right) ,$ $\equiv \frac\left\{1\right\}\left\{\sqrt\left\{2\right\}\right\}\left\left( |3\rangle +|7\rangle \right\right) .$ In fact we can prepare this register in a superposition of all eight numbers -- it is enough to put each qubit into the superposition $1/\sqrt\left\{2\right\} \left\left( |0\rangle +|1\rangle \right\right) .$ This gives $\frac\left\{1\right\}\left\{\sqrt\left\{2\right\}\right\}\left\left( |0\rangle +|1\rangle \right\right) \otimes \frac\left\{1\right\}\left\{\sqrt\left\{ 2\right\}\right\}\left\left( |0\rangle +|1\rangle \right\right) \otimes \frac\left\{1\right\}\left\{\sqrt\left\{2\right\}\right\}\left\left( |0\rangle +|1\rangle \right\right) ,$ which can also be written in binary as (ignoring the normalisation constant $2^\left\{-3/2\right\}$ ), $|000\rangle +|001\rangle +|010\rangle +|011\rangle +|100\rangle +|101\rangle +|110\rangle +|111\rangle .$ or in decimal notation as $|0\rangle +|1\rangle +|2\rangle +|3\rangle +|4\rangle +|5\rangle +|6\rangle +|7\rangle ,$ or simply as $\sum_\left\{x=0\right\}^7|x\rangle.$ These preparations, and any other manipulations on qubits, have to be performed by unitary operations. A ''quantum logic gate'' is a device which performs a fixed unitary operation on selected qubits in a fixed period of time and a ''quantum network'' is a device consisting of quantum logic gates whose computational steps are synchronised in time Deu89. The outputs of some of the gates are connected by wires to the inputs of others. The ''size'' of the network is the number of gates it contains. The most common quantum gate is the Hadamard gate, a single qubit gate $H$ performing the unitary transformation known as the Hadamard transform. It is defined as Image:../sites/default/files/wiki_images/6/62/Img44.png The matrix is written in the computational basis $\\left\{|0\rangle, |1\rangle \\right\}$ and the diagram on the right provides a schematic representation of the gate $H$ acting on a qubit in state $|x\rangle$, with $x=0,1$. And here is a network, of size three, which affects the Hadamard transform on three qubits. If they are initially in state $|000\rangle$ then the output is the superposition of all eight numbers from $0$ to $7.$ Image:../sites/default/files/wiki_images/a/a6/Img49.png If the three qubits are initially in some other state from the computational basis then the result is a superposition of all numbers from $0$ to $7$ but exactly half of them will appear in the superposition with the minus sign, for example, Image:../sites/default/files/wiki_images/7/71/Img50.png In general, if we start with a register of size $n$ in some state $y\in\\left\{0,1\\right\}^n$ then $|y\rangle\mapsto 2^\left\{-n/2\right\} \sum_\left\{x\in\\left\{0, 1\\right\}^n\right\}\left(-1\right)^\left\{y\cdot x\right\}|x\rangle,$ where the product of $y =\left(y_\left\{n-1\right\},\ldots , y_0\right)$ and $x=\left(x_\left\{n-1\right\},\ldots, x_0\right)$ is taken bit by bit: $y\cdot x = \left(y_\left\{n-1\right\}x_\left\{n-1\right\}+\ldots y_1x_1 +y_0x_0\right).$ We will need another single qubit gate -- the phase shift gate $\mathbf\left\{\phi \right\}$ defined as $\left| \,0\right\rangle \mapsto \left| \,0\right\rangle$ and $\left| \,1\right\rangle \mapsto e^\left\{i\phi \right\}\left| \,1\right\rangle$, or, in matrix notation, Image:../sites/default/files/wiki_images/4/4f/Img59.png The Hadamard gate and the phase gate can be combined to construct the following network (of size four), which generates the most general pure state of a single qubit (up to a global phase), Image:../sites/default/files/wiki_images/2/27/Img60.png Consequently, the Hadamard and phase gates are sufficient to construct ''any'' unitary operation on a single qubit. Thus the Hadamard gates and the phase gates can be used to transform the input state $|0\rangle |0\rangle ...|0\rangle$ of the $n$ qubit register into any state of the type $|\Psi _\left\{1\right\}\rangle$ $|\Psi _\left\{2\right\}\rangle ...$ $|\Psi _\left\{n\right\}\rangle ,$ where $|\Psi _\left\{i\right\}\rangle$ is an arbitrary superposition of $|0\rangle$ and $|1\rangle .$ These are rather special $n$-qubit states, called the product states or the separable states. In general, a quantum register of size $n>1$ can be prepared in states which are not separable -- they are known as entangled states. For example, for two qubits ($n=2$), the state $\alpha \ |00\rangle +\beta \ |01\rangle =|0\rangle \otimes\left\left( \alpha \ |0\rangle +\beta \ |1\rangle \right\right)$ is separable, $|\Psi_1\rangle=|0\rangle$ and $|\Psi_2\rangle= \alpha |0\rangle +\beta |1\rangle$, whilst the state $\alpha \ |00\rangle +\beta \ |11\rangle\neq |\Psi_1\rangle\otimes|\Psi_2\rangle$ is entangled ($\alpha ,\beta \neq 0$), because it cannot be written as a tensor product. In order to entangle two (or more qubits) we have to extend our repertoire of quantum gates to two-qubit gates. The most popular two-qubit gate is the controlled-NOT (C-NOT), also known as the XOR or the measurement gate. It flips the second (target) qubit if the first (control) qubit is $\left| \,1\right\rangle$ and does nothing if the control qubit is $\left| \,0\right\rangle$. The gate is represented by the unitary matrix Image:../sites/default/files/wiki_images/5/57/Img76.png where $x,y=0\mbox\left\{ or \right\}1$ and $\oplus$ denotes XOR or addition modulo 2. If we apply the C-NOT to Boolean data in which the target qubit is $|0\rangle$ and the control is either $|0\rangle$ or $|1\rangle$ then the effect is to leave the control unchanged while the target becomes a copy of the control, ''i.e.'' $|x\rangle |0\rangle \mapsto |x\rangle |x\rangle \qquad x=0,1.$ One might suppose that this gate could also be used to copy superpositions such as $|\Psi \rangle =\alpha \ |0\rangle +\beta \ |1\rangle ,$ so that $|\Psi \rangle |0\rangle \mapsto |\Psi \rangle |\Psi \rangle$ for any $|\Psi \rangle .$ This is not so! The unitarity of the C-NOT requires that the gate turns superpositions in the control qubit into ''entanglement'' of the control and the target. If the control qubit is in a superposition state $|\Psi \rangle =\alpha |0\rangle +\beta |1\rangle ,$ \noindent $\left(\alpha ,\beta \neq 0\right),$ and the target in $|0\rangle$ then the C-NOT generates the entangled state $\left\left( \alpha |0\rangle +\beta |1\rangle \right\right) |0\rangle \mapsto \alpha |00\rangle +\beta |11\rangle.$ Let us notice in passing that it is impossible to construct a universal quantum cloning machine effecting the transformation in Eq.(\ref{cloning}), or even the more general $|\Psi \rangle |0\rangle |W\rangle \mapsto |\Psi \rangle |\Psi \rangle |W^\left\{\prime \right\}\rangle$ where $|W\rangle$ refers to the state of the rest of the world and $|\Psi \rangle$ is ''any'' quantum state WZ82. To see this take any two normalised states $|\Psi \rangle$ and $|\Phi \rangle$ which are non-identical ($|\langle \Phi |\Psi \rangle| \neq 1$) and non-orthogonal ($\langle \Phi |\Psi \rangle \neq 0$ ), and run the cloning machine, $|\Psi \rangle |0\rangle |W\rangle \mapsto |\Psi \rangle |\Psi \rangle |W^\left\{\prime\right\}\rangle$ $|\Phi \rangle |0\rangle |W\rangle \mapsto |\Phi \rangle |\Phi \rangle |W^\left\{\prime \prime \right\}\rangle$ As this must be a unitary transformation which preserves the inner product hence we must require $\langle \Phi |\Psi \rangle =\langle \Phi |\Psi \rangle ^\left\{2\right\}\langle W^\left\{\prime \right\}|W^\left\{\prime \prime \right\}\rangle$ and this can only be satisfied when $|\langle \Phi |\Psi \rangle| =0$ or $1$, which contradicts our assumptions. Thus states of qubits, unlike states of classical bits, cannot be faithfully cloned. This leads to interesting applications, quantum cryptography being one such. Another common two-qubit gate is the controlled phase shift gate $B\left(\phi\right)$ defined as Image:../sites/default/files/wiki_images/d/d7/Img99.png Again, the matrix is written in the computational basis $\\left\{ |00\rangle, |01\rangle, |10\rangle, |11\rangle \\right\}$ and the diagram on the right shows the structure of the gate. More generally, these various 2-qubit controlled gates are all of the form controlled-$U$, for some single-qubit unitary transformation $U$. The controlled-$U$ gate applies the identity transformation to the auxiliary (lower) qubit when the control qubit is in state $|0\rangle$ and applies an arbitrary prescribed $U$ when the control qubit is in state $|1\rangle$. The gate maps $|0\rangle|y\rangle$ to $|0\rangle|y\rangle$ and $|1\rangle|y\rangle$ to $|1\rangle\left(U |y\rangle\right)$, and is graphically represented as Image:../sites/default/files/wiki_images/4/46/Img106.png The Hadamard gate, all phase gates, and the C-NOT, form an infinite ''universal set of gates'' ''i.e.'' if the C-NOT gate as well as the Hadamard and all phase gates are available then any $n$-qubit unitary operation can be simulated exactly with $O\left(4^\left\{n\right\}n\right)$ such gates BBC95. (Here and in the following we use the asymptotic notation -- $O\left(T\left(n\right)\right)$ means bounded above by $c\,T\left(n\right)$ for some constant $c>0$ for sufficiently large $n$.) This is not the only universal set of gates. In fact, almost any gate which can entangle two qubits can be used as a universal gate BDEJ95,Llo95. Mathematically, an elegant choice is a pair of the Hadamard and the controlled-$V$ (C-$V$) where $V$ is described by the unitary matrix Image:../sites/default/files/wiki_images/8/80/Img112.png :$V|0\rangle=\begin\left\{pmatrix\right\} 1& 0 \\ 0 &i\\ \end\left\{pmatrix\right\}\begin\left\{pmatrix\right\} 1 \\ 0 \\ \end\left\{pmatrix\right\}=\begin\left\{pmatrix\right\} 1 \\ 0 \\ \end\left\{pmatrix\right\}=|0\rangle$ :$V|1\rangle=\begin\left\{pmatrix\right\} 1 &0 \\ 0 & i\\ \end\left\{pmatrix\right\}\begin\left\{pmatrix\right\} 0 \\ 1 \\ \end\left\{pmatrix\right\}=\begin\left\{pmatrix\right\} 0 \\ i \\ \end\left\{pmatrix\right\}=i|1\rangle$ The two gates form a finite universal set of gates -- networks containing only a finite number of these gates can approximate any unitary transformation on two (and more) qubits. More precisely, if $U$ is any two-qubit gate and $\varepsilon >0$ then there exists a quantum network of size $O\left(\log ^\left\{d\right\}\left(1/\varepsilon \right)\right)$ (where $d$ is a constant) consisting of only $H$ and C-$V$ gates which computes a unitary operation $U^\left\{\prime \right\}$ that is within distance $\varepsilon$ from $U$Sol99. The metric is induced by the Euclidean norm - we say that $U^\left\{\prime \right\}$ is within distance $\varepsilon$ from $U$ if there exists a unit complex number $\lambda$ (phase factor) such that $||U-\lambda U^\left\{\prime \right\}||\leq \varepsilon$. Thus if $U^\left\{\prime \right\}$ is substituted for $U$ in a quantum network then the final state $\sum_\left\{x\right\}\alpha _\left\{x\right\}^\left\{\prime \right\}\left| x\right\rangle$ approximates the final state of the original network $\sum_\left\{x\right\}\alpha _\left\{x\right\}\left| x\right\rangle$ as follows: $\sqrt\left\{ \sum_\left\{x\right\}|\lambda \alpha _\left\{x\right\}^\left\{\prime \right\}-\alpha _\left\{x\right\}|^\left\{2\right\}\right\}\leq \varepsilon$. The probability of any specified measurement outcome on the final state is affected by at most $\varepsilon$. A ''quantum computer'' will be viewed here as a quantum network (or a family of quantum networks)and quantum computation is defined as a unitary evolution of the network which takes its initial state "input" into some final state "output". We have chosen the network model of computation, rather than Turing machines, because it is relatively simple and easy to work with and because it is much more relevant when it comes to physical implementation of quantum computation. = Quantum arithmetic and function evaluations = Let us now describe how quantum computers actually compute, how they add and multiply numbers, and how they evaluate Boolean functions by means of unitary operations. Here and in the following we will often use the modular arithmetic HW79. Recall that $a\bmod\left\{b\right\}$ denotes the remainder obtained by dividing integer $b$ into integer $a$, which is always a number less than $b$. Basically $a=b\bmod n$ if $a=b+kn$ for some integer $k$. This is expressed by saying that $a$ is ''congruent'' to $b$ modulo $n$ or that $b$ is the ''residue'' of $a$ modulo $n$. For example, $1\bmod 7=8\bmod 7=15\bmod 7=50\bmod 7=1$. Modular arithmetic is commutative, associative, and distributive. $\left(a\pm b\right)\bmod n =\left(\left(a\bmod n\right)\pm \left(b\bmod n\right)\right)\bmod n$ $\left(a\times b\right)\bmod n =\left(\left(a\bmod n\right)\times \left(b\bmod n\right)\right)\bmod n$ $\left(a\times \left(b+c\right)\right)\bmod n =\left(\left(\left(a b\right)\bmod n+\left(\left(a c\right)\bmod n\right)\right)\bmod n$ Thus, if you need to calculate, say, $3^8\bmod 7$ do not use the naive approach and perform seven multiplications and one huge modular reduction. Instead, perform three smaller multiplications and three smaller reductions, $\left(\left(3^2\bmod 7\right)^2\bmod 7\right)^2\bmod 7 = \left(2^2\bmod 7\right)^2\bmod 7=16 \bmod 7= 2.$ This kind of arithmetic is ideal for computers as it restricts the range of all intermediate results. For $l$-bit modulus $n$, the intermediate results of any addition, subtraction or multiplication will not be more than $2l$ bits long. In quantum registers of size $n$, addition modulo $2^n$ is one of the most common operations; for all $x \in \\left\{0,1\\right\}^n$ and for any $a\in \\left\{0,1\\right\}^n$, $|x\rangle\mapsto|\left(x+a\right)\bmod 2^n\rangle$ is a well defined unitary transformation. The tricky bit in the modular arithmetic is the inverse operation, and here we need some basic number theory. An integer $a\geq 2$ is said to be ''prime'' if it is divisible only by 1 and $a$ (we consider only positive divisors). Otherwise, $a$ is called ''composite''. The greatest common divisor of two integers $a$ and $b$ is the greatest positive integer $d$ denoted $d=\gcd\left(a,b\right)$ that divides both $a$ and $b$. Two integers $a$ and $b$ are said to be ''coprime'' or ''relatively prime'' if $\gcd \left(a,b\right)=1$. Given two integers $a$ and $n$ that are coprime, it can be shown that there exists an unique integer $d\in\\left\{0,\ldots,n-1\\right\}$ such that $a d=1\bmod n$ HW79. The integer $d$ is called ''inverse modulo '' $n$ of $a$, and denoted $a^\left\{-1\right\}$. For example, modulo $7$ we find that $3^\left\{-1\right\}=5 \bmod n$, since $3 \times 5 = 15 = 2\times 7 +1=1 \bmod 7$. This bizarre arithmetic and the notation is due to Karl Friedrich Gauss (1777-1855). It was first introduced in his ''Disquistiones Arithmeticae'' in 1801. In quantum computers addition, multiplication, and any other arithmetic operation have to be embedded in unitary evolution. We will stick to the Hadamard and the controlled-$V$ (C-$V$), and use them as building blocks for all other gates and eventually for quantum adders and multipliers. If we apply C-$V$ four times we get identity, so any three subsequent applications of C-$V$ give the inverse of C-$V$, which will be called C-$V^\left\{\dagger \right\}$. Now, if we have a couple of the C-$V$ gates and a couple of the Hadamard gates we can build the C-NOT as follows Image:../sites/default/files/wiki_images/c/c4/Img151.png :$|0\rangle|0\rangle\to|0\rangle\left\{1\over\sqrt\left\{2\right\}\right\}\left(|0\rangle+|1\rangle\right)\to|0\rangle\left\{1\over\sqrt\left\{2\right\}\right\}\left(|0\rangle+|1\rangle\right)\to|0\rangle|0\rangle,$ :$|0\rangle|1\rangle\to|0\rangle\left\{1\over\sqrt\left\{2\right\}\right\}\left(|0\rangle-|1\rangle\right)\to|0\rangle\left\{1\over\sqrt\left\{2\right\}\right\}\left(|0\rangle-|1\rangle\right)\to|0\rangle|1\rangle,$ :$|1\rangle|0\rangle\to|1\rangle\left\{1\over\sqrt\left\{2\right\}\right\}\left(|0\rangle+i|1\rangle\right)\to|1\rangle\left\{1\over\sqrt\left\{2\right\}\right\}\left(|0\rangle+i^2|1\rangle\right)=|1\rangle\left\{1\over\sqrt\left\{2\right\}\right\}\left(|0\rangle-|1\rangle\right)\to|1\rangle|1\rangle,$ :$|1\rangle|1\rangle\to|1\rangle\left\{1\over\sqrt\left\{2\right\}\right\}\left(|0\rangle-i|1\rangle\right)\to|1\rangle\left\{1\over\sqrt\left\{2\right\}\right\}\left(|0\rangle-i^2|1\rangle\right)\to|1\rangle|0\rangle.$ A single qubit operation NOT can be performed via a C-NOT gate if the control qubit is set to $|1\rangle$ and viewed as an auxiliary qubit. This is not to say that we want to do it in practice. The C-NOT gate is much more difficult to build than a single qubit NOT. Right now we are looking into the mathematical structure of quantum Boolean networks and do not care about practicalities. Our two elementary gates also allow us to construct a very useful gate called the controlled-controlled-NOT gate ($c^\left\{2\right\}$-NOT) or the Toffoli gate Tof81. The construction is given by the following network, Image:../sites/default/files/wiki_images/7/75/Toffoli.PNG Image:../sites/default/files/wiki_images/3/3c/Img153.png $|110\rangle\to|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle+|1\rangle\right)\to|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle+i|1\rangle\right)\to|10\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle+i|1\rangle\right)\to|10\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle+i|1\rangle\right)\to$ $\to|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle+|1\rangle\right)\to|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle+i^2|1\rangle\right)=|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle+|1\rangle\right)\to|111\rangle.$ $|111\rangle\to|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle-|1\rangle\right)\to|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle-i|1\rangle\right)\to|10\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle-i|1\rangle\right)\to|10\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle-i|1\rangle\right)\to$ $\to|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle-i|1\rangle\right)\to|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle-i^2|1\rangle\right)=|11\rangle\left\{1\over \sqrt\left\{2\right\}\right\}\left(|0\rangle+|1\rangle\right)\to|110\rangle.$ This gate has two control qubits (the top two wires on the diagram) and one target qubit which is negated only when the two controls are in the state $|1\rangle |1\rangle$. The $c^2$-NOT gate gives us the logical connectives we need for arithmetic. If the target is initially set to $|0\rangle$ the gate acts as a reversible AND gate - after the gate operation the target becomes the logical AND of the two control qubits. $|x_1,x_2\rangle|0\rangle\mapsto |x_1,x_2\rangle|x_1\wedge x_2\rangle$ Once we have in our repertoire operations such as NOT, AND, and C-NOT, all of them implemented as unitary operations, we can, at least in principle, evaluate any Boolean function $\\left\{0,1\\right\}^\left\{n\right\}\rightarrow \\left\{0,1\\right\}^\left\{m\right\}$ which map $n$ bits of input into $m$ bits of output. A simple concatenation of the Toffoli gate and the C-NOT gives a simplified quantum adder, shown below, which is a good starting point for constructing full adders, multipliers and more elaborate networks. Image:../sites/default/files/wiki_images/a/ab/Img161.png We can view the Toffoli gate and the evolution given by Eq.~(\ref{andgate}) as a quantum implementation of a Boolean function $f:\\left\{0,1\\right\}^\left\{2\right\}\rightarrow\\left\{0,1\\right\}$ defined by $f\left(x_1,x_2\right) = x_1 \wedge x_2$. The operation AND is not reversible, so we had to embed it in the reversible operation $c^2$-NOT. If the third bit is initially set to $1$ rather than $0$ then the value of $x_1\wedge x_2$ is negated. In general we write the action of the Toffoli gate as the function evaluation, $|x_1,x_2\rangle|y\rangle\mapsto|x_1,x_2\rangle|\left(y+\left(x_1\wedge x_2\right)\right)\bmod 2\rangle.$ This is how we compute any Boolean function $\\left\{0,1\\right\}^\left\{n\right\}\rightarrow\\left\{0,1\\right\}^\left\{m\right\}$ on a quantum computer. We require at least two quantum registers; the first one, of size $n$, to store the arguments of $f$ and the second one, of size $n$, to store the values of $f$. The function evaluation is then a unitary evolution of the two registers, $|x,y\rangle \mapsto |x,\left(y+f\left(x\right)\right)\bmod 2^\left\{m\right\}\rangle .$ for any $y\in\\left\{0,1\\right\}^m$. (In the following, if there is no danger of confusion, we may simplify the notation and omit the $\bmod\left\{\right\}$ suffix.) For example, a network computing $f:\\left\{0,1\\right\}^\left\{2\right\}\rightarrow \\left\{0,1\\right\}^\left\{3\right\}$ such that $f\left(x\right)=x^\left\{2\right\}$ acts as follows $|00\rangle |000\rangle \mapsto |00\rangle |000\rangle,\qquad |10\rangle |000\rangle \mapsto |10\rangle |100\rangle$ $|01\rangle |000\rangle \mapsto |01\rangle |001\rangle,\qquad |11\rangle |000\rangle \mapsto |11\rangle |001\rangle$ which can be written as $|x,0\rangle \mapsto |x,x^\left\{2\right\}\bmod 8\rangle ,$ ''e.g.'' $3^2\bmod 2^3=1$ which explains why $|11\rangle |000\rangle \mapsto |11\rangle |001\rangle$. In fact, for these kind of operations we also need a third register with the so-called working bits which are set to zero at the input and return to zero at the output but which can take non-zero values during the computation. What makes quantum function evaluation really interesting is its action on a superposition of different inputs $x$, for example, $\sum_\left\{x\right\}|x,0\rangle \mapsto \sum_\left\{x\right\}|x,f\left(x\right)\rangle$ produces $f\left(x\right)$ for all $x$ in a single run. The snag is that we cannot get them all from the entangled state $\sum_\left\{x\right\}|x,f\left(x\right)\rangle$ because any bit by bit measurement on the first register will yield one particular value $x^\left\{\prime\right\}\in\\left\{0,1\\right\}^n$ and the second register will then be found with the value $f\left(x^\left\{\prime \right\}\right)\in\\left\{0,1\\right\}^m$. = Algorithms and their complexity = In order to solve a particular problem, computers, be it classical or quantum, follow a precise set of instructions that can be mechanically applied to yield the solution to any given instance of the problem. A specification of this set of instructions is called an algorithm. Examples of algorithms are the procedures taught in elementary schools for adding and multiplying whole numbers; when these procedures are mechanically applied, they always yield the correct result for any pair of whole numbers. Any algorithm can be represented by a family of Boolean networks $\left(N_1,N_2,N_3,... \right)$, where the network $N_n$ acts on all possible input instances of size $n$ bits. Any useful algorithm should have such a family specified by an example network $N_n$ and ''a simple rule'' explaining how to construct the network $N_\left\{n+1\right\}$ from the network $N_\left\{n\right\}$. These are called ''uniform'' families of networks Pap94.\footnote{This means that the network model is not a self-contained model of computation. We need an algorithm, a Turing machine, which maps each $n$ into an explicit description of $N_n$.} The quantum Hadamard transform defined by Eq.(\ref{Had}) has a uniform family of networks whose size is growing as $n$ with the number of input qubits. Another good example of a uniform family of networks is the quantum Fourier transform (QFT) Cop94 defined in the computational basis as the unitary operation $|y\rangle\mapsto 2^\left\{-n/2\right\} \sum_x e^\left\{i \frac\left\{2\pi\right\}\left\{2^n\right\} yx\right\}|x\rangle,$ Suppose we want to ''construct'' such a unitary evolution of $n$ qubits using our repertoire of quantum logic gates. We can start with a single qubit and notice that in this case the QFT is reduced to applying a Hadamard gate. Then we can take two qubits and notice that the QFT can be implemented with two Hadamard gates and the controlled phase shift $B\left(\pi\right)$ in between. Progressing this way we can construct the three qubit QFT and the four qubit QFT, whose network looks like this: Image:../sites/default/files/wiki_images/5/50/Img191.png (''N.B.'' there are three different types of the $\left\{B\right\}\left(\phi\right)$ gate in the network above: $\left\{B\right\}\left(\pi\right)$, $B\left(\pi/2\right)$ and $B\left(\pi/4\right)$.) The general case of $n$ qubits requires a trivial extension of the network following the same sequence pattern of gates $H$ and $B$. The QFT network operating on $n$ qubits contains $n$ Hadamard gates $H$ and $n\left(n-1\right)/2$ phase shifts $B$, in total $n\left(n+1\right)/2$ elementary gates. The big issue in designing algorithms or their corresponding families of networks is the optimal use of physical resources required to solve a problem. Complexity theory is concerned with the inherent cost of computation in terms of some designated elementary operations, memory usage, or network size. An algorithm is said to be fast or efficient if the number of elementary operations taken to execute it increases no faster than a polynomial function of the size of the input. We generally take the input size to be the total number of bits needed to specify the input (for example, a number $N$ requires $\log_\left\{2\right\}N$ bits of binary storage in a computer). In the language of network complexity - an algorithm is said to be ''efficient'' if it has a uniform and polynomial-size network family ($O\left(n^d\right)$ for some constant $d$)Pap94. For example, the quantum Fourier transform can be performed in an efficient way because it has a uniform family of networks whose size grows only as a quadratic function of the size of the input, ''i.e.'' $O\left(n^2\right)$. Changing from one set of gates to another, ''e.g.'' constructing the QFT out of the Hadamard and the controlled-$V$ gates with a prescribed precision $\epsilon$, can only affect the network size by a multiplicative constant which does not affect the quadratic scaling with $n$. Thus the complexity of the QFT is $O\left(n^2\right)$ no matter which set of adequate gates we use. Problems which do not have efficient algorithms are known as hard problems. Elementary arithmetic operations taught at schools, such as long addition, multiplication or division of