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.
Computer scientist Richard 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, Cleve has played a major role in the development of the rich and lively area of quantum communication complexity.
Cleve has also made several contributions to the important theory of quantum algorithms. These include simplifications and efficiency improvements to existing quantum algorithms, results that establish limits on the power of quantum algorithms, and the development of novel algorithmic paradigms. He has recently (with Dominic Berry, Andrew Childs, Robin Kothari and Rolando Somma) developed a very fast algorithm for simulating the dynamics of quantum mechanical systems.
Canadian Association of Physicists Prize in Theoretical and Mathematical Physics
Member, Institute for Quantum Computing
Fellow, Royal Society of Canada
Killam Resident Fellowship
Cleve, R. et al. "How to share a quantum secret." Phys. Rev. Lett. 83, no. 3 (July 1999): 648.
Cleve, R., and H. Buhrman. "Substituting quantum entanglement for communication." Phys. Rev. A. 56, no. 2 (August 1997): 1201.