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/0304073 · International Journal of Quantum Information

On Deciding Whether a Boolean Function is Constant or Not

Fabio Benatti, Luca Marinatto

Published Jun 1, 2003• 0 citations
arXivHTMLPDF

Abstract

We study the probability of making an error if, by querying an oracle a fixed number of times, we declare constant a randomly chosen n-bit Boolean function. We compare the classical and the quantum case, and we determine for how many oracle-queries k and for how many bits n one querying procedure is more efficient than the other.
DOI
10.1142/s0219749903000115

Related papers

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

Optimal quantum query bounds for almost all Boolean functions

Andris Ambainis, Artūrs Bačkurs, Juris Smotrovs +1 more

We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis, and shows that van Dam's oracle interrogation is essentially optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials.

arXiv:1208.1122•Aug 6, 2012•8 citations

Optimal quantum query bounds for almost all Boolean functions

Andris Ambainis, Artūrs Bačkurs, Juris Smotrovs +1 more

We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis (A. Ambainis, 1999), and shows that van Dam's oracle interrogation (W. van Dam, 1998) is essentially optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials.

Leibniz international proceedings in informatics•Jan 1, 2013•9 citations

On Randomized and Quantum Query Complexities

Gatis Midrijānis

We study randomized and quantum query (a.k.a. decision tree) complexity for all total Boolean functions, with emphasis to derandomization and dequantization (removing quantumness from algorithms). Firstly, we show that $D(f) = O(Q_1(f)^3)$ for any total function $f$, where $D(f)$ is the minimal number of queries made by a deterministic query algorithm and $Q_1(f)$ is the number of queries made by any quantum query algorithm (decision tree analog in quantum case) with one-sided constant error; both algorithms compute function $f$. Secondly, we show that for all total Boolean functions $f$ holds $R_0(f)=O(R_2(f)^2 \log N)$, where $R_0(f)$ and $R_2(f)$ are randomized zero-sided (a.k.a Las Vegas) and two-sided (a.k.a. Monte Carlo) error query complexities.

arXiv:quant-ph/0501142•Jan 25, 2005•14 citations

Partial Boolean Functions With Exact Quantum Query Complexity One

Guoliang Xu, Daowen Qiu

We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then F(f) is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.

arXiv:2007.10924•Entropy•Feb 3, 2021•9 citations

Easy and Hard Functions for the Boolean Hidden Shift Problem

Andrew M. Childs, Robin Kothari, Māris Ozols +1 more

We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem.

arXiv:1304.4642•Leibniz international proceedings in informatics•Jan 1, 2013•11 citations
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.
We study randomized and quantum query (a.k.a. decision tree) complexity for all total Boolean functions, with emphasis to derandomization and dequantization (removing quantumness from algorithms). Firstly, we show that D(f)=O(Q1(f)3)D(f) = O(Q_1(f)^3)D(f)=O(Q1​(f)3) for any total function fff, where D(f)D(f)D(f) is the minimal number of queries made by a deterministic query algorithm and Q1(f)Q_1(f)Q1​(f) is the number of queries made by any quantum query algorithm (decision tree analog in quantum case) with one-sided constant error; both algorithms compute function fff. Secondly, we show that for all total Boolean functions fff holds R0(f)=O(R2(f)2log⁡N)R_0(f)=O(R_2(f)^2 \log N)R0​(f)=O(R2​(f)2logN), where R0(f)R_0(f)R0​(f) and R2(f)R_2(f)R2​(f) are randomized zero-sided (a.k.a Las Vegas) and two-sided (a.k.a. Monte Carlo) error query complexities.
We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then F(f) is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.
We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem.