John Watrous

John Watrous

Auto-generated profile, based on publicly available information

John Watrous

Institute for Quantum Computing and School of Computer Science, University of Waterloo

Research Focus & Metrics

Academic Career Length

28Years (1999-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
26 September 2001 in Physical Review Letters
Verified
Journal Article
Closed access
PDF file
HBHarry Buhrman
Harry Buhrman
RCRichard Cleve
Richard Cleve
JWJohn Watrous
John Watrous
RWRonald de Wolf
Ronald de Wolf
Classical fingerprinting associates with each string a shorter string (its fingerprint), such that any two distinct strings can be distinguished with small error by comparing their fingerprints alone. The fingerprints cannot be made exponentially smaller than the original strings unless the parties preparing the fingerprints have access to correlated random sources. We show that fingerprints consisting of quantum information can be made exponentially smaller than the original strings without any correlations or entanglement between the parties. This implies an exponential quantum/classical gap for the equality problem in the simultaneous message passing model of communication complexity.

26 April 2018
Verified
Book
Closed access
JWJohn Watrous
John Watrous
This largely self-contained book on the theory of quantum information focuses on precise mathematical formulations and proofs of fundamental facts that form the foundation of the subject. It is intended for graduate students and researchers in mathematics, computer science, and theoretical physics seeking to develop a thorough understanding of key results, proof techniques, and methodologies that are relevant to a wide range of research topics within the theory of quantum information and computation. The book is accessible to readers with an understanding of basic mathematics, including linear algebra, mathematical analysis, and probability theory. An introductory chapter summarizes these necessary mathematical prerequisites, and starting from this foundation, the book includes clear and complete proofs of all results it presents. Each subsequent chapter includes challenging exercises intended to help readers to develop their own skills for discovering proofs concerning the theory of quantum information.

12 February 2015 in Physical Review Letters
Verified
Journal Article
Closed access
PDF file
MPMarco Piani
Marco Piani
JWJohn Watrous
John Watrous
Steering is the entanglement-based quantum effect that embodies the “spooky action at a distance” disliked by Einstein and scrutinized by Einstein, Podolsky, and Rosen. Here we provide a necessary and sufficient characterization of steering, based on a quantum information processing task: the discrimination of branches in a quantum evolution, which we dub subchannel discrimination. We prove that, for any bipartite steerable state, there are instances of the quantum subchannel discrimination problem for which this state allows a correct discrimination with strictly higher probability than in the absence of entanglement, even when measurements are restricted to local measurements aided by one-way communication. On the other hand, unsteerable states are useless in such conditions, even when entangled. We also prove that the above steering advantage can be exactly quantified in terms of the steering robustness, which is a natural measure of the steerability exhibited by the state.

6 July 2001
Verified
Conference Paper
Open access
AAAndris Ambainis
Andris Ambainis
EBEric Bach
Eric Bach
ANAshwin Nayak
Ashwin Nayak
AVAshvin Vishwanath
Ashvin Vishwanath
JWJohn Watrous
John Watrous
We define and analyze quantum computational variants of random walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random walk, which we call the Hadamard walk. Several striking differences between the quantum and classical cases are observed. For example, when unrestricted in either direction, the Hadamard walk has position that is nearly uniformly distributed in the range [-t/\sqrt 2, t/\sqrt 2] after t steps, which is in sharp contrast to the classical random walk, which has distance O(\sqrt t) from the origin with high probability. With an absorbing boundary immediately to the left of the starting position, the probability that the walk exits to the left is 2/&pgr, and with an additional absorbing boundary at location n, the probability that the walk exits to the left actually increases, approaching 1/\sqrt 2 in the limit. In the classical case both values are 1.

1 June 2005 in computational complexity
Verified
Journal Article
Open access
PDF file
CMChris Marriott
Chris Marriott
JWJohn Watrous
John Watrous
This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that \( {\text{QMA}} \subseteq {\text{PP}}. \) Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.

13 November 2004
Verified
Conference Paper
Closed access
RCR. Cleve
R. Cleve
PHP. Hoyer
P. Hoyer
BTB. Toner
B. Toner
JWJ. Watrous
J. Watrous