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

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. AmbainisA. GilyénA. JefferyS. KokainisM. 2020 “Quadratic speedup for finding marked vertices by quantum walks”, in MakarychevK. MakarychevY. TulsianiM. KamathG. ChuzhoyJ. (eds), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing Jun 22 412 424 Search in Google 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. ApersS. ChakrabortyS. NovoL. RolandJ. 2022 “Quadratic speedup for spatial search by continuous-time quantum walk” Physical Review Letters 129 16 160502 Search in Google Scholar

3. A. Ambainis (2007). “Quantum walk algorithm for element distinctness”. SIAM Journal on Computing 37: 1, 210–239. AmbainisA. 2007 “Quantum walk algorithm for element distinctness” SIAM Journal on Computing 37 1 210 239 Search in Google 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. GambleJ.K. FriesenM. ZhouD. JoyntR. CoppersmithS.N. 2010 “Two-particle quantum walks applied to the graph isomorphism problem” Physical Review A 81 5 052313 Search in Google 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. AharonovD. AmbainisA. KempeJ. 2001 “Quantum walks on graphs” in Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing 50 59 Search in Google 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. TödtliB. LanerM. SemenovJ. 2016 “Continuous-time quantum walks on directed bipartite graphs” Physical Review A 94 5 052338 Search in Google 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. ChavesR. ChagasB. Coutinhoand G. 2023 “Why and how to add direction to a quantum walk” Quantum Information Processing 22 1 41 Search in Google Scholar

8. A.M. Childs (2009). “Universal computation by quantum walk”. Physical Review Letters, 102: 18, 180501. ChildsA.M. 2009 “Universal computation by quantum walk” Physical Review Letters 102 18 180501 Search in Google Scholar

9. A.M. Childs, D. Gosset and Z. Webb (2013). “Universal computation by multiparticle quantum walk”. Science, 339: 6121, 791–794. ChildsA.M. GossetD. WebbZ. 2013 “Universal computation by multiparticle quantum walk” Science 339 6121 791 794 Search in Google Scholar

10. M. Tamura, T. Mukaiyama and K. Toyoda (2020). “Quantum walks of a phonon in trapped ions”. Physical Review Letters, 124: 20, 200501. TamuraM. MukaiyamaT. ToyodaK. 2020 “Quantum walks of a phonon in trapped ions” Physical Review Letters 124 20 200501 Search in Google Scholar

11. J. Wang and K. Manouchehri (2013). Physical Implementation of Quantum Walks. Heidelberg: Springer Berlin, 10: 978–983. WangJ. ManouchehriK. 2013 Physical Implementation of Quantum Walks Heidelberg Springer Berlin 10 978 983 Search in Google 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. RyanC. A. LaforestM. BoileauJ.C. LaflammeR. 2005 “Experimental implementation of a discrete-time quantum random walk on an NMR quantum-information processor” Physical Review A 72 6 062317 Search in Google 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. GroverL. K. 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 212 219 Search in Google Scholar

14. G.L. Long (2001). “Grover algorithm with zero theoretical failure rate”. Physical Review A, 64: 2, 022307. LongG.L. 2001 “Grover algorithm with zero theoretical failure rate” Physical Review A 64 2 022307 Search in Google Scholar

15. G. Li and L. Li, “Deterministic quantum search with adjustable parameters: Implementations and applications”. Information and Computation, 292, 105042. LiG. LiL. “Deterministic quantum search with adjustable parameters: Implementations and applications” Information and Computation 292 105042 Search in Google 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. AmbainisA. KempeJ. RivoshA. 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 Search in Google Scholar

17. T.G. Wong (2015). “Grover search with lackadaisical quantum walks”. Journal of Physics A: Mathematical and Theoretical, 48: 43, 435304. WongT.G. 2015 “Grover search with lackadaisical quantum walks” Journal of Physics A: Mathematical and Theoretical 48 43 435304 Search in Google 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. BezerraG.A. LugãoP.H.G. PortugalR. 2021 “Quantum-walk-based search algorithms with multiple marked vertices” Physical Review A 103 6 062202 Search in Google 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. RogetM. KadriH. Di MolfettaG. 2023 “Optimality conditions for spatial search with multiple marked vertices” Physical Review Research 5 3 033021 Search in Google 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. ChakrabortyS. NovoL. RolandJ. 2020 “Optimality of spatial search via continuous-time quantum walks” Physical Review A 102 3 032214 Search in Google Scholar

