How to calculate circuit depth properly?

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).