Reference number : GC-2017-Q1-01829, amendment number : , agreement type : G, recipient legal name : Godsil, Chris (University of Waterloo), recipient country : CA, recipient province : nan, recipient city : Ontario, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : Physicists, computer scientists and mathematicians are working to decide how we may best make use of quantum computers. Here the basic problems are to work out what we might do with a quantum computer that we cannot do equally well with the ordinary computers already on our desks, and what their limitations might be. 
 
The goal of my project is develop the theory of objects known as quantum walks, which can be viewed as subroutines in a quantum computer. These walks come in many variants, but in each case they are based on an underlying network or graph. In the most general terms, the goal of my project is to develop our understanding of the relation between the properties of the walk and the properties of the underlying graph. I hope to develop the theory to the point where we can produce quantum algorithms for determining properties of the underlying graph. 
 
I expect our work will also lead us to develop limits on just what is possible using these walks. Physicists have proposed algorithms for solving the graph isomorphism problem, an important problem in computing. I and members of my team have shown that most of these proposals do not work. We would like to go further and show that there are no natural modifications of these algorithms that work., program purpose french : Physicists, computer scientists and mathematicians are working to decide how we may best make use of quantum computers. Here the basic problems are to work out what we might do with a quantum computer that we cannot do equally well with the ordinary computers already on our desks, and what their limitations might be. 
 
The goal of my project is develop the theory of objects known as quantum walks, which can be viewed as subroutines in a quantum computer. These walks come in many variants, but in each case they are based on an underlying network or graph. In the most general terms, the goal of my project is to develop our understanding of the relation between the properties of the walk and the properties of the underlying graph. I hope to develop the theory to the point where we can produce quantum algorithms for determining properties of the underlying graph. 
 
I expect our work will also lead us to develop limits on just what is possible using these walks. Physicists have proposed algorithms for solving the graph isomorphism problem, an important problem in computing. I and members of my team have shown that most of these proposals do not work. We would like to go further and show that there are no natural modifications of these algorithms that work., agreement title english : Quantum walks and graph spectra, agreement title french : Quantum walks and graph spectra, agreement number : RGPIN, agreement value : 250000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada