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