Can we think that any multi-qubit quantum gate has a constant complexity from physics perspective?

Question

It's known that any multi-qubit quantum gate can be represented as a product of a number of CNOT and single-qubit gates. The total number of these simple gates required is exponential (in the number of qubits) on average, and thus we can say that an average complexity for a random gate is exponential. Thus, there can be a big difference between some two multi-qubit gates. But this is just from one perspective.

In reality a quantum gate is a physical device. Why, from physics perspective, one quantum gate should be more complex than another one?

As an analogy, think of the distinction between classical CPU and specialized hardware, like FPGA, ASIC, GPU, TPU, LPU, etc. Specialized hardware is much faster for specific tasks, while they are not supposed to be universal computing devices like CPUs.

So, would it be possible for a random quantum gate to physically construct a device that will compute it with a speed comparable to, say, the computation of the Walsh-Hadamard gate?

Perhaps, this question sounds more reasonable when we have just one quantum system with $d$ degrees of freedom and look for a complexity of a random unitary acting on it.

Answer 1

(too long for a comment)

I'm trying to analogize this question to other, classical things that I know about. For example, in the early days of (classical) integrated circuit computing we had resistor-diode logic - which was not universal at least because we were limited to AND and OR gates. So we upgraded to resistor-transistor logic (RTL) initially using NPN (or PNP) bipolar transistors; this was succeeded by diode-transistor, then transistor-transistor, and finally complimentary metal-oxide transistor technology used in the majority of classical processors nowadays.

CMOS has an advantage because, for example, a two-input NAND gate can be realized with "just" four transistors. But a two-input XOR gate needs eight such transistors. While a three-input "AND-OR-INVERT" gate can be realized with fewer than the naive guess of ten such transistors.

But (classical) computer engineers will just take it as they come - we don't ponder too much why the AOI gate is less complex than the XOR gate (but we want to use AOI gates where we can, for efficiency purposes...)

Answer 2

Why, from physics perspective, one quantum gate should be more complex than another one?

The average gate has to be extremely complex to implement, because there are so many possible gates. Consider that there are 31446995505814020383166371418359014222725120000 different 8-qubit Clifford gates. Every one of those gates will require a different implementation. The implementation strategy needs to have enough details that you can encode that many differences, and this inherently makes the implementation strategy complex. But then there will be outlier gates, like single qubit rotations, that we see in practice are much easier than this.

In order for all gates to have the same cost, it would need to be the case that the easiest gate to implement was as hard as the average gate. But the average gate is necessarily totally miserable to implement, and the easiest gates just don't look like that. There are approximately $10^{150000}$ thousand-qubit stabilizer states. So to prepare the average stability state you'd need hundreds of thousands of knobs you can twiddle, just to ensure you have enough degrees of freedom to specify them all. On the other hand, one of those states is "each qubit in the $|0\rangle$ state", which you can prepare by just waiting a millisecond for all the qubits to T1 decay into the $|0\rangle$ state. It's very hard to not have outliers that are easy.

More generally, the gate you're trying to perform can look more/less like physics. For example, physics is local and the gate may also be local; that'll make it easier to do. Physics is mostly built out of two-body interactions, so if the gate only requires interactions between pairs of qubits instead of all-to-all interactions, the gate will be easier to do. Etc.