On the Power of Non-Adaptive Learning Graphs
arXiv:1210.3279
Abstract
We introduce a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only require the knowledge of the disposition 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 and 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 -sum problem derived recently in arXiv:1206.6528. Finally, we use these results to show that the learning graph for the triangle problem from arXiv:1210.1014 is almost optimal in these settings. This also gives a quantum query lower bound for the triangle-sum problem.
16 pages, 1.5 figures v2: the main result generalised for all certificate structures, a bug in the proof of Proposition 17 fixed
References in corpus (11)
- Search via Quantum Walk
- Negative weights make adversaries stronger
- The quantum query complexity of the hidden subgroup problem is polynomial
- Quantum query complexity of state conversion
- Learning-Graph-Based Quantum Algorithm for k-distinctness
- Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem
- Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
- Quantum lower bounds by quantum arguments
- Quantum algorithms for subset finding
- A quantum query algorithm for the graph collision problem
- Adversary Lower Bound for the k-sum Problem