Efficient quantum walk on a quantum processor

Xiaogang Qiang, Thomas Loke, Ashley Montanaro, Kanin Aungskunsiri, Xiaoqi Zhou, Jeremy L. O’Brien, Jingbo B. Wang () and Jonathan C. F. Matthews ()
Additional contact information
Xiaogang Qiang: Centre for Quantum Photonics, University of Bristol
Thomas Loke: School of Physics, The University of Western Australia
Ashley Montanaro: School of Mathematics, University of Bristol
Kanin Aungskunsiri: Centre for Quantum Photonics, University of Bristol
Xiaoqi Zhou: Centre for Quantum Photonics, University of Bristol
Jeremy L. O’Brien: Centre for Quantum Photonics, University of Bristol
Jingbo B. Wang: School of Physics, The University of Western Australia
Jonathan C. F. Matthews: Centre for Quantum Photonics, University of Bristol

Nature Communications, 2016, vol. 7, issue 1, 1-6

Abstract: 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.

Date: 2016
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/ncomms11511 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:7:y:2016:i:1:d:10.1038_ncomms11511

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/ncomms11511

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().