Statistics

Database

Scalability

Quantum

Physics

Quantum walk

Mathematics

Quantum algorithm

Quantum network

Quantum mechanics

Random walk

Computer science

Quantum computer

Nature Photonics

Quantum walks are powerful kernels in quantum computing protocols, and possess strong capabilities in speeding up various simulation and optimization tasks. One striking example is provided by quantum walkers evolving on glued trees1, which demonstrate faster hitting performances than classical random walks. However, their experimental implementation is challenging, as this involves highly complex arrangements of an exponentially increasing number of nodes. Here, we propose an alternative structure with a polynomially increasing number of nodes. We successfully map such graphs on quantum photonic chips using femtosecond-laser direct writing techniques in a geometrically scalable fashion. We experimentally demonstrate quantum fast hitting by implementing two-dimensional quantum walks on graphs with up to 160 nodes and a depth of eight layers, achieving a linear relationship between the optimal hitting time and the network depth. Our results open up a scalable path towards quantum speed-up in classically intractable complex problems. A quantum walker on a hexagonal glued array of optical waveguides is made inside a glass substrate. The optimal hitting time increases linearly with the layer depth, giving a quadratic speed-up over the hitting performance by classical random walks.

Experimental quantum fast hitting on hexagonal graphs