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
The windows form two layers:
Each A window corrects
commit_roundsrounds, decoding them withbuffer_roundsof 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_roundsbetween 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 |
|---|---|
|
Rounds each A window corrects. Required. |
|
Rounds of context on each side of an A window. Required. |
|
Rounds each B window corrects. Default:
|
|
|
|
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
|
|
Windows of each layer that may decode at once. Needs
|
|
Merge fault columns with identical effects into one. Default
|
|
Check each window’s solution against its detectors: |
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 |
|---|---|
|
How an A window stands in for faults from the round before it:
|
|
The shared prior of |
|
Fault columns that look identical in a window but flip different
observables: |
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, eachenqueue_syndromecall finishes its windows before it returns.runandrun_batchdecode complete shots through the same windows. Their result’sconvergedis true when every window’s decoder converged.With
verify_residual, each output’sclosureinstreaming_result().outputsisCLOSEDwhen every window’s solution held,OPENwhen one did not, andNOT_CHECKEDotherwise.
Serving with the decoding server
The decoding server serves the configuration above as written. Three settings matter:
A
finalsyndrome_mapping row. The kernel tags each shot’s last enqueue with that row’s id, throughenqueue_syndromes_mapped. It may carry earlier rounds too, but must end with the shot’s last round. Without afinalrow, a shot never ends.async_streaming: true, so windows decode while rounds arrive.dispatch: host, the default. Parallel-window graphs do not supportdevice_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.
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
windowsblock ofingestdefines each layer’s windows: the rounds each commits and buffers, and what it receives and sends.index_offsetmaps window indices: windowkof the edge’s destination reads windowk + index_offsetof its source. Here, B[k] receives A[k-1]’sforwardcorrections and A[k]’sbackwardones.readoutandlogicalform the logical output; withoutput: correctionsthe pattern leaves them out. See Logical outputs.