We present a scheme for a quantum optical implementation of Grover's algorithm based on resonant atomic interactions with classical fields and dispersive couplings with quantized cavity fields. The proposed scheme depends on preparation of entangled states and is within current state-of-the-art technology.

As was first shown by Grover (1), search of a database by using quantum mechanics can be substantially faster than any classical search of unsorted data. For example, it was shown by Grover that, by using quantum superpositions and quantum entanglement, we can find an object in an unsorted database containing N objects in O() quantum mechanical steps instead of O(N) steps (1–3).

The implementation of search algorithms by using optical methods is a subject of intense interest (4–8), and Grover's search algorithm has been implemented by using nuclear magnetic resonance (NMR) techniques for a system with four states (9–11). However, NMR experiments for quantum computing are carried out at room temperature, and questions have been raised concerning the appearance of entanglement in the physical state at any stage of such experiments (12). Braunstein et al. show that “all states so far used in NMR for quantum computations or for other quantum-information protocols are separable,” and therefore “no entanglement appears in the physical states at any stage of present NMR experiments.”

In this paper, we propose a scheme for quantum optical implementation of Grover's algorithm that is not sensitive to such thermal decoherence effects. The scheme is based on resonant atomic interactions with classical fields and dispersive coupling with quantized cavity fields. We first formulate the problem in terms of a “circuit” logic involving one-bit unitary transformation and a two-bit quantum phase gate. For an atomic system, the one-bit unitary transformation is accomplished by means of resonant interaction with a classical field, whereas a quantum phase gate can be implemented by using dispersive coupling with a cavity field having either 0 or 1 photon. Such a quantum phase gate has been demonstrated recently [for a beautiful demonstration of quantum phase gate, see Rauschenbeutel et al. (13); conditional phase shifts are also demonstrated in Turchette et al. (14)]. The proposed scheme involving atomic interaction with classical field and two cavities therefore lies within present experimental limitations and should be realizable (15).

Grover proposed an algorithm to search an item in an unsorted database. The problem he addressed is as follows. We are given a function f(x) with x = 1, 2…N. The function has the property that it is 0 for all values of x except for x₀, for which f(x₀) = 1. The task is to find x₀. Classically, it would require an average of N/2 steps to accomplish this task. Grover showed that we can find x₀ in O() quantum mechanical steps instead of O(N) steps.

The basic idea of Grover's algorithm is to invert the phase (e.g., change + → −, as in the passage from Eqs. 6 to 8) of the desired basis state and then invert all the basis states about the average amplitude of all the states. In this paper, we restrict ourselves to the simplest interesting Grover's algorithm with N = 4 with two qubits. First, we discuss the implementation of Grover's algorithm in terms of quantum logic gates.

A universal quantum computer consists of only two gates, namely a unitary transformation (one-bit gate) and a two-bit conditional quantum phase gate. The one-bit quantum gate for the ith qubit is given by

1

A convenient representation of U_θ, in terms of Pauli spin matrices is given by

2

The transformation for a two-bit quantum phase gate is given by Q_η|α, β > = exp(iηδ_α,1δ_β,1)|α, β >, where |α > and |β > stand for the basis states |0 > or |1 > of the qubit. Thus, the quantum phase gate introduces a phase η only when both qubits in the input state are 1. In the following, we shall need the quantum phase gate only with η = π, for which we have

3

and because |0 >< 0| = (1 + σ_z)/2 and |1 >< 1| = (1 − σ_z)/2,

4

Grover's algorithm is accomplished in three steps. The initial state of the two qubits is |1, 1 >. In the first step, we apply the Walsh–Hadamard transformation,

5

which rotates each qubit from |0 > to (|0 > −|1 >)/ and |1 > to (|0 > +|1 >)/. The resulting state is

6

In the second step, the unitary operator _α,β flips the sign of state |α, β > (α = 0 or 1 and β = 0 or 1). In the original Grover's algorithm, this is accomplished through operator (1 − 2|α, β > < α, β|). Here we follow a different approach. We first flip the sign of state |1, 1 > via a quantum phase gate Q_π, followed by unitary operators that either retain the state of the qubit or change the state of the qubit from 0 to 1 and 1 to 0. The sign flip operators for the four possible states in this approach are given by

7a

7b

7c

7d

Here the resulting state may have an unimportant overall phase factor.

At this point, the oracle applies one of the C_α,β operators to state 6 and thus changes one of the signs from + to −. For example, if C_0,1 is chosen, then Eq. 6 becomes

8

It is now our job to find the marked state (|0, 1 > in the above example). This is accomplished by the application of operator = 1 − 2|s >< s|. The resulting state is the desired state |a, b > apart from an unimportant π phase shift. To find a representation for in terms of operators U_θ, and Q_π, we first note that

