Richard Cleve's Papers

Non-locality and communication complexity
Harry Buhrman, Richard Cleve, Serge Massar, and Ronald de Wolf
Reviews of Modern Physics, 82:665-698 (2010)
quant-ph/0907.3584: PDF
Journal version: PDF
Exact and approximate unitary 2-designs and their application to fidelity estimation
Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine
Physical Review A, 80:012304 (2009)
quant-ph/0606161: PDF
Journal version: PDF
Efficient discrete-time simulations of continuous-time quantum query algorithms
Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando Somma, David Yonge-Mallo
Proceedings of the 41st annual ACM Symposium on Theory of Computing (STOC 2009), pages 409-416 (2009)
quant-ph/0811.4428
Conference version: PDF
Discrete-query quantum algorithm for NAND trees
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
Theory of Computing, 5:119-123 (2009)
quant-ph/0702160
Journal version: PDF
Entanglement-resistant two-prover interactive proof systems and non-adaptive PIRs
Richard Cleve, Dmitry Gavinsky, and Rahul Jain
To appear in Quantum Information and Computation (2009)
quant-ph/0707.1729
Journal version: PDF
Quantum Algorithms for Evaluating Min-Max Trees
Richard Cleve, Dmitry Gavinsky, and David Yonge-Mallo
Proceedings of Theory of Quantum Computation, Communication, and Cryptography (TQC 2008)
Y. Kawano and M. Mosca (Eds.), Lecture Notes in Computer Science, Volume 5106, Springer, pages 11-15 (2008)
quant-ph/0710.5794
Conference version: PDF
Perfect parallel repetition theorem for quantum XOR proof systems
Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay,
Computational Complexity, 17:282-299 (2008)
Journal version: PDF
Earlier conference version in Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), pages 109-114 (2007)
Conference version: PDF
Earlier quant-ph version with different title Strong parallel repetition theorem for quantum XOR proof systems
quant-ph/0608146: PS, PDF
Efficient quantum algorithms for simulating sparse Hamiltonians
Dominic W. Berry, Graeme Ahokas, Richard Cleve, Barry C. Sanders
Communications in Mathematical Physics, 270(2):359-371 (2007)
quant-ph/0508139: PS, PDF
Journal version: PDF
New limits on fault-tolerant quantum computation
Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 411-419 (2006)
quant-ph/0604141: PS, PDF
Conference version: PDF
Quantum lower bounds for the Goldreich-Levin problem
Mark Adcock, Richard Cleve, Kasuo Iwama, Raymond Putra, Shigeru Yamashita
Information Processing Letters, 97(5): 208-211 (2006)
Manuscript: PS, PDF
Journal version: PDF
Classical and quantum fingerprinting with shared randomness and one-sided error
Rolf T. Horn, A. J. Scott, Jonathan Walgate, Richard Cleve, A. I. Lvovsky, Barry C. Sanders
Quantum Information and Computation, 5(3): 258-271 (2005)
quant-ph/0501021: PS, PDF
Consequences and limits of nonlocal strategies
Richard Cleve, Peter Høyer, Benjamin Toner, and John Watrous
Proceedings of the 19th IEEE Conference on Computational Complexity (CCC 2004), pages 236-249 (2004)
Conference version and quant-ph/0404076: PS, PDF
Exponential algorithmic speedup by a quantum walk
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman
Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pages 59-68 (2003)
Conference version: PS, PDF
quant-ph/0209131: PS, PDF
The complexity of quantum Fourier transforms and integer multiplication
Graeme Ahokas, Richard Cleve, and Lisa Hales
Presented at ERATO Conference on Quantum Information Science, Kyoto, Japan, September 5, 2003
Extended abstract: PDF
A quantum Goldreich-Levin theorem with cryptographic applications
Mark Adcock and Richard Cleve
Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002)
Helmut Alt and Alfonso Ferreira (Eds.), Lecture Notes in Computer Science, Volume 2285, Springer-Verlag, pages 323-334 (2002)
Conference version: PS, PDF
quant-ph/0108095: PS, PDF
Sharp quantum versus classical query complexity separations
J. Niel de Beaudrap, Richard Cleve, and John Watrous
Algorithmica, 34(4):449-461 (2002)
Journal version: PS, PDF
quant-ph/0011065: PS, PDF
Quantum fingerprinting
Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf
Physical Review Letters, 87(16):167902 (2001)
Journal version: PS, PDF
quant-ph/0102001: PS, PDF
Quantum entanglement and communication complexity
Harry Buhrman, Richard Cleve, and Wim van Dam
SIAM Journal on Computing, 30(8):1829-1841 (2001)
Journal version: PS
quant-ph/9705033: PS
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf
Journal of the ACM, 48(4):778-797 (2001)
Journal version: PS
Note: A preliminary version appeared in FOCS 1998
Classical simulation of quantum entanglement without local hidden variables
Serge Massar, Dave Bacon, Nicolas Cerf, and Richard Cleve
Physical Review A, 63(5):052305 (2001)
Journal version: PS
quant-ph/0009088: PS
Experimental realization of order-finding with a quantum computer
Lieven M.K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannon, Richard Cleve, and Isaac L. Chuang
Physical Review Letters, 85(25):5452-5455 (2000)
Journal version: PS
Fast parallel circuits for the quantum Fourier transform
Richard Cleve and John Watrous
Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000), pages 526-536 (2000)
Conference version: PS
quant-ph/0006004: PS
The query complexity of order-finding
Richard Cleve
Proceedings of the 15th Annual IEEE Conference on Computational Complexity (CCC 2000), pages 54-59 (2000)
Conference version: PS
quant-ph/9911124: PS
An introduction to quantum complexity theory
Richard Cleve
in Collected Papers on Quantum Computation and Quantum Information Theory, C. Macchiavello, G.M. Palma, and A. Zeilinger (Eds.) (World Scientific), pages 103-127 (2000)
quant-ph/9906111: PS
Bounds for small-error and zero-error quantum algorithms
Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka
Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1999), pages 358-368 (1999)
cs.CC/9904019: PS
The cost of exactly simulating quantum entanglement with classical communication
Gilles Brassard, Richard Cleve, and Alain Tapp
Physical Review Letters, 83(9):1874-1877 (1999)
Journal version: PS
Extended version on quant-ph/9901035: PS
How to share a quantum secret
Richard Cleve, Daniel Gottesman, and Hoi-Kwong Lo
Physical Review Letters, 83(3):648-651 (1999)
Journal version: PS
Extended version on quant-ph/9901025: PS
Quantum entanglement and the communication complexity of the inner product function
Richard Cleve, Wim van Dam, Michael Nielsen, and Alain Tapp
Proceedings of the First NASA International Conference on Quantum Computing and Quantum Communications
Lecture Notes in Computer Science, Colin P. Williams (Ed.), Volume 1509, Springer-Verlag, pages 61-74 (1999)
Proceedings version: PDF
quant-ph/9708019: PS
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf
Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1998), pages 352-361 (1998)
quant-ph/9802049: PS
Note: A final version appeared in Journal of the ACM in 2001
Quantum vs. classical communication and computation
Harry Buhrman, Richard Cleve, and Avi Wigderson
Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pages 63-68 (1998)
quant-ph/9702040: PS
Quantum algorithms revisited
Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca
Proceedings of the Royal Society of London, Series A, 454(1969):339-354 (1998)
quant-ph/9708016: PS
Teleportation as a quantum computation
Gilles Brassard, Samuel L. Braunstein, and Richard Cleve
Physica D, 120:43-47 (1998)
Journal version: PS
Interpolating arithmetic read-once formulas in parallel
Nader H. Bshouty and Richard Cleve
SIAM Journal on Computing, 27(2):401-413 (1998)
Journal version: PS
Note: A preliminary version entitled "On the exact learning of formulas in parallel" appeared in FOCS 1992
Information-theoretic interpretation of quantum error-correcting codes
Nicolas J. Cerf and Richard Cleve
Physical Review A, 56(3):1721-1732 (1997)
quant-ph/9702031: PS
Substituting quantum entanglement for communication
Richard Cleve and Harry Buhrman
Physical Review A, 56(2):1201-1204 (1997)
quant-ph/9704026: PS
Efficient computations of encodings for quantum error correction
Richard Cleve and Daniel Gottesman
Physical Review A, 56(1):76-82 (1997)
quant-ph/9607030: PS
Quantum stabilizer codes and classical linear codes
Richard Cleve
Physical Review A, 55(6):4054-4059 (1997)
quant-ph/9612048: PS
Oracles and queries that are sufficient for exact learning
Nader H. Bshouty, Richard Cleve, Ricard Gavalda, Sampath Kannan, and Christino Tamon
Journal of Computer and System Sciences, 52(3):421-433 (1996)
Journal version: PS
Note: A preliminary version appeared in COLT 1994
Schumacher's quantum data compression as a quantum computation
Richard Cleve and David P. DiVincenzo
Physical Review A, 54(4):2636-2650 (1996)
quant-ph/9603009: PS
Elementary gates for quantum computation
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter
Physical Review A, 52(5):3457-3467 (1995)
quant-ph/9503016: PS
Size-depth tradeoffs for algebraic formulas
Nader H. Bshouty, Richard Cleve, and Wayne Eberly
SIAM Journal on Computing, 24(4):682-705 (1995)
Journal version: PS
Note: A preliminary version appeared in FOCS 1991
A note on computing Fourier transforms by quantum programs
Richard Cleve
Unpublished (1994)
Manuscript: PS
Oracles and queries that are sufficient for exact learning
Nader H. Bshouty, Richard Cleve, Sampath Kannan, and Christino Tamon
Proceedings of the 7th Annual Conference on Computational Learning Theory (COLT 1994), pages 130-139 (1994)
Note: A final version appeared in Journal of Computer and System Sciences in 1996
Martingales, collective coin flipping and discrete control processes
Richard Cleve and Russell Impagliazzo
Unpublished (1993)
Manuscript: PS
A note on constructive lower bounds for the Ramsey numbers R(3,t)
Fan R.K. Chung, Richard Cleve, and Paul Dagum
Journal of Combinatorial Theory, Series B, 57(1):150-155 (1993)
On the exact learning of formulas in parallel
Nader H. Bshouty and Richard Cleve
Proceedings of the 33th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1992), pages 513-522 (1992)
Note: A final version entitled "Interpolating arithmetic read-once formulas in parallel" appeared in SIAM J. on Computing in 1998
Computing algebraic formulas using a constant number of registers
Michael Ben-Or and Richard Cleve
SIAM Journal on Computing, 21(1):54-58 (1992)
Note: A preliminary version appeared in STOC 1988
Size-depth tradeoffs for algebraic formulae
Nader H. Bshouty, Richard Cleve, and Wayne Eberly
Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 1991), pages 334-341 (1991)
Note: A final version appeared in SIAM Journal on Computing in 1995
Towards optimal simulations of formulas by bounded-width programs
Richard Cleve
Computational Complexity, 1:91-105 (1991)
Note: A preliminary version appeared in STOC 1990
Complexity theoretic issues concerning block ciphers related to D.E.S.
Richard Cleve
Advances in Cryptology - CRYPTO '90 Proceedings, Alfred J. Menezes, Scott A. Vanstone (Eds.), Lecture Notes in Computer Science, Volume 537, Springer-Verlag, pages 530-544 (1990)
A note on self-testing/correcting methods for trigonometric functions
Richard Cleve and Michael Luby
International Computer Science Institute Technical Report TR-90-032
Towards optimal simulations of formulas by bounded-width programs
Richard Cleve
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990), pages 271-277 (1990)
Note: A final version appeared in Computational Complexity in 2001
Controlled gradual disclosure schemes for random bits and their applications
Richard Cleve
Advances in Cryptology - CRYPTO '89 Proceedings, Gilles Brassard (Ed.), Lecture Notes in Computer Science, Volume 435, Springer-Verlag, pages 573-588 (1989)
Methodologies for designing block ciphers and cryptographic protocols
Richard Cleve
PhD thesis, University of Toronto (1989)
Computing algebraic formulas using a constant number of registers
Michael Ben-Or and Richard Cleve
Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988), pages 254-257 (1988)
Note: A final version appeared in SIAM Journal on Computing in 1992
Limits on the security of coin flips when half the processors are faulty
Richard Cleve
Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC 1986), pages 364-369 (1986)
The entropy of a probability measure on a measurable space relative to a generating algebra
Richard Cleve
Master's thesis, University of Waterloo (1984)