HDH Partitioning Utilities

Here is an overview of the partitioning utilities available in the HDH library.

Partitioning HDHs for Distribution

The hdh/passes directory contains scripts for partitioning and manipulating HDH graphs. The primary file for partitioning is cut.py, which offers two main approaches: a greedy, HDH-aware method and a METIS-based method operating on a qubit graph representation (telegate).

Default cut algorithm

The main partitioning function is compute_cut, which implements the Capacity-Aware Greedy HDH Partitioner in cut.py.

Default cut algorithm

The default capacity-aware HDH partitioning algorithm operates in three phases.

Phase 1: Greedy bin filling via temporal expansion

The algorithm begins by selecting the earliest-time unassigned HDH node as a seed and opening a new bin associated with a target QPU. The bin is then expanded forward in time by iteratively considering unassigned nodes that are connected to the current bin by time-respecting HDH dependencies. At each iteration, the algorithm considers a bounded set of temporally admissible frontier nodes, consisting of the earliest-time candidates connected to the current bin. Among this set, it selects the node that minimises the estimated incremental communication cost of adding it to the bin, subject to the bin’s capacity constraint. When multiple candidates have equal incremental cost, temporal order is used as a secondary tie-breaker. Nodes are added individually, even when they arise from multi-qubit operations. If multiple successor nodes are produced by the same operation, each is evaluated independently, and only those whose inclusion respects the bin’s capacity constraint are admitted.

Phase 2: Sequential bin construction

Once no further admissible expansions are possible, either due to capacity saturation or the absence of valid temporal connections to unassigned nodes, the current bin is closed. The algorithm then instantiates the next bin, corresponding to the next available QPU. Whenever possible, bins are instantiated in an order that reflects physical network adjacency between QPUs, so as to favor locality in subsequent inter-bin communication. When no topology information is provided, as in this work, the algorithm assumes a fully interconnected network. Under this assumption, bin ordering does not restrict routability but directly informs the cost model used later to evaluate communication overhead. This process repeats until all bins have been instantiated or no further QPUs are available.

Phase 3: Residual assignment

If unassigned nodes remain after all bins have been instantiated, the algorithm attempts to place them in a best-fit procedure (assigning the next remaining node minimum incremental cost) over the remaining nodes. A node is assigned to a bin only if doing so does not introduce a new logical qubit beyond the bin’s remaining capacity. Nodes that cannot be placed in any bin without violating capacity constraints are left unassigned. This phase ensures completeness of the assignment under the imposed capacity constraints.\todo{Emphasise that nodes should only be left unassigned if the user has asked for something impossible.}

METIS Telegate Partitioner

For an alternative partitioner, the library provides the metis_telegate function, which leverages the METIS algorithm (with a fallback to the Kernighan-Lin algorithm if METIS is not available) on a graph generated by interpreting workload qubits as nodes and operations as edges.

Note: this method is not capable of representing operations implemented on more than 2 states, such as Toffoli gates & only interprets quantum correlations.

Telegate Graph Construction

  • Graph transformation: This method first converts the HDH into a "telegate" graph using the telegate_hdh function. In this representation:
    • Nodes are the qubits of the quantum circuit (labeled as q{idx}).
    • Edges represent quantum operations between qubits (i.e., their co-appearance in a quantum hyperedge).
    • Edge weights correspond to the multiplicity of interactions between two qubits.
  • Quantum operation filtering: Only hyperedges marked as quantum operations (with tau attribute = "q") are considered when building the telegate graph.

Partitioning Process

  • METIS partitioning: The telegate graph is partitioned using the nxmetis library, which provides Python bindings to the highly efficient METIS graph partitioning tool.
    • If METIS is unavailable, the algorithm automatically falls back to the Kernighan-Lin bisection algorithm from NetworkX.
    • METIS attempts to respect capacity constraints through the tpwgts (target partition weights) and ubvec (unbalance vector) parameters.
  • Overflow repair: Since METIS does not guarantee perfectly balanced partitions, a greedy rebalancing algorithm (_repair_overflow) is used to adjust the partitions and ensure that no bin exceeds its qubit capacity.
    • The repair algorithm uses a heuristic gain function (_best_move_for_node) to choose which qubits to move between bins.
    • It prioritizes moving qubits that minimize the increase in cut edges.

Function Signature

def metis_telegate(hdh: "HDH", partitions: int, capacities: int) -> Tuple[List[Set[str]], int, bool, str]

Parameters: * hdh: The HDH graph to partition * partitions: Number of partitions (k) * capacities: Capacity per partition (in qubits)

Returns: * A tuple of (bins_qubits, cut_cost, respects_capacity, method) where: * bins_qubits is a list of sets, each containing qubit IDs (as strings like "q0", "q1") in that partition * cut_cost is the number of edges crossing between partitions (unweighted) * respects_capacity is a boolean indicating whether all bins satisfy the capacity constraint * method is either "metis" or "kl" indicating which algorithm was used

KaHyPar hypergraph partitioner

cut.py also includes a KaHyPar-based partitioner, taken from the KaHyPar library. To versions are included (qubit and node based):

kahypar_cutter * Vertices are logical qubits. * Each HDH hyperedge contributes a hyperedge over the qubits that appear in it. * KaHyPar then runs its multilevel hypergraph partitioning pipeline (coarsening → initial partition → refinement), configured by an INI file (e.g., km1_kKaHyPar_sea20.ini). * Capacity is expressed as a balance constraint via KaHyPar’s epsilon (derived from cap relative to the ideal target size n/k). * This means the partitioner primarily “knows” about balancing qubit counts; it does not model HDH-specific capacity nuances (for example, heterogeneous per-QPU capacities, or time-expanded node effects), and any “capacity” notion lives inside the balance constraint.

kahypar_cutter_nodebalanced: * Vertices are HDH nodes (time-expanded). * Balance is therefore in node count, not in unique logical qubits. * As a result, it can produce partitions that look well-balanced to KaHyPar but do not respect logical-qubit capacity (this is kind-off not respected by the other version either, but this one is even egregious as it doesn't know if a node would require a new active qubit in use).

Cut Cost Evaluation

The quality of a partition is determined by the number of cut hyperedges, that is, the number of hyperedges that span across multiple QPUs (bins). The library provides two functions to evaluate this cost given a partitioning:

_total_cost_hdh

Calculates the total cost of a partition on an HDH graph. This function: * Iterates through all hyperedges in the HDH * Counts a hyperedge as "cut" if its pins (nodes) are distributed across 2 or more bins * Returns the sum of weights of all cut hyperedges (quantum hyperedges count as 10 and classic hyperedges count as 1 - you can modify these values in the source code but if you would like this to be adjustable please feel free to open an issue)

_cut_edges_unweighted

Counts the number of edges that cross between different bins in a standard graph (used for evaluating telegate graph partitions). This function: * Takes a NetworkX graph and a partition assignment * Counts edges where the two endpoints are in different bins * Returns an unweighted count (each cut edge counts as 1)

Use case: This is specifically used by metis_telegate to evaluate the quality of qubit-graph partitions.

Helper Functions and Internal Components

The cut.py file contains helper utilities for the partitioners (note that some older helpers/classes remain in the file as legacy code paths).

Temporal incidence + frontier utilities (greedy partitioner)

  • _build_temporal_incidence: builds inc[node] -> [(hyperedge, edge_time)] and pins[hyperedge] -> {nodes}, where edge_time = max(pin_times); used to enforce temporal validity.
  • _push_next_valid_neighbors: expands a node into the min-heap frontier, pushing only temporally valid neighbour candidates.
  • _select_best_from_frontier_with_rejected: takes the earliest beam_k frontier items (skipping rejected), evaluates delta cost, and returns the best candidate.
  • _compute_delta_cost_simple: delta in (unweighted) cut-hyperedge count if a node is added to a specific bin.
  • _extract_qubit_id: parses q{idx}_t{t} to extract the logical qubit index for capacity accounting.

METIS utilities

  • telegate_hdh: converts the HDH to a qubit interaction graph (“telegate graph”).
  • _repair_overflow, _best_move_for_node, _over_under: post-processing used to fix capacity violations after METIS/KL.
  • _cut_edges_unweighted: unweighted cut-edge count for the telegate graph.

Notes on Evaluating Partitioners on Random Circuits

  • We would like to warn users and partitioning strategy developers that we have found partitioners to behave very differently on real quantum workloads (such as circuits) when compared to randomly generated ones. As such, we recommend not testing partitioners on randomly generated workloads unless that is specifically your goal. *

Key considerations: * Circuit structure matters: Real quantum algorithms often have characteristic patterns (e.g., layered structures, specific qubit interaction patterns) that random circuits lack. * Connectivity patterns: Random circuits may not reflect the typical connectivity found in QAOA, VQE, quantum simulation, or other structured quantum algorithms.