Task Graph Parallel Window

A parallel_window task graph decodes a stream of any number of rounds in fixed-size windows that decode at the same time. Each window is small, so the time from a shot’s last round to its result depends on the window size, not on the shot’s length. With async_streaming, windows decode on the graph’s worker threads, so more threads keep up with faster rounds.

This page builds on Decoding Task Graphs.

How it works

Layer A windows commit 3 rounds each, with 3 buffer rounds on either side. Layer B windows commit the 9 rounds between consecutive A windows. The layout repeats every 12 rounds.

The windows form two layers:

  • Each A window corrects commit_rounds rounds, decoding them with buffer_rounds of context on each side. It needs nothing from any other window, so it decodes as soon as its rounds arrive.

  • Each B window corrects the gap_rounds between two A windows. It decodes once both neighbors have passed it their corrections at its edges.

Every round is corrected by exactly one window. Windows finish in any order, but the graph releases corrections in round order: mid-shot, a read covers rounds up to the frontier, the first round whose window has not finished. Coverage starts at round 0, or where clear_corrections() last consumed the corrections. The FINAL round ends the shot and decodes the last windows.

The model

The graph decodes a dem_chunks model (see Dynamic DEM) with:

  • a repeating phase, so shots may have any length;

  • one round per phase;

  • faults that reach at most the next round, as measurement errors do.

A phase may have no faults, such as a preparation round that no modeled fault touches.

For surface-code memory experiments, memory-experiment-generator writes the model and a parallel_window configuration for you; see Realtime Decoding.

Configuration

This configuration decodes a distance-5 repetition-code memory experiment and returns both results, its corrections and its logical measurement:

decoders:
  - id: 0
    dem_chunks:
      seam: {from: next_round, to: prev_round}
      measurements_per_round: 4        # one per check
      connections:
        - {from: init, to: bulk}
        - {from: bulk, to: bulk}       # bulk repeats
        - {from: bulk, to: final}
      phases:
        # Faults 0-4 flip data qubits 0-4; faults 5-8 are errors in measuring
        # checks 0-3. Check i reads data qubits i and i + 1. Observable 0 reads
        # data qubit 0.
        - name: init                   # first round of checks
          spec:
            num_faults: 9
            seam_specs:
              - name: prev_round       # detectors of this round
                spec: {H_sparse: [0, 1, 5, -1, 1, 2, 6, -1, 2, 3, 7, -1,
                                  3, 4, 8, -1]}
              - name: next_round       # detectors of the next round
                spec: {H_sparse: [5, -1, 6, -1, 7, -1, 8, -1]}
            D_sparse: [0, -1, 1, -1, 2, -1, 3, -1]
            O_sparse: [0, -1]
            error_rates: [0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02]
        - name: bulk
          spec:
            num_faults: 9
            seam_specs:
              - name: prev_round
                spec: {H_sparse: [0, 1, 5, -1, 1, 2, 6, -1, 2, 3, 7, -1,
                                  3, 4, 8, -1]}
              - name: next_round
                spec: {H_sparse: [5, -1, 6, -1, 7, -1, 8, -1]}
            # Detector i: check i in the previous round (index i) and in
            # this one (index 4 + i).
            D_sparse: [0, 4, -1, 1, 5, -1, 2, 6, -1, 3, 7, -1]
            O_sparse: [0, -1]
            error_rates: [0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02]
        - name: final                  # data-qubit readout
          spec:
            num_faults: 5
            num_measurements: 5        # data qubits 0-4
            seam_specs:
              - name: prev_round
                spec: {H_sparse: [0, 1, -1, 1, 2, -1, 2, 3, -1, 3, 4, -1]}
            # Detector i: check i in the previous round and data qubits i
            # and i + 1 in this one.
            D_sparse: [0, 4, 5, -1, 1, 5, 6, -1, 2, 6, 7, -1, 3, 7, 8, -1]
            m2o_sparse: [0, -1]        # observable 0 reads data qubit 0
            O_sparse: [0, -1]
            error_rates: [0.02, 0.02, 0.02, 0.02, 0.02]
    task_graph:
      async_streaming: true            # decode windows concurrently
      nodes:
        - id: pw
          type: parallel_window
          commit_rounds: 3
          buffer_rounds: 3
          gap_rounds: 9
          output: corrections_and_logical
          max_in_flight: 4             # windows of each layer at once
          inner: {type: pymatching, merge_strategy: smallest_weight}
      edges:
        - {from: measurements, to: pw}
        - {from: pw, to: output}

