标题： 多粒子量子漫步用于区分困难图 显示英文标题

标题： Multiparticle quantum walks for distinguishing hard graphs

摘要： 量子随机游走已被证明是在图上执行某些任务（如数据库搜索、量子模拟等）的强大量子算法。 在本工作中，我们关注其在图同构问题中的应用。 特别是我们研究如何比较多粒子量子游走和著名的经典WL测试，以及量子游走如何用来区分像CFI图这样的困难图，而k-WL测试无法区分这些图。 我们提供了理论证明和实证结果，以表明具有输入叠加态的k-QW可以区分k-CFI图。 此外，我们还证明了具有局域输入态的k-1 QW可以区分k-CFI图。 我们还证明了一些关于强正则图（SRGs）的附加结果。 显示英文摘要

摘要： Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs).