dorsal/arxiv
View SchemaQuantum subroutine problem and the robustness of quantum complexity classes
| Authors | Harumichi Nishimura, Masanao Ozawa |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0107089 |
| URL | https://arxiv.org/abs/quant-ph/0107089 |
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.
{
"annotation_id": "8d79c042-34c7-43d4-abb8-39f97232b373",
"date_created": "2026-03-02T18:01:46.073000Z",
"date_modified": "2026-03-02T18:01:46.073000Z",
"file_hash": "df75fdf5fc7a104ae40b39c81c09e494b79c2772ed84197c8f0ab818fa02cece",
"private": false,
"record": {
"abstract": "This paper positively solves the quantum subroutine problem for fully quantum\noracles. The quantum subroutine problem asks whether a quantum computer with an\nefficiently computable oracle can be efficiently simulated by a non-oracle\nquantum computer. We extends the earlier results obtained by Bennett,\nBernstein, Brassard, and Vazirani, and by Aharonov, Kitaev, and Nisan to the\ncase where the oracle evaluates a unitary operator and the computer is allowed\nto be in the superposition of a query state and a non-query state during\ncomputation. We also prove the robustness of {\\bf EQP}, {\\bf BQP}, and {\\bf\nZQP} under the above general formulation, extending the earlier results on the\nrobustness of {\\bf BQP} shown by Bennett et al.",
"arxiv_id": "quant-ph/0107089",
"authors": [
"Harumichi Nishimura",
"Masanao Ozawa"
],
"categories": [
"quant-ph"
],
"title": "Quantum subroutine problem and the robustness of quantum complexity classes",
"url": "https://arxiv.org/abs/quant-ph/0107089"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9334132b-6a08-4d17-8a5a-3dc6cc682134",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}