## Abstract

Quantum walks of correlated particles offer the possibility of studying large-scale quantum interference; simulating biological, chemical, and physical systems; and providing a route to universal quantum computation. We have demonstrated quantum walks of two identical photons in an array of 21 continuously evanescently coupled waveguides in a SiO* _{x}*N

*chip. We observed quantum correlations, violating a classical limit by 76 standard deviations, and found that the correlations depended critically on the input state of the quantum walk. These results present a powerful approach to achieving quantum walks with correlated particles to encode information in an exponentially larger state space.*

_{y}Random walks are a powerful tool used in a broad range of fields, from genetics to economics. The quantum mechanical analog—quantum walks (*1*, *2*)—generates a large coherent superposition state that allows massive parallelism in exploring multiple trajectories through a given connected graph (Fig. 1). A quantum walk can be implemented via a constant tunneling of quantum particles [including photons (*3*)] into several possible sites, realizing what is termed a “continuous-time quantum walk.” The mathematical model of continuous-time quantum walks such as the ones implemented here have been shown to be the limit of the discrete-time quantum walks (*4*). For continuous-time quantum walks, no quantum coin is required to generate superposition; this evolves continuously through tunneling between neighboring sites. Classical Markov chain theory dictates that the distribution of classical random walks converges toward a stationary distribution independent of the initial state (*5*). This is in contrast to the reversible (unitary) evolution of quantum walks, which do not in general converge to a steady state (*5*) but spread ballistically (Fig. 2C) when evolving in a low-noise (decoherence) environment. These features are at the heart of new algorithms for database search (*6*), random graph navigation, universal quantum computation (*7*), and quantum simulation (*8*, *9*).

Quantum walks have been demonstrated with nuclear magnetic resonance (*10*), trapped ions (*11*, *12*) and trapped neutral atoms (*13*), the frequency space of an optical resonator (*14*), single photons in bulk (*15*) and fiber (*16*) optics, and the scattering of light in coupled waveguide arrays (*17*). However, these realizations have been limited to single-particle quantum walks, which have an exact mapping to classical wave phenomena (*18*), and therefore cannot provide any advantage (computational or otherwise) as a result of uniquely quantum mechanical behavior [in (*12*), two trapped ions were used to realize a three-sided coin in a quantum walk of the center-of-mass mode of the two ions]. Indeed, single-particle quantum walks have been observed with classical light (*17*). In contrast, for quantum walks of more than one indistinguishable particle, classical theory no longer provides a sufficient description—quantum theory predicts that probability amplitudes interfere, leading to distinctly nonclassical correlations (*19*). This quantum behavior gives rise to a computational advantage in quantum walks of two identical particles, which can be used to solve the graph isomorphism problem (determining whether there is a one-to-one mapping between two graphs), for example (*20*). The continuous-time model has been shown to offer an exponential speed-up for particular computations (*21*). The major challenge associated with realizing quantum walks of correlated particles is the need for a low-decoherence system that preserves their nonclassical features.

The intrinsically low-decoherence properties and easy manipulation of single photons make them ideal for observing quantum mechanical behavior and for quantum technologies (*22*), and the effectiveness of arrays of continuously coupled waveguides for bright classical light has been demonstrated (*17*). However, quantum walks with correlated photons in such structures require a means to measure two-photon correlations across the waveguide array. The spacing between waveguides in an array required for evanescent coupling (on the order of several micrometers) is smaller than the minimum spacing of optical fiber arrays (127 μm) typically used to couple to single-photon detectors. Previous quantum optical waveguide circuits in a silica-on-silicon architecture promise to avoid decoherence effects present in other experimental realizations—interferometric stability and near-perfect mode overlap (*22*–*25*)—which is problematic in large-scale bulk optical realizations [an arbitrary *N* mode multiport would require a network of *O*(*N*^{2}) beams splitters (*26*)]. However, the low refractive index contrast [∆ = (*n*_{core}^{2} − *n*_{cladding}^{2})/2*n*_{core}^{2} ≈ 0.5%] in this architecture results in a large minimum bend radius (<0.1 dB loss at 800 nm) of ≈15 mm, making it unsuitable for coupling into and out of large-array quantum walk devices.

We fabricated waveguide arrays in SiO* _{x}*N

*(silicon oxynitride), a material that enables a much higher refractive index contrast than silica-on-silicon (the refractive index is determined by*

_{y}*x*and

*y*), resulting in more compact devices (Fig. 2A) and a practical means to realize large coupled waveguide arrays that can be coupled to optical fibers. The device shown in Fig. 2A is a 5-mm-long silicon chip with SiO

*N*

