Quantum random walks - an introductory overview <s> V. PHYSICAL IMPLEMENTATION <s> Methods for, and limitations to, the generation of entangled states of trapped atomic ions are examined. As much as possible, state manipulations are described in terms of quantum logic operations since the conditional dynamics implicit in quantum logic is central to the creation of entanglement. Keeping with current interest, some experimental issues in the proposal for trappedion quantum computation by J. I. Cirac and P. Zoller (University of Innsbruck) are discussed. Several possible decoherence mechanisms are examined and what may be the more important of these are identified. Some potential applications for entangled states of trapped-ions which lie outside the immediate realm of quantum computation are also discussed. <s> BIB001 </s> Quantum random walks - an introductory overview <s> V. PHYSICAL IMPLEMENTATION <s> Recently, several groups have investigated quantum analogues of random walk algorithms, both on a line and on a circle. It has been found that the quantum versions have markedly different features to the classical versions. Namely, the variance on the line, and the mixing time on the circle increase quadratically faster in the quantum versions as compared to the classical versions. Here, we propose a scheme to implement the quantum random walk on a line and on a circle in an ion trap quantum computer. With current ion trap technology, the number of steps that could be experimentally implemented will be relatively small. However, we show how the enhanced features of these walks could be observed experimentally. In the limit of strong decoherence, the quantum random walk tends to the classical random walk. By measuring the degree to which the walk remains quantum, '' this algorithm could serve as an important benchmarking protocol for ion trap quantum computers. <s> BIB002 </s> Quantum random walks - an introductory overview <s> V. PHYSICAL IMPLEMENTATION <s> Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still unclear how to use these novel properties to gain an algorithmic speedup over classical algorithms. In this paper, we present a quantum search algorithm based on the quantum random-walk architecture that provides such a speedup. It will be shown that this algorithm performs an oracle search on a database of N items with O({radical}(N)) calls to the oracle, yielding a speedup similar to other quantum search algorithms. It appears that the quantum random-walk formulation has considerable flexibility, presenting interesting opportunities for development of other, possibly novel quantum algorithms. <s> BIB003 </s> Quantum random walks - an introductory overview <s> V. PHYSICAL IMPLEMENTATION <s> We introduce the quantum quincunx, which physically demonstrates the quantum walk and is analogous to Galton's quincunx for demonstrating the random walk by employing gravity to draw pellets through pegs on a board, thereby yielding a binomial distribution of final peg locations. In contradistinction to the theoretical studies of quantum walks over orthogonal lattice states, we introduce quantum walks over nonorthogonal lattice states (specifically, coherent states on a circle) to demonstrate that the key features of a quantum walk are observable albeit for strict parameter ranges. A quantum quincunx may be realized with current cavity quantum electrodynamics capabilities, and precise control over decoherence in such experiments allows a remarkable decrease in the position noise, or spread, with increasing decoherence. <s> BIB004 </s> Quantum random walks - an introductory overview <s> V. PHYSICAL IMPLEMENTATION <s> We propose an experimental realization of discrete quantum random walks using neutral atoms trapped in optical lattices. The random walk is taking place in position space and experimental implementation with present day technology --even using existing set-ups-- seems feasible. We analyze the influence of possible imperfections in the experiment and investigate the transition from a quantum random walk to the classical random walk for increasing errors and decoherence. <s> BIB005 </s> Quantum random walks - an introductory overview <s> V. PHYSICAL IMPLEMENTATION <s> We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time. <s> BIB006
We have attempted to convince the reader of the utility to study random walks -both for the interesting physical effects they show as well as for their potential algorithmic use. In both cases it would be interesting to find a physical set-up to implement the quantum random walk. Of course a universal quantum computer can do thatas we have seen in Sec. IV. However, this machine has yet to be built on a large scale. Random walks might exhibit specifics that could ease their implementation in certain physical systems, making use of the structure of the graph underlying the walk or the character of the coin, for example. Such an implementation does not necessarily constitute a full fledged quantum computer but could still be well suited to study random walks or to solve algorithmic problems based on them BIB003 BIB006 . In this spirit several proposals for various physical systems have been made BIB002 BIB004 BIB005 . As of today it is not clear which physical architecture is the optimal one to build a quantum computer. As we have seen we need qubits and gates which can be implemented in a multitude of ways. This fungibility of quantum information gives rise to proposals ranging from nuclear magnetic resonance systems, optical cavities, solid state architectures, optical lattices to ion traps, to name just a few. Similarly the options to implement a quantum random walk are vast. We will just touch upon a few, without giving a detailed description of the physical system; the reader is referred to the respective references for the details. Of course the positions of the walk |i need not be real positions in the physical implementation: we can encode them into any discrete degree of freedom. Similarly the coin space need not correspond to the spin of a spin- 1 2 particle. For instance Travaglione and Milburn BIB002 suggest an ion-trap based implementation of the random walk on a line. In this set-up an ion is confined in a RadioFrequency ion trap (see  BIB001 for an overview on the ion trap quantum computer). The positions |i are encoded into the (discrete) motional states of the ion in the trap. The ion is laser-cooled to its motional ground state |0 . The electronic internal states of the ion will encode the coin states | ↑ and | ↓ . Raman beam pulses are applied to implement a coin-flip. A displacement beam excites the motion correlated to the | ↑ internal state of the ion. Flipping the internal states with another Raman pulse and applying the displacement beam again effectively implements the conditional shift. This procedure can be iterated T times. To measure the positions of the walk after T steps it is possible to couple the motional state to the internal state of the ion and measure the latter (see BIB002 for details). The main source of noise in this scheme is the degradation of the internal state of the ion (the coin state). With present day technology we might be able to implement a few steps of the random walk  . If nothing else the variance of the quantum random walk so obtained can serve as a benchmarking protocol for ion trap quantum computers. Another recent suggestion by Sanders et al. BIB004 puts the random walk into a quantum electrodynamics device. The physical system is an optical cavity traversed by an atom. During the traversal the internal electronic levels of the atom interact with the cavity mode. Furthermore the internal atomic levels can be addressed and manipulated with a periodic sequence of microwave pulses. The focus of this proposal is to implement the random walk with existing present day technology in a microwave cavity. In this set-up the position of the random walk is encoded into a single cavity mode, whereas the coin states are the internal atomic states  . Here a random walk on the circle is achieved. Let us sketch the scheme of BIB004 in more detail (for the optical background see  ): The field mode of the cavity is described by the (infinite) Hilbert space of a harmonic oscillator spanned by photon number states {|n : n = 0, 1, . . .}. LetN be the number operator acting asN |i = i|i . For the Hadamard walk on the N -circle we will employ a truncated Hilbert space H N spanned by the N states with less than N photons. The random walk will take place on the phase states {|θ 0 , |θ 1 , . . . , |θ N −1 } with A shift on the phase states can be induced by the operator F ± = exp(± 2πi NN ), i.e. F ± |θ j = |θ j±1 . As in Sec. II let the two atomic states we employ be | ↑ and | ↓ , and let S z be as in Eq. (4). Then the conditional shift S is given by S = exp(−2iS z ⊗ 2π NN ) very similar to Eq.  . To implement S we use a two-level model including ac-Stark shifts. The atomic levels are highly detuned from the cavity field, and the Hamiltonian for this effect is given by H =hχN ⊗ 2S z . The Hadamard transformation for the coin-flip on the atomic levels can be realized by a π/2 pulse. The time τ between successive pulses is set to be τ = 2πi/hχN . This implements the random walk. The standard initial condition would be to have the field in the state that projects to |θ 0 in the truncated space. This is unfeasible experimentally at this point. To make the random walk readily implementable with present state technology the initial state of the cavity is taken to be a coherent state |α (α real and positive). It is possible to find such states |α that have high overlap with |θ 0 and very small overlap with |θ j for j = 0, at least for N not too large BIB004 . Measuring the position of the walker corresponds to detecting a phase shift of an initial coherent cavity field. This can be achieved using homodyne detection (see  for definitions). All ingredients employed in such an implementation of the random walk are achievable with current technology. Another upshot of this proposal is that controlled decoherence can be introduced into the cavity. This allows to study the decrease in phase diffusion (transition from a linear spread σ ∼ T in the quantum case to a classical spread σ ∼ √ T ) with noise (see also Sec. VI). Note how this decrease in dissipation contrasts sharply with the intuition provided by the fluctuation-dissipation theorem: that the introduction of noise usually results in increased dissipation! An implementation of random walks in optical lattices has been proposed by Dür et al. BIB005 . This proposal uses neutral atoms trapped in an optical lattice. The walk (on line or circle) takes place in position space given by the minima of an optical lattice. An optical lattice consists of periodic optical potentials formed by the standing waves resulting from two counter-propagating waves from two lasers. Here two identical one-dimensional optical lattices will be used, each of them trapping one of the internal states | ↑ , | ↓ of a neutral atom. The internal states can be hyperfine states of the nuclear spin of the atom. The relative spacing of the potential minima of the optical lattices can be shifted by modulating the angle between the two counter-propagating waves, in particular the minima of the two lattices coincide when the angle is a multiple of π/2. To implement the conditional shift we modulate the angle such that the lattice trapping the | ↑ -state moves with constant velocity v to the right, whereas the second lattice (trapping | ↓ ) moves with constant velocity −v to the left. This motion realizes the controlled shift. Laser pulses allow one to manipulate the internal state of the atom and to implement the Hadamard transform. For the random walk on the line the two lattices are initially tuned such that their minima overlap and the atom is placed into one of them, x 0 . The lattices are put into motion and the Hadamard pulse is applied at times t = nd/v, where d is the lattice spacing. A simple fluorescence measurement -together with several repetitions of the experiment -allows one to measure the resulting probability distribution. It is possible to implement a walk on the line with one or two absorbing boundaries by shining a laser at a certain position b which couples both internal atomic states to a rapidly decaying level. Modifications of the trapping geometry allow to implement the walk on a circle BIB005 . This set-up is simple enough that many (hundreds) steps of the random walk could be implemented with present day technology. In particular since each lattice site is subject to the same coin-transformation, the procedure does not require individual adressability of the different lattice sites, which is the big challenge when this type of implementation is used to build a quantum computer. Hopefully in the near future either of this proposals or a new one will be implemented to begin experimental observations of quantum walks. Furthermore it would be interesting to see an experimental proposal for the continuous time random walk in some suitable physical system.