清华大学：《生物核磁共振波谱学》课程教学资源（文献资料，英文版）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