# Cost of controlled-$U_i$

What is the cost (number of gates) of $$\sum_{i=0}^{N-1}| i \rangle \langle i|\otimes U_i$$ in terms of $$N$$ and the costs of the unitaries $$U_i$$? Say the gate set consists of arbitrary one-qubit gates and the CNOT. The unitaries $$U_i$$ act on an arbitrary number of qubits.

I know, for example, that the Toffoli gate, which is of the above form with $$N=4$$ and $$U_3=X$$, can be constructed with $$6$$ CNOTs.

• Do you wany to be fully polymorphic in the U_i? So you can't tell if there are simplifications from U_i=U_j or U_i=I etc, bc you only have them as black boxes? – AHusain Mar 14 '20 at 23:40
• The $U_i$ are black boxes with a given cost. Or is the thing I want not possible in this case? – Georg Mar 15 '20 at 11:05
• So the answer will be a coarse upper bound on the cost. You would need more information about the relations between the U_i if you want that upper bound to be tighter. – AHusain Mar 15 '20 at 19:42
• A course upper bound is ok – Georg Mar 15 '20 at 19:54