Lackadaisical discrete-time quantum walk on Johnson graph. (English) Zbl 07820913
Summary: Quantum walk is widely used in search problems, and it has an ideal acceleration effect compared with classical algorithm. Suppose there is a marked vertex \(w\) on Johnson graph \(J(n, k)\), we hope to find \(w\) using quantum walk. We adopt the coined quantum walk model, and we have proved that, for fixed order \(k\), lackadaisical discrete-time quantum walk (DTQW) can find \(w\) with success probability \(1 - o(1)\), keeping a quadratic speedup. Before this paper, the best result of DTQW is that discrete-time quantum walk finds \(w\) with success probability \(\frac{1}{2} - o(1)\). We improve the success probability to \(1 - o(1)\) by adding self-loops with proper weights and choose the appropriate oracle operator. Our result also matches the result of continuous-time quantum walk.
MSC:
| 82-XX | Statistical mechanics, structure of matter |
References:
| [1] | Chakraborty, Shantanav; Novo, Leonardo; Ambainis, Andris; Omar, Yasser, Spatial search by quantum walk is optimal for almost all graphs. Phys. Rev. Lett., 10 (2016) |
| [2] | Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis, Quadratic speedup for finding marked vertices by quantum walks, in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, pp. 412-424. · Zbl 07298258 |
| [3] | Apers, Simon; Chakraborty, Shantanav; Novo, Leonardo; Roland, Jérémie, Quadratic speedup for spatial search by continuous-time quantum walk. Phys. Rev. Lett., 16 (2022) |
| [4] | Štefaňák, Martin; Skoupỳ, S., Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs. Phys. Rev. A, 2 (2016) |
| [5] | Skoupỳ, S.; Štefaňák, M., Quantum-walk-based state-transfer algorithms on the complete M-partite graph. Phys. Rev. A, 4 (2021) |
| [6] | Childs, Andrew M., Universal computation by quantum walk. Phys. Rev. Lett., 18 (2009) |
| [7] | Lovett, Neil B.; Cooper, Sally; Everitt, Matthew; Trevers, Matthew; Kendon, Viv, Universal quantum computation using the discrete-time quantum walk. Phys. Rev. A, 4 (2010) |
| [8] | Underwood, Michael S.; Feder, David L., Universal quantum computation by discontinuous quantum walk. Phys. Rev. A, 4 (2010) |
| [9] | Childs, Andrew M.; Gosset, David; Webb, Zak, Universal computation by multiparticle quantum walk. Science, 6121, 791-794 (2013) · Zbl 1355.68101 |
| [10] | Tanaka, Hajime; Sabri, Mohamed; Portugal, Renato, Spatial search on Johnson graphs by discrete-time quantum walk. J. Phys. A, 25 (2022) · Zbl 1507.81102 |
| [11] | Strauch, Frederick W., Connecting the discrete-and continuous-time quantum walks. Phys. Rev. A, 3 (2006) |
| [12] | Childs, Andrew M., On the relationship between continuous-and discrete-time quantum walk. Comm. Math. Phys., 581-603 (2010) · Zbl 1207.81029 |
| [13] | Coutinho, Gabriel; Portugal, Renato, Discretization of continuous-time quantum walks via the staggered model with Hamiltonians. Nat. Comput., 2, 403-409 (2019) · Zbl 1530.81041 |
| [14] | Wong, Thomas G.; Tarrataca, Luís; Nahimov, Nikolay, Laplacian versus adjacency matrix in quantum walk search. Quantum Inf. Process., 4029-4048 (2016) · Zbl 1348.81188 |
| [15] | Meyer, David A., On the absence of homogeneous scalar unitary cellular automata. Phys. Lett. A, 5, 337-340 (1996) · Zbl 1037.82529 |
| [16] | Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani, Quantum walks on graphs, in: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 50-59. · Zbl 1323.81020 |
| [17] | Szegedy, Mario, Quantum speed-up of Markov chain based algorithms, 32-41 |
| [18] | Portugal, Renato; Santos, Raqueline A. M.; Fernandes, Tharso D.; Gonçalves, Demerson N., The staggered quantum walk model. Quantum Inf. Process., 85-101 (2016) · Zbl 1333.81213 |
| [19] | Grover, Lov K., Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 2, 325 (1997) |
| [20] | Aaronson, Scott; Ambainis, Andris, Quantum search of spatial regions, 200-209 |
| [21] | Childs, Andrew M.; Goldstone, Jeffrey, Spatial search by quantum walk. Phys. Rev. A, 2 (2004) |
| [22] | Janmark, Jonatan; Meyer, David A.; Wong, Thomas G., Global symmetry is unnecessary for fast quantum search. Phys. Rev. Lett., 21 (2014) |
| [23] | Shenvi, Neil; Kempe, Julia; Whaley, K. Birgitta, Quantum random-walk search algorithm. Phys. Rev. A, 5 (2003) |
| [24] | Ambainis, Andris; Kempe, Julia; Rivosh, Alexander, Coins make quantum walks faster, 1099-1108 · Zbl 1297.68076 |
| [25] | Potoček, Václav; Gábris, Aurél; Kiss, Tamás; Jex, Igor, Optimized quantum random-walk search algorithms on the hypercube. Phys. Rev. A, 1 (2009) |
| [26] | László Babai, Graph isomorphism in quasipolynomial time, in: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, 2016, pp. 684-697. · Zbl 1376.68058 |
| [27] | Ambainis, Andris, Quantum walk algorithm for element distinctness. SIAM J. Comput., 1, 210-239 (2007) · Zbl 1134.81010 |
| [28] | Cao, Wei-Feng; Zhang, Yong-Ce; Yang, Yu-Guang; Li, Dan; Zhou, Yi-Hua; Shi, Wei-Min, Constructing quantum hash functions based on quantum walks on Johnson graphs. Quantum Inf. Process., 1-11 (2018) · Zbl 1433.81063 |
| [29] | Wong, Thomas G., Quantum walk search on Johnson graphs. J. Phys. A, 19 (2016) · Zbl 1342.81093 |
| [30] | Tanaka, Hajime; Sabri, Mohamed; Portugal, Renato, Spatial search on Johnson graphs by continuous-time quantum walk. Quantum Inf. Process., 2, 74 (2022) |
| [31] | Lugão, Pedro H. G.; Portugal, Renato; Sabri, Mohamed; Tanaka, Hajime, Multimarked spatial search by continuous-time quantum walk (2022), arXiv preprint arXiv:2203.14384 |
| [32] | Xue, Xi-ling; Ruan, Yue; Liu, Zhi-hao, Discrete-time quantum walk search on Johnson graphs. Quantum Inf. Process., 1-10 (2019) |
| [33] | Wong, Thomas G., Grover search with lackadaisical quantum walks. J. Phys. A, 43 (2015) · Zbl 1326.81053 |
| [34] | Wong, Thomas G., Faster search by lackadaisical quantum walk. Quantum Inf. Process., 1-9 (2018) · Zbl 1386.81051 |
| [35] | Rhodes, Mason L.; Wong, Thomas G., Search by lackadaisical quantum walks with nonhomogeneous weights. Phys. Rev. A, 4 (2019) |
| [36] | Rhodes, Mason L.; Wong, Thomas G., Search on vertex-transitive graphs by lackadaisical quantum walk. Quantum Inf. Process., 1-16 (2020) · Zbl 1509.81494 |
| [37] | Høyer, Peter; Yu, Zhan, Analysis of lackadaisical quantum walks. Quantum Inf. Comput., 1137-1152 (2020) |
| [38] | Cohen, A. M.; Brouwer, A. E.; Neumaier, A., Distance-regular graphs. Modern Surveys Math. (1989) · Zbl 0747.05073 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
