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 resourcesand 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