1210.3279 (Aleksandrs Belovs)

On the Power of Non-Adaptive Learning Graphs    [PDF]

Aleksandrs Belovs

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 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 certificate structures defined by certificates of bounded size. 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 this function. In particular, we show that the learning graph for the triangle problem from arXiv:1210.1014 is optimal in these settings.

View original: http://arxiv.org/abs/1210.3279