Metadata
Title
Papers
Category
general
UUID
6c6431c5422c45bba7172a79b95563bb
Source URL
https://cleve.iqc.uwaterloo.ca/styled-2/index.html
Parent URL
https://cleve.iqc.uwaterloo.ca/
Crawl Time
2026-03-23T19:56:44+00:00
Rendered Raw Markdown 
# Papers

**Source**: https://cleve.iqc.uwaterloo.ca/styled-2/index.html
**Parent**: https://cleve.iqc.uwaterloo.ca/

\
Richard Cleve's Papers\
(See also: [arXiv](http://arxiv.org/find/quant-ph/1/au:+cleve/0/1/0/all/0/1) and [Google Scholar](http://scholar.google.ca/citations?user=dNq5mN4AAAAJ&hl=en))\
\
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)](https://quantum-journal.org/papers/q-2022-07-07-755/)\
[arXiv:1811.12575](https://arxiv.org/abs/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)](https://doi.org/10.4230/LIPIcs.ICALP.2017.17      )\
[arXiv:1612.09512](https://arxiv.org/abs/1612.09512)\
\
Perfect embezzlement of entanglement\
Richard Cleve, Li Liu, and Vern Paulsen\
[Journal of Mathematical Physics 58:012204 (2017)](http://aip.scitation.org/doi/10.1063/1.4974818)\
[arXiv:1606.05061](http://arxiv.org/abs/1606.05061)\
\
Perfect commuting-operator strategies for linear system games\
Richard Cleve, Li Liu, and William Slofstra\
[Journal of Mathematical Physics 58:012202 (2017)](http://aip.scitation.org/doi/10.1063/1.4973422)\
[arXiv:1606.02278](http://arxiv.org/abs/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](http://arxiv.org/abs/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)](http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.114.090502)\
[arXiv:1412.4687](http://arxiv.org/abs/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](http://arxiv.org/abs/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](http://eccc.hpi-web.de/author/019475/)\
\
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](http://arxiv.org/abs/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](http://arxiv.org/abs/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](http://arxiv.org/abs/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](http://arxiv.org/abs/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](http://arxiv.org/abs/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/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](http://arxiv.org/abs/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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)](http://www.sciencedirect.com/science/article/pii/S0020019005003121)\
(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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://qci.is.s.u-tokyo.ac.jp/qci/eqis03/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/0011065)\
 \
Quantum fingerprinting\
Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf\
Physical Review Letters, 87(16):167902 (2001)\
[arXiv:0102001](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/cs/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/9708016)\
\
Teleportation as a quantum computation\
Gilles Brassard, Samuel L. Braunstein, and Richard Cleve\
Physica D, 120:43-47 (1998)\
[journal version](http://www.sciencedirect.com/science/article/pii/S0167278998000438)\
\
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](http://dl.acm.org/citation.cfm?id=279092)\
\
Information-theoretic interpretation of quantum error-correcting codes\
Nicolas J. Cerf and Richard Cleve\
Physical Review A, 56(3):1721-1732 (1997)\
[arXiv:9702031](http://arxiv.org/abs/quant-ph/9702031)\
\
Substituting quantum entanglement for communication\
Richard Cleve and Harry Buhrman\
Physical Review A, 56(2):1201-1204 (1997)\
[arXiv:9704026](http://arxiv.org/abs/quant-ph/9704026)\
\
Efficient computations of encodings for quantum error correction\
Richard Cleve and Daniel Gottesman\
Physical Review A, 56(1):76-82 (1997)\
[arXiv:9607030](http://arxiv.org/abs/quant-ph/9607030)\
\
Quantum stabilizer codes and classical linear codes\
Richard Cleve\
Physical Review A, 55(6):4054-4059 (1997)\
[arXiv:9612048](http://arxiv.org/abs/quant-ph/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](http://www.sciencedirect.com/science/article/pii/S002200009690032X)\
\
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](http://arxiv.org/abs/quant-ph/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](http://arxiv.org/abs/quant-ph/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](http://epubs.siam.org/doi/abs/10.1137/S0097539792232586)\
\
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](http://www.sciencedirect.com/science/article/pii/S002200009690032X)\
\
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](http://www.sciencedirect.com/science/article/pii/S0095895683710130)\
\
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](http://dl.acm.org/citation.cfm?id=279092)\
\
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](http://epubs.siam.org/doi/abs/10.1137/0221006)\
\
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](http://epubs.siam.org/doi/abs/10.1137/S0097539792232586)\
\
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](http://link.springer.com/article/10.1007%2FBF01200059)\
\
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](http://link.springer.com/chapter/10.1007%2F3-540-38424-3_37)\
\
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](http://www.icsi.berkeley.edu/icsi/publication_details?n=596)\
\
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](http://link.springer.com/article/10.1007%2FBF01200059)\
\
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](http://link.springer.com/chapter/10.1007%2F0-387-34805-0_50)\
\
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](http://dl.acm.org/citation.cfm?id=62236)\
[journal version](http://epubs.siam.org/doi/pdf/10.1137/0221006)\
\
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](http://dl.acm.org/citation.cfm?id=12168)\
\
The entropy of a probability measure on a measurable space relative to a generating algebra\
Richard Cleve\
Master's thesis, University of Waterloo (1984)\