The following statement is found on the page 199 of Nielsen and Chuang's book (10th Anniversary Edition) in the proof for the fact that 'approximating arbitrary unitary gates is generically hard':

Suppose we have $g$ different types of gates available, and each gate works on at most $f$ input qubits. These numbers, $f$ and $g$, are fixed by the computing hardware we have available, and may be considered to be constants. Suppose we have a quantum circuit containing m gates, starting from the computational basis state $|0⟩^{\bigotimes n}$. For any particular gate in the circuit there are therefore at most$\binom{n}{f}^g=O(n^{fg})$ possible choices.

I kind of think the number of possible choices for any particular gate is more in line with $\binom{n}{f}\cdot g=O(n^fg)$. What do you think?


1 Answer 1


You are right. There is a choice for place and there is a choice for gate. Then we just multiply the number of choices.
But it's even stronger limitation on the number of possible states that we can obtain. So the general reasoning is still correct.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.