2
$\begingroup$

Since gate complexity correspond to the number of gate for a given quantum circuit, it seems that depth complexity bring no more information about quantum complexity than gate complexity. So does gate complexity encompass depth complexity ?

$\endgroup$
1
$\begingroup$

Circuit depth matters because qubits have finite coherence time. You could imagine two circuits, each with $N$ gates, where the first circuit can implement them all in parallel and thus finish in one time-step, where the other must implement them in series, necessitating longer coherence of the physical qubits. Thus, the gate count alone only tells you how the fidelity might degrade as a function of gate error, and the context of the gates relative to each other and the underlying hardware will determine the circuit depth.

Depth complexity is not totally independent from gate complexity, because a circuit with a large number of gates is likely to have large depth as well, but this is only qualitative. When gates cannot be performed in parallel, they contribute to the total depth of the circuit. This might occur because two sequential gates act on a shared qubit, but could also result from two gates that, though logically independent, rely on shared classical resources (multiplexed drive or readout lines). Thus, circuit depth can increase due to both the algorithm's structure and the physical limitations of the hardware. As an example, this paper discusses how to optimally map logical to physical qubits when compiling quantum circuits onto hardware with restricted connectivity. The algorithm presented by the authors can trade off circuit depth and gate count. To execute the circuit labeled "code" (top left), you can either insert 4 SWAP gates that can all run in parallel, or instead only use 3, but they will need two time-steps. If your qubits have pretty good coherence times but poorly-calibrated gates, you should go with the latter solution, and v.v.

enter image description here

$\endgroup$
0
$\begingroup$

Great answer by chrysaor4! To give another example: implementing Toffoli gates in a fault-tolerant quantum computer. The most time-consuming gate to implement in a fault-tolerant setting will be the T gate [1]. Therefore if you can run T gates in parallel when possible, that could help save a lot of time. Below are 2 different ways to implement a Toffoli gate (taken from this paper) which both have a T-count of 7 but different T-depths. The paper has many more examples, so if you are interested in this kind of stuff I would highly recommend having a quick look through the paper!

enter image description here

[1] This is because it is the only non-Clifford gate required to make a universal fault tolerant computer. For a short explanation, I would recommend reading the first three paragraphs of the introduction section in https://quantum-journal.org/papers/q-2019-04-30-135/

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.