Universality is a foundational concept in quantum computation. However, what it means for a set of basic computational operations to be universal is a surprisingly subtle question. In this proposal, we will discuss the mathematical structures and complexity-theoretic implications of several notions of universality (and non-universality) in quantum computation. In particular we will discuss the decidability of universality in quantum computation and certain non-standard notions of universality, non-universal models of quantum computation, and finally some questions of interest in quantum compilation.
Chaitanya is a PhD student in the computer science department, advised by Daniel Gottesman. His main research interests are in quantum complexity theory, with a particular interest in understanding universality in quantum computation, and the complexity of restricted models of quantum computation. He also has an interest in quantum cryptography and quantum algorithms. Prior to UMD, he obtained his Bachelor's degree from Harvey Mudd college, and worked for a year at Sandia National Labs.