My primary research focus at the moment is in quantum complexity theory. In general, I am presently interested in persuing research that explores the nature of the "landscape" between quantum and classical computation, by way of the algebraic structures manifested by quantum computation in various kinds of computational models.
Beyond quantum complexity theory, I have several research interests more broadly in the union of computer science, quantum foundations, and pure mathematics. There is a more-or-less complete list of my published works here.
Below are descriptions of some of the questions that I'm currently interested in. Please note however, this account of my research interests need not be taken as representative; many problems that are even tenuously related to these topics are likely to catch my interest nonetheless! Furthermore, I'd also recommend taking a look at the website of my friend and colleague Matthew Fox; we are interested in many of the same things, and I could safely endorse my interest in most (if not all!) of the problems he has indicated there as well.
At a high level, this question can be phrased quite simply: which sets of gates are universal for quantum computation?
In quantum computation, there are many notions of universality that we can adopt. One of the most standard and useful definitions is what we may call "approximate universality", wherein a set of quantum gates \( \mathcal{G} \) is said to be universal if for any unitary \( U \) and error \( \epsilon \), there exists a circuit
over \( \mathcal{G} \) that realizes a unitary \( U_{\epsilon} \) such that \( \lVert U - U_{\epsilon} \rVert_{sup} < \epsilon. \) Note that here, importantly, we characterize the "closeness" of two unitaries in operator norm. Though there remain interesting open questions regarding criterion for the realization of approximate universality in quantum gatesets,
a good deal is also known. For example, it is known that if \( \mathcal{G} \) is approximately universal for all single-qubit unitaries, and \( \mathcal{G} \) contains any entangling gate, then \( \mathcal{G} \) is approximately universal at large.
However, there is an argument to be made that approximate universality, while very natural and useful to reason about, is in fact too strong a notion of universality. In particular, whenever a quantum circuit is implemented to solve a given computational task, the solution given is not inherently due to the unitary realized by the circuit, but is rather due to the statistical distribution realized at the end of the circuit.
This observation suggests that even if a given gateset \( \mathcal{G} \) cannot approximate an arbitrary unitary \( U \) to arbitrary precision, so long as it can realize a unitary \( U_\epsilon \) whose output distribution is within arbitrary statistical distance to the output distribution of \( U \), then \( \mathcal{G} \) still ought to be considered universal, at least for computational tasks. Appropriately, we refer to this notion of universality as "computational universality."
A nice example of a computationally universal (but not approximately universal) gateset (due to Shi), is \( \{ \text{CNOT}, V \} \), where \( V \) is any real single-qubit gate which does not preserve the computational basis when squared (essentially so long as \( V \) is not a Hadamard gate).
We naturally ask then, which sets of gates are computationally universal for quantum computing? And more precisely, how might the emergence of computational universality in quantum gatesets be mathematically characterized?
It is generally suspected that quantum computers can outperform classical computers for certain computational tasks. This belief is perhaps most significantly encapsulated by the mathematical conjecture that \( \mathsf{BPP} \subsetneq \mathsf{BQP} \), where, roughly, \( \mathsf{BPP} \) is the set of computational tasks solvable in polynomial time with classical computers (with bounded error), and \( \mathsf{BQP} \) is the same set but with quantum computers.
Like the notorious \( \mathsf{P} \neq \mathsf{NP} \) conjecture, the \( \mathsf{BPP} \neq \mathsf{BQP} \) conjecture has stubbornly evaded all formal attempts of proof for decades. Thus, despite the corpus of evidence in favor of \( \mathsf{BPP} \neq \mathsf{BQP} \), there is at present no concrete proof of this claim.
Given this resistance, there is an interest in the study of restricted computational models. These models of computation are designed to be restricted in a manner that they are certainly not universal for quantum computation,
and yet there exist very strong complexity theoretic arguments to suggest that these models are also not tractable by classical computation; i.e., these models cannot generally be efficiently simulated by a classical machine.
Interesting examples of these restricted models include conjugated Clifford circuits (Bouland et al.), commuting quantum circuits (Bremner et al.), and constant-depth quantum circuits (Terhal et al.).
While several such restricted models of quantum computation have been developed, relatively little is known about how these various models relate to each other.
One of my main research interests is to develop the understanding of known restricted models, studying the hardness of some of their generalizations, and understanding how they might compare to each other.
For example, along with my friend and collaborator Matthew Fox, I have been especially interested in studying various kinds of "perturbed" Clifford circuits,
which include conjugated Clifford circuits as a special case, and understanding their complexity. Additionally, we are also very interested in exploring the complexity of constant-depth quantum circuits, and more generally, parallelizable quantum circuits. There are several very tantalizing questions that manifest in the regime of such restricted models as constant-depth quantum circuits; for instance, one simple question is to ask whether the class of problems solvable on constant-depth quantum circuits (denoted \( \mathsf{QNC}^0 \) ) is robust to changes in the underlying universal gateset?
Note, it is not at all clear that it should be, and in fact optimal circuit compilation algorithms suggest that it might not be, since these require at least logarithmic depth.
Ramsey theory is a branch of mathematics that studies the "forced" emergence of particular kinds of structures. At a high level, I rather like the informal description of Ramsey theory given by Landman and Robertson:
Ramsey theory is the study of the preservation of properties under set partitions. In other words, given a particular set \( S \) that has a property \( P \), is it true that whenever \( S \) is paritioned into finitely many subsets, one of the subsets must also have property \( P \)?There are lots of different problems that are Ramsey theoretic in flavor concerning a remarkable plethora of mathematical structures. One of the most fundamental though is in graph theory; here Ramsey-type problems often manifest in questions about edge colorings. For example, a standard "party problem" question asks how many people must be at a party in order to be certain that there must always exist a group of 4 people who are all mutual friends or all mutual strangers (assuming that any two people are either friends or strangers)? This question can be stated more formally in terms of colorings on graphs, asking what is the minimal \( r \) such that any \(2\)-coloring of a \( K_r \) admits a monochromatic \( K_4 \) as a subgraph? Here the value of \( r \) is one of the "diagonal" Ramsey numbers. While the answer to this question is known, in general, the Ramsey numbers are incredibly difficult to compute: for example, the value of the next diagonal Ramsey number, asking for the minimal value of \( r \) such that any \(2\)-coloring of a \( K_r \) admits a monochromatic \( K_5 \) as a subgraph is unknown (but it is known that \( 43 \leq r \leq 48 \)).
In 1918, Srinivasa Ramanujan introduced the exponential sums given by \{c_q(n) = \sum_{k \in (\mathbb{Z} / q\mathbb{Z})^\times} e^{2\pi i k n / q}.\} These sums, which have come to be known as Ramanujan sums have several remarkable properties, including that they are integer valued on integer inputs, and that they are multiplicative in the index \( q \). However, one property
of particular interest to me is that several important arithmetic functions can expressed very cleanly as a linear combination of Ramanujan sums.
For example, given a positive integer \(n\), let \{\sigma_k(n) = \sum_{d \mid n} d^k\} be the sum of the \( k \)th-power of the divisors \(d\) of \(n\). The divisor functions have a beautiful expansion in terms of Ramanujan sums:
\{\sigma_k(n) = n^k\zeta(k + 1) \sum_{q \geq 1} \frac{c_q(n)}{q^{k + 1}}.\} Note though, that the form of the right hand side expression above suggests an interesting possibility: there is no particular necessity that \( n \) be an integer. While it is not at all obvious what it would mean to compute the "sum of the divisors of \( \pi \)," using the Ramanujan expansion you could sensibly assign a value of the function at \( \pi \). More precisely,
the Ramanujan expansion of \( \sigma_k(n) \) can be extended to an function that analytically interpolates \( \sigma_k(n) \) to the whole real line (and in fact to the upper-half of the complex plane). Showing that this works requires a bit more thought, for example it needs to be verified that the Ramanujan expansion actually converges at non-integer values; I explored some related questions with my friend and colleague Matthew fox here.
In general though, the possibility of using Ramanujan expansions of arithmetic functions to systematically realize analytic analgoues of those functions presents a tantalizing possibility for imposing analytic structure on otherwise highly discrete mathematical objects. Conisder, for example, the miryad open questions surrounding the perfect numbers. Recall that an integer \(n\) is said to be perfect
if and only if \(\sigma_1(n) = 2n\). The first four perfect numbers are 6, 28, 496, and 8128 (sequence A000396 in OEIS
). The perfect numbers are the subject of many fascinating open questions; the most famous of these was presented by Euclid, who conjectured that all perfect numbers are even.
While we don't expect to resolve the open questions surrounding the perfect numbers, it appears nonetheless to us to be interesting avenue of research to use Ramanujan expansions like this to try to interrogate their structure. More broadly, our hope is that Ramanujan expansions of arithmetic functions can be worked into a useful mediator, through which the tools of complex analysis might be brought to bear in order to gain a better understanding of the structure of certain arithmetic functions, which might be challenging to engage with otherwise. We have also spent time exploring applications of Ramanujan interpolations (as we have dubbed them) towards making progress on Lehmer's conjecture on Ramanujan's Tau function, and other related open problems (for example, understanding when \( \tau(n) > 0 \)). We have a fair bit of unpublished work on this topic, which we hope to complete and publish soon.