AF: Small: Graph Isomorphism and Quantum Random Walks by Anyons

量子计算机提供了以指数方式加速某些经典计算难题的解决方案的潜力。 例如，众所周知，量子计算机可以有效地分解数字（这是现代计算机无法做到的），这一事实意味着量子计算机可以破解保护我们国家网络基础设施的大多数密码系统。 量子因子分解算法是当前实际构建量子计算机研究背后的主要动机。 在这项研究中，研究人员提出了一种新的方法来有效地解决计算问题-图同构问题-这也可能承认一个指数加速超过最好的经典算法的问题。 图同构问题是判断两个给定的图（一个顶点的集合，边连接它们）是否可以通过置换不同的顶点来使它们看起来彼此相同。 这里所采用的方法与大多数量子算法社区所采用的方法不同，并且集中在一类新的量子随机行走上，其中行走者携带拓扑量子数。 这种方法是从一系列失败的建议，以图形同构的基础上随机行走的核心玻色子或费米子，是由这些建议失败的形式的动机。 为图同构问题找到一个有效的量子算法将具有潜在的变革性，并将为构建大型量子计算机提供一个重要的新理由。 PI选择的方法还引入了一种新的量子算法技术--任意子的量子随机行走--它有可能在图同构问题之外的原始问题中发挥作用。 最后，该奖项将用于支持研究生谁在计算机科学和物理学之间的边界工作的培训，从而加强跨学科鸿沟的连接。

Quantum computers offer the potential to exponentially speed up the solution of certain classically hard computational problems. It is already known, for example, that quantum computers can efficiently factor numbers (something modern computers cannot do), and this fact implies that quantum computers can break the majority of cryptographic systems which protect our nation's cyber-infrastructure. The quantum factoring algorithm is the main motivation behind current research into actually building a quantum computer. In this grant, the investigator proposes a new approach to efficiently solving a computational problem--the graph isomorphism problem--which might also admit an exponential speedup over the best classical algorithm for the problem. The graph isomorphism problem is to tell whether two given graphs (a collection of vertices with edges connecting them) can be made to look identical to each other by permuting the different vertices. The approach taken here is different from that taken by the majority of the quantum algorithms community and centers on a novel class of quantum random walks, those in which the walkers carry topological quantum numbers. This approach follows from a series of failed proposals to graph isomorphism based on random walks by hard-core bosons or fermions and is motivated by the form in which these proposals fail. Finding an efficient quantum algorithm for the graph isomorphism problem would be potentially transformative and would provide a major new justification for building a large quantum computer. The approach chosen by the PI also introduces a novel quantum algorithm technique--quantum random walks by anyons--which has the potential to be useful a primitive outside of the graph isomorphism problem. Finally, the award will be used to support the training of graduate students who work on the boundary between computer science and physics, and thus strengthen connections across this interdisciplinary divide.