Experimental quantum fast hitting on hexagonal graphs
File(s)nature-photonics _fast_hitting.pdf (155.44 KB)
Accepted version
Author(s)
Type
Journal Article
Abstract
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.
Date Issued
2018-12-01
Date Acceptance
2018-09-26
Citation
Nature Photonics, 2018, 12 (12), pp.754-758
ISSN
1749-4885
Publisher
Springer Nature
Start Page
754
End Page
758
Journal / Book Title
Nature Photonics
Volume
12
Issue
12
Copyright Statement
© 2018 The Author(s), under exclusive licence to Springer Nature Limited.
Sponsor
Engineering & Physical Science Research Council (E
The Royal Society
Samsung Electronics Co. Ltd
Korea Institute of Science and Technology
Grant Number
EP/K034480/1
WM140063
N/A
n/a
Subjects
Science & Technology
Physical Sciences
Optics
Physics, Applied
Physics
WALK
quant-ph
quant-ph
physics.optics
Optoelectronics & Photonics
01 Mathematical Sciences
02 Physical Sciences
Publication Status
Published
Date Publish Online
2018-10-29