arXiv:1701.02143

A Quantum Algorithm for Testing Juntas in Boolean Functions

Khaled El-Wazan, Ahmed Younes, Salah Badawi Doma

Published Jan 9, 2017• 6 citations

Abstract

Given a Boolean function $f$ provided as a black-box with $n$ variables, this paper will propose a quantum algorithm for testing if a certain variable is junta or $ε$-far from being junta. The proposed algorithm constructs another black-box using two copies of the provided black-box. The constructed black-box is used with the partial diffusion operator in an amplitude amplification technique to test whether the variable being tested is junta or not, using $\mathcal{O}(\sqrt{2^n})$ queries to the constructed black-box. The proposed algorithm considers a Boolean function of general form, contrary to relevant algorithms proposed by others.

DOI: 10.48550/arxiv.1701.02143

Related papers

A Quantum Algorithm for Testing Junta Variables and Learning Boolean Functions via Entanglement Measure

Khaled El-Wazan, Ahmed Younes, Salah Badawi Doma

arXiv:1710.10495Oct 28, 20172 citations

Tolerant Quantum Junta Testing

Zhaoyang Chen, Lvzhou Li, Jingquan Luo

arXiv:2411.02244Nov 4, 20241 citation

Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing

Zongbo Bao, Yuxuan Liu, Penghui Yao +2 more

We consider the problem of deciding whether an $n$-qubit unitary (or $n$-bit Boolean function) is $\varepsilon_1$-close to some $k$-junta or $\varepsilon_2$-far from every $k$-junta, where $k$-junta unitaries act non-trivially on at most $k$ qubits and as the identity on the rest, and $k$-junta Boolean functions depend on at most $k$ variables. For constant numbers $\varepsilon_1, \varepsilon_2$ such that $0 \lt \varepsilon_1 \lt \varepsilon_2 \lt 1$, we show the following.1.A non-adaptive $O(k \log k)$-query tolerant ($\varepsilon_1, \varepsilon_2$)-tester for $k$-junta unitaries when $2\sqrt2\varepsilon_1 \lt \varepsilon_2$.2.A non-adaptive tolerant ($\varepsilon_1, \varepsilon_2$)-tester for $k$-junta Boolean functions with $O(k \log k)$ quantum queries when $4\varepsilon_1 \lt \varepsilon_2$.3.A $2^{\widetilde{O}(k)}$-query tolerant ($\varepsilon_1, \varepsilon_2$)-tester for $k$-junta unitaries for any $\varepsilon_1, \varepsilon_2$.The first algorithm provides an exponential improvement over the best-known quantum algorithms [CLL24, ADG25]. The second algorithm shows an exponential quantum advantage over any non-adaptive classical algorithm [CDL+24]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap.

Society for Industrial and Applied Mathematics eBooksJan 1, 20260 citations

Quantum Advantage in Tolerant Junta Testing

Avishay Tal, Weiqiang Yuan

cs.CCCross-listedarXiv:2606.23194Jun 23, 20260 citations

Testing Boolean Functions Properties

Zhengwei Xie, Daowen Qiu, Guangya Cai +2 more

arXiv:2109.06763Fundamenta InformaticaeNov 18, 20210 citations

Testing Boolean Functions Properties

Zhengwei Xie, Daowen Qiu, Guangya Cai +2 more

Fundamenta InformaticaeNov 18, 20210 citations

arXiv:1701.02143

A Quantum Algorithm for Testing Juntas in Boolean Functions

Khaled El-Wazan, Ahmed Younes, Salah Badawi Doma

Published Jan 9, 2017• 6 citations

arXiv HTML PDF

Abstract

Given a Boolean function

f

provided as a black-box with

n

variables, this paper will propose a quantum algorithm for testing if a certain variable is junta or

ε

-far from being junta. The proposed algorithm constructs another black-box using two copies of the provided black-box. The constructed black-box is used with the partial diffusion operator in an amplitude amplification technique to test whether the variable being tested is junta or not, using

\mathcal{O}(\sqrt{2^n})

queries to the constructed black-box. The proposed algorithm considers a Boolean function of general form, contrary to relevant algorithms proposed by others.

DOI: 10.48550/arxiv.1701.02143

Related papers

A Quantum Algorithm for Testing Junta Variables and Learning Boolean Functions via Entanglement Measure

