I'm looking for just a few simple calculations to analyze complexity when comparing quantum circuits.
I'll compare 2 scenarios, and I'd love for someone to critique or verify my analysis:
Circuit of width "n", and one multi-qubit gate that involves all "n" of the qubits. (e.g. a MCT gate, in which the target qubit is an ancilla).
Circuit also of width "n", but with a single qubit gate on each of the "n" wires. (e.g. a simple NOT gate)
Comparing the complexities of the above:
Tensor product of "n" qubits, so in worst case $O(2^n)$.
$O(2)$ for each single qubit gate, so in worse case $O(2n)$.
Therefore, for the same computation time, I can apply $\frac{2^{n-1}}{n}$ layers of circuit 2) instead of applying circuit 1). Is this correct?
I realize there are a few questions out there about this, but the ultimate goal is to compare whether decompositions of MCT will provide any benefit (and if so under what scenarios).
