Project description
Non-local game (Ronald de Wolf, lecture notes Chapter 17) is a fascinating subject connecting quantum information, complexity theory and operator algebra. One such formulation is the complexity class MIP*, the set of problems which can be reduced to approximate the optimal success rate of a non-local game using quantum strategy. Surprisingly, MIP* was shown to be equivalent to the halting problem in one of the breakthrough results of the last decade (MIP*=RE) and, consequently, resolves one of the biggest conjectures within functional analysis (Conners embedding conjecture)!
This project will consider a more limited model, where the players are only allowed a bounded number of entanglements in their quantum strategy. This project aims to show a hierarchy of complexity classes (similar to the runtime hierarchy theorem) but for the amount of entanglement used.
Background required
Strong complexity background (Turing Machines) and strong quantum information background are strongly preferred but not necessary.
Work environment
QuSoft, group Algorithms & Complexity (A&C) at CWI, Amsterdam
What to expect
Background reading and performing research.
Duration
- MSc Information Studies and MSc Logic: 6 months
- MSc Software Engineering: 3 months
- MSc Computational Science: 8 months
Programmes
Master Logic (6 months), Master Computational Science (8 months)
Project Contact
drs. Doutzen Abma (doutzen@cwi.nl)