syndrome_mapping:
  - {id: 0, type: bulk}
  - {id: 1, type: final}               # tag each shot's last round with id 1

Parameter

Meaning

commit_rounds

Rounds each A window corrects. Required.

buffer_rounds

Rounds of context on each side of an A window. Required.

gap_rounds

Rounds each B window corrects. Default: commit_rounds + 2 * buffer_rounds.

output

corrections_and_logical: the corrections and the logical measurements (see Logical measurements). corrections: the corrections only, which a client may consume mid-shot. Required when the model has m2o_sparse; without it, the default is corrections.

inner

The decoder every window uses, with its parameters. It must report the faults it finds, not only observable flips. Windows have parallel fault columns, so for PyMatching set merge_strategy: smallest_weight.

max_in_flight

Windows of each layer that may decode at once. Needs async_streaming.

merge_identical

Merge fault columns with identical effects into one. Default false.

verify_residual

Check each window’s solution against its detectors: none (default), report a failed check in each output’s closure, or fail the graph.

A good starting point is commit_rounds and buffer_rounds equal to the code distance, with the default gap_rounds. Larger buffers give each window more context; larger windows take longer to decode.

Advanced options

Warning

Provisional. These settings stand in for the windows and stored models of the cudaq-edem library and are built on dem_chunks in this release. They will change when task graphs move to cudaq-edem.

Parameter

Meaning

input_boundary

How an A window stands in for faults from the round before it: columns (default) adds one boundary fault per detector, with a shared prior; truncate keeps those faults, with their own priors, and never corrects them.

boundary_prior

The shared prior of columns. Default: the largest chance that an odd number of the faults crossing into a detector fire.

conflicting_parallel

Fault columns that look identical in a window but flip different observables: reject (default) the configuration, or keep the most_likely.

Building a graph in code

The same graph, built with from_topology():

node = qec.TaskGraphNodeConfig()
node.id = "pw"
node.kind = "parallel_window"
node.dem = model
node.node_params = {
    "commit_rounds": 3,
    "buffer_rounds": 3,
    "gap_rounds": 9,
    "output": "corrections_and_logical",
}
node.max_in_flight = 4
node.decoder_type = "pymatching"
node.params = {"merge_strategy": "smallest_weight"}

options = qec.TaskGraphOptions()
options.async_streaming = True
# One node needs no edges: it is wired measurements -> pw -> output.
graph = qec.DecodingTaskGraph.from_topology([node], options=options)
std::vector<task_graph_node_config> nodes(1);
nodes[0].id = "pw";
nodes[0].kind = "parallel_window";
nodes[0].dem = model;
nodes[0].node_params.insert("commit_rounds", std::size_t{3});
nodes[0].node_params.insert("buffer_rounds", std::size_t{3});
nodes[0].node_params.insert("gap_rounds", std::size_t{9});
nodes[0].node_params.insert("output", std::string{"corrections_and_logical"});
nodes[0].max_in_flight = 4;
nodes[0].decoder_type = "pymatching";
nodes[0].params.insert("merge_strategy", std::string{"smallest_weight"});

task_graph_options options;
options.async_streaming = true;
// One node needs no edges: it is wired measurements -> pw -> output.
auto graph =
    decoding_task_graph::from_topology(std::move(nodes), {}, options);

