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)$? enter image description here 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: enter image description here

  • 1
    $\begingroup$ 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. $\endgroup$ Dec 12, 2020 at 6:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy