The system described by Ahn et al., however, cannot implement quantum algorithms any more efficiently than can a classical digital computer. The word "efficiently" in this context refers to how the resources required to implement an algorithm scale with the size of the problem being solved (6). The standard model for quantum computation uses poly-local transformations (7)--implemented, for example, by polynomially many bounded size gates acting on n qubits. These require specification of only polynomially many nontrivial transition amplitudes with constant precision. Any quantum algorithm within this model can also be implemented (on a classical digital computer, for example) by storing the vector of N = 2ⁿ complex amplitudes, which represents the quantum state at each time step, and by successively multiplying the state vector by the N-by-N matrix that specifies each unitary transformation. The resources required for such an implementation scale exponentially, rather than polynomially, with n; the classical implementation is therefore less efficient.

The quantum phase manipulation of Rydberg atom states described by Ahn et al. (1) is not quantum computation because, like this classical implementation, it scales badly with the size of the problem--the number of bits, n = log N, defining the size of the quantum register being searched. This scaling is somewhat subtle because it has two causes, one of which Ahn et al. partly acknowledged and the other of which they did not discuss.

First, the number of atoms they used for each shot at the single-query Grover algorithm (4) was N_min  (2)¹  100. To achieve acceptable success rates, Ahn et al. found that increasing N requires increasing numbers of shots [figure 3 of (1)] or, equivalently, more atoms. In fact, because  = O(1/), Grover showed that the number of N-state quantum systems required scales at least as N log N (4); this single-query algorithm is thus no more efficient than a classical algorithm for the same problem, which is why only Grover's O() query algorithm (3) is the one usually discussed in the quantum computing literature (8).

Second, there is also an exponential price for removing entanglement from Grover's algorithms (9, 10), which commonly is paid with exponentially increasing mass/energy (11). Using N Rydberg states rather than n qubits realizes Lloyd's scheme for removing entanglement (9), but Ahn et al. (1) neglected the exponential overhead required for measurement and for realization of N-by-N unitary transformations. Because the difference (detuning) between adjacent Rydberg energy levels converges to zero polynomially in 1/N (5), both the laser pulses and the final measurements must be specified with exponentially increasing precision in n.

To the best of our knowledge, all physically realized computation is quantum mechanical--but that does not make every computer a quantum computer. A quantum system such as a Rydberg atom that implements a quantum algorithm no more efficiently than a classical computer is not performing quantum computation.

David A. Meyer
Project in Geometry and Physics
Department of Mathematics
University of California at San Diego
La Jolla, CA 92093-0112, USA
and Institute for Physical Sciences
Los Alamos, NM 87544, USA
E-mail: dmeyer{at}chonji.ucsd.edu

REFERENCES AND NOTES

1. J. Ahn, T. C. Weinacht, P. H. Bucksbaum, Science 287, 463 (2000) [Abstract/Free Full Text] .
2. P. Knight, Science 287, 411 (2000) [Free Full Text] .
3. L. K. Grover, Phys. Rev. Lett. 79, 325 (1997) [CrossRef].
4. ___, Phys. Rev. Lett. 79, 4709 (1997) [CrossRef].
5. N. E. Tielking and R. R. Jones, Phys. Rev. A 52, 1371 (1995) [CrossRef] [Medline].
6. E. Bernstein and U. Vazirani, in Proceedings of the 25th Annual Association for Computing Machinery Symposium on the Theory of Computing, San Diego, CA, 16 to 18 May 1993 (ACM, New York, 1993), pp. 1120.
7. M. H. Freedman, http://xxx.lanl.gov/abs/quant-ph/0001077
8. C. H. Bennett and D. P. DiVincenzo, Nature 404, 247 (2000) [CrossRef] [Medline] .
9. S. Lloyd, Phys. Rev. A 61, 010301 (2000) [CrossRef].
10. R. Jozsa, in The Geometric Universe: Science, Geometry, and the Work of Roger Penrose, S. A. Huggett, L. J. Mason, K. P. Tod, S. T. Tsou, N. M. J. Woodhouse, Eds. (Oxford Univ. Press, Oxford, 1998), pp. 369379.
11. P. G. Kwiat, J. R. Mitchel, P. D. D. Schwindt, A. G. White, J. Mod. Optics 47, 257 (2000) [CrossRef].
12. I thank M. Freedman, E. Knill, P. Kwiat, R. Laflamme, L. Small and N. Wallach for useful discussions. This work was partly supported by the National Security Agency (NSA) and Advanced Research and Development Activity (ARDA) under Army Research Office (ARO) contract number DAAG55-98-1-0376.

