title: Efficient quantum walk on a quantum processor.
abstract: The random walk formalism is used across a wide range of applications, from modelling share prices to predicting population genetics. Likewise, quantum walks have shown much potential as a framework for developing new quantum algorithms. Here we present explicit efficient quantum circuits for implementing continuous-time quantum walks on the circulant class of graphs. These circuits allow us to sample from the output probability distributions of quantum walks on circulant graphs efficiently. We also show that solving the same sampling problem for arbitrary circulant quantum circuits is intractable for a classical computer, assuming conjectures from computational complexity theory. This is a new link between continuous-time quantum walks and computational complexity theory and it indicates a family of tasks that could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle, we experimentally implement the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor.
authors.affiliation: Centre for Quantum Photonics, H.H. Wills Physics Laboratory and Department of Electrical and Electronic Engineering, University of Bristol, Bristol BS8 1UB, UK.
authors.forename: Xiaogang
authors.initials: X
authors.lastname: Qiang
authors.affiliation: School of Physics, The University of Western Australia, Crawley, WA 6009, Australia.
authors.forename: Thomas
authors.initials: T
authors.lastname: Loke
authors.affiliation: School of Mathematics, University of Bristol, Bristol BS8 1TW, UK.
authors.forename: Ashley
authors.initials: A
authors.lastname: Montanaro
authors.affiliation: Centre for Quantum Photonics, H.H. Wills Physics Laboratory and Department of Electrical and Electronic Engineering, University of Bristol, Bristol BS8 1UB, UK.
authors.forename: Kanin
authors.initials: K
authors.lastname: Aungskunsiri
authors.affiliation: Centre for Quantum Photonics, H.H. Wills Physics Laboratory and Department of Electrical and Electronic Engineering, University of Bristol, Bristol BS8 1UB, UK.|State Key Laboratory of Optoelectronic Materials and Technologies and School of Physics, Sun Yat-sen University, Guangzhou 510275, China.
authors.forename: Xiaoqi
authors.initials: X
authors.lastname: Zhou
authors.affiliation: Centre for Quantum Photonics, H.H. Wills Physics Laboratory and Department of Electrical and Electronic Engineering, University of Bristol, Bristol BS8 1UB, UK.
authors.forename: Jeremy L
authors.initials: JL
authors.lastname: O'Brien
authors.affiliation: School of Physics, The University of Western Australia, Crawley, WA 6009, Australia.
authors.forename: Jingbo B
authors.initials: JB
authors.lastname: Wang
authors.affiliation: Centre for Quantum Photonics, H.H. Wills Physics Laboratory and Department of Electrical and Electronic Engineering, University of Bristol, Bristol BS8 1UB, UK.
authors.forename: Jonathan C F
authors.initials: JCF
authors.lastname: Matthews