Structure and randomness in quantum networks

Arguably the most striking feature of quantum mechanics is entanglement,

    which manifests itself when two or more quantum systems are measured

    locally in one of two or more possible bases. As an argument against

    quantum, it was observed by Einstein, Podolsky and Rosen that compound

    systems allow superpositions that can result in measurement statistics

    that defy classical Newtonian explanation. A rough interpretation of

    this is that compound quantum-mechanical systems can form networks whose 

    structure only becomes apparent through inherently random outcomes of

    local observations. Celebrated work of Bell showed that one can test

    this feature experimentally. Nonlocal games provide a simple yet

    powerful language to quantitatively reason about such tests. Moreover,

    such games enjoy several intriguing connections with many other areas

    such as quantum algorithms, quantum verification, Banach- and operator

    space theory, approximation algorithms, etc.

    Our current research involves studying the structure of games with the

    property that entanglement does not provide much advantage over

    classical Newtonian play. Counter-intuitively, an important conjecture

    in operator space theory would imply that such games could be turned

    into computational problems that admit fast quantum algorithms. As such

    our project might also give more insight about what structure enables

    quantum computers to quickly solve a problem. Preliminary results expose

    a surprising link with a recent line of research in additive

    combinatorics regarding quantitative measures of (pseudo)randomness in

    the form of Gowers norms and hypergraph norms. The latter also appear in

    the study of graph homomorphism counting and we hope to explore this

    link further in the near future.