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

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1

In the $k$-junta testing problem, a tester has to efficiently decide whether a given function $f:\{0,1{\}}^n\to \{0,1\}$ is a $k$-junta (i.e., depends on at most $k$ of its i…