  In this paper we introduce quantum Latin squares, combinatorial quantum
objects which generalize classical Latin squares, and investigate their
applications in quantum computer science. Our main results are on applications
to unitary error bases (UEBs), basic structures in quantum information which
lie at the heart of procedures such as teleportation, dense coding and error
correction. We present a new method for constructing a UEB from a quantum Latin
square equipped with extra data. Developing construction techniques for UEBs
has been a major activity in quantum computation, with three primary methods
proposed: shift-and-multiply, Hadamard, and algebraic. We show that our new
approach simultaneously generalizes the shift-and-multiply and Hadamard
methods. Furthermore, we explicitly construct a UEB using our technique which
we prove cannot be obtained from any of these existing methods.
