5
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 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$
    – Adam Zalcman
    Commented Dec 12, 2020 at 6:40

0

Reset to default