J.A. Jones/Progress in Nuclear Magnetic Resonance Spectroscopy 38(2001)325-360 Fig 4. The Toffoli gate, which gives=x, y=y, andz =z e( Fig. 6. Thef-controlled-NOT gate, for reversible function evaluation a= a and b'=b⊕fa) in state 1. Note that a controlled-NOT gate is comple- output, but the generalisation to more complex func- tely reversible; indeed it can be reversed by simply tions is straightforward. This can be achieved by applying the same gate again(that is, controlled-NOT constructing a circuit with two inputs and two outputs, is its own inverse). Furthermore, as x y= x XoR y as shown in Fig. 6(anf-controlled-NOT)and setting the controlled-NOT gate is just a reversible XoR gate. b=0. The two values of the function, f(o)and f(1). A more complex example is provided by the can then be evaluated by setting a=0 and a= 1 controlled-controlled-NOT gate, often called the respectively. The f-controlled-NOT gate can itself be Toffoli gate(Fig 4), which plays a central role in built out of simpler gates, such as those described reversible logic. This gate has three inputs, x, y and above; in most cases this will also require a number z, and three corresponding outputs, x, y and z. The of ancilla bits to hold intermediate results. For simpli first two input bits, which are the logical inputs, are city these ancilla bits are usually omitted from copied unchanged, so that x'=x and y=y. A NOT diagrams such as Fig. 6 gate is then applied to the third bit if and only if both x and y are in state 1; hence z=z( AND y). Thus this gate can be considered as a reversible equivalent 4. Quantum computation to the conventional AND and NAND gates: to evaluate AND y just use a Toffoli gate with z=0, while for a We now have all the basic elements needed to NAND gate set z=1 describe how quantum computers could be used to The combination of the Toffoli gate with the extend our computational abilities. While large scale controlled-NOT and simple NoT gates forms an quantum algorithms, such as Shor's algorithm, are too adequate set, in that it is possible to build any other complex to describe here, the basic ideas are relatively gate using only a combination of these gates(in parti- simple cular controlled-NOT gates can also be used to build As described above, a quantum mechanical two- the two implicit gates, CLONE and SwAP, as shown in level system can be used to build a reversible classical Fig 5). Indeed, the Toffoli gate is universal in its own computer by using the two eigenstates of the system to right,as a Toffoli gate can be easily converted into a represent bits in logical states O and l. For example controlled-NOT gate by setting x= l, and to a the two Zeeman levels of a spin-1/2 nucleus in a NoT gate by setting=y= l magnetic field, la)and IB), would be suitable for this purpose. For simplicity the two states are usually 3.3. Reversible function denoted o)and 1), allowing quantum computation to be described without reference to any particular Central to reversible computation is the idea of implementation; this choice of basis set is called the reversible function evaluation. I will initially assume computational basis. The system will not be confined that the function has a single bit as both input and to these two eigenstates, however, but can also be found in superpositions, such as 0)+|1) (the v2 term is necessary to ensure that the state is Fig. 5.(a) The controlled-NoT gate can be used to reversibly clone a normalised). For this reason a quantum mechanical bit.( b) Three controlled-NoT gates implement a SwAP gat two level system has much more freedom than ain state 1. Note that a controlled-not gate is comple￾tely reversible; indeed it can be reversed by simply applying the same gate again (that is, controlled-not is its own inverse). Furthermore, as x % y ˆ x xor y the controlled-not gate is just a reversible xor gate. A more complex example is provided by the controlled-controlled-not gate, often called the Toffoli gate (Fig. 4), which plays a central role in reversible logic. This gate has three inputs, x, y and z, and three corresponding outputs, x0 , y0 and z0 . The ®rst two input bits, which are the logical inputs, are copied unchanged, so that x0 ˆ x and y0 ˆ y. A not gate is then applied to the third bit if and only if both x and y are in state 1; hence z0 ˆ z % (x and y). Thus this gate can be considered as a reversible equivalent to the conventional and and nand gates: to evaluate x and y just use a Toffoli gate with z ˆ 0; while for a nand gate set z ˆ 1: The combination of the Toffoli gate with the controlled-not and simple not gates forms an adequate set, in that it is possible to build any other gate using only a combination of these gates (in parti￾cular controlled-not gates can also be used to build the two implicit gates, clone and swap, as shown in Fig. 5). Indeed, the Toffoli gate is universal in its own right, as a Toffoli gate can be easily converted into a controlled-not gate by setting x ˆ 1; and to a simple not gate by setting x ˆ y ˆ 1: 3.3. Reversible function evaluation Central to reversible computation is the idea of reversible function evaluation. I will initially assume that the function has a single bit as both input and output, but the generalisation to more complex func￾tions is straightforward. This can be achieved by constructing a circuit with two inputs and two outputs, as shown in Fig. 6 (an f-controlled-not) and setting b ˆ 0: The two values of the function, f(0) and f(1), can then be evaluated by setting a ˆ 0 and a ˆ 1; respectively. The f-controlled-not gate can itself be built out of simpler gates, such as those described above; in most cases this will also require a number of ancilla bits to hold intermediate results. For simpli￾city these ancilla bits are usually omitted from diagrams such as Fig. 6. 4. Quantum computation We now have all the basic elements needed to describe how quantum computers could be used to extend our computational abilities. While large scale quantum algorithms, such as Shor's algorithm, are too complex to describe here, the basic ideas are relatively simple. As described above, a quantum mechanical two￾level system can be used to build a reversible classical computer by using the two eigenstates of the system to represent bits in logical states 0 and 1. For example, the two Zeeman levels of a spin-1/2 nucleus in a magnetic ®eld, ual and ubl, would be suitable for this purpose. For simplicity the two states are usually denoted u0l and u1l, allowing quantum computation to be described without reference to any particular implementation; this choice of basis set is called the computational basis. The system will not be con®ned to these two eigenstates, however, but can also be found in superpositions, such as u0l 1 u1l  2 p …1† (the  2 p term is necessary to ensure that the state is normalised). For this reason a quantum mechanical two level system has much more freedom than a J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360 331 Fig. 4. The Toffoli gate, which gives x0 ˆ x; y0 ˆ y; and z0 ˆ z % (x and y). Fig. 5. (a) The controlled-not gate can be used to reversibly clone a bit. (b) Three controlled-not gates implement a swap gate. Fig. 6. The f-controlled-not gate, for reversible function evaluation: a0 ˆ a and b0 ˆ b % f…a†: