Academic participants:
Andris Ambainis, Richard Cleve, Peter Høyer, Michele Mosca, Ashwin Nayak, Barry Sanders, John Watrous.
Recent progress in quantum algorithms has resulted in these two new techniques. What are the applications of these techniques? Can we generalize them? These are examples of questions that will be addressed.
A rich body of techniques has developed in the study of classical Markov chains (including random walks) to yield efficient algorithms. With quantum walks, the goal is similar, but to yield new quantum algorithms. Several preliminary results along these lines have occurred.
An example of a specific direction of exploration concerns the canonical NP-complete problem 3-SAT, which is the problem of determining whether a 3-CNF (conjunctive normal form) boolean formula is satisfiable. Schoning initiated a strong classical approach based on random walks. The latest is an algorithm that runs in time approximately (1.324)n, where n is the number of variables. The basic idea is to perform a random walk on assignments to the variables, guided by the clauses in the formula that are not satisfied. A natural and interesting question is whether we can design and analyze a quantum analogue of this algorithm that is faster. A direct application of amplitude amplification to the random walk scheme described above yields a quadratic speed-up. Given the peculiar properties of quantum walks, it is natural to speculate that further speed-up may be possible by a more direct application.
An early example of quantum walk algorithmic speed-up: a quantum walk-based algorithm is able to reach T from S very fast, whereas any classical algorithm requires exponentially more time.
The adiabatic approach is based on the adiabatic theorem of quantum mechanics, which states that a quantum system stays in its lowest energy state, as long as the forces acting on the system are changed sufficiently slowly. An algorithm based on this approach would work by slowly transforming a quantum system whose ground state is known to one whose ground state encodes the solution to the problem. The power of this approach remains disputed. According to experimental studies by Farhi et al. the adiabatic approach solves random instances of 3-SAT with a small number of variables quickly. On the other hand, van Dam, Mosca and Vazirani and Reichardt have exhibited specific instances of 3-SAT where the approach requires exponential time. Giving a rigorous analysis of the algorithm on average-case instances of 3-SAT appears to be difficult. We will look at adiabatic algorithms for problems other than satisfiability. In particular, we will consider problems with an algebraic structure, which could be more amenable to rigorous analysis than satisfiability (similarly to how factoring and discrete logarithm, two problems with a strong algebraic flavour, were solved by the standard paradigm of quantum computing).
One technique for acquiring further insight is to improve our understanding of adiabatic computations in computer science terms. So far, adiabatic computation has been mainly studied in the language of physics. In particular, the proofs of the adiabatic theorem and related statements are not very intuitive for computer scientists. Understanding the adiabatic approach in computer science terms would bring another perspective that we hope will help apply it to computer science problems. This approach has been initiated by Ambainis and Regev.
This project will interact with project QA4 on simulations of quantum physical systems. Researchers part of this Network located at Perimeter Institute and also the one funded by the Canadian Institute for Advanced Research will investigate the fundamental issues relevant to this project.