On 26 January Farrokh Labib defended his thesis on 'Quasirandomness in quantum information theory'. His 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 Labib's 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 it is not 100% sure yet. The researcher used mathematical techniques that were 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 (e.g. 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. Labib 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 took place on Wednesday 26 January 2022 at the UvA. Supervisor: Prof. H.M. Buhrman (CWI/UvA) and dr. J. Briet (CWI)
- PhD thesis of Farrokh Labib: Quasirandomness in quantum information theory
- Website Farrokh Labib
- Source: QuSoft news item on Farrokh Labib
