Efficient quantum walk on a quantum processor

Xiaogang Qiang, Thomas Loke, Ashley Montanaro, Kanin Aungskunsiri, Xiao-Qi Zhou, Jeremy O'Brien, Jingbo Wang, Jonathan Matthews

Research output: Contribution to journalArticle (Academic Journal)peer-review

34 Citations (Scopus)
370 Downloads (Pure)

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.

Original languageEnglish
Article number11511
Number of pages6
JournalNature Communications
Volume7
DOIs
Publication statusPublished - 5 May 2016
EventPhoton 16 - University of Leeds, Leeds, United Kingdom
Duration: 5 Sep 20168 Sep 2016

Structured keywords

  • Bristol Quantum Information Institute

Fingerprint Dive into the research topics of 'Efficient quantum walk on a quantum processor'. Together they form a unique fingerprint.

Cite this