Algebraic graph theory and quantum walks

代数图论和量子漫步之间的相互作用是这个提议的主题。图上的连续时间量子行走是一种依赖于时间的演化，由薛定谔方程使用与图相关联的矩阵哈密顿量给出。在2003年，查尔兹等人给出了一个基于量子行走的算法，该算法比任何经典算法都要快。连续时间量子行走也可以被看作是量子计算的一个通用原语。 给定一个初始顶点，图上的量子行走给出了在任何给定时间的测量中返回的顶点的概率分布。我们感兴趣的是三个特殊的分布对应的现象称为完美的状态转移，分数复苏和均匀混合。一个图有两个顶点之间的完美状态转移，如果有一个时间，从一个顶点开始的行走返回第二个顶点的概率为1。这种现象允许信息从初始顶点到另一个顶点的保真度为1。这种转移是重要的，因为不可克隆定理表明不可能复制量子态。具有完美状态转移的图是罕见的，因此我们考虑称为分数恢复的松弛。如果从一个顶点开始的行走以概率1返回初始或第二个顶点，则在两个顶点之间发生分数复兴。除了态转移之外，分数复活还可以用来产生纠缠，这是量子计算中的一种有用资源。我以前的工作奠定了基础，研究分数复苏图。我们建议继续这项研究，其中包括寻找更多的图与分数复苏和调查的图形属性所产生的这种现象。相反，均匀混合要求行走在顶点集上具有均匀的概率分布。在均匀混合时，行走的转移矩阵给出了一个复杂的阿达玛矩阵，这是其他数学领域感兴趣的对象。大多数已知的具有均匀混合的图来自于结合方案。我们建议搜索复杂的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.