Projects are listed by Type:
Algorithms, Machine Learning-AI, Quantum Computing
Algorithms Projects
TITLE: Space-Efficient Parallel Algorithms
Mentor: Laxman Dhulipala
Prerequisites Knowledge of Data Structures and Algorithms. Programming skills in C
Description
In parallel algorithm design we are interested in designing algorithms that obtain good speedup over the fastest sequential algorithms as we increase the number of cores used. The two primary measures of interest are the work of the algorithm, i.e., the total number of basic operations performed, and the depth, i.e., the longest chain of sequential dependencies in the algorithm. Due to the increasing size of modern data, designing algorithms that also minimize the amount of space used by the algorithm while having high parallelism are of interest. This project will explore theoretical and practical parallel algorithms that have provably low space usage. Some directions we may consider include designing succinct or compact parallel algorithms, space-efficient parallel graph algorithms, and space-efficient parallel data structures. In this project you will learn about parallel algorithms and space-efficient algorithms and parallel programming.
TITLE: Exploring the Hilbert and Thompson Geometries Computationally
Mentors: David Mount, Auguste Gezalyan
Prerequisites Knowledge of discrete structures/introduction to proofs, algorithms, and programming skills.
Description
The field of computational geometry looks at problems in Eucilidean Geometry computationally. For example, given n points in the plane, find which two are closest together. But there are other metrics that have been useful in fields such as Genetics, Probability, and Physics (see HERE). In this project we will be examining the Hilbert and Thompson Metric (Hilbert Metric: HERE Thompson Metric: HERE) from the perspective of computational geometry. We will explore questions involving this metric, such as how it behaves in the probability simplex. (see HERE). The project will include contributing to a software package to help us visualize these structures. In this project you will learn computational geometry and combine computational geometry with programming.
Machine Learning and AI Projects
TITLE: Machine Learning for Autonomous Driving: Theory and Practice
Mentors: Ming Lin
Prerequisites Basic knowledge about Machine Learning and Neural Networks. Experience with Game Engines preferred but not required.
Description
Recent advances in self-driving platforms, from food delivery robots to autonomous vehicles (AV), highlight the urgent need for strong safety standards. AVs to operate in a mixed autonomy, where there will be human-driven and self-driving cars operating side by side on the road for the foreseeable future need the capability to anticipate human-driven vehicle behaviors. Human behaviour is different and less predictable than a self-driving car, thereby making it especially critical to capture large amounts of human driving data under diverse pre-crash scenarios for machine learning algorithms to learn from human demonstration.
This project aims to bridge this gap between theory and practice of Machine Learning applied to Autonomous Driving. This project will enable machine learning algorithms for autonomous driving to learn to drive more safely from collections of human driving data and behaviors in high-risk situations. This work will significantly enhancing our understanding of driving dynamics and vehicle safety.
TITLE: Cross-species identification of DNA that moves around: Retrospective analysis and improved methods
Mentors: Erin Molloy,Rachel Parsons
Prerequisites
1) Familiarity with discrete math, algorithms, probability, and machine learning
2) Knowledge of command line (UNIX)
3) Proficiency in at least one programming language (ideally Python or C/C)
Description
Did you know that 30-50% of human (and other vertebrate) genomes are derived from DNA sequences that can copy-paste themselves to new locations?! These DNA sequences, called retrotransposons, are major drivers of genome expansion and innovation. Researchers studying these biological processes need to identify retrotransposons that are present or absent across the genomes of different species or individuals of the same species.
In this project, you will learn about theory and practice for analyzing biological data with discrete and machine learning algorithms. First, you will perform an empirical evaluation of the leading methods for cross-species retrotransposon identification from short read data, leveraging high quality genome reconstructions that have only recently become available, thanks to advances in long-read sequencing. Second, you will perform a probabilistic analysis of method accuracy and compare it to your experimental results. Time permitting, you will seek to develop new and improved methods.
TITLE: Crop Planning Decision Support with Multi-Agent Reinforcement Learning
Mentor: Aviva Prins
Prereqisites Algorithms, Machine Learning, Python. Helpful but not required: Game theory, Databases (SQL)
Description
In India, the majority of farmers are classified as small or marginal, and their livelihoods are vulnerable to climate risk. Giving farmers help in planning crops well (e.g., delaying planting by a couple of days) can make a huge difference to their expected income. The overall goal of this project is to build an optimization-based decision support tool that provides crop planning advice to farmers. This summer, well be focusing on decision support for multiple farmers and variable-length or hierarchial episodes.
This work is in conjunction with Kheyti a nonprofit in India. Check out the paper that came out of the 2023-REU-CAAR and 2024-REU-CAAR:
Quantum Computing Projects
TITLE: Symmetries, defects, and boundaries of bicycle codes
Mentors: Victor Albert, Dominic Williamson
Prerequisites It is preferred that candidates are familiar with basic quantum mechanics, (binary) linear algebra, and basic programming.
Description
Quantum technologies rely on inherently quantum mechanical correlations that are fragile to noise induced by coupling to the environment. Quantum error-correcting codes can protect quantum correlations at the cost of a time and space overhead that is required to run consistency checks on the code. The surface code has long been the leading candidate for the implementation of quantum error correction. However it comes with a large overhead cost which has motived recent exploration of more sophisticated codes that reduce the overhead cost. A prominent family of such codes are the bivariate bicycle codes, which have been demonstrated to perform well even at small sizes. In this project we will take techniques which are well understood for surface code, such as altering the lattice, boundary conditions, and including defects, and introduce them into the setting of bivariate bicycle codes. The space for exploration in this area is wide open and so the project could go in many directions including decoding, finding higher code thresholds, lowering code overhead, or performing logical operations.
TITLE: Quantum routing for neutral atoms and beyond
Mentors: Andrew Childs,Alexy Gorshov
Prerequisites Linear algebra, programming, and general mathematical maturity. Some experience with quantum information and/or quantum physics is a plus.
Realistic quantum processors typically come with constraints on how their qubits can interact. To implement general quantum circuits, which may involve interactions between any pair of qubits, one can permute the qubits so that the desired interactions can be performed locally. The cost of such “quantum routing” depends significantly on the available connectivity and other constraints on the kinds of operations that the system can perform. This project will study protocols for performing quantum routing as efficiently as possible, as well as limitations on how efficient such protocols can be. In particular, we will consider questions motivated by systems of neutral atom qubits, which can be repositioned using so-called optical tweezers.
The project may investigate one or more of the following topics, and/or variations thereof, depending on the background of the participants and the state of the art at the outset of the project:
1) Neutral atom routing in practice. Prior work has developed protocols for permuting neutral atom qubits under natural constraints on the ways that subsets of the qubits can be transported, and has established general upper bounds on the performance of these protocols. However, it is not well understood how well these methods will perform in practice. By implementing these protocols in software, we can study how well they work on particular quantum computing tasks of interest, and try to develop new protocols that perform even better.
2) Limitations on neutral atom routing. Prior work has also shown limitations on how efficiently neutral atom qubits can be permuted. However, these bounds are not constructive. By finding explicit examples of permutations that saturate the bounds, we can identify features that make neutral atom routing hard.
3) Neutral atom routing in three dimensions. Work so far has focused on protocols and lower bounds for one- and two-dimensional arrays of neutral atom qubits. While more technically challenging, it is possible that more advanced systems could manipulate neutral atom arrays in three dimensions. It would be useful to understand the capabilities and limitations of quantum routing protocols in this setting.
4) Quantum routing lower bounds by counting arguments. The non-constructive lower bounds on the efficiency of neutral atom routing are based on so-called “counting arguments,” which turn out to provide a powerful technique. This approach has not been explored for other models of quantum routing that are motivated by other natural constraints on quantum information processors. It would be natural to explore the power of counting arguments for other models of quantum routing, and to investigate other ways of lower bounding the efficiency of quantum routing in various models.
TITLE: Reducing the overhead for quantum error correction with LDPC codes
Mentors Yuxin Wang,Yifan Hong
Prerequisites Proficiency with linear algebra. Familiarity with error-correcting codes (classical or quantum) helpful but not required.
Description
Quantum error correction is an essential primitive for many algorithms to run reliably in noisy quantum computers. In a quantum error-correcting code, information is encoded in collective degrees of freedom known as logical qubits. The ratio of physical to logical qubits in a code is a measure of its spatial overhead and is an important metric for practical implementation. Quantum low-density parity-check (LDPC) codes are a class of codes where this overhead can be asymptotically optimal (constant). Despite this theoretical promise, the constant can still be quite large, which can prohibit practical implementations.
In this project, you will learn about constructions of classical and quantum LDPC codes and their applications to fault-tolerant quantum computing. The goal is to explore methods to reduce the spatial overhead of LDPC codes, while maintaining their useful error-correcting properties. The results of this project should improve the practical implementation of certain quantum LDPC codes in near-term hardware.
TITLE: Qutrit Quantum Quadratic Residue codes
Mentors Shubham Jain
Prerequisites: Linear algebra, Programming. Familiarity with finite field and quantum mechanics helpful but not required.
Description
Quantum error correction is a structure underlying all quantum computing operations which ensures that the noise present in hardware does not irretrievably damage the information involved in quantum computations. This typically involves encoding one qubit worth of information in the entangled state of many qubits, a quantum error correcting code. A subclass of quantum error correcting codes, known as the CSS codes, allow simple descriptions via a pair of classical error correcting codes, which are formally just vector spaces over the binary field.
One of the prime challenges in quantum computing is to find codes and protocols which allow universal computation (i.e. a full set of quantum gates) compatible with the error correcting code. One of the harder gates to implement in this full set is called the T-gate. We previously identified a family which comes in pairs of such codes (See (1) below), with resource scaling of 
as opposed to the previous state of the art 
, where 
is some measure of code performance. These codes all come from the classical binary Quadratic Residue (QR) code family.
The student would work on extending similar ideas to qutrits, i.e. the quantum versions of numbers over the finite field 
. These are expected to follow the same formal structure as the previous work on qubits. The student would work on identifying ternary quadratic residue codes and make sure they generalize to quantum codes with the desired properties, patching things along the way if they don’t work. Depending on the time and interest of the student, the project can then be extended to incorporate higher dimensional finite fields .
(1) Jain S., Albert, V.V., High-distance codes with transversal Clifford and T-gates
TITLE: Robust Bell Sampling
Mentors Michael Gullans
Prerequisites: Linear algebra, Computer Programming, basic quantum mechanics and quantum computing.
Description
The project involves analyzing Bell sampling of quantum simulation algorithms in the presense of noise. We will develop error mitigation strategies that can be used for verification therough fidelity estimation and shadows for local observables. the student will work with a graduate student to analyze the problem theoretically, perform numerical simulations, and implement the protocols on past and new experiemental data.
Outcome/Goals for the Summer Reserach: The deliverables include open source code for error mitated Bell sampling, as well as contributions toa paper on robust Bell sampling to be written in collaboration with the PI, a gradute student, and a postdoc.