Quantum computers are an emerging technology which may allow to solve some hard problems efficiently. The most prominent example is to factorize integers in polynomial time. However, looking more closely we find that such spectacular speedups are achieved only for highly structured problems, and that the algorithms heavily exploit these intrinsic structures.
In this talk, we will examine the other end of the spectrum: How much do we gain from quantum computers for general purpose algorithm schemes? In particular, we will look at evolutionary algorithms, which are widely used in practice just because they may be applied without any deep knowledge about the problem. We will see how to transfer EAs to quantum computers, and I will explain how to analyze the runtime of such quantum evolutionary algorithms (QEAs) by classical means. Surprisingly, it turns out that the speed-up depends very much on the problem at hand, and at the end of the talk we will understand quite precisely the type of problems where QEAs are superior to their classical counterparts.
Evolutionary algorithms (EAs) are widely used in practice since they may be used with only minimal knowledge about the problem at hand.