Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Basel
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106915 |
| _version_ | 1826204435937755136 |
|---|---|
| author | Belovs, Aleksandrs |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Belovs, Aleksandrs |
| author_sort | Belovs, Aleksandrs |
| collection | MIT |
| description | In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on.When h is the XOR or the OR function, this gives a restricted variant of the Bernstein–Vazirani or the combinatorial group testing problem, respectively.
We analyze the general case using the adversary bound and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is Θ(√k) ) or the exact-half function (complexity is O(k[supercript 1/4])). The first algorithm resolves an open problem from Ambainis & Montanaro (Quantum Inf Comput 14(5&6): 439–453, 2014). For the case when h is the majority function, we prove an upper bound of O(k[supercript 1/4]). All these algorithms can be made exact. We obtain a quartic improvement when compared to the randomized complexity (if h is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper). |
| first_indexed | 2024-09-23T12:55:01Z |
| format | Article |
| id | mit-1721.1/106915 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:55:01Z |
| publishDate | 2017 |
| publisher | Springer Basel |
| record_format | dspace |
| spelling | mit-1721.1/1069152022-10-01T11:55:03Z Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound Belovs, Aleksandrs Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Belovs, Aleksandrs In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on.When h is the XOR or the OR function, this gives a restricted variant of the Bernstein–Vazirani or the combinatorial group testing problem, respectively. We analyze the general case using the adversary bound and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (complexity is Θ(√k) ) or the exact-half function (complexity is O(k[supercript 1/4])). The first algorithm resolves an open problem from Ambainis & Montanaro (Quantum Inf Comput 14(5&6): 439–453, 2014). For the case when h is the majority function, we prove an upper bound of O(k[supercript 1/4]). All these algorithms can be made exact. We obtain a quartic improvement when compared to the randomized complexity (if h is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper). National Science Foundation (U.S.) (Scott Aaronson’s Alan T. Waterman Award) 2017-02-10T21:17:43Z 2017-02-10T21:17:43Z 2015-04 2016-08-18T15:40:17Z Article http://purl.org/eprint/type/JournalArticle 1016-3328 1420-8954 http://hdl.handle.net/1721.1/106915 Belovs, Aleksandrs. “Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound.” Comput. Complex. 24, no. 2 (April 17, 2015): 255–293. en http://dx.doi.org/10.1007/s00037-015-0099-2 computational complexity Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Basel application/pdf Springer Basel Springer Basel |
| spellingShingle | Belovs, Aleksandrs Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound |
| title | Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound |
| title_full | Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound |
| title_fullStr | Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound |
| title_full_unstemmed | Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound |
| title_short | Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound |
| title_sort | quantum algorithms for learning symmetric juntas via the adversary bound |
| url | http://hdl.handle.net/1721.1/106915 |
| work_keys_str_mv | AT belovsaleksandrs quantumalgorithmsforlearningsymmetricjuntasviatheadversarybound |