CoChat
Sign Up
Cited by 108Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum Mechanics and Applications

Efficient quantum walk on a quantum processor

Open access
Qiang, Xiaogang, Loke, Thomas, Montanaro, Ashley, Aungskunsiri, Kanin, Zhou, Xiaoqi, O’Brien, Jeremy L., Wang, Jingbo B., Matthews, Jonathan C. F.·2016·Nature Communications
DOI 10.1038/ncomms11511PMC PMC4858748
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/ncomms11511

Cites

8 of 8 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The circuit-based implementations reported to date are a DQW on a three-qubit NMR system, a CQW on a two-qubit photonic processor, and a split-step QW on superconducting circuits.

    “The implementation of a DQW on a three-qubit NMR system36, a CQW on a two-qubit photonic processor37 and a split-step QW on superconducting circuits38,39 are the circuit-based implementations reported to date.”

    From Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer (2020) · cites this paper as [37]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 38

  1. Farhi E. & Gutmann S. Quantum computation and decision trees. Phys. Rev. A 58, 915 (1998).
  2. Childs A. M., Gosset D. & Webb Z. Universal computation by multiparticle quantum walk. Science 339, 791– 794 (2013). 23413349
  3. Childs A. M. & Goldstone J. Spatial search by quantum walk. Phys. Rev. A 70, 022314 (2004).
  4. Douglas B. L. & Wang J. B. A classical approach to the graph isomorphism problem using quantum walks. J. Phys. A 41, 075303 (2008).
  5. Gamble J. K., Friesen M., Zhou D., Joynt R. & Coppersmith S. N. Two-particle quantum walks applied to the graph isomorphism problem. Phys. Rev. A 81, 052313 (2010).
  6. Berry S. D. & Wang J. B. Two-particle quantum walks: entanglement and graph isomorphism testing. Phys. Rev. A 83, 042317 (2011).
  7. Berry S. D. & Wang J. B. Quantum-walk-based search and centrality. Phys. Rev. A 82, 042333 (2010).
  8. Sánchez-Burillo E., Duch J., Gómez-Gardeñes J. & Zueco D. Quantum navigation and ranking in complex networks. Sci. Rep. 2, 605 (2012). 22930671 PMC3428603
  9. Schreiber A.. A 2D quantum walk simulation of two-particle dynamics. Science 336, 55– 58 (2012). 22403179
  10. Rebentrost P.. Environment-assisted quantum transport. New J. Phys. 11, 033003 (2009).
  11. Du J.. Experimental implementation of the quantum random-walk algorithm. Phys. Rev. A 67, 042316 (2003).
  12. Ryan C. A.. Experimental implementation of a discrete-time quantum random walk on an NMR quantum-information processor. Phys. Rev. A 72, 062317 (2005).
  13. Xue P., Sanders B. C. & Leibfried D. Quantum walk on a line for a trapped ion. Phys. Rev. Lett. 103, 183602 (2009). 19905805
  14. Schmitz H.. Quantum walk of a trapped ion in phase space. Phys. Rev. Lett. 103, 090504 (2009). 19792773
  15. Zähringer F.. Realization of a quantum walk with one and two trapped ions. Phys. Rev. Lett. 104, 100503 (2010). 20366407
  16. Karski M.. Quantum walk in position space with single optically trapped atoms. Science 325, 174– 177 (2009). 19589996
  17. Perets H. B.. Realization of quantum walks with negligible decoherence in waveguide lattices. Phys. Rev. Lett. 100, 170506 (2008). 18518267
  18. Carolan J.. On the experimental verification of quantum complexity in linear optics. Nat. Photon. 8, 621 (2014).
  19. Manouchehri K. & Wang J. B. Physical Implementation of Quantum Walks Springer-Verlag (2014).
  20. Aharonov D. & Ta-Shma A. in Proceedings of the 35th Annual ACM Symposium on Theory of Computing 20–29 (ACM, New York, NY, USA, 2003).
  21. Ng M. K. Iterative Methods for Toeplitz Systems Oxford Univ. Press (2004).
  22. Gray R. M. Toeplitz and Circulant Matrices: A Review Now Publishers Inc. (2006).
  23. Buhrman H., Cleve R., Watrous J. & De Wolf R. Quantum fingerprinting. Phys. Rev. Lett. 87, 167902 (2001). 11690244
  24. Han D.. Folding and cutting DNA into reconfigurable topological nanostructures. Nat. Nanotechnol. 5, 712– 717 (2010). 20890274 PMC3071358
  25. Peres A. Stability of quantum motion in chaotic and regular systems. Phys. Rev. A 30, 1610 (1984).
  26. Prosen T. & Znidaric M. Stability of quantum motion and correlation decay. J. Phys. A Math. Gen. 35, 1455 (2002).
  27. Aaronson S. & Arkhipov A. in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing 333-342 (ACM Press, New York, NY, USA, 2011).
  28. Bremner M. J., Montanaro A. & Shepherd D. J. Average-case complexity versus approximate simulation of commuting quantum computations. Preprint at http://arxiv.org/abs/1504.07999 (2015). 27588839 · arXiv
  29. Nielsen N. A. & Chuang I. L. Quantum Computation and Quantum Information Cambridge Univ. Press (2010).
  30. Childs A. M. Quantum Information Processing in Continuous Time (PhD thesis, Massachusetts Institute of Technology (2004).
  31. Zhou X. Q.. Adding control to arbitrary unknown quantum operations. Nat. Commun. 2, 413 (2011). 21811242 PMC3267055
  32. Shepherd D. & Bremner M. J. Temporally unstructured quantum computation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 465, 1413– 1439 (2009).
  33. Fujii K. & Morimae T. Quantum commuting circuits and complexity of Ising partition functions. Preprint at http://arxiv.org/abs/1311.2128 (2013). · arXiv
  34. Goldberg L. A. & Guo H. The complexity of approximating complex-valued Ising and Tutte partition functions. Preprint at http://arxiv.org/abs/1409.5627 (2014). · arXiv
  35. Papadimitriou C. Computational Complexity Addison-Wesley (1994).
  36. Schwarz M. & Nest M. Simulating quantum circuits with sparse output distributions. Preprint at http://arxiv.org/abs/1310.6749 (2013). · arXiv
  37. Rohde P. P. & Ralph T. C. Error tolerance of the boson-sampling model for linear optics quantum computing. Phys. Rev. A 85, 022332 (2012).
  38. Rangarajan R., Goggin M. & Kwiat P. Optimizing type-I polarization-entangled photons. Opt. Express 17, 18920– 18933 (2009). 20372627

Cited by

Sorted by citations

Authors
Qiang, X., Loke, T., Montanaro, A., Aungskunsiri, K., Zhou, X., O’Brien, J. L., Wang, J. B., & Matthews, J. C. F.
Affiliations
  • University of Bristol (GB)
  • The University of Western Australia (AU)
  • Sun Yat-sen University (CN)
Corresponding author
  • Wang, Jingbo B.
  • Matthews, Jonathan C. F.
ORCID
Venue
Nature Communications
Publisher
Springer Science and Business Media LLC
Published
2016-05-05
Volume
7
Issue
1
Pages
11511-11511
ISSN
2041-1723 (ISSN-L)
DOI
10.1038/ncomms11511
PMC
PMC4858748
OpenAlex
W1872062004
Cited by
108
References
8
Citations by year
2026: 4 · 2025: 11 · 2024: 12 · 2023: 20 · 2022: 13 · 2021: 11 · 2020: 11 · 2019: 10 · 2018: 6 · 2017: 7 · 2016: 3
FWCI
7.14
Type
journal article
Language
en
Open access
Licence
Locations
  • Nature Communications (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • UWA Profiles and Research Repository (UWA) (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • RePEc: Research Papers in Economics (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • Explore Bristol Research (submittedVersion, cc-by)
  • Bristol Research (University of Bristol) (submittedVersion, cc-by)
  • arXiv (Cornell University)
Funders
  • Leverhulme Trust
  • Royal Academy of Engineering
  • University of Bristol
  • China Scholarship Council
  • Horizon 2020 Framework Programme
  • Engineering and Physical Sciences Research Council (EP/L021005/1, EP/M024385/1, EP/J017175/1, H2020, EP/L024020/1, EP/K021931/1, EP/I035935/1)
  • Army Research Office (W911NF-14-1, W911NF-14-1-0133, W911NF)
  • FP7 People: Marie-Curie Actions (FP7-PEOPLE-2013-ITN, FP7-PEOPLE-2013)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
Keywords
continuous-time quantum walks, circulant graphs, quantum circuits, quantum sampling, quantum advantage, computational complexity, quantum algorithms

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review