Since their initial development for studying random motions of microscopic particles (such as those suspended in a fluid), random walks have become a successful model for random processes, and it has been applied in many fields, from computer science to economics. Such processes are random in the sense that, at a particular time, a particle's choice to make a particular step is probabilistic and decided by flipping a coin.

In the quantum analog—the quantum walk^{1}—the walker is, at a given time, in a superposition of possible states, and the possible paths can interfere, exhibiting ballistic propagation with faster dynamics compared to the slow diffusion of classical random walks (see Figure 1). This has prompted applications in quantum-computer science and quantum communication. Indeed, it has been shown that quantum walks are universal for quantum computing. They enable direct simulation of important physical, chemical, and biological systems and the possibility to study very large entangled states of several particles, with the potential to investigate the existence of quantum-classical boundaries.

**Figure 1. **(left) Diffusive propagation of a random walk, compared to (right) ballistic propagation of a continuous-time quantum walk.

Both discrete- and continuous-time quantum walks (DTQW and CTQW) are commonly employed. In a DTQW, the step direction is specified by a coin and a shift operator. These are applied repeatedly, similarly to the classical random walk, but the coin flip is replaced by a quantum-coin operation defining the superposition of the step directions. CTQWs describe tunneling of quantum particles through arrayed potential wells. Quantum walks have been extensively studied theoretically, but only few experimental demonstrations of several steps of single-particle quantum walks using atoms, trapped ions, nuclear magnetic resonance, or photons have been carried out.

Quantum walks are based on wave interference, and they require a stable environment to reduce the noise (decoherence) that would otherwise destroy this interference. Interferometric stability and miniaturization using photonic-waveguide circuits represent a promising approach for quantum-optics experiments, while silica-on-silicon waveguides have been used to demonstrate high-fidelity quantum-information components^{2–4} as well as a small-scale quantum algorithm for prime-number factorization.^{5}

We have implemented CTQWs of photons by designing periodic waveguide arrays in integrated photonic circuits that enable injection of single photons and coupling to single-photon detectors at their output (see Figure 2). We fabricated the chips using the high-refractive-index contrast material, silicon oxynitride, enabling us to quickly stop the coupling between neighboring waveguides, thus allowing a high level of propagation control.

**Figure 2. **Integrated quantum-photonic circuit used to implement a continuous-time quantum walk of two correlated photons.

In contrast to all previous demonstrations (which were restricted to single-particle quantum walks that have exact classical counterparts), we demonstrated the quantum walk of two identical photons that were spatially correlated within an arrayed waveguide. We observed uniquely quantum-mechanical behavior in the two-photon correlations at the array outputs.^{6} We generated pairs of correlated photons in a standard type I spontaneous parametric downconversion process, i.e., a nonlinear process where a 402nm-wavelength continuous-wave laser pumps a χ^{2} nonlinear bismuth borate crystal, generating pairs of photons at a wavelength of 804nm through conservation of energy and momentum. The correlated photons were coupled to the waveguide using fiber arrays, and we recorded the correlations at the output by measuring two-photon-coincidence events with a detection system consisting of 12 avalanche single-photon detectors and three programmable counting boards. The measured correlations fit our simulations very well.

We have shown that the results strongly depend on the input state and that these correlations violate classical limits by 76 standard deviations, proving that such phenomena cannot be described using classical theory. This generalized form of quantum interference is similar to the Hong-Ou-Mandel dip effect in an optical beam splitter, but in our case it occurs in a 21-mode system. Antibunching of correlated photons reduces the probability of detecting two photons on opposite sides of the array, while enhancing the case of two particles on the same side.

Such two-particle quantum walks have already been identified as a powerful computational tool for solving important problems, such as graph isomorphism, and provide a direct route to powerful quantum simulations. Implementing new algorithms based on quantum walks will require integration of single-photon sources and detectors. These have already been shown to be compatible with integration, reducing coupling losses and considerably improving overall performance. Reconfigurability and feedback will provide further tools, enabling performance of more challenging and interesting tasks. Random walks are extremely successful tools that are employed in many scientific fields, and their quantum analogs promise to be similarly powerful. We are now focusing on their applications.

*This work was supported by the UK's Engineering and Physical Sciences Research Council, the European Research Council, the European Commission's Seventh Framework Programme project ‘Quantum Integrated Photonics’ (QUANTIP), the quantum-information-processing interdisciplinary research collaboration, the Intelligence Advanced Research Projects Activity (IARPA), the Leverhulme Trust, and the Centre for NanoScience and Quantum Information at the University of Bristol (UK). Jeremy O'Brien acknowledges a Royal Society Wolfson Research Merit Award.*

Alberto Peruzzo, Jeremy O'Brien

Centre for Quantum Photonics (CQP)

University of Bristol

Bristol, UK

Alberto Peruzzo is a PhD student in physics. He received a Laurea degree in computer engineering from the University of Padova (Italy) in 2008.

Jeremy O'Brien is professor of physics and electrical engineering, and leads the CQP. He received his PhD in physics from the University of New South Wales (Australia) in 2002 for experimental work on correlated and confined electrons in organic conductors, superconductors, and semiconductor nanostructures, as well as progress towards fabrication of phosphorus in a silicon quantum computer. As a research fellow at the University of Queensland (Australia, 2001–2006), he worked on quantum optics and quantum-information science with single photons. CQP's efforts focus on the fundamental and applied quantum mechanics at the heart of quantum-information science and technology, ranging from prototypes for scalable quantum computing to generalized quantum measurements, control, and metrology.

References:

4.

A. Laing, A. Peruzzo, A. Politi, M. Rodas Verde, M. Halder, T. C. Ralph, M. G. Thompson, J. L. O'Brien, High-fidelity operation of quantum photonic circuits, *Quant. Phys*., arXiv:1004.0326v2. Electronic preprint.

6.

A. Peruzzo, M. Lobino, J. C. F. Matthews, N. Matsuda, A. Politi, K. Poulios, X.-Q. Zhou, Y. Lahini, N. Ismail, K. Wörhoff, Y. Bromberg, Y. Silberberg, M. G. Thompson, J. L. O'Brien, Quantum walks of correlated photons, *Science* 329, pp. 1500-1503, 2010. doi:10.1126/science.1193515