# John Watrous

According to our database

Collaborative distances:

^{1}, John Watrous authored at least 51 papers between 1995 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2020

Complexity limitations on one-turn quantum refereed games.

CoRR, 2020

2019

Detecting mixed-unitary quantum channels is NP-hard.

CoRR, 2019

2018

Revisiting the simulation of quantum Turing machines by quantum circuits.

CoRR, 2018

Oracle Separations for Quantum Statistical Zero-Knowledge.

CoRR, 2018

Extended Nonlocal Games from Quantum-Classical Games.

Chicago J. Theor. Comput. Sci., 2018

2016

Quantum Proofs.

Foundations and Trends in Theoretical Computer Science, 2016

Zero-Knowledge Proof Systems for QMA.

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Limitations on Separable Measurements by Convex Optimization.

IEEE Trans. Information Theory, 2015

2013

Simpler semidefinite programs for completely bounded norms.

Chicago J. Theor. Comput. Sci., 2013

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

Chicago J. Theor. Comput. Sci., 2013

2012

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

SIAM J. Comput., 2012

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

Proceedings of the Theory of Quantum Computation, 2012

Quantum interactive proofs with weak error bounds.

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

Quantum Interactive Proofs with Short Messages.

Theory of Computing, 2011

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

SIGACT News, 2011

QIP = PSPACE.

J. ACM, 2011

2009

Quantum Computational Complexity.

Proceedings of the Encyclopedia of Complexity and Systems Science, 2009

Semidefinite Programs for Completely Bounded Norms.

Theory of Computing, 2009

Zero-Knowledge against Quantum Attacks.

SIAM J. Comput., 2009

Mixing doubly stochastic quantum channels with the completely depolarizing channel.

Quantum Information & Computation, 2009

Two-Message Quantum Interactive Proofs Are in PSPACE.

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

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

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

2008

Distinguishing quantum operations having few Kraus operators.

Quantum Information & Computation, 2008

Closed Timelike Curves Make Quantum and Classical Computing Equivalent.

Electronic Colloquium on Computational Complexity (ECCC), 2008

2007

Toward a general theory of quantum games.

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

2005

Notes on super-operator norms induced by schatten norms.

Quantum Information & Computation, 2005

Quantum Arthur-Merlin games.

Computational Complexity, 2005

Quantum Interactive Proofs with Competing Provers.

Proceedings of the STACS 2005, 2005

2004

One-dimensional quantum walks with absorbing boundaries.

J. Comput. Syst. Sci., 2004

On the hardness of distinguishing mixed-state quantum computations

CoRR, 2004

Consequences and Limits of Nonlocal Strategies.

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

2003

PSPACE has constant-round quantum interactive proof systems.

Theor. Comput. Sci., 2003

On the complexity of simulating space-bounded quantum computations.

Computational Complexity, 2003

Continuous-Time Quantum Walks on the Symmetric Group.

Proceedings of the Approximation, 2003

2002

Two-way finite automata with quantum and classical state.

Theor. Comput. Sci., 2002

Sharp Quantum versus Classical Query Complexity Separations.

Algorithmica, 2002

imits on the Power of Quantum Statistical Zero-Knowledge.

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

Arthur and Merlin in a Quantum World.

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

2001

Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity.

J. Comput. Syst. Sci., 2001

Quantum algorithms for solvable groups.

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

One-dimensional quantum walks.

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.

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

Succinct quantum proofs for properties of finite groups.

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

Fast parallel circuits for the quantum Fourier transform.

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

1999

Space-Bounded Quantum Complexity.

J. Comput. Syst. Sci., 1999

Two-way finite automata with quantum and classical states

CoRR, 1999

PSPACE has 2-round quantum interactive proof systems

CoRR, 1999

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

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

1998

Relationships Between Quantum and Classical Space-Bounded Complexity Classes.

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

1997

On the Power of Quantum Finite State Automata.

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

1995

On One-Dimensional Quantum Cellular Automata.

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