Quantum walks and graph spectra

量子行走和图谱

• 批准号: RGPIN-2017-04214
• 负责人: Godsil, Chris
• 金额: $ 3.64万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=709979
• 关键词: Quantum; walks; graph; spectra

Physicists, computer scientists and mathematicians are working to decide how we may best make use of quantum computers. Here the basic problems are to work out what we might do with a quantum computer that we cannot do equally well with the ordinary computers already on our desks, and what their limitations might be. The goal of my project is develop the theory of objects known as quantum walks, which can be viewed as subroutines in a quantum computer. These walks come in many variants, but in each case they are based on an underlying network or graph. In the most general terms, the goal of my project is to develop our understanding of the relation between the properties of the walk and the properties of the underlying graph. I hope to develop the theory to the point where we can produce quantum algorithms for determining properties of the underlying graph. I expect our work will also lead us to develop limits on just what is possible using these walks. Physicists have proposed algorithms for solving the graph isomorphism problem, an important problem in computing. I and members of my team have shown that most of these proposals do not work. We would like to go further and show that there are no natural modifications of these algorithms that work.

物理学家，计算机科学家和数学家正在努力决定我们如何最好地利用量子计算机。这里的基本问题是，我们可以用量子计算机做什么，而我们不能用我们桌上的普通计算机做得同样好，以及它们的局限性可能是什么。 我的项目的目标是发展被称为量子行走的对象理论，它可以被视为量子计算机中的子程序。这些遍历有许多变体，但在每种情况下，它们都基于底层网络或图。在最一般的术语中，我的项目的目标是发展我们对行走的属性和底层图的属性之间关系的理解。我希望将理论发展到我们可以产生量子算法来确定底层图形的属性的程度。 我希望我们的工作也将引导我们开发限制什么是可能使用这些步行。图同构问题是计算中的一个重要问题，物理学家已经提出了解决这个问题的算法。我和我的团队成员已经证明，这些建议中的大多数都行不通。我们想进一步证明，这些算法没有自然的修改。