Quantum Information & Computation
Volume 24, Issue 1
RESEARCH ARTICLE Open access

Deterministic Search on Complete Bipartite Graphs by Continuous-Time Quantum Walk

Honghong Lin, Yun Shang

Author affiliations
  • Honghong Lin1
  • Yun Shang2
  1. Institute of Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China; School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China
  2. Institute of Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China; NCMIS, MDIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China

pp. 1-15 · 10.2478/qic-2024-0001

Read PDF View on Reference Global
On this page

Abstract

How to design deterministic spatial search algorithms is a difficult but important problem. This paper presents a deterministic search algorithm on complete bipartite graphs with optimal runtime scaling. Our algorithm adopts the simple form of alternating iterations of an oracle and a continuous-time quantum walk operator, which is a generalization of Grover's search algorithm. To address the case of the number of marked vertices being unknown, we construct a quantum counting algorithm based on the spectrum structure of the search operator. This is a non-trivial example of quantum counting for spatial search. To implement the continuous-time quantum walk operator, we perform Hamiltonian simulation in the quantum circuit model and simulate it on the IBM quantum computing platform Qiskit.
Open accessCC BY-NC-SA 4.0

Keywords

  • spatial search
  • deterministic quantum algorithm
  • quantum counting
  • continuous-time quantum walk
  • complete bipartite graph

Suggested citation

Honghong Lin, Yun Shang (2024). Deterministic Search on Complete Bipartite Graphs by Continuous-Time Quantum Walk. Quantum Information & Computation, 24(1), 1-15. https://doi.org/10.2478/qic-2024-0001

Download BibTeX

References (43)

  1. A. Ambainis, A. Gilyén, S. Jeffery and M. Kokainis (2020). “Quadratic speedup for finding marked vertices by quantum walks”, in K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath and J. Chuzhoy (eds), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Jun 22, 412–424.DOI: 10.1145/3357713.3384252Google Scholar
  2. S. Apers, S. Chakraborty, L. Novo and J. Roland (2022). “Quadratic speedup for spatial search by continuous-time quantum walk”. Physical Review Letters, 129: 16, 160502.DOI: 10.1103/PhysRevLett.129.160502Google Scholar
  3. A. Ambainis (2007). “Quantum walk algorithm for element distinctness”. SIAM Journal on Computing 37: 1, 210–239.DOI: 10.1137/S0097539705447311Google Scholar
  4. J.K. Gamble, M. Friesen, D. Zhou, R. Joynt and S.N. Coppersmith (2010). “Two-particle quantum walks applied to the graph isomorphism problem”. Physical Review A 81: 5, 052313.DOI: 10.1103/PhysRevA.81.052313Google Scholar
  5. D. Aharonov, A. Ambainis, J. Kempe, et al. (2001). “Quantum walks on graphs”, in Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, 50–59.DOI: 10.1145/380752.380758Google Scholar
  6. B. Tödtli, M. Laner, J. Semenov, et al. (2016). “Continuous-time quantum walks on directed bipartite graphs”. Physical Review A, 94: 5, 052338.DOI: 10.1103/PhysRevA.94.052338Google Scholar
  7. R. Chaves, B. Chagas, and G. Coutinho (2023). “Why and how to add direction to a quantum walk”. Quantum Information Processing, 22: 1, 41.DOI: 10.1007/s11128-022-03746-9Google Scholar
  8. A.M. Childs (2009). “Universal computation by quantum walk”. Physical Review Letters, 102: 18, 180501.DOI: 10.1103/PhysRevLett.102.180501Google Scholar
  9. A.M. Childs, D. Gosset and Z. Webb (2013). “Universal computation by multiparticle quantum walk”. Science, 339: 6121, 791–794.DOI: 10.1126/science.1229957Google Scholar
  10. M. Tamura, T. Mukaiyama and K. Toyoda (2020). “Quantum walks of a phonon in trapped ions”. Physical Review Letters, 124: 20, 200501.DOI: 10.1103/PhysRevLett.124.200501Google Scholar
  11. J. Wang and K. Manouchehri (2013). Physical Implementation of Quantum Walks. Heidelberg: Springer Berlin, 10: 978–983.DOI: 10.1007/978-3-642-36014-5Google Scholar
  12. C. A. Ryan, M. Laforest, J.C. Boileau and R. Laflamme (2005). “Experimental implementation of a discrete-time quantum random walk on an NMR quantum-information processor”. Physical Review A, 72: 6, 062317.DOI: 10.1103/PhysRevA.72.062317Google Scholar
  13. L. K. Grover (1996). “A fast quantum mechanical algorithm for database search”, in: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, 1996 Jul 1, pp. 212–219.DOI: 10.1145/237814.237866Google Scholar
  14. G.L. Long (2001). “Grover algorithm with zero theoretical failure rate”. Physical Review A, 64: 2, 022307.DOI: 10.1103/PhysRevA.64.022307Google Scholar
  15. G. Li and L. Li, “Deterministic quantum search with adjustable parameters: Implementations and applications”. Information and Computation, 292, 105042.DOI: 10.1016/j.ic.2023.105042Google Scholar
  16. A. Ambainis, J. Kempe and A. Rivosh (2005). “Coins make quantum walks faster”, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, USA, 1099–1108.Google Scholar
  17. T.G. Wong (2015). “Grover search with lackadaisical quantum walks”. Journal of Physics A: Mathematical and Theoretical, 48: 43, 435304.DOI: 10.1088/1751-8113/48/43/435304Google Scholar
  18. G.A. Bezerra, P.H.G. Lugão and R. Portugal (2021). “Quantum-walk-based search algorithms with multiple marked vertices”. Physical Review A, 103: 6, 062202.DOI: 10.1103/PhysRevA.103.062202Google Scholar
  19. M. Roget, H. Kadri and G. Di Molfetta (2023). “Optimality conditions for spatial search with multiple marked vertices”. Physical Review Research, 5: 3, 033021.DOI: 10.1103/PhysRevResearch.5.033021Google Scholar
  20. S. Chakraborty, L. Novo and J. Roland (2020). “Optimality of spatial search via continuous-time quantum walks”. Physical Review A, 102: 3, 032214.DOI: 10.1103/PhysRevA.102.032214Google Scholar
  21. S. Marsh and J.B. Wang (2021). “Deterministic spatial search using alternating quantum walks,” Physical Review A 104: 2, 022216.DOI: 10.1103/PhysRevA.104.022216Google Scholar
  22. D. Qu, S. Marsh, K. Wang, L. Xiao, J. Wang and P. Xue (2022). “Deterministic search on star graphs via quantum walks”. Physical Review Letters, 128: 5, 050501.DOI: 10.1103/PhysRevLett.128.050501Google Scholar
  23. Q. Wang, Y. Jiang, S. Feng, et al. (2023). “Universal approach to deterministic spatial search via alternating quantum walks”. arxiv preprint arxiv:2307.16133.Google Scholar
  24. F. Peng, M. Li and X. Sun (2024). “Deterministic discrete-time quantum walk search on complete bipartite graphs”. Physical Review Research, 6: 3, 033042.DOI: 10.1103/PhysRevResearch.6.033042Google Scholar
  25. Z. Gong, S. Liu, Y. Wen, et al. (2016). “Biclique cryptanalysis using balanced complete bipartite subgraphs”. Science China. Information Sciences, 59: 4, 049101.DOI: 10.1007/s11432-016-5540-xGoogle Scholar
  26. M. Štefaòák and S. Skoupı (2017). “Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs”. Quantum Information Processing, 16, 1–14.DOI: 10.1007/s11128-017-1516-zGoogle Scholar
  27. R.A.M. Santos (2022). “Quantum state transfer on the complete bipartite graph”. Journal of Physics A: Mathematical and Theoretical 55: 12, 125301.DOI: 10.1088/1751-8121/ac5217Google Scholar
  28. T.G. Wong, L. Tarrataca and N. Nahimov (2016). “Laplacian versus adjacency matrix in quantum walk search”. Quantum Information Processing, 5, 4029–4048.DOI: 10.1007/s11128-016-1373-1Google Scholar
  29. M.L. Rhodes and T.G. Wong (2019). “Quantum walk search on the complete bipartite graph”. Physical Review A, 99: 3, 032301.DOI: 10.1103/PhysRevA.99.032301Google Scholar
  30. R. Beals, H. Buhrman, R. Cleve, et al. (2001). “Quantum lower bounds by polynomials”. Journal of the ACM (JACM), 48: 4, 778–797.DOI: 10.1145/502090.502097Google Scholar
  31. Y. Xu, D. Zhang and L. Li (2022). “Robust quantum walk search without knowing the number of marked vertices”. Physical Review A 106: 5, 052207.DOI: 10.1103/PhysRevA.106.052207Google Scholar
  32. M.A. Nielsen and I.L. Chuang (2010). Quantum Computation and Quantum Information. Cambridge University Press.Google Scholar
  33. G.A. Bezerra, R.A. Santos and R. Portugal (2023). “Quantum counting on the complete bipartite graph”. arxiv preprint arXiv:2311.10407[quant-ph].DOI: 10.1142/S0219749924500278Google Scholar
  34. G. Brassard, P. Hoyer, M. Mosca, and A. Tapp (2002). “Quantum amplitude amplification and estimation”. Contemporary Mathematics, 305, 53–74.DOI: 10.1090/conm/305/05215Google Scholar
  35. T. Loke and J.B. Wang (2017). “Efficient quantum circuits for continuous-time quantum walks on composite graphs”. Journal of Physics A: Mathematical and Theoretical, 50: 5, 055303.DOI: 10.1088/1751-8121/aa53a9Google Scholar
  36. D.W. Berry, A.M. Childs, R. Cleve, R. Kothari and R.D. Somma (2014). “Exponential improvement in precision for simulating sparse Hamiltonians”, in: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pp. 283–292.DOI: 10.1145/2591796.2591854Google Scholar
  37. https://qiskit.qotlabs.org/api/qiskit/0.45/qiskit.primitives.SamplerGoogle Scholar
  38. https://qiskit.github.io/qiskit-aer/Google Scholar
  39. https://github.com/ScarletLynn1998/Paper-Code-for-Deterministic-Search-on-Complete-Bipartite-Graphs-by-Continuous-Time-Quantum-WalkGoogle Scholar
  40. W. Chu-Ryang (2019). Simpler quantum counting. Quantum Information & Computation, 19, 967–983DOI: 10.26421/QIC19.11-12-5Google Scholar
  41. S. Aaronson and P. Rall (2020). “Quantum approximate counting, simplified”, in Symposium on Simplicity in Algorithms. Society for Industrial and Applied Mathematics, 24–32.DOI: 10.1137/1.9781611976014.5Google Scholar
  42. Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera and N. Yamamoto (2020). “Amplitude estimation without phase estimation”. Quantum Information Processing, 19, 1–7.DOI: 10.1007/s11128-019-2565-2Google Scholar
  43. D. Grinko, J. Gacon, C. Zoufal and S. Woerner. (2021). “Iterative quantum amplitude estimation”. NPJ Quantum Information, 7: 1, 52.DOI: 10.1038/s41534-021-00379-1Google Scholar