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/0109104 · Physical Review A

Comparison of quantum oracles

Elham Kashefi, Adrian Kent, Vlatko Vedral, Konrad Banaszek

Published May 8, 2002• 50 citations
arXivHTMLPDF

Abstract

A standard quantum oracle ${S}_{f}$ for a general function $f: {Z}_{N}\ensuremath{\rightarrow}{Z}_{N}$ is defined to act on two input states and return two outputs, with inputs $|i〉$ and $|j〉 (i,j\ensuremath{\in}{Z}_{N})$ returning outputs $|i〉$ and $|j\ensuremath{\bigoplus}f(i)〉.$ However, if f is known to be a one-to-one function, a simpler oracle, ${M}_{f},$ which returns $|f(i)〉$ given $|i〉,$ can also be defined. We consider the relative strengths of these oracles. We define a simple promise problem that minimal quantum oracles can solve exponentially faster than classical oracles, via an algorithm that cannot be naively adapted to standard quantum oracles. We show that ${S}_{f}$ can be constructed by invoking ${M}_{f}$ and ${(M}_{f}{)}^{\ensuremath{-}1}$ once each, while $\ensuremath{\Theta}(\sqrt{N})$ invocations of ${S}_{f}$ and/or ${(S}_{f}{)}^{\ensuremath{-}1}$ are required to construct ${M}_{f}.$

DOI
10.1103/physreva.65.050304

Related papers

Comparative Computational Strength of Quantum Oracles

Alp Atıcı

It is an established fact that for many of the interesting problems quantum algorithms based on queries of the standard oracle bring no significant improvement in comparison to known classical algorithms. It is conceivable that there are other oracles of algorithmic importance acting in a less intuitive fashion to which such limitations do not apply. Thus motivated this article suggests a broader understanding towards what a general quantum oracle is. We propose a general definition of a quantum oracle and give a classification of quantum oracles based on the behavior of the eigenvalues and eigenvectors of their queries. Our aim is to determine the computational characteristics of a quantum oracle in terms of these eigenvalues and eigenvectors. Within this framework we attempt to describe the class of quantum oracles that are efficiently simulated by the standard oracle and compare the computational strength of different kinds of quantum oracles by an adversary argument using trigonometric polynomials.

arXiv:quant-ph/0312107•Dec 11, 2003•2 citations

Quantum Evaluation of Multi-Valued Boolean Functions

Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda +2 more

Our problem is to evaluate a multi-valued Boolean function $F$ through oracle calls. If $F$ is one-to-one and the size of its domain and range is the same, then our problem can be formulated as follows: Given an oracle $f(a,x): \{0,1\}^n\times\{0,1\}^n \to \{0,1\}$ and a fixed (but hidden) value $a_0$, we wish to obtain the value of $a_0$ by querying the oracle $f(a_0,x)$. Our goal is to minimize the number of such oracle calls (the query complexity) using a quantum mechanism. Two popular oracles are the EQ-oracle defined as $f(a,x)=1$ iff $x=a$ and the IP-oracle defined as $f(a,x)= a\cdot x \mod 2$. It is also well-known that the query complexity is $Θ(\sqrt{N})$ ($N=2^n$) for the EQ-oracle while only O(1) for the IP-oracle. The main purpose of this paper is to fill this gap or to investigate what causes this large difference. To do so, we introduce a parameter $K$ as the maximum number of 1's in a single column of $T_f$ where $T_f$ is the $N\times N$ truth-table of the oracle $f(a,x)$. Our main result shows that the (quantum) query complexity is heavily governed by this parameter $K$: ($i$) The query complexity is $Ω(\sqrt{N/K})$. ($ii$) This lower bound is tight in the sense that we can construct an explicit oracle whose query complexity is $O(\sqrt{N/K})$. ($iii$) The tight complexity, $Θ(\frac{N}{K}+\log{K})$, is also obtained for the classical case. Thus, the quantum algorithm needs a quadratically less number of oracle calls when $K$ is small and this merit becomes larger when $K$ is large, e.g., $\log{K}$ v.s. constant when $K = cN$.

arXiv:quant-ph/0304131•Apr 21, 2003•1 citation

Nearly optimal quantum circuits for Boolean oracles

