John Watrous

Most-cited papers

Quantum fingerprinting.
H. Buhrman, R. Cleve, John Watrous, R. de Wolf
2001Physical Review Letters1,155 citations Open access
Semantic Scholar
One-dimensional quantum walks
A. Ambainis, E. Bach, A. Nayak, A. Vishwanath +1 more
2001Symposium on the Theory of Computing640 citations
Semantic Scholar
Consequences and limits of nonlocal strategies
R. Cleve, Peter Høyer, Ben Toner, John Watrous
2004Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004.519 citations
Semantic Scholar
On the power of quantum finite state automata
Attila Kondacs, John Watrous
1997Proceedings 38th Annual Symposium on Foundations of Computer Science392 citations
Semantic Scholar
Necessary and sufficient quantum information characterization of Einstein-Podolsky-Rosen steering.
M. Piani, John Watrous
2015Physical Review Letters367 citations Open access
Semantic Scholar
Quantum Computational Complexity
John Watrous
2008Encyclopedia of Complexity and Systems Science352 citations Open access
Semantic Scholar
Quantum Arthur–Merlin games
Chris Marriott, John Watrous
2004Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004.309 citations Open access
Semantic Scholar
Fast parallel circuits for the quantum Fourier transform
R. Cleve, John Watrous
2000Proceedings 41st Annual Symposium on Foundations of Computer Science294 citations Open access
Semantic Scholar
Zero-knowledge against quantum attacks
John Watrous
2005Symposium on the Theory of Computing285 citations Open access
Semantic Scholar
Toward a general theory of quantum games
Gus Gutoski, John Watrous
2006Symposium on the Theory of Computing273 citations Open access
Semantic Scholar
Semidefinite Programs for Completely Bounded Norms
John Watrous
2009Theory of Computing239 citations Open access
Semantic Scholar
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
A. Kitaev, John Watrous
2000Symposium on the Theory of Computing216 citations
Semantic Scholar
Quantum simulations of classical random walks and undirected graph connectivity
John Watrous
1998Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317)193 citations Open access
Semantic Scholar
On one-dimensional quantum cellular automata
John Watrous
1995Proceedings of IEEE 36th Annual Foundations of Computer Science184 citations
Semantic Scholar
Succinct quantum proofs for properties of finite groups
John Watrous
2000Proceedings 41st Annual Symposium on Foundations of Computer Science182 citations Open access
Semantic Scholar
QIP = PSPACE
Rahul Jain, Zheng-Feng Ji, Sarvagya Upadhyay, John Watrous
2009Symposium on the Theory of Computing158 citations
Semantic Scholar
All entangled states are useful for channel discrimination.
M. Piani, John Watrous
2009Physical Review Letters146 citations Open access
Semantic Scholar
PSPACE has constant-round quantum interactive proof systems
John Watrous
199940th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)135 citations Open access
Semantic Scholar
Limits on the power of quantum statistical zero-knowledge
John Watrous
2002The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.134 citations
Semantic Scholar
Simpler semidefinite programs for completely bounded norms
John Watrous
2012Chicago journal of theoretical computer science129 citations
Semantic Scholar
One-dimensional quantum walks with absorbing boundaries
E. Bach, S. Coppersmith, Marcel Paz Goldschen, R. Joynt +1 more
2002Journal of computer and system sciences (Print)126 citations Open access
Semantic Scholar
Notes on super-operator norms induced by schatten norms
John Watrous
2004Quantum information & computation118 citations
Semantic Scholar
Bipartite subspaces having no bases distinguishable by local operations and classical communication.
John Watrous
2005Physical Review Letters117 citations Open access
Semantic Scholar
Closed timelike curves make quantum and classical computing equivalent
S. Aaronson, John Watrous
2008Proceedings of the Royal Society A113 citations Open access
Semantic Scholar
Adaptive versus nonadaptive strategies for quantum channel discrimination
A. Harrow, A. Hassidim, D. Leung, John Watrous
2009109 citations Open access
Semantic Scholar
Two-way finite automata with quantum and classical state
A. Ambainis, John Watrous
1999Theoretical Computer Science106 citations Open access
Semantic Scholar
Quantum algorithms for solvable groups
John Watrous
2000Symposium on the Theory of Computing102 citations Open access
Semantic Scholar
Limitations on Separable Measurements by Convex Optimization
Somshubhro Bandyopadhyay, Alessandro Cosentino, N. Johnston, Vincent Russo +2 more
2014IEEE Transactions on Information Theory78 citations Open access
Semantic Scholar
On the hardness of distinguishing mixed-state quantum computations
Bill Rosgen, John Watrous
2004Cybersecurity and Cyberforensics Conference77 citations Open access
Semantic Scholar
Space-Bounded Quantum Complexity
John Watrous
1999Journal of computer and system sciences (Print)74 citations Open access
Semantic Scholar
On the complexity of simulating space-bounded quantum computations
John Watrous
2004Computational Complexity70 citations
Semantic Scholar
Two-Message Quantum Interactive Proofs Are in PSPACE
Rahul Jain, Sarvagya Upadhyay, John Watrous
20092009 50th Annual IEEE Symposium on Foundations of Computer Science66 citations Open access
Semantic Scholar
Matchgate and space-bounded quantum computations are equivalent
R. Jozsa, B. Kraus, A. Miyake, John Watrous
2009Proceedings of the Royal Society A65 citations Open access
Semantic Scholar
Optimal Counterfeiting Attacks and Generalizations for Wiesner's Quantum Money
Abel Molina, T. Vidick, John Watrous
2012Theory of Quantum Computation, Communication, and Cryptography61 citations Open access
Semantic Scholar
Continuous-Time Quantum Walks on the Symmetric Group
Heath Gerhardt, John Watrous
2003RANDOM-APPROX61 citations Open access
Semantic Scholar
Zero-Knowledge Proof Systems for QMA
Anne Broadbent, Zheng-Feng Ji, Fang Song, John Watrous
2016IEEE Annual Symposium on Foundations of Computer Science59 citations Open access
Semantic Scholar
Quantum Proofs
T. Vidick, John Watrous
2016Foundations and Trends® in Theoretical Computer Science55 citations Open access
Semantic Scholar
Parallel Approximation of Non-interactive Zero-sum Quantum Games
Rahul Jain, John Watrous
20082009 24th Annual IEEE Conference on Computational Complexity50 citations Open access
Semantic Scholar
Coherent state exchange in multi-prover quantum interactive proof systems
D. Leung, B. Toner, John Watrous
2008Chicago journal of theoretical computer science49 citations
Semantic Scholar
Many Copies May Be Required for Entanglement Distillation
John Watrous
200341 citations Open access
Semantic Scholar
Distinguishing quantum operations having few Kraus operators
John Watrous
2007Quantum information & computation40 citations Open access
Semantic Scholar
Extended non-local games and monogamy-of-entanglement games
N. Johnston, R. Mittal, Vincent Russo, John Watrous
2015Proceedings of the Royal Society A35 citations Open access
Semantic Scholar
Entanglement in channel discrimination with restricted measurements
W. Matthews, M. Piani, John Watrous
201035 citations Open access
Semantic Scholar
Einstein-Podolsky-Rosen steering provides the advantage in entanglement-assisted subchannel discrimination with one-way measurements
M. Piani, John Watrous
201434 citations Open access
Semantic Scholar
Sharp Quantum versus Classical Query Complexity Separations
J. Niel de Beaudrap, R. Cleve, John Watrous
2002Algorithmica34 citations
Semantic Scholar
On the Mixed-Unitary Rank of Quantum Channels
Mark W. Girard, D. Leung, Jeremy Levick, Chi-Kwong Li +3 more
2020Communications in Mathematical Physics33 citations Open access
Semantic Scholar
Quantum Interactive Proofs with Competing Provers
Gus Gutoski, John Watrous
2004Symposium on Theoretical Aspects of Computer Science33 citations Open access
Semantic Scholar
Revisiting the simulation of quantum Turing machines by quantum circuits
Abel Molina, John Watrous
2018Proceedings of the Royal Society A31 citations Open access
Semantic Scholar
Mixing doubly stochastic quantum channels with the completely depolarizing channel
John Watrous
2008Quantum information & computation27 citations Open access
Semantic Scholar
On the complementary quantum capacity of the depolarizing channel
D. Leung, John Watrous
2015Quantum25 citations Open access
Semantic Scholar