2023 Iowa State REU Projects
Quantum information theory
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.
Spectral graph theory
Project mentor: Steve Butler
Graphs look at how objects (vertices) are connected (via edges). One way to store and understand a graph is to associate it with a matrix (think array with benefits). So given a graph, there is a matrix, given a matrix, there are eigenvalues. The goal of spectral graph theory is to understand what is the relationship between the graph and the eigenvalues.
We will primarily be considering a matrix known as the distance matrix, which stores information about how far apart pairs of vertices are, and consider what happens when we "glue" two graphs together at a vertex. Our main goal is to either find formulas, or relationships, that might arise from gluing with an ultimate goal of answering a conjecture from the 2022 REU.
In the meantime we will have fun with combinatorial flavored problems on the side including nontransitive dice games, prime juggling patterns, robotic scheduling and bijections with trees, and some card shuffling. We will also work on building a LEGO Menger sponge which has been sliced at an angle.
Prerequisites: A (proof-based) linear algebra course and some experience with discrete mathematics (e.g. combinatorics or graph theory). Experience with programming will be helpful, but not required
Mixing times of Markov chains
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.
Project mentor: James Rossmanith
When sufficient energy is added to a gas, electrons are stripped from their atoms, turning the previously neutral gas into an electrically charged gas comprised of negatively charged electrons and positively charged nuclei. This state of matter is plasma, the fourth state of matter after solid, liquid, and gas; plasma is the most abundant form of ordinary matter in the universe, largely because stars are gravitationally confined balls of plasma. Plasma also occurs terrestrially in various engineering and physics applications, most notably in fusion reactors in the quest for humanity to create cleaner energy sources. Therefore, modeling and understanding plasma dynamics is extremely important in the scientific community.
At very small scales, plasma is a collection of electrically charged and neutral particles that interact through various short, medium, and long-scale forces. At larger scales, the plasma can be described by macroscopic quantities such as particle number densities, momentum densities, and energy densities. Physically meaningful mathematical models of plasma dynamics are inherently difficult to solve. These models are typically nonlinear and describe dynamics over many spatial and temporal scales that couple in complex ways.
In this REU project, we will study computational numerical methods for a (relatively) simple time-dependent plasma model in a single spatial dimension bounded by two infinitely conducting walls. We will consider a two-fluid model of electrons and ions that couple to each other through an electrostatic force and ionization. Although no exact solution is known for this problem, qualitatively, the behavior is well-understood and consists of small regions of charged gas near the walls and a quasi-neutral region in the bulk of the domain. We will study numerical methods that employ operator-splitting techniques to solve the underlying equations and approaches that do not require operator-splitting.
Basic programming skills (any programming language is fine)
Some background in numerical analysis (introductory undergraduate level)
Some familiarity with partial differential equations (introductory undergraduate level)
Strong mathematical curiosity is expected of the participants