Project mentor: Peter Burton

In quantum information theory, a nonlocal game is a cryptographic protocol designed to test concepts of entanglement between particles. The set-up involves two players, conventionally known as Alice and Bob, who submit pairs of answers to pairs of questions posed by a ‘referee’. Before the game starts, Alice and Bob get to look at all the question pairs the referee plans to ask, together with the list of correct answers. However, once the game has started they are not allowed to communicate with each other. During the game, the referee chooses a pair of questions at random from the prearranged list and transmits one to Alice and one to Bob. They each have to send back a response, but crucially the correctness of a pair of answers to a pair of questions depends on both questions! In other words, whether Alice should answer ‘yes’ or ‘no’ to a given question can depend not only on the question she received but also on the question Bob received, about which she has no knowledge. This turns the game into a communication dilemma – how do you build a strategy for a game where you only know what question you got but to answer correctly you need information about which question the other player got?

The Einstein–Podolsky–Rosen hypothesis from 1935 suggested that the best Alice and Bob can do under the laws of physics is to write down a common strategy beforehand and just stick to it once the noncommunicating phase of the game has started. In the 1960s it was discovered that quantum entanglement allows for better strategies, so that if Alice and Bob can build a machine which sends them a pair of entangled photons then they can exploit the entanglement to coordinate their answers without directly communicating. The first experimental verification that this is actually possible occurred in 1982 and is known as Aspect’s experiment. Aspect and his collaborators won the 2022 Nobel Prize in Physics for this result and it is generally regarded as the strongest empirical proof that quantum entanglement is a real phenomenon.

Our REU project will focus on a new formulation of the nonlocal game set-up that involves calculating averages of functions on finite sets rather than the usual description in terms of projection operators on Hilbert spaces. We’ll start off by using this technique to understand the classic CHSH game underlying Aspect’s experiment and then move on to other nonlocal games involving combinatorial problems like completing magic squares. These games are tractable concrete objects – the CHSH game involves only sixteen bits – but the averaging approach was introduced very recently and so there should be some interesting opportunities for original research into what it means.

Project mentor: David Herzog

A Markov chain is a process that evolves randomly in time where the future of the system depends only on the current state and not its past. Simple examples of Markov chains include:

• A gambler's total "winnings" after playing a game sequentially in which they bet $1 and with $1 with probability p and lose a $1 with probability 1-p (where 0<p<1).

• The number of balls in a given bin after moving balls between bins randomly, e.g. starting from a collection of r balls in two bins, with k in bin 1 and r-k in bin 2, pick one of the r balls at random and move it to the other bin and repeat.

Although these examples may appear basic, they are the building blocks for describing complex phenomena such as the movement of pollen grains suspended in water (i.e. Brownian motion), the behavior of stock prices over time, card shuffling schemes, turbulent fluid flow and statistical sampling algorithms.

In concrete examples of interest, the goal of this project is to understand how long it takes for a Markov chain to be close to its statistical equilbrium, also known as estimating the mixing time of the chain. Thinking in the context of card shuffling, understanding the mixing time is the same as understanding when the deck of cards is well-shuffled. In the context of fluids, if we put a dye in the fluid under a stirring mechanism, the mixing time measures how long it takes for the dye in the fluid to be well-mixed.

Despite the mixing time being a natural quantity associated to the Markov chain, outside of a few, simple examples it is difficult to actually estimate it. This is because the equations describing the chain can be difficult to parse, e.g. in the context of fluids the Euler/Navier-Stokes equations are hard to understand. The goal of this REU will be to study mixing times of Markov chains arising in card shuffling schemes using a combination of numerics, heuristics and theoretical arguments.

Prerequisites: A course in undergraduate probability and basic programming skills. Some background in MATLAB and stochastic processes will be helpful but not required.