21. S. Marsh and J.B. Wang (2021). “Deterministic spatial search using alternating quantum walks,” Physical Review A 104: 2, 022216. MarshS. WangJ.B. 2021 “Deterministic spatial search using alternating quantum walks,” Physical Review A 104 2 022216 Search in Google 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. QuD. MarshS. WangK. XiaoL. WangJ. XueP. 2022 “Deterministic search on star graphs via quantum walks” Physical Review Letters 128 5 050501 Search in Google 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. WangQ. JiangY. FengS. 2023 “Universal approach to deterministic spatial search via alternating quantum walks” arxiv preprint arxiv:2307.16133. Search in 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. PengF. LiM. SunX. 2024 “Deterministic discrete-time quantum walk search on complete bipartite graphs” Physical Review Research 6 3 033042 Search in Google 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. GongZ. LiuS. WenY. 2016 “Biclique cryptanalysis using balanced complete bipartite subgraphs” Science China. Information Sciences 59 4 049101 Search in Google 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. ŠtefaòákM. SkoupıS. 2017 “Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs” Quantum Information Processing 16 1 14 Search in Google 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. SantosR.A.M. 2022 “Quantum state transfer on the complete bipartite graph” Journal of Physics A: Mathematical and Theoretical 55 12 125301 Search in Google 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. WongT.G. TarratacaL. NahimovN. 2016 “Laplacian versus adjacency matrix in quantum walk search” Quantum Information Processing 5 4029 4048 Search in Google Scholar

29. M.L. Rhodes and T.G. Wong (2019). “Quantum walk search on the complete bipartite graph”. Physical Review A, 99: 3, 032301. RhodesM.L. WongT.G. 2019 “Quantum walk search on the complete bipartite graph” Physical Review A 99 3 032301 Search in Google 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. BealsR. BuhrmanH. CleveR. 2001 “Quantum lower bounds by polynomials” Journal of the ACM (JACM) 48 4 778 797 Search in Google 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. XuY. ZhangD. LiL. 2022 “Robust quantum walk search without knowing the number of marked vertices” Physical Review A 106 5 052207 Search in Google Scholar

32. M.A. Nielsen and I.L. Chuang (2010). Quantum Computation and Quantum Information. Cambridge University Press. NielsenM.A. ChuangI.L. 2010 Quantum Computation and Quantum Information Cambridge University Press Search in 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]. BezerraG.A. SantosR.A. PortugalR. 2023 “Quantum counting on the complete bipartite graph” arxiv preprint arXiv:2311.10407[quant-ph]. Search in Google Scholar

34. G. Brassard, P. Hoyer, M. Mosca, and A. Tapp (2002). “Quantum amplitude amplification and estimation”. Contemporary Mathematics, 305, 53–74. BrassardG. HoyerP. MoscaM. TappA. 2002 “Quantum amplitude amplification and estimation” Contemporary Mathematics 305 53 74 Search in Google 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. LokeT. WangJ.B. 2017 “Efficient quantum circuits for continuous-time quantum walks on composite graphs” Journal of Physics A: Mathematical and Theoretical 50 5 055303 Search in Google 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. BerryD.W. ChildsA.M. CleveR. KothariR. SommaR.D. 2014 “Exponential improvement in precision for simulating sparse Hamiltonians” in: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing 283 292 Search in Google Scholar

37. https://qiskit.qotlabs.org/api/qiskit/0.45/qiskit.primitives.Sampler https://qiskit.qotlabs.org/api/qiskit/0.45/qiskit.primitives.Sampler Search in Google Scholar

38. https://qiskit.github.io/qiskit-aer/ https://qiskit.github.io/qiskit-aer/ Search in Google Scholar

39. https://github.com/ScarletLynn1998/Paper-Code-for-Deterministic-Search-on-Complete-Bipartite-Graphs-by-Continuous-Time-Quantum-Walk https://github.com/ScarletLynn1998/Paper-Code-for-Deterministic-Search-on-Complete-Bipartite-Graphs-by-Continuous-Time-Quantum-Walk Search in Google Scholar

40. W. Chu-Ryang (2019). Simpler quantum counting. Quantum Information & Computation, 19, 967–983 Chu-RyangW. 2019 Simpler quantum counting Quantum Information & Computation 19 967 983 Search in Google 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. AaronsonS. RallP. 2020 “Quantum approximate counting, simplified” in Symposium on Simplicity in Algorithms Society for Industrial and Applied Mathematics, 24 32 Search in Google 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. SuzukiY. UnoS. RaymondR. TanakaT. OnoderaT. YamamotoN. 2020 “Amplitude estimation without phase estimation” Quantum Information Processing 19 1 7 Search in Google Scholar

43. D. Grinko, J. Gacon, C. Zoufal and S. Woerner. (2021). “Iterative quantum amplitude estimation”. NPJ Quantum Information, 7: 1, 52. GrinkoD. GaconJ. ZoufalC. WoernerS. 2021 “Iterative quantum amplitude estimation” NPJ Quantum Information 7 1 52 Search in Google Scholar