Universal Computation by Multiparticle Quantum Walk
Open accessAbstract
Computing Power of Quantum Mechanics: There is much interest in developing quantum computers in order to perform certain tasks much faster than, or that are intractable for, a classical computer. A general quantum computer, however, requires the fabrication and operation a number of quantum logic devices (see the Perspective by Franson ). Broome et al. (p. 794 , published online 20 December) and Spring et al. (p. 798 , published online 20 December) describe experiments in which single photons and quantum interference were used to perform a calculation (the permanent of a matrix) that is very difficult on a classical computer. Similar to random walks, quantum walks on a graph describe the movement of a walker on a set of predetermined paths; instead of flipping a coin to decide which way to go at each point, a quantum walker can take several paths at once. Childs et al. (p. 791 ) propose an architecture for a quantum computer, based on quantum walks of multiple interacting walkers. The system is capable of performing any quantum operation using a subset of its nodes, with the size of the subset scaling favorably with the complexity of the operation.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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?
Quantum walks lie at the core of simulating condensed matter systems, quantum-enhanced search algorithms, and universal models of quantum computation.
“This simple phenomenon lies at the core of simulating condensed matter systems, quantum-enhanced search algorithms, and universal models of quantum computation (1, 2).”
From Two-photon quantum walk in a multimode fiber (2016) · cites this paper as [1]
Cites
Universal Computation by Quantum Walk
Childs, A. M. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.180501 · Cited by 1,002 · see citing works
Self-citationQuantum Walks of Correlated Photons
Peruzzo, A., Lobino, M., Matthews, J. C. F., Matsuda, N., Politi, A., Poulios, K., Zhou, X.-Q., Lahini, Y., Ismail, N., Wörhoff, K., et al. (2010) · Science · doi:10.1126/science.1193515 · Cited by 929 · see citing works
Exponential algorithmic speedup by a quantum walk
Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780552 · Cited by 825 · see citing works
Self-citationTwo-Particle Bosonic-Fermionic Quantum Walk via Integrated Photonics
Sansoni, L., Sciarrino, F., Vallone, G., Mataloni, P., Crespi, A., Ramponi, R., & Osellame, R. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.010502 · Cited by 578 · see citing works
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., & Watrous, J. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380757 · Cited by 562 · see citing works
On the Relationship Between Continuous- and Discrete-Time Quantum Walk
Childs, A. M. (2010) · Communications in Mathematical Physics · doi:10.1007/s00220-009-0930-1 · Cited by 411 · see citing works
Self-citationAdiabatic quantum state generation and statistical zero knowledge
Aharonov, D., & Ta-Shma, A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780546 · Cited by 322 · see citing works
Quantum and Classical Correlations in Waveguide Lattices
Bromberg, Y., Lahini, Y., Morandotti, R., & Silberberg, Y. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.253904 · Cited by 318 · cited 1× · see citing works
“Recently, there has been considerable interest in experimentally implementing multi-particle quantum walk [4, 10, 11, 12] and these experiments can be viewed as first steps toward implementing our construction.”
BackgroundQuantum walk on a line with two entangled particles
Omar, Y., Paunković, N., Sheridan, L., & Bose, S. (2006) · Physical Review A · doi:10.1103/physreva.74.042304 · Cited by 149 · see citing works
Two-photon quantum walks in an elliptical direct-write waveguide array
Owens, J. O., Broome, M. A., Biggerstaff, D. N., Goggin, M. E., Fedrizzi, A., Linjordet, T., Ams, M., Marshall, G. D., Twamley, J., Withford, M. J., et al. (2011) · New Journal of Physics · doi:10.1088/1367-2630/13/7/075003 · Cited by 135 · cited 1× · see citing works
“Recently, there has been considerable interest in experimentally implementing multi-particle quantum walk [4, 10, 11, 12] and these experiments can be viewed as first steps toward implementing our construction.”
BackgroundExperimental realization of a quantum quincunx by use of linear optical elements
Do, B., Stohler, M. L., Balasubramanian, S., Elliott, D. S., Eash, C., Fischbach, E., Fischbach, M. A., Mills, A., & Zwickl, B. (2005) · Journal of the Optical Society of America B · doi:10.1364/josab.22.000499 · Cited by 128 · see citing works
Quantum random walk of two photons in separable and entangled states
Pathak, P. K., & Agarwal, G. S. (2007) · Physical Review A · doi:10.1103/physreva.75.032351 · Cited by 83 · see citing works
Rohde, P. P., Schreiber, A., Štefaňák, M., Jex, I., & Silberhorn, C. (2011) · New Journal of Physics · doi:10.1088/1367-2630/13/1/013001 · Cited by 81 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Observation of topological edge states in parity–time-symmetric quantum walks
Xiao, L., Zhan, X., Bian, Z. H., Wang, K. K., Zhang, X., Wang, X. P., Li, J., Mochizuki, K., Kim, D., Kawakami, N., et al. (2017) · Nature Physics · doi:10.1038/nphys4204 · Cited by 576 · see citing works
Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
Gong, M., Wang, S., Zha, C., Chen, M.-C., Huang, H.-L., Wu, Y., Zhu, Q., Zhao, Y., Li, S., Guo, S., et al. (2021) · Science · doi:10.1126/science.abg7812 · Cited by 331 · see citing works
Two-photon quantum walk in a multimode fiber
Defienne, H., Barbieri, M., Walmsley, I. A., Smith, B. J., & Gigan, S. (2016) · Science Advances · doi:10.1126/sciadv.1501054 · Cited by 168 · see citing works
Quantum Walks of Correlated Photon Pairs in Two-Dimensional Waveguide Arrays
Poulios, K., Keil, R., Fry, D., Meinecke, J. D. A., Matthews, J. C. F., Politi, A., Lobino, M., Gräfe, M., Heinrich, M., Nolte, S., et al. (2014) · Physical Review Letters · doi:10.1103/physrevlett.112.143604 · Cited by 148 · see citing works
Fast escape of a quantum walker from an integrated photonic maze
Caruso, F., Crespi, A., Ciriolo, A. G., Sciarrino, F., & Osellame, R. (2016) · Nature Communications · doi:10.1038/ncomms11682 · Cited by 105 · see citing works
Providing End-to-End Security Using Quantum Walks in IoT Networks
El-Latif, A. A. A., Abd-El-Atty, B., Venegas-Andraca, S. E., Elwahsh, H., Piran, M. J., Bashir, A. K., Song, O.-Y., & Mazurczyk, W. (2020) · IEEE Access · doi:10.1109/access.2020.2992820 · Cited by 89 · see citing works
Lu, D., Biamonte, J. D., Li, J., Li, H., Johnson, T. H., Bergholm, V., Faccin, M., Zimborás, Z., Laflamme, R., Baugh, J., et al. (2016) · Physical Review A · doi:10.1103/physreva.93.042302 · Cited by 58 · see citing works
Universally optimal noisy quantum walks on complex networks
Caruso, F. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/5/055015 · Cited by 54 · see citing works
A quantum walk-assisted approximate algorithm for bounded NP optimisation problems
Marsh, S., & Wang, J. B. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2171-3 · Cited by 50 · see citing works
Quantum walks of two correlated photons in a 2D synthetic lattice
Esposito, C., Barros, M. R., Durán Hernández, A., Carvacho, G., Di Colandrea, F., Barboza, R., Cardano, F., Spagnolo, N., Marrucci, L., & Sciarrino, F. (2022) · npj Quantum Information · doi:10.1038/s41534-022-00544-0 · Cited by 36 · see citing works
Integrated photonic quantum walks
Gräfe, M., & Szameit, A. (2020) · Journal of Physics B: Atomic, Molecular and Optical Physics · doi:10.1088/1361-6455/ab6cfc · Cited by 28 · see citing works
“Since then, QWs have found applications as the fundamental concept behind Groverʼs search algorithm [9] or universal quantum computing [10, 11].”
BackgroundQuantum Google algorithm: Construction and application to complex networks
Paparo, G. D., Müller, M., Comellas, F., & Martin-Delgado, M. A. (2014) · The European Physical Journal Plus · doi:10.1140/epjp/i2014-14150-y · Cited by 17 · see citing works
Multi-particle quantum walks on 3D integrated photonic chip
Zhou, W.-H., Wang, X.-W., Ren, R.-J., Fu, Y.-X., Chang, Y.-J., Xu, X.-Y., Tang, H., & Jin, X.-M. (2024) · Light: Science & Applications · doi:10.1038/s41377-024-01627-7 · Cited by 16 · see citing works
Irreconcilable difference between quantum walks and adiabatic quantum computing
Wong, T. G., & Meyer, D. A. (2016) · Physical Review A · doi:10.1103/physreva.93.062313 · Cited by 13 · see citing works
Experimental realization of quantum walks near synthetic horizons on photonic lattices
He, R., Zhao, Y., Sheng, C., Duan, J., Wei, Y., Sun, C., Lu, L., Gong, Y.-X., Zhu, S., & Liu, H. (2024) · Physical Review Research · doi:10.1103/physrevresearch.6.013233 · Cited by 5 · see citing works
- Authors
- Childs, A. M., Gosset, D., & Webb, Z.
- Affiliations
- University of Waterloo (CA)
- Corresponding author
- Gosset, David
- Venue
- Science
- Published
- 2013-02-15
- Volume
- 339
- Issue
- 6121
- Pages
- 791-794
- ISSN
- 0036-8075 (ISSN-L)
- 1095-9203
- OpenAlex
- W2161027938
- Cited by
- 456
- References
- 13
- Citations by year
- 2026: 18 · 2025: 35 · 2024: 43 · 2023: 40 · 2022: 36 · 2021: 34 · 2020: 44 · 2019: 47 · 2018: 34 · 2017: 25 · 2016: 35 · 2015: 25 · 2014: 27 · 2013: 11 · 2012: 1
- FWCI
- 36.13
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Science (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- 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
- universal computation, quantum computing, quantum walks, quantum interference, permanent, single photons, quantum gates
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
