11 citations · 21 across the 4 of their papers we have counts for
Showing 1999Show all
3 papers · 1 filter
cs.CC1999
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…
cs.CC1999
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…
cs.CC1999
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…