- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review A

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Continuous-time quantum-walk-based ansätze on neutral-atom hardware

Edric Matwiejew1, Jonathan Wurtz2, Jing Chen2, Pascal Jahan Elahi1, Tommaso Macri2, and Ugo Varetto1

PDF

Phys. Rev. A 114, 012425 – Published 9 July, 2026

DOI: https://doi.org/10.1103/cbd2-635q

Abstract

Continuous-time quantum walks offer provable speedups for certain computational problems, yet translating these advantages to near-term hardware remains challenging. We realize variational ansätze based on continuous-time quantum walks on an analog neutral-atom processor. For unentangled targets, we derive closed-form expressions for near-optimal control parameters that transfer directly to hardware with minimal calibration. On QuEra's Aquila processor, we observe the superquadratic convergence characteristic of efficient quantum walk algorithms, visible at low circuit depth, with theory predicting stronger speedups as hardware improves. For entangled targets, specifically symmetric superpositions in the Rydberg-blockaded subspace, we introduce an optimization protocol exploiting spectral properties of the walk dynamics. The required evolution timescales inversely with the spectral gap, offering an advantage over adiabatic protocols, whose evolution timescales as the inverse square of the spectral gap. We verify this scaling behavior on Aquila and confirm that the prepared states are coherent superpositions via quench dynamics. Our results establish a practical pathway from abstract quantum walk algorithms to analog quantum processors, demonstrating that the dynamics underlying their potential for superquadratic quantum speedup are accessible on current devices.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (67)

  1. J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  2. E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv:1411.4028.
  3. A. Ambainis, Quantum walk algorithm for element distinctness, SIAM J. Comput. 37, 210 (2007).
  4. A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett. 102, 180501 (2009).
  5. A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC '03 (ACM Press, San Diego, 2003), pp. 59–68.
  6. S. Deffner and S. Campbell, Quantum speed limits: From Heisenberg's uncertainty principle to optimal quantum control, J. Phys. A: Math. Theor. 50, 453001 (2017).
  7. M. Christandl, N. Datta, A. Ekert, and A. J. Landahl, Perfect state transfer in quantum spin networks, Phys. Rev. Lett. 92, 187902 (2004).
  8. E. Matwiejew, J. Pye, and J. B. Wang, Quantum optimisation for continuous multivariable functions by a structured search, Quantum Sci. Technol. 8, 045013 (2023).
  9. T. Bennett, L. Noakes, and J. Wang, in Proceedings of the 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE, Piscataway, NJ, 2024), pp. 31–41.
  10. A. Peruzzo, M. Lobino, J. C. F. Matthews, N. Matsuda, A. Politi, K. Poulios, X.-Q. Zhou, Y. Lahini, N. Ismail, K. Wörhoff, Y. Bromberg, Y. Silberberg, M. G. Thompson, and J. L. O'Brien, Quantum walks of correlated photons, Science 329, 1500 (2010).
  11. P. M. Preiss, R. Ma, M. E. Tai, A. Lukin, M. Rispoli, P. Zupancic, Y. Lahini, R. Islam, and M. Greiner, Strongly correlated quantum walks in optical lattices, Science 347, 1229 (2015).
  12. M. Tamura, T. Mukaiyama, and K. Toyoda, Quantum walks of a phonon in trapped ions, Phys. Rev. Lett. 124, 200501 (2020).
  13. Z. Yan, Y.-R. Zhang, M. Gong, Y. Wu, Y. Zheng, S. Li, C. Wang, F. Liang, J. Lin, Y. Xu, C. Guo, L. Sun, C.-Z. Peng, K. Xia, H. Deng, H. Rong, J. Q. You, F. Nori, H. Fan, X. Zhu, et al., Strongly correlated quantum walks with a 12-qubit superconducting processor, Science 364, 753 (2019).
  14. M. Gong, S. Wang, C. Zha, M.-C. Chen, H.-L. Huang, Y. Wu, Q. Zhu, Y. Zhao, S. Li, S. Guo, H. Qian, Y. Ye, F. Chen, C. Ying, J. Yu, D. Fan, D. Wu, H. Su, H. Deng, H. Rong, J.-W. Pan, et al., Quantum walks on a programmable two-dimensional 62-qubit superconducting processor, Science 372, 948 (2021).
  15. A. W. Young, W. J. Eckner, N. Schine, A. M. Childs, and A. M. Kaufman, Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice, Science 377, 885 (2022).
  16. D. Qu, E. Matwiejew, K. Wang, J. Wang, and P. Xue, Experimental implementation of quantum-walk-based portfolio optimization, Quantum Sci. Technol. 9, 025014 (2024).
  17. S. Choi, C. J. Turner, H. Pichler, W. W. Ho, A. A. Michailidis, Z. Papić, M. Serbyn, M. D. Lukin, and D. A. Abanin, Emergent SU(2) dynamics and perfect quantum many-body scars, Phys. Rev. Lett. 122, 220603 (2019).
  18. H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, V. Vuletić, and M. D. Lukin, Probing many-body dynamics on a 51-atom quantum simulator, Nature (London) 551, 579 (2017).
  19. M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, B. Burkett, N. Bushnell, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nat. Phys. 17, 332 (2021).
  20. R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun, Y. Alexeev, J. M. Dreiling, J. P. Gaebler, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V. Horst, S. Hu, et al., Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem, Sci. Adv. 10, eadm6761 (2024).
  21. S. Hadfield, Z. Wang, B. O'Gorman, E. Rieffel, D. Venturelli, and R. Biswas, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Algorithms 12, 34 (2019).
  22. J. A. Montañez-Barrera and K. Michielsen, Toward a linear-ramp QAOA protocol evidence of a scaling advantage in solving some combinatorial optimization problems, npj Quantum Inf. 11, 131 (2025).
  23. S. Marsh and J. B. Wang, Combinatorial optimization via highly efficient quantum walks, Phys. Rev. Res. 2, 023302 (2020).
  24. F. G. Fuchs and R. Bassa, LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism, Quantum 8, 1535 (2024).
  25. J. Wurtz, A. Bylinskii, B. Braverman, J. Amato-Grill, S. H. Cantu, F. Huber, A. Lukin, F. Liu, P. Weinberg, J. Long, S.-T. Wang, N. Gemelke, and A. Keesling, Aquila: QuEra's 256-qubit neutral-atom quantum computer, arXiv:2306.11727.
  26. 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, et al., Quantum optimization of maximum independent set using Rydberg atom arrays, Science 376, 1209 (2022).
  27. A. Bärtschi and S. Eidenbenz, Deterministic preparation of Dicke states, in Fundamentals of Computation Theory, edited by L. Gąsieniec, J. Jansson, and C. Levcopoulos, Lecture Notes in Computer Science Vol. 11651 (Springer, Cham, 2019).
  28. A. Lukin, B. F. Schiffer, B. Braverman, S. H. Cantu, F. Huber, A. Bylinskii, J. Amato-Grill, N. Maskara, M. Cain, D. S. Wild, R. Samajdar, and M. D. Lukin, Quantum quench dynamics as a shortcut to adiabaticity, arXiv:2405.21019.
  29. H. Krovi and T. A. Brun, Quantum walks on quotient graphs, Phys. Rev. A 75, 062332 (2007).
  30. S. E. Venegas-Andraca, Quantum walks: A comprehensive review, Quantum Inf. Process. 11, 1015 (2012).
  31. E. Munarini, C. P. Cippo, and N. Z. Salvi, On the lucas cubes, Fibonacci Quarterly 39, 12 (2001).
  32. L. G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8, 410 (1979).
  33. A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavžar, and M. Petkovšek, Vertex and edge orbits of Fibonacci and Lucas cubes, Ann. Comb. 20, 209 (2016).
  34. A. Gonzales, R. Herrman, C. Campbell, I. Gaidai, J. Liu, T. Tomesh, and Z. H. Saleem, Efficient sparse state preparation via quantum walks, npj Quantum Inf. 11, 143 (2025).
  35. K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer, A review on quantum approximate optimization algorithm and its variants, Phys. Rep. 1068, 1 (2024).
  36. J. Sawada, Generating bracelets in constant amortized time, SIAM J. Comput. 31, 259 (2001).
  37. A. Bärtschi and S. Eidenbenz, Grover mixers for QAOA: Shifting complexity from mixer design to state preparation, in Proceedings of the 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE, Piscataway, NJ, 2020), pp. 72–82.
  38. J. Wurtz and P. Love, MaxCut quantum approximate optimization algorithm performance guarantees for p>1, Phys. Rev. A 103, 042612 (2021).
  39. G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Contemp. Math. 305, 53 (2002).
  40. A. Ambainis, Quantum walks and their algorithmic applications, Int. J. Quantum Inform. 01, 507 (2003).
  41. C. Zalka, Grover's quantum searching algorithm is optimal, Phys. Rev. A 60, 2746 (1999).
  42. J. Wurtz and P. J. Love, Counterdiabaticity and the quantum approximate optimization algorithm, Quantum 6, 635 (2022).
  43. D. Guéry-Odelin, A. Ruschhaupt, A. Kiely, E. Torrontegui, S. Martínez-Garaot, and J. G. Muga, Shortcuts to adiabaticity: Concepts, methods, and applications, Rev. Mod. Phys. 91, 045001 (2019).
  44. Y. Atia and S. Chakraborty, Improved upper bounds for the hitting times of quantum walks, Phys. Rev. A 104, 032215 (2021).
  45. T. Albash and D. A. Lidar, Adiabatic quantum computation, Rev. Mod. Phys. 90, 015002 (2018).
  46. J.-Y. Desaules, K. Bull, A. Daniel, and Z. Papić, Hypergrid subgraphs and the origin of scarred quantum walks in many-body Hilbert space, Phys. Rev. B 105, 245137 (2022).
  47. M. Saffman, Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges, J. Phys. B: At. Mol. Opt. Phys. 49, 202001 (2016).
  48. M. Morgado and S. Whitlock, Quantum simulation and computing with Rydberg-interacting qubits, AVS Quantum Sci. 3, 023501 (2021).
  49. D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, J. P. Bonilla Ataides, N. Maskara, I. Cong, X. Gao, P. Sales Rodriguez, T. Karolyshyn, G. Semeghini, M. J. Gullans, M. Greiner, V. Vuletić, M. D. Lukin, et al., Logical quantum processor based on reconfigurable atom arrays, Nature (London) 626, 58 (2024).
  50. B. W. Reichardt, A. Paetznick, D. Aasen, I. Basov, J. M. Bello-Rivas, P. Bonderson, R. Chao, W. van Dam, M. B. Hastings, R. V. Mishmash, A. Paz, M. P. da Silva, A. Sundaram, K. M. Svore, A. Vaschillo, Z. Wang, M. Zanner, W. B. Cairncross, C.-A. Chen, D. Crow, et al., Fault-tolerant quantum computation with a neutral atom processor, arXiv:2411.11822.
  51. P. S. Rodriguez, J. M. Robinson, P. N. Jepsen, Z. He, C. Duckering, C. Zhao, K.-H. Wu, J. Campo, K. Bagnall, M. Kwon, T. Karolyshyn, P. Weinberg, M. Cain, S. J. Evered, A. A. Geim, M. Kalinowski, S. H. Li, T. Manovitz, J. Amato-Grill, J. I. Basham, et al., Experimental demonstration of logical magic state distillation, Nature (London) 645, 620 (2025).
  52. D. Bluvstein, A. A. Geim, S. H. Li, S. J. Evered, J. P. B. Ataides, G. Baranes, A. Gu, T. Manovitz, M. Xu, M. Kalinowski, S. Majidy, C. Kokail, N. Maskara, E. C. Trapp, L. M. Stewart, S. Hollerith, H. Zhou, M. J. Gullans, S. F. Yelin, M. Greiner, et al., Architectural mechanisms of a universal fault-tolerant quantum computer, arXiv:2506.20661.
  53. A. L. Shaw, Z. Chen, J. Choi, D. K. Mark, P. Scholl, R. Finkelstein, A. Elben, S. Choi, and M. Endres, Benchmarking highly entangled states on a 60-atom analogue quantum simulator, Nature (London) 628, 71 (2024).
  54. S. J. Evered, M. Kalinowski, A. A. Geim, T. Manovitz, D. Bluvstein, S. H. Li, N. Maskara, H. Zhou, S. Ebadi, M. Xu, J. Campo, M. Cain, S. Ostermann, S. F. Yelin, S. Sachdev, M. Greiner, V. Vuletić, and M. D. Lukin, Probing topological matter and fermion dynamics on a neutral-atom quantum computer, Nature (London) 645, 341 (2025).
  55. D. González-Cuadra, M. Hamdan, T. V. Zache, B. Braverman, M. Kornjaca, A. Lukin, S. H. Cantú, F. Liu, S.-T. Wang, A. Keesling, M. D. Lukin, P. Zoller, and A. Bylinskii, Observation of string breaking on a (2 + 1)D Rydberg quantum simulator, Nature (London) 642, 321 (2025).
  56. S. J. Evered, D. Bluvstein, M. Kalinowski, S. Ebadi, T. Manovitz, H. Zhou, S. H. Li, A. A. Geim, T. T. Wang, N. Maskara, H. Levine, G. Semeghini, M. Greiner, V. Vuletić, and M. D. Lukin, High-fidelity parallel entangling gates on a neutral-atom quantum computer, Nature (London) 622, 268 (2023).
  57. D. Bluvstein, A. Omran, H. Levine, A. Keesling, G. Semeghini, S. Ebadi, T. T. Wang, A. A. Michailidis, N. Maskara, W. W. Ho, S. Choi, M. Serbyn, M. Greiner, V. Vuletić, and M. D. Lukin, Controlling quantum many-body dynamics in driven Rydberg atom arrays, Science 371, 1355 (2021).
  58. J. Wurtz, S. H. Sack, and S.-T. Wang, Solving nonnative combinatorial optimization problems using hybrid quantum-classical algorithms, IEEE Trans. Quantum Eng. 5, 1 (2024).
  59. M. Cerezo, G. Verdon, H.-Y. Huang, L. Cincio, and P. J. Coles, Challenges and opportunities in quantum machine learning, Nat. Comput. Sci. 2, 567 (2022).
  60. J. Choi, H. Zhou, H. S. Knowles, R. Landig, S. Choi, and M. D. Lukin, Robust dynamic Hamiltonian engineering of many-body spin systems, Phys. Rev. X 10, 031002 (2020).
  61. Pawsey Supercomputing Research Centre, Setonix supercomputer (2023), Pawsey Supercomputing Research Centre, Perth, Western Australia, Australia.
  62. E. Matwiejew, J. Wurtz, J. Chen, P. J. Elahi, T. Macrì, and U. Varetto, Supplementary data and software for “Continuous-time quantum-walk-based ansätze on neutral-atom hardware” Zenodo, 2026, https://doi.org/10.5281/zenodo.20520609.
  63. B. Pokharel, S. Srinivasan, G. Quiroz, and B. Boots, Scalable measurement error mitigation via iterative Bayesian unfolding, Phys. Rev. Res. 6, 013187 (2024).
  64. D. J. MacKay, Information Theory, Inference and Learning Algorithms (Cambridge University Press, Cambridge, 2003).
  65. R. Blume-Kohout, Optimal, reliable estimation of quantum states, New J. Phys. 12, 043034 (2010).
  66. A. P. Dempster, N. M. Laird, and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, J. Roy. Stat. Soc. B Met. 39, 1 (1977).
  67. B. Efron, Bootstrap methods: Another look at the jackknife, in Breakthroughs in Statistics (Springer, New York, 1992), pp. 569–593.

Outline

Information

Phys. Rev. A 114, 012425– Published 9 July, 2026
  • Received 2 September 2025
  • Revised 5 March 2026
  • Accepted 13 May 2026
Crossmark - Check for updates button

©2026 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation