Functions | |
| def | _check_gurobi_available () |
| def | _get_topo_order (g, rg, gate_to_qubit) |
| def | _print_gurobi_fallback_warning (exc) |
| def | _solve_pulp_with_gurobi_or_cbc (prob, pulp, callback=None, gurobi_kwargs) |
| def | _test_max_qasm () |
| def | all_cycles_from_dag_edges (succ, max_len=5) |
| def | contract_single_qubit_chains (go, rgo, gate_to_qubit, topo_order) |
| def | find_next_biggest_partition (c, max_qubits_per_partition, prevparts=None) |
| def | get_all_partitions (c, max_qubits_per_partition) |
| def | get_part_cycle_graph (g, gate_to_parts) |
| def | ilp_global_optimal (allparts, g, weighted_info=None, gurobi_direct=False, use_order=False, weights=None) |
| def | ilp_max_partitions (c, max_qubits_per_partition) |
| def | max_partitions (c, max_qubits_per_partition, use_ilp=True, fusion_cost=False, control_aware=False) |
| def | nuutila_reach_scc (succ, subg=None) |
| def | recombine_single_qubit_chains (g, rg, single_qubit_chains, gate_to_tqubit, L, fusion_info, surrounded_only=False) |
| def | scc_tarjan_iterative (succ) |
| def | sol_to_badsccs (g, allparts, L) |
| def | topo_sort_partitions (c, parts) |
| def | two_cycles_from_dag_edges (g, gate_to_parts, allparts) |
Variables | |
| _GUROBI_AVAILABILITY_ERROR | |
| _GUROBI_AVAILABLE | |
| _GUROBI_FALLBACK_WARNING_PRINTED | |
Function Documentation
◆ _check_gurobi_available()
|
private |
◆ _get_topo_order()
|
private |
Get a topological order of a DAG given forward and reverse adjacency.
Args:
g (dict[int, set[int]]): Forward adjacency (u -> successors).
rg (dict[int, set[int]]): Reverse adjacency (v -> predecessors).
Returns:
list[int]: A topological ordering of nodes.
Definition at line 240 of file ilp.py.
Here is the caller graph for this function:
◆ _print_gurobi_fallback_warning()
|
private |
◆ _solve_pulp_with_gurobi_or_cbc()
|
private |
◆ _test_max_qasm()
|
private |
◆ all_cycles_from_dag_edges()
| def ilp.all_cycles_from_dag_edges | ( | succ, | |
max_len = 5 |
|||
| ) |
Enumerate chordless directed cycles consistent with a given successor map.
Args:
succ (dict[Hashable, set[Hashable]]): Successor adjacency among nodes.
max_len (int | None): Optional max cycle length bound; None disables bound.
Returns:
list[list[Hashable]]: List of chordless cycles (each as node list in order).
◆ contract_single_qubit_chains()
| def ilp.contract_single_qubit_chains | ( | go, | |
| rgo, | |||
| gate_to_qubit, | |||
| topo_order | |||
| ) |
Contract maximal chains of single-qubit gates to simplify the DAG.
Args:
go (dict[int, set[int]]): Forward gate DAG (gate -> children).
rgo (dict[int, set[int]]): Reverse gate DAG (gate -> parents).
gate_to_qubit (dict[int, set[int]]): Gate index -> acted-on qubits.
topo_order (list[int]): A topological order of the original DAG.
Returns:
tuple: (g, rg, topo_order_reduced, chains)
g (dict[int, set[int]]): Reduced forward DAG after contraction.
rg (dict[int, set[int]]): Reduced reverse DAG after contraction.
topo_order_reduced (list[int]): Topological order without single-qubit gates.
chains (set[tuple[int,...]]): Set of contracted chains (each a tuple of gate ids).
Definition at line 267 of file ilp.py.
Here is the caller graph for this function:
◆ find_next_biggest_partition()
| def ilp.find_next_biggest_partition | ( | c, | |
| max_qubits_per_partition, | |||
prevparts = None |
|||
| ) |
Find the next largest feasible gate partition via ILP (single partition step).
Args:
c: SQUANDER circuit to be partitioned.
max_qubits_per_partition (int): Maximum number of qubits allowed in the partition.
prevparts (Iterable[Iterable[int]] | None): Previously selected partitions whose
gates must be excluded in this step.
Returns:
set[int]: Set of gate indices forming the next largest partition.
Definition at line 125 of file ilp.py.
Here is the call graph for this function:
Here is the caller graph for this function:
◆ get_all_partitions()
| def ilp.get_all_partitions | ( | c, | |
| max_qubits_per_partition | |||
| ) |
Generate all feasible parts (gate sets) for partitioning a circuit.
Args:
c: SQUANDER circuit object.
max_qubits_per_partition (int): Max allowed qubits per partition.
Returns:
tuple: (allparts, go, rgo, single_qubit_chains, gate_to_qubit, gate_to_tqubit)
allparts (set[frozenset[int]]): All feasible parts (gate sets).
g (dict[int, set[int]]): Gate -> successors (original graph).
go (dict[int, set[int]]): Gate -> successors.
rgo (dict[int, set[int]]): Gate -> predecessors.
single_qubit_chains (set[tuple[int]] | None): Set of single-qubit chains (as tuples).
gate_to_qubit (dict[int, set[int]]): Gate -> qubits acted on.
gate_to_tqubit (dict[int, int | None]): Gate -> target qubit (or None).
Definition at line 859 of file ilp.py.
Here is the call graph for this function:
Here is the caller graph for this function:
◆ get_part_cycle_graph()
| def ilp.get_part_cycle_graph | ( | g, | |
| gate_to_parts | |||
| ) |
Build a partition-level interaction DAG and prune intra-overlap edges.
Args:
g (dict[int, set[int]]): Gate DAG (u -> successors v).
gate_to_parts (dict[int, Iterable[int]]): Gate -> indices of parts containing it.
Returns:
dict[int, set[int]]: Pruned successor map among parts (DAG over part indices).
Definition at line 430 of file ilp.py.
Here is the call graph for this function:
Here is the caller graph for this function:
◆ ilp_global_optimal()
| def ilp.ilp_global_optimal | ( | allparts, | |
| g, | |||
weighted_info = None, |
|||
gurobi_direct = False, |
|||
use_order = False, |
|||
weights = None |
|||
| ) |
Select an optimal set of non-overlapping parts via ILP/MIP with cycle cuts.
Args:
allparts (list[frozenset[int]]): Candidate parts (gate sets).
g (dict[int, set[int]]): Gate DAG (u -> successors v).
weighted_info (tuple | None): Optional tuple providing cost modeling:
(single_qubit_chains, max_qubits_per_partition, go, rgo, gate_to_qubit, gate_to_tqubit).
gurobi_direct (bool): If True, build and solve directly in gurobipy with callbacks.
use_order (bool): If True, add an ordering formulation to avoid cycles.
Returns:
tuple: (selected_parts, fusion_info or None)
selected_parts (list[frozenset[int]]): Chosen parts minimizing the cost.
fusion_info (tuple[set[int], set[int]] | None): (inpre, inpost) sets for
chain placements when weighted_info enables fusion costs.
Definition at line 600 of file ilp.py.
Here is the call graph for this function:
Here is the caller graph for this function:
◆ ilp_max_partitions()
| def ilp.ilp_max_partitions | ( | c, | |
| max_qubits_per_partition | |||
| ) |
Partitions a circuit using ILP to maximize gates per partition
Args:
c: SQUANDER Circuit to partition
max_qubits_per_partition: Max qubits per partition
Returns:
Partitioned circuit, parameter order (source_idx, dest_idx, param_count), partition assignments
Definition at line 105 of file ilp.py.
Here is the call graph for this function:
◆ max_partitions()
| def ilp.max_partitions | ( | c, | |
| max_qubits_per_partition, | |||
use_ilp = True, |
|||
fusion_cost = False, |
|||
control_aware = False |
|||
| ) |
Enumerate feasible parts and select a maximum/optimal partitioning of a circuit.
Args:
c: SQUANDER circuit object.
max_qubits_per_partition (int): Max allowed qubits per partition.
use_ilp (bool): If True, solve selection via ILP; else greedy largest-first.
fusion_cost (bool): If True, include FLOP-based cost with fusion/controls.
control_aware (bool): If True and fusion_cost, treat single-qubit chains as
pre/post relative to targets.
Returns:
tuple: (partitioned_circ, param_order, parts)
partitioned_circ: 2-level partitioned circuit (SQUANDER object).
param_order (list[tuple[int,int,int]]): (source_idx, dest_idx, param_count).
parts (list[frozenset[int]]): Final partition assignment sets.
Definition at line 935 of file ilp.py.
Here is the call graph for this function:
Here is the caller graph for this function:
◆ nuutila_reach_scc()
| def ilp.nuutila_reach_scc | ( | succ, | |
subg = None |
|||
| ) |
Compute SCCs and intra-SCC reachability using Nuutila's variant (iterative).
Args:
succ (dict[Hashable, Iterable[Hashable]]): Successor adjacency list.
subg (set[Hashable] | None): Optional node subset to restrict the search.
Returns:
tuple: (sccs, reach)
sccs (dict[Hashable, set]): Map from SCC root to set of vertices in that SCC.
reach (dict[Hashable, set]): For each SCC root, the set of vertices reachable
from that SCC (including the SCC itself iff it has a self-loop).
Definition at line 178 of file ilp.py.
Here is the caller graph for this function:
◆ recombine_single_qubit_chains()
| def ilp.recombine_single_qubit_chains | ( | g, | |
| rg, | |||
| single_qubit_chains, | |||
| gate_to_tqubit, | |||
| L, | |||
| fusion_info, | |||
surrounded_only = False |
|||
| ) |
Re-insert contracted single-qubit chains back into partition groups.
Args:
g (dict[int, set[int]]): Forward DAG of original gates.
rg (dict[int, set[int]]): Reverse DAG of original gates.
single_qubit_chains (set[tuple[int,...]]): Contracted chains to re-attach.
gate_to_tqubit (dict[int, int]): Gate -> target qubit id.
L (Iterable[Iterable[int]]): Current partition groups.
fusion_info (tuple[set[int], set[int]] | None): Optional pre/post placement
hints (inpre, inpost) for chain endpoints.
Returns:
list[frozenset[int]]: Updated partition groups with single-qubit chains merged.
Definition at line 309 of file ilp.py.
Here is the caller graph for this function:
◆ scc_tarjan_iterative()
| def ilp.scc_tarjan_iterative | ( | succ | ) |
Strongly Connected Components (Tarjan) without recursion.
Parameters
----------
succ : list of iterables
succ[u] is an iterable of out-neighbors of u. Nodes are 0..n-1.
Returns
-------
comp_id : list[int]
comp_id[u] = index of the SCC containing u (0..k-1).
comps : list[list[int]]
List of SCCs; each is a list of nodes. Order is discovery order.
Notes
-----
- No recursion; uses an explicit DFS stack of (u, iterator) frames.
- Self-loops and parallel edges are handled.
- Time O(n + m), space O(n).
Definition at line 351 of file ilp.py.
Here is the caller graph for this function:
◆ sol_to_badsccs()
| def ilp.sol_to_badsccs | ( | g, | |
| allparts, | |||
| L | |||
| ) |
◆ topo_sort_partitions()
| def ilp.topo_sort_partitions | ( | c, | |
| parts | |||
| ) |
Topologically sort partition groups and re-partition with Kahnâs algorithm.
Args:
c: SQUANDER circuit object.
max_qubits_per_partition (int): Maximum number of qubits allowed in a partition.
parts (list[Iterable[int]]): Precomputed gate groups (each is an iterable of gate indices).
Returns:
tuple: (partitioned_circ, param_order, parts)
partitioned_circ: 2-level partitioned circuit (SQUANDER object).
param_order (list[tuple[int,int,int]]): Tuples (source_idx, dest_idx, param_count).
parts (list[frozenset[int]]): Final partition assignments (topologically sorted).
Definition at line 55 of file ilp.py.
Here is the call graph for this function:
Here is the caller graph for this function:
◆ two_cycles_from_dag_edges()
| def ilp.two_cycles_from_dag_edges | ( | g, | |
| gate_to_parts, | |||
| allparts | |||
| ) |
Detect pairwise 2-cycles between partitions induced by gate-level edges.
Args:
g (dict[int, set[int]]): Gate DAG (u -> successors v).
gate_to_parts (dict[int, Iterable[int]]): Gate -> indices of parts containing it.
allparts (list[frozenset[int]]): The parts (gate sets) by index.
Returns:
list[tuple[int, int]]: List of (a, b) where a < b and a <-> b two-cycle is found,
excluding cases where parts overlap.