Khaled El-Wazan, Ahmed Younes, Salah Badawi Doma

Given a black-box representing an unknown Boolean function $f$ of $n$ variables, in this paper we propose a fast quantum algorithm to test whether or not a certain variable in the function $f$ is a junta variable. The proposed algorithm creates entanglement between the variable under test and an auxiliary qubit, where the entanglement is measured using concurrence measure to decide if the variable is junta. The paper shows applications to the proposed algorithm in learning and categorization of Boolean functions.Given a black-box representing an unknown Boolean function $f$ of $n$ variables, in this paper we propose a fast quantum algorithm to test whether or not a certain variable in the function $f$ is a junta variable. The proposed algorithm creates entanglement between the variable under test and an auxiliary qubit, where the entanglement is measured using concurrence measure to decide if the variable is junta. The paper shows applications to the proposed algorithm in learning and categorization of Boolean functions.

arXiv:1710.10495Oct 28, 20172 citations

Tolerant Quantum Junta Testing

Zhaoyang Chen, Lvzhou Li, Jingquan Luo

Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is $ε_1$ -close to some quantum $k$ -junta or is $ε_2$ -far from any quantum $k$ -junta, where an $n$ -qubit unitary $U$ is called a quantum $k$ -junta if it only non-trivially acts on just $k$ of the $n$ qubits. More specifically, we present a tolerant tester with $ε_1 = \frac{\sqrtρ}{8} ε$ , $ε_2 = ε$ , and $ρ\in (0,1)$ , and the query complexity is $O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)$ , which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to $U^\dagger$ , whereas this is usually required in the literature.Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is $ε_1$-close to some quantum $k$-junta or is $ε_2$-far from any quantum $k$-junta, where an $n$-qubit unitary $U$ is called a quantum $k$-junta if it only non-trivially acts on just $k$ of the $n$ qubits. More specifically, we present a tolerant tester with $ε_1 = \frac{\sqrtρ}{8} ε$, $ε_2 = ε$, and $ρ\in (0,1)$, and the query complexity is $O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)$, which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to $U^\dagger$, whereas this is usually required in the literature.

arXiv:2411.02244Nov 4, 20241 citation

Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing

Zongbo Bao, Yuxuan Liu, Penghui Yao +2 more

We consider the problem of deciding whether an $n$ -qubit unitary (or $n$ -bit Boolean function) is $\varepsilon_1$ -close to some $k$ -junta or $\varepsilon_2$ -far from every $k$ -junta, where $k$ -junta unitaries act non-trivially on at most $k$ qubits and as the identity on the rest, and $k$ -junta Boolean functions depend on at most $k$ variables. For constant numbers $\varepsilon_1, \varepsilon_2$ such that $0 \lt \varepsilon_1 \lt \varepsilon_2 \lt 1$ , we show the following.1.A non-adaptive $O(k \log k)$ -query tolerant ( $\varepsilon_1, \varepsilon_2$ )-tester for $k$ -junta unitaries when $2\sqrt2\varepsilon_1 \lt \varepsilon_2$ .2.A non-adaptive tolerant ( $\varepsilon_1, \varepsilon_2$ )-tester for $k$ -junta Boolean functions with $O(k \log k)$ quantum queries when $4\varepsilon_1 \lt \varepsilon_2$ .3.A $2^{\widetilde{O}(k)}$ -query tolerant ( $\varepsilon_1, \varepsilon_2$ )-tester for $k$ -junta unitaries for any $\varepsilon_1, \varepsilon_2$ .The first algorithm provides an exponential improvement over the best-known quantum algorithms [CLL24, ADG25]. The second algorithm shows an exponential quantum advantage over any non-adaptive classical algorithm [CDL+24]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap.We consider the problem of deciding whether an $n$-qubit unitary (or $n$-bit Boolean function) is $\varepsilon_1$-close to some $k$-junta or $\varepsilon_2$-far from every $k$-junta, where $k$-junta unitaries act non-trivially on at most $k$ qubits and as the identity on the rest, and $k$-junta Boolean functions depend on at most $k$ variables. For constant numbers $\varepsilon_1, \varepsilon_2$ such that $0 \lt \varepsilon_1 \lt \varepsilon_2 \lt 1$, we show the following.1.A non-adaptive $O(k \log k)$-query tolerant ($\varepsilon_1, \varepsilon_2$)-tester for $k$-junta unitaries when $2\sqrt2\varepsilon_1 \lt \varepsilon_2$.2.A non-adaptive tolerant ($\varepsilon_1, \varepsilon_2$)-tester for $k$-junta Boolean functions with $O(k \log k)$ quantum queries when $4\varepsilon_1 \lt \varepsilon_2$.3.A $2^{\widetilde{O}(k)}$-query tolerant ($\varepsilon_1, \varepsilon_2$)-tester for $k$-junta unitaries for any $\varepsilon_1, \varepsilon_2$.The first algorithm provides an exponential improvement over the best-known quantum algorithms [CLL24, ADG25]. The second algorithm shows an exponential quantum advantage over any non-adaptive classical algorithm [CDL+24]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap.

