Also, it is not quite clear to me, if you have n qubits, what operators Cn -> Cn a quantum computer is allowed to use, and what exactly counts as one time step for complexity purposes. --AxelBoldt
You are allowed to use single-qubit or two-qubit gates (i.e., operators that act like the identity on the rest of the space). (I don't think the complexity classes would change if we allowed gates with a fixed number of qubits higher than 2.) The action of one such gate counts as one time step. --Seb