about me

Using the jargon, my two main lines of work are in quantum learning theory and dequantized or quantum-inspired algorithms for machine learning.

Some broad motivating questions for me are: How can we evaluate promising applications of quantum computers? How can we design algorithms for understanding nature? and When is engineering a big quantum system tractable?

For more, see my [research] and [teaching] statements.

The most famous quantum algorithms can all be distilled into subroutines that work with unitary oracles.

• Shor’s algorithm uses phase estimation;
• Grover’s algorithm uses amplitude amplification;
• Hamiltonian simulation and the HHL algorithm use quantum singular value transformation.

To elaborate, these subroutines are “circuits with empty slots”: they take as input a black-box circuit which implements a unitary matrix \(U\), with the guarantee that, upon plugging in the black box into the slots of the circuit, the subroutine will output something useful about \(U\). Annoyingly, the “slots” are slightly different for each algorithm: some algorithms require only the circuit for \(U\); others require the inverse circuit, \(U^\dagger\), and still others require the controlled circuit, \(\mathrm{c}U\). I’ve been interested in figuring out, why is this the case? Do you really need these different forms of access to perform these tasks? And when are these different forms of \(U\) truly helpful?

In a series of works with John Wright (1) (2) and (later) Mark Zhandry (3), we look into these questions and get some satisfying resolutions. Our investigations started off mostly as expected: yes, these canonical algorithms really do need the kinds of access that they need. But as we investigated deeper, we found more and more instances of algorithms not needing the kinds of assumptions that they purport to, eventually culminating in the discovery of the random purification channel and a broader principle which we call the “acorn trick” (don’t ask why).

The existence of the random purification channel is easy to state and straightforward to prove, but a little hard to believe: there is an efficient quantum circuit which maps \(n\) copies of a quantum mixed state \(\rho\) to \(n\) copies of a random purification of \(\rho\), \(\operatorname{E}_{\ket{\rho}}[\ket{\rho}\bra{\rho}^{\otimes n}]\). Purification is a useful tool, but it’s been known for a long time that such an operation is “unphysical”, with various no-go theorems ruling out types of algorithms for purification. However, we showed that random purification is possible, dodging these barriers. The channel has since been used to simplify and resolve a bunch of questions in quantum learning, algorithms, and information. Here are some examples that I’ve been a part of (4) (5) and some I haven’t (6) (7) (8).

Perhaps the most exciting application of quantum computers is simulating quantum systems that are too large and complicated for ordinary super-computers. The consensus among experts is that they should be able to do this in at least some cases, but there’s less concrete evidence for this than you’d think. Since quantum computers are still a bit too small to experimentally test this claim, we’d really like theoretical evidence that quantum computers can indeed simulate interesting systems that classical computers can’t. However, the features that make these systems hard for classical computers also make them hard to understand and analyze.

I’ve been thinking about various questions in this space, to understand both algorithms for quantum systems as well as the quantum systems themselves. These can go hand-in-hand: see my papers with Ainesh Bakshi, Allen Liu, and Ankur Moitra (1) (2) (3). My favorite is the first paper, which gives a sampling-to-counting reduction for locally interacting quantum spin systems at high-temperature (think quantum generalizations of the Ising model on a lattice). Such reductions had been considered before, but our reduction is strong enough that we can show that such systems exhibit zero entanglement. Our dramatic name for this is the “sudden death of thermal entanglement”, because entanglement drops to literally zero at a finite temperature, as opposed to tending to 0 but never reaching it. This was a shocking result to us, because entanglement of mixed states is quite mysterious, and there weren’t techniques before ours for giving such a strong bound. But now we have nice tools to study at which temperature a model become entangled: see (4) and (5) for follow-ups in this vein, and (6) (7) (8) for investigations of these thresholds for other models.

In undergrad and grad school, I spent a lot of time thinking about quantum machine learning/quantum linear algebra algorithms, and whether, in futures with working quantum computers, they could be faster than classical (i.e. non-quantum) algorithms. Many papers in the literature conjectured massive exponential speedups, but all of these proposals had to contend with the cost of loading data. If just getting the data into the quantum computer is too expensive, it ruins the speedup, and for most data, it is just too expensive. To address this, researchers assumed that the input data was pre-processed into a data structure that supports efficient loading into the quantum computer. However, it wasn’t clear whether this pre-processing made the problem “too easy”: if a classical algorithm is also allowed pre-processing, can it match the quantum algorithm in speed?

I showed that the answer is yes: most of these quantum machine learning proposals do not give their desired exponential speedup (1) (2); see also (3) and (4) for more of my writing on the topic. In particular, given its input in the same data structure as the quantum algorithm uses, a classical algorithm can perform constant-time importance sampling on the input, allowing it to access the “important” parts of the data efficiently. It’s easy to see that the data structure supports importance sampling, but at the time, it wasn’t so clear that this observation was useful. In fact, this observation allows us to bring to bear the massive literature on classical “sketching and sampling” algorithms and, in this odd “quantum-inspired” regime, get super-fast algorithms for a variety of linear algebraic tasks.

My favorite aspect of this work is that our theory of “quantum-inspired linear algebra” has pleasant compositional properties. We show that, if you can importance sample from input matrices, then provided these matrices are sufficiently low-rank, then you can importance sample from any polynomial of these matrices in constant time. This is a direct classical analogue of the algorithm framework of quantum singular value transformation, which has similar compositional behavior (replacing the words “importance sample” by “prepare quantum states”). I’m not aware of similar ideas in randomized numerical linear algebra, but it also reminds me of classical sampling work on Bernoulli factories.