Junhong Nie, Wei Zi

Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size $b$: with $1\le m\leΘ\left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)$, depth $\mathcal{O}\left(\frac{b2^n}{n+m}\right)$; partial Boolean functions of effective support size $d$ and output size $b$: with $Θ\left(\log d\right)\le m\le Θ\left(d\right)$ ancilla, size $\mathcal{O}\left(n\log d+bd\right)$, depth $\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)$; sparse Boolean functions of true input size $d$: with $Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)$ ancilla, size $\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)$, depth $\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)$. All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.

quant-pharXiv:2607.28402•Jul 31, 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

Quantum conditional query complexity

Imdad S. B. Sardharwalla, Sergii Strelchuk, Richard Jozsa

We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain highly efficient quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an n-input m-output boolean function is balanced or e-far from balanced; and (c) give an algorithm, requiring O˜(n/e) queries, for testing whether an n-dimensional quantum state is maximally mixed or not.

arXiv:1609.01600•Quantum Information and Computation•May 1, 2017•6 citations

A quantum oracle separation between QMA(2) and QMA

John Bostanci, Sabee Grewal, Jonas Haferkamp +4 more

We find a quantum oracle relative to which $\mathsf{QMA} \neq \mathsf{QMA}(2)$. As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every $ε+δ<1$, any $(ε,δ)$-disentangler requires input size exponential in the number of output qubits. Our proof combines the unitarily invariant polynomial method of She and Yuen (ITCS '23) with a new construction based on the symmetric and antisymmetric subspace projectors, reducing the $\mathsf{QMA}$ lower bound to the approximate degree of $\mathrm{OR}$.

quant-pharXiv:2609.02865•Sep 3, 2026•0 citations
A standard quantum oracle Sf{S}_{f}Sf​ for a general function f:ZN\ensuremath→ZNf: {Z}_{N}\ensuremath{\rightarrow}{Z}_{N}f:ZN​\ensuremath→ZN​ is defined to act on two input states and return two outputs, with inputs ∣i〉|i〉∣i〉 and ∣j〉(i,j\ensuremath∈ZN)|j〉 (i,j\ensuremath{\in}{Z}_{N})∣j〉(i,j\ensuremath∈ZN​) returning outputs ∣i〉|i〉∣i〉 and ∣j\ensuremath⨁f(i)〉.|j\ensuremath{\bigoplus}f(i)〉.∣j\ensuremath⨁f(i)〉. However, if f is known to be a one-to-one function, a simpler oracle, Mf,{M}_{f},Mf​, which returns ∣f(i)〉|f(i)〉∣f(i)〉 given ∣i〉,|i〉,∣i〉, can also be defined. We consider the relative strengths of these oracles. We define a simple promise problem that minimal quantum oracles can solve exponentially faster than classical oracles, via an algorithm that cannot be naively adapted to standard quantum oracles. We show that Sf{S}_{f}Sf​ can be constructed by invoking Mf{M}_{f}Mf​ and (Mf)\ensuremath−1{(M}_{f}{)}^{\ensuremath{-}1}(Mf​)\ensuremath−1 once each, while \ensuremathΘ(N)\ensuremath{\Theta}(\sqrt{N})\ensuremathΘ(N​) invocations of Sf{S}_{f}Sf​ and/or (Sf)\ensuremath−1{(S}_{f}{)}^{\ensuremath{-}1}(Sf​)\ensuremath−1 are required to construct Mf.{M}_{f}.Mf​.
It is an established fact that for many of the interesting problems quantum algorithms based on queries of the standard oracle bring no significant improvement in comparison to known classical algorithms. It is conceivable that there are other oracles of algorithmic importance acting in a less intuitive fashion to which such limitations do not apply. Thus motivated this article suggests a broader understanding towards what a general quantum oracle is. We propose a general definition of a quantum oracle and give a classification of quantum oracles based on the behavior of the eigenvalues and eigenvectors of their queries. Our aim is to determine the computational characteristics of a quantum oracle in terms of these eigenvalues and eigenvectors. Within this framework we attempt to describe the class of quantum oracles that are efficiently simulated by the standard oracle and compare the computational strength of different kinds of quantum oracles by an adversary argument using trigonometric polynomials.
Our problem is to evaluate a multi-valued Boolean function FFF through oracle calls. If FFF is one-to-one and the size of its domain and range is the same, then our problem can be formulated as follows: Given an oracle f(a,x):{0,1}n×{0,1}n→{0,1}f(a,x): \{0,1\}^n\times\{0,1\}^n \to \{0,1\}f(a,x):{0,1}n×{0,1}n→{0,1} and a fixed (but hidden) value a0a_0a0​, we wish to obtain the value of a0a_0a0​ by querying the oracle f(a0,x)f(a_0,x)f(a0​,x). Our goal is to minimize the number of such oracle calls (the query complexity) using a quantum mechanism. Two popular oracles are the EQ-oracle defined as f(a,x)=1f(a,x)=1f(a,x)=1 iff x=ax=ax=a and the IP-oracle defined as f(a,x)=a⋅xmod  2f(a,x)= a\cdot x \mod 2f(a,x)=a⋅xmod2. It is also well-known that the query complexity is Θ(N)Θ(\sqrt{N})Θ(N​) (N=2nN=2^nN=2n) for the EQ-oracle while only O(1) for the IP-oracle. The main purpose of this paper is to fill this gap or to investigate what causes this large difference. To do so, we introduce a parameter KKK as the maximum number of 1's in a single column of TfT_fTf​ where TfT_fTf​ is the N×NN\times NN×N truth-table of the oracle f(a,x)f(a,x)f(a,x). Our main result shows that the (quantum) query complexity is heavily governed by this parameter KKK: (iii) The query complexity is Ω(N/K)Ω(\sqrt{N/K})Ω(N/K​). (iiiiii) This lower bound is tight in the sense that we can construct an explicit oracle whose query complexity is O(N/K)O(\sqrt{N/K})O(N/K​). (iiiiiiiii) The tight complexity, Θ(NK+log⁡K)Θ(\frac{N}{K}+\log{K})Θ(KN​+logK), is also obtained for the classical case. Thus, the quantum algorithm needs a quadratically less number of oracle calls when KKK is small and this merit becomes larger when KKK is large, e.g., log⁡K\log{K}logK v.s. constant when K=cNK = cNK=cN.
Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size bbb: with 1≤m≤Θ(2nn)1\le m\leΘ\left(\frac{2^n}{n}\right)1≤m≤Θ(n2n​) ancilla, size O(b2nlog⁡(n+m))\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)O(log(n+m)b2n​), depth O(b2nn+m)\mathcal{O}\left(\frac{b2^n}{n+m}\right)O(n+mb2n​); partial Boolean functions of effective support size ddd and output size bbb: with Θ(log⁡d)≤m≤Θ(d)Θ\left(\log d\right)\le m\le Θ\left(d\right)Θ(logd)≤m≤Θ(d) ancilla, size O(nlog⁡d+bd)\mathcal{O}\left(n\log d+bd\right)O(nlogd+bd), depth O(nlog⁡nlog⁡dn+m+log⁡n+d(log⁡d+blog⁡m)m)\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)O(n+mnlognlogd​+logn+md(logd+blogm)​); sparse Boolean functions of true input size ddd: with Θ(log⁡n+log⁡d)≤m≤Θ(ndlog⁡d)Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)Θ(logn+logd)≤m≤Θ(logdnd​) ancilla, size O(n2log⁡d+ndlog⁡(log⁡d+m/n))\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)O(n2logd+log(logd+m/n)nd​), depth O(n2log⁡nlog⁡dn+m+log⁡n+ndm)\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)O(n+mn2lognlogd​+logn+mnd​). All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.
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.
We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain highly efficient quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an n-input m-output boolean function is balanced or e-far from balanced; and (c) give an algorithm, requiring O˜(n/e) queries, for testing whether an n-dimensional quantum state is maximally mixed or not.
We find a quantum oracle relative to which QMA≠QMA(2)\mathsf{QMA} \neq \mathsf{QMA}(2)QMA=QMA(2). As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every ε+δ<1ε+δ<1ε+δ<1, any (ε,δ)(ε,δ)(ε,δ)-disentangler requires input size exponential in the number of output qubits. Our proof combines the unitarily invariant polynomial method of She and Yuen (ITCS '23) with a new construction based on the symmetric and antisymmetric subspace projectors, reducing the QMA\mathsf{QMA}QMA lower bound to the approximate degree of OR\mathrm{OR}OR.