Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0107089

Quantum subroutine problem and the robustness of quantum complexity classes

Harumichi Nishimura, Masanao Ozawa

Published Jul 17, 2001• 0 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.quant-ph/0107089

Related papers

Quantum Oracles and Computational Complexity (Algebraic Systems, Formal Languages and Computations)

Harumichi Nishimura, Masanao Ozawa

In this paper, we consider the following problem (the subroutine problem).If the operation performed by an oracle is efficiently computable, can a non-oracle quantum computer simulate a quantum computer with this oracle efficiently ?Bennett et al. and Aharonov et al. respectively solved the subroutine problem when their oracles evaluate deterministic and probabilistic functions.However, both of them considered only the case where machines enter the query mode deterministically.We extend the notion of an oracle of a quantum computer to a device for performing a unitary transformation, and solve the subroutine problem in the general setting where a query state and a nonquery state may superpose.Using this result, we show that EQP and BQP are robust in the general setting, which extends the robustness of BQP shown by Bennett et al. in the case where machines enter the query mode deterministically.Moreover, we prove the robustness of ZQP by improving.themethod of Bennett et al. employed for the above BQP result.

数理解析研究所講究録•Aug 1, 2000•0 citations

On Quantum Computing and Pseudorandomness

William Jason Fefferman

The relationship between efficient verification and quantum computing is one of the most important and least well-understood questions in the theory of computation. In particular, is there a problem that can be solved efficiently on a quantum computer that cannot be verified? In this thesis we give evidence that BQP ⊄ PH, relating the classes of languages decidable with a quantum computer to a generalization of NP. In so doing we connect a question in pseudorandomness, first studied [BSW03] to the problem of finding an oracle relative to which BQP ⊄ PH. The primary technical challenge is to construct a unitary matrix, realized by an efficient quantum circuit and whose rows are supported on nearly disjoint subsets. Using this matrix and assuming the validity of the aforementioned question in pseudorandomness, we show an instantiation of the Nisan-Wigderson pseudorandom generator that can be broken with quantum computers, but not with the relevant mode of classical computation.

•Feb 2, 2011•0 citations

Quantum bounded query complexity

Harry Buhrman, Wim van Dam

We combine the classical notions and techniques for bounded query classes with those developed in quantum computing. We give strong evidence that quantum queries to an oracle in the class NP does indeed reduce the query, complexity of decision problems. Under traditional complexity assumptions, we obtain an exponential speedup between the quantum and the classical query complexity of function classes. For decision problems and function classes we obtain the following results: P/sub /spl par///sup NP[2k]//spl sube/EQP/sub /spl par///sup NP[k]/; P/sub /spl par///sup NP[2k+1-2]//spl sube/EQP/sup NP[k]/; FP/sub /spl par///sup NP[2k=1-2]//spl sube/FEQP/sup NP[2k]/; FP/sub /spl par///sup NP/spl sube/FEQP(NP[Olog n)]/. For sets A that are many-one complete for PSPACE or EXP we show that Fp/sup A//spl sube/FEQP/sup A[1]/. Sets A that are many-one complete for PP have the property that FP/sub /spl par///sup A//spl sube/FEQP/sup A[1]/. In general we prove that for any set A there is a set X such that FP/sup A//spl sube/FEQP/sup X[1]/, establishing that no set is superterse in the quantum setting.

arXiv:quant-ph/9903035•IEEE Conference on Computational Complexity (CCC)•Jan 20, 2003•8 citations

A Separation Between Types of Quantum Oracle Separations

Scott Aaronson, Adam Bouland, Jordan Docter +1 more

Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes $\mathsf{PostBQP}$ and $\mathsf{PreciseBQP}$, the exponentially precise variant of $\mathsf{BQP}$. Both classes equal $\mathsf{PP}$ in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.

quant-pharXiv:2609.38704•Oct 1, 2026•0 citations

Oracle separations of hybrid quantum-classical circuits

Atul Singh Arora, Alexandru Gheorghiu, Singh, Uttam