Society for Industrial and Applied Mathematics eBooksJan 1, 20260 citations

Quantum Advantage in Tolerant Junta Testing

Avishay Tal, Weiqiang Yuan

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$ -junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$ -junta testing is as follows: given parameters $(k, ε_1, ε_2)$ , with $0\le ε_1<ε_2 \le 1/2$ , and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$ -close to some $k$ -junta or $ε_2$ -far from every $k$ -junta. We show the quantum advantage for a range of parameters close to $1/2$ , for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$ . The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$ -juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$ -juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, ε_1, ε_2)$, with $0\le ε_1<ε_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$-close to some $k$-junta or $ε_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.

cs.CCCross-listedarXiv:2606.23194Jun 23, 20260 citations

Testing Boolean Functions Properties

Zhengwei Xie, Daowen Qiu, Guangya Cai +2 more

The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is $\varepsilon$ -far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function $f$ , of $n$ variables, is identical with a given function $g$ or is $\varepsilon$ -far from $g$ , where $\varepsilon$ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity $O(\frac{1}{\sqrt{\varepsilon}})$ . Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is $\Theta(\frac{1}{\varepsilon})$ . Secondly, we consider the D-J problem from the perspective of functional correlations and let $C(f,g)$ denote the correlation of $f$ and $g$ . We propose an exact quantum algorithm for making distinction between $|C(f,g)|=\varepsilon$ and $|C(f,g)|=1$ using six queries, while the classical deterministic query complexity for this problem is $\Theta(2^{n})$ queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus $\varepsilon$ -far balanced using $O(\frac{1}{\varepsilon})$ queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of $O(1/\varepsilon^{2})$ . Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta InformaticaeThe goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is $\varepsilon$-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function $f$, of $n$ variables, is identical with a given function $g$ or is $\varepsilon$-far from $g$, where $\varepsilon$ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity $O(\frac{1}{\sqrt{\varepsilon}})$. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is $\Theta(\frac{1}{\varepsilon})$. Secondly, we consider the D-J problem from the perspective of functional correlations and let $C(f,g)$ denote the correlation of $f$ and $g$. We propose an exact quantum algorithm for making distinction between $|C(f,g)|=\varepsilon$ and $|C(f,g)|=1$ using six queries, while the classical deterministic query complexity for this problem is $\Theta(2^{n})$ queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus $\varepsilon$-far balanced using $O(\frac{1}{\varepsilon})$ queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of $O(1/\varepsilon^{2})$. Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae

arXiv:2109.06763Fundamenta InformaticaeNov 18, 20210 citations

Testing Boolean Functions Properties

Zhengwei Xie, Daowen Qiu, Guangya Cai +2 more

Fundamenta InformaticaeNov 18, 20210 citations

Given a Boolean function

f

provided as a black-box with

n

variables, this paper will propose a quantum algorithm for testing if a certain variable is junta or

ε

\mathcal{O}(\sqrt{2^n})

queries to the constructed black-box. The proposed algorithm considers a Boolean function of general form, contrary to relevant algorithms proposed by others.

Given a black-box representing an unknown Boolean function

f

n

variables, in this paper we propose a fast quantum algorithm to test whether or not a certain variable in the function

f

is a junta variable. The proposed algorithm creates entanglement between the variable under test and an auxiliary qubit, where the entanglement is measured using concurrence measure to decide if the variable is junta. The paper shows applications to the proposed algorithm in learning and categorization of Boolean functions.

