ProfileRichard Cleve obtained his Ph.D. from the University of Toronto in 1989, working in cryptography and computational complexity. He 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. In 2001, he held a Killam Resident Fellowship, and in 2002 he was honoured with the title University Professor. In 2004, Dr. Cleve moved to the University of Waterloo's School of Computer Science, and also became a member of the Institute for Quantum Computing in Waterloo. He is a Founding Managing Editor of the journal, Quantum Information & Computation.
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. He has recently helped develop a new class of algorithms based on the behaviour of quantum walks (which are quantum analogs of classical random walks).
Outputs
Title | Category | Date | Authors |
Consequences and limits of nonlocal strategies University of Calgary | Publication | 2004-01-01 | R. Cleve, P. Høyer, B. Toner, J. Watrous | Fast parallel circuits for the quantum Fourier transform University of Calgary | Publication | 2000-01-01 | R. Cleve, J. Watrous | Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems University of Calgary | Publication | 2007-06-01 | R. Cleve, W. Slofstra, F. Unger, S. Upadhyay | Quantum Algorithms for Evaluating Min-Max Trees University of Calgary | Publication | 2008-01-01 | R. Cleve, D. Gavinsky, D. L. Yonge-Mallo | Consequences and limits of nonlocal strategies University of Calgary | Publication | 2004-01-01 | R. Cleve, P. Høyer, B. Toner, J. Watrous | Quantum Communication ComplexityA distributed information processing task is one where two or more physically separated parties each receive some input data and they are required to compute some quantities based on this data. A simple two-party example is where each party receives a binary string and their goal is to determine whether or not the strings are identical. It is clear that this particular task cannot be accomplished without some communication occurring between the parties. In communication complexity, the amount of communication required to perform distributed information processing tasks is quantified.
We shall give examples of information processing tasks that can be accomplished with significant savings in communication when quantum resources are available. These include some intriguing nonlocal effects that were first discovered by John Bell in the 1960s, as well as more recent communication protocols which have connections with quantum algorithms. Taken together, these results complement the well-known fact that bits cannot be compressed by encoding them into qubits. University of Calgary | Presentation | 2004-06-21 | R. Cleve | Quantum Fingerprinting University of Calgary | Publication | 2001-09-01 | H. Buhrman, R. Cleve, J. Watrous, R. d. Wolf | Quantum lower bounds for the Goldreich–Levin problem University of Calgary | Publication | 2006-03-01 | M. Adcock, R. Cleve, K. Iwama, R. Putra, S. Yamashita | Exact and approximate unitary 2-designs and their application to fidelity estimation University of Calgary | Publication | 2009-07-01 | C. Dankert, R. Cleve, J. Emerson, E. Livine | Quantum lower bounds for the Goldreich-Levin problem University of Calgary | Publication | 2006-01-01 | M. Adcock, R. Cleve, K. Iwama, R. Putra, S. Yamashita | Exponential algorithmic speedup by a quantum walk University of Calgary | Publication | 2003-01-01 | A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, D. A. Spielman | Efficient Quantum Algorithms for Simulating Sparse Hamiltonians University of Calgary | Publication | 2006-12-01 | D. W. Berry, G. Ahokas, R. Cleve, B. C. Sanders | Classical and quantum fingerprinting with shared randomness and one-sided error University of Calgary | Publication | 2005-05-01 | R. T. Horn, A. Scott, J. Walgate, R. Cleve, A. Lvovsky, B. C. Sanders |
| |