# Complexity of controlled operations in a two-level unitary operation

In Neilsen and Chuang, chapter 4.5.2 (~p.193), why did the authors come to the conclusion that complexity of operations $$C^n(X)$$ and $$C^n(\tilde{U})$$ is $$O(n)$$? Did they assume using work qubits? If so, then is it true that the complexity in terms of gates has nothing to do with the complexity in terms of space (amount of qubits) and thus, any number of additional qubits is allowed using this notation?

Without work qubits this result seems suspicious, since in exercises 4.29 and 4.30 a reader is supposed to find a circuit of complexity $$O(n^2)$$ using no work qubits:

• I think they have in mind a construction like the one in figure 4.10 on p.184 in section 4.3 "Controlled Operations", so yes it looks like they assume access to work qubits. Dec 12, 2020 at 6:40