Ahn et al. (1) described an experimental implementation of an algorithm to search for the marked element in a database with ~7 elements. The labels for the N database elements were represented as amplitudes of Rydberg states of individual cesium atoms, a large ensemble of which were examined to determine the marked element. The report (1) and the accompanying Perspective (2) characterized the results as an implementation of Grover's second quantum search algorithm (3) and as a method for storing information in a "single quantum system." Although we are impressed with the experimental control over Rydberg states, we disagree with these assertions. The reported experiment did not implement the search algorithm as proposed, and offered no computational advantage relative to a classical implementation. It did, however, illuminate the resources required for quantum information processing to achieve an advantage over classical.

Grover's search algorithms (3, 4) rely on the inversion-about-the-mean (IOM) procedure, in which probability amplitude is transferred from each unmarked database element to the marked element. If each of the N elements has an initial amplitude of , the marked element will have final amplitude (3  4/N). Thus, for large databases, the probability of being in the marked state approaches 9². Ideally,  = 1/, though in the experiment of Ahn et al.,  = ~1/20. More important, their procedure implemented an inversion about /2 instead of about the mean, transferring amplitude from the unmarked elements into the 7s state, not into the marked state; hence, the final probability of detecting the marked state is only (2)². To accomplish genuine IOM requires interference between the different elements of the database--that is, coherent transitions between the various Rydberg states--which was not achieved in the Ahn et al. experiment. Their procedure could therefore be performed equally well with a classical system (Fig. 1).

Notwithstanding the suggestion by Knight (2), the IOM procedure itself is not intrinsically nonclassical. As alluded to in (5), physically demonstrated in a classical-optics implementation (6) of Grover's first search algorithm (4), and, finally, discussed for general systems in (7), the same results could be achieved with any system supporting wavelike phenomena, even media such as water or sound. All that are required for these "unary" representations are interacting multiple modes of at least one degree of freedom.

Ahn et al. also speculate on using their Rydberg atoms to store large amounts of information, by allowing multiple Rydberg levels to be marked so that the amplitude of each level represents a bit of information. Many classical bits of information are required, however, to specify the precise pump pulse-shape to prepare the state. Further, information readout requires many replicas: One needs more than 1/(2)² (>N/4) atoms in each marked Rydberg level to have a reasonable likelihood of detecting it, and more than N times that number to sample each Rydberg level [Grover (3) showed that N log N atoms are required]. Is it meaningful to say that an N-bit number is stored in a single atom when quantum mechanics requires greater than O(N² log N) copies to read out this number?

Finally, Ahn et al. suggest that they can encode more information in their states by using more than just the two phase settings, 0 and . This is equivalent to the possibility of encoding an infinite amount of information in the polarization state of a single photon. In both cases, however, these many states are no longer orthogonal and cannot be resolved by a measurement on a single system. The uncertainty principle dictates that the number of particles, N, must equal or exceed 1/, where is the angular resolution. And unless entangled particles are employed (8-10)--certainly not the case for the Rydberg atoms--an even larger number of copies, N ~ O[(1/)²], is required owing to Poisson statistics. Consequently, although a single Rydberg atom could in some philosophical sense store one of 30²⁰ numbers, more than O[(30)²(20)²] = 360,000 copies are required to read it out, a very large number compared with the 100 bits needed to store this information classically. Accounting for the experimental parameters of Ahn et al., the predicted number of copies would be yet another order of magnitude greater.

Three categories of resources would seem to be necessary for quantum information. The first is temporal resources, or the number of operations needed--the number of queries, for example, in the Grover database search. The second is processing resources, or the physical resources to carry out the necessary transformations; this is the resolution of the pulse-shape in the Rydberg case. The third is readout resources, or the number of system copies (for example, Rydberg atoms) required to accurately determine the final state. [Grover (3) calls the second step preprocessing and the third step postprocessing.] Each of the three systems thus far used to implement quantum algorithms--optical, bulk NMR (11-13), and Rydberg atoms--displays savings in temporal resources. Optical implementations (5, 6) require processing resources, optical elements, that grow exponentially in the equivalent number of qubits (linear in N), but a single photon is sufficient for readout when implementing Grover's first search algorithm. The bulk NMR systems require an exponential number of readout resources (14-16). To implement their modified version of Grover's algorithm, Ahn et al. require an exponential number of both processing resources and readout resources.

Paul G. Kwiat
Richard J. Hughes
Los Alamos National Laboratory
Los Alamos, NM 87545, USA
E-mail: kwiat{at}lanl.gov, hughes{at}lanl.gov

REFERENCES AND NOTES

