The quantum query complexity of combinatorial group testing

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

The Quantum Complexity of Group Testing

Sebastian Dörn, Thomas Thierauf

Springer eBooksJan 5, 20088 citations

Combinatorial Optimization and Quantum Computers

Alexandre Gondran, Michel Gondran

Feb 7, 20200 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

Quantum Query Complexity of Some Graph Problems

Christoph Dürr, Mark Heiligman, Peter Høyer +1 more

Lecture notes in computer scienceJan 1, 200472 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 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

ε