_{x}*waveguides with high refractive index contrast ∆ = 4.4%. The minimum bend radius for this index contrast is 600 μm, which enables much more rapid spreading of the waveguides from the evanescent coupling region where waveguides are pitched at 2.8 μm to a pitch suitable for optical fiber [250 μm and 125 μm for photon injection and photon collection, respectively (*

_{y}*27*)].

Photon pairs were generated in a frequency-entangled but spatial mode–separable state via type I spontaneous parametric downconversion in a 2-mm-thick χ^{2} nonlinear bismuth borate BiB_{3}O_{6} (BiBO) crystal, pumped with 40 mW of 402-nm light from a continuous-wave diode laser. With an opening angle of 3°, pairs of degenerate photons of wavelength λ = 804 nm were filtered by 2-nm interference filters and focused onto two inputs of an array of polarization-maintaining fibers, which were butt-coupled to the waveguide chip. At the output of the chip, an array of multimode fibers guides the photons to 12 single-photon–counting modules. The detectors were connected to photon-counting logic based on three FPGA (field programmable gate array) boards used to postselect all possible two-photon coincidences between different outputs of the array in order to reconstruct the correlation matrices (Figs. 3 and 4). Quantum interference (degree of indistinguishability) was controlled by relative temporal delay between the pair of photons, using an automated linear actuator, and characterized with a standard Hong-Ou-Mandel experiment. The pitch of the waveguide outputs is half that of the collecting fiber arrays, allowing 121 of the 231 possible two-photon correlations to be measured at the output.

Photons propagating through the coupled waveguide array (Fig. 2A) are modeled assuming nearest-neighbor coupling with the Hamiltonian for coupled oscillators (*28*), setting *ħ* = 1:*a _{j}* obey Bose-Einstein statistics and act on waveguide

*j*. In our devices, the waveguide propagation constant β

*= β and coupling constant between adjacent waveguides*

_{j }*C*

_{j}_{,}

_{j}_{±1 }=

*C*are designed to be uniform for all

*j*. Through choice of operator

*z*of the array. For example, the propagation of a single photon initially injected into waveguide

*k*is described by

*29*)