Decoding a shot

Stream the shot one round at a time and tag the last round, the data-qubit readout, FINAL:

# A 40-round shot in which data qubit 0 flips in round 10: from then on,
# check 0 reads 1. Stream one round per call; the last, FINAL, reads the data
# qubits.
rounds = 40
checks = graph.get_num_msyn_per_round()
graph.reset_decoder()
for r in range(rounds - 1):
    syndrome = bytes(int(r >= 10 and i == 0) for i in range(checks))
    graph.enqueue_syndrome(syndrome)
    if r == 30:
        # Mid-shot: the corrections cover rounds [0, frontier).
        progress = graph.streaming_result().outputs[0]
        print(f"after round {r}: rounds [{progress.coverage_begin_round}, "
              f"{progress.coverage_end_round}) committed")
graph.enqueue_syndrome(bytes([1, 0, 0, 0, 0]), qec.round_type.FINAL)

corrections = list(graph.get_obs_corrections())
logical = list(graph.get_logical_measurements())
print(f"corrections: {corrections}")
print(f"logical measurements: {logical}")
graph.clear_corrections()  # start the next shot
// A 40-round shot in which data qubit 0 flips in round 10: from then on,
// check 0 reads 1. Stream one round per call; the last, FINAL, reads the
// data qubits.
const std::size_t rounds = 40;
std::vector<std::uint8_t> syndrome(graph->get_num_msyn_per_round(), 0);
const std::vector<std::uint8_t> readout{1, 0, 0, 0, 0};
graph->reset_decoder();
for (std::size_t r = 0; r + 1 < rounds; ++r) {
  syndrome[0] = r >= 10;
  graph->enqueue_syndrome(syndrome.data(), syndrome.size());
  if (r == 30) {
    // Mid-shot: the corrections cover rounds [0, frontier).
    const auto progress = graph->streaming_result().outputs.at(0);
    std::cout << "after round " << r << ": rounds ["
              << progress.coverage_begin_round << ", "
              << progress.coverage_end_round << ") committed\n";
  }
}
graph->enqueue_syndrome(readout.data(), readout.size(), round_type::FINAL);

const std::uint8_t correction = graph->get_obs_corrections()[0];
const std::uint8_t logical = graph->get_logical_measurements()[0];
std::cout << "corrections: [" << int(correction) << "]\n";
std::cout << "logical measurements: [" << int(logical) << "]\n";
graph->clear_corrections(); // start the next shot
after round 30: rounds [0, 15) committed
corrections: [1]
logical measurements: [0]

Data qubit 0 flipped, so the readout reads 1 and the correction flips it back: the logical measurement is 0. It is ready only after FINAL, which also lets clear_corrections() start the next shot.

  • With async_streaming, windows decode while later rounds arrive. Without it, each enqueue_syndrome call finishes its windows before it returns.

  • run and run_batch decode complete shots through the same windows. Their result’s converged is true when every window’s decoder converged.

  • With verify_residual, each output’s closure in streaming_result().outputs is CLOSED when every window’s solution held, OPEN when one did not, and NOT_CHECKED otherwise.

Serving with the decoding server

A quantum kernel enqueues each round with syndrome_mapping row 0 (bulk) and the last round with row 1 (final), then reads the logical measurements or the corrections back from the decoding server.

The decoding server serves the configuration above as written. Three settings matter:

  • A final syndrome_mapping row. The kernel tags each shot’s last enqueue with that row’s id, through enqueue_syndromes_mapped. It may carry earlier rounds too, but must end with the shot’s last round. Without a final row, a shot never ends.

  • async_streaming: true, so windows decode while rounds arrive.

  • dispatch: host, the default. Parallel-window graphs do not support device_graph.

The server logs a warning for a parallel-window decoder that breaks any of these.

