# Is the complexity of a quantum circuit constant in the depth of the circuit?

Take a quantum circuit on $$n$$ qubits, you have some sequence of gates.

You can represent these gates as hermitian matrices, and then with some padding, you could take the product of these matrices, by closure would be a hermitian matrix, a quantum operation. Then you have who knows how many gates into one single, but complicated $$n$$-ary gate.

On a perfect fidelity machine, this could be o(1) right. Does this logic make sense? I feel like it shouldn't be independent of the depth, or a lot of classical circuit problems become constant time on a QC.

The same could be said about any classically computable function. We could use the Cook-Levin theorem to unroll any Turing machine into a single but complicated $$n$$-input gate, and then claim it's $$o(1)$$.
Thus because we don't want this silly exception, usually when speaking of $$\mathrm{BQP}$$ or $$\mathrm{P}$$ in a circuit model, we have to limit our gate set (to, say, NAND gates classically and Hadamard/CCNOT gates quantumly).
Further we should put in a uniformity condition: given $$n$$ you'll need a Turing machine to provide the requisite quantum circuit (classical circuit) in polynomial time.
• I'm not familiar with the U3 gate, but I'm not sure I believe or understand the statement "some unary operations might take more than a few steps, when in the real world using the U3 gate, it takes one step". Perhaps you are asking about a single rotation gate being able to apply a rotation of a qubit about an arbitrary angle, in which case the Solovay-Kitaev theorem states that a single qubit gate (a unary gate in your language) generates a dense subset of $\mathrm{SU}(2)$ efficiently. But that says nothing about $n$-ary ($n$-input) gates. Apr 30 at 19:01