## Abstract

Quantum walks, in virtue of the coherent superposition and quantum interference, have exponential superiority over their classical counterpart in applications of quantum searching and quantum simulation. The quantum-enhanced power is highly related to the state space of quantum walks, which can be expanded by enlarging the photon number and/or the dimensions of the evolution network, but the former is considerably challenging due to probabilistic generation of single photons and multiplicative loss. We demonstrate a two-dimensional continuous-time quantum walk by using the external geometry of photonic waveguide arrays, rather than the inner degree of freedoms of photons. Using femtosecond laser direct writing, we construct a large-scale three-dimensional structure that forms a two-dimensional lattice with up to 49 × 49 nodes on a photonic chip. We demonstrate spatial two-dimensional quantum walks using heralded single photons and single photon–level imaging. We analyze the quantum transport properties via observing the ballistic evolution pattern and the variance profile, which agree well with simulation results. We further reveal the transient nature that is the unique feature for quantum walks of beyond one dimension. An architecture that allows a quantum walk to freely evolve in all directions and at a large scale, combining with defect and disorder control, may bring up powerful and versatile quantum walk machines for classically intractable problems.

## INTRODUCTION

Quantum walks (QWs), the quantum analog of classical random walks (*1*, *2*), demonstrate remarkably different behaviors compared to classical random walks, due to the superposition of the quantum walker in their path. This very distinct feature leads the QWs to be a stunningly powerful approach to quantum information algorithms (*3*–*7*), and quantum simulation for various systems (*8*–*10*). For instance, theoretical research has revealed that QWs propagating in one dimension have superior transport properties to one-dimensional (1D) classical random walks (*11*), and the coherence in QWs is crucial in simulating energy transport in the photosynthetic process (*9*, *10*). The potential of applying QWs in machine learning algorithms such as artificial neural networks (*6*) also draws wide attention from multidisciplinary researchers. Inspired by the prospects of QWs, many endeavors have been made to realize QWs in different physics systems, including nuclear magnetic resonance (*12*), trapped neutral atoms (*13*), trapped ions (*14*), and photonic systems (*15*–*17*).

However, these experimental implementations reveal a very evident limitation: The realized QW is normally of only one dimension, and the evolving scale of QWs remains very small. A simple demonstration of 1D QW could not suffice the ever-growing demand for further speedup of certain quantum algorithms or the simulation of quantum systems of a much higher complexity (*18*, *19*). In the spatial search algorithm, a QW outperforms its classical counterparts only when the dimension is higher than one (*20*); in the simulation of graphene, photosynthesis, or neural network systems, these complex networks always intuitively have high dimensions. Experimental research on QWs of beyond one dimension becomes indispensable, and a few attempts having covered 2D QWs in experiments are worth noting. A discrete-time 2D QW was achieved in the fiber network system by dynamically controlling the time interval of two walkers (*21*), in the so-called delayed-choice scheme (*22*), or using two walkers sharing coins (*23*). Researchers ingeniously use either time-polarization dimension or the analog from two walkers acting on 1D graph to represent one walker on a 2D lattice, and the 2D lattice does not physically occur. A quasi-2D continuous-time QW was explored in the waveguide coupled in a “Swiss cross” arrangement (*18*), but this is not, strictly speaking, a 2D QW, because photons could not freely propagate in the diagonal and many other directions as they are supposed to do in the 2D array.

Here, for the first time, we, experimentally observe the evolution of 2D continuous-time QWs with single photons on the 2D waveguide array. We set up the heralded single-photon source and measure the evolution results that agree well with theoretical simulation using an ultralow-noise single photon–level imaging technique. We further analyze the transport and recurrent properties, measured from the variance and the probability from the initial waveguide, respectively. We experimentally verify the unique features for 2D QWs that differ from both classical random walks and QWs of one dimension.

## RESULTS

Photons propagating through the coupled waveguide arrays can be described by the Hamiltonian(1)where β_{i} is the propagating constant in waveguide *i*, and *C*_{i,j} is the coupling strength between waveguides *i* and *j*. For a uniform array, all β_{i} is regarded equal to β, and *C*_{i,j}, which mainly depends on waveguide spacing, can be obtained via a coupled mode approach (*24*).

