Publications (44)
Succinct quantum proofs for properties of finite groups
John Watrous
Many copies may be required for entanglement distillation
John Watrous
PSPACE has 2-round quantum interactive proof systems
John Watrous
Matchgate and space-bounded quantum computations are equivalent
Richard Jozsa, Barbara Kraus, Akimasa Miyake +1
Quantum interactive proofs with weak error bounds
Tsuyoshi Ito, Hirotada Kobayashi, John Watrous
Operational meaning of quantum measures of recovery
Tom Cooney, Christoph Hirche, Ciara Morgan +4
Quantum Proofs
Thomas Vidick, John Watrous
Bipartite subspaces having no LOCC-distinguishable bases
John Watrous
Optimal counterfeiting attacks and generalizations for Wiesner's quantum money
Abel Molina, Thomas Vidick, John Watrous
Parallel approximation of non-interactive zero-sum quantum games
Rahul Jain, John Watrous
Quantum algorithms for solvable groups
John Watrous
Einstein-Podolsky-Rosen steering provides the advantage in entanglement-assisted subchannel discrimination with one-way measurements
Marco Piani, John Watrous
Quantum statistical zero-knowledge
John Watrous
Sharp Quantum vs. Classical Query Complexity Separations
J. Niel de Beaudrap, Richard Cleve, John Watrous
Semidefinite programs for completely bounded norms
John Watrous
Simpler semidefinite programs for completely bounded norms
John Watrous
Hedging bets with correlated quantum strategies
Abel Molina, John Watrous
Consequences and Limits of Nonlocal Strategies
Richard Cleve, Peter Hoyer, Ben Toner +1
Quantum Arthur-Merlin Games
Chris Marriott, John Watrous
Quantum simulations of classical random walks and undirected graph connectivity
John Watrous
QIP = PSPACE
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay +1
On quantum and classical space-bounded processes with algebraic transition amplitudes
John Watrous
Two-message quantum interactive proofs are in PSPACE
Rahul Jain, Sarvagya Upadhyay, John Watrous
Quantum Computational Complexity
John Watrous
Entanglement in channel discrimination with restricted measurements
William Matthews, Marco Piani, John Watrous
On the hardness of distinguishing mixed-state quantum computations
Bill Rosgen, John Watrous
One-dimensional quantum walks with absorbing boundaries
Eric Bach, Susan Coppersmith, Marcel Paz Goldschen +2
Closed Timelike Curves Make Quantum and Classical Computing Equivalent
Scott Aaronson, John Watrous
Fast parallel circuits for the quantum Fourier transform
Richard Cleve, John Watrous
Distinguishing quantum operations having few Kraus operators
John Watrous
Toward a general theory of quantum games
Gus Gutoski, John Watrous
Mixing doubly stochastic quantum channels with the completely depolarizing channel
John Watrous
Quantum interactive proofs with short messages
Salman Beigi, Peter W. Shor, John Watrous
Zero-knowledge against quantum attacks
John Watrous
Coherent state exchange in multi-prover quantum interactive proof systems
Debbie Leung, Ben Toner, John Watrous
Continuous-time quantum walks on the symmetric group
Heath Gerhardt, John Watrous
Quantum Interactive Proofs with Competing Provers
Gus Gutoski, John Watrous
Adaptive versus non-adaptive strategies for quantum channel discrimination
Aram W. Harrow, Avinatan Hassidim, Debbie W. Leung +1
Quantum fingerprinting
Harry Buhrman, Richard Cleve, John Watrous +1
Notes on super-operator norms induced by Schatten norms
John Watrous
Zero-knowledge proof systems for QMA
Anne Broadbent, Zhengfeng Ji, Fang Song +1
Ancilla dimension in quantum channel discrimination
Daniel Puzzuoli, John Watrous
Extended nonlocal games and monogamy-of-entanglement games
Nathaniel Johnston, Rajat Mittal, Vincent Russo +1
Two-way finite automata with quantum and classical states
Andris Ambainis, John Watrous