Richard Cleve's Papers

  • 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

  • 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, Volume 34, Number 4, pages 449-461 (2002)
    Journal version: PS
    quant-ph/0011065: PS

  • Quantum fingerprinting
    Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf
    Physical Review Letters, Volume 87, Number 16, Article 167902 (2001)
    Journal version: PS
    quant-ph/0102001: PS

  • Quantum entanglement and communication complexity
    Harry Buhrman, Richard Cleve, and Wim van Dam
    SIAM Journal on Computing, Volume 30, Number 8, pages 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, Volume 48, Number 4, pages 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, Volume 63, Number 5, Article 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, Volume 85, Number 25, pages 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, Volume 83, Number 9, pages 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, Volume 83, Number 3, pages 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, Volume 454, Number 1969, pages 339-354 (1998)
    quant-ph/9708016: PS

  • Teleportation as a quantum computation
    Gilles Brassard, Samuel L. Braunstein, and Richard Cleve
    Physica D, Volume 120, pages 43-47 (1998)
    Journal version: PS

  • Interpolating arithmetic read-once formulas in parallel
    Nader H. Bshouty and Richard Cleve
    SIAM Journal on Computing, Volume 27, Number 2, pages 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, Volume 56, Number 3, pages 1721-1732 (1997)
    quant-ph/9702031: PS

  • Substituting quantum entanglement for communication
    Richard Cleve and Harry Buhrman
    Physical Review A, Volume 56, Number 2, pages 1201-1204 (1997)
    quant-ph/9704026: PS

  • Efficient computations of encodings for quantum error correction
    Richard Cleve and Daniel Gottesman
    Physical Review A, Volume 56, Number 1, pages 76-82 (1997)
    quant-ph/9607030: PS

  • Quantum stabilizer codes and classical linear codes
    Richard Cleve
    Physical Review A, Volume 55, Number 6, pages 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, Volume 52, Number 3, pages 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, Volume 54, Number 4, pages 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, Volume 52, Number 5, pages 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, Volume 24, Number 4, pages 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, Volume 57, Number 1, pages 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, Volume 21, Number 1, pages 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, Volume 1, pages 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)