清华大学：《生物核磁共振波谱学》课程教学资源（文献资料，英文版）Jones-38-325-NMR quantum computation

PROGRESS IN NUCLEAR MAGNETIC RESONANCE SPECTROSCOPY ELSEVIER Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001)325-360 www.elsevier.nl/locate/pnmrs nMR quantum computation J.A. Jones a.b,* Oxford Centre for Molecular Sciences, New Chemistry Laboratory, South Parks Road, Oxford OX1 30T, UK Centre for Quantum Computation, Clarendon Laboratory, Parks Road, Oxford OXI 3PU, UK Received 31 July 2000 Contents 1. Introduction 1. Structure and scope 2. Limits to computation 2. 1. Computational complexity 2. 2. Quantum complexity 3. Atomic computation 3. 2. Reversible computation 3.3. Reversible function evaluation 4. 1. Quantum parallelism 4. 2. Deutsch's algorithm 332 .3. Quantum gate 4.4. Universality of quantum gates 5. Building NMR quantum computers 5. 2. Logic gates 5.3. Initialisation 5.5. Some two spin systems 5.6. Scaling the system up 6. Qubits and NMR spin states 6. 1. One qubit states 337 7. NMR logic gates 7.1. One qubit gates 7. 2. Controlled-NOT gates 7.3. Other two qubit gates 340 7.4. Gates in larger spin systems *Tel+44-1865-272247;fax:+44-1865-272387 E-mail address: jones@qubit. org (J.A. Jones) ont matter 2001 Elsevier Science B.v. All rights reserved. P:S0079-6565(00)00033-9

NMR quantum computation J.A. Jonesa,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)

J.A. Jones /Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001)325-360 .5. Multi-qubit logic gates 7.6. Single transition selective pulses 7.7. Geometric phase-shift gates 341 8. Initialisation and NMR 341 8.1. Spatial averaging 8.2. Logical labelling 8.3. Temporal averaging 84. The use of“cat” states 9. Readout 344 9. 1. Simple readout 10. Practicalities 10. 1. Selective pulses 10.2. Composite pulses 46 10.3. Abstract reference frames 11. Simple algorithms 11. 1. Functions and phases 11.2. Deutsch's algorithm 11.3. NMR implementations 11.4. Extensions and simplifications 11.5. Grovers quantum search 11.6. NMR implementations 11.7. Extensions 12. Quantum phenomena 12. 1. Entangled states 12.2. Quantum teleportatic 12.3. Error correction 13. NMR and entanglement 13. 1. Quantifying entanglement 13.2. NMR and quantum mechanics Conclusions Acknowledgements Appendix A. An explicitly separable decomposition of a pseudo-entangled state References 358 1. Introduction In recent years there has been considerable interest in the use of NMR techniques [7] to implement quan- Quantum computation [1-3] offers the prospect of tum computations [8-14]. It has proved surprisingly revolutionising many areas of science by allowing us simple to build small NMR quantum computers, and to solve problems well beyond the power of our while such computers are themselves too small for current classical computers [4]. In particular a quan- any practical use, their mere existence has brought tum computer would be superb for simulating the great excitement to a field largely deprived of experi- behaviour of other complex quantum mechanical mental achievements systems [5,6]. Although the theory of quantum computation has been studied for many years, and I.1. Structure and scop many important theoretical results have been obtained, early attempts to actually build even the In this article I will describe how NMR techniqu smallest quantum computer proved extremely ay be used to build simple quantum information processing devices, such as small quantum computers

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 simpli®cations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 ®eld 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, 326 J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360

J.A. Jones/Progress in Nuclear Magnetic Resonance Spectroscopy 38(2001)325-360 and show how these techniques are related to more At current rates of progress it is estimated [19] that the conventional NMR experiments. Many tricks and ultimate limits of this approach will be reached by techniques well known from conventional NMR about 2012, and any further progress in the power of studies can be applied to NMr quantum computation, our computers will require a radically different and it is likely that some of these will be applied in approach. One possible approach is to use the power any large scale quantum computer which is eventually offered by quantum computation 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 Even if the problems described above are side- explaining what quantum computation is, and what stepped in some way, there are still strong limits to it could achieve. This in turn requires a brief discus- the problems which we can solve with current compu- sion of classical reversible computation [15]. In order ters. These limits are derived from the underlying to reduce these introductory sections to a reasonable theory of computation itself, and in particular from length many technical points have inevitably been computational complexity theory [20]. Complexity kipped over. Wherever possible I will use traditional theory considers the classification of mathematical product operator notation [16]to describe how NMr problems according to how difficult they are to deal quantum computers are implemented; it will some- with, and seeks to divide them into those which are times, however, be necessary to use more abstract relatively easy(tractable)and those which are uncom- quantum mechanical notations [17] to describe what fortably difficult(intractable). Note that complexity these computers seek to achieve ot concerned with problems which we de Before the advent of NMr quantum computation, not know how to solve, or which we know cannot be almost all research in this field was performed within solved, but only with problems for which an algorith- a small community of physicists and mathematicians. mic solution(tractable or intractable) is known. Some important results have never been published as The classical theory of computation has remained conventional papers, but simply circulate as electronic largely unchanged for decades, with a central role preprints;copies of most of these can be obtained played by the Church-Turing thesis. This asserts from the quant-ph archive on the LANL e-print server that all physically reasonable models of computation [18]. Similarly, many other papers appear as LAN are ultimately equivalent to one another, so that it is e-prints long before more formal publication. 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 2. Limits to computation or otherwise of a problem is independent of the computational device used As we will see, quantum Over the last forty years there has been astonishing computation challenges this thesis, as quantum progress in the power of computational devices using computers appear to be fundamentally more powerful silicon based integrated circuits. This progress is than their classical equivalents summarised in a set of"laws", usually ascribed to To make further progress it is necessary to use a Moore, although some were developed by other more precise measure of the complexity of an algo- people. Over this period the power of computational rithm. The usual approach is to determine the compu devices has roughly doubled every eighteen months, tational resources (most commonly defined as the or increased ten-fold every five years. Unfortunately, this extraordinary technological progress may not required to implement it. Clearly this measure will continue for much longer, as this increase in comput- depend on the exact nature of the computational ing power requires a corresponding decrease in the resources available to our computer, and so this is size of the transistors on the chip; this shrinkin not directly useful. a better approach is to consider process cannot be continued indefinitely as the tran- not a single isolated problem, but a family of closely sistors will eventually be reduced to the atomic scale related problems, and to determine how the resources

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 ®rst 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 ®eld 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 ®ve 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 inde®nitely 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 classi®cation of mathematical problems according to how dif®cult they are to deal with, and seeks to divide them into those which are relatively easy (tractable) and those which are uncom￾fortably dif®cult (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 de®ned 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

J.A. Jones/ Progress in Nuclear Magnetic Resonance 38(2001)325-360 tired scale within this family. To take a simple should give a significant increase in example, adding two n digit numbers with pencil this range Exponential functions, however, rise extre- and paper requires n separate additions, together mely rapidly with n, and so it will only be possible to with n carries, and so the time required for addition solve problems with exponential complexity for rela scales linearly with n. Similarly, multiplying two n tively small input sizes; furthermore a modest digit numbers by long multiplication requires n- increase in computer power will result in only a tiny multiplications and a similar number of additions. increase in the range of problems that can be solved Mathematically, adding two n digit numbers is said he apparent exponential complexity of factoring is to be o(n)(that is, of order n). The exact number of a matter of some importance, as it underlies many steps required will depend on exactly how elementary cryptographic schemes in use today, notably those computational steps are counted, but the total number based on the Rivest-Shamir-Adleman (RSA) of steps will always scale linearly with n. Similarly, approach to public key cryptography, such as Pretty long multiplication can always be performed in a Good Privacy(PGP)[21]. These schemes involve a number of steps which varies quadratically with n, public key, which anyone may use to encrypt a and so is o(n) message, and a private key, which is required to The complexity of a problem, rather than an algo- decrypt such messages. The relationship between rithm, may be defined as the complexity of the best these two keys is equivalent to the relationship known algorithm for solving the problem; thus addi- between the product of two large prime numbers tion is O(n). It might seem that multiplication is O(n"), and the two prime numbers themselves. The security but in fact long multiplication is not the best known of the system depends on the difficulty of determinin algorithm; a better approach is known with complex- the private key from a long public key, which itse y about O(n log n)[20]. Strictly speaking one should depends on the complexity of factoring By contrast, also distinguish between an upper bound on the the computational complexity of encrypting and number of steps known to be sufficient to solve a decrypting messages is only a polynomial function problem (indicated by O), and a lower bound on the of the size of the keys. Thus a small increase in the number of steps known to be required to solve a amount of effort required to use the cryptographic problem(indicated by (2); a problem, such as addition scheme results in an enormous increase in its security of n digit numbers, which is both O(n) and n2(n)is plexity whose complexity is at worst a polynomial function Quantum computation offers the possibility of of n, are said to be easy, while problems whose bypassing some of the limits apparently imposed by complexity is worse than a polynomial function of n complexity theory. This is because a quantum comp are said to be hard. For example, consider the problem ter could implement entirely new classes of algo- of finding the prime factors of an n digit composite rithms which would allow currently intractable number. The obvious way to do this is to simply try problems to be solved with ease dividing the composite number by every number less The first serious discussion of quantum computa than its square root; as there are approximately tion was by Feynman, who analysed the difficulty of 10=102 such trial divisors, this algorithm has simulating quantum mechanical systems using classi- complexity O(10"). Better algorithms for factoring cal computers [5]. This difficulty is well known and are known, but they all have the same property of easy to understand; it arises from the enormous free- dom available to quantum systems. For example,a For problems with polynomial complexity, espe- system of n coupled spin-1/2 nuclei inhabits a Hilbert cially those whose complexity is described by a low pace of size 2, and so must be described by a vector power of n, such as n or n, the effort required to solve with 2"components. Thus it appears that any classical a problem increases only slowly with n. Thus it should algorithm to simulate the behaviour of n spin-1n2 parti- be possible to tackle such problems for a reasonable cles must have complexity at least O(2 ); within NMR range of input sizes, and a modest increase in this corresponds to the well known computational

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 n2 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(n2 ). The complexity of a problem, rather than an algo￾rithm, may be de®ned 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(n2 ), 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 suf®cient 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 ®nding 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 ˆ 10n=2 such trial divisors, this algorithm has complexity O(10n/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 n2 , 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 signi®cant 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 dif®culty 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 ®rst serious discussion of quantum computa￾tion was by Feynman, who analysed the dif®culty of simulating quantum mechanical systems using classi￾cal computers [5]. This dif®culty 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 2n , and so must be described by a vector with 2n 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(2n ); within NMR this corresponds to the well known computational 328 J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360

J.A. Jones/Progress in Nuclear Magnetic Resonance Spectroscopy 38(2001)325-360 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] 1. A circuit to compute the exclusive-OR(XOR) function,z=x Deutsch also described a(somewhat contrived y,using AND, OR and NOT gates. Note that this circuit uses three problem [23-25] which could be solved more implicit gates, two CLONE gates, shown as small circles, where wires ciently on a quantum mechanical computer than on split into two( to copy the input) and one swap gate( where the wires any classical computer, suggesting that it might be cross over). These implicit gates are fairly easy to implement in possible to use a quantum computer to solve otherwise traditional electronic computers, but can cause designs and so cannot simply be ignored. So intractable problems onsider the wires which interconnect gates as no Since that time several quantum algorithms [26] their own right have been developed, the most notable of which is Shors quantum factoring algorithm [4]; this allows difficulty of simulating a large strongly coupled spin a composite number to be factored with a complexity system. This apparently inevitable exponential only slightly greater than O(n), thus rendering factor- complexity makes the simulation of quantum mechan- ing tractable. As well as being of great mathematical ical systems an intractable problem interest, this algorithm has obvious practical signifi espite this apparent complexity, however, cance, as it poses a threat to many current crypto- coupled spin systems evolve in the"correct"manner. graphic schemes. The discovery of Shors algorithm Thus, in some sense, such a spin system appears to triggered an enormous increase in research directed at have the capacity to solve a problem which is intact- quantum computation and related areas of quantum able by conventional classical means. Clearly using a information theory 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 3. Atomic computation another quite different system. Thus an easily control- lable system might be used to simulate the behaviour Before describing how quantum mechanical com- of another less well behaved system, while a carefully puters can be built, it is useful to consider how an chosen system might be usable as a general purpose atomic scale system, such as a group of coupled tum simulator [5, 6 nuclei, could be used to implement classical com- eynman's ideas appear to have been limited to the putations [15, 27, 28]. Discussions NAND NAND Fig. 2.(a) A circuit to compute the exclusive-OR(XOR)function, z=x XOR y, using only NAND and 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 te NoT NAND gate. By combining circuits(a)and(b) it is possible to implement XoR using only NAND gates. function may be computed in a similar fashion, and so NAND is a universal gate. Note, however, that both circuits use implicit while (a)also uses one implicit

dif®culty 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 ef®- 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(n2 ), thus rendering factor￾ing tractable. As well as being of great mathematical interest, this algorithm has obvious practical signi®- 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

J.A. Jones/Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001)325-360 This description works well with conventional computers, in which bit states are represented by voltages applied to wires, but it cannot be used with atomic computers. Atomic computers represent bit Fig. 3. The controlled-NOT gate, which plays a central role in rever- sible and quantum computation. The target bit is marked by a eD values using the quantum states of atomic systems, mbol, indicating the close relationship with binary arithmeti so a logic gate can neither create nor destroy bits; nodulo two; the control bit is marked by a dot and a vertical control thus logic gates such as AND, which have two input ne(the dot is important in drawings of larger circuits where bits and only one output bit, are immediately ruled ontrol line may have to cross lines representing other bits). out. Similarly, atomic systems evolve under a series of unitary transformations, which correspond to rever suggestions that quantum devices might have funda sible operations, while many of the operations mentally different properties. described above are clearly not reversible. In order The basic approach is very simple. Classical to build atomic computers, therefore, it is necessary computation [15] is implemented with two state to use a different approach, using only reversible logic devices, usually called bits, and these two states can operations two eigenstates of a quantum mechanical two level system. The calculation then 3. 2. Reversible computation proceeds by manipulating the states of various bits such that the final state of some group of bits(the The theory of reversible computation [15, 27, 28] output register")depends on the result of the desired has been studied extensively and, perhaps surpris- computation As will be shown later, quantum compu ingly, it is simple to perform any logic operation in tation is very similar, except that the bits are not a reversible manner. The only irreversible operation confined to their eigenstates; this effectively allows required when performing a computation [29,30]is many different calculations to be carried out in the preparation of a well defined initial state, usually parallel taken as having all bits in state 0; after this initialise tion process the computation can be performed 3. 1. Computational circuit The basic approach needed to achieve reversible Although several different theoretical models are logic can be summarised in two simple rules. First, useful for abstract descriptions of computers, one of any logical inputs to a gate must be preserved in the the most convenient approaches for describing how to outputs: this is most simply achieved by copying them build small computers is the circuit model, in which to output bits without change. Secondly, the output of bits interact through gates which implement Boolean the gate(here assumed for simplicity to comprise logic operations. One traditional set of classical gates single bit)must be combined in a reversible fashion is the one bit NoT gate together with two different two with an additional auxiliary bit, for example by addin bit gates, AND and OR. These three gates are said to the two bits together using binary arithmetic modulo form an adequate set, in that any desired logic opera tion can be performed by building an appropriate Binary arithmetic modulo two, usually indicated by circuit(see Fig. 1 for an example)using some combi- the symbol 6, has the useful properties that x e 0 nation of these three gates 0⊕x= r and x1=1r=Nor(x), while x⊕ In fact it is not necessary to use all these gates: they x=0. A simple example of a reversible logic gate an themselves all be obtained using combinations of based on this approach is the controlled-NOT gate NAND gates(Fig. 2), and so the NAND gate is universal(see Fig 3), which has two inputs, x and y and two for classical computation. It is, however, necessary to corresponding outputs xand y. The first input bit is proceed with some caution, as several other"implicit copied to its output bit, so x'=x, and is also gates are also required, such as the cLone gate, which combined with the second input bit to give y'=xe makes a copy of a bit, and the SwAP gate, which allows y. Thus a NoT gate is applied to the second bit(the two wires to cross one another target bit)if and only if the first bit(the control bit)is

suggestions that quantum devices might have 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 ®nal 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 con®ned to their eigenstates; this effectively allows many different calculations to be carried out in parallel. 3.1. Computational circuits Although several different theoretical models are useful for abstract descriptions of computers, one of the most convenient approaches for describing how to build small computers is the circuit model, in which bits interact through gates which implement Boolean logic operations. One traditional set of classical gates is the one bit not gate together with two different two bit gates, and and or. These three gates are said to form an adequate set, in that any desired logic 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 de®ned 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 x0 and y0 . The ®rst input bit is copied to its output bit, so x0 ˆ x; and is also combined with the second input bit to give y0 ˆ x % y: Thus a not gate is applied to the second bit (the target bit) if and only if the ®rst bit (the control bit) is 330 J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360 Fig. 3. The controlled-not gate, which plays a central role in 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)

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

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

J-A. Jones/ Progress in Nucleo tic Resonance Spectroscopy 38(2001)325-360 classical bit, and so is called a quantum bit, or qubit superposition described by Eq. (1)and the second for short. a qubit in a superposition state is(in some qubit is in state o). This can be easily calculated as sense)in both of the states contributing to the super- quantum mechanics is linear, and so the effect of position at the same time, so a qubit can simulta- applying a gate to a superposition is a superposition neously occupy two different logical states of the results of applying the gate to the two eigen Computational circuits are implemented within states. Hence the result is quantum computers by performing physical manip- (0)+10) lo)(0)+liL() lations so that the computer evolves under a propaga tor which implements the desired unitary transformation. Just as circuits can be built up from Thus the quantum computer has simultaneously tes these propagators can ssembled from evaluated the values of f(o)and f(1). simpler elements, and so these propagators are often When applied to more complex systems, quantum referred to as circuits, even though their physical parallelism has potentially enormous power. Consider implementation may bear little resemblance to a function for which the input is described by n bits, so conventional electrical circuits. As before, this that there are 2 possible inputs(since n bits can be abstract model allows quantum computers to be used to describe any integer between 0 and 2"-1):a described in a device-independent fashion. quantum computer using n qubits as inputs can eval- As discussed below, it is possible to construct any uate the function over all of these 2" inputs in one step quantum circuit by combining a small number of In effect a quantum computer with n input qubits simple propagators, usually called gates. These gates appears to have the computational power of 2"classi only affect one or two qubits at a time, and so it is cal computers acting in parallel. Unfortunately it is perfectly practical to describe their propagators expli- not always possible to use this quantum parallelism citly, for example as a matrix. A matrix description in any useful way. Performing parallel function clearly depends on the choice of basis set, but the evaluation over n qubits will result in a state of the usual choice is to work in the computational basi form in which the basis vectors correspond with the differ ent logical states of the computer; thus for a two qubit gate the basis set is (00), 01), 10), 11)). In many 列f() proposed physical implementations of quantum computers, such as NMR, this basis set is also the natural basis for the system, as the basis states which is a superposition of the 2 possible inputs, each eigenstates of the background Hamiltonian entangled with its own function value. If any attempt is made to measure the state of the system, then the 4.1. Quantum parallelism superposition will collapse into one of its component values, r)f(r)), where the value of r is chosen at The central feature underlying all quantum algo- random. Thus even though it seems possible to eval- rithms is the idea of quantum parallelism, which in uate the function over its 2 input values, it is only turns stems from the ability of quantum systems to be possible to obtain one of these values. found in superposition states Consider once again the It is, however, sometimes possible to obtain useful reversible circuit for function evaluation( Fig. 6). This information in a more subtle way. In some cases, the can be achieved by constructing a propagator, Uf, answer of interest does not depend on specific values, fr), but only on global properties of the function itself. This is the basis of both Deutsch's toy algorithm a)b)→园a)b⊕f(a) (2) and Shor's quantum factoring algorithm d setting b)= o). The two values of the fu 4.2. Deutsch's algorithm f(O)and f(1), can then be evaluated by setting a)=o) and a)=1)as before. Now consider the effect of Deutsch's algorithm [23-25] was the first quantum applying this circuit when the first qubit is in a algorithm to be discovered, and is one of the few

classical bit, and so is called a quantum bit, or qubit for short. A qubit in a superposition state is (in some sense) in both of the states contributing to the 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, Uf, applied to two qubits, which performs ualubl ! Uf 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 ®rst qubit is in a superposition described by Eq. (1) and the second qubit is in state u0l. This can be easily calculated as quantum mechanics is linear, and so the effect of applying a gate to a superposition is a superposition of the results of applying the gate to the two eigen￾states. Hence the result is …u0l 1 u1l†  2 p u0l ! Uf 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 2n possible inputs (since n bits can be used to describe any integer between 0 and 2n 2 1); a quantum computer using n qubits as inputs can eval￾uate the function over all of these 2n inputs in one step. In effect a quantum computer with n input qubits appears to have the computational power of 2n 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 2 Xn 2 1 iˆ0 uilu f…i†l 2n=2 ; …4† which is a superposition of the 2n possible inputs, each entangled with its own function value. If any attempt is made to measure the state of the system, then the superposition will collapse into one of its component values, urluf(r)l, where the value of r is chosen at random. Thus even though it seems possible to eval￾uate the function over its 2n input values, it is only possible to obtain one of these values. It is, however, sometimes possible to obtain useful information in a more subtle way. In some cases, the answer of interest does not depend on speci®c values, f(r), but only on global properties of the function itself. This is the basis of both Deutsch's toy algorithm and Shor's quantum factoring algorithm. 4.2. Deutsch's algorithm Deutsch's algorithm [23±25] was the ®rst quantum algorithm to be discovered, and is one of the few 332 J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360

J.A. Jones/Progress in Nuclear Magnetic Resonance Spectroscopy 38(2001)325-360 quantum algorithms simple enough to describe here which take a quantum register into a uniform super The problem can be described in terms of function position of all its possible values: evaluation, but a more concrete picture can be obtained by thinking about coins. Normal coins 100)-(00)+101)+ 10)+ 11)/2 have two different faces, conventionally called heads and tails. but fake coins can be obtained This can be easily achieved by applying a one qubit both faces Hadamard to each qubit which have the same pattern Another important property of the Hadamard Consider an unknown coin, which could be either a gate can be seen by examining the right hand normal coin or a fake coin. In order to determine sides of Eqs. (5)and(6). These differ only by which type it is, it would seem necessary to look at the presence of a minus sign, so the two super- both sides to find out whether they showed heads or tails. and then see whether these two results were the positions differ only by the phase with which the two eigenstates are combined. The ability of the same(a false coin) or different(a true coin). With a Hadamard gate to convert such phase differences quantum device, however, it would be possible to look at both sides simultaneously, and thus determine into different eigenstates plays a central role in many quantum algorithms whether the coin was normal or fake in a singl anc 4.4. Universality of quantum gates The trick lies in abandoning any attempt to deter mine the pattern shown on either side of the coin The gates we have seen so far are enough to explain instead one must simply ask whether the two faces some simple quantum algorithms; for example, are the same or different. This is a property not of Deutsch's algorithm can be described using only the individual faces of the coin, but of the whole Hadamard gates and reversible function evaluation coin, and thus may be extracted from a state of the gates. It is, however, useful to consider other more kind described by Eq (3). A more detailed explana general quantum gates; indeed as any unitary trans- tion of this approach is given in Section 11 formation can be considered as a quantum gate, we may need to consider an infinite number of gates 4.3. Ouantum gates Within classical models of computation(both reversible and irreversible) it is possible to construct Just as classical reversible computations can be any desired gate by combining copies of a small performed using circuits built up out of reversible number of simple gates. A similar situation applies gates,quantum circuits can be constructed using in quantum computation, but in this case there are uantum gates [31]. Unlike classical circuits, an infinite number of possible gates(even if we however,quantum circuits can include gates which restrict ourselves to single qubit gates, any rotation generate and analyse qubits which are in superpo around any axis constitutes a valid one qubit gate). of Clearly it cannot be possible to construct an infinite One such gate is the single qubit Hadamard gate, H, number of different gates by combining a finite which implements the transformations number of simpler gates, but it is possible to simulate (0)+|1)2 any gate to any desired accuracy [32, 33], which is (5) good enough. Perhaps surprisingly there very large number of two qubit gates which are l)2(0)-1)2 universal in this restricted sense, in that it is possi to simulate any desired gate(that is, any unitary trans- discussed below, this is closely related to a 90 formation) using only one of these universal gates pulse, but differs in some subtle ways; in particular the together with its twin, obtained by swapping the Hadamard is its own inverse roles of the two qubits. Indeed, mathematically speak The Hadamard gate is useful as it takes a qubit in an ing, almost all two qubit gates are universal [34-36] eigenstate to a uniform superposition of states. By While mathematically interesting, this result is of one can de efine multi-qubit Hadamard gates little immediate practical implication for most

quantum algorithms simple enough to describe here. The problem can be described in terms of function evaluation, but a more concrete picture can be obtained by thinking about coins. Normal coins have two different faces, conventionally called heads and tails, but fake coins can be obtained which have the same pattern on both faces. Consider an unknown coin, which could be either a normal coin or a fake coin. In order to determine which type it is, it would seem necessary to look at both sides to ®nd out whether they showed heads or tails, and then see whether these two results were the same (a false coin) or different (a true coin). With a quantum device, however, it would be possible to look at both sides simultaneously, and thus determine whether the coin was normal or fake in a single glance. The trick lies in abandoning any attempt to 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 de®ne 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 in®nite number of gates. Within classical models of computation (both reversible and irreversible) it is possible to construct any desired gate by combining copies of a small number of simple gates. A similar situation applies in quantum computation, but in this case there are an in®nite number of possible gates (even if we restrict ourselves to single qubit gates, any rotation around any axis constitutes a valid one qubit gate). Clearly it cannot be possible to construct an in®nite number of different gates by combining a ®nite number of simpler gates, but it is possible to simulate any gate to any desired accuracy [32,33], which is good enough. Perhaps surprisingly there exists a very large number of two qubit gates which are universal in this restricted sense, in that it is possible to simulate any desired gate (that is, any unitary 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

J.A. Jones/ Progress in Nuclear Magnetic Resonance Spectroscopy 38(2001)325-360 possible implementations of a quantum computer, as combined together to implement any other desired it is usually more sensible to use a larger and more gate. While many different sets of gates are possible convenient set of gates. As one qubit gates are usually a simple approach is to implement the set of all possi much simpler to perform than gates involving two or ble one qubit gates, together with one or more non- more qubits, it is often reasonable to assume that any trivial two qubit gates [33] one qubit gate(or, at least a reasonable approximation One qubit gates correspond to rotations of a sp to it) is available. The combination of this set of one within its own one-spin Hilbert space, which can be qubit gates with any single non-trivial two qubit gate, readily achieved using RF fields. Note that it is neces such as the controlled-NOT gate forms an adequate set sary to apply these rotations selectively to individual [33], from which any other gate may be built with qubits. In most other suggested implementations of relative ease quantum computation [2,3] this is easily achieved using some type of spatial localisation: the physical objects implementing the qubits are located at well 5. Building NMR quantum computers defined and distinct locations in space. This approach While it would in principle be possible to use a is not possible in NMR, as each qubit is implemented using an ensemble of nuclei. each of which is located wide range of different approaches to build a quantum at a different place in the NMR sample, and all of computer,all the main proposals to date [2,3] have which are undergoing rapid motion Instead different used broadly similar approaches, based on the quan- qubits are implemented using different nuclei in the tum circuit model outlined above. This model contains five major components, each of which must same molecule, and they are distinguished using the different resonance frequencies of each nucleus be implemented in order to construct a working computer [37]. Four central components can all be Two qubit gates, such as the controlled-NOT gate, implemented within NN are more complicated as they involve conditional below, while the fifth component, error correction evolution(that is, the evolution of one spin must is discussed in Section 12 depend on the state of the other spin), and thus require some interaction between the two qubits. The J- 5.1. Qubits coupling in NMR is well suited to this purp Note that all the different nuclei making up an NMR The first of these requirements, a set of qubits quantum computer must participa appears easy to achieve, as the two spin states of coupling network. It is not necessary(or even desir- spin-1/2 nuclei in a magnetic field provide a natural able)that all the nuclei are directly coupled together implementation. However, one important feature but they must be connected, directly or indirectly, by which distinguishes NMR quantum computers from some chain of resolved couplings. Since J-coupling other suggested implementations is that NMR studies only occurs within a molecule, and does not connect not a single isolated quantum system, but rather a very different molecules, we can treat an ensemble of large number (effectively an ensemble) of such molecules as an ensemble of identical mutually systems. Thus an NMR quantum computer is actually isolated computers an ensemble of indistinguishable computers, one on each molecule in the NMR sample. This has a number 5.3. Initialisation of subtle and important consequences as discussed below Quantum logic gates transform qubits from one state to another, but this is only useful if the qubits 5.2. Logic gates start off in some well defined initial state. In practice it is sufficient to have some method for reaching any one In order to perform an arbitrary computation it is initial state, and the obvious choice is to have all the necessary to implement arbitrary quantum logic qubits in the o)state, corresponding to a CLEAR opera circuits. This can be achieved as long as it is possible tion. Any other desired starting state can then be easily to implement an adequate set of gates, which can be

