Quantum walks and graph spectra

量子行走和图谱

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

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