1. J. Ahn, T. C. Weinacht, P. H. Bucksbaum, Science 287, 463 (2000) .
2. P. Knight, Science 287, 441 (2000) [Free Full Text] .
3. L. K. Grover, Phys. Rev. Lett. 79, 4709 (1997) .  4.  ___, Phys. Rev. Lett. 79, 325 (1997) .
4. N. J. Cerf, C. Adami, P. G. Kwiat, Phys. Rev. A 57, R1477 (1998) [CrossRef].
5. P. G. Kwiat, J. R. Mitchell, P. D. D. Schwindt, A. G. White, J. Mod. Opt. 47, 257 (2000) [CrossRef].
6. S. Lloyd, Phys. Rev. A 61, 010301 (2000) .
7. B. Yurke, Phys. Rev. Lett. 56, 1515 (1986) [CrossRef] [Web of Science] [Medline].
8. ___, S. L. McCall, J. R. Klauder, Phys. Rev. A 33, 4033 (1986) [CrossRef] [Medline].
9. J. J. Bollinger, W. M. Itano, D. J. Wineland, D. J. Heinzen, Phys. Rev. A 54, R4649 (1996) [CrossRef] [Medline].
10. N. A. Gershenfeld and I. L. Chuang, Science 275, 350 (1997) [Abstract/Free Full Text] .
11. I. L. Chuang, N. Gershenfeld, M. Kubinuc, Phys. Rev. Lett. 80, 3408 (1998) [CrossRef].
12. J. A. Jones, M. Mosca, R. H. Hansen, Nature 393, 344 (1998) [CrossRef] .
13. W. S. Warren, Science 277, 1688 (1997) [Free Full Text] .
14. S. L. Braunstein, et al., Phys. Rev. Lett. 83, 1054 (1999) [CrossRef].
15. R. Schack and C. Caves, Phys. Rev. A 60, 4354 (1999) [CrossRef] [Web of Science].
16. This work was supported in part by the NSA and ARDA under contract number MOD713700.

Response: The comment of Meyer and that of Kwiat and Hughes both hinge on the assertion that quantum computations should exhibit a certain type of scaling that takes advantage of the multiple degrees of freedom in the quantum state space. The use of quantum phase to store information, the comments argue, does not automatically imply favorable scaling for large problems. We agree; indeed, the experiment of Ahn et al. (1) demonstrates that point. In this response, we examine that experiment in the context of the scaling issue, and then address some additional important questions raised by Kwiat and Hughes about quantum mechanics in general.

In the Ahn et al. experiment, binary 1's and 0's were encoded as + and  phases, respectively, of the quantum states in the energy eigenbasis of a Rydberg wave packet. We demonstrated that a universal unitary transformation of the system (executed in this case by a single ultrafast laser pulse incident on an ensemble of Rydberg atoms) exists that can interrogate all of the states at once, and decode the location of the binary 1's in a single step. The Rydberg eigenstates form a unary basis; thus, the degrees of freedom in the atom (three space and two spin) are coupled so that each state in the system can be addressed individually. Each state in the Rydberg data register lies at a different energy, so different states are populated by exciting the ground state of the atom with a different spectral component of the light field. Each spectral component is therefore a separate "control knob" for the problem.

Because of that individuality, a scaling problem arises for large data registers: the number of independent colors that need to be controlled to load a binary number into an N-state register grows linearly with N and, therefore, exponentially with the number of degrees of freedom. In Rydberg atoms, as Meyer points out, the state splittings converge as 1/N, so the required optical resolution diverges as N increases. The number of atoms in the ensemble multiplied by the optical pulse energy must also grow at least linearly with N, because the excitation oscillator strength per unit energy remains roughly constant throughout the Rydberg spectrum.

We stress that the optical-resolution-scaling problem does not exist for the database search itself, but only for the initial loading of the register. That is because the universal decoding transformation is a single ultrafast pulse--an optical pulse with constant spectral phase. The pulse has a continuous frequency distribution, so it retains its effectiveness as the density of Rydberg states increases. Furthermore, as long as the loading and decoding pulses have the same spectral width and total energy, the decoding pulse will be efficient (1).

Because the scaling failure of Rydberg data storage is the fault of the addressing scheme and not of the Rydberg atom itself, the limitation is not fundamental. The unfavorable scaling properties of Rydberg state addressing are overcome in some other physical systems by manipulating the degrees of freedom, rather than the coupled states (2, 3). One successful example is the cooled ion trap (2), in which the number of control knobs grows only as a polynomial power of the number of ions, and therefore as the logarithm of the number of states. Ahn et al. [p. 465 of (1)] raised the possibility that the individual degrees of freedom of Rydberg states might be addressable using terahertz "half-cycle" pulsed radiation. Many unsolved problems remain for the future, however; terahertz pulses have not yet been used to store and retrieve information, for example, and scaling the system to more than five degrees of freedom will require coupling atoms together.

