Grant: Discovery Grants Program - Individual
York University
$18,000.00
Algebraic graph theory and quantum walks
EF 2023-24
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2021-03609
Name nom
Chan, Ada
Department département
Mathematics and Statistics
Organization id
38
Institution établissement
York University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2021
Award amount
18000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2714
Research subject group en
Information technology
Research subject group fr
Mathematics of computing
Research subject en
Technologie de l'information
Research subject fr
Mathématiques de l'informatique
Application title
Algebraic graph theory and quantum walks
Keyword
algebraic graph theory; association scheme; complex Hadamard matrix; fractional revival; instantaneous uniform mixing; perfect state transfer; quantum walks; scattering; spatial search; Terwilliger algebra
Application summary
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.