9

so that, from Eqs. 8 and 9, we have C_0,1|s >= −|0, 1 >. If we use the fact that rotating σ_z about the y axis yields σ_x, that is,

10

we note the remarkable fact that operator as given by Eq. 9 is the appropriately rotated quantum phase operator Q_π of Eq. 7b, i.e.,

11

This is the essence of Grover's algorithm and the departure point for our implementation of the algorithm.

On combining the various operators from Eqs. 5, 7, and 11, we can write Grover's algorithm in terms of simple transformations corresponding to one- and two-bit quantum gates as _α,β|1, 1 >= e^iψ|α, β >, where ψ is a phase depending on the choice of α and β. These steps are summarized in the “circuit” diagram of Fig. 1 for the present (N = 4) implementation of Grover's algorithm. Only the one-bit unitary gates and two-bit conditional quantum phase gates are required for this purpose.

Next, we consider schemes for the implementation of Grover's algorithm on the basis of cavity quantum electrodynamics (16–20), using resonant atomic interaction with classical Ramsey fields and dispersive atomic interaction with quantized high Q cavity fields. First, we present a scheme that requires two species of atoms and two cavities. This scheme is conceptually simple but difficult to implement. We then consider a second scheme that requires single species of atoms interacting with only one cavity that supports two modes, and the atomic level spacings are appropriately changed by electric or magnetic fields.

First, we consider the schematic for the proposed implementation as given in Fig. 2. The two qubits are represented by two different three-level atoms of types A and B (Fig. 2a). Levels |a > and |b > of these atoms represent qubits |0 > and |1 >, respectively. The levels scheme is such that ω_a1b₁ = ω_c2b₂ + Δ₁ and ω_a2b₂ = ω_c1b₁ + Δ₂. Cavities C₁ and C₂ are resonant with transitions ω_a1b₁ and ω_a2b₂, respectively. Here, and in the following, the odd subscripts 1, 3, 5, and 7 refer to the atom, cavity, and classical fields corresponding to the atoms of type A, whereas the even subscripts 2, 4, 6, and 8 refer to atoms of type B. Four atoms (two of type A and two of type B) pass through cavities C₁ and C₂ and a sequence of classical fields, as follows (Fig. 2b).

All the atoms are initially in their ground states |b >, i.e., |b₁, b₂, b₃, b₄ >, and we assume that the classical Ramsey fields are on only when the appropriate atoms are passing through them. Atom 1 of type A and atom 2 of type B are initially in their ground states |b₁ > and |b₂ >, i.e., in qubits |1, 1 >. The Walsh–Hadamard transformation on these atoms is carried out by interacting with classical fields R₁ and R₂ of frequencies ω_a1b₁ and ω_a2b₂, respectively. The interaction of an atom with the classical field results in the unitary transformation (Eq. 1) on the atomic states |a > and |b >, such that θ depends on the Rabi frequency and the interaction time, and depends on the phase of the driving field (21, 22). We choose, for the interaction of R₁ with atom 1 and R₂ with atom 2, θ₁ = θ₂ = π/4 and ₁ = ₂ = −π/2, so that the state of the atoms is (|a₁, a₂ > +|a₁, b₂ > +|b₁, a₂ > +|b₁, b₂ >)/2.

In the next step, we consider operation _a,b. This step requires, in addition to the unitary operations, a quantum phase gate. The operation of the quantum phase gate is accomplished as follows. Atom 1 in the state (|a₁ > +|b₁ >)/ passes through the empty cavity C₁. The interaction time is chosen such that the atom leaves in the ground state |b₁ >, and the field state inside the cavity becomes (|0₁ > +|1₁ >)/. Atom 2, which is of type B, then passes through the cavity. Because of the dispersive coupling, the effective Hamiltonian for the interaction between atom 2 and cavity C₁ is (21, 22)

12

where g is a coupling coefficient, and a₁ and a are destruction and creation operators for the field state inside cavity C₁. The resulting entangled state between atom 2 and the field in cavity C₁ is ½(|0₁, a₂ > +|0₁, b₂ > +|1₁, a₂ > +e^iη|1₁, b₂ >), where η = g²τ/Δ₁. The net result is that there is no photon number change inside the cavity, and there is a phase change only when there is one photon inside the cavity and the atom is in state |b₂ >. Interaction time τ and detuning Δ₁ are chosen such that η = π. This operation corresponds to the quantum phase gate discussed above and experimentally implemented in refs. 13 and 14.

