  In this paper, we introduce a new public quantum interactive proof system and
the first quantum alternating Turing machine: qAM proof system and qATM,
respectively. Both are obtained from their classical counterparts
(Arthur-Merlin proof system and alternating Turing machine, respectively,) by
augmenting them with a fixed-size quantum register. We focus on space-bounded
computation, and obtain the following surprising results: Both of them with
constant-space are Turing-equivalent. More specifically, we show that for any
Turing-recognizable language, there exists a constant-space weak-qAM system,
(the nonmembers do not need to be rejected with high probability), and we show
that any Turing-recognizable language can be recognized by a constant-space
qATM even with one-way input head.
  For strong proof systems, where the nonmembers must be rejected with high
probability, we show that the known space-bounded classical private protocols
can also be simulated by our public qAM system with the same space bound.
Besides, we introduce a strong version of qATM: The qATM that must halt in
every computation path. Then, we show that strong qATMs (similar to private
ATMs) can simulate deterministic space with exponentially less space. This
leads to shifting the deterministic space hierarchy exactly by one-level. The
method behind the main results is a new public protocol cleverly using its
fixed-size quantum register. Interestingly, the quantum part of this public
protocol cannot be simulated by any space-bounded classical protocol in some
cases.
