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.

  • $\begingroup$ 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? $\endgroup$ – AHusain Mar 14 '20 at 23:40
  • $\begingroup$ The $U_i$ are black boxes with a given cost. Or is the thing I want not possible in this case? $\endgroup$ – Georg Mar 15 '20 at 11:05
  • $\begingroup$ 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. $\endgroup$ – AHusain Mar 15 '20 at 19:42
  • $\begingroup$ A course upper bound is ok $\endgroup$ – Georg Mar 15 '20 at 19:54

Your Answer

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

Browse other questions tagged or ask your own question.