John Watrous

According to our database, John Watrous authored at least 53 papers between 1995 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Complexity Limitations on One-turn Quantum Refereed Games.

Soumik Ghosh, John Watrous

Theory Comput. Syst., April, 2023

2022

Quantum game theory and the complexity of approximating quantum Nash equilibria.

John Bostanci, John Watrous

Quantum, September, 2022

2021

Certifying optimality for convex quantum channel optimization problems.

Bryan Coutts, Mark Girard, John Watrous

Quantum, 2021

2020

Zero-Knowledge Proof Systems for QMA.

Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous

SIAM J. Comput., 2020

Detecting mixed-unitary quantum channels is NP-hard.

Colin Do-Yan Lee, John Watrous

Quantum, 2020

2018

Revisiting the simulation of quantum Turing machines by quantum circuits.

Abel Molina, John Watrous

CoRR, 2018

Oracle Separations for Quantum Statistical Zero-Knowledge.

Sanketh Menda, John Watrous

CoRR, 2018

Extended Nonlocal Games from Quantum-Classical Games.

Vincent Russo, John Watrous

Chic. J. Theor. Comput. Sci., 2018

2016

Quantum Proofs.

Thomas Vidick, John Watrous

Found. Trends Theor. Comput. Sci., 2016

2015

Limitations on Separable Measurements by Convex Optimization.

Somshubhro Bandyopadhyay, Alessandro Cosentino, Nathaniel Johnston, Vincent Russo, John Watrous, Nengkun Yu

IEEE Trans. Inf. Theory, 2015

2013

Simpler semidefinite programs for completely bounded norms.

John Watrous

Chic. J. Theor. Comput. Sci., 2013

Coherent state exchange in multi-prover quantum interactive proof systems.

Debbie W. Leung, Benjamin Toner, John Watrous

Chic. J. Theor. Comput. Sci., 2013

2012

Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011).

Kousha Etessami, Dieter van Melkebeek, Seth Pettie, John Watrous, Salil P. Vadhan

SIAM J. Comput., 2012

Optimal Counterfeiting Attacks and Generalizations for Wiesner's Quantum Money.

Abel Molina, Thomas Vidick, John Watrous

Proceedings of the Theory of Quantum Computation, 2012

Quantum interactive proofs with weak error bounds.

Tsuyoshi Ito, Hirotada Kobayashi, John Watrous

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

Quantum Interactive Proofs with Short Messages.

Salman Beigi, Peter W. Shor, John Watrous

Theory Comput., 2011

Guest column: an introduction to quantum information and quantum circuits 1.

John Watrous

SIGACT News, 2011

QIP = PSPACE.

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous

J. ACM, 2011

2009

Quantum Computational Complexity.

John Watrous

Proceedings of the Encyclopedia of Complexity and Systems Science, 2009

Semidefinite Programs for Completely Bounded Norms.

John Watrous

Theory Comput., 2009

Zero-Knowledge against Quantum Attacks.

John Watrous

SIAM J. Comput., 2009

Mixing doubly stochastic quantum channels with the completely depolarizing channel.

John Watrous

Quantum Inf. Comput., 2009

Two-Message Quantum Interactive Proofs Are in PSPACE.

Rahul Jain, Sarvagya Upadhyay, John Watrous

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Parallel Approximation of Non-interactive Zero-sum Quantum Games.

Rahul Jain, John Watrous

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Distinguishing quantum operations having few Kraus operators.

John Watrous

Quantum Inf. Comput., 2008

Closed Timelike Curves Make Quantum and Classical Computing Equivalent.

Scott Aaronson, John Watrous

Electron. Colloquium Comput. Complex., 2008

2007

Toward a general theory of quantum games.

Gus Gutoski, John Watrous

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2005

Notes on super-operator norms induced by schatten norms.

John Watrous

Quantum Inf. Comput., 2005

Quantum Arthur-Merlin games.

Chris Marriott, John Watrous

Comput. Complex., 2005

Quantum Interactive Proofs with Competing Provers.

Gus Gutoski, John Watrous

Proceedings of the STACS 2005, 2005

2004

One-dimensional quantum walks with absorbing boundaries.

Eric Bach, Susan N. Coppersmith, Marcel Paz Goldschen, Robert Joynt, John Watrous

J. Comput. Syst. Sci., 2004

On the hardness of distinguishing mixed-state quantum computations

Bill Rosgen, John Watrous

CoRR, 2004

Consequences and Limits of Nonlocal Strategies.

Richard Cleve, Peter Høyer, Benjamin Toner, John Watrous

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

PSPACE has constant-round quantum interactive proof systems.

John Watrous

Theor. Comput. Sci., 2003

On the complexity of simulating space-bounded quantum computations.

John Watrous

Comput. Complex., 2003

Continuous-Time Quantum Walks on the Symmetric Group.

Heath Gerhardt, John Watrous

Proceedings of the Approximation, 2003

2002

Two-way finite automata with quantum and classical state.

Andris Ambainis, John Watrous

Theor. Comput. Sci., 2002

Sharp Quantum versus Classical Query Complexity Separations.

J. Niel de Beaudrap, Richard Cleve, John Watrous

Algorithmica, 2002

imits on the Power of Quantum Statistical Zero-Knowledge.

John Watrous

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Arthur and Merlin in a Quantum World.

John Watrous

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity.

John Watrous

J. Comput. Syst. Sci., 2001

Quantum algorithms for solvable groups.

John Watrous

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

One-dimensional quantum walks.

Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

Parallelization, amplification, and exponential time simulation of quantum interactive proof systems.

Alexei Y. Kitaev, John Watrous

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Succinct quantum proofs for properties of finite groups.

John Watrous

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Fast parallel circuits for the quantum Fourier transform.

Richard Cleve, John Watrous

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Space-Bounded Quantum Complexity.

John Watrous

J. Comput. Syst. Sci., 1999

Two-way finite automata with quantum and classical states

Andris Ambainis, John Watrous

CoRR, 1999

PSPACE has 2-round quantum interactive proof systems

John Watrous

CoRR, 1999

On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes.

John Watrous

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Relationships Between Quantum and Classical Space-Bounded Complexity Classes.

John Watrous

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

On the Power of Quantum Finite State Automata.

Attila Kondacs, John Watrous

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1995

On One-Dimensional Quantum Cellular Automata.

John Watrous

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995