其他
专题丨量子游走相关算法研究进展
作者简介
李萌
中国科学院计算技术研究所特别研究助理，主要从事量子游走理论及其应用、量子计算与量子信息领域研究工作。孙晓明
中国科学院计算技术研究所研究员，量子计算与算法理论实验室主任，主要从事量子计算、算法复杂性、社会网络近似算法、通信复杂性、判定树复杂性、组合数学等领域研究工作。论文引用格式：
李萌, 孙晓明. 量子游走相关算法研究进展[J]. 信息通信技术与政策, 2022,48(7):28-36.
量子游走相关算法研究进展
李萌1 孙晓明1,2
（1.中国科学院计算技术研究所 处理器芯片全国重点实验室，北京 100190；2.中国科学院大学，北京 100049）
摘要：量子游走是经典随机游走在量子世界的对应，已经被证明是一种通用的量子计算模型，也是设计高效量子算法和量子信息处理方案的基础工具之一。简要介绍了量子游走的概念和基本原理，阐述了量子游走在搜索问题及其他方面的一些重要应用，并总结和展望了量子游走的未来发展前景。
关键词：量子游走；量子算法；量子加速；量子应用
中图分类号：TP311.13；TP38；O413 文献标志码：A
引用格式：李萌, 孙晓明. 量子游走相关算法研究进展[J]. 信息通信技术与政策, 2022,48(7):28-36.
DOI：10.12267/j.issn.2096-5931.2022.07.005
0 引言
量子计算的发展趋势欣欣向荣，量子比特本身的存在就意味着相较于经典计算所具有的指数增加的运算空间和相应强大的并行性，有指数加速的潜力，未来能够被应用于密码破译、量子化学、工程计算、人工智能、材料模拟、金融经济等方面，甚至可以突破经典计算的瓶颈。虽然量子计算由于量子力学所特有的量子叠加和量子纠缠使得其在某些具体问题上的解决速度和效果大大提升，但如何发挥其并行优势，提高普遍计算力是当下最为关键的挑战之一。同时，真正通用的量子计算机还未建造成功，甚至一个在规模上有限制的通用物理设备仍有待设计和构建，量子计算优越性的充分体现更要依赖于量子算法的巧妙构思。
近年来量子算法的设计需要和应用需求不断增长。无论是有直接加速效果的，还是可以在带噪音中等规模量子设备（Noisy Intermediate-Scale Quantum Technology，NISQ）上运行展示优越性的量子算法，其研究从未中断。Shor算法在多项式时间内解决了大数因子分解问题[1]；Grover算法对于无结构数据库的搜索问题相较于经典算法可以达到平方加速的效果[2]。除了这些早期的著名量子算法，还有一类以量子游走为基础的量子算法在蓬勃发展，且在实验和应用方面展示出了巨大的活力和潜力。
经典的随机游走可以用作设计随机算法的计算框架，因此被广泛应用到包括计算机学科在内的许多学科中。量子游走刻画了微观世界中波函数的动力学演化过程，是经典随机游走在量子世界的对应和推广，但二者却很不一样。比如经典随机游走的概率分布是高斯型，而在量子情况下它具有多个峰值，不断震荡，扩散速度呈现平方式的增长。量子叠加和量子干涉特性使得量子游走有着显著区别于经典随机游走的优势。基于此可以利用量子游走开发高效量子算法，例如量子搜索算法、元素区分等，这些量子游走算法的性能表现相较于经典算法均会有加速效果。同时，随着研究的深入，量子游走陆续被证明是一种通用的量子计算模型。任何量子过程都可以理解为系统的动力学演化，进一步可以用量子游走来模拟。因此，量子游走为量子信息处理提供了一个直观的框架，是基础的量子算法设计工具之一，也是创新量子技术的核心之一[3-6]。
本文将首先介绍量子游走的基本概念和基本原理；然后介绍基于量子游走的几种搜索算法的发展，以及量子游走在其他相关应用中的关键进展；最后对量子游走未来的发展进行总结和展望。
1 量子游走简介
经典随机游走在数学上刻画了一系列随机步骤演变的过程。这一随机过程通常被描述为马尔可夫过程，游走者的下一个位置只取决于它当前的位置，不依赖于游走者之前时刻的任何信息。像花粉的布朗运动、波动的股票价格，以及高尔顿钉板和醉汉问题均属于经典随机游走。在经典的随机游走中，游走者本身占据一定的状态，状态间的随机跃迁导致了随机性的产生。这一概念最初由Pearson引入[7]，随后逐渐被用作计算机科学和各类算法发展的基本框架之一，且在计算机科学中有着广泛的应用，比如PageRank[8]、计算机视觉[9]和复杂社交网络分析[10]等。
Aharonov等人于1993年将量子物理与经典随机游走结合起来，首次提出量子游走模型[11]。量子状态的叠加和确定可逆的酉演化产生了随机性。与经典随机游走类似，量子游走可以分为离散时间量子游走和连续时间量子游走，二者在具体形式上有明显的差异。相比于连续时间量子游走，量子硬币为离散时间量子游走提供了额外的自由度，因此二者在性质上也有一定的差异和联系[12]。下面对二者做一些简单刻画[13]。
2 基于量子游走的搜索算法
空间搜索问题是利用经典随机游走来解决的一类常见问题。在这类问题中，无向图G中有一个由标记顶点组成的顶点子集M，游走的方式由无向图G的边决定。空间搜索问题的目标是通过沿着图的边对图遍历以期用最短的时间来找到其中一个被标记的顶点。寻找标记顶点的一个简单策略是对图G进行随机游走，反复应用一些随机矩阵，直到达到其中一个标记顶点。相应地，量子游走也被用来解决空间搜索问题，并相较经典随机游走情形有一定的加速效果。这里将对两种关键框架（基于马尔可夫链的和基于不同图结构的）下量子游走搜索算法的由来、发展和现状做简要介绍。
Feynman为了给量子计算机这种计算设备提供一个物理上合理的描述，构造了一个哈密顿量来实现任意量子电路[35]。Childs扩展了Feynman的这一结果，首次证明了连续时间量子游走是一种通用的计算模型，即量子游走和量子电路本质上具有同样的能力，任意一个可以用通用量子计算机完成的任务也可以利用连续时间量子游走来完成[36]。事实上，对于一般的连续时间量子游走模型加以限制，即在稀疏图（低度的非加权图）上的量子游走对于量子计算均是通用的。Childs用虚拟量子线来表示计算基态，并通过散射理论讨论连接在导线上的小部件实现了3 个量子门，即受控非门、π/8门和交换两个计算基的量子门。π/8门和交换两个计算基的量子门连续作用可以生成阿达玛门，而受控非门，阿达玛门和π/8门构成了一组通用量子门集合，故稀疏图上的连续时间量子游走可以有效地模拟任何量子电路，从而是一种通用的计算模型。
但是，用于对n个量子比特进行计算的图的规模关于n是指数级别的，而图中的各个顶点占据不同的空间位置，故量子游走不能有效地实现。鉴于此，Childs等人考虑了以上连续时间量子游走模型的推广，其中有许多相互作用的游走者；利用散射理论证明了多粒子量子游走能够实现通用的量子计算[37]，此时仅使用了多项式大小的图，故较之文献[36]更易于实验实现，并且可以作为构建一个可伸缩的量子计算机的架构，而不需要依赖时间的控制。
Lovett等人利用离散时间量子游走代替连续量子游走[36]，给出了一组同样的通用门集的等价构造，即受控非门、阿达玛门和π/8门，由此证明了离散时间量子游走和连续时间量子游走都是计算元件，具有通用性[38]。在连续时间量子游走的情况下[36]，图中任意顶点的最大度为3。而在离散时间的情况下，要用具有更高度的顶点来确保定向传播[38]。
除了以上利用量子游走在各个节点动态调控硬币操作来实现完美状态传输的方法以外，量子游走搜索算法也可以用来实现完美状态传输这一协议。考虑有两个标记顶点（发送点和接收点）的量子游走搜索算法，通过在标记顶点和非标记顶点处分别选取合适的硬币操作，可以较高概率地从发送顶点到达接收顶点。Štefaňák等人讨论了星形图和带自环的完全图上的状态传输[52]。完全二部图[53-54]和完全多部图[55]上的完美状态传输也陆续得到分析。此外，在纠缠交换框架下，量子游走可以避开联合贝尔测量实现难这一瓶颈，在远距离几方之间实现纠缠的制备[56]。
4 结束语
量子游走作为一种有效的算法工具，本身具有强大的计算能力和应用潜力，在很多具体问题中的应用开发和算法设计都值得深入研究和探索。量子游走本身在实验方面的进展也令人欣喜，包括光子[57-59]、离子阱[60]、超导量子比特[61-62]和原子系统[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. Searchvia quantum walk[J]. SIAM Journal on Computing,2011,40(1):142-164. [17] MAGNIEZ F, NAYAK A, RICHER P C, et al. On thehitting times of quantum versus random walks[J]. Algorithmica, 2012,63(1):91-116. [18] KROVI H, MAGNIEZ F, OZOLS M, et al. Quantumwalks can find a marked element on any graph[J]. Algorithmica, 2016,74(2):851-907. [19] DOHOTARU C, HØYER P. Controlled quantumamplification[C]//44th International Colloquium onAutomata, Languages, and Programming (ICALP2017), 2017. [20] AMBAINIS A, KEMPE J, RIVOSH A. Coins makequantum walks faster. 16th Annual ACM-SIAMSymposium on Discrete Algorithms, 2005:1099-1108. [21] AARONSON S, AMBAINIS A. Quantum search ofspatial regions[C]//44th Annual IEEE Symposium onFoundations of Computer Science, 2003. Proceedings. IEEE, 2003:200-209. [22] CHILDS A M, GOLDSTONE J. Spatial search byquantum walk[J]. Physical Review A, 2004, 70(2):022314. [23] TULSI A. Faster quantum-walk algorithm for the twodimensional spatial search[J]. Physical Review A, 2008,78(1):012310. [24] HOYER P, KOMEILI M. Efficient qantum walk on thegrid with multiple marked elements[C]//34thSymposium 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 byquantum walks[C]//Proceedings of the 52nd AnnualACM SIGACT Symposium on Theory of Computing, 2020:412-424. [26] RHODES M L, WONG T G. Quantum walk search onthe complete bipartite graph[J]. Physical Review A, 2019,99(3):032301. [27] RHODES M L, WONG T G. Search by lackadaisicalquantum 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]. PhysicalReview A, 2018,98(1):012338. [29] TANAKA H, SABRI M, PORTUGAL R. Spatial searchon Johnson graphs by discrete-time quantum walk[J].Journal of Physics A: Mathematical andTheoretical, 2022. [30] JANMARK J, MEYER D A, WONG T G. Globalsymmetry 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 onComputational Complexity. IEEE, 2001:131-137. [32] AARONSON S, SHI Y. Quantum lower bounds for thecollision and the element distinctness problems[J]. Journal of the ACM (JACM), 2004,51(4):595-605. [33] AMBAINIS A. Quantum walk algorithm for elementdistinctness[J]. SIAM Journal on Computing, 2007,37(1):210-239. [34] MAGNIEZ F, SANTHA M, SZEGEDY M. Quantumalgorithms for the triangle problem[J]. SIAM Journalon 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. Universalcomputation 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-timequantum walk[J]. Physical Review A, 2010,81(4):042330. [39] UNDERWOOD M S, FEDER D L. Universal quantumcomputation by discontinuous quantum walk[J]. Physical Review A, 2010,82(4):042304. [40] KURZYN' SKI P, WÓJCIK A. Quantum walk as ageneralized measuring device[J]. Physical ReviewLetters, 2013,110(20):200404. [41] ZHAO Y, YU N, KURZYN' SKI P, et al. Experimental realization of generalized qubit measurements based onquantum walks[J]. Physical Review A, 2015,91(4):042101. [42] BIAN Z, LI J, QIN H, et al. Realization of single-qubitpositive-operator-valued measurement via a onedimensional photonic quantum walk[J]. PhysicalReview Letters, 2015,114(20):203602. [43] LI Z, ZHANG H, ZHU H. Implementation ofgeneralized 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. Deterministicrealization of collective measurements via photonicquantum walks[J]. Nature Communications, 2018,9(1):1-7. [45] WANG Y, SHANG Y, XUE P. Generalizedteleportation by quantum walks[J]. QuantumInformation Processing, 2017,16(9):1-13. [46] CHATTERJEE Y, DEVRARI V, BEHERA B K, et al.Experimental realization of quantum teleportation usingcoined quantum walks[J]. Quantum InformationProcessing, 2020,19(1):1-14. [47] LI H J, CHEN X B, WANG Y L, et al. A new kind offlexible quantum teleportation of an arbitrary multi-qubitstate by multi-walker quantum walks[J]. QuantumInformation Processing, 2019,18(9):1-16. [48] YALÇINKAYA I·, GEDIK Z. Qubit state transfer viadiscrete-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 transferand efficient quantum routing: a discrete-time quantumwalk approach[J]. Physical Review A, 2014,90(1):012331. [50] SHANG Y, WANG Y, LI M, et al. Quantumcommunication protocols by quantum walks with twocoins[J]. EPL ( Europhysics Letters ), 2019,124(6):60009. [51] SHANG Y, LI M. Experimental realization of statetransfer by quantum walks with two coins[J]. QuantumScience and Technology, 2019,5(1):015005. [52] ŠTEFANˇ ÁK M, SKOUPY' S. Perfect state transfer bymeans of discrete-time quantum walk search algorithmson highly symmetric graphs[J]. Physical Review A, 2016,94(2):022301. [53] ŠTEFANˇ ÁK M, SKOUPY' S. Perfect state transfer bymeans of discrete-time quantum walk on completebipartite graphs[J]. Quantum Information Processing, 2017,16(3):1-14. [54] SANTOS R A M. Quantum state transfer on thecomplete bipartite graph[J]. Journal of Physics A:Mathematical and Theoretical, 2022,55(12):125301. [55] SKOUP Y' S, ŠTEFA Nˇ A' K M. Quantum-walk-basedstate-transfer algorithms on the complete M-partite graph[J]. Physical Review A, 2021,103(4):042222. [56] LI M, SHANG Y. Entangled state generation viaquantum walks with multiple coins[J]. npj QuantumInformation, 2021,7(1):1-8. [57] CHEN C, DING X, QIN J, et al. Observation oftopologically protected edge states in a photonic twodimensional quantum walk[J]. Physical Review letters, 2018,121(10):100502. [58] TANG H, LIN X F, FENG Z, et al. Experimental twodimensional quantum walk on a photonic chip[J].Science Advances, 2018,4(5):eaat3174. [59] QIANG X, LOKE T, MONTANARO A, et al. Efficientquantum walk on a quantum processor[J]. NatureCommunications, 2016,7(1):1-6. [60] XUE P, SANDERS B C, LEIBFRIED D. Quantumwalk on a line for a trapped ion[J]. Physical ReviewLetters, 2009,103(18):183602. [61] YAN Z, ZHANG Y R, GONG M, et al. Stronglycorrelated quantum walks with a 12-qubit superconductingprocessor[J]. Science, 2019,364(6442):753-756. [62] GONG M, WANG S, ZHA C, et al. Quantum walks ona programmable two-dimensional 62-qubit superconductingprocessor[J]. Science, 2021,372(6545):948-952. [63] KARSKI M, FÖRSTER L, CHOI J M, et al. Quantumwalk in position space with single optically trapped atoms[J]. Science, 2009,325(5937):174-177.
Research progress on quantum walk related algorithms
LI Meng1, SUN Xiaoming1,2
(1. State Key Lab of Processors, Institute of Computing Technology, CAS, Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)
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.Keywords:quantum walk; quantum algorithm; quantum speed-up; quantum application
本文刊于《信息通信技术与政策》2022年 第7期
主办：中国信息通信研究院
《信息通信技术与政策》是工业和信息化部主管、中国信息通信研究院主办的专业学术期刊。本刊定位于“信息通信技术前沿的风向标，信息社会政策探究的思想库”，聚焦信息通信领域技术趋势、公共政策、 国家/产业/企业战略，发布前沿研究成果、焦点问题分析、热点政策解读等，推动5G、工业互联网、数字经济、人工智能、区块链、大数据、云计算等技术产业的创新与发展，引导国家技术战略选择与产业政策制定，搭建产、学、研、用的高端学术交流平台。
《信息通信技术与政策》官网开通啦！
为进一步提高期刊信息化建设水平，为广大学者提供更优质的服务，我刊于2020年11月18日起正式推出官方网站，现已进入网站试运行阶段。我们将以更专业的态度、更丰富的内容、更权威的报道，继续提供有前瞻性、指导性、实用性的优秀文稿，为建设网络强国和制造强国作出更大贡献！
推荐阅读
你“在看”我吗？