Quite apart from the scaling issue, Kwiat and Hughes raise several other questions about the Ahn et al. experiment and about quantum mechanics in general. Particularly important is the issue of quantum interference, which Kwiat and Hughes claims is not a general feature of these atomic wave packet experiments. We have a different view. The simple fact that two probability amplitudes (in this case, the encoding and decoding amplitudes) can either add or subtract, depending on their phase, plainly implies quantum interference in the Ahn et al. experiment.

Kwiat and Hughes also discuss the quantum process that corresponds to the vector algebraic operation of inversion about the mean. This operation lies at the heart of the data manipulation routines described by Grover (4), who used IOM to transfer probability from the general data state space to the single state representing the marked bit--that is, the state being sought. In the view of Kwiat and Hughes, the use by Ahn et al. (1) of the 7s level of atomic cesium as a repository for most of the quantum probability amplitude violates the IOM operation, because at the end of the retrieval operation the most probable place to find the atom is back in the 7s state.

Use of 7s in this way, however, actually afforded a very important experimental convenience: It allowed Ahn et al. to use perturbation theory formalism to calculate the shape of the decoding wave packet, which transferred all of the probability amplitude out of the unmarked bits and placed additional probability amplitude in the marked bit. Ahn et al. thus accomplished the same result intended by Grover's IOM, because the only Rydberg population remaining after this operation resided in the marked bit. Convenience has its cost, however, as noted by Kwiat and Hughes (and, for that matter, by Ahn et al.): The information retrieval is inefficient, because when the Rydberg state spectrum is measured by state-selective field ionization, the atom has a good probability of collapsing to the 7s state, which effectively renders it invisible.

The experimental technique could be modified to overcome this inefficiency. We have explored algorithms that store no probability in the 7s state. Such an approach has some advantages, because nearly all of the quantum dissipation in the experiment occurs through the 7s radiative decay. The universal decoding pulse can then execute the IOM operation in the way preferred by Kwiat and Hughes, and the final state has a 100% probability of residing in the marked location, rather than a probability proportional to ². Shaped terahertz pulses can perform this universal decoding function (5), as can specially shaped optical fields that transfer population via Raman coherences with lower-lying atomic states.

Finally, Kwiat and Hughes describe a tabletop optical analog to the Ahn et al. experiment that would require neither coherent light nor interference. The difference, however, is that in the Ahn et al. experiment, each atom contains the entire data register. The experiment would not work with a heterogeneous collection of atoms--some of which, for example, are excited to state 27p and others to state 28p. In that case, the decoding pulse would have a very different effect, according to the normal rules of photoexcitation: it would excite the empty states in this heterogeneous mixture, and state-selective field ionization would detect many occupied final Rydberg states, not just the one with the marked bit.

The similarity of quantum dynamics and classical wave mechanics is because, as Schrödinger's equation guarantees, quantum evolution prior to a measurement is the same as the evolution of any classical scalar field. In the case of the Ahn et al. experiment, the quantum evolution mirrors a classical wave analysis right up until the point of measurement. The measurement breaks this, because the measurement operator must, according to quantum mechanics, return an eigenvalue of the measurement. Thus, even though the probability amplitude for a Rydberg state might be only on the order of , some atoms (actually, a fraction equivalent to ²) will be found in that state, not just "partly there." Atomic physicists are so accustomed to this natural form of quantum filtering that they often forget to emphasize it.

In sum, the number of physical operator "levers" in the Ahn experiment needed to access any desired state scales with the size of the state space, and that does not favor increasing the system to very large size. In quantum systems in which each degree of freedom is addressed separately, the operator complexity scales logarithmically with the state space, a more favorable scaling. This is, as Meyer and Kwiat and Hughes imply, an extremely important point for anyone wishing to build a large computational engine based on quantum mechanics. Although the unfavorable scaling makes the data storage method used by Ahn et al. unsuitable for very large computational problems, the experiments described in (1) nonetheless constitute progress that can serve to stimulate greater understanding and further developments in this field.

P. H. Bucksbaum
J. Ahn
T. C. Weinacht
Department of Physics
Randall Laboratory
University of Michigan
Ann Arbor, MI 48109-1120, USA
E-mail: phb{at}umich.edu

REFERENCES AND NOTES

1. J. Ahn, T. C. Weinacht, P. H. Bucksbaum, Science 287, 463 (2000) .
2. C. A. Sackett, et al., Nature 404, 256 (2000) [CrossRef] [Medline] .
3. S. Lloyd, Phys. Rev. A 61, 010301 (2000) .
4. L. K. Grover, Phys. Rev. Lett. 79, 4709 (1997) .
5. N. Tielking and R. Jones, Phys. Rev. A 52,1371 (1995).
6. This work was supported by NSF grants 9414335 and 9987916.