Quantum Walks on Arbitrary Spatial Networks with Rydberg Atoms
1Instituto Superior Técnico, Universidade de Lisboa, Portugal
2PQI – Portuguese Quantum Institute, Portugal
3Eindhoven University of Technology, Netherlands
4University of Strathclyde, Scotland, United Kingdom
5Physics of Information and Quantum Technologies Group, Centro de Física e Engenharia de Materiais Avançados (CeFEMA), Portugal
| Published: | 2026-10-13, volume 10, page 2235 |
| Editor: | Tommaso Macrì |
| Eprint: | arXiv:2507.21011v2 |
| Doi: | https://doi.org/10.22331/q-2026-10-13-2235 |
| Citation: | Quantum 10, 2235 (2026). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Rydberg atoms provide a highly promising platform for quantum computation, leveraging their strong tunable interactions to encode and manipulate information in the electronic states of individual atoms. Key advantages of Rydberg atoms include scalability, reconfigurable connectivity, and native multi-qubit gates, making them particularly well-suited for addressing complex network problems. These problems can often be framed as graph-based tasks, which can be efficiently addressed using quantum walks. In this work, we propose a general implementation of staggered quantum walks with Rydberg atoms, with a particular focus on spatial networks. We also present an efficient algorithm for constructing the tessellations required for the staggered quantum walk. Finally, we demonstrate that our proposal achieves performance consistent with a quadratic speedup in spatial search algorithms.

Featured image: Proposed implementation of a staggered quantum walk. Each vertex of the spatial network is encoded in a single atom and for each tessellation ($\alpha, \beta, \dots$), the walk operator is diagonalized on each clique with local interactions (colored spots).
Popular summary
Our proposal takes advantage of the unique features of Rydberg atom platforms, which can dynamically reconfigure how qubits are connected during the computation. This allows us to tailor the quantum walk to the specific structure of a given network. As a benchmark, we tested our method on a search problem and showed that the quantum walk can find a target node faster than any classical method, and that this speedup is the best that quantum mechanics allows.
This work brings quantum walks closer to practical use in solving meaningful network problems. Looking ahead, it opens the door to both quantum hardware and novel quantum algorithms tackling more realistic and complex networks, with potential applications in optimization, materials science and biology.
► BibTeX data
► References
[1] Albert-László Barabási and Márton Pósfai. ``Network science''. Volume 3. Cambridge University Press. (2016).
https://doi.org/10.1098/rsta.2012.0375
[2] Santo Fortunato. ``Community detection in graphs''. Physics Reports 486, 75–174 (2010).
https://doi.org/10.1016/j.physrep.2009.11.002
[3] Bogdan Danila, Yong Yu, John A. Marsh, and Kevin E. Bassler. ``Optimal transport on complex networks''. Phys. Rev. E 74, 046106 (2006).
https://doi.org/10.1103/PhysRevE.74.046106
[4] Gang Yan, Tao Zhou, Bo Hu, Zhong-Qian Fu, and Bing-Hong Wang. ``Efficient routing on complex networks''. Phys. Rev. E 73, 046108 (2006).
https://doi.org/10.1103/PhysRevE.73.046108
[5] Yamir Moreno, Maziar Nekovee, and Amalio F. Pacheco. ``Dynamics of rumor spreading in complex networks''. Phys. Rev. E 69, 066130 (2004).
https://doi.org/10.1103/PhysRevE.69.066130
[6] M. Morgado and S. Whitlock. ``Quantum simulation and computing with Rydberg-interacting qubits''. AVS Quantum Science 3, 023501 (2021).
https://doi.org/10.1116/5.0036562
[7] K McInroy, N Pearson, and JD Pritchard. ``Benchmarking the algorithmic performance of near-term neutral atom processors'' (2024). url: https://doi.org/10.48550/arXiv.2402.02127.
https://doi.org/10.48550/arXiv.2402.02127
[8] Nishad Maskara, Stefan Ostermann, James Shee, Marcin Kalinowski, Abigail McClain Gomez, Rodrigo Araiza Bravo, Derek S Wang, Anna I Krylov, Norman Y Yao, Martin Head-Gordon, et al. ``Programmable simulations of molecules and materials with reconfigurable quantum processors''. Nature Physics 21, 289–297 (2025).
https://doi.org/10.1038/s41567-024-02738-z
[9] S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletić, and M. D. Lukin. ``Quantum optimization of maximum independent set using Rydberg atom arrays''. Science 376, 1209–1215 (2022).
https://doi.org/10.1126/science.abo6587
[10] Minhyuk Kim, Kangheun Kim, Jaeyong Hwang, Eun-Gook Moon, and Jaewook Ahn. ``Rydberg quantum wires for maximum independent set problems''. Nature Physics 18, 755–759 (2022).
https://doi.org/10.1038/s41567-022-01629-5
[11] Seokho Jeong, Minhyuk Kim, Minki Hhan, JuYoung Park, and Jaewook Ahn. ``Quantum programming of the satisfiability problem with Rydberg atom graphs''. Phys. Rev. Res. 5, 043037 (2023).
https://doi.org/10.1103/PhysRevResearch.5.043037
[12] Aaron W. Young, William J. Eckner, Nathan Schine, Andrew M. Childs, and Adam M. Kaufman. ``Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice''. Science 377, 885–889 (2022).
https://doi.org/10.1126/science.abo0608
[13] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. ``Quantum approximate optimization of non-planar graph problems on a planar superconducting processor''. Nature Physics 17, 332–336 (2021).
https://doi.org/10.1038/s41567-020-01105-y
[14] Yingyue Zhu, Zewen Zhang, Bhuvanesh Sundar, Alaina M Green, C Huerta Alderete, Nhung H Nguyen, Kaden RA Hazzard, and Norbert M Linke. ``Multi-round QAOA and advanced mixers on a trapped-ion quantum computer''. Quantum science and technology 8, 015007 (2022).
https://doi.org/10.1088/2058-9565/ac91ef
[15] Yu-Hao Deng, Si-Qiu Gong, Yi-Chao Gu, Zhi-Jiong Zhang, Hua-Liang Liu, Hao Su, Hao-Yang Tang, Jia-Min Xu, Meng-Hao Jia, Ming-Cheng Chen, Han-Sen Zhong, Hui Wang, Jiarong Yan, Yi Hu, Jia Huang, Wei-Jun Zhang, Hao Li, Xiao Jiang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. ``Solving Graph Problems Using Gaussian Boson Sampling''. Phys. Rev. Lett. 130, 190601 (2023).
https://doi.org/10.1103/PhysRevLett.130.190601
[16] Andrew M. Childs, David Gosset, and Zak Webb. ``Universal Computation by Multiparticle Quantum Walk''. Science 339, 791–794 (2013).
https://doi.org/10.1126/science.1229957
[17] Andrew M. Childs and Jeffrey Goldstone. ``Spatial search by quantum walk''. Phys. Rev. A 70, 022314 (2004).
https://doi.org/10.1103/PhysRevA.70.022314
[18] Frédéric Magniez, Miklos Santha, and Mario Szegedy. ``Quantum Algorithms for the Triangle Problem''. SIAM Journal on Computing 37, 413–424 (2007).
https://doi.org/10.1137/050643684
[19] Andris Ambainis. ``Quantum Walk Algorithm for Element Distinctness''. SIAM Journal on Computing 37, 210–239 (2007).
https://doi.org/10.1137/S0097539705447311
[20] S. Marsh and J. B. Wang. ``Combinatorial optimization via highly efficient quantum walks''. Phys. Rev. Res. 2, 023302 (2020).
https://doi.org/10.1103/PhysRevResearch.2.023302
[21] Kunkun Wang, Xingze Qiu, Lei Xiao, Xiang Zhan, Zhihao Bian, Wei Yi, and Peng Xue. ``Simulating Dynamic Quantum Phase Transitions in Photonic Quantum Walks''. Phys. Rev. Lett. 122, 020501 (2019).
https://doi.org/10.1103/PhysRevLett.122.020501
[22] Giuseppe Di Molfetta and Armando Pérez. ``Quantum walks as simulators of neutrino oscillations in a vacuum and matter''. New J. of Phys. 18, 103038 (2016).
https://doi.org/10.1088/1367-2630/18/10/103038
[23] Zhiguang Yan, Yu-Ran Zhang, Ming Gong, Yulin Wu, Yarui Zheng, Shaowei Li, Can Wang, Futian Liang, Jin Lin, Yu Xu, Cheng Guo, Lihua Sun, Cheng-Zhi Peng, Keyu Xia, Hui Deng, Hao Rong, J. Q. You, Franco Nori, Heng Fan, Xiaobo Zhu, and Jian-Wei Pan. ``Strongly correlated quantum walks with a 12-qubit superconducting processor''. Science 364, 753–756 (2019).
https://doi.org/10.1126/science.aaw1611
[24] Ming Gong, Shiyu Wang, Chen Zha, Ming-Cheng Chen, He-Liang Huang, Yulin Wu, Qingling Zhu, Youwei Zhao, Shaowei Li, Shaojun Guo, Haoran Qian, Yangsen Ye, Fusheng Chen, Chong Ying, Jiale Yu, Daojin Fan, Dachao Wu, Hong Su, Hui Deng, Hao Rong, Kaili Zhang, Sirui Cao, Jin Lin, Yu Xu, Lihua Sun, Cheng Guo, Na Li, Futian Liang, V. M. Bastidas, Kae Nemoto, W. J. Munro, Yong-Heng Huo, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. ``Quantum walks on a programmable two-dimensional 62-qubit superconducting processor''. Science 372, 948–952 (2021).
https://doi.org/10.1126/science.abg7812
[25] Hao Tang, Xiao-Feng Lin, Zhen Feng, Jing-Yuan Chen, Jun Gao, Ke Sun, Chao-Yue Wang, Peng-Cheng Lai, Xiao-Yun Xu, Yao Wang, Lu-Feng Qiao, Ai-Lin Yang, and Xian-Min Jin. ``Experimental two-dimensional quantum walk on a photonic chip''. Science Advances 4, eaat3174 (2018).
https://doi.org/10.1126/sciadv.aat3174
[26] Chao Chen, Xing Ding, Jian Qin, Yu He, Yi-Han Luo, Ming-Cheng Chen, Chang Liu, Xi-Lin Wang, Wei-Jun Zhang, Hao Li, Li-Xing You, Zhen Wang, Da-Wei Wang, Barry C. Sanders, Chao-Yang Lu, and Jian-Wei Pan. ``Observation of Topologically Protected Edge States in a Photonic Two-Dimensional Quantum Walk''. Phys. Rev. Lett. 121, 100502 (2018).
https://doi.org/10.1103/PhysRevLett.121.100502
[27] Alberto Peruzzo, Mirko Lobino, Jonathan C. F. Matthews, Nobuyuki Matsuda, Alberto Politi, Konstantinos Poulios, Xiao-Qi Zhou, Yoav Lahini, Nur Ismail, Kerstin Wörhoff, Yaron Bromberg, Yaron Silberberg, Mark G. Thompson, and Jeremy L. OBrien. ``Quantum Walks of Correlated Photons''. Science 329, 1500–1503 (2010).
https://doi.org/10.1126/science.1193515
[28] F. Zähringer, G. Kirchmair, R. Gerritsma, E. Solano, R. Blatt, and C. F. Roos. ``Realization of a Quantum Walk with One and Two Trapped Ions''. Phys. Rev. Lett. 104, 100503 (2010).
https://doi.org/10.1103/PhysRevLett.104.100503
[29] H. Schmitz, R. Matjeschk, Ch. Schneider, J. Glueckert, M. Enderlein, T. Huber, and T. Schaetz. ``Quantum Walk of a Trapped Ion in Phase Space''. Phys. Rev. Lett. 103, 090504 (2009).
https://doi.org/10.1103/PhysRevLett.103.090504
[30] Masaya Tamura, Takashi Mukaiyama, and Kenji Toyoda. ``Quantum Walks of a Phonon in Trapped Ions''. Phys. Rev. Lett. 124, 200501 (2020).
https://doi.org/10.1103/PhysRevLett.124.200501
[31] Robert Matjeschk, Ch Schneider, Martin Enderlein, Thomas Huber, Hector Schmitz, Jan Glueckert, and Tobias Schaetz. ``Experimental simulation and limitations of quantum walks with trapped ions''. New J. Phys. 14 14, 035012 (2012).
https://doi.org/10.1088/1367-2630/14/3/035012
[32] Peng Xue, Barry C. Sanders, and Dietrich Leibfried. ``Quantum Walk on a Line for a Trapped Ion''. Phys. Rev. Lett. 103, 183602 (2009).
https://doi.org/10.1103/PhysRevLett.103.183602
[33] Michal Karski, Leonid Förster, Jai-Min Choi, Andreas Steffen, Wolfgang Alt, Dieter Meschede, and Artur Widera. ``Quantum Walk in Position Space with Single Optically Trapped Atoms''. Science 325, 174–177 (2009).
https://doi.org/10.1126/science.1174436
[34] Siamak Dadras, Alexander Gresch, Caspar Groiseau, Sandro Wimberger, and Gil S. Summy. ``Experimental realization of a momentum-space quantum walk''. Phys. Rev. A 99, 043617 (2019).
https://doi.org/10.1103/PhysRevA.99.043617
[35] Philipp M. Preiss, Ruichao Ma, M. Eric Tai, Alexander Lukin, Matthew Rispoli, Philip Zupancic, Yoav Lahini, Rajibul Islam, and Markus Greiner. ``Strongly correlated quantum walks in optical lattices''. Science 347, 1229–1233 (2015).
https://doi.org/10.1126/science.1260364
[36] J. H. Clark, C. Groiseau, Z. N. Shaw, S. Dadras, C. Binegar, S. Wimberger, G. S. Summy, and Y. Liu. ``Quantum to classical walk transitions tuned by spontaneous emissions''. Phys. Rev. Res. 3, 043062 (2021).
https://doi.org/10.1103/PhysRevResearch.3.043062
[37] Renato Portugal. ``Staggered quantum walks on graphs''. Phys. Rev. A 93, 062335 (2016).
https://doi.org/10.1103/PhysRevA.93.062335
[38] M. Szegedy. ``Quantum speed-up of markov chain based algorithms''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 32–41. (2004).
https://doi.org/10.1109/FOCS.2004.53
[39] R. Portugal, M. C. de Oliveira, and J. K. Moqadam. ``Staggered quantum walks with Hamiltonians''. Phys. Rev. A 95, 012328 (2017).
https://doi.org/10.1103/PhysRevA.95.012328
[40] J. Khatibi Moqadam, M. C. de Oliveira, and R. Portugal. ``Staggered quantum walks with superconducting microwave resonators''. Phys. Rev. B 95, 144506 (2017).
https://doi.org/10.1103/PhysRevB.95.144506
[41] A Abreu, L Cunha, T Fernandes, C de Figueiredo, L Kowada, F Marquezino, D Posner, and R Portugal. ``Bounds and complexity for the tessellation problem''. Mat. Contemp 45, 22–30 (2017).
https://doi.org/10.21711/231766362017/rmc453
[42] Alexandre Abreu, Luis Cunha, Tharso Fernandes, Celina de Figueiredo, Luis Kowada, Franklin Marquezino, Daniel Posner, and Renato Portugal. ``The Graph Tessellation Cover Number: Extremal Bounds, Efficient Algorithms and Hardness''. In LATIN 2018: Theoretical Informatics. Pages 1–13. Cham (2018). Springer International Publishing.
https://doi.org/10.1007/978-3-319-77404-6_1
[43] Alexandre Abreu, Luís Cunha, Celina de Figueiredo, Luis Kowada, Franklin Marquezino, Renato Portugal, and Daniel Posner. ``A computational complexity comparative study of graph tessellation problems''. Theoretical Computer Science 858, 81–89 (2021).
https://doi.org/10.1016/j.tcs.2020.11.045
[44] Jeremy T. Young, Przemyslaw Bienias, Ron Belyansky, Adam M. Kaufman, and Alexey V. Gorshkov. ``Asymmetric Blockade and Multiqubit Gates via Dipole-Dipole Interactions''. Phys. Rev. Lett. 127, 120501 (2021).
https://doi.org/10.1103/PhysRevLett.127.120501
[45] Meng Li, F.-Q. Guo, Z. Jin, L.-L. Yan, E.-J. Liang, and S.-L. Su. ``Multiple-qubit controlled unitary quantum gate for Rydberg atoms using shortcut to adiabaticity and optimized geometric quantum operations''. Phys. Rev. A 103, 062607 (2021).
https://doi.org/10.1103/PhysRevA.103.062607
[46] Gerard Pelegrí, Andrew J Daley, and Jonathan D Pritchard. ``High-fidelity multiqubit Rydberg gates via two-photon adiabatic rapid passage''. Quantum Science & Technology 7, 045020 (2022).
https://doi.org/10.1088/2058-9565/ac823a
[47] Sinchan Snigdha Rej and Bimalendu Deb. ``Neutral-atom quantum computation using multi-qubit geometric gates via adiabatic passage''. New J. Phys. 28, 014513 (2026).
https://doi.org/10.1088/1367-2630/ae390c
[48] Shi-Lei Su, Ya Gao, Erjun Liang, and Shou Zhang. ``Fast Rydberg antiblockade regime and its applications in quantum logic gates''. Phys. Rev. A 95, 022319 (2017).
https://doi.org/10.1103/PhysRevA.95.022319
[49] S. L. Su, H. Z. Shen, Erjun Liang, and Shou Zhang. ``One-step construction of the multiple-qubit Rydberg controlled-phase gate''. Phys. Rev. A 98, 032306 (2018).
https://doi.org/10.1103/PhysRevA.98.032306
[50] Mathew D Penrose. ``The longest edge of the random minimal spanning tree''. Ann. Appl. Probab. 7, 340–361 (1997).
https://doi.org/10.1214/aoap/1034625335
[51] Martin J.B. Appel and Ralph P. Russo. ``The connectivity of a graph on uniform points on $[0,1]^d$''. Statistics & Probability Letters 60, 351–357 (2002).
https://doi.org/10.1016/S0167-7152(02)00233-X
[52] Amlan Chakrabarti, ChiaChun Lin, and Niraj K. Jha. ``Design of Quantum Circuits for Random Walk Algorithms''. In 2012 IEEE Computer Society Annual Symposium on VLSI. Pages 135–140. (2012).
https://doi.org/10.1109/ISVLSI.2012.45
[53] Mikko Möttönen and Juha J Vartiainen. ``Decompositions of general quantum gates''. Chapter 7. Nova Publishers. (2006).
https://doi.org/10.48550/arXiv.quant-ph/0504100
arXiv:quant-ph/0504100
[54] Juha J. Vartiainen, Mikko Möttönen, and Martti M. Salomaa. ``Efficient Decomposition of Quantum Gates''. Phys. Rev. Lett. 92, 177902 (2004).
https://doi.org/10.1103/PhysRevLett.92.177902
[55] Michael A. Nielsen and Isaac L. Chuang. ``Quantum Computation and Quantum Information''. Volume 2. Cambridge University Press. (2001).
https://doi.org/10.1017/CBO9780511976667
[56] Seth Lloyd. ``Universal Quantum Simulators''. Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073
[57] R. Portugal and T. D. Fernandes. ``Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians''. Phys. Rev. A 95, 042341 (2017).
https://doi.org/10.1103/PhysRevA.95.042341
[58] Dongmin Yu, Han Wang, Jin-ming Liu, Shi-Lei Su, Jing Qian, and Weiping Zhang. ``Multiqubit Toffoli Gates and Optimal Geometry with Rydberg Atoms''. Phys. Rev. Applied 18, 034072 (2022).
https://doi.org/10.1103/PhysRevApplied.18.034072
[59] Yucheng He, Jing-Xin Liu, F.-Q. Guo, L.-L. Yan, Ronghui Luo, Erjun Liang, S.-L. Su, and M. Feng. ``Multiple-qubit Rydberg quantum logic gate via dressed-state scheme''. Optics Communications 505, 127500 (2022).
https://doi.org/10.1016/j.optcom.2021.127500
[60] S. Marsh and J.B. Wang. ``A quantum walk-assisted approximate algorithm for bounded NP optimisation problems''. Quantum Inf Process 18, 61 (2019).
https://doi.org/10.1007/s11128-019-2171-3
[1] Albert-László Barabási and Márton Pósfai. ``Network science''. Volume 3. Cambridge University Press. (2016).
https://doi.org/10.1098/rsta.2012.0375
[2] Santo Fortunato. ``Community detection in graphs''. Physics Reports 486, 75–174 (2010).
https://doi.org/10.1016/j.physrep.2009.11.002
[3] Bogdan Danila, Yong Yu, John A. Marsh, and Kevin E. Bassler. ``Optimal transport on complex networks''. Phys. Rev. E 74, 046106 (2006).
https://doi.org/10.1103/PhysRevE.74.046106
[4] Gang Yan, Tao Zhou, Bo Hu, Zhong-Qian Fu, and Bing-Hong Wang. ``Efficient routing on complex networks''. Phys. Rev. E 73, 046108 (2006).
https://doi.org/10.1103/PhysRevE.73.046108
[5] Yamir Moreno, Maziar Nekovee, and Amalio F. Pacheco. ``Dynamics of rumor spreading in complex networks''. Phys. Rev. E 69, 066130 (2004).
https://doi.org/10.1103/PhysRevE.69.066130
[6] M. Morgado and S. Whitlock. ``Quantum simulation and computing with Rydberg-interacting qubits''. AVS Quantum Science 3, 023501 (2021).
https://doi.org/10.1116/5.0036562
[7] K McInroy, N Pearson, and JD Pritchard. ``Benchmarking the algorithmic performance of near-term neutral atom processors'' (2024). url: https://doi.org/10.48550/arXiv.2402.02127.
https://doi.org/10.48550/arXiv.2402.02127
[8] Nishad Maskara, Stefan Ostermann, James Shee, Marcin Kalinowski, Abigail McClain Gomez, Rodrigo Araiza Bravo, Derek S Wang, Anna I Krylov, Norman Y Yao, Martin Head-Gordon, et al. ``Programmable simulations of molecules and materials with reconfigurable quantum processors''. Nature Physics 21, 289–297 (2025).
https://doi.org/10.1038/s41567-024-02738-z
[9] S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletić, and M. D. Lukin. ``Quantum optimization of maximum independent set using Rydberg atom arrays''. Science 376, 1209–1215 (2022).
https://doi.org/10.1126/science.abo6587
[10] Minhyuk Kim, Kangheun Kim, Jaeyong Hwang, Eun-Gook Moon, and Jaewook Ahn. ``Rydberg quantum wires for maximum independent set problems''. Nature Physics 18, 755–759 (2022).
https://doi.org/10.1038/s41567-022-01629-5
[11] Seokho Jeong, Minhyuk Kim, Minki Hhan, JuYoung Park, and Jaewook Ahn. ``Quantum programming of the satisfiability problem with Rydberg atom graphs''. Phys. Rev. Res. 5, 043037 (2023).
https://doi.org/10.1103/PhysRevResearch.5.043037
[12] Aaron W. Young, William J. Eckner, Nathan Schine, Andrew M. Childs, and Adam M. Kaufman. ``Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice''. Science 377, 885–889 (2022).
https://doi.org/10.1126/science.abo0608
[13] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. ``Quantum approximate optimization of non-planar graph problems on a planar superconducting processor''. Nature Physics 17, 332–336 (2021).
https://doi.org/10.1038/s41567-020-01105-y
[14] Yingyue Zhu, Zewen Zhang, Bhuvanesh Sundar, Alaina M Green, C Huerta Alderete, Nhung H Nguyen, Kaden RA Hazzard, and Norbert M Linke. ``Multi-round QAOA and advanced mixers on a trapped-ion quantum computer''. Quantum science and technology 8, 015007 (2022).
https://doi.org/10.1088/2058-9565/ac91ef
[15] Yu-Hao Deng, Si-Qiu Gong, Yi-Chao Gu, Zhi-Jiong Zhang, Hua-Liang Liu, Hao Su, Hao-Yang Tang, Jia-Min Xu, Meng-Hao Jia, Ming-Cheng Chen, Han-Sen Zhong, Hui Wang, Jiarong Yan, Yi Hu, Jia Huang, Wei-Jun Zhang, Hao Li, Xiao Jiang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. ``Solving Graph Problems Using Gaussian Boson Sampling''. Phys. Rev. Lett. 130, 190601 (2023).
https://doi.org/10.1103/PhysRevLett.130.190601
[16] Andrew M. Childs, David Gosset, and Zak Webb. ``Universal Computation by Multiparticle Quantum Walk''. Science 339, 791–794 (2013).
https://doi.org/10.1126/science.1229957
[17] Andrew M. Childs and Jeffrey Goldstone. ``Spatial search by quantum walk''. Phys. Rev. A 70, 022314 (2004).
https://doi.org/10.1103/PhysRevA.70.022314
[18] Frédéric Magniez, Miklos Santha, and Mario Szegedy. ``Quantum Algorithms for the Triangle Problem''. SIAM Journal on Computing 37, 413–424 (2007).
https://doi.org/10.1137/050643684
[19] Andris Ambainis. ``Quantum Walk Algorithm for Element Distinctness''. SIAM Journal on Computing 37, 210–239 (2007).
https://doi.org/10.1137/S0097539705447311
[20] S. Marsh and J. B. Wang. ``Combinatorial optimization via highly efficient quantum walks''. Phys. Rev. Res. 2, 023302 (2020).
https://doi.org/10.1103/PhysRevResearch.2.023302
[21] Kunkun Wang, Xingze Qiu, Lei Xiao, Xiang Zhan, Zhihao Bian, Wei Yi, and Peng Xue. ``Simulating Dynamic Quantum Phase Transitions in Photonic Quantum Walks''. Phys. Rev. Lett. 122, 020501 (2019).
https://doi.org/10.1103/PhysRevLett.122.020501
[22] Giuseppe Di Molfetta and Armando Pérez. ``Quantum walks as simulators of neutrino oscillations in a vacuum and matter''. New J. of Phys. 18, 103038 (2016).
https://doi.org/10.1088/1367-2630/18/10/103038
[23] Zhiguang Yan, Yu-Ran Zhang, Ming Gong, Yulin Wu, Yarui Zheng, Shaowei Li, Can Wang, Futian Liang, Jin Lin, Yu Xu, Cheng Guo, Lihua Sun, Cheng-Zhi Peng, Keyu Xia, Hui Deng, Hao Rong, J. Q. You, Franco Nori, Heng Fan, Xiaobo Zhu, and Jian-Wei Pan. ``Strongly correlated quantum walks with a 12-qubit superconducting processor''. Science 364, 753–756 (2019).
https://doi.org/10.1126/science.aaw1611
[24] Ming Gong, Shiyu Wang, Chen Zha, Ming-Cheng Chen, He-Liang Huang, Yulin Wu, Qingling Zhu, Youwei Zhao, Shaowei Li, Shaojun Guo, Haoran Qian, Yangsen Ye, Fusheng Chen, Chong Ying, Jiale Yu, Daojin Fan, Dachao Wu, Hong Su, Hui Deng, Hao Rong, Kaili Zhang, Sirui Cao, Jin Lin, Yu Xu, Lihua Sun, Cheng Guo, Na Li, Futian Liang, V. M. Bastidas, Kae Nemoto, W. J. Munro, Yong-Heng Huo, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. ``Quantum walks on a programmable two-dimensional 62-qubit superconducting processor''. Science 372, 948–952 (2021).
https://doi.org/10.1126/science.abg7812
[25] Hao Tang, Xiao-Feng Lin, Zhen Feng, Jing-Yuan Chen, Jun Gao, Ke Sun, Chao-Yue Wang, Peng-Cheng Lai, Xiao-Yun Xu, Yao Wang, Lu-Feng Qiao, Ai-Lin Yang, and Xian-Min Jin. ``Experimental two-dimensional quantum walk on a photonic chip''. Science Advances 4, eaat3174 (2018).
https://doi.org/10.1126/sciadv.aat3174
[26] Chao Chen, Xing Ding, Jian Qin, Yu He, Yi-Han Luo, Ming-Cheng Chen, Chang Liu, Xi-Lin Wang, Wei-Jun Zhang, Hao Li, Li-Xing You, Zhen Wang, Da-Wei Wang, Barry C. Sanders, Chao-Yang Lu, and Jian-Wei Pan. ``Observation of Topologically Protected Edge States in a Photonic Two-Dimensional Quantum Walk''. Phys. Rev. Lett. 121, 100502 (2018).
https://doi.org/10.1103/PhysRevLett.121.100502
[27] Alberto Peruzzo, Mirko Lobino, Jonathan C. F. Matthews, Nobuyuki Matsuda, Alberto Politi, Konstantinos Poulios, Xiao-Qi Zhou, Yoav Lahini, Nur Ismail, Kerstin Wörhoff, Yaron Bromberg, Yaron Silberberg, Mark G. Thompson, and Jeremy L. OBrien. ``Quantum Walks of Correlated Photons''. Science 329, 1500–1503 (2010).
https://doi.org/10.1126/science.1193515
[28] F. Zähringer, G. Kirchmair, R. Gerritsma, E. Solano, R. Blatt, and C. F. Roos. ``Realization of a Quantum Walk with One and Two Trapped Ions''. Phys. Rev. Lett. 104, 100503 (2010).
https://doi.org/10.1103/PhysRevLett.104.100503
[29] H. Schmitz, R. Matjeschk, Ch. Schneider, J. Glueckert, M. Enderlein, T. Huber, and T. Schaetz. ``Quantum Walk of a Trapped Ion in Phase Space''. Phys. Rev. Lett. 103, 090504 (2009).
https://doi.org/10.1103/PhysRevLett.103.090504
[30] Masaya Tamura, Takashi Mukaiyama, and Kenji Toyoda. ``Quantum Walks of a Phonon in Trapped Ions''. Phys. Rev. Lett. 124, 200501 (2020).
https://doi.org/10.1103/PhysRevLett.124.200501
[31] Robert Matjeschk, Ch Schneider, Martin Enderlein, Thomas Huber, Hector Schmitz, Jan Glueckert, and Tobias Schaetz. ``Experimental simulation and limitations of quantum walks with trapped ions''. New J. Phys. 14 14, 035012 (2012).
https://doi.org/10.1088/1367-2630/14/3/035012
[32] Peng Xue, Barry C. Sanders, and Dietrich Leibfried. ``Quantum Walk on a Line for a Trapped Ion''. Phys. Rev. Lett. 103, 183602 (2009).
https://doi.org/10.1103/PhysRevLett.103.183602
[33] Michal Karski, Leonid Förster, Jai-Min Choi, Andreas Steffen, Wolfgang Alt, Dieter Meschede, and Artur Widera. ``Quantum Walk in Position Space with Single Optically Trapped Atoms''. Science 325, 174–177 (2009).
https://doi.org/10.1126/science.1174436
[34] Siamak Dadras, Alexander Gresch, Caspar Groiseau, Sandro Wimberger, and Gil S. Summy. ``Experimental realization of a momentum-space quantum walk''. Phys. Rev. A 99, 043617 (2019).
https://doi.org/10.1103/PhysRevA.99.043617
[35] Philipp M. Preiss, Ruichao Ma, M. Eric Tai, Alexander Lukin, Matthew Rispoli, Philip Zupancic, Yoav Lahini, Rajibul Islam, and Markus Greiner. ``Strongly correlated quantum walks in optical lattices''. Science 347, 1229–1233 (2015).
https://doi.org/10.1126/science.1260364
[36] J. H. Clark, C. Groiseau, Z. N. Shaw, S. Dadras, C. Binegar, S. Wimberger, G. S. Summy, and Y. Liu. ``Quantum to classical walk transitions tuned by spontaneous emissions''. Phys. Rev. Res. 3, 043062 (2021).
https://doi.org/10.1103/PhysRevResearch.3.043062
[37] Renato Portugal. ``Staggered quantum walks on graphs''. Phys. Rev. A 93, 062335 (2016).
https://doi.org/10.1103/PhysRevA.93.062335
[38] M. Szegedy. ``Quantum speed-up of markov chain based algorithms''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 32–41. (2004).
https://doi.org/10.1109/FOCS.2004.53
[39] R. Portugal, M. C. de Oliveira, and J. K. Moqadam. ``Staggered quantum walks with Hamiltonians''. Phys. Rev. A 95, 012328 (2017).
https://doi.org/10.1103/PhysRevA.95.012328
[40] J. Khatibi Moqadam, M. C. de Oliveira, and R. Portugal. ``Staggered quantum walks with superconducting microwave resonators''. Phys. Rev. B 95, 144506 (2017).
https://doi.org/10.1103/PhysRevB.95.144506
[41] A Abreu, L Cunha, T Fernandes, C de Figueiredo, L Kowada, F Marquezino, D Posner, and R Portugal. ``Bounds and complexity for the tessellation problem''. Mat. Contemp 45, 22–30 (2017).
https://doi.org/10.21711/231766362017/rmc453
[42] Alexandre Abreu, Luis Cunha, Tharso Fernandes, Celina de Figueiredo, Luis Kowada, Franklin Marquezino, Daniel Posner, and Renato Portugal. ``The Graph Tessellation Cover Number: Extremal Bounds, Efficient Algorithms and Hardness''. In LATIN 2018: Theoretical Informatics. Pages 1–13. Cham (2018). Springer International Publishing.
https://doi.org/10.1007/978-3-319-77404-6_1
[43] Alexandre Abreu, Luís Cunha, Celina de Figueiredo, Luis Kowada, Franklin Marquezino, Renato Portugal, and Daniel Posner. ``A computational complexity comparative study of graph tessellation problems''. Theoretical Computer Science 858, 81–89 (2021).
https://doi.org/10.1016/j.tcs.2020.11.045
[44] Jeremy T. Young, Przemyslaw Bienias, Ron Belyansky, Adam M. Kaufman, and Alexey V. Gorshkov. ``Asymmetric Blockade and Multiqubit Gates via Dipole-Dipole Interactions''. Phys. Rev. Lett. 127, 120501 (2021).
https://doi.org/10.1103/PhysRevLett.127.120501
[45] Meng Li, F.-Q. Guo, Z. Jin, L.-L. Yan, E.-J. Liang, and S.-L. Su. ``Multiple-qubit controlled unitary quantum gate for Rydberg atoms using shortcut to adiabaticity and optimized geometric quantum operations''. Phys. Rev. A 103, 062607 (2021).
https://doi.org/10.1103/PhysRevA.103.062607
[46] Gerard Pelegrí, Andrew J Daley, and Jonathan D Pritchard. ``High-fidelity multiqubit Rydberg gates via two-photon adiabatic rapid passage''. Quantum Science & Technology 7, 045020 (2022).
https://doi.org/10.1088/2058-9565/ac823a
[47] Sinchan Snigdha Rej and Bimalendu Deb. ``Neutral-atom quantum computation using multi-qubit geometric gates via adiabatic passage''. New J. Phys. 28, 014513 (2026).
https://doi.org/10.1088/1367-2630/ae390c
[48] Shi-Lei Su, Ya Gao, Erjun Liang, and Shou Zhang. ``Fast Rydberg antiblockade regime and its applications in quantum logic gates''. Phys. Rev. A 95, 022319 (2017).
https://doi.org/10.1103/PhysRevA.95.022319
[49] S. L. Su, H. Z. Shen, Erjun Liang, and Shou Zhang. ``One-step construction of the multiple-qubit Rydberg controlled-phase gate''. Phys. Rev. A 98, 032306 (2018).
https://doi.org/10.1103/PhysRevA.98.032306
[50] Mathew D Penrose. ``The longest edge of the random minimal spanning tree''. Ann. Appl. Probab. 7, 340–361 (1997).
https://doi.org/10.1214/aoap/1034625335
[51] Martin J.B. Appel and Ralph P. Russo. ``The connectivity of a graph on uniform points on $[0,1]^d$''. Statistics & Probability Letters 60, 351–357 (2002).
https://doi.org/10.1016/S0167-7152(02)00233-X
[52] Amlan Chakrabarti, ChiaChun Lin, and Niraj K. Jha. ``Design of Quantum Circuits for Random Walk Algorithms''. In 2012 IEEE Computer Society Annual Symposium on VLSI. Pages 135–140. (2012).
https://doi.org/10.1109/ISVLSI.2012.45
[53] Mikko Möttönen and Juha J Vartiainen. ``Decompositions of general quantum gates''. Chapter 7. Nova Publishers. (2006).
https://doi.org/10.48550/arXiv.quant-ph/0504100
arXiv:quant-ph/0504100
[54] Juha J. Vartiainen, Mikko Möttönen, and Martti M. Salomaa. ``Efficient Decomposition of Quantum Gates''. Phys. Rev. Lett. 92, 177902 (2004).
https://doi.org/10.1103/PhysRevLett.92.177902
[55] Michael A. Nielsen and Isaac L. Chuang. ``Quantum Computation and Quantum Information''. Volume 2. Cambridge University Press. (2001).
https://doi.org/10.1017/CBO9780511976667
[56] Seth Lloyd. ``Universal Quantum Simulators''. Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073
[57] R. Portugal and T. D. Fernandes. ``Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians''. Phys. Rev. A 95, 042341 (2017).
https://doi.org/10.1103/PhysRevA.95.042341
[58] Dongmin Yu, Han Wang, Jin-ming Liu, Shi-Lei Su, Jing Qian, and Weiping Zhang. ``Multiqubit Toffoli Gates and Optimal Geometry with Rydberg Atoms''. Phys. Rev. Applied 18, 034072 (2022).
https://doi.org/10.1103/PhysRevApplied.18.034072
[59] Yucheng He, Jing-Xin Liu, F.-Q. Guo, L.-L. Yan, Ronghui Luo, Erjun Liang, S.-L. Su, and M. Feng. ``Multiple-qubit Rydberg quantum logic gate via dressed-state scheme''. Optics Communications 505, 127500 (2022).
https://doi.org/10.1016/j.optcom.2021.127500
[60] S. Marsh and J.B. Wang. ``A quantum walk-assisted approximate algorithm for bounded NP optimisation problems''. Quantum Inf Process 18, 61 (2019).
https://doi.org/10.1007/s11128-019-2171-3
Cited by
On Crossref's cited-by service no data on citing works was found (last attempt 2026-11-15 00:06:23). On SAO/NASA ADS no data on citing works was found (last attempt 2026-11-15 00:06:23).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.