J.A. Jones/Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001)325-360 This description works well with conventional computers, in which bit states are represented by voltages applied to wires, but it cannot be used with atomic computers. Atomic computers represent bit Fig. 3. The controlled-NOT gate, which plays a central role in rever- sible and quantum computation. The target bit is marked by a eD values using the quantum states of atomic systems, mbol, indicating the close relationship with binary arithmeti so a logic gate can neither create nor destroy bits; nodulo two; the control bit is marked by a dot and a vertical control thus logic gates such as AND, which have two input ne(the dot is important in drawings of larger circuits where bits and only one output bit, are immediately ruled ontrol line may have to cross lines representing other bits). out. Similarly, atomic systems evolve under a series of unitary transformations, which correspond to rever suggestions that quantum devices might have funda sible operations, while many of the operations mentally different properties. described above are clearly not reversible. In order The basic approach is very simple. Classical to build atomic computers, therefore, it is necessary computation [15] is implemented with two state to use a different approach, using only reversible logic devices, usually called bits, and these two states can operations two eigenstates of a quantum mechanical two level system. The calculation then 3. 2. Reversible computation proceeds by manipulating the states of various bits such that the final state of some group of bits(the The theory of reversible computation [15, 27, 28] output register")depends on the result of the desired has been studied extensively and, perhaps surpris- computation As will be shown later, quantum compu ingly, it is simple to perform any logic operation in tation is very similar, except that the bits are not a reversible manner. The only irreversible operation confined to their eigenstates; this effectively allows required when performing a computation [29,30]is many different calculations to be carried out in the preparation of a well defined initial state, usually parallel taken as having all bits in state 0; after this initialise tion process the computation can be performed 3. 1. Computational circuit The basic approach needed to achieve reversible Although several different theoretical models are logic can be summarised in two simple rules. First, useful for abstract descriptions of computers, one of any logical inputs to a gate must be preserved in the the most convenient approaches for describing how to outputs: this is most simply achieved by copying them build small computers is the circuit model, in which to output bits without change. Secondly, the output of bits interact through gates which implement Boolean the gate(here assumed for simplicity to comprise logic operations. One traditional set of classical gates single bit)must be combined in a reversible fashion is the one bit NoT gate together with two different two with an additional auxiliary bit, for example by addin bit gates, AND and OR. These three gates are said to the two bits together using binary arithmetic modulo form an adequate set, in that any desired logic opera tion can be performed by building an appropriate Binary arithmetic modulo two, usually indicated by circuit(see Fig. 1 for an example)using some combi- the symbol 6, has the useful properties that x e 0 nation of these three gates 0⊕x= r and x1=1r=Nor(x), while x⊕ In fact it is not necessary to use all these gates: they x=0. A simple example of a reversible logic gate an themselves all be obtained using combinations of based on this approach is the controlled-NOT gate NAND gates(Fig. 2), and so the NAND gate is universal(see Fig 3), which has two inputs, x and y and two for classical computation. It is, however, necessary to corresponding outputs xand y. The first input bit is proceed with some caution, as several other"implicit copied to its output bit, so x'=x, and is also gates are also required, such as the cLone gate, which combined with the second input bit to give y'=xe makes a copy of a bit, and the SwAP gate, which allows y. Thus a NoT gate is applied to the second bit(the two wires to cross one another target bit)if and only if the first bit(the control bit)is
suggestions that quantum devices might have fundamentally different properties. The basic approach is very simple. Classical computation [15] is implemented with two state devices, usually called bits, and these two states can be mapped to the two eigenstates of a quantum mechanical two level system. The calculation then proceeds by manipulating the states of various bits such that the ®nal state of some group of bits (the ªoutput registerº) depends on the result of the desired computation. As will be shown later, quantum computation is very similar, except that the bits are not con®ned to their eigenstates; this effectively allows many different calculations to be carried out in parallel. 3.1. Computational circuits Although several different theoretical models are useful for abstract descriptions of computers, one of the most convenient approaches for describing how to build small computers is the circuit model, in which bits interact through gates which implement Boolean logic operations. One traditional set of classical gates is the one bit not gate together with two different two bit gates, and and or. These three gates are said to form an adequate set, in that any desired logic operation can be performed by building an appropriate circuit (see Fig. 1 for an example) using some combination of these three gates. In fact it is not necessary to use all these gates: they can themselves all be obtained using combinations of nand gates (Fig. 2), and so the nand gate is universal for classical computation. It is, however, necessary to proceed with some caution, as several other ªimplicitº gates are also required, such as the clone gate, which makes a copy of a bit, and the swap gate, which allows two wires to cross one another. This description works well with conventional computers, in which bit states are represented by voltages applied to wires, but it cannot be used with atomic computers. Atomic computers represent bit values using the quantum states of atomic systems, so a logic gate can neither create nor destroy bits; thus logic gates such as and, which have two input bits and only one output bit, are immediately ruled out. Similarly, atomic systems evolve under a series of unitary transformations, which correspond to reversible operations, while many of the operations described above are clearly not reversible. In order to build atomic computers, therefore, it is necessary to use a different approach, using only reversible logic operations. 3.2. Reversible computation The theory of reversible computation [15,27,28] has been studied extensively and, perhaps surprisingly, it is simple to perform any logic operation in a reversible manner. The only irreversible operation required when performing a computation [29,30] is the preparation of a well de®ned initial state, usually taken as having all bits in state 0; after this initialisation process the computation can be performed entirely reversibly. The basic approach needed to achieve reversible logic can be summarised in two simple rules. First, any logical inputs to a gate must be preserved in the outputs; this is most simply achieved by copying them to output bits without change. Secondly, the output of the gate (here assumed for simplicity to comprise a single bit) must be combined in a reversible fashion with an additional auxiliary bit, for example by adding the two bits together using binary arithmetic modulo two. Binary arithmetic modulo two, usually indicated by the symbol % , has the useful properties that x % 0 0 % x x and x % 1 1 % x not x; while x % x 0: A simple example of a reversible logic gate based on this approach is the controlled-not gate (see Fig. 3), which has two inputs, x and y and two corresponding outputs x0 and y0 . The ®rst input bit is copied to its output bit, so x0 x; and is also combined with the second input bit to give y0 x % y: Thus a not gate is applied to the second bit (the target bit) if and only if the ®rst bit (the control bit) is 330 J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360 Fig. 3. The controlled-not gate, which plays a central role in reversible and quantum computation. The target bit is marked by a % symbol, indicating the close relationship with binary arithmetic modulo two; the control bit is marked by a dot and a vertical control line (the dot is important in drawings of larger circuits where a control line may have to cross lines representing other bits)
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 a
in state 1. Note that a controlled-not gate is completely 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 particular 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 functions 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 simplicity 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 twolevel 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:
J-A. Jones/ Progress in Nucleo tic Resonance Spectroscopy 38(2001)325-360 classical bit, and so is called a quantum bit, or qubit superposition described by Eq. (1)and the second for short. a qubit in a superposition state is(in some qubit is in state o). This can be easily calculated as sense)in both of the states contributing to the super- quantum mechanics is linear, and so the effect of position at the same time, so a qubit can simulta- applying a gate to a superposition is a superposition neously occupy two different logical states of the results of applying the gate to the two eigen Computational circuits are implemented within states. Hence the result is quantum computers by performing physical manip- (0)+10) lo)(0)+liL() lations so that the computer evolves under a propaga tor which implements the desired unitary transformation. Just as circuits can be built up from Thus the quantum computer has simultaneously tes these propagators can ssembled from evaluated the values of f(o)and f(1). simpler elements, and so these propagators are often When applied to more complex systems, quantum referred to as circuits, even though their physical parallelism has potentially enormous power. Consider implementation may bear little resemblance to a function for which the input is described by n bits, so conventional electrical circuits. As before, this that there are 2 possible inputs(since n bits can be abstract model allows quantum computers to be used to describe any integer between 0 and 2"-1):a described in a device-independent fashion. quantum computer using n qubits as inputs can eval- As discussed below, it is possible to construct any uate the function over all of these 2" inputs in one step quantum circuit by combining a small number of In effect a quantum computer with n input qubits simple propagators, usually called gates. These gates appears to have the computational power of 2"classi only affect one or two qubits at a time, and so it is cal computers acting in parallel. Unfortunately it is perfectly practical to describe their propagators expli- not always possible to use this quantum parallelism citly, for example as a matrix. A matrix description in any useful way. Performing parallel function clearly depends on the choice of basis set, but the evaluation over n qubits will result in a state of the usual choice is to work in the computational basi form in which the basis vectors correspond with the differ ent logical states of the computer; thus for a two qubit gate the basis set is (00), 01), 10), 11)). In many 列f() proposed physical implementations of quantum computers, such as NMR, this basis set is also the natural basis for the system, as the basis states which is a superposition of the 2 possible inputs, each eigenstates of the background Hamiltonian entangled with its own function value. If any attempt is made to measure the state of the system, then the 4.1. Quantum parallelism superposition will collapse into one of its component values, r)f(r)), where the value of r is chosen at The central feature underlying all quantum algo- random. Thus even though it seems possible to eval- rithms is the idea of quantum parallelism, which in uate the function over its 2 input values, it is only turns stems from the ability of quantum systems to be possible to obtain one of these values. found in superposition states Consider once again the It is, however, sometimes possible to obtain useful reversible circuit for function evaluation( Fig. 6). This information in a more subtle way. In some cases, the can be achieved by constructing a propagator, Uf, answer of interest does not depend on specific values, fr), but only on global properties of the function itself. This is the basis of both Deutsch's toy algorithm a)b)→园a)b⊕f(a) (2) and Shor's quantum factoring algorithm d setting b)= o). The two values of the fu 4.2. Deutsch's algorithm f(O)and f(1), can then be evaluated by setting a)=o) and a)=1)as before. Now consider the effect of Deutsch's algorithm [23-25] was the first quantum applying this circuit when the first qubit is in a algorithm to be discovered, and is one of the few
classical bit, and so is called a quantum bit, or qubit for short. A qubit in a superposition state is (in some sense) in both of the states contributing to the superposition at the same time, so a qubit can simultaneously occupy two different logical states. Computational circuits are implemented within quantum computers by performing physical manipulations so that the computer evolves under a propagator which implements the desired unitary transformation. Just as circuits can be built up from gates these propagators can be assembled from simpler elements, and so these propagators are often referred to as circuits, even though their physical implementation may bear little resemblance to conventional electrical circuits. As before, this abstract model allows quantum computers to be described in a device-independent fashion. As discussed below, it is possible to construct any quantum circuit by combining a small number of simple propagators, usually called gates. These gates only affect one or two qubits at a time, and so it is perfectly practical to describe their propagators explicitly, for example as a matrix. A matrix description clearly depends on the choice of basis set, but the usual choice is to work in the computational basis, in which the basis vectors correspond with the different logical states of the computer; thus for a two qubit gate the basis set is {u00l; u01l; u10l; u11l}: In many proposed physical implementations of quantum computers, such as NMR, this basis set is also the natural basis for the system, as the basis states are eigenstates of the background Hamiltonian. 4.1. Quantum parallelism The central feature underlying all quantum algorithms is the idea of quantum parallelism, which in turns stems from the ability of quantum systems to be found in superposition states. Consider once again the reversible circuit for function evaluation (Fig. 6). This can be achieved by constructing a propagator, Uf, applied to two qubits, which performs ualubl ! Uf ualub % f al 2 and setting ubl u0l: The two values of the function, f(0) and f(1), can then be evaluated by setting ual u0l and ual u1l as before. Now consider the effect of applying this circuit when the ®rst qubit is in a superposition described by Eq. (1) and the second qubit is in state u0l. This can be easily calculated as quantum mechanics is linear, and so the effect of applying a gate to a superposition is a superposition of the results of applying the gate to the two eigenstates. Hence the result is u0l 1 u1l 2 p u0l ! Uf u0lu f 0l 1 u1lu f 1l 2 p : 3 Thus the quantum computer has simultaneously evaluated the values of f(0) and f(1). When applied to more complex systems, quantum parallelism has potentially enormous power. Consider a function for which the input is described by n bits, so that there are 2n possible inputs (since n bits can be used to describe any integer between 0 and 2n 2 1); a quantum computer using n qubits as inputs can evaluate the function over all of these 2n inputs in one step. In effect a quantum computer with n input qubits appears to have the computational power of 2n classical computers acting in parallel. Unfortunately it is not always possible to use this quantum parallelism in any useful way. Performing parallel function evaluation over n qubits will result in a state of the form 2 Xn 2 1 i0 uilu f il 2n=2 ; 4 which is a superposition of the 2n possible inputs, each entangled with its own function value. If any attempt is made to measure the state of the system, then the superposition will collapse into one of its component values, urluf(r)l, where the value of r is chosen at random. Thus even though it seems possible to evaluate the function over its 2n input values, it is only possible to obtain one of these values. It is, however, sometimes possible to obtain useful information in a more subtle way. In some cases, the answer of interest does not depend on speci®c values, f(r), but only on global properties of the function itself. This is the basis of both Deutsch's toy algorithm and Shor's quantum factoring algorithm. 4.2. Deutsch's algorithm Deutsch's algorithm [23±25] was the ®rst quantum algorithm to be discovered, and is one of the few 332 J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360
J.A. Jones/Progress in Nuclear Magnetic Resonance Spectroscopy 38(2001)325-360 quantum algorithms simple enough to describe here which take a quantum register into a uniform super The problem can be described in terms of function position of all its possible values: evaluation, but a more concrete picture can be obtained by thinking about coins. Normal coins 100)-(00)+101)+ 10)+ 11)/2 have two different faces, conventionally called heads and tails. but fake coins can be obtained This can be easily achieved by applying a one qubit both faces Hadamard to each qubit which have the same pattern Another important property of the Hadamard Consider an unknown coin, which could be either a gate can be seen by examining the right hand normal coin or a fake coin. In order to determine sides of Eqs. (5)and(6). These differ only by which type it is, it would seem necessary to look at the presence of a minus sign, so the two super- both sides to find out whether they showed heads or tails. and then see whether these two results were the positions differ only by the phase with which the two eigenstates are combined. The ability of the same(a false coin) or different(a true coin). With a Hadamard gate to convert such phase differences quantum device, however, it would be possible to look at both sides simultaneously, and thus determine into different eigenstates plays a central role in many quantum algorithms whether the coin was normal or fake in a singl anc 4.4. Universality of quantum gates The trick lies in abandoning any attempt to deter mine the pattern shown on either side of the coin The gates we have seen so far are enough to explain instead one must simply ask whether the two faces some simple quantum algorithms; for example, are the same or different. This is a property not of Deutsch's algorithm can be described using only the individual faces of the coin, but of the whole Hadamard gates and reversible function evaluation coin, and thus may be extracted from a state of the gates. It is, however, useful to consider other more kind described by Eq (3). A more detailed explana general quantum gates; indeed as any unitary trans- tion of this approach is given in Section 11 formation can be considered as a quantum gate, we may need to consider an infinite number of gates 4.3. Ouantum gates Within classical models of computation(both reversible and irreversible) it is possible to construct Just as classical reversible computations can be any desired gate by combining copies of a small performed using circuits built up out of reversible number of simple gates. A similar situation applies gates,quantum circuits can be constructed using in quantum computation, but in this case there are uantum gates [31]. Unlike classical circuits, an infinite number of possible gates(even if we however,quantum circuits can include gates which restrict ourselves to single qubit gates, any rotation generate and analyse qubits which are in superpo around any axis constitutes a valid one qubit gate). of Clearly it cannot be possible to construct an infinite One such gate is the single qubit Hadamard gate, H, number of different gates by combining a finite which implements the transformations number of simpler gates, but it is possible to simulate (0)+|1)2 any gate to any desired accuracy [32, 33], which is (5) good enough. Perhaps surprisingly there very large number of two qubit gates which are l)2(0)-1)2 universal in this restricted sense, in that it is possi to simulate any desired gate(that is, any unitary trans- discussed below, this is closely related to a 90 formation) using only one of these universal gates pulse, but differs in some subtle ways; in particular the together with its twin, obtained by swapping the Hadamard is its own inverse roles of the two qubits. Indeed, mathematically speak The Hadamard gate is useful as it takes a qubit in an ing, almost all two qubit gates are universal [34-36] eigenstate to a uniform superposition of states. By While mathematically interesting, this result is of one can de efine multi-qubit Hadamard gates little immediate practical implication for most
quantum algorithms simple enough to describe here. The problem can be described in terms of function evaluation, but a more concrete picture can be obtained by thinking about coins. Normal coins have two different faces, conventionally called heads and tails, but fake coins can be obtained which have the same pattern on both faces. Consider an unknown coin, which could be either a normal coin or a fake coin. In order to determine which type it is, it would seem necessary to look at both sides to ®nd out whether they showed heads or tails, and then see whether these two results were the same (a false coin) or different (a true coin). With a quantum device, however, it would be possible to look at both sides simultaneously, and thus determine whether the coin was normal or fake in a single glance. The trick lies in abandoning any attempt to determine the pattern shown on either side of the coin; instead one must simply ask whether the two faces are the same or different. This is a property not of the individual faces of the coin, but of the whole coin, and thus may be extracted from a state of the kind described by Eq. (3). A more detailed explanation of this approach is given in Section 11. 4.3. Quantum gates Just as classical reversible computations can be performed using circuits built up out of reversible gates, quantum circuits can be constructed using quantum gates [31]. Unlike classical circuits, however, quantum circuits can include gates which generate and analyse qubits which are in superpositions of states. One such gate is the single qubit Hadamard gate, H, which implements the transformations u0l ! H u0l 1 u1l= 2 p 5 u1l ! H u0l 2 u1l= 2 p 6 As discussed below, this is closely related to a 908 pulse, but differs in some subtle ways; in particular the Hadamard is its own inverse. The Hadamard gate is useful as it takes a qubit in an eigenstate to a uniform superposition of states. By analogy one can de®ne multi-qubit Hadamard gates which take a quantum register into a uniform superposition of all its possible values: u00l ! H u00l 1 u01l 1 u10l 1 u11l=2: 7 This can be easily achieved by applying a one qubit Hadamard to each qubit. Another important property of the Hadamard gate can be seen by examining the right hand sides of Eqs. (5) and (6). These differ only by the presence of a minus sign, so the two superpositions differ only by the phase with which the two eigenstates are combined. The ability of the Hadamard gate to convert such phase differences into different eigenstates plays a central role in many quantum algorithms. 4.4. Universality of quantum gates The gates we have seen so far are enough to explain some simple quantum algorithms; for example, Deutsch's algorithm can be described using only Hadamard gates and reversible function evaluation gates. It is, however, useful to consider other more general quantum gates; indeed as any unitary transformation can be considered as a quantum gate, we may need to consider an in®nite number of gates. Within classical models of computation (both reversible and irreversible) it is possible to construct any desired gate by combining copies of a small number of simple gates. A similar situation applies in quantum computation, but in this case there are an in®nite number of possible gates (even if we restrict ourselves to single qubit gates, any rotation around any axis constitutes a valid one qubit gate). Clearly it cannot be possible to construct an in®nite number of different gates by combining a ®nite number of simpler gates, but it is possible to simulate any gate to any desired accuracy [32,33], which is good enough. Perhaps surprisingly there exists a very large number of two qubit gates which are universal in this restricted sense, in that it is possible to simulate any desired gate (that is, any unitary transformation) using only one of these universal gates together with its twin, obtained by swapping the roles of the two qubits. Indeed, mathematically speaking, almost all two qubit gates are universal [34±36]. While mathematically interesting, this result is of little immediate practical implication for most J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360 333
J.A. Jones/ Progress in Nuclear Magnetic Resonance Spectroscopy 38(2001)325-360 possible implementations of a quantum computer, as combined together to implement any other desired it is usually more sensible to use a larger and more gate. While many different sets of gates are possible convenient set of gates. As one qubit gates are usually a simple approach is to implement the set of all possi much simpler to perform than gates involving two or ble one qubit gates, together with one or more non- more qubits, it is often reasonable to assume that any trivial two qubit gates [33] one qubit gate(or, at least a reasonable approximation One qubit gates correspond to rotations of a sp to it) is available. The combination of this set of one within its own one-spin Hilbert space, which can be qubit gates with any single non-trivial two qubit gate, readily achieved using RF fields. Note that it is neces such as the controlled-NOT gate forms an adequate set sary to apply these rotations selectively to individual [33], from which any other gate may be built with qubits. In most other suggested implementations of relative ease quantum computation [2,3] this is easily achieved using some type of spatial localisation: the physical objects implementing the qubits are located at well 5. Building NMR quantum computers defined and distinct locations in space. This approach While it would in principle be possible to use a is not possible in NMR, as each qubit is implemented using an ensemble of nuclei. each of which is located wide range of different approaches to build a quantum at a different place in the NMR sample, and all of computer,all the main proposals to date [2,3] have which are undergoing rapid motion Instead different used broadly similar approaches, based on the quan- qubits are implemented using different nuclei in the tum circuit model outlined above. This model contains five major components, each of which must same molecule, and they are distinguished using the different resonance frequencies of each nucleus be implemented in order to construct a working computer [37]. Four central components can all be Two qubit gates, such as the controlled-NOT gate, implemented within NN are more complicated as they involve conditional below, while the fifth component, error correction evolution(that is, the evolution of one spin must is discussed in Section 12 depend on the state of the other spin), and thus require some interaction between the two qubits. The J- 5.1. Qubits coupling in NMR is well suited to this purp Note that all the different nuclei making up an NMR The first of these requirements, a set of qubits quantum computer must participa appears easy to achieve, as the two spin states of coupling network. It is not necessary(or even desir- spin-1/2 nuclei in a magnetic field provide a natural able)that all the nuclei are directly coupled together implementation. However, one important feature but they must be connected, directly or indirectly, by which distinguishes NMR quantum computers from some chain of resolved couplings. Since J-coupling other suggested implementations is that NMR studies only occurs within a molecule, and does not connect not a single isolated quantum system, but rather a very different molecules, we can treat an ensemble of large number (effectively an ensemble) of such molecules as an ensemble of identical mutually systems. Thus an NMR quantum computer is actually isolated computers an ensemble of indistinguishable computers, one on each molecule in the NMR sample. This has a number 5.3. Initialisation of subtle and important consequences as discussed below Quantum logic gates transform qubits from one state to another, but this is only useful if the qubits 5.2. Logic gates start off in some well defined initial state. In practice it is sufficient to have some method for reaching any one In order to perform an arbitrary computation it is initial state, and the obvious choice is to have all the necessary to implement arbitrary quantum logic qubits in the o)state, corresponding to a CLEAR opera circuits. This can be achieved as long as it is possible tion. Any other desired starting state can then be easily to implement an adequate set of gates, which can be
possible implementations of a quantum computer, as it is usually more sensible to use a larger and more convenient set of gates. As one qubit gates are usually much simpler to perform than gates involving two or more qubits, it is often reasonable to assume that any one qubit gate (or, at least a reasonable approximation to it) is available. The combination of this set of one qubit gates with any single non-trivial two qubit gate, such as the controlled-not gate forms an adequate set [33], from which any other gate may be built with relative ease. 5. Building NMR quantum computers While it would in principle be possible to use a wide range of different approaches to build a quantum computer, all the main proposals to date [2,3] have used broadly similar approaches, based on the quantum circuit model outlined above. This model contains ®ve major components, each of which must be implemented in order to construct a working computer [37]. Four central components can all be implemented within NMR systems as described below, while the ®fth component, error correction, is discussed in Section 12. 5.1. Qubits The ®rst of these requirements, a set of qubits, appears easy to achieve, as the two spin states of spin-1/2 nuclei in a magnetic ®eld provide a natural implementation. However, one important feature which distinguishes NMR quantum computers from other suggested implementations is that NMR studies not a single isolated quantum system, but rather a very large number (effectively an ensemble) of such systems. Thus an NMR quantum computer is actually an ensemble of indistinguishable computers, one on each molecule in the NMR sample. This has a number of subtle and important consequences as discussed below. 5.2. Logic gates In order to perform an arbitrary computation it is necessary to implement arbitrary quantum logic circuits. This can be achieved as long as it is possible to implement an adequate set of gates, which can be combined together to implement any other desired gate. While many different sets of gates are possible, a simple approach is to implement the set of all possible one qubit gates, together with one or more nontrivial two qubit gates [33]. One qubit gates correspond to rotations of a spin within its own one-spin Hilbert space, which can be readily achieved using RF ®elds. Note that it is necessary to apply these rotations selectively to individual qubits. In most other suggested implementations of quantum computation [2,3] this is easily achieved using some type of spatial localisation: the physical objects implementing the qubits are located at well de®ned and distinct locations in space. This approach is not possible in NMR, as each qubit is implemented using an ensemble of nuclei, each of which is located at a different place in the NMR sample, and all of which are undergoing rapid motion. Instead different qubits are implemented using different nuclei in the same molecule, and they are distinguished using the different resonance frequencies of each nucleus. Two qubit gates, such as the controlled-not gate, are more complicated as they involve conditional evolution (that is, the evolution of one spin must depend on the state of the other spin), and thus require some interaction between the two qubits. The Jcoupling in NMR is well suited to this purpose. Note that all the different nuclei making up an NMR quantum computer must participate in a single coupling network. It is not necessary (or even desirable) that all the nuclei are directly coupled together, but they must be connected, directly or indirectly, by some chain of resolved couplings. Since J-coupling only occurs within a molecule, and does not connect different molecules, we can treat an ensemble of molecules as an ensemble of identical mutually isolated computers. 5.3. Initialisation Quantum logic gates transform qubits from one state to another, but this is only useful if the qubits start off in some well de®ned initial state. In practice it is suf®cient to have some method for reaching any one initial state, and the obvious choice is to have all the qubits in the u0l state, corresponding to a clear operation. Any other desired starting state can then be easily obtained. 334 J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360