On the Power of Non-Adaptive Learning Graphs

Aleksandrs Belovs, Ansis Rosmanis

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 requir…