In our implementation, we fabricate 2D waveguide arrays using femtosecond laser writing techniques (Fig. 1A) (*25*). The waveguides are written in different depths of the borosilicate glass to form a 2D array (*26*) from the cross-sectional view (Fig. 1B). The center-to-center spacing between the two nearest waveguides is set as a spacing unit that is 15 μm in the vertical direction (Δ*d*_{V}) and 13.5 μm in the horizontal direction (Δ*d*_{H}). In this 2D array, each waveguide is set into comprehensive coupling with surrounding waveguides, for example, waveguide *O* has different waveguide spacings to waveguides *P*, *Q*, *M*, and *N* as marked in Fig. 1C, namely, Δ*d*_{V}, Δ*d*_{H}, and for Δ*d*_{PO}, Δ*d*_{QO}, Δ*d*_{MO} and Δ*d*_{NO} respectively. These differences in waveguide spacings and waveguide-pair orientations affect the coupling coefficient significantly, as shown in Fig. 1D. Through the measured value of *C* following the standard method (*24*), we observe the exponential decay as waveguide spacing increases and some discrepancy of *C* in different directions. We select Δ*d*_{H} and Δ*d*_{V} to ensure uniform coupling coefficients for the nearest waveguide pairs in the horizontal and vertical directions. For other waveguide pairs in inclined directions, such as pair *M*-*O* and pair *N*-*O* in Fig. 1C, because the directional discrepancy of *C* gets smaller when waveguide spacing increases, we use the average of the horizontal and vertical values at the corresponding spacing for their coupling coefficient.

For a QW that evolves along the waveguide, the propagation length *z* is proportional to the propagation time by *z* = *ct*, where *c* is the speed of light in the waveguide, and thus, for simplicity, all terms that are a function of *t* would use *z* instead in this paper. The wavefunction that evolves from an initial wavefunction satisfies(2)where |Ψ(*z*)〉 = ∑_{j}*a*_{j}(*z*)|*j*〉, and |*a*_{j}(*z*)|^{2} = |〈*j*|Ψ(*z*)||〉^{2} = *P*_{j}(*z*), respectively. |*a*_{j}(*z*)|^{2} or *P*_{j}(*z*) is the probability of the walker (*27*) being found at waveguide *j* at the propagation length *z*. As shown in Fig. 1E, we observe the dynamics by injecting a vertically polarized heralded single-photon source (810 nm) into the central waveguide (*28*) and measuring the evolution patterns using an intensified charge-coupled device (ICCD) camera. More details about our single-photon source and the ultralow-noise single photon–level imaging can be found in Materials and Methods.

These 2D patterns of different propagation lengths from both experimental evolution of heralded single photons and theoretical simulations are then collected (Fig. 2). The intensity peaks always emerge at the diagonal positions, and they move further in these directions when the propagation length *z* increases. The similarity between the two probability distributions Γ_{i,j} and can be defined by (*15*). For the five pairs in Fig. 2, the similarities are calculated as 0.961 (Fig. 2A and F), 0.957 (Fig. 2B and G), 0.920 (Fig. 2C and H), 0.917 (Fig. 2D and I), and 0.913 (Fig. 2E and J), respectively. Therefore, there is a good match between experimental evolution patterns and the theoretical results of 2D QWs.

### The transport properties of QWs

We know QWs have unique transport properties, which could be examined from the variance against the propagation length, as defined in Eq. 3(3)where Δ*l*_{i} is the normalized spacing between waveguide *i* and the central waveguide where the single photons are injected into. Plotting the variance–propagation length relationship with double-logarithmic axes, the ballistic 1D QW is known for yielding a straight line with slope 2, whereas the diffusive 1D classical random walk results in a straight line with slope 1, that is, QW transports quadratically faster than the classical random walk (*29*).

