2001/07/17 by Harumichi Nishimura, Nishimura, Harumichi, Masanao Ozawa +1
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0107089
Latex, 22 pages
arxiv created 2001/07/17 · openalex publication_date 2001/07/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.