Algebraic graph theory and quantum walks

代数图论和量子行走之间的相互作用是本提案的主题。图上的连续时间量子行走是一种依赖时间的进化，由Schrödinger方程给出，该方程使用哈密顿量，哈密顿量是与图相关的矩阵。2003年，Childs等人给出了一种基于量子行走的算法，该算法解决神谕问题的速度比任何经典算法都要快。连续时间量子行走也可以看作是量子计算的通用原语。给定一个初始顶点，图上的量子行走给出了在任何给定时间测量返回顶点的概率分布。我们感兴趣的是三种特殊分布，它们对应于完全状态转移、分数还原和均匀混合现象。如果从一个顶点开始的行走返回第二个顶点的概率为1，则图具有两个顶点之间的完美状态转移。这种现象允许信息从初始顶点传输到另一个具有保真度的顶点。这种转移很重要，因为不可克隆定理说不可能复制量子态。具有完全状态转移的图很少，因此我们考虑一种称为分数恢复的松弛。如果从一个顶点开始的遍历以1的概率返回初始顶点或第二个顶点，则在两个顶点之间发生分数恢复。除了状态转移之外，分数恢复还可以用于产生纠缠，这是量子计算中有用的资源。我以前的工作为研究图中的分数复活奠定了基础。我们打算继续这方面的研究，包括寻找更多具有分数复活的图，并研究由此产生的图的性质。相比之下，均匀混合要求行走在顶点集上具有均匀的概率分布。在均匀混合时，行走的过渡矩阵给出了一个复杂的Hadamard矩阵，这是其他数学领域感兴趣的对象。大多数已知的均匀混合图来自于关联方案。我们提出在关联方案中搜索具有均匀混合的复Hadamard矩阵和图。我们计划研究具有均匀混合的图的表征。量子行走是量子算法发展的重要工具，量子行走的进展将影响量子计算领域。由于量子行走的哈密顿量是一个图矩阵，代数图理论提供了自然而强大的工具。另一方面，本研究也产生了一些有趣的图论问题。量子行走是一个活跃且不断发展的领域，在Mathscinet上搜索2019年的量子行走，返回了52篇文章。该项目的跨学科性质将促进计算机科学家、数学家和物理学家之间的合作，并吸引来自不同背景的学生。

The interplay between algebraic graph theory and quantum walks is the theme of this proposal. The continuous-time quantum walk on a graph is a time dependent evolution, given by the Schrödinger equation using a Hamiltonian which is a matrix associated with the graph. In 2003, Childs et al. gave a quantum walk based algorithm that solves an oracular problem exponentially faster than any classical algorithm. Continuous-time quantum walks can also be viewed as a universal primitive for quantum computation.  Given an initial vertex, the quantum walk on a graph gives a probability distribution on the vertices being returned at a measurement at any given time. We are interested in three special distributions corresponding to phenomena called perfect state transfer, fractional revival and uniform mixing. A graph has perfect state transfer between two vertices if there is a time when the walk starting from one vertex returns the second vertex with probability one. This phenomenon allows information transfer from the initial vertex to the other with fidelity one. This transfer is important since the no-cloning theorem says it is impossible to copy a quantum state. Graphs with perfect state transfer are rare, hence we consider a relaxation called fractional revival. Fractional revival occurs between two vertices if there is a time when the walk starting from one vertex returns the initial or the second vertex with probability one. In addition to state transfer, fractional revival can be used to generate entanglement, which is a useful resource in quantum computing. My previous work has laid the groundwork to study fractional revival in graphs. We propose to continue this research which include finding more graphs with fractional revival and investigating the graph properties arising from this phenomenon. In contrast, uniform mixing requires the walk to have uniform probability distribution on the vertex set. At the time of uniform mixing, the transition matrix of the walk gives a complex Hadamard matrix, which is an object of interest in other areas of mathematics. Most known graphs with uniform mixing come from association schemes. We propose to search for both complex Hadamard matrices and graphs with uniform mixing in association schemes. We plan to work towards a characterization of graphs having uniform mixing. Quantum walks are a major tool in the development of quantum algorithms, progress on quantum walks will impact the area of quantum computing. Since the Hamiltonian of a quantum walk is a graph matrix, algebraic graph theory provides natural and powerful tools. On the other hand, there are interesting graph theoretic problems arising from this research. Quantum walk is an active and growing area, a Mathscinet search on quantum walk for 2019 returned 52 articles. The interdisciplinary nature of this project will foster collaborations among computer scientists, mathematicians and physicists, and attract students from different backgrounds.