Atom 3 of type A in ground state |b₃ > now passes through cavity C₁, followed by a classical field R_C1. The interaction times with the cavity and classical fields are such that the cavity field is reduced to |0 >, and the resultant entangled state between atoms 2 and 3 is given by (|a₃, a₂ > +|a₃, b₂ > +|b₃, a₂ > −|b₃, b₂ >)/2. Here and in the following, we neglect the unimportant overall phase factor. Now _0,0, _0,1, _1,0, and _1,1 are implemented by turning classical fields R₃ and R₄ on, only R₃ on, only R₄ on, and none of the fields on, respectively. In the present example where the oracle picks _0,1, field R₃ is tuned to frequency ω_a1b₁ and interacts with atom 3, and field R₄ tuned to frequency ω_a2b₂ is off. The interaction time for field R₃ is chosen such that θ = π/2 and = 0. Atoms 2 and 3 are in an entangled state (|a₃, a₂ > −|a₃, b₂ > +|b₃, a₂ > +|b₃, b₂ >)/2. This completes the oracle operation _0,1 corresponding to the π phase shift of state |a₃, b₂ >.

Next, we implement operator , which inverts the states about the average. Atoms 3 and 2 interact with classical Ramsey field R₅ and R₆, which are resonant with |a > to |b > transitions of atoms 3 and 2 with θ = π/4 and = π/2.

According to Eq. 12, we should next apply a quantum phase gate Q_α with α = π. This step is accomplished as above by first transferring the atomic coherence of atom 2 to the empty cavity C₂ by adjusting the interaction time with the cavity appropriately. And then, on passing atom 3 through cavity C₂, the entangled state of atom 3 and cavity C₂ is (|a₃, 0₂ > −|a₃, 1₂ > +|b₃, 0₂ > −|b₃, 1₂ >)/2.

Subsequently, a fourth atom of type B passes through cavity C₂, and a classical field, R_C2, leaves the cavity empty and transfers the field coherence to the atom yielding (|a₃, a₄ > −|a₃, b₄ > +|b₃, a₄ > −|b₃, b₄ >)/2. As a last step, atoms 3 and 4 pass through a sequence of classical fields, R₇, resonant with |a > to |b > transitions of atom 3 and R₈ resonant with |a > to |b > transitions of atom 4, such that θ = π/4, = π/2 for R₇, R₈. This step completes the implementation of operator , and the resulting state of atoms 3 and 4 is |a₃, b₄ >. The final state of atoms 3 and 4 would be |a₃, a₄ >, |a₃, b₄ >, |b₃, a₄ > or |b₃, b₄ >, depending on the choice of _α,β.

Motivated by the above scheme, we consider an equivalent scheme that requires only one species of atoms and a single cavity, as shown in Fig. 3. Here the atoms have one lower level and two excited levels, whose splitting can be adjusted by applying electric or magnetic fields (23). These Stark or Zeeman splittings can be used to carry out resonant or dispersive atomic couplings with the cavity fields.

We consider a cavity that can support two modes of frequencies ν₁ and ν₂. The three-level atoms having a lower level |b > and two upper levels |a₁ > and |a₂ > can have level spacings that depend on the applied electric or magnetic fields, as shown in Fig. 3a. Level |b > corresponds to qubit |1 >, and levels |a₁ > and |a₂ > correspond to qubit |0 > for atoms 1 and 3 and atoms 2 and 4, respectively. In configuration 0, levels |a₁ > and |a₂ > are completely detuned with respect to cavity resonance frequencies ν₁ and ν₂, and the atom is effectively decoupled from the cavity fields. In configuration 1, the atom resonantly interacts with ν₁ but is decoupled with ν₂. In configuration 2, the atom interacts dispersively with ν₂ but is decoupled with ν₁. Similarly, in configurations 3 and 4, the atom interacts resonantly with ν₂ with no interaction with ν₁, dispersively with ν₁, and with no interaction with ν₂.

As before, four atoms are sent inside the cavity initially in their ground state |b > such that they interact with a sequence of classical driving fields R_i (i = 1 − 8) and cavity fields C₁ and C₂ of frequencies ν₁ and ν₂, respectively, as shown in Fig. 3b. The interaction times are the same as in the first scheme. The appropriate interactions leading to the implementation of Grover's algorithm corresponding to the first scheme are obtained if the sequence of the atomic level spacings during the passage through R_i and C_i is chosen for various atoms as that given in Fig. 3c.

In conclusion, we have shown how Grover's algorithm can be implemented by using the known methods and techniques of quantum optics. Limitations are imposed by considerations of spontaneous emission and by cavity field damping. A potential source of error is the uncertainty associated with the location of atoms in the various fields.

We thank L. Davidovich, J. Dowling, K. Kapale, H. Lee, and C. P. Williams for valuable discussions. This research is supported by the Office of Naval Research, the National Science Foundation, and the Welch Foundation.