Circuit Partitioning Examples

Examples demonstrating circuit partitioning algorithms.

Naive Capacity-Based Circuit Partitioning on a Grover Circuit

This example demonstrates naive capacity-based partitioning, which distributes gates evenly across partitions based purely on capacity, ignoring connectivity.

capacity_based_partitioning_grover_example.py
 1from kosmos.partitioning.algorithms.capacity_partitioner import CapacityBasedPartitioner
 2from kosmos.partitioning.mqt_bench.bench_circuit import MQTBenchCircuit
 3from kosmos.utils.rng import RNG
 4
 5GATE_VISUALIZATION_LENGTH = 5
 6
 7
 8def partitioning_result_description(
 9    algorithm_name: str, assignments: dict[int, int], num_gates: int
10) -> list[str]:
11    """Format partitioning results as human-readable text lines.
12
13    Args:
14        algorithm_name: Name of the partitioning algorithm.
15        assignments: Gate-to-partition assignments.
16        num_gates: Total number of gates in the circuit.
17
18    Returns:
19        list[str]: Formatted output lines.
20
21    """
22    output = [f"\n{'=' * 60}", f"Algorithm: {algorithm_name}", f"{'=' * 60}"]
23
24    # Group gates by partition
25    partitions: dict[int, list[int]] = {}
26    for gate_idx, partition_id in assignments.items():
27        if partition_id not in partitions:
28            partitions[partition_id] = []
29        partitions[partition_id].append(gate_idx)
30
31    # Calculate statistics
32    num_partitions = len(partitions)
33    partition_sizes = [len(gates) for gates in partitions.values()]
34    avg_size = sum(partition_sizes) / num_partitions if num_partitions > 0 else 0
35    max_size = max(partition_sizes) if partition_sizes else 0
36    min_size = min(partition_sizes) if partition_sizes else 0
37
38    output.append("\nStatistics:")
39    output.append(f"  Total gates: {num_gates}")
40    output.append(f"  Number of partitions: {num_partitions}")
41    output.append(f"  Partition sizes: min={min_size}, max={max_size}, avg={avg_size:.1f}")
42
43    # Calculate balance metric
44    if avg_size > 0:
45        balance = max(abs(size - avg_size) for size in partition_sizes) / avg_size
46        output.append(f"  Balance (max deviation): {balance:.2%}")
47
48    output.append("\nPartition Details:")
49    for partition_id in sorted(partitions.keys()):
50        gates = sorted(partitions[partition_id])
51        gate_str = (
52            f"[{gates[0]}...{gates[-1]}]" if len(gates) > GATE_VISUALIZATION_LENGTH else str(gates)
53        )
54        output.append(f"  Partition {partition_id}: {len(gates)} gates {gate_str}")
55
56    return output
57
58
59def capacity_based_grover_example() -> None:
60    """Run example for naive capacity-based circuit partitioning on a Grover circuit."""
61    RNG.initialize(seed=1)
62
63    output = ["\n=== Circuit Characteristics ==="]
64
65    # Load Grover circuit from MQT Bench
66    benchmark = MQTBenchCircuit(circuit_type="grover-noancilla", num_qubits=8)
67    circuit = benchmark.circuit()
68
69    output.append(f"Qubits: {benchmark.num_qubits}")
70    output.append(f"Gates: {benchmark.num_gates}")
71    output.append(f"Depth: {benchmark.depth}")
72
73    partitioner = CapacityBasedPartitioner(network=None, num_partitions=3)
74    assignments = partitioner.partition(circuit)
75
76    output.extend(
77        partitioning_result_description("Capacity-Based", assignments, benchmark.num_gates)
78    )
79
80    print("\n".join(output))  # noqa: T201
81
82
83if __name__ == "__main__":
84    capacity_based_grover_example()

Circuit Partitioning Using Metis on a QFT Circuit

This example demonstrates partitioning using METIS.

