This research project is about exploring surprising links between the foundations of quantum information theory and classical computation.
The project is a unique cooperative effort of leading experts in quantum information (the group Algorithms and Complexity, led by prof. Harry Buhrman) and optimization (the group Algorithms, Combinatorics and Optimization, led by prof. Monique Laurent).
Keywords
Quantum Entanglement
Quantum Mechanics is currently the most accurate theoretical model of Nature on atomic scales.
Quantum information theory is a revolutionary new field of science and technology, whose central goal is to understand the power of quantum-mechanical systems for information processing.
The field has been growing explosively since the 1990s, when it was first realized that quantum devices can be used to perform a number of information-processing tasks thought to be hard, or even impossible, in a classical world. For example, a quantum computer is able to factor an integer into its prime factors exponentially faster than any known classical algorithm.
Quantum systems can behave very differently from classical ones. In particular, two spatially separated quantum systems can be entangled, meaning that they are correlated in a non-classical way. Sharing entanglement allows remote parties to realize nonlocal correlations that are impossible to obtain classically, without imparting them with the ability to communicate instantaneously. This distinction is one of the most peculiar aspects of quantum theory and required many years to be properly appreciated.
Two broad objectives of this project are to develop our understanding of entanglement and to study settings in which entanglement can be utilized as a tool in real-world situations. Entanglement can be studied quantitatively through the use of nonlocal games. Nonlocal games form a theoretical framework modelling physical experiments with which properties of entanglement can be tested in a lab. Recently, quantum variants of well-known graph parameters such as the chromatic number and the Shannon capacity were studied in the contexts of contrasting quantum mechanics with its classical variant, entanglement-assisted communication over noisy channels and optimization.
Optimization, semidefinite programs and hierarchies
Optimization typically involves searching for an optimal element in a huge complex structure of possible choices.
A famous example of a combinatorial optimization problem is the maximum cut problem problem (MAX CUT), where one has to partition the vertices of a graph to maximize the number of the edges crossing the partition.
MAX CUT belongs to the general class of polynomial optimization problems, where the objective is to minimize or maximize a real-valued polynomial over a set of vectors that satisfy a number polynomial constraints. Polynomial optimization in general is NP-hard.
Other examples of polynomial optimization problems are finding optimal classical strategies for a given nonlocal game, determining the chromatic number of a graph and computing the cut-norm of a matrix.
One can also consider polynomial optimization over non-commutative variables, which is more suitable for studying problems such as finding optimal quantum strategies for nonlocal games.
To turn a hard polynomial optimization problem into a tractable problem, one can relax it by modifying or dropping some of the constraints. By doing so, some of these problems can be turned into polynomial-time solvable semidefinite programs, whose optimum can be used to approximate the true optimum. A celebrated example of this is Goemans and Williamson's semidefinite programming relaxation of the MAX CUT problem.
Certain nonlocal games known as XOR games can be relaxed similarly to get semidefinite programs that approximate the classical value (in fact, MAX CUT can be reduced to computing the classical value of an XOR game).
A celebrated and fundamental result from functional analysis, Grothendieck's inequality, then shows that the classical value of XOR games can be approximated to within a factor 1.78... (this factor is known as Grothendieck's constant).
As for the quantum value of XOR game, a surprising result of Tsirelson shows that these values are exactly the optimum of the semidefinite relaxition for the classical value!
Hierarchies of semidefinite programing relaxations involving increasing numbers of constraints, can be used to approximate optimization problems for which no good polynomial-time approxiamtion algortihms are known. Recently, hierarchies for polynomial optimization problems in non-commutative variables were discovered. These can be used, for example, to approximate the entangled winning probability of nonlocal games.
PhD and postdoc positions are currently available for highly motivated people with a strong background in computer science and/or mathematics. You can apply by contacting Harry Buhrman or Monique Laurent.
Nonlocal games provide a
quantitative framework in which to study quantum entanglement and nonlocal quantum correlations. Consider the following game, played by Alice and Bob (who are on the same team) against Charlie. The game proceeds as follows: Charlie, whose strategy is fixed, sends Alice a bit a and Bob a bit b, choosing each bit independently and uniformly at random. Alice and Bob can agree on a strategy before the game begins but are not allowed to communicate once they receive questions. Alice and Bob win the game if they output one bit each, in such a way that the XOR of the bits they output is equal to a^b (the AND of the two inputs). In other words, they should output the same bit, except when both input bits are 1. A moment's reflection shows that their best strategy is to always output, say, 0. This allows them to win on three of the four possible inputs. It is also not difficult to show that equipping them with a shared source of randomness cannot help: the average success probability over the four possible questions will always be at most 3/4. Thus the maximum probability with which Alice and Bob can win, termed the classical value of the game, is 3/4. This game is the simplest example of a nonlocal game, and is also
called XOR-game because the correlations between Alice and Bob are in the XOR of their outputs.
What is remarkable is that if Alice and Bob are allowed
to share quantum entanglement, then they can win the game with probability about .85, no matter which questions are asked. The maximum probability with which Alice and Bob can win if they share entanglement is termed the quantum value of the game.
