清华大学：生物核磁共振波谱学（英文）：Jones-38-325-NMR quantum computation

NMR quantum computation J.A. Jones a,b, * a Oxford Centre for Molecular Sciences, New Chemistry Laboratory, South Parks Road, Oxford OX1 3QT, UK b Centre for Quantum Computation, Clarendon Laboratory, Parks Road, Oxford OX1 3PU, UK Received 31 July 2000 Contents 1. Introduction .................................................................. 326 1.1. Structure and scope ......................................................... 326 2. Limits to computation ........................................................... 327 2.1. Computational complexity .................................................... 327 2.2. Quantum complexity ........................................................ 328 3. Atomic computation ............................................................ 329 3.1. Computational circuits ...................................................... 330 3.2. Reversible computation ...................................................... 330 3.3. Reversible function evaluation ................................................. 331 4. Quantum computation ........................................................... 331 4.1. Quantum parallelism ........................................................ 332 4.2. Deutsch’s algorithm ........................................................ 332 4.3. Quantum gates ............................................................ 333 4.4. Universality of quantum gates ................................................. 333 5. Building NMR quantum computers ................................................. 334 5.1. Qubits .................................................................. 334 5.2. Logic gates ............................................................... 334 5.3. Initialisation .............................................................. 334 5.4. Readout ................................................................. 335 5.5. Some two spin systems ...................................................... 335 5.6. Scaling the system up ....................................................... 336 6. Qubits and NMR spin states ....................................................... 336 6.1. One qubit states ........................................................... 337 6.2. Two qubit states ........................................................... 337 7. NMR logic gates ............................................................... 338 7.1. One qubit gates ............................................................ 338 7.2. Controlled-not gates ....................................................... 339 7.3. Other two qubit gates ....................................................... 340 7.4. Gates in larger spin systems .................................................. 340 Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 0079-6565/01/$ - see front matter q 2001 Elsevier Science B.V. All rights reserved. PII: S0079-6565(00)00033-9 www.elsevier.nl/locate/pnmrs * Tel.: 144-1865-272247; fax: 144-1865-272387. E-mail address: jones@qubit.org (J.A. Jones). 7.5. Multi-qubit logic gates ...................................................... 340 7.6. Single transition selective pulses . . ............................................. 340 7.7. Geometric phase-shift gates ................................................... 341 8. Initialisation and NMR .......................................................... 341 8.1. Spatial averaging .......................................................... 342 8.2. Logical labelling ........................................................... 342 8.3. Temporal averaging ........................................................ 343 8.4. The use of “cat” states ...................................................... 343 9. Readout ..................................................................... 344 9.1. Simple readout ............................................................ 344 9.2. Tomography .............................................................. 345 10. Practicalities .................................................................. 345 10.1. Selective pulses ........................................................... 345 10.2. Composite pulses .......................................................... 346 10.3. Abstract reference frames .................................................... 346 11. Simple algorithms .............................................................. 347 11.1. Functions and phases ....................................................... 347 11.2. Deutsch’s algorithm ........................................................ 347 11.3. NMR implementations ...................................................... 348 11.4. Extensions and simplifications ................................................. 349 11.5. Grover’s quantum search ..................................................... 350 11.6. NMR implementations ...................................................... 351 11.7. Extensions ............................................................... 352 12. Quantum phenomena ............................................................ 353 12.1. Entangled states ........................................................... 353 12.2. Quantum teleportation ....................................................... 353 12.3. Error correction ........................................................... 354 13. NMR and entanglement .......................................................... 355 13.1. Quantifying entanglement .................................................... 356 13.2. NMR and quantum mechanics ................................................. 357 14. Conclusions .................................................................. 357 Acknowledgements ................................................................ 358 Appendix A. An explicitly separable decomposition of a pseudo-entangled state ................... 358 References ...................................................................... 358 1. Introduction Quantum computation [1–3] offers the prospect of revolutionising many areas of science by allowing us to solve problems well beyond the power of our current classical computers [4]. In particular a quan- tum computer would be superb for simulating the behaviour of other complex quantum mechanical systems [5,6]. Although the theory of quantum computation has been studied for many years, and many important theoretical results have been obtained, early attempts to actually build even the smallest quantum computer proved extremely challenging. In recent years there has been considerable interest in the use of NMR techniques [7] to implement quan- tum computations [8–14]. It has proved surprisingly simple to build small NMR quantum computers, and while such computers are themselves too small for any practical use, their mere existence has brought great excitement to a field largely deprived of experi- mental achievements. 1.1. Structure and scope In this article I will describe how NMR techniques may be used to build simple quantum information processing devices, such as small quantum computers, J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360326 and show how these techniques are related to more conventional NMR experiments. Many tricks and techniques well known from conventional NMR studies can be applied to NMR quantum computation, and it is likely that some of these will be applied in any large scale quantum computer which is eventually built. Conversely, techniques from quantum computa- tion could have applications within NMR. It is impossible to explain how NMR may be used to implement quantum computations without first explaining what quantum computation is, and what it could achieve. This in turn requires a brief discus- sion of classical reversible computation [15]. In order to reduce these introductory sections to a reasonable length many technical points have inevitably been skipped over. Wherever possible I will use traditional product operator notation [16] to describe how NMR quantum computers are implemented; it will some- times, however, be necessary to use more abstract quantum mechanical notations [17] to describe what these computers seek to achieve. Before the advent of NMR quantum computation, almost all research in this field was performed within a small community of physicists and mathematicians. Some important results have never been published as conventional papers, but simply circulate as electronic preprints; copies of most of these can be obtained from the quant-ph archive on the LANL e-print server [18]. Similarly, many other papers appear as LANL e-prints long before more formal publication. 2. Limits to computation Over the last forty years there has been astonishing progress in the power of computational devices using silicon based integrated circuits. This progress is summarised in a set of “laws”, usually ascribed to Moore, although some were developed by other people. Over this period the power of computational devices has roughly doubled every eighteen months, or increased ten-fold every five years. Unfortunately, this extraordinary technological progress may not continue for much longer, as this increase in comput- ing power requires a corresponding decrease in the size of the transistors on the chip; this shrinking process cannot be continued indefinitely as the tran- sistors will eventually be reduced to the atomic scale. At current rates of progress it is estimated [19] that the ultimate limits of this approach will be reached by about 2012, and any further progress in the power of our computers will require a radically different approach. One possible approach is to use the power offered by quantum computation. 2.1. Computational complexity Even if the problems described above are side- stepped in some way, there are still strong limits to the problems which we can solve with current compu- ters. These limits are derived from the underlying theory of computation itself, and in particular from computational complexity theory [20]. Complexity theory considers the classification of mathematical problems according to how difficult they are to deal with, and seeks to divide them into those which are relatively easy (tractable) and those which are uncom- fortably difficult (intractable). Note that complexity theory is not concerned with problems which we do not know how to solve, or which we know cannot be solved, but only with problems for which an algorith- mic solution (tractable or intractable) is known. The classical theory of computation has remained largely unchanged for decades, with a central role played by the Church–Turing thesis. This asserts that all physically reasonable models of computation are ultimately equivalent to one another, so that it is not really necessary to consider any particular compu- ter when assessing the complexity of a problem; any reasonable model will do. In particular, the tractability or otherwise of a problem is independent of the computational device used. As we will see, quantum computation challenges this thesis, as quantum computers appear to be fundamentally more powerful than their classical equivalents. To make further progress it is necessary to use a more precise measure of the complexity of an algo- rithm. The usual approach is to determine the compu- tational resources (most commonly defined as the number of elementary computational operations) required to implement it. Clearly this measure will depend on the exact nature of the computational resources available to our computer, and so this is not directly useful. A better approach is to consider not a single isolated problem, but a family of closely related problems, and to determine how the resources J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 327 required scale within this family. To take a simple example, adding two n digit numbers with pencil and paper requires n separate additions, together with n carries, and so the time required for addition scales linearly with n. Similarly, multiplying two n digit numbers by long multiplication requires n 2 multiplications and a similar number of additions. Mathematically, adding two n digit numbers is said to be O(n) (that is, of order n). The exact number of steps required will depend on exactly how elementary computational steps are counted, but the total number of steps will always scale linearly with n. Similarly, long multiplication can always be performed in a number of steps which varies quadratically with n, and so is O(n 2 ). The complexity of a problem, rather than an algo- rithm, may be defined as the complexity of the best known algorithm for solving the problem; thus addi- tion is O(n). It might seem that multiplication is O(n 2 ), but in fact long multiplication is not the best known algorithm; a better approach is known with complex- ity about O(n log n) [20]. Strictly speaking one should also distinguish between an upper bound on the number of steps known to be sufficient to solve a problem (indicated by O), and a lower bound on the number of steps known to be required to solve a problem (indicated by V); a problem, such as addition of n digit numbers, which is both O(n) and V(n)is denoted as Q(n). Problems, such as addition and multiplication, whose complexity is at worst a polynomial function of n, are said to be easy, while problems whose complexity is worse than a polynomial function of n are said to be hard. For example, consider the problem of finding the prime factors of an n digit composite number. The obvious way to do this is to simply try dividing the composite number by every number less than its square root; as there are approximately 10 n p 10 n=2 such trial divisors, this algorithm has complexity O(10 n/2 ). Better algorithms for factoring are known, but they all have the same property of exponential complexity. For problems with polynomial complexity, espe- cially those whose complexity is described by a low power of n, such as n or n 2 , the effort required to solve a problem increases only slowly with n. Thus it should be possible to tackle such problems for a reasonable range of input sizes, and a modest increase in computer power should give a significant increase in this range. Exponential functions, however, rise extre- mely rapidly with n, and so it will only be possible to solve problems with exponential complexity for rela- tively small input sizes; furthermore a modest increase in computer power will result in only a tiny increase in the range of problems that can be solved. The apparent exponential complexity of factoring is a matter of some importance, as it underlies many cryptographic schemes in use today, notably those based on the Rivest–Shamir–Adleman (RSA) approach to public key cryptography, such as Pretty Good Privacy (PGP) [21]. These schemes involve a public key, which anyone may use to encrypt a message, and a private key, which is required to decrypt such messages. The relationship between these two keys is equivalent to the relationship between the product of two large prime numbers and the two prime numbers themselves. The security of the system depends on the difficulty of determining the private key from a long public key, which itself depends on the complexity of factoring. By contrast, the computational complexity of encrypting and decrypting messages is only a polynomial function of the size of the keys. Thus a small increase in the amount of effort required to use the cryptographic scheme results in an enormous increase in its security. 2.2. Quantum complexity Quantum computation offers the possibility of bypassing some of the limits apparently imposed by complexity theory. This is because a quantum compu- ter could implement entirely new classes of algo- rithms which would allow currently intractable problems to be solved with ease. The first serious discussion of quantum computa- tion was by Feynman, who analysed the difficulty of simulating quantum mechanical systems using classi- cal computers [5]. This difficulty is well known and easy to understand; it arises from the enormous free- dom available to quantum systems. For example, a system of n coupled spin-1/2 nuclei inhabits a Hilbert space of size 2 n , and so must be described by a vector with 2 n components. Thus it appears that any classical algorithm to simulate the behaviour of n spin-1/2 parti- cles must have complexity at least O(2 n ); within NMR this corresponds to the well known computational J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360328 difficulty of simulating a large strongly coupled spin system. This apparently inevitable exponential complexity makes the simulation of quantum mechan- ical systems an intractable problem. Despite this apparent complexity, however, coupled spin systems evolve in the “correct” manner. Thus, in some sense, such a spin system appears to have the capacity to solve a problem which is intract- able by conventional classical means. Clearly using a system to simulate itself is not a huge step forward, but Feynman suggested that it might also be possible to use one quantum mechanical system to simulate another quite different system. Thus an easily control- lable system might be used to simulate the behaviour of another less well behaved system, while a carefully chosen system might be usable as a general purpose quantum simulator [5,6]. Feynman’s ideas appear to have been limited to the simulation of physical systems, and the ideas he described have more in common with analogue computers than with current digital computers. In 1985, however, Deutsch extended these ideas and described a quantum mechanical Turing machine, which could act as a general purpose computer [22]. Deutsch also described a (somewhat contrived) problem [23–25] which could be solved more effi- ciently on a quantum mechanical computer than on any classical computer, suggesting that it might be possible to use a quantum computer to solve otherwise intractable problems. Since that time several quantum algorithms [26] have been developed, the most notable of which is Shor’s quantum factoring algorithm [4]; this allows a composite number to be factored with a complexity only slightly greater than O(n 2 ), thus rendering factor- ing tractable. As well as being of great mathematical interest, this algorithm has obvious practical signifi- cance, as it poses a threat to many current crypto- graphic schemes. The discovery of Shor’s algorithm triggered an enormous increase in research directed at quantum computation and related areas of quantum information theory. 3. Atomic computation Before describing how quantum mechanical com- puters can be built, it is useful to consider how an atomic scale system, such as a group of coupled nuclei, could be used to implement classical com- putations [15,27,28]. Discussions of this predate J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 329 Fig. 1. A circuit to compute the exclusive-or (xor) function, z x xor y, using and, or and not gates. Note that this circuit uses three implicit gates, two clone gates, shown as small circles, where wires split into two (to copy the input) and one swap gate (where the wires cross over). These implicit gates are fairly easy to implement in traditional electronic computers, but can cause problems in other designs and so cannot simply be ignored. Some authors even consider the wires which interconnect gates as non-trivial gates in their own right. Fig. 2. (a) A circuit to compute the exclusive-or (xor) function, z x xor y, using only nand and not gates. This is not the best such circuit; simpler circuits are known, but this one preserves the basic structure seen in Fig. 1. (b) A circuit to implement a not gate, y not x, using a nand gate. By combining circuits (a) and (b) it is possible to implement xor using only nand gates. Any other function may be computed in a similar fashion, and so nand is a universal gate. Note, however, that both circuits use implicit clone gates, while (a) also uses one implicit swap gate. suggestions that quantum devices might have funda- mentally 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 final state of some group of bits (the “output register”) depends on the result of the desired computation. As will be shown later, quantum compu- tation is very similar, except that the bits are not confined 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 opera- tion can be performed by building an appropriate circuit (see Fig. 1 for an example) using some combi- nation 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 rever- sible 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 surpris- ingly, 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 defined initial state, usually taken as having all bits in state 0; after this initialisa- tion 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 x 0 and y 0 . The first input bit is copied to its output bit, so x 0 x; and is also combined with the second input bit to give y 0 x % y: Thus a not gate is applied to the second bit (the target bit) if and only if the first bit (the control bit) is J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360330 Fig. 3. The controlled-not gate, which plays a central role in rever- sible 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). in 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, x 0 , y 0 and z 0 . The first two input bits, which are the logical inputs, are copied unchanged, so that x 0 x and y 0 y.Anot gate is then applied to the third bit if and only if both x and y are in state 1; hence z 0 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 field, 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 confined 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 x 0 x; y 0 y; and z 0 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: a 0 a and b 0 b % f a : 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 super- position at the same time, so a qubit can simulta- neously occupy two different logical states. Computational circuits are implemented within quantum computers by performing physical manipu- lations so that the computer evolves under a propaga- tor 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 expli- citly, 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 differ- ent 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 algo- rithms 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, U f , applied to two qubits, which performs ualubl! U f ualub % f a l 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 first 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 eigen- states. Hence the result is u0l 1 u1l 2 p u0l! U f u0lu f 0 l 1 u1lu f 1 l 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 2 n possible inputs (since n bits can be used to describe any integer between 0 and 2 n 2 1); a quantum computer using n qubits as inputs can eval- uate the function over all of these 2 n inputs in one step. In effect a quantum computer with n input qubits appears to have the computational power of 2 n classi- cal 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 X 2 n 2 1 i 0 uilu f i l 2 n=2 ; 4 which is a superposition of the 2 n 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 eval- uate the function over its 2 n 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 specific 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 first quantum algorithm to be discovered, and is one of the few J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360332 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 find 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 deter- mine 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 explana- tion 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 superposi- tions 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 define multi-qubit Hadamard gates which take a quantum register into a uniform super- position 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 super- positions 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 trans- formation can be considered as a quantum gate, we may need to consider an infinite 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 infinite 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 infinite number of different gates by combining a finite 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 trans- formation) using only one of these universal gates together with its twin, obtained by swapping the roles of the two qubits. Indeed, mathematically speak- ing, 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 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 quan- tum circuit model outlined above. This model contains five 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 fifth component, error correction, is discussed in Section 12. 5.1. Qubits The first of these requirements, a set of qubits, appears easy to achieve, as the two spin states of spin-1/2 nuclei in a magnetic field 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 possi- ble one qubit gates, together with one or more non- trivial 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 fields. Note that it is neces- sary 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 defined 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 J- coupling 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 desir- able) 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 defined initial state. In practice it is sufficient 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 opera- tion. Any other desired starting state can then be easily obtained. J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360334 When, as for NMR, the computational basis coin- cides with the natural basis of the quantum system it should in principle be easy to implement clear as it takes the quantum computer to its energetic ground state, and this can be achieved by some cooling process. Unfortunately this approach is not practical in NMR as the Zeeman energy gap is small compared with the Boltzman energy at any reasonable temperature; thus at room temperature the population of all the states will be almost equal, with only small deviations (around one part in 10 4 ) from the average. Techniques for enhan- cing spin polarisation [38], such as optical pumping [39–41], and the use of para-hydrogen [42–44] allow this deviation to be increased, but with the exception of optically pumped noble gases it has so far proved impos- sible to even approach a pure ground state system. This apparent inability to implement the CLEAR operation led to NMR being rejected as a practical technology for implementing quantum computers. Recently, however, it was realised [8] that this conclu- sion was over hasty, as with an ensemble quantum computer it is not actually necessary to produce a pure ground state; instead it suffices to produce a state which behaves in the same manner as the pure ground state. This point can be clarified by consider- ing the density matrix describing a single isolated spin-half nucleus. This exhibits nearly equal popula- tions for the two eigenstates, but with a slight excess in the (low energy) u0l state compared with the (slightly higher energy) u1l state. No NMR signal will be observed from the equal populations, as the signals from different molecules will cancel out, but a small signal can be seen which arises from the devia- tions away from the average. Thus, ignoring questions of signal intensity, for a single isolated nucleus the thermodynamic equilibrium state is indistinguishable from a pure u0l state. States of this kind are often called pseudo-pure states,oreffective pure states [8–10]. Unfortunately the simple approach outlined above does not work for larger spin systems, as the pattern of population devia- tions is more complicated, and does not have the desired form. Several different techniques have, however, been developed to tackle this problem. 5.4. Readout The last stage in any quantum computation is to characterise the final state of the system, so that the result of the computation may be read out. Just as for initialisation, a range of different approaches have been used, but all these approaches combine two major elements. For simplicity I will assume that the computation ends with the result qubits in eigenstates; thus it is only necessary to determine whether a given qubit is in (the pseudo-pure) state u0l or u1l. The simplest approach is to apply a 908 pulse to the corresponding spin, and observe the NMR spectrum [11]. Since u0l corresponds to the ground state, a qubit in u0l will give rise to an absorption line; correspond- ingly a qubit in state u1l will give an emissive signal. It is, of course, necessary to acquire some sort of refer- ence signal, in order to distinguish between these two extremes, but this can be easily achieved by acquiring the spectrum of the pseudo-pure initial state. The second major approach [12] is to determine the state of one qubit by analysing the multiplet structure within the spectrum of a neighbouring spin. If several spins are coupled together, then individual lines within a multiplet can be assigned to specific states of these neighbours. Thus, the spectrum of one spin can give information on the states of several different qubits. 5.5. Some two spin systems While a number of different systems have been used to build small NMR quantum computers, all their major features can be explored using two differ- ent two-qubit systems which were used in the earliest demonstrations of NMR quantum computation [11,12]. The most important difference between these systems is that one uses a homonuclear two- spin system, while the other is heteronuclear. The first example system uses the two 1 H nuclei of partially deuterated cytosine in D 2 O (see Fig. 7). As J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 335 Fig. 7. The structure of partially deuterated cytosine obtained by dissolving cytosine in D 2 O; the three protons bound to nitrogen nuclei exchange with solvent deuterons, leaving two 1 H nuclei as an isolated two spin system (all other nuclei can be ignored). this system is homonuclear it is possible to excite both nuclei with a single hard pulse, and to observe both nuclei in the same spectrum. Another more subtle advantage is that the pattern of Boltzmann popula- tions is simpler in homonuclear systems than in their heteronuclear counterparts. There are, however, two significant disadvantages of such as system. Firstly the two 1 H multiplets have relatively similar frequencies, as they lie only about 1.51 ppm apart, and thus it is necessary to use soft frequency selective pulses [45] (or sequences of hard pulses and delays with equivalent effects) in order to address the spins individually. Secondly, the J-coupling between the two spins is relatively small (about 7 Hz), and so controlled gates take a fairly long time to implement. It would, of course, be possible to choose a different molecule, in which the chemical shift difference or J- coupling was larger, but it is difficult to improve one without making the other worse. While it is unlikely that cytosine is the absolutely optimal choice, no other homonuclear 1 H system would be very much better. The heteronuclear alternative is probably the most widely used two qubit NMR system. It is based on the 1 H and 13 C nuclei in 13 C-labelled chloroform. This has the huge advantage that it is possible to separately excite the two spins using hard pulses, rendering selective excitation essentially trivial. Furthermore, the relatively large size of the J-coupling allows two qubit gates to be performed much more rapidly than in homonuclear systems. In this heteronuclear system it is not possible to acquire signals from both spins simultaneously, but this is not a major problem as it is possible to determine the states of both spins by examining either the 1 H or the 13 C spectrum. Simi- larly, the complex pattern of populations over the four energy levels of this system does not fit with the origi- nal scheme for generating pseudo-pure states; however, some more modern schemes are in fact simpler to implement in heteronuclear systems. Considering all these issues together, it is not easy to say whether it is better to use homonuclear or heteronuclear systems to implement two qubit NMR quantum computers: heteronuclear systems are perhaps simpler to work with, but homonuclear systems give more elegant results. With larger spin systems the issues become even more complex, and a wide range of options have been explored. It is clear, however, that the simplest approach of using a fully heteronuclear spin system is unlikely to be practical beyond five qubit systems, as there are only five “obvious” spin-half nuclei which can be used ( 1 H, 13 C, 15 N, 19 F and 31 P). In practice NMR quantum computers with more than three qubits are likely to include two or more spins of the same nuclear species; it is, therefore, essential to consider how computation can be performed in homonuclear systems. 5.6. Scaling the system up The requirements outlined above are adequate for building small quantum computers, suitable for simple demonstrations of quantum information processing. If, however, one wishes to build a large scale quantum computer, suitable for performing interesting computations, then it is necessary to consider whether the approaches used are limited to such small systems, or whether (and if so, how) they can be scaled up. A fifth requirement for practical quantum computation [37], the implementation of fault-tolerant quantum error correction, is described in Section 12. This is an important practical question, but not one which will be addressed in detail here. The problems of scaling up NMR quantum computers are formid- able, and have been well described elsewhere [38,46,47]. Most authors now agree that NMR approaches are likely to be limited to computers containing 10–20 qubits; this is significantly smaller than estimates of the size required to perform useful computations (50–300 qubits). Furthermore the apparent inability of NMR systems to perform effi- cient quantum error correction rules out their use for many types of problem. The fundamental difficulties involved in scaling up current NMR quantum computers to large sizes have led some authors to suggest that this approach does not actually implement real quantum computation at all. This is a quite subtle question which will be discussed further in Section 13 below. 6. Qubits and NMR spin states Traditional designs for quantum computers comprise a number of two-level systems which inter- act with one another and have some specific interac- tion with the outside world, through which they can be J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360336 monitored and controlled, but are otherwise isolated. NMR systems are rather different: a typical NMR sample comprises not one spin-system, but a very large number of copies, one from each molecule in the sample, effectively forming an ensemble of copies. Traditional quantum computers are usually described using Dirac’s bra(c)ket notation [17], but NMR systems are better described using density matrices, usually written in the product operator basis [16], which has a number of important conse- quences. It is possible to draw close analogies between the states of traditional quantum computers and those used in descriptions of NMR systems [48], but it is necessary to proceed with caution. 6.1. One qubit states A single qubit can be in either of its two eigenstates, u0l and u1l, or in some linear superposition of them. Such a state is most conveniently written as a column vector in Hilbert space, for example ucl c 0 c 1 ! : 8 NMR quantum computers cannot be properly described in this way; instead they must be described using the corresponding density matrix r uclkcu c p 0 c 0 c p 1 c 0 c p 0 c 1 c p 1 c 1 ! 9 which can then be decomposed as a sum of the four Pauli basis states or their product operator equiva- lents, 1 2 E, I x , I y , and I z . Consider first the eigenstates, u0l and u1l, which correspond to the density matrices u0lk0u 10 00 ! 1 2 E 1 I z 10 and u1lk1u 00 01 ! 1 2 E 2 I z ; 11 respectively. As all NMR observables are traceless, multiples of the unit matrix can be added to density matrices at will, and so as far as any NMR experiment is concerned the density matrix I z is equivalent to u0l, while 2I z is equivalent to u1l. In the language intro- duced above, I z and 2I z are pseudo-pure states, corre- sponding to u0l and u1l, respectively. This approach cannot, however, be extended to larger spin systems without modifications. Next consider superpositions, such as u0l 1u1l = 2 p ; with its corresponding density matrix 1 2 1 2 1 2 1 2 ! 1 2 E 1 I x : 12 As before multiples of the unit matrix can be ignored, and so u0l 1 u1l = 2 p is equivalent to I x . Simi- larly u0l 1 iu1l is equivalent to I y , while u0l 2 u1l is equivalent to 2I x . Just as single qubit eigenstates are closely related to one spin magnetisations, their super- positions are closely related to one spin coherences. 6.2. Two qubit states While there is a simple relationship between qubit states and NMR states for a single qubit (a one spin system), this relationship is more complicated in systems with two or more qubits [48]. Typically quan- tum algorithms start with all qubits in state u0l, which for a two-qubit computer is the state u00l. The corre- sponding density matrix u00lk00u 1000 0000 0000 0000 0 B B B B B B @ 1 C C C C C C A 13 is not the same as the thermal equilibrium density matrix I z 1 S z 100 0 000 0 000 0 00021 0 B B B B B B @ 1 C C C C C C A : 14 The ideal density matrix (Eq. (13)) can, however, be decomposed as the sum of four product operators: u00lk00u 1 2 1 2 E 1 I z 1 S z 1 2I z S z ; 15 and this sum (ignoring multiples of the unit matrix as J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 337 usual) can be assembled using conventional NMR techniques, as described below. Superpositions can be treated in much the same way, but they are not directly related to NMR coher- ences in any very simple way. For example consider the state u00l 1 u01l = 2 p ; in which the first spin is in state u0l, while the second spin is in a superposition of states. The corresponding density matrix can be decomposed directly 1 2 1 2 00 1 2 1 2 00 0000 0000 0 B B B B B B @ 1 C C C C C C A 1 2 1 2 E 1 I z 1 S x 1 2I z S x ; 16 but there is a more subtle approach. Note that u00l 1 u01l = 2 p can be written as a product of single qubit states u00l 1 u01l 2 p u0l u0l 1 u1l 2 p ; 17 and so the corresponding density matrix can also be decomposed as a direct product of Eqs. (10) and (12): 10 00 ! ^ 1 2 1 2 1 2 1 2 ! 1 2 E 1 I z ￡ 1 2 E 1 S x 1 2 1 2 E 1 I z 1 S x 1 2I z S x : (18) Unlike the single qubit case, a simple superposition does not correspond directly to an NMR coherence, but instead to a complex mixture of coherences and populations. It is, however, rarely necessary to worry about this, as such states can be easily obtained from states like Eq. (13). Finally consider superpositions of the form u00l 1 u11l = 2 p ; which cannot be broken down into a product of one qubit states (such states are said to be entangled). As they cannot be factored it is necessary to decompose the corresponding density matrices directly. In this case 1 2 00 1 2 0000 0000 1 2 00 1 2 0 B B B B B B @ 1 C C C C C C A 1 2 1 2 E 1 2I z S z 1 2I x S x 2 2I y S y ; 19 which is a mixture of longitudinal two-spin order and DQ x double quantum coherence. 7. NMR logic gates After the rather abstract discussions above, we now turn to the details of methods by which quantum logic gates can be (and have been) implemented within NMR. 7.1. One qubit gates Many one qubit logic gates can be implemented directly. For example, a simple not gate, which inter- converts u0l and u1l; can be implemented as a 1808 x rotation [48]. Rotations about axes in the xy-plane can be achieved using RF pulses, while rotations about the z-axis can be accomplished either by using periods of free precession under the Zeeman Hamiltonian, or by composite z-pulses [49]. This does not, however, cover the full range of gates which may be desired, as some of these correspond to rotations about tilted axes. An obvious (and important) example is the Hada- mard gate. While this superficially resembles a 908 pulse, this resemblance is misleading, as the Hada- mard gate is its own inverse. Clearly the Hadamard must correspond to a 1808 rotation, and a little thought reveals that this rotation occurs around an axis tilted at 458 within the xz-plane. This could be achieved directly by using off-resonance excitation, but this has a number of practical difficulties. Alternatively it can be implemented using a composite pulse sequence, such as 458 y 2 1808 x 2 458 2y ; as 1808 x 2 458 ^y can be replaced by 458 7y 2 1808 x this three pulse sequence may be simplified to the two pulse sequence 908 y 2 1808 x or 1808 x 2 908 2y : J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360338 In fact, when implementing quantum algorithms on NMR quantum computers it is rarely necessary or desirable to use a Hadamard gate, as it can generally be replaced by the NMR pseudo-Hada- mard gate, a 908 y pulse [48]. As this gate is not self-inverse it is usually necessary to replace pairs of Hadamard gates by one pseudo-Hadamard and one inverse pseudo Hadamard 908 2y gate. This is a simple example of a general rule in experimen- tal implementations of quantum computation: rather than directly implementing the gates commonly used in theoretical descriptions, it is better to use simpler gates which are broadly func- tionally equivalent to them. 7.2. Controlled-not gates This approach is also applicable to the implementa- tion of controlled two-qubit gates. While it is perfectly possible to implement a controlled-not gate, this is not necessarily the most sensible approach. The controlled-not gate can itself be assembled from simpler basic gates, and it may be more sensible to use these basic gates directly. A natural way to implement a controlled-not gate is to use a three gate circuit, as shown in Fig. 8(a). The two boxes marked H are one qubit Hadamard gates, and the central gate (two circles connected by a control line) is a two qubit controlled p phase-shift gate. This gate performs the transformation u1lu1l! p 2 u1lu1l 20 while leaving all other states unchanged, and so is described by the matrix p 100 0 010 0 001 0 00021 0 B B B B B B @ 1 C C C C C C A 21 Unlike the controlled-not gate this phase shift gate is symmetric; it is not meaningful to ask which qubit the phase shift was applied to. Note that the other controlled-not gate, in which the roles of control and target qubit are reversed, can be constructed by simply moving the two Hadamard gates to the upper line. When implementing this circuit on an NMR quantum computer it is preferable to avoid using Hadamard gates, as these are difficult to implement. Instead these two gates are replaced by an inverse pseudo-Hadamard (a 90 2y pulse) and a pseudo-Hadamard gate (a 90 y pulse) respectively, as shown in Fig. 8(b). To see how to implement the controlled phase shift gate it is best to break down the propagator, Eq. (21), using the product operator basis set. As this propaga- tor is diagonal, it must arise from evolution under the diagonal operators I z , S z ,2I z S z and (for completeness) 1 2 E: It can be decomposed in two ways, p exp 2i ￡ p=2 1 2 E 2 I z 2 S z 1 2I z S z ; 22 or p exp 2i ￡ p=2 2 1 2 E 1 I z 1 S z 2 2I z S z : 23 The choice between these two decompositions is simply a matter of experimental convenience. The use of 1 2 E in these equations might appear to give rise to difficulties, as this is not normally considered as a product operator which can arise in NMR Hamiltonians. In fact it is of no significance at all, as the effect of the 1 2 E term is simply to impose a global phase shift. Such global phase shifts have no physical meaning, and cannot be detected; note that these global phase shifts have no effect on density matrix (or product operator) descriptions of the spin system. Physically this corre- sponds to the fact that there is no absolute zero against which energies may be measured. Implementing these propagators (Eqs. (22) and (23)) is fairly straightforward. The pure spin–spin coupling term (2I z S z ) can be generated using conventional spin- echo techniques, while the two Zeeman Hamiltonians J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 339 Fig. 8. (a) A circuit for implementing a controlled-not gate; the two outer gates are one qubit Hadamard gates, while the central gate is a controlled p-phase-shift gate (see text for details). (b) A circuit for implementing a controlled-not gate on an NMR quantum compu- ter; the one qubit Hadamard gates are replaced by pseudo-Hada- mard (h) and inverse pseudo-Hadamard (h 21 ) gates. (I z and S z ) can be achieved by appropriately timed periods of free precession, by the use of composite z-pulses, or most simply by just rotating the RF refer- ence frame. As the three terms all commute, they need not be applied simultaneously, but can be applied in any order. When the individual elements making up the propagator are combined, it is frequently possible to combine or cancel individual pulses, thus simplify- ing the whole sequence. This results in a wide variety of possible pulse sequences, and the choice among them is largely a matter of taste. For example, one possible sequence for implementing p is 1 4J 2 180 x 2 1 4J 2 90 x 2 90 2y 2 90 x 24 where all pulses are applied to both spins. While the possible pulse sequences differ in detail they have one feature in common: an evolution time of 1 2 J (occasionally 3/2J) during which the spins evolve under the spin–spin coupling, so that the anti- phase condition is achieved. This is, of course, the central feature of coherence transfer sequences such as INEPT, indicating the close relationship between controlled two qubit gates and coherence transfer. 7.3. Other two qubit gates While the controlled-not gate is important it is not the only two-qubit gate worth considering: while it is possible to construct any desired gate using only controlled-not gates and one-qubit gates, it is usually more efficient to use a wider repertoire of basic gates. One simple and important example is the controlled square-root of not gate, which plays a central role in traditional constructions of the three-qubit Toffoli gate [31]; this is one member of a more general family of nth roots of not. Such gates can be built in much the same way as controlled-not gates, except that the controlled p phase-shift gate must be replaced by the more general transformation u1lu1l! f e if u1lu1l 25 with f p=n: Clearly f can be constructed in much the same way as p, Eq. (23). 7.4. Gates in larger spin systems The approaches described above can be easily imple- mented in two spin systems, allowing quantum compu- ters with two qubits to be easily constructed. With larger spin systems, however, the process can become much more complicated [38]. It is not possible simply to use pulse sequences designed for two spin systems, as it is necessary to consider the evolution of all the additional spins in the system. In particular it may be necessary to refocus the evolution of these spins under their chemical shift and J-coupling interactions. The simplest method is to nest spin echoes within one another, so that all the undesirable interactions are removed, but this na?¨ve approach requires an exponentially large number of refocusing pulses (that is, the complexity of the pulse sequence doubles with every additional spin). This problem can be overcome by using efficient refocusing sequences [50,51], which allow refocusing to be achieved with quadratic overhead. It is, of course, rare to find a large spin system where all the couplings have significant size; in most cases long range couplings will be small enough to be neglected. This greatly simplifies the problem, both by reducing the number of couplings which have to be refocused, and by simplifying the echo sequences required [50,52]. It might seem that it would be difficult to implement some logic gates in such a partially coupled spin system, as the necessary spin–spin couplings are missing. In fact this is not a problem, as long as every pair of spins is connected by some chain of couplings: quantum swap gates [53,54] can be used to move quantum information along this chain. 7.5. Multi-qubit logic gates Multi-qubit logic gates are gates, such as the Toffoli gate, which perform controlled operations involving more than two qubits. Such gates can of course be imple- mented by constructing appropriate networks of one qubit and two-qubit gates [31], but as the NMR Hamil- tonian can contain terms connecting multiple pairs of spins it should be possible to build some such gates directly, with a significant saving in pulse sequence complexity. This is indeed the case, and several inter- esting results have been obtained [55,56]. 7.6. Single transition selective pulses An alternative approach for building controlled two qubit gates is to use ultra-soft selective pulses [45], with excitation profiles so narrow that they pick out, J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360340 for example, a single transition from within a doublet. This corresponds to only exciting the nucleus of inter- est when the neighbouring nucleus is in a certain state [57]; if the excitation corresponds to a 1808 pulse then this provides a simple way of constructing a controlled-not gate [58]. The relationship between this approach and the (more common) multiple pulse sequence approach is analogous to that between the old fashioned selective population transfer experi- ment [59] and its more modern counterpart, INEPT [60]. One advantage of this approach [58,61] is that it is relatively easy to extend it to multi-qubit gates such as the Toffoli gate. This can be achieved by using a selective pulse which affects one of the four transi- tions of a spin coupled to two neighbours. A corre- sponding disadvantage is that in this case constructing a simple controlled-not gate requires either a selec- tive pulse which excites two of the four transitions in such a system or the application of two single transi- tion selective pulses in sequence. The traditional Toffoli gate corresponds to invert- ing a qubit when two other qubits are in the state u1l, but there is an entire family of related gates which effect an inversion for some given pattern of states. Each such gate corresponds to exciting a different transition in the multiplet, and so the entire family of gates can be achieved directly. In practice, however, the central regions of a multiplet can become quite crowded, with many lines nearly over- lapping, and it will be difficult to select a single tran- sition. By contrast the two transitions at the extreme ends of the multiplet will always be relatively well separated from their nearest neighbours, and it is best to concentrate on these two frequencies. Other gates can then be constructed by surrounding these basic gates with not gates applied to the neighbouring spins, thus permuting the identities of the lines in the multiplet. 7.7. Geometric phase-shift gates A third approach for implementing NMR quantum computation, based on the use of geometric phase- shift gates, has recently been described [62,63]. Like the conventional approach it relies on controlled phase-shift gates, but the phase shifts are generated using geometric phases [64], such as Berry’s phase [65], rather than the more conventional dynamic phases. Berry phases have been demonstrated in a wide variety of systems [64], including NMR [66,67] and the closely related technique of NQR [68–70], and can be used to implement controlled phase shift gates in NMR systems [62,63]. This approach has few advantages for NMR quantum computation, but may prove useful in other systems [63]. 8. Initialisation and NMR As it is impractical to cool down NMR spin systems to their ground state [38,46,47], initialisation of an NMR quantum computer in practice means assem- bling an appropriate pseudo-pure state. This approach is useful only if some practical procedure for assem- bling such states can be devised. For the simplest possible system (a single nucleus) the process is trivial, as the thermal equilibrium density matrix has the desired form, but with larger systems the situation is more complicated. The essen- tial feature of a pseudo-pure state is that it has a diag- onal density matrix in which the populations of all the spin states (the elements along the diagonal) are the same, with the exception of one state (normally u0l u000…0l which has a larger population. By contrast, at thermal equilibrium the spin state populations are distributed in accordance with the Boltzmann equa- tion, and so exhibit a more complex variation. For a homonuclear two spin system the equilibrium density matrix (neglecting multiples of the identity matrix and an initial scaling factor) is I z 1 S z , while the desired pseudo-pure state is proportional to I z 1 S z 1 2I z S z (Eq. (15)). The original approach for assembling pseudo-pure states, developed by Cory et al. [8,9], uses conven- tional NMR techniques. Assembling such a mixture using pulse sequences and field gradients is a fairly straightforward, if somewhat unusual, NMR problem. This process is commonly called spatial averaging, presumably a reference to the use of field gradients. A second early approach, suggested by Gershenfeld and Chuang [10], is to use a subset of the energy levels in a more complex spin system. For example, in a homonuclear three spin system it is possible to find a set of four energy levels which exhibit the pattern of J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 341 populations corresponding to the pseudo-pure state of a two spin system. This approach, often called logical labelling, is elegant in principle but complex to apply in practice, and has only rarely been experimentally demonstrated. More recently a variety of different approaches have been used, although these all combine elements of the two basic approaches above. The most popular technique, usually called temporal averaging [71], works by performing many different experiments, each with a different initial state. For example, in a two qubit system, one might perform experiments starting from I z , S z , and 2I z S z . If the spectra from these three experiments are then added together, the result is equivalent to a single experiment starting from a mixture of these states. Clearly temporal aver- aging and spatial averaging are related in much the same way as coherence selection methods based on phase cycling and gradients. Finally, a new approach combines these methods in a cunning way, using the analogy between multiple quantum coherence and so- called “cat” states to generate pseudo-pure states in a fairly efficient manner [72]. 8.1. Spatial averaging The direct “spatial averaging” technique may be exemplified by the original sequence of Cory et al. [8,9] for constructing a pseudo-pure state in a two spin system: I z 1 S z ! 608S x I z 1 1 2 S z 2 3 p 2 S y ! crush I z 1 1 2 S z ! 458I x 1 2 p I z 2 1 2 p I y 1 1 2 S z ! couple 1 2 p I z 1 1 2 p 2I x S z 1 1 2 S z ! 458I 2 y 1 2 I z 2 1 2 I x 1 1 2 2I x S z 1 1 2 S z 1 1 2 2I z S z ! crush 1 2 I z 1 1 2 S z 1 1 2 2I z S z 26 where the sequence is described in product operator notation, “crush” indicates the application of a crush field gradient pulse, and “couple” indicates evolution under the scalar coupling for a time 1 2 J. Note that the two crush pulses must be applied along different axes, or with different strengths, to prevent undesired terms from being refocused. Several alternative sequences for creating two spin pseudo-pure states have been developed; for example [73] I z 1 S z ! 458 I x 1 S x ! couple ! 308 I 2 y 1 S 2 y ! crush 3 8 r I z 1 S z 1 2I z S z (27) where zero quantum terms (which in a homonuclear spin system will survive the crush pulse) have been neglected. This scheme works well in heteronuclear spin systems, but in homonuclear systems it is neces- sary to use a more complex approach to deal with the zero quantum terms. These sequences can be generalised to larger spin systems, but this process is quite complex. For this reason most work on larger spin systems has used temporal averaging techniques. Recently, however, Knill et al. [72] have developed a general scheme based on cat states, which allows pulse sequences for any spin system to be developed. This approach is described below. 8.2. Logical labelling Logical labelling [10] is most easily understood by examining the thermal equilibrium density matrix for a homonuclear three spin system: I z 1 S z 1 R z 1 2 {3;1;1;21;1;21;21;23}; 28 where the braces indicate a diagonal matrix defined by listing its diagonal elements. While this matrix does not have the right form for a three spin pseudo-pure state it is possible to select out four levels (corre- sponding to the states u000l, u011l, u101l and u110l) which have the same population pattern as I z 1 S z 1 2I z S z 1 2 {3;21;21;21}; 29 and so this subset of levels can be used as a two spin pseudo-pure state. It would be possible to use these states directly, but this would greatly complicate subsequent logic operations as there is no simple correspondence J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360342 between these four states of the three spin system and the four basic states of a two spin system. Instead it is better to permute the populations of the various states, performing u001l$u101l and u010l$u110l; these permutations can be achieved using controlled-not gates. At the end of this process the populations are given by 1 2 {3;21;21;21;1;1;1;23}; 30 so that the states u000l, u001l, u010l and u011l are in a pseudo-pure state. Note that these four states all have the first spin in state u0l, and so the first spin acts as an ancilla spin, labelling the “correct” subspace. Similar, but more complex, procedures can be used with larger spin systems [10]. The overhead required is fairly small; that is the number of pseudo-pure spins which can be encoded in a spin system is only slightly smaller than the size of the system. However, while these results are elegant the complexity of implement- ing logical labelling means that experimental demon- strations have so far been confined to three spin systems [61,74]. 8.3. Temporal averaging As discussed previously, temporal averaging [71] bears much the same relationship to spatial averaging as phase cycling does to the use of gradients to select coherence transfer pathways. The name can, however, be used to cover a variety of different approaches. As described above (Eq. (15)), a pseudo-pure state of a two spin system can be assembled as a mixture of three terms: I z , S z and 2I z S z . The simplest approach to temporal averaging is just to perform a computation starting from each of these states, and add the results together at the end. This is easily generalised to larger spin systems: for a system of n spins it is necessary to perform 2 n 2 1 separate experiments. In some simple experiments it is possible to show that only some of these starting states will give an observable signal [75], and so it is unnecessary to perform experiments starting in other states. This permits substantial experimental simplifications, but it is not a general technique. A better approach is to use the original scheme of Knill et al. [71]. The thermal equilibrium density matrix for a two spin system I z 1 S z {1;0;0;21} 31 (where the braces have the same meaning as before) can be easily converted into two other states, I z 1 2I z S z {1;0;21;0} 32 and S z 1 2I z S z {1;21;0;0}: 33 These three states are related by simple permutations of the populations of the levels, which can be achieved using controlled-not gates. Adding together the three starting states gives 2 I z 1 S z 1 2I z S z {3;21;21;21}; 34 which is a pseudo-pure state. Adding together the spectra from computations started in these three states therefore gives the spectrum which would be produced from a pseudo-pure state. Once again this process is easily generalised to larger spin systems. The most obvious approach is to average over the 2 n 2 1 cyclic permutations of the populations in an n spin system. This exhaustive averaging scheme is just as inefficient as the na?¨ve approach outlined above, but Knill et al. [71] have shown that similar results can be achieved by aver- aging over much smaller numbers of states. 8.4. The use of “cat” states The schemes described above are perfectly practi- cal for small spin systems but are harder to use with larger systems. Recently Knill et al. [72] have described a simple approach which works for spin systems of any size and which can be used with either the gradient (spatial averaging) or phase cycling (temporal averaging) approaches. Their method is based on the properties of “cat” states, named by analogy with Schro¨dinger’s Cat. An n qubit cat state is a superposition state of the form f ^ n u00…0l ^ u11…1l = 2 p ; 35 so that either all the n qubits are in state u0l, or all the qubits are in state u1l. (In fact the relative phase of the two states contributing to the superposition can take any value between 0 and 2p, but it is convenient to restrict ourselves to the two values 0 and p, giving rise to the factor of ^1). States of this form are said to be entangled, and play a central role in quantum information processing and experimental tests of quantum mechanics. The role of entanglement in J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 343 NMR quantum computers will be explored in more detail below, but for the moment it is suffi- cient to note that cat states are closely related to (but not simply equivalent to) multiple quantum coherence [48]. As discussed above (Eq. (19)) the two qubit cat state f 1 2 u00l 1 u11l = 2 p (commonly called a Bell state [76]) is a mixture of DQ x double quantum coherence and longitudinal two-spin order. Similarly the three qubit cat state f 1 3 (usually called a GHZ state [76]) is a mixture of 3Q x triple quantum coher- ence and the three possible states of longitudinal two- spin order, and a general n qubit cat state will correspond to a mixture of n quantum coherence and ordered population states. Thus an n quantum filtration sequence is almost (though not quite) equivalent to selecting n qubit cat states. Cat states are easily prepared from pure states, using controlled-not gates. One possible network for a three qubit system is shown in Fig. 9; networks for larger systems can be derived by analogy. Simi- larly by reversing this network cat states can be converted back into pure states. Thus, if it is possible to prepare an n qubit cat state, it should be possible to obtain a corresponding pure state. This suggests a simple scheme for preparing pseudo-pure states. If the network shown in Fig. 9 is applied to a three spin system in its thermal equili- brium state, the resulting mixture will include a component of triple quantum coherence, and thus of the desired cat state. This component can be selected, either by phase cycling or by using gradient methods. Finally the network can be reversed to convert the cat state back into a pseudo-pure state. Unfortunately this does not quite have the desired effect, as triple quantum coherence is not quite equivalent to the desired cat state; in fact 3Q x corre- sponds to uf 1 3 lkf 1 3 u 2 uf 2 3 lkf 2 3 u; and so both cat states will be retained by the triple quantum filter. The effect of reversing the network is then to convert this to the pseudo-pure state corresponding to u000lk000u 2 u100lk100u I z ^ u00lk00u: 36 This is a pseudo-pure state of the last two spins, and in general multiple quantum selection of cat states provides a convenient way of generating an n 2 1 qubit pseudo-pure state in an n spin system. Further- more, for some purposes states of the form given by Eq. (36) can be used as if they were n qubit pseudo- pure states [72]. 9. Readout As described above there are two main methods for determining the final state of an NMR quantum computer: by examining the spectrum of the spins corresponding to the qubits of interest, and by exam- ining the spectra of other neighbouring spins. These methods are simplest to describe when the quantum computer ends its computation with all the answer qubits in the eigenstates u0l and u1l, rather than in superposition states or entangled states, as in this case a small number of measurements will provide all the information required [11]. A more thorough approach is to completely characterise the final state of the spin system by so called quantum state tomo- graphy [12]; while the results can be interesting in small spin systems the effort required to perform tomography increases rapidly with the size of the spin system, and this approach is probably impractical for systems of more than three spins. 9.1. Simple readout The simplest situation to consider is a one qubit NMR quantum computer which ends a calculation in the pseudo-pure state corresponding to u0l or u1l. As discussed above (Eqs. (10) and (11)), these corre- spond to the NMR states I z and 2I z , respectively, and excitation with a 908 I y pulse will convert these to ^I x . Thus the two states will give rise to absorption and emission lines in the NMR spectrum; this is hardly surprising as they correspond to excess population in the low energy and high energy spin states. It is, of course, necessary to obtain a reference signal against which the phase of the signal of interest can be determined, but this is easily achieved, either by using the NMR signal from a reference compound, J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360344 Fig. 9. A network for creating the three qubit cat state f 1 3 : or by acquiring a signal from the computer in a known state, u0l or u1l. The situation is similar, but more complex, with larger spin systems. The NMR state corresponding to u00l is not just I z 1 S z ; as might na?¨vely be expected; instead it is I z 1 S z 1 2I z S z (see Eq. (15)). A general two qubit pseudo-pure eigenstate can be expressed similarly as uablkabu 1 2 21 a I z 1 21 b S z 1 21 a%b 2I z S z : 37 This can be analysed in two ways: by exciting and observing both spins, or by exciting and observing just one spin, say I. The first approach is perhaps the most natural approach in a homonuclear spin system, while the second method is more appropriate in a hetero- nuclear spin system. If both spins are excited, then the two population terms (I z and S z ) are converted to single quantum coherences, while the longitudinal two spin order is converted to unobservable double and zero quantum coherence. Thus the observable signal from a state of the form Eq. (37) is proportional to 21 a I x 1 21 b S x : 38 Clearly the desired information can be obtained from the phases (absorption or emission) of the NMR signals from the two spins. The situation is slightly more complicated if only one spin is observed: application of a 908 I y pulse to the state Eq. (37) gives 21 a I x 1 21 b S z 1 21 a%b 2I x S z =2; 39 and the observable signal is proportional to 21 a I x 1 21 b 2I x S z : 40 Thus only one of the two lines in the I spin doublet will be observed; which of the two lines this is depends on b, the state of spin S, while the phase of the signal depends on a, the state of spin I, as before. 9.2. Tomography Many NMR quantum computation experiments have used a readout scheme called quantum state tomography, and while this scheme is impractical for use with large spin systems it merits some expla- nation. The easiest approach to readout is simply to determine the states of one or more critical qubits which contain the desired answer, while an alterna- tive, far more thorough, approach is to characterise the complete density matrix describing the final state of the system [12]. This state tomography approach requires a large number of different measurements to fully characterise all the elements of density matrix, and for large spin systems the complexity of this approach becomes prohibitive. For small systems, however, it provides detailed information not just on the result of the calculation, but also on any error terms. The density matrix describing a two spin system can itself be described using fifteen real numbers, corresponding to the amounts of the fifteen two-spin product operators in the state (neglecting the identity matrix as usual). In a heteronuclear spin system it is possible to determine the values of four of these coef- ficients (the amounts of I x , I y ,2I x S z , and 2I y S z ) just by observing the I spin free induction decay, while four more can be determined by observing spin S. The seven remaining coefficients can then be determined in a minimum of two more experiments by exciting either I or S before observation. In general the spec- trum of a single spin can provide at most 2 n real numbers, while 4 n 2 1 numbers are required to char- acterise the spin system; thus a minimum of 2 n sepa- rate experiments will be required. In practice the schemes actually used are substantially less efficient, greatly increasing the effort required for full tomogra- phy. For example, one tomographic analysis of a heteronuclear two qubit system involved nine separate experiments [77]. 10. Practicalities 10.1. Selective pulses Implementing these pulse sequences in a fully heteronuclear spin system is straightforward, but in a homonuclear spin system complications arise from the need to perform selective excitation. The simplest approach is the use of conventional selective pulses [45]. These pulses can be simple Gaussian pulses incorporating a phase ramp to allow off-resonance excitation, but it is probably better to use more subtle pulse shapes, such as members of the BURP family of J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 345 pulses [54]. The soft pulses should excite all the lines in the target multiplet in an identical fashion, while leaving other lines completely untouched. In practice this is difficult to achieve in 1 H systems, leading to the substantial errors clearly visible in many experiments. As pulse sequences implementing quantum logic gates can contain a large number of selective pulses separated by delays, it is necessary to address each spin in its own rotating frame. In homonuclear two- spin systems, however, such as those used to imple- ment two qubit NMR computers, it is possible to use a simpler approach. Suppose the centres of the two multiplets are separated by n Hz; in this case the two frames will rotate with a relative frequency n.If the rotating frames were aligned at the beginning of the pulse sequence, they will come back into align- ment at time intervals 1/n. As long as excitation and observation is performed stroboscopically it is possi- ble to treat both nuclei as inhabiting the same rotating frame. Similarly, by choosing times such that the two rotating frames are 90 or 1808 out of phase, it is possi- ble to use variations on the simple “jump and return” pulse sequence [78] to perform selective excitation. This approach [79] can prove simpler than using selective pulses directly, but it cannot easily be used in systems with more than two spins of a given nuclear species. 10.2. Composite pulses Composite pulses [45,80] play an important role in many NMR experiments, enabling the effects of experimental imperfections, such as pulse length errors and off-resonance effects, to be reduced. Such pulses could also prove useful in NMR quantum computers, acting to reduce systematic errors in quan- tum logic gates [81]. Unfortunately most conventional composite pulse sequences are not appropriate for quantum computers as they only perform well for certain initial states, while pulse sequences designed for quantum information processing must act as general rotors, that is they must perform well for any initial state. Composite pulses of this kind (sometimes called Class A composite pulses [80]) are rarely if ever needed for more conventional NMR experiments, and so have been relatively little studied. One impor- tant example is a composite 908 pulse developed by Tycko [80,82], which has recently been generalised to arbitrary rotation angles [81]. These composite pulses give excellent compensation of off-resonance effects at small offset frequencies, such as those found for 1 H nuclei, but are of no use for the much larger off- resonance frequencies typically found for 13 C. Fortunately when composite pulses are used for NMR quantum computation one great simplification can be made: it is only necessary that the pulse sequence perform well over a small number of discrete frequency ranges, corresponding to the reso- nance frequencies of the nuclei used to implement qubits; it is not necessary to design pulses which work well over a broad frequency range. In particular many NMR quantum computers use at most two spins of each nuclear species (see, for example, [75]), and it is convenient to place the RF frequency in the centre of the spectrum, so that the two spins have equal and opposite resonance offsets [79]. Thus it is sufficient to tailor the composite pulse sequence to work well at these two frequencies, while the performance at all other frequencies can be completely ignored [83]. 10.3. Abstract reference frames One technique which has proved extremely useful in the implementation of NMR quantum computers with more than two qubits is the use of abstract refer- ence frames [72]. As it is necessary to address each spin in its own rotating frame of reference, it is possi- ble to simply rotate this frame to absorb the effects of z rotations, whether these arise from attempts to imple- ment quantum gates (see Eqs. (22) and (23)), or the failure to fully refocus chemical shifts. For example, 908 ^z rotations occur in the imple- mentations of many interesting gates. If need be these can be achieved either by periods of free preces- sion, or by composite z-pulses. A simpler approach, however, is to achieve the same effect by rotating the RF reference frame, so that subsequent pulses are applied with appropriate phase shifts. Thus, for exam- ple, the pulse sequence 90 z 90 x can be replaced by 90 2y 90 z : the phase of the RF pulse has been shifted, and the z-pulse has been delayed. Ideally it is possible to use this method to delay the z rotation to the very end of the pulse sequence, where it can be replaced by a rotation of the RF detection axis, or in many cases ignored altogether. J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360346 11. Simple algorithms Now that we have seen all the elements necessary to implement quantum logic operations within NMR it is useful to see how they can be assembled to build small NMR quantum computers. Only two algorithms will be discussed in detail, both of which can be implemented using two qubit computers, that is two spin systems. Brief reference will, however, be made to more complex systems. Computers as small as these bear little immediate resemblance to the computers in widespread use today: with only two qubits there is simply no avail- able memory in which to store extraneous data or programs! Instead the program is built into the design of the NMR pulse sequence used to implement the computation, and the two qubits are used to store the input data and the result of the computation, as well as forming the “CPU” of the system. 11.1. Functions and phases Before discussing the algorithms themselves, it is useful to describe a trick widely used in quantum computation for converting the results of a function evaluation into a phase shift. This phase trick plays a central role in conventional implementations of many algorithms, but with NMR quantum computers it is often more appropriate to redesign the computer to implement the desired phase shifts directly. These simple demonstration algorithms are based on the analysis of one-bit binary functions, that is functions which take in one or more bits as input and return a single bit (that is, 0 or 1) as output. These functions can be evaluated on reversible computers using f-controlled-not gates, as shown in Fig. 6, with the result returned as the value of an additional output bit, which begins the computation initialised to 0. An equivalent approach can be used with quantum computers, Fig. 10, but it is also possi- ble to perform function evaluation with this “output” qubit set not to u0l but to the superposition u0l 2 u1l = 2 p : Since u0 % bl 2 u1 % bl 2 p 21 b u0l 2 u1ul 2 p 41 an f-controlled-not will perform the transformation uxl u0l 2 u1l 2 p ! f 21 f x uxl u0l 2 u1l 2 p 42 and so the result of the function is returned as a phase. Note that the starting state of the ancilla qubit can be easily prepared from the state u1l by the application of a Hadamard gate (Eq. (6)). This phase trick might seem pointless, indeed coun- terproductive, as it seems to return the result of the function as a global phase, and such global phases have no physical meaning. As we shall see, however, the phase trick can be combined with quantum paral- lelism in a cunning and useful way. 11.2. Deutsch’s algorithm Deutsch’s algorithm [23–25] is concerned with the analysis of binary functions from one bit to one bit, that is functions which take in one bit as input and return another bit as output. Clearly there are four such functions, as shown in Table 1. These four func- tions can be divided into two groups: the two constant functions, for which f(x) is independent of x ( f 00 and f 11 ), and the two balanced functions, for which f(x)is zero for one value of x and one for the other ( f 01 and f 10 ). Equivalently, the functions can be classified according to the parity of the function, f 0 % f 1 : Given some unknown function f (chosen from among these four functions), it is possible to deter- mine which function it is by applying f to two inputs, 0 and 1, using the circuit shown in Fig. 10. This proce- dure also provides enough information to determine the parity of f, and thus whether the function is J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 347 Fig. 10. A quantum circuit for the classical analysis of a binary function f; this circuit is drawn for a quantum computer but is equivalent to that for a classical reversible computer (see Fig. 6). Table 1 The four possible binary functions mapping one bit to another; each function is conveniently labelled by the bit pattern in its truth table Xf 00 (x) f 01 (x) f 10 (x) f 11 (x) 00011 10101 constant or balanced. However knowing the parity of f corresponds to only one bit of information, and so it might be possible to answer this question using only one evaluation of the function f. This cannot be achieved with a classical computer, but with a quan- tum computer the problem can be solved using Deutsch’s algorithm. The basic idea behind Deutsch’s algorithm is to combine the phase trick with quantum parallelism. Suppose that the f-controlled-not gate is applied with the input qubit in the state u0l 1 u1l = 2 p and the ancilla qubit in the state u0l 2 u1l = 2 p ; then from Eq. (42) the result of the computation will be 21 f 0 u0l 1 21 f 1 u1l 2 p ! u0l 2 u1l 2 p 21 f 0 u0l 1 21 f 0 % f 1 u1l u0l 2 u1l 2 ! : (43) The ancilla qubit remains in u0l 2 u1l = 2 p ; while the “input” qubit now contains the state u0l ^ u1l = 2 p ; where the choice of plus or minus sign depends on f 0 % f 1 : As relative phases in super- positions can be detected (for example, by applying a Hadamard gate as shown in Eqs. (5) and (6)), this allows the parity of f to be determined with only one function evaluation. A quantum circuit for Deutsch’s algorithm is shown in Fig. 11. The Hadamard gates act to interconvert eigenstates and superpositions, allowing both the phase trick and quantum parallelism to be implemen- ted. Note that in this algorithm there is no input, and the result ends up in the first qubit, not the second qubit as occurs for traditional function evaluation. The second qubit is used simply as an ancilla to imple- ment the phase trick. As discussed previously, it is not possible to program such a simple computer; instead the choice of function f is “hard wired” into the computer by the design of the f-controlled-not gate. 11.3. NMR implementations Deutsch’s algorithm was not only the first quantum algorithm to be described: it was also the first algo- rithm to be implemented on an NMR quantum compu- ter, first using a homonuclear system (cytosine) and then a heteronuclear system ( 13 C-labelled chloro- form). These two implementations will be described below, while more modern implementations, includ- ing some extensions and simplifications, are described in the next section. The cytosine system [11] used the two 1 H nuclei remaining on a cytosine molecule when dissolved in D 2 O (Fig. 7). The two 1 H multiplets are separated by 763 Hz (at a 1 H frequency of 500 MHz), with a J- coupling of 7.2 Hz. Selective excitation was achieved using Gaussian shaped soft pulses incorporating a phase ramp, and the lengths of the soft pulses were chosen as multiples of the inverse of the frequency separation of the two resonances, so that the unexcited spin experienced no net rotation during a selective pulse. Both classical function analysis and Deutsch’s algorithm were implemented, using the modified J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360348 Fig. 11. A quantum circuit implementing Deutsch’s algorithm to determine the parity of a binary function f. Fig. 12. Modified quantum circuit for the classical analysis of f(0) on an NMR quantum computer; U f is a propagator corresponding to the f-controlled-not gate in the conventional circuit (Fig. 10). Function evaluation is followed by 908 y pulses to excite the NMR spectrum. Clearly f(1) can be obtained in a very similar fashion. Fig. 13. Modified quantum circuit for the implementation of the Deutsch algorithm on an NMR quantum computer. Hadamard gates have been replaced by pseudo-Hadmard and inverse pseudo- Hadamard gates, that is 908 ^y pulses. The final 908 y excitation pulses cancel out the 908 2y pulses, and thus all four pulses can be omitted. quantum circuits shown in Figs. 12 and 13. In these figures the f-controlled-not gates have been written as general two qubit propagators, U f , Hadamard gates have been replaced by 908 ^y pulses, and final 908 y pulses have been added at the end of each sequence to convert eigenstates to observable magnetisation; for simplicity pulses which simply act to cancel one another are omitted. The initial pseudo-pure states were prepared using field gradient techniques (spatial averaging), and the final results were determined by examining the phase (^x) of the NMR signals from the two spins. The heart of these computations is contained in the implementation of the propagators U f . Each propaga- tor corresponds to flipping the state of the second spin as follows: U 00 , never flip the second spin; U 01 , flip the second spin when the first spin is in state u1l; U 10 , flip the second spin when the first spin is in state u0l; U 11 , always flip the second spin. The first and last cases are particularly simple, as U 00 corresponds to doing noth- ing, while U 11 is just a selective 1808 x pulse (a not gate) on the second spin. The second propagator is a controlled-not gate, while the third case is a reverse controlled-not gate, so that a not gate is applied to the target when the control spin is in state u0l. These last two gates can be implemented as described above. The sequences actually used were 90S y 2 1 4J 2 180 x 2 1 4J 2 180 x 90I y 90I x 90 2y 90S ^x 44 where pulses not marked as either I or S were applied to both nuclei. The phase of the final pulse distin- guishes U 01 (for which the final pulse was S 1x ) from U 10 (for which it was S 2x ). In retrospect it is clear that these sequences are unnecessarily complicated; substantial simplifications could have been achieved by combing pulses and by absorbing phase shifts into abstract reference frames. The second implementation of Deutsch’s algorithm used the heteronuclear two spin system provided by 13 C-labelled chloroform in solution in deuterated acet- one. The initial pseudo-pure state was prepared by temporal averaging, although results were also shown for computations beginning in the thermal equilibrium state, while the results of the computation were determined both by direct observation of the 1 H spectrum, and by full quantum state tomography, which allows errors to be studied. Only the Deutsch algorithm was demonstrated, with no results shown for classical computations. The pulse sequences used to implement U 01 and U 10 were similar to those used for cytosine; slight differ- ences can be traced to the heteronuclear nature of the spin system and the consequent ability to place both spins exactly on resonance. The sequences used to implement the two balanced functions, U 00 and U 11 were more complicated than for cytosine, as periods of free precession were included so that each of the four propagators was applied over approximately the same time period (about 1/2J). This means that the effects of relaxation (dominated by the relatively short T 2 of the 13 C nucleus) were similar in all cases. 11.4. Extensions and simplifications In addition to these two early examples several more implementations of Deutsch’s algorithm, and its more general cousin the Deutsch–Jozsa algorithm [24], have been published. From among these a few particularly interesting examples will be described in more detail. The Deutsch–Jozsa algorithm is a generalisation of Deutsch’s algorithm which considers binary functions with any number of input bits. Clearly such functions need not be either constant (that is, give the same output for all input values) or balanced (output 0 for half the possible inputs and 1 for the remainder); for example a binary function with two input bits could return 0 for one of the four input values and 1 for the other three. Suppose, however, that it is guaranteed that some (otherwise unknown) function f is either constant or balanced (such theoretically convenient if apparently arbitrary guarantees are usually referred to as promises), and it is necessary to determine to which of these two categories the function belongs. To solve this problem by classical means would in the worst case require the evaluation of f for just over half its inputs (if the function uses n input bits it may be necessary to evaluate the function over 2 n21 1 1 inputs), while even in the best case it would be neces- sary to evaluate the function at least twice. By contrast the Deutsch–Jozsa algorithm can always distinguish between constant and balanced functions with a single function evaluation. The first experimental implementation of the Deutsch–Jozsa algorithm [58], which used functions J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 349 with two input bits, is also notable as the first example of the use of transition selective pulses. The three qubit system chosen was the homonuclear spin system made up by the three 1 H nuclei in 2,3-dibromopropa- noic acid. For simplicity pseudo-pure states were not prepared; instead the algorithm was simply applied to the spin system in its thermal state. Function evalua- tion for the six possible balanced functions was accomplished by the simultaneous application of single transition selective 1808 pulses to two of the four components of the low field multiplet (which exhibits the largest separations between the four components), and the result of the computation was determined by observation of NMR signal intensities in the two high field multiplets. This simple approach worked remarkably well; the deviations from ideal behaviour seen in experimental spectra were largely ascribed to the effects of strong coupling. The Deutsch–Jozsa algorithm has also been applied to larger spin systems, most notably a largely hetero- nuclear 5 spin system (containing single 1 H, 15 N and 19 F nuclei, together with two 13 C nuclei) derived from glycine [75]; in this case multiple pulse techniques were used to implement controlled gates. This system permits functions with 4 input bits to be studied, but only one constant and one (particularly simple) balanced function were actually implemented, out of a possible total of two constant and 12870 balanced functions. Similarly while an approach related to temporal averaging was used for initialisation, it was used to construct an initial state which gave the same signal as a pseudo-pure state, rather than the pseudo-pure state itself. Thus this can only be consid- ered as a partial implementation. Another important variation on the Deutsch–Jozsa algorithm is to remove the ancilla qubit which is normally used to implement the phase trick, convert- ing function values into phase shifts. This indirect approach is not necessary for NMR implementations, as it is possible to implement controlled phase-shift gates directly. Indeed it is usually simpler to do this; in particular the propagator for both constant functions is reduced to “do nothing”. This approach, sometimes called the refined Deutsch–Jozsa algorithm [84], has the advantage that one fewer qubit is required to implement a given algorithm. It does however have one minor disadvantage for demonstration algorithms, as such systems are intrinsically quantum mechanical and cannot be used to implement classical function analysis. This simplified approach has been used with a three spin system (the three 13 C nuclei in labelled alanine) to implement the Deutsch–Jozsa algorithm for func- tions with three bit inputs [85]. In this case there are 70 balanced functions, from which ten representative functions were chosen. At the other extreme this tech- nique can also be used to implement the refined Deutsch algorithm using a single qubit! In this case the algorithm is so simple as to be almost trivial: the U f propagator is a 1808 z pulse for the two balanced functions, while for the two constant functions it is as usual “do nothing”. Since the z-pulse can be absorbed into the RF reference frame, the pulse sequence can in principle be reduced to a 908 y pulse followed by observation along ^x. Such a simple experiment seems hardly worth performing, but for completeness it has been demonstrated as one member of a set of experiments using the isolated one spin and two spin 1 H systems is 5-nitro-2-furaldehyde [86]. 11.5. Grover’s quantum search Grover’s algorithm [87,88] is designed to speed up searches comparable to searching for a needle in a haystack. More mathematically it concerns the analy- sis of binary functions which map a large number of bits to a single output bit, where the task is to deter- mine an input for which the value of the function is 1. If the function has many inputs for which its value is 1 (that is, if the haystack contains a substantial number of needles), one of these inputs can be easily located by trial and error, but if there is only one suitable input among a large number of unsuitable inputs (one needle in a large haystack), locating this single input is obviously a difficult process. Suppose that the function f has inputs described by n bits, so that there are N 2 n possible inputs, and that f 1 for only one of these inputs. The only general way to locate this input is to evaluate f over some trial inputs, and look for a value f 1 (a satis- fying input). A lucky guess would permit this input to be located in one try, but this can hardly be relied on; on average a random search (the best classical algo- rithm) would require about N/2 trial evaluations, or N 2 1 evaluations in the worst case. The situation is similar if there are k inputs which satisfy the function; J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360350 in this case about N/k trials will be required. By contrast, Grover’s algorithm permits a satisfying value to be located with only O N=k p evaluations. This increase in computational efficiency is less impressive than the exponential increase seen for Shor’s quantum factoring algorithm [4], but is still quite substantial; furthermore the algorithm is quite general, with a range of potential applications. Early NMR implementations [77,89,90] concen- trated on the case n 2; so that there are four possible inputs, with only a single satisfying input. For this case the operation of the algorithm is fairly simple to explain, and more complicated cases can be under- stood by analogy. The algorithm involves two steps: evaluation of the function over all possible inputs, followed by a selection process to pick out the desired result. As an example I will assume that f 01 1 while f x 0 for all other inputs x. The algorithm begins with one quantum register (that is a group of qubits) in a uniform superposition of the four possible inputs, so that its state is u00l 1 u01l 1 u10u 1 u11l =2: 45 An attempt to read out the value of this register will return one of the four possible inputs at random. A propagator implementing the function f is then applied, so that f is evaluated over all 4 inputs; the propagator is set (either directly or indirectly by means of the phase trick) to return the value of f as a phase shift, that is uxl! U f 21 f x uxl; 46 so that at the end of the calculation the quantum regis- ter is in the state u00l 2 u01l 1 u10l 1 u11l =2: 47 The desired satisfying input has now in some sense been identified, as it bears the unique mark of a nega- tive phase; this is not, however, of any immediate use, as an attempt to analyse this state will still return one of the four contributing inputs at random. It is, there- fore, necessary to apply some propagator which converts the phase difference into an amplitude difference. This process might seem simple, but it is in fact quite tricky, as any such propagator must correspond to a logically reversible unitary operation. There is, however, a solution: inversion around the average. This slightly peculiar operation takes in a superposi- tion and reflects the amplitude of each component around the average amplitude of all the components. In the example, the individual amplitudes are ^ 1 2 ; and the average amplitude of the four components is 1=4; reflecting 1=2 around 1=4 gives 0, while reflecting 21=2 gives 1. Thus this operation acts to concentrate all the amplitude on one member of the superposition, giving a final state of just u01l. Surprisingly this appar- ently complex operation can be performed using only Hadamard gates and a controlled phase-shift gate which negates u00l while leaving all other states alone. A quantum network for implementing this algorithm is shown in Fig. 14; this network assumes that the function is evaluated using propagators which apply the necessary phase shifts directly; this can of course be achieved using an ancilla qubit if desired, but direct application of phase shifts has been the universal practice in NMR implementations of this algorithm. 11.6. NMR implementations The first implementation of Grover’s search [77] was performed using a heteronuclear NMR quantum computer based on chloroform. This used temporal averaging to prepare the initial pseudo-pure state, and quantum state tomography to characterise the final result. Quantum logic gates were implemented using multiple pulse sequences as discussed below. As this implementation used a heteronuclear spin system, both nuclei were placed on resonance in their respective rotating frames; thus it was not necessary to refocus chemical shifts, and periods of free precession correspond to evolution under the spin–spin coupling. The four desired controlled phase shift gates were J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 351 Fig. 14. A quantum circuit for the implementation of Grover’s quantum search algorithm on a two qubit computer. Boxes marked H are Hadamard gates. The first two qubit gate U f ab corresponds to evaluation of the function f ab , replacing an eigenstate uijl by 2uijl if i a and j b; while U f 00 simply replaces u00l by 2u00l. achieved (up to an irrelevant global phase) by combin- ing this with ^z rotations on the two spins; these were explicitly implemented using composite z-pulses. The Hadamard gates were implemented using the two pulse sequence 90 2y 180 x described in Section 7. Finally the elements of the pulse sequence with the exception of the initial pair of Hadamard gates were assembled together to give a single propagator, U ab , and sequential pairs of pulses were combined where ever possible to give simpler pulse sequences. Thus the final pulse sequences for U ab were 1 2J 2 90 2y 90S ^x 90I ^x 2 1 2J 2 90 2y 90 2x 48 where, as before, pulses not marked as either I or S were applied to both nuclei. The choice of ^ signs on the second and third pulses determined which of the three functions f was implemented. Results were shown only for U 11 , in which case both signs are positive, but experiments were performed for all four functions. The second NMR implementation of Grover’s quantum search [89] was based on the homonuclear 1 H spin system in cytosine. In this case spatial aver- aging was used to prepare the initial pseudo-pure state, and the result was analysed by excitation and detection of the two 1 H signals; this provides a parti- cularly simple and immediate readout scheme. Quan- tum logic gates were implemented using multiple pulse sequences, with soft pulses used to perform selective excitation and spin echoes used to refocus chemical shifts; sequential pairs of pulses were combined within the individual propagators U f ab ; but no attempt was made at global simplification of the pulse sequence. For these reasons the homonuclear implementation produced relatively poor results, although the cosmetic appearance of the spectra was greatly improved by the application of a magnetic field crush gradient between the end of the quantum circuit and the application of a final 908 pulse prior to detection. 11.7. Extensions Grover’s quantum search algorithm is not, of course, limited to two qubit implementations, but can be used to search over a space described by any number of input qubits, n, in which case there are N 2 n possible inputs. For n . 2 the behaviour of the algorithm is similar to but more complex than that described above; a single application of U ab (that is, function evaluation and inversion around the average) acts to concentrate the intensity of the superposition on the satisfying state, but does not simply produce this state. Instead it is necessary to apply these two operations repeatedly, driving the register towards the desired state. The intensity of the desired state oscil- lates with a frequency inversely proportional to N p ; and so after O N p applications of U ab the intensity will be largely on the satisfying state; measurement of the register will then return this state with high prob- ability. Further application of U ab will then drive the register away from the desired state, and so it is important to choose the correct number of repetitions. This oscillatory behaviour was in fact demonstrated for the two qubit case in the first NMR implementa- tion [77], where U ab was applied between zero and seven times. More recently Grover’s algorithm has been implemented with three qubits, searching over eight possible inputs, with up to 28 repetitions of the propagator [91]; this implementation used the 1 H– 19 F– 13 C spin system in 13 C labelled CHFBr 2 . Another variant on Grover’s algorithm occurs when there is more than one satisfying input; in this case the number of such inputs is usually called k. The algo- rithm is almost identical to the simple case when k 1; except that it is only necessary of use O N=k p repetitions to drive the quantum register into an equally weighted superposition of the k satisfying inputs. A measurement on this register will then cause the superposition to collapse into one of its constituent values, and so one of the k satisfying inputs can be returned at random. Clearly this requires either that the value of k be known beforehand, or that it be determined; fortunately k can be readily esti- mated using an extension of Grover’s search called quantum counting [79,92–94]. The basic idea behind quantum counting is that in addition to driving the quantum register towards the satisfying values application of the Grover propaga- tors also results in a phase shift which depends on the value of k/N. In a conventional implementation of Grover’s algorithm this phase shift is a global phase shift, and so cannot be detected. Quantum counting, however, uses an approach similar to Deutsch’s algo- rithm to convert this phase shift into a relative phase shift which can be measured. This algorithm requires J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360352 one additional qubit, and so when it was implemented on the cytosine system [79] it was performed using one bit functions, for which either zero, one, or two inputs satisfy the function. 12. Quantum phenomena In addition to implementing quantum computa- tions, NMR techniques have also been used to imple- ment other more general aspects of quantum information processing, including demonstrations of some quantum phenomena. A few of the more impor- tant examples are described below. 12.1. Entangled states Entangled states [76] are states of quantum mechanical systems which cannot adequately be char- acterised by describing the states of their component subsystems; instead the properties of such states are properties of the system as a whole. An important example is provided by the four Bell states: f ^ u00l ^ u11l 2 p c ^ u10l ^ u01l 2 p : 49 (The cat states introduced in Section 8 are an obvious generalisation of f ^ to systems of more than two qubits.) Such states play a central role in experimental tests of quantum theory, and also form the essential information processing resource for quantum commu- nication techniques. For this reason there is significant interest in techniques for generating entangled systems, especially multiple particle entangled systems such as cat states. The quantum network for generating cat states is well known, and the three qubit version is shown in Fig. 9. This was used early on to generate Bell states and three qubit cat states (GHZ states) [95], and more recently has been used to prepare seven qubit cat states [72]. There are, however, several reasons for questioning the true significance of these results, and they have certainly not generated as much excite- ment as similar results with smaller numbers of qubits in other quantum technologies [96]. The first reason for skepticism is the close relation- ship between cat states and multiple quantum coher- ences. As described above (Section 8) nQ x multiple quantum coherence corresponds to a mixture of uf 1 n lkf 1 n u and uf 2 n lkf 2 n u; thus the generation of high order multiple quantum coherence is nearly equiva- lent to the production of cat states. Seen in this light, seven quantum coherence is not particularly impress- ive: solid state NMR techniques have been used to generate coherence orders above one hundred [97]. A second difficulty with NMR cat states arises from the use of pseudo-pure states. As discussed in Section 13, the fact that NMR density matrices are always highly mixed, with nearly equal populations in all spin states, appears to mean that they cannot, strictly speaking, exhibit entanglement. Thus NMR cat states might be more properly described as pseudo- entangled states. Finally even if truly entangled NMR states were to be produced there are serious limitations on the use of NMR to investigate quantum mechanics. The ensem- ble nature of NMR measurements complicates the investigation of deviations from classical behaviour, while the short distances over which NMR entangle- ment can be produced (normally confined to molecu- lar dimensions) compares unfavourably with the distance achievable with entangled photons (hundreds of metres). 12.2. Quantum teleportation Quantum teleportation [98–100] is a particularly intriguing example of quantum communication; in essence it involves the transfer of an unknown quan- tum state from one quantum particle to another, with- out any attempt to characterise the state. The technique relies on the peculiar, apparently non- local, correlations inherent in entangled states, such as Bell states. Note that quantum teleportation does not permit the direct transfer of a quantum system into empty space: a suitable target particle (one half of a Bell state) must be provided at the destination to receive the quantum information. Thus it is the state of the particle which is teleported, and not the particle itself. Quantum teleportation has been implemented on a three spin NMR quantum computer [101] using two 13 C nuclei and a single 1 H nucleus in 13 C labelled trichloroethene. The process can be summarised by uc a l u0 b 0 c l 1 u1 b 1 c l ! u0 a 0 b l 1 u1 a 1 b l uc c l 50 where ucl indicates an arbitrary quantum state, and the J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 353 subscripts a, b, c simply label the three qubits. Although this implementation raises some interesting issues, arguments similar to those used above for entangled states can be applied to NMR teleportation, and once again optical implementations [100] are rather more convincing. 12.3. Error correction Any computing technology is ultimately based on some physical device, and such devices are inevitably error prone. There are two main methods by which the effects of these random errors can be reduced: stabi- lisation techniques which act to cancel out the effects of small errors, and error correction techniques which detect, characterise and finally fix the results of larger errors. Stabilisation against small errors is an inherent feature of digital information processing. In any digi- tal system information is stored as ones and zeroes, which are ultimately represented as two states of a physical system, such as high and low voltages. Small fluctuations away from the two ideal voltages (noise) do not matter, as long as it is always clear whether the voltage is high or low. In some cases this passive insensitivity to noise can be further enhanced by active stabilisation, which acts to continuously drive the system towards the nearer of the two ideal states. Because of this intrinsic stabilisa- tion digital information processing devices are effec- tively invulnerable to the effects of noise, as long as the noise signals remain below some critical thresh- old. If the noise rises above this threshold, however, stabilisation is no longer effective, and it is necessary to resort to error correction. Error correction techniques are even more impor- tant for quantum information processing, as simple stabilisation techniques are ruled out. Unlike bits qubits are not confined to two states, but can also exist in superpositions of these states, and any stabi- lisation scheme which drives a qubit back towards the two eigenstates will of course destroy these vital superpositions. For some time it was believed that the nature of superposition states would also render error correction schemes impractical, but happily this is not in fact the case. Classical error correction schemes [15] are most simply described in terms of the transmission of infor- mation along a noisy channel, which has the effect of flipping bits (that is, changing them from 0 to 1 and vice versa) at random, with an error probability e. Quantum error correction schemes are similar except that as well as correcting qubit flip errors (that is errors which take a qubit from u0l to u1l) it is also necessary to correct phase errors (which interconvert, for exam- ple, u0l 1 u1l and u0l 2 u1l). For simplicity, however, I will only describe how classical schemes work. All such schemes (including quantum schemes [102– 105]) use multiple copies of each bit (or qubit); the redundancy provided by these ancillas allows errors to be detected and corrected. The simplest classical scheme is triplet coding, in which a bit is encoded using three repetitions (so that 0 is encoded as 000, while 1 is encoded as 111) and decoded by taking a majority vote (so that 000, 001, 010 and 100 all decode as 0, while 111, 110, 101 and 011 all decode as 1). This scheme is robust against random errors in any one of the three bits. Of course if there are errors in two of the bits then the message will still be corrupted; however the chance of two errors occurring is e 2 1 2 e ; and as long as e is small this possibility can be neglected. If the level of errors is too high then triplet coding is no longer effective, but more robust schemes (involving even greater redun- dancy) can be used. Triplet coding and other error correction schemes might seem very different from stabilisation schemes, J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360354 Fig. 15. The relationship between the triplet error correction code and active stabilisation. The eight possible states of three bits can be placed on the eight corners of a cube, where the sides of the cube connect states which differ by a single bit flip and the two ideal states (000 and 111) lie at opposite corners. Decoding a triplet state by majority vote is equivalent to moving the state to the nearer of the two ideal corners. but in fact the basic ideas are quite similar as shown in Fig. 15. In effect the code divides the eight possible settings of a three bit system into two subspaces, just as voltages can be divided into high and low. Note that if a simpler doublet coding scheme (in which 0 is represented as 00 and 1 as 11) is used it is still possible to detect single bit errors, but not to correct them, as the two states which can occur after a bit flip error (01 and 10) lie equally close to the two ideal states. In communication (as opposed to data storage) schemes, however, it may be sufficient to detect errors, as the erroneous bits can then be sent again. Some simple quantum error detection and correc- tion protocols have been implemented on NMR quan- tum computers [106,107]. Full quantum error correction requires at least five qubits to encode a single state, but simpler schemes exist which use only three qubits; these simplified schemes can only correct phase errors or bit-flip errors, but not both. Phase errors occur as a result of spin–spin relaxation, while bit-flip errors correspond to spin-lattice relaxa- tion, and so in many NMR systems phase errors will dominate. Furthermore, phase errors only occur in quantum computers, as they have no classical analo- gue. For these reasons early studies on NMR error correction have concentrated on three qubit phase- correcting codes. It should be noted that these NMR experiments are demonstrations of the principle of error correction, rather than practical implementations of error correct- ing codes. In order to effectively suppress errors in a quantum computation it is necessary to apply the error correction protocol repeatedly; this in turn requires that the ancilla qubits be maintained in the correct state. This is most simply achieved by initialising them to u0l before each correction round. Unfortu- nately the NMR techniques described in Section 8 allow qubits to be initialised only once, at the start of the calculation; they cannot be repeatedly reinitia- lised. This appears to rule out current NMR imple- mentations as practical technologies for quantum computation [38]. 13. NMR and entanglement Finally I will return to the question, briefly discussed in Section 5, of whether NMR quantum computers are in fact true quantum computers at all. Much of the opposition to NMR as a quantum computing technology stems from the formidable difficulties [38] in scaling up the current small systems to computers with a reasonable number of qubits. A particularly common observation is that the use of pseudo-pure states is exponentially inefficient [46,47], in that the amount of pseudo-pure state which can be extracted from an NMR system at ther- mal equilibrium falls off exponentially with the number of spins in the system. Of course this problem can be overcome by using an exponentially large sample, but this approach would remove any increase in computational efficiency supposedly arising from quantum mechanical effects: there are a wide range of classical techniques (such as DNA computing [108]) which allow exponential gains in computing power to be obtained from exponentially large samples. This problem is not in principle unique to NMR; it will occur in any potential quantum computing tech- nology which works in the high temperature limit [38]. It can in principle be overcome by working at sufficiently low temperatures, or by using some other initialisation technique to produce a non-Boltzmann population distribution, although the technical problems involved are substantial [38]. However NMR is the only technology among those currently under investigation which falls into this category. In addition to the obvious technological issues raised by this exponential efficiency there are also some more fundamental concerns. It has long been suspected that the non-classical power of quantum computation is closely linked to the existence of entangled states during quantum computations [109]. Although this belief has never actually been proved, and some recent theoretical results have suggested that it may not be entirely correct [110], it is clear that some important algorithms such as Shor’s quantum factoring algorithm do require the generation of entangled states [111]. It can be shown that the pseudo-entangled states generated in NMR quantum computations do not actually fulfil the mathematical requirements for true entanglement [112], casting doubt on their ability to exhibit true quantum phenomena. As we shall see, however, this concern may not be entirely well founded. J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 355 13.1. Quantifying entanglement Although the concept of entanglement is relatively easy to explain, actually quantifying the amount of entanglement in any given system is a surprisingly difficult task. For a system of two qubits in a pure state the problem is relatively straightforward, and the four Bell states (f ^ and c ^ ; see Section 12) form a basis set describing the possible maximally entangled states. With larger systems the problem is much more difficult, as different definitions of entan- glement lead to quite different conclusions. Difficulties can also arise when considering mixed states, such as those observed in NMR experiments. These difficulties occur because there is no unique way to break down a given mixed state into a mixture of pure states. To see this consider the maximally mixed state, which for a two qubit system has the form 1 4 1 4 000 0 1 4 00 00 1 4 0 000 1 4 0 B B B B B B @ 1 C C C C C C A : 51 This is perhaps most easily described as an equally populated mixture of the four eigenstates, but this is by no means the only possible description: an equally weighted mixture of the four Bell states will have exactly the same form! It might be claimed that this alternative decomposition is unnatural, but there are no real grounds for such a statement, as the choice of basis set is entirely arbitrary, and this approach is sometimes referred to as the preferred ensemble fallacy. Similar difficulties arise when considering the pseudo-entangled states formed from pseudo-pure states, such as 1 2 e 1 4 1 euc 1 lkc 1 u 11e 4 00 e 2 0 12e 4 00 00 12e 4 0 e 2 00 11e 4 0 B B B B B B @ 1 C C C C C C A 52 (mixed states of this kind were first considered by Werner [113], and thus are often referred to as Werner states). It is tempting to argue that this mixed state is a mixture of the maximally mixed state together with a fraction e of an entangled state, but as discussed above there is no particular reason to choose this description. The amount of apparent entanglement in the state could be increased by decomposing the maximally mixed state as a mixture of entangled states, but it is also possible to choose decomposi- tions which reduce the apparent contribution from entanglement. While it is not possible to say how much entangle- ment is in any particular mixed state it is possible to determine the minimum contribution from entangled states which must be present in the state (in a pure entangled state this minimum fraction is, of course, one). If this minimum quantity is greater than zero then it is reasonable to say that the mixed state does contain some entanglement; if, however, the mini- mum amount is zero then it is possible to describe the mixed state using only product states (and thus without invoking entanglement), and the state is said to be separable. In particular it can be shown [114] that two qubit pseudo-entangled states are in fact separable if e , 1=3: An explicit separable decompo- sition of Eq. (52) with e 1=9 is given in Appendix A. With larger systems the problem is more compli- cated, but two important results are known [112]. Given any state ucl of an n-qubit system, a mixture made by mixing a fraction e of this state into the maximally mixed state, 1/2 n , can always be shown to be separable for sufficiently small values of e, such that e # 1 1 1 2 2n21 , 2 4 n : 53 It can also be shown that non-separable states do exist for sufficiently large values of e, such that e . 1 1 1 2 n=2 , 2 2 n=2 : 54 By comparison the values of e obtainable with NMR quantum computers working within the high tempera- ture limit [38,46,47] are given by e , n 2 n 55 which lies between the two bounds given in Eqs. (53) and (54). Using realistic parameters it can be calculated that the states used in NMR quantum J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360356 computations are always separable for systems with less than about 13 qubits and may (or may not) become entangled beyond this point. Since the systems used so far have involved no more that seven qubits, all NMR quantum computations to date have involved purely separable states. 13.2. NMR and quantum mechanics The observation that NMR quantum computers have so far only used separable states has led some authors to suggest that they are not true quantum computers at all! When assessing claims of this kind it must be remembered that quantum is being used here in its technical sense of provably non-classical. Consider, for example, a set of NMR quantum compu- ters which are identical except for having different values of e, with some of them lying above the entan- glement limit discussed previously, and the remainder lying below this limit. It seems very strange to claim that two groups of computers are fundamentally different in character, with the first group being quan- tum mechanical and the second group classical, but it is more reasonable to suggest that only the computers in the first group are capable of exhibiting convin- cingly non-classical behaviour. Even this claim, however, may be too strong. It seems highly unlikely that it is the mere presence of entanglement which leads to non-classical efficiency; rather it is the ability to interconvert a wide range of entangled and non-entangled states. Thus in order to claim that NMR quantum computing experiments are classical it is not sufficient to show that they involve only classical states; instead it is necessary to show that the processes which connect these states can themselves be described classically. To date attempts to achieve this have failed [115], and it is not clear that such a model is possible. In an unrelated approach, some authors have attempted to draw a distinction between the density matrix (which is a description of the state of an NMR system) and the state itself, although it is tricky to draw this distinction in an entirely convincing fashion. It is true, however, that the density matrix approach is only an approximate description of an NMR system, and that any conclusions based on this approximation are to some extent open to suspicion. 14. Conclusions When assessing NMR quantum computation it is important to take a balanced view, avoiding both excessive excitement at the apparently impressive results achieved so far and undue despair at the limita- tions that have been identified. NMR quantum compu- tation has been the subject of a great deal of sceptical scrutiny, probably more than any other approach. In part this is a result of the great success of NMR as a technique for quantum information processing; furthermore, the highly developed nature of NMR experiments, in comparison with many other putative quantum technologies, means that the limits of the technique are well known and understood. On the positive side, NMR is far ahead of any competing technology in the implementation of quan- tum computations and other forms of quantum infor- mation processing. Although some basic elements have been implemented using other technologies, such as the ion trap controlled-not gate [116], NMR remains the only technology capable of imple- menting a complete quantum algorithm. Progress from two qubit devices [8–12] to systems with seven qubits [72] has been extremely rapid, and there is every reason to believe that more progress will soon be made. Against this it must be pointed out that most researchers believe that the current designs for NMR quantum computers cannot be extended very much farther: while there is some disagreement as to which technical difficulty will actually stop further progress it is widely agreed that it will be difficult to progress beyond 10–20 qubits. While current demon- stration systems are undoubtedly interesting they are far too small to be used to tackle problems beyond the range of current classical computers. Similarly, although there are important applications of quantum information processing, such as quantum cryptogra- phy [117], which require only devices with small numbers of qubits, all such applications lie in the field of quantum communication where NMR meth- ods appear completely unsuitable. The discovery [112] that current NMR implemen- tations of quantum computation do not seem to involve entanglement might appear a serious blow, but its implications should not be overstated. This result does not mean that NMR quantum computers J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 357 are not true quantum computers, although it does appear to mean that they cannot be used to achieve non-classical efficiencies. However it has long been known [46,47] that the exponential inefficiency of pseudo-pure state preparation means that current implementations are unlikely to exhibit true efficiency gains. It seems likely that in the next few years it will be possible to use para-hydrogen techniques [42–44] to build two qubit NMR quantum computers above the entanglement threshold, but it will be tricky to extend this approach to larger systems. Acknowledgements I thank Mark Bowdrey, Holly Cummins, Ruth Dixon and Vlatko Vedral for helpful conversations, and Steffen Glaser for providing a preprint of his work [44]. Appendix A. An explicitly separable decomposition of a pseudo-entangled state While it can be shown that a two qubit pseudo- entangled state with e , 1=3 is in fact separable [114], the argument used to derive this result does not provide an explicit decomposition of such states into product states, but merely proves that such a decomposition exists. It is, however, fairly simple to find such a decomposition [112] for mixed states with low values of e. The process begins by constructing an overcom- plete basis for a single qubit; a basis set of this kind is sufficient to describe any state of a single qubit (a single spin), but contains more basic elements than is strictly necessary. One suitable basis is the set of six states u0lu1l u0l ^ u1l 2 p u0l ^ iu1l 2 p A1 which may be labelled as b j , j 1;2;…;6: This can then be used to construct a two qubit basis set, b jk ,by taking direct products. This basis set, comprising 36 elements, was constructed by taking products of single qubit states, and so is explicitly composed of product states only. Thus any density matrix which can be decomposed in this basis must be separable. As an example consider a pseudo-entangled state of the form given by Eq. (52) with e 1=9: r 2 9 1 1 1 9 uc 1 lkc 1 u 1 18 5001 0400 0040 1005 0 B B B B B B @ 1 C C C C C C A : A2 This can be written in the form r X jk P jk b jk A3 and the proportions P jk of each basis state b jk can be obtained from the trace of the product of r and b jk giving P 1 36 201111 021111 112011 110211 111102 111120 0 B B B B B B B B B B B B @ 1 C C C C C C C C C C C C A : A4 This calculation also makes clear the danger of an unquestioning equation of entanglement and multiple quantum coherence. The state shown in Eq. (A2) clearly contains double quantum coherence (it can be decomposed in product operator notation as 1 2 E=2 1 2I z S z =18 1 DQ x =9) and yet is not provably entangled. References [1] C.H. Bennett, D. DiVincenzo, Nature 404 (2000) 247. [2] C. Macchiavello, G.M. Palma, A. Zeilinger (Eds.), Quantum Computation and Quantum Information Theory, World Scientific, Singapore, 2000 (in press). [3] D. Bouwmeester, A. Ekert, A. Zeilinger (Eds.), The Physics of Quantum Information Springer, Berlin, 2000. [4] P.W. Shor, SIAM Rev. 41 (1999) 303. [5] R.P. Feynman, Int. J. Theor. Phys. 21 (1982) 467. [6] S. Lloyd, Science 273 (1996) 1073. [7] R.R. Ernst, G. Bodenhausen, A. Wokaun, Principles of Nuclear Magnetic Resonance in One and Two Dimensions, Oxford University Press, Oxford, 1987. [8] D.G. Cory, A.F. Fahmy, T.F. Havel, PhysComp ‘96, in: T. Toffoli, M. Biafore, J. Lea?o (Eds.), New England Complex Systems Institute, 1996, pp. 87–91. J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360358 [9] D.G. Cory, A.F. Fahmy, T.F. Havel, Proc. Natl Acad. Sci. USA 94 (1997) 1634. [10] N.A. Gershenfeld, I.L. Chuang, Science 275 (1997) 350. [11] J.A. Jones, M. Mosca, J. Chem. Phys. 109 (1998) 1648. [12] I.L. Chuang, L.M.K. Vandersypen, X. Zhou, D.W. Leung, S. Lloyd, Nature 393 (1998) 143. [13] J.A. Jones, NMR Quantum Computing, in: C. Macchiavello, G.M. Palma, A. Zeilinger (Eds.), Quantum Computation and Quantum Information Theory, World Scientific, Singapore, 2000 (in press). [14] J.A. Jones, Quantum Computing and NMR, in: D. Bouwmee- ster, A. Ekert, A. Zeilinger (Eds.), The Physics of Quantum Information, Springer, Berlin, 2000. [15] R.P. Feynman, in: A.J.G. Hey, R.W. Allen (Eds.), Feynman Lectures on Computation, Addison-Wesley, Reading, MA, 1996. [16] O.W. S?rensen, G.W. Eich, M.H. Levitt, G. Bodenhausen, R.R. Ernst, Prog. NMR Spectrosc. 16 (1983) 163. [17] M. Goldman, Quantum Description of High-Resolution NMR in Liquids, Clarendon Press, Oxford, 1988. [18] http://www.arxiv.org/quant-ph. [19] M. Schulz, Nature 399 (1999) 729. [20] D. Welsh, Codes and Cryptography, Clarendon Press, Oxford, 1988. [21] B. Schneier, Applied Cryptography, Wiley, New York, 1996. [22] D. Deutsch, Proc. R. Soc. Lond. A 400 (1985) 97. [23] D. Deutsch, in: R. Penrose, C.J. Isham (Eds.), Quantum Concepts in Space and Time, Clarendon Press, Oxford, 1986. [24] D. Deutsch, R. Jozsa, Proc. R. Soc. Lond. A 439 (1992) 553. [25] R. Cleve, A. Ekert, C. Macchiavello, M. Mosca, Proc. R. Soc. Lond. A 454 (1998) 339. [26] A. Ekert, R. Jozsa, Rev. Mod. Phys. 68 (1996) 733. [27] C.H. Bennett, IBM J. Res. Dev. 17 (1973) 525. [28] E. Fredkin, T. Toffoli, Int. J. Theor. Phys. 21 (1982) 219. [29] R. Landauer, IBM J. Res. Dev. 5 (1961) 183. [30] R. Landauer, Int. J. Theor. Phys. 21 (1982) 283. [31] D.P. DiVincenzo, Proc. R. Soc. Lond. A 454 (1998) 261. [32] D. Deutsch, Proc. R. Soc. Lond. A 425 (1989) 73. [33] A. Barenco, C.H. Bennett, R. Cleve, D.P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, H. Weinfurter, Phys. Rev. A 52 (1995) 3457. [34] A. Barenco, Proc. R. Soc. Lond. A 449 (1995) 679. [35] D. Deutsch, A. Barenco, A. Ekert, Proc. Roy. Soc. Lond. A 449 (1995) 669. [36] S. Lloyd, Phys. Rev. Lett. 92 (1995) 346. [37] D.P. DiVincenzo, Fort. der Physik 48 (2000) 771. See also LANL e-print quant-ph/0002077. [38] J.A. Jones, Fort. der Physik 48 (2000) 909. See also LANL e-print quant-ph/0002085. [39] T.G. Walker, W. Happer, Rev. Mod. Phys. 69 (1997) 629. [40] G. Navon, Y.Q. Song, T. Ro?o?m, A. Appelt, R.E. Taylor, A. Pines, Science 271 (1996) 1848. [41] T. Pietra?, Colloids Surf. A 158 (1999) 51. [42] J. Natterer, J. Bargon, Prog. NMR Spectrosc. 31 (1997) 293. [43] S.B. Duckett, C.J. Sleigh, Prog. NMR Spectrosc. 34 (1999) 71. [44] P. Hu¨bbler, J. Bargon, S.J. Glaser, J. Chem. Phys. 113 (2000) 2056. [45] R. Freeman, Spin Choreography, Spektrum, Oxford, 1997. [46] W.S. Warren, Science 277 (1997) 1688. [47] N.A. Gershenfeld, I.L. Chuang, Science 277 (1997) 1689. [48] J.A. Jones, R.H. Hansen, M. Mosca, J. Magn. Reson. 135 (1998) 353. [49] R. Freeman, T.A. Frenkiel, M.H. Levitt, J. Magn. Reson. 44 (1981) 409. [50] J.A. Jones, E. Knill, J. Magn. Reson. 141 (1999) 322. [51] D.W. Leung, I.L. Chuang, F. Yamaguchi, Y. Yamamoto, Phys. Rev. A 61 (2000) 042310. [52] N. Linden, E. Kupce, R. Freeman, Chem. Phys. Lett. 311 (1999) 321. [53] Z.L. Ma′di, R. Bru¨schweiler, R.R. Ernst, J. Chem. Phys. 109 (1998) 10 603. [54] N. Linden, H. Barjat, E. Kupce, R. Freeman, Chem. Phys. Lett. 307 (1999) 198. [55] M.D. Price, S.S. Somaroo, A.E. Dunlop, T.F. Havel, D.G. Cory, Phys. Rev. A 60 (1999) 2777. [56] M.D. Price, T.F. Havel, D.G. Cory, New. J. Phys. 2.10 (2000) 1. [57] A. Barenco, D. Deutsch, A. Ekert, R. Jozsa, Phys. Rev. Lett. 74 (1995) 4083. [58] N. Linden, H. Barjat, R. Freeman, Chem. Phys. Lett. 296 (1998) 61. [59] K.G.R. Pachler, P.L. Wessels, J. Magn. Reson. 12 (1973) 337. [60] G.A. Morris, R. Freeman, J. Am. Chem. Soc. 101 (1979) 760. [61] K. Dorai, A.A. Kumar, Phys. Rev. A 61 (2000) 042306. [62] J.A. Jones, V. Vedral, A. Ekert, G. Castagnoli, Nature 403 (2000) 869. [63] A. Ekert, M. Ericsson, P. Hayden, H. Inamori, J.A. Jones, D.L.K. Oi, V. Vedral, J. Mod. Opt. (2000) (in press). [64] A. Shapere, F. Wilczek, Geometric Phases in Physics, World Scientific, Singapore, 1989. [65] M.V. Berry, Proc. R. Soc. Lond. A 392 (1984) 45. [66] D. Suter, G. Chingas, R. Harris, A. Pines, Mol. Phys. 61 (1987) 1327. [67] M. Goldman, V. Fleury, M. Gue′ron, J. Magn. Reson. A 118 (1996) 11. [68] R. Tycko, Phys. Rev. Lett. 58 (1987) 2281. [69] S. Appelt, G. Wa¨ckerle, M. Mehring, Phys. Rev. Lett. 72 (1994) 3921. [70] J.A. Jones, A. Pines, J. Chem. Phys. 106 (1997) 3007. [71] E. Knill, I. Chuang, R. Laflamme, Phys. Rev. A 57 (1998) 3348. [72] E. Knill, R. Laflamme, R. Martinez, C.-H. Tseng, Nature 404 (2000) 368. [73] M. Pravia, E. Fortunato, Y. Weinstein, M.D. Price, G. Tekle- mariam, R.J. Nelson, Y. Sharf, S. Somaroo, C.H. Tseng, T.F. Havel, D.G. Cory, Concepts Magn. Reson. 11 (1999) 225. [74] L.M.K. Vandersypen, C.S. Yannoni, M.H. Sherwood, I.L. Chuang, Phys. Rev. Lett. 83 (1999) 3085. [75] R. Marx, A.F. Fahmy, J.M. Myers, W. Bermel, S.J. Glaser, Phys. Rev. A 62 (2000) 012310. [76] D. Bouwmeester, A. Zeilinger, The Physics of Quantum J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360 359 Information: Basic Concepts, in: D. Bouwmeester, A. Ekert, A. Zeilinger (Eds.), The Physics of Quantum Information, Springer, Berlin, 2000. [77] I.L. Chuang, N. Gershenfeld, M. Kubinec, Phys. Rev. Lett. 80 (1998) 3408. [78] P. Plateau, M. Gue′ron, J. Am. Chem. Soc. 104 (1982) 7310. [79] J.A. Jones, M. Mosca, Phys. Rev. Lett. 83 (1999) 1050. [80] M.H. Levitt, Prog. NMR Spectrosc. 18 (1986) 61. [81] H.K. Cummins, J.A. Jones, New J. Phys. 2.6 (2000) 1. [82] R. Tycko, Phys. Rev. Lett. 51 (1983) 775. [83] H.K. Cummins, J.A. Jones, J. Magn. Reson, 2001, in press. See also LANL e-print quant-ph/0008034. [84] D. Collins, K.W. Kim, W.C. Holton, Phys. Rev. A 58 (1998) R1633. [85] D. Collins, K.W. Kim, W.C. Holton, H. Sierzputowska- Gracz, E.O. Stejskal, Phys. Rev. A 62 (2000) 022304. [86] Arvind, K. Dorai, A. Kumar, LANL e-print quant-ph/ 9909067. [87] L.K. Grover, Phys. Rev. Lett. 79 (1997) 325. [88] L.K. Grover, Science 280 (1998) 228. [89] J.A. Jones, M. Mosca, R.H. Hansen, Nature 393 (1998) 344. [90] J.A. Jones, Science 280 (1998) 229. [91] L.M.K. Vandersypen, M. Steffen, M.H. Sherwood, C.S. Yannoni, G. Breyta, I.L. Chuang, Appl. Phys. Lett. 76 (2000) 646. [92] M. Boyer, G. Brassard, P. H?yer, A. Tapp, Fort. Der. Physik 46 (1998) 493. [93] G. Brassard, P. H?yer, A. Tapp, Proceedings of ICALP 1998; see also LANL e-print quant-ph/9805082. [94] M. Mosca, Proceedings of Randomized Algorithms, 1998. [95] R. Laflamme, E. Knill, W.H. Zurek, P. Catasti, S.V.S. Mariappan, Phil. Trans. R. Soc. Lond A 356 (1998) 1941. [96] D. Bouwmeester, J.-W. Pan, M. Daniell, H. Weinfurter, A. Zeilinger, Phys. Rev. Lett. 82 (1999) 1345. [97] L. Emsley, A. Pines, Lectures on Pulsed NMR, in: B. Mara- viglia (Ed.), Proceedings of the International School of Physics ‘Enrico Fermi’ (Societa` Italiana di Fisica, 1992). [98] D. Bouwmeester, H. Weinfurter, A. Zeilinger, Quantum Dense Coding and Quantum Teleportation, in: D. Bouwmee- ster, A. Ekert, A. Zeilinger (Eds.), The Physics of Quantum Information, Springer, Berlin, 2000. [99] C.H. Bennett, G. Brassard, C. Cre′peau, R. Jozsa, A. Peres, W.K. Wooters, Phys. Rev. Lett. 70 (1993) 1895. [100] D. Bouwmeester, J.-W. Pan, K. Mattle, M. Eible, H. Wein- furter, A. Zeilinger, Nature 390 (1997) 575. [101] M.A. Nielsen, E. Knill, R. Laflamme, Nature 396 (1998) 52. [102] P.W. Shor, Phys. Rev. A 52 (1995) 2493. [103] A.M. Steane, Phys. Rev. Lett. 77 (1996) 793. [104] A.M. Steane, Philos. Trans. R. Soc. Lond. A 356 (1998) 1739. [105] A.M. Steane, Nature 399 (1999) 6732. [106] D.G. Cory, M.D. Price, W. Maas, E. Knill, R. Laflamme, W.H. Zurek, T.F. Havel, S.S. Somaroo, Phys. Rev. Lett. 81 (1998) 2152. [107] D. Leung, L. Vandersypen, X.L. Zhou, M. Sherwood, C. Yannoni, M. Kubinec, I. Chuang, Phys. Rev. A 60 (1999) 1924. [108] L.M. Adleman, Science 266 (1994) 1021. [109] A. Ekert, R. Jozsa, Philos. Trans. R. Soc. Lond. A 356 (1998) 1769. [110] E. Knill, R. Laflamme, Phys. Rev. Lett. 81 (1998) 5672. [111] N. Linden, S. Popescu, LANL e-print quant-ph/9906008. [112] S.L. Braunstein, C.M. Caves, R. Jozsa, N. Linden, S. Popescu, R. Schack, Phys. Rev. Lett. 83 (1999) 1054. [113] R.F. Werner, Phys. Rev. A 40 (1989) 4276. [114] A. Peres, Phys. Rev. Lett. 77 (1996) 1412. [115] R. Schack, C.M. Caves, Phys. Rev. A 60 (1999) 4354. [116] C. Monroe, D.M. Meekhof, B.E. King, W.M. Itano, D.J. Wineland, Phys. Rev. Lett. 75 (1995) 4714. [117] A. Ekert, N. Gisin, B. Huttner, H. Inamori, H. Weinfurter, Quantum Cryptography, in: D. Bouwmeester, A. Ekert, A. Zeilinger (Eds.), The Physics of Quantum Information, Springer, Berlin, 2000. J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325–360360