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

DOI10.1137/1.9781611974331.CH65MaRDI QIDQ4575644zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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$).

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

Cited in

(11)

• Quantum Algorithms for Classical Probability Distributions
• Quantum cryptographic property testing of multi-output Boolean functions
• Harmonicity and invariance on slices of the Boolean cube
• An exact quantum logarithmic time algorithm for the 3-junta problem
• 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

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)