An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models, that combine poly-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a d-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a d-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung & Lai (STOC 2020) and Coudron & Menda (STOC 2020) showed that these models (with d=log^O(1) (n)) are strictly weaker than BQP (the class of problems solvable by poly-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. We show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d $\nsubseteq$ QC_d and QC_d $\nsubseteq$ CQ_d relative to an oracle. In other words, there exist problems that one model can solve but not the other and vice versa. We do this by considering new oracle problems that capture the distinctions between the two models and by introducing the notion of an intrinsically stochastic oracle, an oracle whose responses are inherently randomised, which is used for our second result. While we leave showing the second separation relative to a standard oracle as an open problem, we believe the notion of stochastic oracles could be of independent interest for studying complexity classes which have resisted separation in the standard oracle model. Our constructions also yield simpler oracle separations between the hybrid models and BQP, compared to earlier works.

arXiv:2201.01904•Jan 6, 2022•3 citations

Oracle Quantum Computing

Departement Iro

This paper continues the study of the power of oracles to separate quantum com.plexity classes from classical (including probabilistic and nondeterministic) complexity classes, which we initiated in an earlier paper [5]. The new results are that, under appropriate oracles, (1) there is a decision problem that can be solved in polynomial time on the quantum computer, which would classically require exponential time in the worst case even on a nondeterministic computer (in particular QP g NP relative to this oracle), and (2) there is a decision problem that can be solved in exponential time on the quantum computer for which any deterministic classical computer would require double exponential time on all but finitely many instances.

•Jan 1, 1993•6 citations
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.
In this paper, we consider the following problem (the subroutine problem).If the operation performed by an oracle is efficiently computable, can a non-oracle quantum computer simulate a quantum computer with this oracle efficiently ?Bennett et al. and Aharonov et al. respectively solved the subroutine problem when their oracles evaluate deterministic and probabilistic functions.However, both of them considered only the case where machines enter the query mode deterministically.We extend the notion of an oracle of a quantum computer to a device for performing a unitary transformation, and solve the subroutine problem in the general setting where a query state and a nonquery state may superpose.Using this result, we show that EQP and BQP are robust in the general setting, which extends the robustness of BQP shown by Bennett et al. in the case where machines enter the query mode deterministically.Moreover, we prove the robustness of ZQP by improving.themethod of Bennett et al. employed for the above BQP result.
The relationship between efficient verification and quantum computing is one of the most important and least well-understood questions in the theory of computation. In particular, is there a problem that can be solved efficiently on a quantum computer that cannot be verified? In this thesis we give evidence that BQP ⊄ PH, relating the classes of languages decidable with a quantum computer to a generalization of NP. In so doing we connect a question in pseudorandomness, first studied [BSW03] to the problem of finding an oracle relative to which BQP ⊄ PH. The primary technical challenge is to construct a unitary matrix, realized by an efficient quantum circuit and whose rows are supported on nearly disjoint subsets. Using this matrix and assuming the validity of the aforementioned question in pseudorandomness, we show an instantiation of the Nisan-Wigderson pseudorandom generator that can be broken with quantum computers, but not with the relevant mode of classical computation.
We combine the classical notions and techniques for bounded query classes with those developed in quantum computing. We give strong evidence that quantum queries to an oracle in the class NP does indeed reduce the query, complexity of decision problems. Under traditional complexity assumptions, we obtain an exponential speedup between the quantum and the classical query complexity of function classes. For decision problems and function classes we obtain the following results: P/sub /spl par///sup NP[2k]//spl sube/EQP/sub /spl par///sup NP[k]/; P/sub /spl par///sup NP[2k+1-2]//spl sube/EQP/sup NP[k]/; FP/sub /spl par///sup NP[2k=1-2]//spl sube/FEQP/sup NP[2k]/; FP/sub /spl par///sup NP/spl sube/FEQP(NP[Olog n)]/. For sets A that are many-one complete for PSPACE or EXP we show that Fp/sup A//spl sube/FEQP/sup A[1]/. Sets A that are many-one complete for PP have the property that FP/sub /spl par///sup A//spl sube/FEQP/sup A[1]/. In general we prove that for any set A there is a set X such that FP/sup A//spl sube/FEQP/sup X[1]/, establishing that no set is superterse in the quantum setting.
Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes PostBQP\mathsf{PostBQP}PostBQP and PreciseBQP\mathsf{PreciseBQP}PreciseBQP, the exponentially precise variant of BQP\mathsf{BQP}BQP. Both classes equal PP\mathsf{PP}PP in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.
An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models, that combine poly-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a d-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a d-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung & Lai (STOC 2020) and Coudron & Menda (STOC 2020) showed that these models (with d=log^O(1) (n)) are strictly weaker than BQP (the class of problems solvable by poly-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. We show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d ⊈\nsubseteq⊈ QC_d and QC_d ⊈\nsubseteq⊈ CQ_d relative to an oracle. In other words, there exist problems that one model can solve but not the other and vice versa. We do this by considering new oracle problems that capture the distinctions between the two models and by introducing the notion of an intrinsically stochastic oracle, an oracle whose responses are inherently randomised, which is used for our second result. While we leave showing the second separation relative to a standard oracle as an open problem, we believe the notion of stochastic oracles could be of independent interest for studying complexity classes which have resisted separation in the standard oracle model. Our constructions also yield simpler oracle separations between the hybrid models and BQP, compared to earlier works.
This paper continues the study of the power of oracles to separate quantum com.plexity classes from classical (including probabilistic and nondeterministic) complexity classes, which we initiated in an earlier paper [5]. The new results are that, under appropriate oracles, (1) there is a decision problem that can be solved in polynomial time on the quantum computer, which would classically require exponential time in the worst case even on a nondeterministic computer (in particular QP g NP relative to this oracle), and (2) there is a decision problem that can be solved in exponential time on the quantum computer for which any deterministic classical computer would require double exponential time on all but finitely many instances.