Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing

Zongbo Bao, Yuxuan Liu, Penghui Yao +2

We consider the problem of deciding whether an $n$-qubit unitary (or $n$-bit Boolean function) is ${\epsilon }_1$-close to some $k$-junta or ${\epsilon }_2$-far from every $k$-junt…