Efficient quantum walk on a quantum processor
| Autor: | Jonathan C. F. Matthews, Xiaogang Qiang, Ashley Montanaro, Xiao-Qi Zhou, Jingbo Wang, Jeremy L. O'Brien, Kanin Aungskunsiri, T. Loke |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Computer science
Science FOS: Physical sciences General Physics and Astronomy Topology Bristol Quantum Information Institute 01 natural sciences Article General Biochemistry Genetics and Molecular Biology 010305 fluids & plasmas QETLabs Open quantum system Computer Science::Emerging Technologies Quantum error correction 0103 physical sciences Quantum operation Quantum walk Quantum information 010306 general physics Quantum Physics Quantum network Multidisciplinary TheoryofComputation_GENERAL General Chemistry ComputerSystemsOrganization_MISCELLANEOUS Quantum process Quantum algorithm Quantum Physics (quant-ph) |
| Zdroj: | Nature Communications Nature Communications, Vol 7, Iss 1, Pp 1-6 (2016) Qiang, X, Loke, T, Montanaro, A, Aungskunsiri, K, Zhou, X-Q, O'Brien, J, Wang, J & Matthews, J 2016, ' Efficient quantum walk on a quantum processor ', Nature Communications, vol. 7, 11511 . https://doi.org/10.1038/ncomms11511 |
| ISSN: | 2041-1723 |
| Popis: | 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 frame- work for developing new quantum algorithms. In this paper, 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 which could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle we have experimentally implemented the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor. 10 pages, 5 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|