A 2D Quantum Walk Simulation of Two-Particle Dynamics

See allHide authors and affiliations

Science  06 Apr 2012:
Vol. 336, Issue 6077, pp. 55-58
DOI: 10.1126/science.1218448


Multidimensional quantum walks can exhibit highly nontrivial topological structure, providing a powerful tool for simulating quantum information and transport systems. We present a flexible implementation of a two-dimensional (2D) optical quantum walk on a lattice, demonstrating a scalable quantum walk on a nontrivial graph structure. We realized a coherent quantum walk over 12 steps and 169 positions by using an optical fiber network. With our broad spectrum of quantum coins, we were able to simulate the creation of entanglement in bipartite systems with conditioned interactions. Introducing dynamic control allowed for the investigation of effects such as strong nonlinearities or two-particle scattering. Our results illustrate the potential of quantum walks as a route for simulating and understanding complex quantum systems.

Quantum simulation constitutes a paradigm for developing our understanding of quantum mechanical systems. A current challenge is to find schemes that can be readily implemented in the laboratory to provide insights into complex quantum phenomena. Quantum walks (1, 2) serve as an ideal test bed for studying the dynamics of such systems. Examples include understanding the role of entanglement and interactions between quantum particles, the occurrence of localization effects (3), topological phases (4), energy transport in photosynthesis (5, 6), and the mimicking of the formation of molecule states (7). Although theoretical investigations already take advantage of complex graph structures in higher dimensions, experimental implementations are still limited by the required physical resources.

All demonstrated quantum walks have so far been restricted to evolution in one dimension. They have been realized in a variety of architectures, including photonic (811) and atomic (1214) systems. Achieving increased dimensionality in a quantum walk (15) is of practical interest because many physical phenomena cannot be simulated with a single walker in a one-dimensional (1D) quantum walk, such as multiparticle entanglement and nonlinear interactions. Furthermore, in quantum computation based on quantum walks (16, 17), search algorithms exhibit a speed-up only in higher dimensional graphs (1820). The first optical approaches to increasing the complexity of a linear quantum walk (21, 22) showed that the dimensionality of the system is effectively expanded by using two walkers, keeping the graph one-dimensional. Although adding additional walkers to the system is promising, introducing conditioned interactions and, in particular, controlled nonlinear interactions at the single-photon level is technologically very challenging. Interactions between walkers typically result in the appearance of entanglement and have been shown to improve certain applications, such as the graph isomorphism problem (23). In the absence of such interactions, the two walkers remain effectively independent, which severely limits observable quantum features.

We present a highly scalable implementation of an optical quantum walk on two spatial dimensions for quantum simulation, using frugal physical resources. One major advance of a 2D system is the possibility to simulate a discrete evolution of two particles, including controlled interactions. In particular, one walker, in our case a coherent light pulse, on a 2D lattice is topologically equivalent to two walkers acting on a 1D graph. Thus, despite using an entirely classical light source, our experiment is able to demonstrate several archetypal two-particle quantum features. For our simulations, we exploited the similarity between coherent processes in quantum mechanics and classical optics (24, 25), as it was used, for example, to demonstrate Grover’s quantum search algorithm (26).

A quantum walk consists of a walker, such as a photon or an atom, which coherently propagates between discrete vertices on a graph. A walker is defined as a bipartite system consisting of a position (x) and a quantum coin (c). The position value indicates at which vertex in the graph the walker resides, whereas the coin is an ancillary quantum state determining the direction of the walker at the next step. In a 2D quantum walk, the basis states of a walker are of the form |x1, x2, c1, c2〉 describing its position x1,2 in spatial dimensions one and two and the corresponding two-sided coin parameters with c1,2 = ±1. The evolution takes place in discrete steps, each of which has two stages, defined by coin (Ĉ) and step (Ŝ) operators. The coin operator coherently manipulates the coin parameter, leaving the position unchanged, whereas the step operator updates the position according to the new coin value. Explicitly, with a so-called Hadamard (H) coin ĈH = Ĥ1Ĥ2, a single step in the evolution is defined by the operators,H^i|xi,±1(|xi,1±|xi,1)/2,i=1,2S^|x1,x2,c1,c2|x1+c1,x2+c2,c1,c2 (1)The evolution of the system proceeds by repeatedly applying coin and step operators on the initial state |ψin〉, resulting in |ψn〉 = (ŜĈ)nin〉 after n steps. The step operator Ŝ hereby translates superpositions and entanglement between the coin parameters directly to the spatial domain, imprinting signatures of quantum effects in the final probability distribution.

