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

DOI10.1137/1.9781611974331.CH65zbMATH Open1410.68132arXiv1507.03126OpenAlexW2949645943MaRDI QIDQ4575644FDOQ4575644

Authors: Aleksandrs Belovs, Andris Ambainis, Oded Regev, Ronald de Wolf 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: In the $k$-junta testing problem, a tester has to efficiently decide whether a given function $f:{0,1}^{n}ightarrow0,1$ is a $k$-junta (i.e., depends on at most $k$ of its input bits) or is $epsilon$-far from any $k$-junta. Our main result is a quantum algorithm for this problem with query complexity $ildeO(sqrtk/epsilon)$ and time complexity $ildeO(nsqrtk/epsilon)$. This quadratically improves over the query complexity of the previous best quantum junta tester, due to Ati ci 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 $Omega(k^{1/3})$ queries for junta-testing (for constant $epsilon$).

Full work available at URL: https://arxiv.org/abs/1507.03126

Recommendations

• Quantum algorithm for distribution-free junta testing
• Quantum algorithms for learning and testing juntas
• An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product
• Quantum algorithms for learning symmetric juntas via the adversary bound
• The Quantum Complexity of Group Testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum algorithms and complexity in the theory of computing (68Q12)

Cited In (11)

• Quantum cryptographic property testing of multi-output Boolean functions
• An exact quantum logarithmic time algorithm for the 3-junta problem
• Harmonicity and invariance on slices of the Boolean cube
• Quantum algorithm for distribution-free junta testing
• An exact quantum algorithm for the 2-junta problem
• An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product
• An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables
• An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product
• A fast Fourier transform for the Johnson graph
• A exact quantum learning algorithm for the 2-junta problem in constant time
• Quantum Algorithms for Classical Probability Distributions

This page was built for publication: Efficient quantum algorithms for (gapped) group testing and junta testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575644)