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.