The kernel reads the results back with get_logical_measurements and get_corrections. A read with reset consumes the shot. With corrections_and_logical, that is possible only after the final round; before it, such a read is not ready. With output: corrections, a client may reset mid-shot, and each read returns the corrections committed since the last. See Realtime Decoding and the realtime decoding API.

What the pattern builds

parallel_window is a pattern: it builds the graph below from the configuration above.

ingest feeds layer A and layer B. A hands corrections to B through its forward and backward ports, and an xor node, sum, adds both layers' corrections for the corrections output. A logical_readout node, readout, reads the raw logical value, and an xor node, logical, applies the corrections to it for the logical output.

Written out node by node, the same graph is below. The keys of ingest’s windows block are provisional.

Warning

Provisional. These settings stand in for the windows and stored models of the cudaq-edem library and are built on dem_chunks in this release. They will change when task graphs move to cudaq-edem.

task_graph:
  async_streaming: true
  nodes:
    - id: ingest
      type: ingest
      windows:                     # one output port per layer
        A:
          period: 12               # commit_rounds + gap_rounds
          zones: {buffers: [[-3, 0], [3, 6]], commit: [0, 3]}
          ports:
            input: {disposition: open, prior: 0.02}
            output: {disposition: open}
          sends: [{id: forward}, {id: backward}]
        B:
          period: 12
          offset: -9               # B[k] is the gap before A[k]
          zones: {commit: [0, 9]}
          ports:
            input: {disposition: closed}
            output: {disposition: closed}
    - id: A
      type: decode_window
      max_in_flight: 4
      inner: {type: pymatching, merge_strategy: smallest_weight}
    - id: B
      type: decode_window
      num_receives: 2
      max_in_flight: 4
      inner: {type: pymatching, merge_strategy: smallest_weight}
    - id: sum
      type: xor
    - id: readout                  # the raw logical value
      type: logical_readout
    - id: logical                  # corrections applied to it
      type: xor
  edges:
    - {from: measurements, to: ingest}
    - {from: ingest.A, to: A}
    - {from: ingest.B, to: B}
    - {from: A.forward, to: B.receive_0, index_offset: -1}  # A[k-1] to B[k]
    - {from: A.backward, to: B.receive_1}                   # A[k] to B[k]
    - {from: A, to: sum.a}
    - {from: B, to: sum.b}
    - {from: measurements, to: readout}
    - {from: sum, to: output.corrections}
    - {from: sum, to: logical.a}
    - {from: readout, to: logical.b}
    - {from: logical, to: output.logical}

Write the graph out to give the layers different decoders or to change the windows themselves.

  • The windows block of ingest defines each layer’s windows: the rounds each commits and buffers, and what it receives and sends.

  • index_offset maps window indices: window k of the edge’s destination reads window k + index_offset of its source. Here, B[k] receives A[k-1]’s forward corrections and A[k]’s backward ones.

  • readout and logical form the logical output; with output: corrections the pattern leaves them out. See Logical outputs.

Sharing data across decoders

Warning

Provisional. These settings stand in for the windows and stored models of the cudaq-edem library and are built on dem_chunks in this release. They will change when task graphs move to cudaq-edem.

A top-level data_artifacts section declares a model, a window or a Stim DEM file once and names it wherever a block is expected:

data_artifacts:
  rep_memory:
    dem_chunks: {...}            # the model above
  pw_A:
    window:
      context: rep_memory        # the model the window is built on
      period: 12
      zones: {buffers: [[-3, 0], [3, 6]], commit: [0, 3]}
      ports:
        input: {disposition: open, prior: 0.02}
        output: {disposition: open}
      sends: [{id: forward}, {id: backward}]
decoders:
  - id: 0
    dem_chunks: rep_memory
    task_graph:
      nodes:
        - id: ingest
          type: ingest
          windows:
            A: pw_A
            B: {...}             # as above
        # A, B and sum as above

Each entry is built once and shared by every decoder that names it.