Grant: Discovery Grants Program - Individual
York University
$18,000.00
Algebraic graph theory and quantum walks
FY 2022-23
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2021-03609
Name nom
Chan, Ada
Department département
Mathematics and Statistics - 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
2022
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
2900
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Pure mathematics
Research subject fr
Mathématiques pures
Installment
inst:2
Partie
1
Nb partie
5
Application title
Algebraic graph theory and quantum walks
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.