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.