Algebraic graph theory and quantum walks

代数图论和量子漫步之间的相互作用是这项提议的主题。图上的连续时间量子行走是一个依赖于时间的演化，由薛定谔方程使用哈密顿量给出，哈密顿量是与图相关的矩阵。2003年，Childs et al.给出了一种基于量子游走的算法，该算法解决预言问题的速度比任何经典算法都快。连续时间量子游动也可以被视为量子计算的通用原语。在给定初始顶点的情况下，图上的量子游动给出了在任何给定时间测量时返回的顶点的概率分布。我们感兴趣的是与完美态转移、分数复苏和均匀混合现象相对应的三种特殊分布。如果从一个顶点开始的游动以概率1返回第二个顶点，则图有两个顶点之间的完美状态转移。这一现象允许信息从初始顶点保真地传递到另一个顶点。这种转移很重要，因为不可克隆定理说，复制量子态是不可能的。具有完全状态转移的图是罕见的，因此我们考虑一种称为分数恢复的松弛。如果从一个顶点开始的漫游以概率1返回初始顶点或第二个顶点，则在两个顶点之间发生分数恢复。除了态转移，分数复兴还可以用于产生纠缠，这在量子计算中是一种有用的资源。我以前的工作为研究图中的分数恢复奠定了基础。我们建议继续这方面的研究，包括寻找更多具有分数再生的图，并研究由这一现象产生的图的性质。相反，均匀混合要求游动在顶点集上具有均匀的概率分布。在均匀混合时，游动的转移矩阵给出了复哈达玛矩阵，这是其他数学领域感兴趣的对象。大多数已知的均匀混合图都来自于结合方案。我们建议在结合方案中搜索具有均匀混合的复Hadamard矩阵和图。我们计划致力于刻画具有均匀混合的图。量子行走是发展量子算法的重要工具，量子行走的进展将对量子计算领域产生重大影响。由于量子行走的哈密顿量是一个图矩阵，代数图论提供了自然而强大的工具。另一方面，在这项研究中也出现了一些有趣的图论问题。量子行走是一个活跃且不断增长的领域，在Mathceeet上搜索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.