Ronak Ramachandran

Like a game of 20 Questions, the query complexity of a problem is the number of questions (queries) about the problem's input that must be answered to find a solution. Changing how we ask questions and receive answers, known as the query model, can sometimes change how many questions are needed. Consider the following problem in query complexity, called Permutation Inversion: a magician shuffles a deck of N cards numbered 1 to N. Your goal is to find the position of 1 using as few queries as possible, but you can only query by handing the magician a chalkboard with a number x which she returns after writing the value of the card at position x. Without a quantum computer, you might need N queries to solve this problem, since 1 could be the last card you check. However, with a quantum computer, it might matter how the magician responds. When she writes down her answer next to your query, that's called a standard XOR query. When she erases your query to write her answer, that's called an in-place query. Some problems are known to require far fewer in-place queries than standard queries, and before our work, no task was known to require more in-place queries than standard queries, seeming to suggest in-place queries are more powerful than standard queries. Despite this, researchers believed that standard queries might outperform in-place queries for some problems, and researchers conjectured that Permutation Inversion was an example. We refuted this conjecture by designing an algorithm for Permutation Inversion using √N in-place queries. However, we also came up with tasks that require far more in-place queries than standard queries, showing that the two query models are better suited for different tasks.

Imagine you're given a huge crossword. Because each clue could have many valid answers, solving the crossword might seem difficult, but if you were given a solved copy, you probably could check it pretty quickly. A central goal of theoretical computer science is to prove differences between the resources required to solve problems and the resources required to check their solutions. Proving a difference between what quantum computers can solve and what they can check has been an open problem for over 25 years. Unable to resolve this problem, some researchers began considering how a couple slight modifications to physics might affect the answer:

1. In quantum mechanics, observation is a destructive action: when we measure a quantum state, it changes. What if quantum computers could measure non-destructively?
2. Some early quantum physicists were unsettled by the idea that quantum measurement outcomes are probabilistic. To avoid this randomness, many argued for alternative laws of physics, called hidden variable theories, where perceived randomness was explained away by an underlying truth we could never access. What if quantum computers had access to the entire history of such an underlying truth?

Prior work establishes that the above modifications each only slightly improve how quickly quantum computers solve problems. In this work, we show that with these modifications, quantum computers quickly check problems that classical computers can't check quickly.

Quantum gravity is the study of possible ways to resolve inconsistencies between quantum mechanics and Einstein's theory of relativity. One well-studied approach shows how a D-dimensional spacetime with a certain kind of gravity, called the bulk, can be equated with a (D-1)-dimensional spacetime with a certain kind of quantum mechanics, called the the boundary. The Bulk Reconstruction Problem is the task of describing the bulk given information about the boundary. Aaronson and Pollack designed algorithms solving this problem in the special case when we think of the bulk and boundary as split up into discrete cells instead of being continuous spacetimes. I was skeptical that results in a discrete spacetime would carry over to "the real world" where spacetime is continuous, so in this thesis I attempted to make the work of Aaronson and Pollack more physical. I showed how careless choices can lead to strange unphysical bulks, but I also showed how carefully splitting spacetimes into cells can lead to discrete bulks with natural embeddings into continuous spaces.

In a year with fewer than half the usual number of NSF GRFP awardees, I was one of 3018 'Honorable Mentions' nationally recognized for outstanding achievements and potential to become a future leader in STEM.

I wrote this note to remind myself how:

1. single qubit unitaries form a Lie group (ignoring global phase),
2. Hamiltonians form the Lie algebra for that Lie group,
3. the Pauli matrices naturally arise as a basis for that algebra, and
4. representing Hamiltonians in this basis tell us a lot about their energy eigenstates.

See Lecture 25 of Scott Aaronson's lecture notes for a primer on Hamiltonians.

Introductory slides for a talk I gave on quantum error correction during an internship at IBM Quantum. Some slides refer to an unfinished survey I wrote on Bosonic codes.

Proposal for a project I worked on with Jonathan Pierce and Xuexin Wei attempting to design neurosecurity primitives.