Richard Cleve's Papers
(See also: arXiv and Google Scholar)
Constant gap between conventional strategies and those based on C*-dynamics for self-embezzlement
Richard Cleve, Benoît Collins, Li Liu, and Vern Paulsen
Quantum 6, 755 (2022)
arXiv:1811.12575
Efficient Quantum Algorithms for Simulating Lindblad Evolution
Richard Cleve, Chunhao Wang
Proceedings 44th International Colloquium on Automata, Languages, and Programming
(ICALP 2017), pages 17:1-14 (2017)
arXiv:1612.09512
Perfect embezzlement of entanglement
Richard Cleve, Li Liu, and Vern Paulsen
Journal of Mathematical Physics 58:012204 (2017)
arXiv:1606.05061
Perfect commuting-operator strategies for linear system games
Richard Cleve, Li Liu, and William Slofstra
Journal of Mathematical Physics 58:012202 (2017)
arXiv:1606.02278
Near-linear constructions of exact unitary 2-designs
Richard Cleve, Debbie Leung, Li Liu, and Chunhao Wang
Quantum Information and Computation 16(9&10):0721-0756 (2016)
arXiv:1501.04592
Simulating Hamiltonian dynamics with a truncated Taylor series
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
Physical Review Letters 114:090502 (2015)
arXiv:1412.4687
Exponential improvement in precision for simulating sparse Hamiltonians
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014), pages 283-292 (2014)
arXiv:1312.1414
Computing with a full memory: Catalytic space
Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, and Florian Speelman
Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014), pages 857-866 (2014)
ECCC:TR14-053
Gate-efficient discrete simulations of continuous-time quantum query algorithms
Dominic W. Berry, Richard Cleve, and Sevag Gharibian
Quantum Information and Computation 14, 0001 (2014)
arXiv:1211.4637
Characterization of binary constraint system games
Richard Cleve and Rajat Mittal
Proceedings 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), pages 320-331 (2014)
arXiv:1209.2729
Reconstructing strings from substrings with quantum queries
Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, and Shigeru Yamashita
Proceedings of 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), Fedor V. Fomin and Petteri Kaski (Eds.), Lecture Notes in Computer Science, Volume 7357, Springer, pages 388-397.
arXiv:1204.4691
Classical simulation of entanglement swapping with bounded communication
Cyril Branciard, Nicolas Brunner, Harry Buhrman, Richard Cleve, Nicolas Gisin, Samuel Portmann, Denis Rosset, and Mario Szegedy
Physical Review Letters 109:100401 (2012)
arXiv:1203.0445
Non-locality and communication complexity
Harry Buhrman, Richard Cleve, Serge Massar, and Ronald de Wolf
Reviews of Modern Physics, 82:665-698 (2010)
arXiv:0907.3584
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)
arXiv:0606161
Efficient discrete-time simulations of continuous-time quantum query algorithms
Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando Somma, and David Yonge-Mallo
Proceedings of the 41st annual ACM Symposium on Theory of Computing (STOC 2009), pages 409-416 (2009)
arXiv:0811.4428
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)
arXiv:0702160
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)
arXiv:0707.1729
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)
arXiv:0710.5794
Perfect parallel repetition theorem for quantum XOR proof systems
Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay,
Computational Complexity, 17:282-299 (2008)
Earlier conference version in Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), pages 109-114 (2007)
arXiv:0608146
Efficient quantum algorithms for simulating sparse Hamiltonians
Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders
Communications in Mathematical Physics, 270(2):359-371 (2007)
arXiv:0508139
New limits on fault-tolerant quantum computation
Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, and Falk Unger
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 411-419 (2006)
arXiv:0604141
Quantum lower bounds for the Goldreich-Levin problem
Mark Adcock, Richard Cleve, Kasuo Iwama, Raymond Putra, and Shigeru Yamashita
Information Processing Letters, 97(5): 208-211 (2006)
(no arXiv version)
Classical and quantum fingerprinting with shared randomness and one-sided error
Rolf T. Horn, A. J. Scott, Jonathan Walgate, Richard Cleve, A. I. Lvovsky, and Barry C. Sanders
Quantum Information and Computation, 5(3): 258-271 (2005)
arXiv:0501021
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)
arXiv:0404076
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)
arXiv:0209131
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
(no arXiv version; extended abstract is available from the conference program, in session A1 on Sept. 5)
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)
arXiv:0108095
Sharp quantum versus classical query complexity separations
J. Niel de Beaudrap, Richard Cleve, and John Watrous
Algorithmica, 34(4):449-461 (2002)
arXiv:0011065
Quantum fingerprinting
Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf
Physical Review Letters, 87(16):167902 (2001)
arXiv:0102001
Quantum entanglement and communication complexity
Harry Buhrman, Richard Cleve, and Wim van Dam
SIAM Journal on Computing, 30(8):1829-1841 (2001)
arXiv:9705033
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)
Note: A preliminary version appeared in FOCS 1998
arXiv:9802049
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)
arXiv:0009088
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)
arXiv:0007017
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)
arXiv:0006004
The query complexity of order-finding
Richard Cleve
Proceedings of the 15th Annual IEEE Conference on Computational Complexity (CCC 2000), pages 54-59 (2000)
arXiv:9911124
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)
arXiv:9906111
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)
arXiv:9904019
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)
arXiv:9901035
How to share a quantum secret
Richard Cleve, Daniel Gottesman, and Hoi-Kwong Lo
Physical Review Letters, 83(3):648-651 (1999)
arXiv:9901025
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)
arXiv:9708019
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)
Note: A final version appeared in Journal of the ACM in 2001
arXiv:9802049
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)
arXiv:9802040
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)
arXiv:9708016
Teleportation as a quantum computation
Gilles Brassard, Samuel L. Braunstein, and Richard Cleve
Physica D, 120:43-47 (1998)
journal version
Interpolating arithmetic read-once formulas in parallel
Nader H. Bshouty and Richard Cleve
SIAM Journal on Computing, 27(2):401-413 (1998)
Note: A preliminary version entitled "On the exact learning of formulas in parallel" appeared in FOCS 1992
journal version
Information-theoretic interpretation of quantum error-correcting codes
Nicolas J. Cerf and Richard Cleve
Physical Review A, 56(3):1721-1732 (1997)
arXiv:9702031
Substituting quantum entanglement for communication
Richard Cleve and Harry Buhrman
Physical Review A, 56(2):1201-1204 (1997)
arXiv:9704026
Efficient computations of encodings for quantum error correction
Richard Cleve and Daniel Gottesman
Physical Review A, 56(1):76-82 (1997)
arXiv:9607030
Quantum stabilizer codes and classical linear codes
Richard Cleve
Physical Review A, 55(6):4054-4059 (1997)
arXiv:9612048
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)
Note: A preliminary version appeared in COLT 1994
journal version
Schumacher's quantum data compression as a quantum computation
Richard Cleve and David P. DiVincenzo
Physical Review A, 54(4):2636-2650 (1996)
arXiv:9603009
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)
arXiv:9503016
Size-depth tradeoffs for algebraic formulas
Nader H. Bshouty, Richard Cleve, and Wayne Eberly
SIAM Journal on Computing, 24(4):682-705 (1995)
Note: A preliminary version appeared in FOCS 1991
journal version
A note on computing Fourier transforms by quantum programs
Richard Cleve
Unpublished (1994)
(Manuscript available on request)
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
journal version
Martingales, collective coin flipping and discrete control processes
Richard Cleve and Russell Impagliazzo
Unpublished (1993)
(Manuscript available on request)
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)
journal version
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
journal version
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
journal version
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
journal version
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
journal version
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)
conference version
A note on self-testing/correcting methods for trigonometric functions
Richard Cleve and Michael Luby
International Computer Science Institute Technical Report TR-90-032
technical report
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
journal version
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)
conference version
Methodologies for designing block ciphers and cryptographic protocols
Richard Cleve
PhD thesis, University of Toronto (1989)
(Manuscript available on request)
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
conference version
journal version
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)
conference version
The entropy of a probability measure on a measurable space relative to a generating algebra
Richard Cleve
Master's thesis, University of Waterloo (1984)