  Several kinds of quantum pushdown automaton models have been proposed, and
their computational power is investigated intensively. However, for some
quantum pushdown automaton models, it is not known whether quantum models are
at least as powerful as classical counterparts or not. This is due to the
reversibility restriction. In this paper, we introduce a new quantum pushdown
automaton model that has a garbage tape. This model can overcome the
reversibility restriction by exploiting the garbage tape to store popped
symbols. We show that the proposed model can simulate any quantum pushdown
automaton with a classical stack as well as any probabilistic pushdown
automaton. We also show that our model can solve a certain promise problem
exactly while deterministic pushdown automata cannot. These results imply that
our model is strictly more powerful than classical counterparts in the setting
of exact, one-sided error and non-deterministic computation.
