Academic participants:
Richard Cleve, Peter Høyer, Michele Mosca, Ashwin Nayak, Alain Tapp, John Watrous.
Partners:
Communication Security Establishment, Certicom.
The primary goal of our research in quantum algorithms is to discover new algorithms that allow quantum computers to outperform classical computers. A particular focus of the proposed research on quantum algorithms is in the area of group-theoretic problems. The main motives for this are that (i) almost all of the problems for which quantum algorithms have been shown to offer exponential speed-up over the best known classical algorithms can be stated as problems regarding finite groups, (ii) several group-theoretic problems are good candidates for admitting an exponential quantum-over-classical speed-up because of their complexity-theoretic properties, and (iii) some of the group-theoretic problems that we conclude are not likely to be efficiently solvable by quantum algorithms may as a result be useful in designing classical cryptosystems that are secure against quantum cryptanalysis.
This project will interact with projects QC2 on the implications of quantum algorithms on classical cryptography and QC3 on new quantum algorithms. The Communication Security Establishment is intends to sponsor research in the area of theoretical quantum information which impacts cryptography. Dr Bertrand Campagna from Pitney Bowes will work with academic researchers on problems concerning the vulnerability that quantum computing imposes on classical cryptography.