Quantum walks and 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.