Definitions of a quantum circuit's depth and connectivity

Question

The quantum circuit model of computation uses wires and gates. The information flows along the wires and gates attached to the wires modify the information and pass it further down the wires.

In quantum computing, people often talk about circuit depth and circuit connectivity. While I have an intuitive understanding of both, I cannot find the formal definitions of these concepts. Does anyone know the formal definition of circuit depth and connectivity?

Below is a handwavy explanation of depth given in the book "An Introduction to Quantum Computing" by Kaye, Laflamme and Mosca:

If we visualize the circuit as being divided into a sequence of discrete time-slices, where the application of a single gate requires a single time-slice, the depth of a circuit is its total number of time- slices. Note that this is not necessarily the same as the total number of gates in the circuit, since gates that act on disjoint bits can often be applied in parallel.

While it is somewhat clear what they mean here it is not the definition. One of my colleagues casually mentioned the "longest path" in the circuit as a measure of depth, though they did not attempt to give a formal definition. The connectivity in the circuit is even less clear to me, let alone trying to come up with a formal definition of the concept.

Just to summarize. I would like to know if the notion of circuit depth and connectivity were ever formally defined in some literature.

Edit: Niel de Beaudrap gave the definition of the circuit depth

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.

No luck with the definition of the circuit connectivity , so far.

Answer 1

The traditional definitions of classical Boolean circuits work perfectly well here: https://en.wikipedia.org/wiki/Boolean_circuit. This is the definition that gives you Niel de Beaudrap's definition.

The unfortunate part of the circuit model here is that you can have as many output wires as you want for free, i.e., it doesn't track memory. You can avoid this by allowing only one outgoing edge from each vertex, and requiring all quantum gates to have the same number of input edges as output edges. For example, a Toffoli gate would have 3 inputs, but also 3 outputs.

This gives you two properties:

(1) you don't really need to account for "time slices" because it's baked in: you can't apply 2 gates to the same qubit at the same time because that would correspond to two outgoing edges on the same vertex.

(2) you now have persistent qubit labels. That is, each input vertex (representing a specific physical qubit) will have at most one outgoing edge, so give each edge a label $q_i$. For each quantum gate you can define a bijection from input edges to output edges, which defines what label each outgoing edge will get based on the label of the input edge, so that the output edges will continue to represent qubits. (e.g., an $X$ gate has one input, so if the incoming edge has label $q_i$, the outgoing edge will also have label $q_i$. A CNOT has 2 inputs, so you should define the mapping to appropriately track control/target qubits).

(incidentally, the graph defined above will now look exactly like a quantum circuit diagram, as long as the vertices are drawn as rectangles).

So far, all we've done is restrict the definition for boolean circuits, just to better account for reversibility/etc.

Then to define "connectivity" you restrict your gate set further, so that multi-qubit gates can only apply to certain qubits. For example, maybe you say that only qubits with sequential labels can be inputs to the same 2-qubit gate, so $(q_1,q_2)$ could be input to a CNOT but $(q_1,q_3)$ could not.

For this, you often define another graph that represents the physical layout of the qubits (e.g., a 2-d grid). Each vertex in this graph is a qubit (so you would need a bijection from your labels on the circuit graph to vertices in this graph). Each edge represents a possible interaction, so you restrict 2-qubit gates so that the labels of their inputs must correspond to an edge in the physical layout graph.

I leave it up to you if you want to formalize this with symbols and set-builder notation (e.g., a quantum circuit with connectivity $\Gamma$ is a graph $G$ such that for all vertices in $G$...).

You can modify this definition a bit more to account for, e.g., classical computations. For example, you could label edges as "classical" and "quantum", add rules to each gate so that it only takes a classical edge for classical inputs and quantum edge for quantum inputs, and then the classical edges don't need to obey the rules on incoming/outgoing edges.

Answer 2

Let me try to provide a more precise definition of connectivity in a quantum circuit.

Every quantum circuit defines a graph (network), with vertices (nodes) given by qubits. There is an edge $q_1 q_2$ if, for some timeslice $t$, there is a gate which acts nontrivially on both $q_1$ and $q_2$. The connected components of the graph tell you which groups of qubits are connected in the circuit, and can therefore "talk" to each other.

One might also like to prove that two equivalent circuits have the same connectivity under this definition, but I think this is true. Circuit depth does depend on representation, however, hence the importance of good circuit transpilers!

Answer 3

I would like to give explicit definitions of the circuit depth and connectivity. I assume that the meaning of terms like vector state, quantum circuit, wires, and 1- and 2-qubit gates is understood.

I'll start with the circuit depth. Essentially, I formalize the handwavy explanation given in "An Introduction to Quantum Computing" by Kaye, Laflamme and Mosca.

Definition 1 (Time step) A time step is a single application of the maximum number of gates on a state vector such that all applied gates can be executed in parallel and simultaneously.

With the notion of a time step, it is now possible to define circuit depth which is equivalent to the definition involving the longest path in a circuit given here

Definition 2 (Circuit depth) The depth of a circuit is the maximum number of consecutive time steps necessary to execute a circuit.

I now define the circuit connectivity. For this, I rework the definition of graph connectivity.

Definition 3 (Circuit connectivity) The connectivity of a circuit is the minimum number of 2-qubit gates that must be removed to separate wires in two or more independent groups of wires.

While not ideal, these definitions are concise and are based on the graph-theoretical concepts and explanations given by the aforementioned book authors.

Also, using Definition 3 it is easy to define such things like "all-to-all connectivity". E.g. A circuit with $n$ wires has an all-to-all connectivity if its connectivity is $n-1$.