Ronald de Wolf (Centrum Wiskunde & Informatica & UvA)

Mathematical Aspects of Quantum Machine Learning

Machine learning can be enhanced by quantum computing, both by allowing quantum data and by having quantum speedups for the optimization process that finds a good model for given data. This talk will examine some mathematical aspects of both.

Peter Bruin (Leiden University)

Hidden shift problems

There has been a lot of interest in possible quantum algorithms for solving the following problem. Suppose we are given an Abelian group A, a set X and two injective `black-box’ functions f, g: A → X such that for some unknown s ∈ A (the hidden shift) and all a ∈ A, we have g(a) = f(a + s). How can we efficiently (in terms of both the number of function evaluations and computation time) determine s?

Unlike for the somewhat similar hidden subgroup problem, which is efficiently solved by Shor’s algorithm, no polynomial-time quantum algorithm is known for the hidden shift problem. The best known algorithm for the general problem is Kuperberg’s subexponential algorithm.

I will talk about various aspects of quantum algorithms for (special cases of) the hidden shift problem. Parts of this are joint work in progress with Māris Ozols, Arend-Jan Quist and Serge Adonsou.

Maris Ozols (University of Amsterdam)

Quantum telepathy for mathematicians

The goal of this talk is to introduce quantum pseudo-telepathy to a wider audience of mathematicians through the example of quantum nonlocal games. I will try to explain it at three levels of difficulty.

First, I will introduce the celebrated Mermin-Peres magic square game and explain why it has no perfect classical strategy but has a perfect quantum strategy. Next, I will discuss an elegant framework by Arkhipov (https://arxiv.org/abs/1209.3819) that characterizes nonlocal games with perfect quantum strategy in terms of graph planarity. Finally, I will mention a recent homotopical extension of Arkhipov’s framework due to Okay & Raussendorf (https://arxiv.org/abs/1905.03822).