We performed 2D quantum walks with photons obtained from attenuated laser pulses. The two internal coin states are represented by two polarization modes (horizontal and vertical) in two different spatial modes (27), similar to the proposal in (28). Incident photons follow, depending on their polarization, four different paths in a fiber network (Fig. 1A). The four paths correspond to the four different directions a walker can take in one step on a 2D lattice. Different path lengths in the circuit generate a temporally encoded state, where different position states are represented by discrete time bins (Fig. 1B). Each round trip in the setup implements a single-step operation, whereas the quantum coin operation is performed with linear optical elements (half-wave plates, HWP) (27). In order to adjust the coin operator independently at each position, we used a fast-switching electrooptic modulator (EOM). A measurement with time-resolving single-photon counting modules allowed for the reconstruction of the output photostatistics (27).

Fig. 1

(A) Experimental setup. Our photon source is a pulsed diode laser with a pulse width of 88 ps, a wavelength of 805 nm, and a repetition rate of 110 kHz. The photons are initialized at position |x1, x2〉 = |0, 0〉 in horizontal polarization (corresponding to coin state |c1, c2〉 = |−1, −1〉). Once coupled into the setup through a low-reflectivity beam splitter (BS, reflectivity 3%), their polarization state is manipulated with an EOM and a HWP. The photonic wave packets are split by a polarizing beam splitter (PBS) and routed through single-mode fibers (SMF) of length 135 or 145 m, implementing a temporal step in the x2 direction. Additional HWPs and a second PBS perform a step in the x1 direction based on the same principle. The split wave packet after the first step with equal splitting is indicated in the picture. At each step, the photons have a probability of 12% in loops x1 − 1 (or 4% in loops x1 + 1) of being coupled out to a polarization and hence coin state resolving detection of the arrival time via four avalanche photodiodes (APDs). Including losses and detection efficiency, the probability of a photon continuing the walk after one step is 52% without the EOM and 12% with the EOM. (B) Projection of the spatial lattice onto a 1D temporally encoded pulse chain for step one and two. Each step consists of a shift in both x1 direction, corresponding to a time difference of ∆t1 = 3.11 ns, and x2 direction with ∆t2 = 46.42 ns.

We have implemented two different kinds of quantum coins in our 2D quantum walks. First, we investigated quantum walks driven only by separable coin operations, Ĉ = Ĉ1Ĉ2. Here, the separability can directly be observed in the spatial spread over the lattice, when initializing the walker in a separable state. As an example, we measured a Hadamard walk with photons initially localized at position |x1, x2〉 = |0, 0〉. The probability distribution showing at which position the photons were detected after 10 steps (Fig. 2, A and B) can be factorized into two independent distributions of 1D quantum walks (15), stating no conceptual advantage of a 2D quantum walk. However, 2D quantum walks allow for much greater complexity using controlled operations. These operations condition the transformation of one coin state on the actual state of the other. Because of the induced quantum correlations, one obtains a nontrivial evolution resulting in an inseparable final state. The probability (P) distribution for a Hadamard walk with an additional controlling operation can be seen in Fig. 2, C and D. We compare the ideal theoretical distribution with the measured photostatistics via the similarity, S=[x1,x2Pth(x1,x2)Pexp(x1,x2)]2, quantifying the equality of two classical probability distributions (S = 0 for completely orthogonal distributions and S = 1 for identical distributions). For the Hadamard walk (Fig. 2, A and B), we observe S = 0.957 ± 0.003, and for the quantum walk with controlling gates (Fig. 2, C and D) S = 0.903 ± 0.018 (after 10 steps, across 121 positions).

Fig. 2

Measured and simulated probability distribution P(x1,x2) (traced over the coin space) after 10 steps of a 2D quantum walk with initial state |0, 0, −1, −1〉. Theoretical (A) and measured (B) probability distribution of a 2D Hadamard walk using the operation ĈH (Eq. 1). Because only separable coin operations were performed (inset), the distribution is separable, given by a product of two 1D distributions (gray). Theoretical (C) and measured (D) probability distribution of a 2D walk with controlled-not X and controlled-phase operation Z, resulting in an unfactorizable distribution. Here, c2 is only transformed by Embedded Image if c1 = −1. The results in (B) and (D) are obtained by detecting over 7 × 103 events and calibrated by the detection efficiencies of all four coin basis states. (E) Dynamic evolution of the von Neumann entropy E generated by quantum walks (B) and (D) and quantum walks using controlled Hadamard coin operations (inset). The experimental values (dots) and theoretical predictions (dashed lines) mark a lower boundary for simulated two-particle entanglement. Statistical errors are smaller than the dot size.

Increasing the number of walkers in a quantum walk effectively increases its dimensionality (21). Specifically, for a given 1D quantum walk with N positions and two walkers, there exists an isomorphic square lattice walk of size N2 with one walker. By this topological analogy, a measured spatial distribution from a 2D lattice with positions (x1, x2) can be interpreted as a coincidence measurement for two walkers at positions x1 and x2 propagating on the same linear graph. Hereby each combined coin operation of both particles, including controlled operations, has an equivalent coin operation in a 2D quantum walk. This allows us to interpret the 2D walk in Fig. 2, C and D, as a quantum walk with controlled two-particle operations, a system typically creating two-particle entanglement. The inseparability of the final probability distribution is then a direct signature of the simulated entanglement.

