Hello, on BQP/Talk I asked the question about how many qubits a quantum computer is allowed to use, and the answer seemed reasonable to me. Should we incorporate that somewhere in the main articles about quantum computers?
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