Research Statements

Largest coding project question The largest programming project I’ve contributed to was a program which could take an arbitrary boolean function as input and design an Ising Hamiltonian whose ground states modeled the correct answers of the given function. It consisted roughly of three parts:

A) Python program predominantly using PyTorch to construct an initial linear programming problem, almost always infeasible B) Custom Merhrotra predictor-corrector LP solver written in C used to solve the linear program OR assign a score quantifying the degree of infeasibility of the linear program. Optimized specifically for our problem, up to 100x faster than the GLOP solver provided by Ortools C) Python circuit design program which modified the linear program using the score given by the LP solver. Steps B) and C) alternate until a feasible LP is found, at which point the problem is solved. Details can be found in “Design of General Purpose Minimal-Auxiliary Ising Machines” listed above.

I worked primarily with one other collaborator (Andrew Moore, co-first author on the paper) on this project with feedback from a larger team of 7 people. About 50% of the code was written by me.

This program consisted of roughly 5,000 lines of code between Python and C. Research on the project involved a lot of pen-and-paper mathematics informed by dozens of experiments, mostly written in Python. These experiments, though not strictly part of the final program, grew into a fairly robust code base featuring their own API and lots of reusable general code. If these are included in the line count, the full ecosystem is roughly 50,000 lines of code (average of ~500 lines for 100 python files).

Creativity Question I concluded my work on the Ising problem this past December. The aim of the project was simple: design an Ising computer capable of 8x8 digit integer multiplication using as few “spins” as possible. An Ising system is a thermodynamic system modeled by a graph. Nodes or “spins” can take a state of +1 of -1 and edges receive weights. By designating some spins as “inputs” whose states can be locked in place and the others as “outputs” whose states are allowed to vary freely, the system computes the ground state with some probability. “Solving the Ising problem” for a given boolean function entails correctly choosing edge weights so that the ground states of the system are the outputs of the boolean function. Our team was given 8x8 multiplication as a target problem by the government.

Though it is impossible to solve the Ising problem for almost all Boolean functions, including multiplication functions, it can always be made possible by adding extra spins to the system. Any solution to this problem would naturally proceed therefore by a two step optimization process:

1. Add additional spins, obtain a linear problem
2. Attempt to solve the linear problem, score the result

There are two problems.

• Each pass of 2. requires solving a massive linear problem which grows exponentially every time a spin is added.
• The process of adding additional spins intelligently is a non-convex non-linear discrete optimization problem. The discrete nature of the spin values mean that gradient decent methods don’t work well, and the non-convexity means it is very easy to fall into a local minima.

Solving this problem would have been impossible without substantial mathematical insight. Research typically proceeded in a cycle of 2-3 days of experiment design to generate and test hypotheses, after which we spent 2-3 days on pen and paper math attempting to find exploitable properties from the mathematics. My proudest achievements include

• Producing a formal mathematical description of the Ising problem. When I arrived at the project, its statement was far more vague and particular to multiplication problems. Arriving at the correct mathematical formulation required generalizing far beyond the original goal and paved the way for all subsequent mathematical insights. In particular, this provides an incredibly quick way to solve the Ising problem using polynomial reduction techniques at the cost of adding far more than optimal additional spins.
• Circuit gluing. I found a way to “glue” Ising systems together in such a way that the resulting system is strictly more likely to be feasible. This idea came from the common algebraic theme in which objects are decomposed into simpler constituent parts.
• Formulating geometric interpretations. In order to solve the Ising problem algorithmically, one needs to drastically reduce its computational complexity. Even relatively simple geometric insights, viewing the state space of an Ising system as a hypercube for instance, led to huge algorithm improvements. It allowed us to reduce the problem scaling from exponential to quadratic scaling, isolate a tiny class of “good” circuits for use in the gluing approach and the discovery of “Ising symmetries” which further speed up solution searches by a factor of 8x to 32x depending on the problem.

I believe formal math yields superior insight into the nature of a problem, and I thoroughly enjoyed this project because it demonstrated precisely this. It’s an aid to creativity as it provides a flexible way to view a single problem from multiple angles – in this case, as an LP problem, a classification problem, or a polynomial reduction problem. However, as opposed to much pure mathematics research, the applied nature of this problem allowed for quickly prototyping and testing ideas. This proved enormously useful, as dead ends could be identified by showing them to be empirically ineffectual far faster than they could be useless using formal proofs. This interplay between empirical and formal methods is my favorite kind of research, and is exactly why I aim to leave pure math academia after the conclusion of my Ph.D.