**On Wednesday, January 26, Farrokh Labib will defend his thesis on “Quasirandomness in quantum information theory”. Farrokh’s dissertation contributes to a large international research program that is trying to map out how information can be processed on quantum systems and when this has or does not have advantages over ‘classical’ information processing. This is important because a lot is currently being invested in the development of quantum computers.**

One of the chapters in his thesis deals with the question of how well a quantum computation could be simulated with classical computers. It is expected that this will not work in general, but we are not 100% sure yet. Farrokh uses mathematical techniques developed in the last 20 years for a completely different purpose to make progress in a special case of this problem.

The philosophy behind those mathematical techniques has to do with the ‘structure-versus-coincidence phenomenon’. This phenomenon was identified in the late 1990s in work by Field Medal winner Tim Gowers. That was about the fact that every sufficiently large set of whole numbers must contain an `arithmetic sequence’. Such a row is formed by each time making a step of the same size (eg 2,5,8,11 etc, where the step is 3). Arithmetic sequences are thus ‘inevitable patterns’: No matter how you choose a set of numbers, if there are enough of them, you can find a long arithmetic sequence in it. To prove this mathematically, you can look at two complementary situations. Your set of numbers can look a lot like a totally random set, say where you toss a coin at each number to decide whether to add it or not. In that case it is relatively easy to show that there is a long arithmetic sequence. If your collection does not look randomly selected, you can show that it must have a certain structure. This is roughly comparable to a the piano keys a cat would pick (coincidentally) and a chord (structured). You can then use this structure to find an arithmetic sequence. Farrokh shows that this phenomenon also occurs and can be used in quantum information.

#### More information

- The research was carried out at QuSoft, and at the
**Algorithms and Complexity group**at CWI the Centrum Wiskunde & Informatica (CWI), Amsterdam. - The PhD ceremony takes place on Wednesday 26 January 2022 at the UvA. Supervisor: prof.dr. H.M. Buhrman (CWI/UvA) and dr. J. Briet (CWI)
- PhD thesis of Farrokh Labib:
**Quasirandomness in quantum information theory** **Website Farrokh Labib**