Scheduler Module

Scheduler

Graph scheduler for measurement and preparation timing in MBQC patterns.

This module provides:

  • compress_schedule: Compress preparation and measurement times by removing gaps.

  • Scheduler: Schedule graph node preparation and measurement operations

class graphqomb.scheduler.ScheduleTimings[source]

Scheduling timings for preparation, entanglement, and measurement.

prepare_time: dict[int, int | None]

Mapping from node indices to their preparation time.

measure_time: dict[int, int | None]

Mapping from node indices to their measurement time.

entangle_time: dict[tuple[int, int], int | None]

Mapping from edges to their entanglement time.

static __new__(_cls, prepare_time, measure_time, entangle_time)

Create new instance of ScheduleTimings(prepare_time, measure_time, entangle_time)

class graphqomb.scheduler.TimeSlice[source]

Operations for a single time slice in the schedule.

prepare_nodes: set[int]

Set of node indices to prepare in this time slice.

entangle_edges: set[tuple[int, int]]

Set of edges to entangle in this time slice.

measure_nodes: set[int]

Set of node indices to measure in this time slice.

static __new__(_cls, prepare_nodes, entangle_edges, measure_nodes)

Create new instance of TimeSlice(prepare_nodes, entangle_edges, measure_nodes)

graphqomb.scheduler.compress_schedule(prepare_time, measure_time, entangle_time=None)[source]

Compress a schedule by removing gaps in time indices.

This function shifts all time indices forward to remove unused time slots, reducing the total number of slices without changing the relative ordering.

Parameters:
Returns:

A NamedTuple containing compressed timing information:

Return type:

ScheduleTimings

class graphqomb.scheduler.Scheduler[source]

Schedule graph preparation and measurements.

graph

The graph state to be scheduled.

Type:

BaseGraphState

dag

The directed acyclic graph representing dependencies.

Type:

dict[int, set[int]]

prepare_time

A mapping from node indices to their preparation time.

Type:

dict[int, int | None]

measure_time

A mapping from node indices to their measurement time.

Type:

dict[int, int | None]

entangle_time

A mapping from edge (as tuple of two node indices) to their entanglement time.

Type:

dict[tuple[int, int], int | None]

__init__(graph, xflow, zflow=None)[source]
num_slices()[source]

Return the number of slices in the schedule.

Returns:

The number of slices, which is the maximum time across all nodes and edges plus one.

Return type:

int

property timeline: list[TimeSlice]

Get the per-slice operations for preparation, entanglement, and measurement.

Returns:

Each element is a TimeSlice containing three sets for each time slice:

  • prepare_nodes: Nodes to prepare

  • entangle_edges: Edges to entangle

  • measure_nodes: Nodes to measure

Return type:

list[TimeSlice]

manual_schedule(prepare_time, measure_time, entangle_time=None)[source]

Set the schedule manually.

Parameters:

Notes

After setting preparation and measurement times, any unscheduled entanglement times (with None value) are automatically scheduled using auto_schedule_entanglement().

The graph is treated as undirected. For convenience, entangle_time accepts edges in either order: both (u, v) and (v, u) are recognized. If both keys are provided, the canonical order (as returned by BaseGraphState.edges) takes precedence, even when the value is None.

auto_schedule_entanglement()[source]

Automatically schedule entanglement operations based on preparation times.

Each edge is scheduled at the time when both of its endpoints are prepared. For edges involving input nodes, they are scheduled when the non-input node is prepared. Input nodes are considered to be prepared at time -1 (before the first time slice).

Note

Only schedules entanglement for edges with None time. Preserves manually set times. Validation of measurement causality is performed by validate_schedule().

validate_schedule()[source]

Validate that the schedule is consistent with the graph state and DAG.

Checks: - Input nodes are not prepared (assumed to be prepared before time 0) - Output nodes are not measured - All non-input nodes have a preparation time - All non-output nodes have a measurement time - Measurement order respects DAG dependencies - Within same time slice, measurements happen before preparations - Entanglement times respect causality constraints (if entanglement is scheduled):

  • Entanglement happens AFTER both nodes are prepared

  • Entanglement happens BEFORE either node is measured

solve_schedule(config=None, timeout=60)[source]

Compute the schedule using constraint programming or greedy heuristics.

Parameters:

  • config (ScheduleConfig | None, optional) – The scheduling configuration. If None, defaults to MINIMIZE_TIME strategy.

  • timeout (int, optional) – Maximum solve time in seconds for CP-SAT solver, by default 60. Ignored when use_greedy=True.

Returns:

True if a solution was found and applied, False otherwise.

Return type:

bool

Note

After solving, any unscheduled entanglement times (with None value) are automatically scheduled using auto_schedule_entanglement().

Scheduling Solver

Scheduling solver for optimizing MBQC pattern execution.

This module provides:

  • Strategy: Enumeration of scheduling optimization strategies

  • ScheduleConfig: Configuration for scheduling parameters and constraints

  • solve_schedule: Solve scheduling optimization using constraint programming

class graphqomb.schedule_solver.Strategy[source]

Enumeration for scheduling strategies.

class graphqomb.schedule_solver.ScheduleConfig[source]

Configuration for scheduling strategy, constraints, and parameters.

__init__(strategy, max_qubit_count=None, max_time=None, use_greedy=False)
graphqomb.schedule_solver.solve_schedule(graph, dag, config, timeout=60)[source]

Solve the scheduling problem for the given graph.

Parameters:
Returns:

A tuple of (prepare_time, measure_time) dictionaries if solved, None if no solution found.

Return type:

tuple[dict[int, int], dict[int, int]] | None