## Abstract

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 (*8*–*11*) and atomic (*12*–*14*) 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 (*18*–*20*). 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 |*x*_{1}, *x*_{2}, *c*_{1}, *c*_{2}〉 describing its position *x*_{1,2} in spatial dimensions one and two and the corresponding two-sided coin parameters with *c*_{1,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,_{in}〉, resulting in |ψ* _{n}*〉 = (

*ŜĈ*)

*|ψ*

^{n}_{in}〉 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*).

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 |*x*_{1}, *x*_{2}〉 = |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 *= 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).

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 *N*^{2} with one walker. By this topological analogy, a measured spatial distribution from a 2D lattice with positions (*x*_{1}, *x*_{2}) can be interpreted as a coincidence measurement for two walkers at positions *x*_{1} and *x*_{2} 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 *C*_{nl} = (*H*_{1} ⊗ *H*_{2})*C _{Z}*, where

*C*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 (

_{Z}*7*). Evidently, the quantum walk is to a large extent confined to the main diagonal [

*29*).

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

www.sciencemag.org/cgi/content/full/science.1218448/DC1

Materials and Methods

Fig. S1

## References and Notes

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
Materials and methods are available as supporting material on
*Science*Online. - ↵
- ↵
- ↵
- ↵
- ↵
**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).