On the Power of Non-adaptive Learning Graphs
We introduce a notion of the quantum query complexity of a certificate structure. This is a formalization of a well-known observation that many quantum query algorithms only require the knowledge of the position of possible certificates in the input string, not the precise values therein. Next, w...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Basel
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106914 |
| _version_ | 1826195199633653760 |
|---|---|
| author | Belovs, Aleksandrs Rosmanis, Ansis |
| 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 Rosmanis, Ansis |
| author_sort | Belovs, Aleksandrs |
| collection | MIT |
| description | We introduce a notion of the quantum query complexity of a certificate structure. This is a formalization of a well-known observation that many quantum query algorithms only require the knowledge of the position of possible certificates in the input string, not the precise values therein.
Next, we derive a dual formulation of the complexity of a non-adaptive learning graph and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure such that a learning graph gives an optimal quantum query algorithm for it.
For a special case of certificate structures generated by certificates of bounded size, we construct a relatively general class of functions having this property. The construction is based on orthogonal arrays and generalizes the quantum query lower bound for the k-sum problem derived recently by Belovs and Špalek (Proceeding of 4th ACM ITCS, 323–328, 2013).
Finally, we use these results to show that the learning graph for the triangle problem by Lee et al. (Proceeding of 24th ACM-SIAM SODA, 1486–1502, 2013) is almost optimal in the above settings. This also gives a quantum query lower bound for the triangle sum problem. |
| first_indexed | 2024-09-23T10:08:58Z |
| format | Article |
| id | mit-1721.1/106914 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:08:58Z |
| publishDate | 2017 |
| publisher | Springer Basel |
| record_format | dspace |
| spelling | mit-1721.1/1069142022-09-30T19:12:59Z On the Power of Non-adaptive Learning Graphs Belovs, Aleksandrs Rosmanis, Ansis Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Belovs, Aleksandrs We introduce a notion of the quantum query complexity of a certificate structure. This is a formalization of a well-known observation that many quantum query algorithms only require the knowledge of the position of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by certificates of bounded size, we construct a relatively general class of functions having this property. The construction is based on orthogonal arrays and generalizes the quantum query lower bound for the k-sum problem derived recently by Belovs and Špalek (Proceeding of 4th ACM ITCS, 323–328, 2013). Finally, we use these results to show that the learning graph for the triangle problem by Lee et al. (Proceeding of 24th ACM-SIAM SODA, 1486–1502, 2013) is almost optimal in the above settings. This also gives a quantum query lower bound for the triangle sum problem. National Science Foundation (U.S.) (Scott Aaronson’s Alan T. Waterman Award) 2017-02-10T21:02:51Z 2017-02-10T21:02:51Z 2014-05 2016-08-18T15:40:16Z Article http://purl.org/eprint/type/JournalArticle 1016-3328 1420-8954 http://hdl.handle.net/1721.1/106914 Belovs, Aleksandrs, and Ansis Rosmanis. “On the Power of Non-Adaptive Learning Graphs.” Comput. Complex. 23, no. 2 (May 13, 2014): 323–354. en http://dx.doi.org/10.1007/s00037-014-0084-1 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 Rosmanis, Ansis On the Power of Non-adaptive Learning Graphs |
| title | On the Power of Non-adaptive Learning Graphs |
| title_full | On the Power of Non-adaptive Learning Graphs |
| title_fullStr | On the Power of Non-adaptive Learning Graphs |
| title_full_unstemmed | On the Power of Non-adaptive Learning Graphs |
| title_short | On the Power of Non-adaptive Learning Graphs |
| title_sort | on the power of non adaptive learning graphs |
| url | http://hdl.handle.net/1721.1/106914 |
| work_keys_str_mv | AT belovsaleksandrs onthepowerofnonadaptivelearninggraphs AT rosmanisansis onthepowerofnonadaptivelearninggraphs |