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.