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

Quantum Oracle Interrogation: Getting All Information for Almost Half the Price

Wim Van Dam

Published May 5, 1998• 65 citations
OpenAlex

Abstract

A quantum computer in combination with a binary oracle of domain size N is considered. It is shown how N/2+sqrt(N) calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 85%. This contrasts the power of classical computers which would require N calls to achieve the same result. From this result it follows that any binary function with the N bits of the oracle as input, can be calculated with a small 2 sided error using N/2+sqrt(N) queries.

Related papers

Quantum oracle interrogation: getting all information for almost half the price

W. van Dam

Consider a quantum computer in combination with a binary oracle of domain size N. It is shown how N/2+/spl radic/N calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 95%. This contrasts the power of classical computers which would require N calls to achieve the same task. From this result it follows that any function with the N bits of the oracle as input can be calculated using N/2+/spl radic/N queries if we allow a small probability of error. It is also shown that this error probability can be made arbitrary small by using N/2+O(/spl radic/N) oracle queries. In the second part of the article 'approximate interrogation' is considered. This is when only a certain fraction of the N oracle bits are requested. Also for this scenario does the quantum algorithm outperform the classical protocols. An example is given where a quantum procedure with N/10 queries returns a string of which 80% of the bits are correct. Any classical protocol would need 6N/10 queries to establish such a correctness ratio.

arXiv:quant-ph/9805006•Annual Symposium on Foundations of Computer Science•Nov 27, 2002•62 citations

Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions

Yuan Deng, Zihan Hao, Honghao Lin +4 more

The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+Ω(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.

arXiv:2611.09809•Nov 6, 2026•0 citations

Robust Quantum Algorithms Computing OR with -Biased Oracles

T. SUZUKI, Shigeru Yamashita, Masaki Nakanishi +1 more

This paper considers the quantum query complexity of e-biased oracles that return the correct value with probability only 1/2 + e. In particular, we show a quantum algorithm to compute N-bit OR functions with O(√N/e) queries to e-biased oracles. This improves the known upper bound of O(√N/e2) and matches the known lower bound; we answer the conjecture raised by the paper yamashita affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of e. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of e.

IEICE Transactions on Information and Systems•Feb 1, 2007•0 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•2 citations

Robust Quantum Algorithms with $\eps$-Biased Oracles

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1 more

This paper considers the quantum query complexity of {\it $\eps$-biased oracles} that return the correct value with probability only $1/2 + \eps$. In particular, we show a quantum algorithm to compute $N$-bit OR functions with $O(\sqrt{N}/{\eps})$ queries to $\eps$-biased oracles. This improves the known upper bound of $O(\sqrt{N}/{\eps}^2)$ and matches the known lower bound; we answer the conjecture raised by the paper by Iwama et al. affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of $\eps$. This contrasts with the corresponding classical situation, where it is almost hopeless to achieve more than a constant success probability without knowing the value of $\eps$.

arXiv:quant-ph/0605077•May 8, 2006•3 citations

Optimal compression with quantum retrieval

Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar +1 more

We consider the following data compression problem. Given a string $x \in \{0,1\}^m$ of Hamming weight at most $n$, compress it into a shorter string $y \in \{0,1\}^s$ so that any bit $x_i$ of $x$ can be retrieved without any error using at most $t$ quantum queries to the standard oracle encoding of $y$. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on $m$ except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on $n$.

quant-pharXiv:2610.06702•Oct 6, 2026•0 citations
A quantum computer in combination with a binary oracle of domain size N is considered. It is shown how N/2+sqrt(N) calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 85%. This contrasts the power of classical computers which would require N calls to achieve the same result. From this result it follows that any binary function with the N bits of the oracle as input, can be calculated with a small 2 sided error using N/2+sqrt(N) queries.
Consider a quantum computer in combination with a binary oracle of domain size N. It is shown how N/2+/spl radic/N calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 95%. This contrasts the power of classical computers which would require N calls to achieve the same task. From this result it follows that any function with the N bits of the oracle as input can be calculated using N/2+/spl radic/N queries if we allow a small probability of error. It is also shown that this error probability can be made arbitrary small by using N/2+O(/spl radic/N) oracle queries. In the second part of the article 'approximate interrogation' is considered. This is when only a certain fraction of the N oracle bits are requested. Also for this scenario does the quantum algorithm outperform the classical protocols. An example is given where a quantum procedure with N/10 queries returns a string of which 80% of the bits are correct. Any classical protocol would need 6N/10 queries to establish such a correctness ratio.
Beyond the n/2n/2n/2 Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
The oracle-interrogation algorithm [van Dam, FOCS '98] computes every nnn-bit Boolean function with bounded error using n/2+O(n)n/2+O(\sqrt n)n/2+O(n​) quantum queries. In contrast, parity can be computed exactly using ⌈n/2⌉\lceil n/2\rceil⌈n/2⌉ queries, but whether an additive overhead beyond n/2n/2n/2 is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring n/2+Ω(n1/3)n/2+Ω(n^{1/3})n/2+Ω(n1/3) quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using n/2+O(n1/3)n/2+O(n^{1/3})n/2+O(n1/3) quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.
This paper considers the quantum query complexity of e-biased oracles that return the correct value with probability only 1/2 + e. In particular, we show a quantum algorithm to compute N-bit OR functions with O(√N/e) queries to e-biased oracles. This improves the known upper bound of O(√N/e2) and matches the known lower bound; we answer the conjecture raised by the paper yamashita affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of e. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of e.
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.
This paper considers the quantum query complexity of {\it $\eps$-biased oracles} that return the correct value with probability only $1/2 + \eps$. In particular, we show a quantum algorithm to compute NNN-bit OR functions with $O(\sqrt{N}/{\eps})$ queries to $\eps$-biased oracles. This improves the known upper bound of $O(\sqrt{N}/{\eps}^2)$ and matches the known lower bound; we answer the conjecture raised by the paper by Iwama et al. affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of $\eps$. This contrasts with the corresponding classical situation, where it is almost hopeless to achieve more than a constant success probability without knowing the value of $\eps$.
We consider the following data compression problem. Given a string x∈{0,1}mx \in \{0,1\}^mx∈{0,1}m of Hamming weight at most nnn, compress it into a shorter string y∈{0,1}sy \in \{0,1\}^sy∈{0,1}s so that any bit xix_ixi​ of xxx can be retrieved without any error using at most ttt quantum queries to the standard oracle encoding of yyy. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on mmm except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on nnn.