# How to calculate circuit depth properly?

Is the circuit depth the longest sequence of gates applied on one of the qubits? Or is it something more complicated?

The circuit depth is the length of the longest path from the input (or from a preparation) to the output (or a measurement gate), moving forward in time along qubit wires. The stopping points on the path are the gates, the allowed paths that must be considered can enter and exit those gates on any input / output, and the length is the number of jumps from each gate to the next gates along the path.

(When considering a unitary circuit, there is often a convention among theorists to ignore the final measurement in the count of the depth, which I actually provided in my original answer to this question. While it might not be entirely appropriate in the context of quantum technologies, this is something you may see here and there.)

Put another way: the depth is the smallest amount of time steps required to perform the circuit, if every gate (including each measurement and preparation) is performed at some integer time-step, gates which act on no common qubits are allowed to be performed at the same time-step, and gates acting on at least one qubit in common must act at different time-steps (and in the correct order of course). With a bit of work, it's possible to show that determining this smallest number of time-steps amounts to the first description that I give.

Practically speaking, this is best computed with dynamic programming, taking the circuit gate by gate and computing how each gate contributes to the length of the longest path that ends at a given qubit.

Example

Using the example provided by Hastings:

Here is how you can compute the circuit depth, adding one gate at a time, to compute the length of the longest path that ends at a given qubit.

1. Initialise the depth ending at each qubit to 0.

Init:       [0, 0, 0, 0, 0]

2. For each gate in sequence (consistent with the input/output dependencies of the gates), take the maximum depth $$d$$ to that point on all of the qubits on which the gate acts, add one, and set the new max-depth on those qubits to that result. (If you are considering a unitary circuit with final measurements, and for some reason you want to use the convention of ignoring the depth-contribution of the measurements, then just don't count the measurements.) In the case of the circuit above, this yields:

H 1:        [1, 0, 0, 0, 0]
H 2:        [1, 1, 0, 0, 0]
H 3:        [1, 1, 1, 0, 0]
CU^4 1 4 5: [2, 1, 1, 2, 2]
CU^2 2 4 5: [2, 3, 1, 3, 3]
CU^1 3 4 5: [2, 2, 4, 4, 4]
H 1:        [3, 2, 4, 4, 4]
CS 1 2:     [4, 4, 4, 4, 4]
H 2:        [4, 5, 4, 4, 4]
CT 1 3:     [5, 5, 5, 4, 4]
CS 2 3:     [5, 6, 6, 4, 4]
H 3:        [5, 6, 7, 4, 4]
Meas 1:     [6, 6, 7, 4, 4]
Meas 2:     [6, 7, 7, 4, 4]
Meas 3:     [6, 7, 8, 4, 4]

3. Take the maximum of the depths ending at each qubit. In this case, it is qubit 3, with a depth of 8. With a little bit of work, by tracing how this depth arose, you can also find one or more particular paths through the circuit which yields this depth (e.g. H 1 ; CU^4 1 4 5 ; H 1; CS 1 2; H 2; CS 2 3; H 3; Meas 3).

• Are you omitting the measurement gates from the depth calculation? I counted 8 layers (H,CU4,H,CS,CT,CS,H,M). – Craig Gidney Mar 26 '19 at 0:41
• @CraigGidney: I did omit them. This is an old convention from theoretical quantum computation, for computing the depth of unitary quantum circuits (without any intermediary measurements). The measurements are sort of considered "what one does with the quantum output" in that setting, so that cost is 'externalised'. But perhaps this is not an appropriate convention in the setting of quantum technologies. (Also, if we count the measurements and not the preparations, this makes 'depth' the number of time intervals, i.e. the length of the actual path through the circuit.) I'll edit my answer. – Niel de Beaudrap Mar 26 '19 at 9:55

It is the maximum time from input to output assuming all gates take 1 unit of time. So in this example:

Register 3 has 5 gates, but the 2nd gate (controlled-$$U$$) cannot be done until the controlled-$$U^4$$ and controlled-$$U^2$$ are done, so that adds 2 time steps. The controlled-$$T$$ can be done at the same time as the $$H$$, so there's no added time steps there. In total we have a gate depth of 7. If you include the measurement as a "gate", then the gate depth is 8.

• @NieldeBeaudrap: I had the same definition as you in mind, but didn't take the care to look at the circuit thoroughly. Is my modified answer correct now? I notice in your answer you got 8. Usually we talk about gate depth with asymptotic notation: for example, $\mathcal{O}(n^2)$ vs $\mathcal{O}(n)$ with respect to the size of the problem $n$. In this sense the measurement at the end doesn't matter. Is there a case where there's so many intermediate measurements that it actually changes the asymptotic notation? Maybe this deserves to be a separate question of its own. – Hastings Mar 27 '19 at 21:46
• Your answer is now correct. To answer your question: MBQC involves so many measurements that they make up a large constant fraction of all operations performed, and classically-controlled operations which depend on the outcomes essentially determine the depth, whether described asymptotically (ie. approximately, up to scalar factors, for a family of MBQC procedures) or exactly (eg. for a given specified MBQC procedure). – Niel de Beaudrap Mar 28 '19 at 19:18
• @NieldeBeaudrap: Thank you. As for measurements and asymptotics, I was thinking only about circuit-based quantum computation (CBQC), not MBQC. In my diagram, the measurements only happen at the end, but there's other circuits where measurements can happen in the intermediate stages of the computation; and there can be, as you mention, "classically-controlled" operations even in CBQC, so I wondered if there's any examples where measurements contribute to the asymptotics in CBQC! – Hastings Mar 29 '19 at 22:02
• If you allow intermediate measurements in your circuits, then MBQC is a subclass of CBQC (modulo the shallow circuit that would be required in CBQC to prepare the entangled state). – Niel de Beaudrap Mar 30 '19 at 0:42