mimiqcircuits.dag

Directed-acyclic-graph view of a Circuit.

A circuit is stored as a flat list of instructions, but its true ordering constraints form a partial order: two instructions must keep their relative order only when they share a wire (a qubit, a classical bit, or a z-variable). CircuitDAG captures that partial order as a dependency graph, which lets callers iterate a circuit in orders other than the literal insertion order — for example grouping mutually independent gates into layers.

The vertices are instruction positions and an edge u -> v records that v depends on the most recent earlier instruction u acting on a shared wire.

Functions

build_dag(circuit)

Build the CircuitDAG of circuit.

to_networkx(circuit)

Return the circuit's dependency graph as a networkx.DiGraph.

topological_sort_by_bfs(dag)

Return the vertices of dag in breadth-first topological order.

topological_sort_by_dfs(dag)

Return the vertices of dag in depth-first topological order.

traverse_by_bfs(circuit)

Yield the instructions of circuit in breadth-first topological order.

traverse_by_dfs(circuit)

Yield the instructions of circuit in depth-first topological order.

Classes

CircuitDAG(n)

Dependency graph of a circuit's instructions.

class CircuitDAG(n)[source]

Bases: object

Dependency graph of a circuit’s instructions.

Vertices are the integer positions 0 .. n-1 of the instructions in the circuit. An edge u -> v means instruction v depends on instruction u: they touch a common qubit, bit, or z-variable and u is the most recent earlier instruction on that wire. Only the immediate predecessor on each wire is linked, so the graph is the transitive reduction along wires rather than a dense reachability graph.

The graph is normally obtained from Circuit.dag(), which builds it on first use and caches it. CircuitDAG(n) creates a graph with n vertices and no edges.

Parameters:

n (int) – The number of vertices.

Raises:

TypeError – If n is not an integer, for example a circuit.

Examples

>>> from mimiqcircuits import *
>>> c = Circuit()
>>> _ = c.push(GateH(), 0)
>>> _ = c.push(GateH(), 1)
>>> _ = c.push(GateCX(), 0, 1)
>>> _ = c.push(GateX(), 0)
>>> dag = c.dag()
>>> dag
CircuitDAG(vertices=4, edges=3)
>>> # the CX (instruction 2) waits for both H gates
>>> dag.in_neighbors(2)
[0, 1]
>>> # the X on qubit 0 only depends on the CX
>>> dag.in_neighbors(3)
[2]
num_vertices()[source]

Return the number of vertices, that is the number of instructions.

num_edges()[source]

Return the number of dependency edges.

vertices()[source]

Return the vertex indices, as range(num_vertices()).

edges()[source]

Return the list of edges (u, v), with u before v in the circuit.

out_neighbors(v)[source]

Return the vertices that depend directly on v (its successors), sorted.

in_neighbors(v)[source]

Return the vertices that v depends on directly (its predecessors), sorted.

in_degree(v)[source]

Return the number of direct predecessors of v.

out_degree(v)[source]

Return the number of direct successors of v.

has_vertex(v)[source]

Return True if v is a vertex index of the graph.

has_edge(u, v)[source]

Return True if the graph has the edge u -> v.

build_dag(circuit)[source]

Build the CircuitDAG of circuit.

Each instruction is linked to the last earlier instruction on each of its qubits, bits and z-variables. The result holds exactly the orderings that must be kept for the circuit to stay equivalent. Amplitude, BondDim, SchmidtRank and VonNeumannEntropy depend on the whole state, so they are linked as if they acted on every qubit.

Circuit.dag() calls this and caches the result; use that instead.

Returns:

The dependency graph.

Return type:

CircuitDAG

topological_sort_by_bfs(dag)[source]

Return the vertices of dag in breadth-first topological order.

The order is built layer by layer with Kahn’s algorithm: first every vertex with no predecessor, then every vertex whose predecessors are all in the first layer, and so on. The first layer comes in increasing index order, and each later vertex is added when its last predecessor is visited, so the result is deterministic.

Parameters:

dag (CircuitDAG) – The graph, usually from Circuit.dag().

Returns:

Every vertex once, each after all its predecessors.

Return type:

list of int

Raises:

TypeError – If dag is not a CircuitDAG.

Examples

>>> from mimiqcircuits import *
>>> c = Circuit()
>>> _ = c.push(GateH(), 0)
>>> _ = c.push(GateX(), 0)
>>> _ = c.push(GateH(), 1)
>>> # the two H gates form the first layer, the X the second
>>> topological_sort_by_bfs(c.dag())
[0, 2, 1]
topological_sort_by_dfs(dag)[source]

Return the vertices of dag in depth-first topological order.

The order is the reverse post-order of a depth-first search. It follows one chain of dependencies as far as possible before moving on, so an instruction and the ones that depend on it tend to stay close together.

Parameters:

dag (CircuitDAG) – The graph, usually from Circuit.dag().

Returns:

Every vertex once, each after all its predecessors.

Return type:

list of int

Raises:

Examples

>>> from mimiqcircuits import *
>>> c = Circuit()
>>> _ = c.push(GateH(), 0)
>>> _ = c.push(GateX(), 0)
>>> _ = c.push(GateH(), 1)
>>> topological_sort_by_dfs(c.dag())
[2, 0, 1]
traverse_by_bfs(circuit)[source]

Yield the instructions of circuit in breadth-first topological order.

Instructions come out layer by layer, as in topological_sort_by_bfs(): all instructions that can run at the same time are yielded one after the other. Pushing them in this order gives an equivalent circuit.

Parameters:

circuit (Circuit) – The circuit to traverse.

Yields:

Instruction – The instructions of the circuit, each once.

Examples

>>> from mimiqcircuits import *
>>> c = Circuit()
>>> _ = c.push(GateH(), 0)
>>> _ = c.push(GateX(), 0)
>>> _ = c.push(GateH(), 1)
>>> list(traverse_by_bfs(c))
[H @ q[0], H @ q[1], X @ q[0]]
traverse_by_dfs(circuit)[source]

Yield the instructions of circuit in depth-first topological order.

The order is that of topological_sort_by_dfs(). Pushing the instructions in this order gives an equivalent circuit.

Parameters:

circuit (Circuit) – The circuit to traverse.

Yields:

Instruction – The instructions of the circuit, each once.

Examples

>>> from mimiqcircuits import *
>>> c = Circuit()
>>> _ = c.push(GateH(), 0)
>>> _ = c.push(GateX(), 0)
>>> _ = c.push(GateH(), 1)
>>> list(traverse_by_dfs(c))
[H @ q[1], H @ q[0], X @ q[0]]
to_networkx(circuit)[source]

Return the circuit’s dependency graph as a networkx.DiGraph.

Node i is instruction i of the circuit and carries it in its instruction attribute; edges are those of Circuit.dag(). The graph can be passed to any networkx algorithm or drawing function.

Parameters:

circuit (Circuit) – The circuit.

Returns:

The dependency graph.

Return type:

networkx.DiGraph

Raises:

ImportError – If networkx is not installed. It is an optional dependency, installed with pip install mimiqcircuits[graph].

Examples

>>> from mimiqcircuits import *
>>> c = Circuit().push(GateH(), 0).push(GateCX(), 0, 1)
>>> g = to_networkx(c)  
>>> g.nodes[1]["instruction"]  
CX @ q[0], q[1]