Ronak Ramachandran

We design a quantum algorithm to invert a permutation over N items using sqrt(N) in-place queries, and we identify some tasks requiring more in-place queries than standard XOR queries. 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 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. As you might intuitively expect, about N queries are necessary to solve this problem on average. With a quantum computer, however, the ability to query in superposition means 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 N 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.

This is my undergraduate Turing Scholar's Honors thesis. With guidance from Scott Aaronson and Jason Pollack, I extended their work in quantum gravity on the Discrete Bulk Reconstruction Problem. 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.