Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
| Autor: | Ambainis, A., Belovs, A., Regev, O., de Wolf, R., Krauthgamer, R. |
|---|---|
| Přispěvatelé: | ILLC (FNWI), Quantum Matter and Quantum Information, Logic and Computation (ILLC, FNWI/FGw) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Computational Complexity Quantum Physics 0103 physical sciences FOS: Physical sciences 010307 mathematical physics Computational Complexity (cs.CC) Computer Science::Computational Complexity Quantum Physics (quant-ph) 010306 general physics 01 natural sciences |
| Zdroj: | Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms: SODA 2016 : January 10-12, 2016, Crystal Gateway Marriott, Arlington, Virginia, USA, 903-922 STARTPAGE=903;ENDPAGE=922;TITLE=Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms |
| Popis: | 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 fc of its input bits) or is ε-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity Õ([EQUATION]) and time complexity Õ(n[EQUATION]). 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 ε). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|