The variance for both 1D QWs in theory and 2D QWs in theory and in experiments is presented in Fig. 3A. All QWs have the same coupling coefficient for waveguide pairs of the nearest spacing, and the walks evolve in a lattice large enough to ignore boundary effects. For 2D QW, the experimental results agree well with the theoretical ones. The variance from 1D QW in theory goes all the way below the 2D case, as a walker can move in more directions in the latter. However, the variance for all these QWs follows the trend of slope 2 rather than slope 1, suggesting the universal ballistic spreading for both 1D and 2D QWs, which distinguishes them from diffusive classical random walks.

Projecting the evolution patterns of a 2D QW and a 2D classical random walk onto the *x* and *y* axes (Fig. 3, B and C), the random walk in a 2D Gaussian distribution (*30*) has the projection profiles of a 1D Gaussian distribution, whereas the projection profiles for the quantum case show a ballistic shape similar to the 1D QWs. It indicates that the intensity peaks in random walks always remain in the center, but those in the QWs always move to all frontiers, causing a larger variance for the latter.

### The recurrent properties of QWs

We further investigate the difference between QWs of different dimensions, which can be gauged by *P*_{0}(*z*) and the Pólya number, two indices that concern the recurrent properties of a walker in a network (*31*, *32*).

*P*_{0}(*z*), the probability of a walker being found at the initial waveguide after a propagation length *z*, is plotted in Fig. 4A. All QWs have a decreasing *P*_{0}(*z*) as *z* increases, but follow different asymptotic lines. A walker in a 2D lattice evolves away from the original site much faster through many additional paths and is less likely to move back (with a smaller oscillation) compared to the 1D scenario.

A system can be judged to be recurrent or transient depending on the Pólya number, through the definition (*31*, *32*)(4)where *z*_{m} is a set of propagation lengths sampled periodically (*32*). When the Pólya number is 1, a system is recurrent, because *P*_{0}(*z*_{m}) can always be a large value to make close to zero, whereas for a transient system, *P*_{0}(*z*_{m}) quickly drops to a very marginal value so the Pólya number would be smaller than 1 (*33*, *34*).

2D QWs in experiment and in theory and 1D QWs in theory show Pólya numbers approaching 0.887, 0.912, and 0.998, respectively (Fig. 4B). The 2D QW is much less inclined to be recurrent than the 1D QW. Further interpretation (*32*) comes from the asymptotic features *z*^{−d}. It has been pointed out that transient systems tend to have a value of *d* larger than 1, whereas *d* for recurrent systems would be equal to or go below 1. From Fig. 4A, the 2D QWs in experiments and theory both follow an asymptotic line *z*^{−2}, revealing the transient nature for these 2D continuous-time QWs in our implementation. We, for the first time, measure the transient nature of a 2D QW in experiments, which makes it different from all experimentally realized QWs that were either in 1D or in 2D with limited scales.

## DISCUSSION

Here, we have demonstrated strong capacity in achieving large-scale 3D photonic chips and ultralow-noise single photon–level imaging techniques that are crucial for the implementation and measurement of our spatial 2D continuous-time QWs. The first and large-scale realization of real spatial 2D QW may not only be fundamentally interesting but also provide a powerful platform for quantum simulation and quantum computing. Because we increase the dimensions by the evolution network geometry, even with a single walker, photon evolution on lattices up to 49 × 49 nodes may lead to a huge state space being large enough to explore new physics in entirely new regimes. Quantum advantage/supremacy may also be explored in such a platform using analog quantum computing protocols, such as 2D Boson sampling (*35*) and fast hitting (*2*) and even universal quantum computing protocols (*36*), instead of using circuit-model protocols of universal quantum computing.

The spatial structure itself can also be freely fabricated with special geometric arrangement, defect, disorder and topological structure in a programmable way, which may offer a new approach of Hamiltonian engineering to enable designing and building quantum simulators on demand on a photonic chip. Such Hamiltonian engineering can be realized by adding waveguide curvature, variation of the fabrication power or dynamic waveguide spacings, etc. Through these methods, we could potentially extend the issue of localization in QWs to higher dimensions (*37*), as well as exploring topological photonics and the simulation of quantum open systems in photonic lattices (*38*).

