Research progress on quantum walk related algorithms

doi:10.12267/j.issn.2096-5931.2022.07.005

Abstract

Abstract:

Quantum walk is the analogy of classical random walk in the quantum world. It is a universal computing model and one of the key tools for designing efficient quantum algorithms and quantum information processing schemes. This paper briefly introduces the concepts and basic principles of quantum walk, expounds the key development nodes of quantum walk in search problems and other applications, and summarizes the prospect of quantum walk in the future.

Key words: quantum walk, quantum algorithm, quantum speed-up, quantum application

CLC Number:

LI Meng, SUN Xiaoming. Research progress on quantum walk related algorithms[J]. Information and Communications Technology and Policy, 2022, 48(7): 28-36.

Add to citation manager EndNote|Ris|BibTeX

URL:

http://ictp.caict.ac.cn/EN/10.12267/j.issn.2096-5931.2022.07.005

http://ictp.caict.ac.cn/EN/Y2022/V48/I7/28

References 63

[1]	SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2):303-332.
[2]	GROVER L K. A fast quantum mechanical algorithm for database search[C]// Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, 1996:212-219.
[3]	KADIAN K, GARHWAL S, KUMAR A. Quantum walk and its application domains: a systematic review[J]. Computer Science Review, 2021,41:100419.
[4]	VENEGAS-ANDRACA S E. Quantum walks: a comprehensive review[J]. Quantum Information Processing, 2012, 11(5):1015-1106.
[5]	SHAO C, LI Y, LI H. Quantum algorithm design: techniques and applications[J]. Journal of Systems Science and Complexity, 2019, 32(1):375-452.
[6]	KENDON V. Decoherence in quantum walks-a review[J]. Mathematical Structures in Computer Science, 2007, 17(6):1169-1220.
[7]	PEARSON K. The problem of the random walk[J]. Nature, 1905, 72(1865):294-294.
[8]	PAGE L, BRIN S, MOTWANI R, et al. The pagerank citation ranking: bringing order to the web[R]. Stanford InfoLab, 1999.
[9]	SHEN J, DU Y, WANG W, et al. Lazy random walks for superpixel segmentation[J]. IEEE Transactions on Image Processing, 2014, 23(4):1451-1462.
[10]	SARKAR P, MOORE A W. Random walks in social networks and their applications: a survey[M]//Social Network Data Analytics. Springer, Boston, MA, 2011:43-77.
[11]	AHARONOV Y, DAVIDOVICH L, ZAGURY N. Quantum random walks[J]. Physical Review A, 1993, 48(2):1687.
[12]	STRAUCH F W. Connecting the discrete-and continuous-time quantum walks[J]. Physical Review A, 2006, 74(3):030301.
[13]	KEMPE J. Quantum random walks: an introductory overview[J]. Contemporary Physics, 2003, 44(4):307-327.
[14]	PORTUGAL R. Quantum walks and search algorithms[M]. Springer, 2018.
[15]	SZEGEDY M. Quantum speed-up of Markov chain based algorithms[C]// 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2004:32-41.
[16]	MAGNIEZ F, NAYAK A, ROLAND J, et al. Search via quantum walk[J]. SIAM Journal on Computing, 2011, 40(1):142-164.
[17]	MAGNIEZ F, NAYAK A, RICHER P C, et al. On the hitting times of quantum versus random walks[J]. Algorithmica, 2012, 63(1):91-116.
[18]	KROVI H, MAGNIEZ F, OZOLS M, et al. Quantum walks can find a marked element on any graph[J]. Algorithmica, 2016, 74(2):851-907.
[19]	DOHOTARU C, HØYER P. Controlled quantum amplification[C]// 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), 2017.
[20]	AMBAINIS A, KEMPE J, RIVOSH A. Coins make quantum walks faster. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005:1099-1108.
[21]	AARONSON S, AMBAINIS A. Quantum search of spatial regions[C]// 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE, 2003:200-209.
[22]	CHILDS A M, GOLDSTONE J. Spatial search by quantum walk[J]. Physical Review A, 2004, 70(2):022314.
[23]	TULSI A. Faster quantum-walk algorithm for the two-dimensional spatial search[J]. Physical Review A, 2008, 78(1):012310.
[24]	HOYER P, KOMEILI M. Efficient qantum walk on the grid with multiple marked elements[C]// 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), 2017.
[25]	AMBAINIS A, GILYÉN A, JEFFERY S, et al. Quadratic speedup for finding marked vertices by quantum walks[C]// Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020:412-424.
[26]	RHODES M L, WONG T G. Quantum walk search on the complete bipartite graph[J]. Physical Review A, 2019, 99(3):032301.
[27]	RHODES M L, WONG T G. Search by lackadaisical quantum walks with nonhomogeneous weights[J]. Physical Review A, 2019, 100(4):042303.
[28]	WONG T G, WÜNSCHER K, LOCKHART J, et al. Quantum walk search on Kronecker graphs[J]. Physical Review A, 2018, 98(1):012338.
[29]	TANAKA H, SABRI M, PORTUGAL R. Spatial search on Johnson graphs by discrete-time quantum walk[J]. Journal of Physics A: Mathematical and Theoretical, 2022.
[30]	JANMARK J, MEYER D A, WONG T G. Global symmetry is unnecessary for fast quantum search[J]. Physical Review Letters, 2014, 112(21):210502.
[31]	BUHRMAN H, DURR C, HEILIGMAN M, et al. Quantum algorithms for element distinctness[C]// Proceedings 16th Annual IEEE Conference on Computational Complexity. IEEE, 2001:131-137.
[32]	AARONSON S, SHI Y. Quantum lower bounds for the collision and the element distinctness problems[J]. Journal of the ACM (JACM), 2004, 51(4):595-605.
[33]	AMBAINIS A. Quantum walk algorithm for element distinctness[J]. SIAM Journal on Computing, 2007, 37(1):210-239.
[34]	MAGNIEZ F, SANTHA M, SZEGEDY M. Quantum algorithms for the triangle problem[J]. SIAM Journal on Computing, 2007, 37(2):413-424.
[35]	FEYNMAN R P. Quantum mechanical computers[J]. Optics News, 1985, 11(2):11-20.
[36]	CHILDS A M. Universal computation by quantum walk[J]. Physical Review Letters, 2009, 102(18):180501.
[37]	CHILDS A M, GOSSET D, WEBB Z. Universal computation by multiparticle quantum walk[J]. Science, 2013, 339(6121):791-794.
[38]	LOVETT N B, COOPER S, EVERITT M, et al. Universal quantum computation using the discrete-time quantum walk[J]. Physical Review A, 2010, 81(4):042330.
[39]	UNDERWOOD M S, FEDER D L. Universal quantum computation by discontinuous quantum walk[J]. Physical Review A, 2010, 82(4):042304.
[40]	KURZYŃSKI P, WÓJCIK A. Quantum walk as a generalized measuring device[J]. Physical Review Letters, 2013, 110(20):200404.
[41]	ZHAO Y, YU N, KURZYŃSKI P, et al. Experimental realization of generalized qubit measurements based on quantum walks[J]. Physical Review A, 2015, 91(4):042101.
[42]	BIAN Z, LI J, QIN H, et al. Realization of single-qubit positive-operator-valued measurement via a one-dimensional photonic quantum walk[J]. Physical Review Letters, 2015, 114(20):203602.
[43]	LI Z, ZHANG H, ZHU H. Implementation of generalized measurements on a qudit via quantum walks[J]. Physical Review A, 2019, 99(6):062342.
[44]	HOU Z, TANG J F, SHANG J, et al. Deterministic realization of collective measurements via photonic quantum walks[J]. Nature Communications, 2018, 9(1):1-7.
[45]	WANG Y, SHANG Y, XUE P. Generalized teleportation by quantum walks[J]. Quantum Information Processing, 2017, 16(9):1-13.
[46]	CHATTERJEE Y, DEVRARI V, BEHERA B K, et al. Experimental realization of quantum teleportation using coined quantum walks[J]. Quantum Information Processing, 2020, 19(1):1-14.
[47]	LI H J, CHEN X B, WANG Y L, et al. A new kind of flexible quantum teleportation of an arbitrary multi-qubit state by multi-walker quantum walks[J]. Quantum Information Processing, 2019, 18(9):1-16.
[48]	YALÇINKAYA İ, GEDIK Z. Qubit state transfer via discrete-time quantum walks[J]. Journal of Physics A: Mathematical and Theoretical, 2015, 48(22):225302.
[49]	ZHAN X, QIN H, BIAN Z, et al. Perfect state transfer and efficient quantum routing: a discrete-time quantum-walk approach[J]. Physical Review A, 2014, 90(1):012331.
[50]	SHANG Y, WANG Y, LI M, et al. Quantum communication protocols by quantum walks with two coins[J]. EPL (Europhysics Letters), 2019, 124(6):60009.
[51]	SHANG Y, LI M. Experimental realization of state transfer by quantum walks with two coins[J]. Quantum Science and Technology, 2019, 5(1):015005.
[52]	ŠTEFAŇÁK M, SKOUPÝ S. Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs[J]. Physical Review A, 2016, 94(2):022301.
[53]	ŠTEFAŇÁK M, SKOUPÝ S. Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs[J]. Quantum Information Processing, 2017, 16(3):1-14.
[54]	SANTOS R A M. Quantum state transfer on the complete bipartite graph[J]. Journal of Physics A: Mathematical and Theoretical, 2022, 55(12):125301.
[55]	SKOUPÝ S, ŠTEFAŇÁK M. Quantum-walk-based state-transfer algorithms on the complete M-partite graph[J]. Physical Review A, 2021, 103(4):042222.
[56]	LI M, SHANG Y. Entangled state generation via quantum walks with multiple coins[J]. npj Quantum Information, 2021, 7(1):1-8.
[57]	CHEN C, DING X, QIN J, et al. Observation of topologically protected edge states in a photonic two-dimensional quantum walk[J]. Physical Review letters, 2018, 121(10):100502.
[58]	TANG H, LIN X F, FENG Z, et al. Experimental two-dimensional quantum walk on a photonic chip[J]. Science Advances, 2018, 4(5):eaat3174.
[59]	QIANG X, LOKE T, MONTANARO A, et al. Efficient quantum walk on a quantum processor[J]. Nature Communications, 2016, 7(1):1-6.
[60]	XUE P, SANDERS B C, LEIBFRIED D. Quantum walk on a line for a trapped ion[J]. Physical Review Letters, 2009, 103(18):183602.
[61]	YAN Z, ZHANG Y R, GONG M, et al. Strongly correlated quantum walks with a 12-qubit superconducting processor[J]. Science, 2019, 364(6442):753-756.
[62]	GONG M, WANG S, ZHA C, et al. Quantum walks on a programmable two-dimensional 62-qubit superconducting processor[J]. Science, 2021, 372(6545):948-952.
[63]	KARSKI M, FÖRSTER L, CHOI J M, et al. Quantum walk in position space with single optically trapped atoms[J]. Science, 2009, 325(5937):174-177.