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

Alexander Belov

Faculty of Computing
University of Latvia
Latvia

Quantum query complexity and the adversary bound

Abstract

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

• A. Belovs. Quantum query complexity and the adversary bound. Slides from the EWSCS 2017 course.
• Lecture 1: The adversary bound [pdf]
• Lecture 2: Learning graphs [pdf]
• Lecture 3: Dual learning graphs [pdf]
• Lecture 4: Further topics [pdf]
• Problems on the lecture material [pdf]
• Videos from the lectures (unedited, large files).
• Lecture 1 [mts]
• Lecture 2 [mts]
• Lecture 3 [mts]
• Lecture 4 [mts]


• A. Belovs. Applications of the Adversary Method in Quantum Query Algorithms. PhD thesis, U. of Latvia, 2013. [thesis on arXiv]
• A. Belovs. Quantum algorithms for learning symmetric juntas via the adversary bound. In Proc of 29th IEEE Conf. on Computational Complexity, CCC 2014, pp. 22-31. IEEE 2014. [doi link]
• A. Ambainis, A. Belovs, O. Regev, R. de Wolf. Efficient quantum algorithms for (gapped) group testing and junta testing. In Proc. of 27th Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA 2016, pp. 903-922. SIAM, 2016. [doi link]

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/