11 citations · 21 across the 4 of their papers we have counts for
6 papers · 1 filter
Quantum Arthur-Merlin Games
Chris Marriott, 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 informa…
Succinct quantum proofs for properties of finite groups
John Watrous
In this paper we consider a quantum computational variant of nondeterminism based on the notion of a quantum proof, which is a quantum state that plays a role similar to a certific…
Two-way finite automata with quantum and classical states
Andris Ambainis, John Watrous
We introduce 2-way finite automata with quantum and classical states (2qcfa's). This is a variant on the 2-way quantum finite automata (2qfa) model which may be simpler to implemen…
On quantum and classical space-bounded processes with algebraic transition amplitudes
John Watrous
We define a class of stochastic processes based on evolutions and measurements of quantum systems, and consider the complexity of predicting their long-term behavior. It is shown t…
PSPACE has 2-round quantum interactive proof systems
John Watrous
In this paper we consider quantum interactive proof systems, i.e., interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum…
Quantum simulations of classical random walks and undirected graph connectivity
John Watrous
It is not currently known if quantum Turing machines can efficiently simulate probabilistic computations in the space-bounded case. In this paper we show that space-bounded quantum…