Evolving the vacuum state |0〉 according to Eq. 2 and inspecting in the Schrödinger picture *id*|ψ_{1}〉/*dz *= *H*^{(1)}|ψ_{1}〉, yields the effective Hamiltonian in the one-photon subspace *H*^{(1)}. From this Hamiltonian, an adjacency matrix * _{j}*} for representation. A quantum walk on this graph evolves over length

*z*according to the unitary transform

*U*

^{(1) }= exp[−

*iH*

^{(1)}

*z*] (

*2*,

*29*), the exact dynamics of which can be observed by injecting bright light into the waveguide array (

*17*). We used this approach to calibrate our device and the coupling efficiencies by launching horizontally polarized 810-nm laser light into the input of the central waveguide, waveguide 0. We measured the interference pattern shown in Fig. 2C, which corresponds to the probability distribution for single photons detected at the 21 output waveguides (numbered −10 on the left, through 0, to 10 on the right). Before the waveguides reach their minimum separation at the central coupling region, they are coupled in the spreading regions on both sides. This coupling provides an effective coupling length of 82 μm. We determined this length by comparing the output interference pattern for an array of length 350 μm (fig. S1). From these data, the coupling constant

*C*= 5 mm

^{−1}was determined by running the simulation and minimizing the square of the errors (

*27*).

The propagation of two indistinguishable photons initially injected into waveguide j and k is modeled with the operator

From Eq. 3, the effective Hamiltonian *H*^{(2)} acting on the two-photon Fock space is extracted as a matrix represented in the two-photon Fock basis {|1〉* _{j}*|1〉

*,|2〉*

_{k}*} which is equal to the adjacency matrix for the graph given in Fig. 1B. Evolution of the two-photon state through the device therefore simulates a single-particle quantum walk on the graph in Fig. 1B with*

_{l}*O*(

*N*

^{2}) vertices and unitary transform

*U*

^{(2)}= exp[−

*iH*

^{(2)}

*z*]. In general, a linear increase in the number of photons input into the coupled array results in exponential growth of the Hilbert space and of the corresponding graph. Emulating this with a single photon (or bright laser beam) would require an exponentially large number of waveguides. However, only when indistinguishable photons are injected in the device can the output state be nonseparable, exhibiting nonclassical correlated behavior (

*27*). The two-photon unitary evolution can also be computed from the product of single-photon mode transformations (

*29*).

The measured correlation matrices Γ_{q}_{,}* _{r}* (defined as the probability of detecting a two-photon coincidence across waveguides

*q*,

*r*) (

*29*,

*30*) for injecting two single photons into the central neighboring waveguides 0 and 1

*S*= 0.980 ± 0.001 and

*S*= 0.934 ± 0.001, respectively, where

*S*is the similarity between two probability distributions Γ and Γ′ defined by

*S*in the overlapped case is attributed to imperfect quantum interference. These results display a generalized bunching behavior (tending to both travel to one side of the array or the other) characteristic of quantum interference: The vanishing of the two off-diagonal lobes is a result of destructive interference of quantum amplitudes resulting from repeated π/2 phase shifts in the photon tunneling between neighboring waveguides.

Distinctly different behavior is observed on injecting two photons in two waveguides with one waveguide separating them. The measured correlation matrices for injecting photons into waveguides −1 and 1, and the vacuum in waveguide 0 *S *= 0.970 ± 0.002 and *S *= 0.903 ± 0.002 for the delayed and overlapped photons, respectively. In this case, instead of bunching, when the two photons are indistinguishable they generate a pattern in which the main feature is the vanishing of the probability of simultaneously detecting one photon in the center of the array and one at the limit of ballistic propagation (for example, in waveguides 0 and 7 in Fig. 4, C and D).

Detecting twofold coincidences of two indistinguishable photons leads to nonclassical correlations across pairs of waveguides in the array (*29*). The correlation function after length *z* for two photons populating waveguides *q* and *r* is given (*29*, *30*) by

For classical light, including random phase fluctuations that mimic certain properties of quantum light, diagonal correlations Γ_{q}_{,}* _{q}* are related to correlations in the off-diagonal lobes Γ

_{q}_{,}

*,*

_{r}*q*≠

*r*according to the inequality (

*29*)

Inequality Eq. 5 is violated when two indistinguishable photons are injected into the device. Measured violations from injecting photons into 0, 1, and −1,+1 are plotted in fig. S2, with white data points representing no violation, and colored data points representing the extent of violating Eq. 5 for each pair of waveguides. This is quantified as a function of standard deviations σ (computed from propagation of error from two-photon coincidence detection, assuming Poissonian statistics), with the maximum violation reaching 76 standard deviations. Inequality Eq. 5 is not violated when the photons of the input pairs are distinguishable.

These demonstrations show uniquely nonclassical behavior of two identical particles, tunneling through arrayed potential wells; two photons initially prepared in a separable product state interfere in a generalization of the Hong-Ou-Mandel effect, yielding nonclassical spatial correlations. Increasing the photon number *n* will emulate quantum walks on hypercubic graphs exponentially large in *n*, and exploiting quantum interference in three-dimensional directly written waveguides (*31*) allows a further increase in graph size (*32*). Enlarging the guided mode or decreasing the waveguide separation provides another increase in graph complexity. This requires a model beyond nearest-neighbor coupling, tending toward a multimode interference slab waveguide when the channel separation goes to zero.

Here, we have modeled and used arrays of waveguide with fixed propagation and coupling coefficients β* _{k}* = β and

*C*

_{k}_{±1 }=

*C*, but varying these parameters independently for each

*k*provides a means to engineer the quantum walk’s precise graph structure. For example, varying these parameters randomly and independently allows one to investigate correlated quantum walks in disordered systems and to verify the effects of Anderson localization, known to affect propagation of quantum information (

*33*,

*34*). Reconfigurable waveguide circuits (

*22*,

*24*) will allow real-time control of the input state and the graph structure itself, enabling, for example, phase control over entangled “NOON” input states, such as |20〉 +

*e*

^{i}^{ϕ }|02〉, to yield methods for simulating symmetric and antisymmetric particles undergoing a quantum walk (

*29*). The waveguide architecture is intrinsically scalable—networks of hundreds of waveguides are routinely implemented in photonics applications (switches, modulators, etc.)—and single-particle quantum walks with classical light have been implemented in such devices (

*17*). Homogeneity of the coupling constant for quantum walk devices with hundreds of waveguides is set by the tolerance of waveguide fabrication and will be comparable to that observed here (indicated by the symmetry in Fig. 2C). For future application, computational data rates will be defined by high-efficiency and high–repetition rate single-photon sources and detectors (

*22*).

## Supporting Online Material

www.sciencemag.org/cgi/con500tent/full/329/5998/1500/DC1

Methods

Figs. S1 to S3

References

## References and Notes

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
Materials and methods are available as supporting material on
*Science*Online. - ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- We thank N. Brunner, A. Laing, T. Rudolph, and J. Twamley for helpful discussions. This work was supported by Engineering and Physical Sciences Research Council, European Research Council, EU-FP7 project “Quantum Integrated Photonics”, Quantum Information Processing Interdisciplinary Research, Intelligence Advanced Research Projects Activity, the Leverhulme Trust, Centre for Nanoscience and Quantum Information, and the Japan Society for the Promotion of Science. J.L.OB. acknowledges a Royal Society Wolfson Merit Award.