Furthermore, we could go beyond two dimensions through various ways. Quantum simulations in (2 + 1) dimensions are possible, and their dynamic properties can be explored if we introduce time-varying Hamiltonian equations along the propagating axis. For issues such as QWs in bosonic and fermionic behaviors (*39*), multiparticle entanglement and evolution, etc., the multiphoton source interfaced to the robust and precise photonic chips could give the research of high-dimensional quantum systems an instant boost and demonstrate its strong potential for quantum simulation in a highly complex regime.

## MATERIALS AND METHODS

### Photonic lattice preparation

Waveguide arrays were prepared by steering a femtosecond laser (10 W, 1026 nm; pulse duration, 290 fs; repetition rate, 1 MHz; working frequency, 513 nm) into a spatial light modulator (SLM) to create burst trains onto a borosilicate substrate with a 50× objective lens (numerical aperture, 0.55) at a constant velocity of 10 mm/s. Power and SLM compensation were processed to ensure the waveguides to be uniform and depth-independent (*40*). The borosilicate glass wafer was 1 × 20 × 20 mm in size and consisted of 20 sets of lattices of different evolution lengths from 0.31 to 9.81 mm. Each set of lattice had 49 × 49 waveguides 0.72 mm × 0.648 mm big in the cross-sectional view.

### Single-photon source and imaging

A 405-nm diode laser pumped a PPKTP (periodically poled KTP crystal) to generate pairs of 810 nm via type II spontaneous parametric downconversion. The resulting single-channel count rate and two-channel coincidence count rate reached 510,000 and 120,000, respectively. The generated photon pairs then passed an 810-nm band-pass filter and a polarized beam splitter to be divided to two purified components of horizontal and vertical polarization. The vertically polarized photon was coupled into a single-mode optical fiber and then injected into the photonic chips, whereas the horizontally polarized photon was connected to a single-photon detector that sets a trigger for heralding the vertically polarized photons on the ICCD camera with a time slot of 10 ns. Lacking an external trigger, the measured patterns would come from light in thermal states rather than single-photon states. The ICCD camera captured each evolution pattern from the photon output end of the photonic chip, after accumulating single-photon injections in the “external” mode for around an hour.

### Simulation of light field evolution

Solving Eq. 2 requires a matrix exponential method, and this yields the light evolving pattern that contains the probability matrix for all waveguides. The Pade approximation function (*41*) in MATLAB was used in the simulation. The calculated probability for each waveguide was then treated to be a Gaussian spot with the spot intensity proportional to the probability to visualize the comparison between the theoretical and experimental patterns.

This is an open-access article distributed under the terms of the Creative Commons Attribution-NonCommercial license, which permits use, distribution, and reproduction in any medium, so long as the resultant use is **not** for commercial advantage and provided the original work is properly cited.

## REFERENCES AND NOTES

**Acknowledgments:**We thank J.-W. Pan for the helpful discussions. We also thank the Zhiyuan Innovative Research Center.

**Funding:**This research is supported by the National Key Research and Development Program of China (2017YFA0303700), the National Natural Science Foundation of China (grant nos. 61734005, 11761141014, 11690033, and 11374211), the Innovation Program of Shanghai Municipal Education Commission, Shanghai Science and Technology Development Funds, and the open fund from State Key Laboratory of High Performance Computing (no. 201511-01). X.-M.J. acknowledges support from the National Young 1000 Talents Plan.

**Author contributions:**X.-M.J. conceived and supervised the project. H.T., X.-F.L., and X.-M.J. designed the experiment. H.T., X.-F.L., J.G., and K.S. performed the single-photon experiment. Z.F., J.-Y.C., and L.-F.Q. conducted the theoretical work. C.-Y.W. and P.-C.L. analyzed the experimental data. Z.F., X.-Y.X., Y.W., and A.-L.Y. conducted chip fabrication and parameter optimization. H.T. and X.-M.J. wrote the paper with input from all the other authors.

**Competing interests:**The authors declare that they have no competing interests.

**Data and materials availability:**All data needed to evaluate the conclusions in the paper are present in the paper. Additional data related to this paper may be requested from the authors.

- Copyright © 2018 The Authors, some rights reserved; exclusive licensee American Association for the Advancement of Science. No claim to original U.S. Government Works. Distributed under a Creative Commons Attribution NonCommercial License 4.0 (CC BY-NC).