On the Complexity of Quantum Languages

Elham Kashefi, Carolina Moura Alves

The standard inputs given to a quantum machine are classical binary strings. In this view, any quantum complexity class is a collection of subsets of $\{0,1{\}}^{\ast }$. However, a quan…