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

AF：小：图同构和任意子的量子随机游走

• 批准号: 0916400
• 负责人: Paul Beame
• 金额: --
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-06-01 至 2013-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916400&HistoricalAwards=false
• 关键词: AF; Small; Graph; Isomorphism; Quantum

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.

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