metis_partitioning_qft_example.py
 1from kosmos.partitioning.algorithms.metis_partitioner import METISPartitioner
 2from kosmos.partitioning.mqt_bench.bench_circuit import MQTBenchCircuit
 3from kosmos.utils.rng import RNG
 4
 5GATE_VISUALIZATION_LENGTH = 5
 6
 7
 8def partitioning_result_description(
 9    algorithm_name: str, assignments: dict[int, int], num_gates: int
10) -> list[str]:
11    """Format partitioning results as human-readable text lines.
12
13    Args:
14        algorithm_name: Name of the partitioning algorithm.
15        assignments: Gate-to-partition assignments.
16        num_gates: Total number of gates in the circuit.
17
18    Returns:
19        list[str]: Formatted output lines.
20
21    """
22    output = [f"\n{'=' * 60}", f"Algorithm: {algorithm_name}", f"{'=' * 60}"]
23
24    # Group gates by partition
25    partitions: dict[int, list[int]] = {}
26    for gate_idx, partition_id in assignments.items():
27        if partition_id not in partitions:
28            partitions[partition_id] = []
29        partitions[partition_id].append(gate_idx)
30
31    # Calculate statistics
32    num_partitions = len(partitions)
33    partition_sizes = [len(gates) for gates in partitions.values()]
34    avg_size = sum(partition_sizes) / num_partitions if num_partitions > 0 else 0
35    max_size = max(partition_sizes) if partition_sizes else 0
36    min_size = min(partition_sizes) if partition_sizes else 0
37
38    output.append("\nStatistics:")
39    output.append(f"  Total gates: {num_gates}")
40    output.append(f"  Number of partitions: {num_partitions}")
41    output.append(f"  Partition sizes: min={min_size}, max={max_size}, avg={avg_size:.1f}")
42
43    # Calculate balance metric
44    if avg_size > 0:
45        balance = max(abs(size - avg_size) for size in partition_sizes) / avg_size
46        output.append(f"  Balance (max deviation): {balance:.2%}")
47
48    output.append("\nPartition Details:")
49    for partition_id in sorted(partitions.keys()):
50        gates = sorted(partitions[partition_id])
51        gate_str = (
52            f"[{gates[0]}...{gates[-1]}]" if len(gates) > GATE_VISUALIZATION_LENGTH else str(gates)
53        )
54        output.append(f"  Partition {partition_id}: {len(gates)} gates {gate_str}")
55
56    return output
57
58
59def metis_partition_qft_example() -> None:
60    """Run example for circuit partitioning using METIS on a QFT circuit."""
61    RNG.initialize(seed=1)
62
63    output = ["\n=== Circuit Characteristics ==="]
64
65    # Load QFT circuit from MQT Bench
66    benchmark = MQTBenchCircuit(circuit_type="qft", num_qubits=16)
67    circuit = benchmark.circuit()
68
69    output.append(f"Qubits: {benchmark.num_qubits}")
70    output.append(f"Gates: {benchmark.num_gates}")
71    output.append(f"Depth: {benchmark.depth}")
72
73    partitioner = METISPartitioner(network=None, num_partitions=3)
74    assignments = partitioner.partition(circuit)
75
76    output.extend(partitioning_result_description("METIS", assignments, benchmark.num_gates))
77
78    print("\n".join(output))  # noqa: T201
79
80
81if __name__ == "__main__":
82    metis_partition_qft_example()

Spectral Circuit Partitioning on a QFT Circuit

This example demonstrates spectral partitioning using the Fiedler vector of the graph Laplacian.

spectral_partitioning_qft_example.py
 1from kosmos.partitioning.algorithms.spectral_partitioner import SpectralPartitioner
 2from kosmos.partitioning.mqt_bench.bench_circuit import MQTBenchCircuit
 3from kosmos.utils.rng import RNG
 4
 5GATE_VISUALIZATION_LENGTH = 5
 6
 7
 8def partitioning_result_description(
 9    algorithm_name: str, assignments: dict[int, int], num_gates: int
10) -> list[str]:
11    """Format partitioning results as human-readable text lines.
12
13    Args:
14        algorithm_name: Name of the partitioning algorithm.
15        assignments: Gate-to-partition assignments.
16        num_gates: Total number of gates in the circuit.
17
18    Returns:
19        list[str]: Formatted output lines.
20
21    """
22    output = [f"\n{'=' * 60}", f"Algorithm: {algorithm_name}", f"{'=' * 60}"]
23
24    # Group gates by partition
25    partitions: dict[int, list[int]] = {}
26    for gate_idx, partition_id in assignments.items():
27        if partition_id not in partitions:
28            partitions[partition_id] = []
29        partitions[partition_id].append(gate_idx)
30
31    # Calculate statistics
32    num_partitions = len(partitions)
33    partition_sizes = [len(gates) for gates in partitions.values()]
34    avg_size = sum(partition_sizes) / num_partitions if num_partitions > 0 else 0
35    max_size = max(partition_sizes) if partition_sizes else 0
36    min_size = min(partition_sizes) if partition_sizes else 0
37
38    output.append("\nStatistics:")
39    output.append(f"  Total gates: {num_gates}")
40    output.append(f"  Number of partitions: {num_partitions}")
41    output.append(f"  Partition sizes: min={min_size}, max={max_size}, avg={avg_size:.1f}")
42
43    # Calculate balance metric
44    if avg_size > 0:
45        balance = max(abs(size - avg_size) for size in partition_sizes) / avg_size
46        output.append(f"  Balance (max deviation): {balance:.2%}")
47
48    output.append("\nPartition Details:")
49    for partition_id in sorted(partitions.keys()):
50        gates = sorted(partitions[partition_id])
51        gate_str = (
52            f"[{gates[0]}...{gates[-1]}]" if len(gates) > GATE_VISUALIZATION_LENGTH else str(gates)
53        )
54        output.append(f"  Partition {partition_id}: {len(gates)} gates {gate_str}")
55
56    return output
57
58
59def spectral_partition_qft_example() -> None:
60    """Run example for spectral circuit partitioning on a QFT circuit."""
61    RNG.initialize(seed=1)
62
63    output = ["\n=== Circuit Characteristics ==="]
64
65    # Load QFT circuit from MQT Bench
66    benchmark = MQTBenchCircuit(circuit_type="qft", num_qubits=64)
67    circuit = benchmark.circuit()
68
69    output.append(f"Qubits: {benchmark.num_qubits}")
70    output.append(f"Gates: {benchmark.num_gates}")
71    output.append(f"Depth: {benchmark.depth}")
72
73    partitioner = SpectralPartitioner(network=None, num_partitions=2)
74    assignments = partitioner.partition(circuit)
75
76    output.extend(
77        partitioning_result_description(
78            "Spectral (Fiedler Vector)", assignments, benchmark.num_gates
79        )
80    )
81
82    print("\n".join(output))  # noqa: T201
83
84
85if __name__ == "__main__":
86    spectral_partition_qft_example()