THIS SITE

Information for

Richard Cleve

Professor

Research interests

Quantum information can be used to perform a variety of feats that cannot be accomplished with classical information. For example, there is a quantum algorithm that can factorize integers very quickly (in polynomial time), whereas all known conventional algorithms require an enormous (exponential) amount of time to do this. Quantum information can also exhibit “non-local” behaviour, whereby two (or more) quantum systems that are physically separated exhibit a collective behaviour that cannot occur with classical systems, unless communication occurs between them.

Professor Cleve realized that non-local behaviour was intimately connected to a class of computational problems involving distributed systems in which the primary resource under consideration is the amount of communication that occurs between processors. Building on this insight, he was the first (with Harry Buhrman) to show that quantum information can reduce “communication complexity” costs in distributed systems. Since then he has played a major role in the development of the rich and lively area of quantum communication complexity.

Professor Cleve has also made several contributions to the fascinating and important theory of quantum algorithms. These include simplifications and efficiency improvements to existing quantum algorithms, results that establish limits on the power quantum algorithms, and the development of novel algorithmic paradigms, such as the development of quantum walks.

Previous employment experience: Professor Cleve was a Postdoctoral Fellow at Berkeley's International Computer Science Institute during 1988-90 and became a faculty member at the University of Calgary in 1990, where he was promoted to Full Professor in 2000.

Degrees and awards

BMath, MMath (Waterloo), PhD (Toronto)

Fellow of the Royal Society of Canada (2010); Canadian Association of Physicists/Centre de Recherches en Mathématiques Prize in Theoretical and Mathematical Physics (2008); Institute for Quantum Computing Endowed Chair, University of Waterloo (2004-2011); Founding Fellow CIAR in Quantum Information Processing (2002)

Representative publications

H. Buhrman, R. Cleve, S. Massar, and R. de Wolf. Nonlocality and communication complexity. Reviews of Modern Physics, 82:665–698, 2010.

R. Cleve, D. Gottesman, M. Mosca, R. Somma, D. Yonge-Mallo. Efficient discrete-time simulations of continuous-time quantum query algorithms. Proceedings of the 41st annual ACM Symposium on Theory of Computing (STOC), pp. 409-416, 2009.

R. Cleve, P. Hoyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. Proceedings of the 19th IEEE Conference on Computational Complexity, pp. 236-249, 2004.

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman. Exponential algorithmic speedup by a quantum walk. Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 59-68, 2003.

R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778-797, 2001.

H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 63-68, 1998.

Affiliation: 
University of Waterloo
Contact information: