Abstract
This paper positively solves the quantum subroutine problem for fully quantum oracles. The quantum subroutine problem asks whether a quantum computer with an efficiently computable oracle can be efficiently simulated by a non-oracle quantum computer. We extends the earlier results obtained by Bennett, Bernstein, Brassard, and Vazirani, and by Aharonov, Kitaev, and Nisan to the case where the oracle evaluates a unitary operator and the computer is allowed to be in the superposition of a query state and a non-query state during computation. We also prove the robustness of \{\bf EQP\}, \{\bf BQP\}, and \{\bf ZQP\} under the above general formulation, extending the earlier results on the robustness of \{\bf BQP\} shown by Bennett et al.