In Fig. 2E, we show a lower bound for the simulated entanglement between the two particles during the stepwise evolution with four different coin operations. We quantified the simulated entanglement via the von Neumann entropy, E, assuming pure final states after the quantum walk (27). For this calculation, the relative phases between the positions and coins were reconstructed from the obtained interference patterns, whereas phases between the four coin states were chosen to minimize the entanglement value. Without conditioned operations, the two particles evolve independently (E = 0), whereas an evolution including controlled operations reveals a probability distribution characterized by bipartite entanglement. We found that the interactions presented in Fig. 2, C and D, exhibit an entropy of at least E = 2.63 ± 0.01 after 12 steps, which is 56% of the maximal entropy (given by a maximally entangled state). The nonzero entropies obtained in the higher steps of the separable Hadamard walk are attributed to the high sensitivity of the entropy measure to small errors in the distribution for E ≈ 0.

The investigated interactions can be interpreted as long-distance interactions with the interaction strength being independent of the spatial distance of the particles. This is a unique effect and highly nontrivial to demonstrate in actual two-particle quantum systems.

Contrary to the position-independent interactions is the evolution of two-particle quantum walks with short-range interactions, that is, interactions occurring only when both particles occupy the same position. These interactions can be interpreted as two-particle scattering or nonlinear interactions. When using a 2D quantum walk to simulate two walkers, all vertices on the diagonal of the 2D lattice correspond to both walkers occupying the same position. Hence, we can introduce nonlinear interactions by modifying the coin operator on the diagonal positions while keeping all other positions unaffected. As an example of a two-particle quantum walk with nonlinear interactions (Fig. 3), the coin operator on the diagonal is in the form Cnl = (H1H2)CZ, where CZ is a controlled phase operation implemented by a fast switching EOM. The chosen operation simulates a quantum scenario of particular interest: the creation of bound molecule states, predicted as a consequence of two-particle scattering (7). Evidently, the quantum walk is to a large extent confined to the main diagonal [xP(x,x)=0.317±0.006 as opposed to the Hadamard walk xP(x,x)=0.242±0.001], a signature of the presence of a bound molecule state. In general, using a coin invariant under particle exchange, bosonic, or fermionic behavior can be simulated, depending on whether the initial states are chosen to be symmetric or antisymmetric with respect to particle permutations. With our initial state being invariant under particle exchange, we simulated an effective Bose-Hubbard type nonlinearity for two bosons (29).

Fig. 3

(A) Circuit representation of coin operations simulating nonlinear interactions via 2D quantum walk. Only when the two virtual particles meet (x1 = x2) is a controlled operation applied. Theoretical (B) and measured (C) coincidence distributions P(x1, x2) (traced over the coin space) after seven steps of a simulated two-particle quantum walk with initial state |0, 0, −1, −1〉. The high probability that both particles are at the same position (diagonal) is a notable signature of bound states. The measured distribution is reconstructed by detecting over 8 × 103 events and has a similarity of S = 0.957 ± 0.013. Adding the EOM to the setup for dynamical control limits the step number to n = 7 because of the higher losses per step. Small imperfections of the EOM are included in the theoretical plot.

We have demonstrated an efficient implementation of a 2D quantum walk and proved the experimental feasibility to simulate a diversity of interesting multiparticle quantum effects. Our experiment overcomes the technical challenges of two-particle experiments while exhibiting very high similarity and scalability. Combined with the flexibility in the choice of input state, controlling the coin at each position independently allows for simulations of a broad spectrum of dynamic quantum systems under different physical conditions.

Our experimental architecture can be generalized to more than two dimensions, with the addition of extra loops and orbital angular momentum modes as coin states (30). This opens a largely unexplored field of research, facilitating quantum simulation applications with multiple walkers, including bosonic and fermionic behavior, and nonlinear interactions. It may be possible to study the effects of higher dimensional localization or graph percolations or to use the network topology in conjunction with single- or two-photon states. Additionally, a foreseeable future application for our system is the implementation of a quantum search algorithm. We demonstrated that, with a physical resource overhead, a classical experiment can simulate many genuine quantum features. Although our experiment is important for simulation applications, it is equally interesting for understanding fundamental physics at the border between classical and quantum coherence theory.

Supplementary Materials

Materials and Methods

Fig. S1

References (3133)

References and Notes

  1. Materials and methods are available as supporting material on Science Online.
  2. Acknowledgments: We acknowledge financial support from the German Israel Foundation (project no. 970/2007). A.G., M.S., V.P., C.H., and I.J. acknowledge grant support from MSM6840770039 and MSMT LC06002, SGS10/294/OHK4/3T/14, GA CR 202/08/H078, and OTKA T83858. P.P.R. acknowledges support from the Australian Research Council Centre of Excellence for Engineered Quantum Systems (project no. CE110001013).

Stay Connected to Science

Navigate This Article