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 the |
|
Return the circuit's dependency graph as a |
Return the vertices of |
|
Return the vertices of |
|
|
Yield the instructions of |
|
Yield the instructions of |
Classes
|
Dependency graph of a circuit's instructions. |
- class CircuitDAG(n)[source]¶
Bases:
objectDependency graph of a circuit’s instructions.
Vertices are the integer positions
0 .. n-1of the instructions in the circuit. An edgeu -> vmeans instructionvdepends on instructionu: they touch a common qubit, bit, or z-variable anduis 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 withnvertices and no edges.- Parameters:
n (int) – The number of vertices.
- Raises:
TypeError – If
nis 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]
- build_dag(circuit)[source]¶
Build the
CircuitDAGofcircuit.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,SchmidtRankandVonNeumannEntropydepend 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:
- topological_sort_by_bfs(dag)[source]¶
Return the vertices of
dagin 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:
- Raises:
TypeError – If
dagis not aCircuitDAG.
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
dagin 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:
- Raises:
TypeError – If
dagis not aCircuitDAG.ValueError – If the graph has a cycle. A graph built from a circuit never has one.
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
circuitin 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
circuitin 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
iis instructioniof the circuit and carries it in itsinstructionattribute; edges are those ofCircuit.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
networkxis not installed. It is an optional dependency, installed withpip 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]