arXiv:1311.6777

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound

Aleksandrs Belovs

Published Nov 26, 2013• 3 citations

Abstract

In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function $f$ on $n$ variables that only depends on $k$ variables, and, when restricted to them, equals some predefined function $h$. The task is to identify the variables the function depends on. When $h$ is the XOR or the OR function, this gives a restricted variant of the Bernstein-Vazirani or the combinatorial group testing problem, respectively. We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when $h$ is the OR function (complexity is $Θ(\sqrt{k})$) or the exact-half function (complexity is $Θ(k^{1/4})$). The first algorithm resolves an open problem from arXiv:1210.1148. For the case when $h$ is the majority function, we prove an upper bound of $O(k^{1/4})$. All these algorithms can be made exact. We obtain a quartic improvement when compared to the randomised complexity (if $h$ is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).

DOI: 10.48550/arxiv.1311.6777

Related papers

Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound

Aleksandrs Belovs

IEEE Conference on Computational Complexity (CCC)Jun 1, 20146 citations

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1 more

arXiv:1507.03126Jul 11, 20150 citations

Efficient quantum algorithms for (Gapped) group testing and junta testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1 more

Jan 1, 201618 citations

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

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1 more

ACM-SIAM Symposium on Discrete Algorithms (SODA)Dec 21, 201527 citations

arXiv:1311.6777

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound

Aleksandrs Belovs

Published Nov 26, 2013• 3 citations

arXiv HTML PDF

Abstract

In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function

f

n

variables that only depends on

k

variables, and, when restricted to them, equals some predefined function

h

. The task is to identify the variables the function depends on. When

h

is the XOR or the OR function, this gives a restricted variant of the Bernstein-Vazirani or the combinatorial group testing problem, respectively. We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when

h

is the OR function (complexity is

Θ(\sqrt{k})

) or the exact-half function (complexity is

Θ(k^{1/4})

). The first algorithm resolves an open problem from arXiv:1210.1148. For the case when

h

is the majority function, we prove an upper bound of

O(k^{1/4})

. All these algorithms can be made exact. We obtain a quartic improvement when compared to the randomised complexity (if

h

is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).

DOI: 10.48550/arxiv.1311.6777

Related papers

Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound

Aleksandrs Belovs

In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. This is a generalisation of the Bernstein-Vazirani problem [1] (when h is the XOR function) and the combinatorial group testing problem [2] (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is square root of k) or the exact-half function (complexity is the fourth power root of k). The first algorithm resolves an open problem from. For the case when h is the majority function, we prove an upper bound of the fourth power root of k. We obtain a quartic improvement when compared to the randomised complexity (if h is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. This is a generalisation of the Bernstein-Vazirani problem [1] (when h is the XOR function) and the combinatorial group testing problem [2] (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is square root of k) or the exact-half function (complexity is the fourth power root of k). The first algorithm resolves an open problem from. For the case when h is the majority function, we prove an upper bound of the fourth power root of k. We obtain a quartic improvement when compared to the randomised complexity (if h is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).

IEEE Conference on Computational Complexity (CCC)Jun 1, 20146 citations

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1 more

In the $k$ -junta testing problem, a tester has to efficiently decide whether a given function $f:\{0,1\}^n\rightarrow \{0,1\}$ is a $k$ -junta (i.e., depends on at most $k$ of its input bits) or is $ε$ -far from any $k$ -junta. Our main result is a quantum algorithm for this problem with query complexity $\tilde O(\sqrt{k/ε})$ and time complexity $\tilde O(n\sqrt{k/ε})$ . This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of $Ω(k^{1/3})$ queries for junta-testing (for constant $ε$ ).In the $k$-junta testing problem, a tester has to efficiently decide whether a given function $f:\{0,1\}^n\rightarrow \{0,1\}$ is a $k$-junta (i.e., depends on at most $k$ of its input bits) or is $ε$-far from any $k$-junta. Our main result is a quantum algorithm for this problem with query complexity $\tilde O(\sqrt{k/ε})$ and time complexity $\tilde O(n\sqrt{k/ε})$. This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of $Ω(k^{1/3})$ queries for junta-testing (for constant $ε$).

arXiv:1507.03126Jul 11, 20150 citations

Efficient quantum algorithms for (Gapped) group testing and junta testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1 more

In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0,1}n → {0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ∈-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity Ō(√∈) and time complexity Ō(n√∈). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of ω(k1/3) queries for junta-testing (for constant ∈).In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0,1}n → {0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ∈-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity Ō(√∈) and time complexity Ō(n√∈). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of ω(k1/3) queries for junta-testing (for constant ∈).

Jan 1, 201618 citations

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

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1 more

In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0, 1}n → {0, 1} is a k-junta (i.e., depends on at most k of its input bits) or is ∊-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity and time complexity . This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ∊).In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0, 1}n → {0, 1} is a k-junta (i.e., depends on at most k of its input bits) or is ∊-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity and time complexity . This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ∊).

ACM-SIAM Symposium on Discrete Algorithms (SODA)Dec 21, 201527 citations

In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function

f

n

variables that only depends on

k

variables, and, when restricted to them, equals some predefined function

h

. The task is to identify the variables the function depends on. When

h

h

is the OR function (complexity is

Θ(\sqrt{k})

) or the exact-half function (complexity is

Θ(k^{1/4})

). The first algorithm resolves an open problem from arXiv:1210.1148. For the case when

h

is the majority function, we prove an upper bound of

O(k^{1/4})

. All these algorithms can be made exact. We obtain a quartic improvement when compared to the randomised complexity (if

h

is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).

In the

k

-junta testing problem, a tester has to efficiently decide whether a given function

f:\{0,1\}^n\rightarrow \{0,1\}

is a

k

-junta (i.e., depends on at most

k

of its input bits) or is

ε

-far from any

k

-junta. Our main result is a quantum algorithm for this problem with query complexity

\tilde O(\sqrt{k/ε})

and time complexity

\tilde O(n\sqrt{k/ε})

. This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of

Ω(k^{1/3})

queries for junta-testing (for constant

ε

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.