Projects per year
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 language | English |
---|---|
Article number | 11511 |
Number of pages | 6 |
Journal | Nature Communications |
Volume | 7 |
DOIs | |
Publication status | Published - 5 May 2016 |
Event | Photon 16 - University of Leeds, Leeds, United Kingdom Duration: 5 Sept 2016 → 8 Sept 2016 |
Research Groups and Themes
- Bristol Quantum Information Institute
- QETLabs
Fingerprint
Dive into the research topics of 'Efficient quantum walk on a quantum processor'. Together they form a unique fingerprint.Projects
- 11 Finished
-
8031 EPSRC EP/M024385/1 -PHYS RB1771
Matthews, J. C. F. (Principal Investigator)
1/04/15 → 30/03/20
Project: Research
-
Practical Photonic Quantum-Enhanced Sensors
Matthews, J. C. F. (Principal Investigator)
1/04/15 → 31/03/20
Project: Research
-
New insights in quantum algorithms and complexity
Montanaro, A. M. R. (Principal Investigator)
31/07/14 → 30/07/19
Project: Research
Profiles
-
Professor Ashley M R Montanaro
- School of Mathematics - Professor of Quantum Computation
- Algorithms and Complexity
- Mathematical Physics
- Quantum Information Theory
Person: Academic , Member, Group lead