possible implementations of a quantum computer, as it is usually more sensible to use a larger and more convenient set of gates. As one qubit gates are usually much simpler to perform than gates involving two or more qubits, it is often reasonable to assume that any one qubit gate (or, at least a reasonable approximation to it) is available. The combination of this set of one qubit gates with any single non-trivial two qubit gate, such as the controlled-not gate forms an adequate set [33], from which any other gate may be built with relative ease. 5. Building NMR quantum computers While it would in principle be possible to use a wide range of different approaches to build a quantum computer, all the main proposals to date [2,3] have used broadly similar approaches, based on the quan￾tum circuit model outlined above. This model contains ®ve major components, each of which must be implemented in order to construct a working computer [37]. Four central components can all be implemented within NMR systems as described below, while the ®fth component, error correction, is discussed in Section 12. 5.1. Qubits The ®rst of these requirements, a set of qubits, appears easy to achieve, as the two spin states of spin-1/2 nuclei in a magnetic ®eld provide a natural implementation. However, one important feature which distinguishes NMR quantum computers from other suggested implementations is that NMR studies not a single isolated quantum system, but rather a very large number (effectively an ensemble) of such systems. Thus an NMR quantum computer is actually an ensemble of indistinguishable computers, one on each molecule in the NMR sample. This has a number of subtle and important consequences as discussed below. 5.2. Logic gates In order to perform an arbitrary computation it is necessary to implement arbitrary quantum logic circuits. This can be achieved as long as it is possible to implement an adequate set of gates, which can be combined together to implement any other desired gate. While many different sets of gates are possible, a simple approach is to implement the set of all 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 ®elds. 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 de®ned and distinct locations in space. This approach is not possible in NMR, as each qubit is implemented using an ensemble of nuclei, each of which is located at a different place in the NMR sample, and all of which are undergoing rapid motion. Instead different qubits are implemented using different nuclei in the same molecule, and they are distinguished using the different resonance frequencies of each nucleus. Two qubit gates, such as the controlled-not gate, are more complicated as they involve conditional evolution (that is, the evolution of one spin must depend on the state of the other spin), and thus require some interaction between the two qubits. The 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 de®ned initial state. In practice it is suf®cient to have some method for reaching any one initial state, and the obvious choice is to have all the qubits in the u0l state, corresponding to a clear opera￾tion. Any other desired starting state can then be easily obtained. 334 J.A. Jones / Progress in Nuclear Magnetic Resonance Spectroscopy 38 (2001) 325±360