ε_1

-close to some quantum

k

-junta or is

ε_2

-far from any quantum

k

-junta, where an

n

-qubit unitary

U

is called a quantum

k

-junta if it only non-trivially acts on just

k

of the

n

qubits. More specifically, we present a tolerant tester with

ε_1 = \frac{\sqrtρ}{8} ε

ε_2 = ε

, and

ρ\in (0,1)

, and the query complexity is

O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)

, which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to

U^\dagger

, whereas this is usually required in the literature.

We consider the problem of deciding whether an

n

-qubit unitary (or

n

-bit Boolean function) is

\varepsilon_1

-close to some

k

-junta or

\varepsilon_2

-far from every

k

-junta, where

k

-junta unitaries act non-trivially on at most

k

qubits and as the identity on the rest, and

k

-junta Boolean functions depend on at most

k

variables. For constant numbers

\varepsilon_1, \varepsilon_2

such that

0 \lt \varepsilon_1 \lt \varepsilon_2 \lt 1

, we show the following.1.A non-adaptive

O(k \log k)

-query tolerant (

\varepsilon_1, \varepsilon_2

)-tester for

k

-junta unitaries when

2\sqrt2\varepsilon_1 \lt \varepsilon_2

.2.A non-adaptive tolerant (

\varepsilon_1, \varepsilon_2

)-tester for

k

-junta Boolean functions with

O(k \log k)

quantum queries when

4\varepsilon_1 \lt \varepsilon_2

.3.A

2^{\widetilde{O}(k)}

-query tolerant (

\varepsilon_1, \varepsilon_2

)-tester for

k

-junta unitaries for any

\varepsilon_1, \varepsilon_2

.The first algorithm provides an exponential improvement over the best-known quantum algorithms [CLL24, ADG25]. The second algorithm shows an exponential quantum advantage over any non-adaptive classical algorithm [CDL+24]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap.

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant

k

-junta testing with high precision can be solved using

\mathrm{poly}(k)

quantum queries, whereas any classical algorithm requires at least

k^{Ω(\log k)}

queries. The problem of tolerant

k

-junta testing is as follows: given parameters

(k, ε_1, ε_2)

, with

0\le ε_1<ε_2 \le 1/2

, and black-box access to a Boolean function

f

(defined on

n

variables), distinguish whether

f

ε_1

-close to some

k

-junta or

ε_2

-far from every

k

-junta. We show the quantum advantage for a range of parameters close to

1/2

, for example,

ε_1 = 1/2-1/k

and

ε_2 = 1/2-1/(2k^2)

. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most

ε_1

k

-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick

k

out of

n

coordinates, and for each fixing of the

k

coordinates, the

2^{n-k}

values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to

k

-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making

k^{o(\log k)}

queries.

The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is

\varepsilon

-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function

f

, of

n

variables, is identical with a given function

g

or is

\varepsilon

-far from

g

, where

\varepsilon

is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity

O(\frac{1}{\sqrt{\varepsilon}})

. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is

\Theta(\frac{1}{\varepsilon})

. Secondly, we consider the D-J problem from the perspective of functional correlations and let

C(f,g)

denote the correlation of

f

and

g

. We propose an exact quantum algorithm for making distinction between

|C(f,g)|=\varepsilon

and

|C(f,g)|=1

using six queries, while the classical deterministic query complexity for this problem is

\Theta(2^{n})

queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus

\varepsilon

-far balanced using

O(\frac{1}{\varepsilon})

queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of

O(1/\varepsilon^{2})

. Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae

The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is

\varepsilon

f

, of

n

variables, is identical with a given function

g

or is

\varepsilon

-far from

g

, where

\varepsilon

is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity

O(\frac{1}{\sqrt{\varepsilon}})

. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is

\Theta(\frac{1}{\varepsilon})

. Secondly, we consider the D-J problem from the perspective of functional correlations and let

C(f,g)

denote the correlation of

f

and

g

. We propose an exact quantum algorithm for making distinction between

|C(f,g)|=\varepsilon

and

|C(f,g)|=1

using six queries, while the classical deterministic query complexity for this problem is

\Theta(2^{n})

queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus

\varepsilon

-far balanced using

O(\frac{1}{\varepsilon})

O(1/\varepsilon^{2})