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


4 Answers 4


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.


Using the example provided by Hastings:

      A short eigenvalue estimation circuit

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

  • $\begingroup$ Are you omitting the measurement gates from the depth calculation? I counted 8 layers (H,CU4,H,CS,CT,CS,H,M). $\endgroup$ Commented Mar 26, 2019 at 0:41
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Mar 26, 2019 at 9:55
  • $\begingroup$ Are the lines CU^1 3 4 5: [2, 2, 4, 4, 4] and H 1: [3, 2, 4, 4, 4] correct? Shouldn't they be CU^1 3 4 5: [2, 3, 4, 4, 4] and H 1: [3, 3, 4, 4, 4]? $\endgroup$
    – Eenoku
    Commented Mar 12, 2021 at 20:19

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

enter image description here

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.

  • $\begingroup$ @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. $\endgroup$
    – Hastings
    Commented Mar 27, 2019 at 21:46
  • $\begingroup$ 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). $\endgroup$ Commented Mar 28, 2019 at 19:18
  • $\begingroup$ @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! $\endgroup$
    – Hastings
    Commented Mar 29, 2019 at 22:02
  • $\begingroup$ 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). $\endgroup$ Commented Mar 30, 2019 at 0:42

It is hard to beat the animation present in the Qiskit documentation at https://docs.quantum.ibm.com/api/qiskit/0.42/circuit (and in the source tree here) where they describe depth finding as "playing Tetris" and which gives a good intuition about the algorithm:

enter image description here

This suggests the following algorithm:

  • create a linear list of all the gates as they are applied
  • merge gates into the lowest layer as much as possible as long as each gate does not touch a qubit already used up the the layer
  • when a gate arrives that already has one of its qubits used in the top layer, create a new layer and repeat

You can also use Qiskit, as described here:

The depth of a circuit is a metric that calculates the longest path between the data input and the output. Each gate counts as a unit.

That is, it's not just the longest sequence of gates on one qubit, but the number of gates that qubit relies upon (which includes gates of other qubits it interacts with).

In Qiskit, it can be calculated using QuantumCircuit.depth.

  • 1
    $\begingroup$ Even with this edit, it only describes in informal terms what depth is, not how to compute it. $\endgroup$ Commented Sep 19, 2020 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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