22nd Estonian Winter School in Computer Science (EWSCS)
XXII Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 5 - 10, 2017

Alexander Belov

Faculty of Computing
University of Latvia

Quantum query complexity and the adversary bound


In the query complexity model, the complexity of an algorithm is measured by the number of queries it makes to the input string, assuming all other operations are free. This is a useful model for proving lower bounds, in particular in cryptography, and it is quite non-trivial, so that studying query complexity gives sufficient insight into the inner workings of algorithms.

In this series of lectures, we will consider quantum query complexity using the so-called adversary bound. The adversary bound is a tight characterisation of quantum query complexity by a semi-definite optimisation program. First, we define the bound, consider some simple examples, and discuss its usefulness for function composition. Next, we move to the model of learning graphs, which is a convenient way for constructing quantum query algorithms via the adversary bound. In particular, we will cover quantum query complexity of the love triangle problem in detail. Finally, we consider some other applications of the bound, and mention few open problems.

Familiarity with quantum computation is not required. Familiarity with deterministic/randomised query complexity, linear algebra and semi-definite optimisation is a bonus.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed March 19, 2017 0:26 Europe/Helsinki (GMT +02:00) by local organizers, ewscs17(at)cs.ioc.ee
EWSCS'17 page: //cs.ioc.ee/ewscs/2017/