Skip to content

Commit f09b467

Browse files
perlinmCopilot
andauthored
Weigh the words of the costliest coset queries by their pivot-deleted tails (#808)
* Scan coset layers by pivot-deleted tails in the shared BZ scan The shared scan `affine_search._scan` gains two constant flags: `ranked` weighs a word of one search basis of rank `ranks[0]` by its rows below the rank plus its tail, and `record_support` keeps the support of each lighter word. The always-compiled entry point `scan_coset_layer_by_tails` uses both to scan one layer of one set of a coset by the tails of its words. The four existing entry points pass both flags as False and compile to the same machine code as before. The docstring of `scan_coset_layer` no longer gives `support` a size in terms of itself. Co-authored-by: Copilot <[email protected]> * Weigh the words of the costliest coset queries by their pivot-deleted tails In a BZ coset search that weighs Hamming weights, a route is a route by tails if a query at its maximum weight with no light enough word is predicted to examine at least `overlapping_minimum_work` words with the route's own family, not only with the disjoint family, as the gate tests. The routes build once, for the family of each route by tails, a record `_CosetTails` of the tails of its rows and of the rows of the right inverse of the checks, without the pivot columns of each set. Single queries of a route by tails run `_search_coset_by_tails`, and batches `_find_first_not_within_max_weight_by_tails`, which add up the tail of each offset, scan layers with `scan_coset_layer_by_tails`, and rebuild the lightest word from its set and support. They visit the same words in the same order as `_search_coset`, so every answer stays the same. The search of Pauli errors by CSS weight has no routes by tails. `_CosetSearch.find_first_not_within_max_weight` now answers the batches of `CosetLeaderSearch`, and replaces `_CosetSearch.get_tables`. Inline helpers share the skip rule of sets and the reduction of a word to an offset between the two drivers, and `_xor_selected_rows` sums the rows for the set bits of a syndrome for both drivers and for `_map_syndromes`. Co-authored-by: Copilot <[email protected]> * Exclude pytest 9.1, whose conftest fixtures missed tests for some orders of paths In pytest 9.1, a test file given on the command line collected its directory again, with new collectors for its subdirectories, while the fixtures of a conftest file stayed with the first collector of its directory (pytest-dev/pytest#14971). So `pytest codes/distance/_search/x_test.py code_style_test.py codes/distance/_tuning_test.py` could not find `costly_stages` for the last file, and the reverse order could not find `tune`. Pytest 8 and 9.0 do not have this regression, and pytest 9.2 fixes it (pytest-dev/pytest#14635), so the development and CI requirements exclude only the 9.1 releases. Co-authored-by: Copilot <[email protected]> --------- Co-authored-by: Copilot <[email protected]>
1 parent e2b8aae commit f09b467

12 files changed

Lines changed: 923 additions & 149 deletions

‎docs/source/exact_search_tuning.rst‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,8 @@ Start from a symptom
3333
- Raise :attr:`~SearchTuning.overlapping_minimum_work` or :attr:`~SearchTuning.partition_work_ratio`, or lower :attr:`~SearchTuning.max_information_sets`.
3434
* - Queries of ``CosetLeaderSearch`` by the Brouwer--Zimmermann method at moderate maximum weights are slow, as in residual-weight estimates
3535
- Lower :attr:`~SearchTuning.overlapping_minimum_work`, so that cheaper queries try a family of overlapping information sets, or a disjoint family with more information sets or a larger partial set.
36-
The oracle builds these families once for each cached search (see :data:`CSS_SEARCH_CACHE_SIZE` and :data:`PAULI_SEARCH_CACHE_SIZE`).
36+
In the BZ searches by physical weight, and in the searches of the X and Z parts of errors for the CSS weight on CSS states, a query also weighs words without the pivot columns of each set if its predicted examinations with the family that it takes reach the threshold too.
37+
The oracle builds these families and their tails once for each cached search (see :data:`CSS_SEARCH_CACHE_SIZE` and :data:`PAULI_SEARCH_CACHE_SIZE`).
3738
For larger overlapping families, raise :attr:`~SearchTuning.max_information_sets` or :attr:`~SearchTuning.overlapping_attempts_per_set`.
3839
* - A search or count uses too much memory
3940
- For distance searches and counts, lower :attr:`~SearchTuning.completion_bound_max_table_bytes`, which applies to each problem of a joint search, such as each sector of a CSS code, and to the scan of each sector of a count.

‎pyproject.toml‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,7 @@ optional-dependencies.dev = [
6161
"jupyter>=1.1.1",
6262
"pypandoc-binary>=1.13", # bundles pandoc for building the notebook docs locally
6363
"pyproject-fmt>=2", # pyproject.toml formatting, run by checks/format_.py
64-
"pytest>=8",
64+
"pytest>=8,!=9.1.*", # excludes 9.1, whose collection lost conftest fixtures for some orders of paths
6565
"pytest-randomly>=3.10", # tests that need reproducibility read its randomly_seed option
6666
"pytest-socket>=0.7", # implements the --disable-socket in [tool.pytest] addopts below
6767
"pytest-xdist>=3", # parallel test runs, as in checks/coverage_.py
@@ -112,7 +112,7 @@ ci-test = [
112112
"checks-superstaq>=0.5.67",
113113
"coverage>=7.10",
114114
"grimp>=3.14",
115-
"pytest>=8",
115+
"pytest>=8,!=9.1.*",
116116
"pytest-randomly>=3.10",
117117
"pytest-socket>=0.7",
118118
"pytest-xdist>=3",

‎src/qldpc/codes/distance/README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ Users reach it through the `get_distance_exact` method of binary codes in `src/q
4444
| Information sets with bounded column coverage, by matroid partitioning | `_search/matroid_partition.py` |
4545
| Exhaustive enumeration, for small codes, fallbacks, and the `brute_force` method | `_search/brute_force.py` |
4646
| Minimum weights of syndrome classes of Pauli errors (coset-leader weights), by BZ or by connected-support searches, with two classical searches for the CSS weight on CSS states, used by `src/qldpc/circuits/certification/` and `src/qldpc/experimental/circuits/benchmarking/residual_weights.py` | `_search/coset_leader_search.py` |
47-
| The families of information sets with which a BZ coset-leader search answers costly queries, and the gate that chooses them for each maximum weight | `_search/coset_routes.py` |
47+
| The families of information sets with which a BZ coset-leader search answers costly queries, the gate that chooses them for each maximum weight, and the routes whose queries weigh words by their tails | `_search/coset_routes.py` |
4848
| The counter, its deformed counters, or `compile_search_setup` | `logical_counts.py` |
4949
| The scan of a count, or how its basis families follow local gates | `_counting/scan.py` |
5050
| The local Clifford gates of deformed counters | `_counting/local_cliffords.py` |

‎src/qldpc/codes/distance/_search/affine_instance.py‎

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -17,11 +17,12 @@
1717
A distance instance packs the rows of each set with its pivot columns deleted, since a scan of a
1818
space restores their weight arithmetically. Its certificate is the one that the distance search
1919
selects, with the proven divisor of eligible weights. A coset instance packs the full rows of the
20-
sets of a family of information sets of its code, disjoint or overlapping, which the coset search
21-
weighs whole. Its certificate takes the maximum coverage of the family, and no divisor, since the
22-
words of a coset need not share the divisibility of the code. If every word of the code has even
23-
Hamming weight, the Hamming weights of the words of each coset all have one parity instead, and the
24-
bounds of a coset may be rounded up to its parity.
20+
sets of a family of information sets of its code, disjoint or overlapping, which a coset search
21+
weighs whole or, in a search that weighs Hamming weights, on its routes by tails, by tails derived
22+
from them (see ``coset_leader_search._CosetTails``). Its certificate takes the maximum coverage of
23+
the family, and no divisor, since the words of a coset need not share the divisibility of the code.
24+
If every word of the code has even Hamming weight, the Hamming weights of the words of each coset
25+
all have one parity instead, and the bounds of a coset may be rounded up to its parity.
2526
"""
2627

2728
from __future__ import annotations

‎src/qldpc/codes/distance/_search/affine_search.py‎

Lines changed: 111 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,10 @@
66
basis holds the sums of its offset and ``w`` of its rows (see ``brouwer_zimmermann.md``). The
77
distance search scans ``V`` itself, with zero offsets and quotient labels that tell eligible words
88
from excluded ones, and keeps only the best weight. The coset search of ``CosetLeaderSearch`` scans
9-
a coset, with the offset of each basis, and keeps the lightest word.
9+
a coset, with the offset of each basis, and keeps the lightest word. On its routes by tails (see
10+
``coset_routes``), a coset search that weighs Hamming weights scans the tails of the rows and
11+
offsets instead, without the pivot columns of each basis, and keeps the support of the lightest
12+
word, from which it rebuilds the word.
1013
1114
Every scan of this module runs one body, ``_scan``, which its compiled entry points call with
1215
constant flags. Numba includes the body in each entry point, which compiles it for those flags, so
@@ -82,16 +85,19 @@ def scan_family(
8285
_NO_TABLE_BYTES,
8386
_NO_TABLE_OFFSETS,
8487
0,
85-
# This scan neither weighs X parts nor records words.
88+
# This scan neither weighs X parts nor records words or supports.
8689
prefixes[0, 0],
8790
prefixes[0, 0],
91+
support,
8892
one_set=False,
8993
pair_steps=False,
9094
deleted_pivots=True,
9195
test_labels=True,
9296
record=False,
9397
css_weight=False,
9498
chunked=True,
99+
ranked=False,
100+
record_support=False,
95101
)
96102
return best, depth, visited
97103

@@ -131,7 +137,7 @@ def scan_information_set(
131137
numbers of supports that the chunk weighed, of bounds that it looked up, and of supports
132138
that it skipped.
133139
"""
134-
# This scan neither reads ranks nor weighs X parts nor records words.
140+
# This scan neither reads ranks nor weighs X parts nor records words or supports.
135141
return _scan(
136142
generators,
137143
labels,
@@ -149,13 +155,16 @@ def scan_information_set(
149155
block_bits,
150156
prefixes[0, 0],
151157
prefixes[0, 0],
158+
support,
152159
one_set=True,
153160
pair_steps=True,
154161
deleted_pivots=True,
155162
test_labels=True,
156163
record=False,
157164
css_weight=False,
158165
chunked=True,
166+
ranked=False,
167+
record_support=False,
159168
)
160169

161170

@@ -179,8 +188,9 @@ def scan_coset_layer(
179188
The words are packed and full width, with no columns deleted, and weigh their Hamming weight.
180189
``rows`` has shape ``(1, num_rows, num_words)``, a stack of one search basis, and ``widths`` is
181190
``[num_words]``. The layer must have ``1 <= len(support) <= num_rows`` rows; the coset driver
182-
weighs the offset itself, layer zero, without a scan. ``support`` and ``prefixes``, of at least
183-
``len(support)`` rows, are work space. The scan keeps each word lighter than ``best`` in
191+
weighs the offset itself, layer zero, without a scan. ``prefixes``, of at least
192+
``len(support)`` rows, and ``support`` are work space. The scan keeps each word lighter than
193+
``best`` in
184194
``representative``. After each word, it returns if the best weight so far, which starts at
185195
``best``, is at most ``cutoff``, and otherwise it returns once the layer is complete.
186196
@@ -205,16 +215,19 @@ def scan_coset_layer(
205215
_NO_TABLE_BYTES,
206216
_NO_TABLE_OFFSETS,
207217
0,
208-
# This scan neither reads labels nor ranks nor weighs X parts.
218+
# This scan neither reads labels nor ranks nor weighs X parts nor records supports.
209219
representative,
210220
representative,
221+
support,
211222
one_set=True,
212223
pair_steps=False,
213224
deleted_pivots=False,
214225
test_labels=False,
215226
record=True,
216227
css_weight=False,
217228
chunked=False,
229+
ranked=False,
230+
record_support=False,
218231
)
219232
return best, weighed
220233

@@ -254,16 +267,81 @@ def scan_coset_layer_by_css_weight(
254267
_NO_TABLE_BYTES,
255268
_NO_TABLE_OFFSETS,
256269
0,
257-
# This scan neither reads labels nor ranks.
270+
# This scan neither reads labels nor ranks nor records supports.
258271
x_mask,
259272
representative,
273+
support,
260274
one_set=True,
261275
pair_steps=False,
262276
deleted_pivots=False,
263277
test_labels=False,
264278
record=True,
265279
css_weight=True,
266280
chunked=False,
281+
ranked=False,
282+
record_support=False,
283+
)
284+
return best, weighed
285+
286+
287+
@always_compiled
288+
def scan_coset_layer_by_tails(
289+
offset_tail: npt.NDArray[np.uint64],
290+
tails: npt.NDArray[np.uint64],
291+
ranks: npt.NDArray[np.int64],
292+
widths: npt.NDArray[np.int64],
293+
support: npt.NDArray[np.int64],
294+
prefixes: npt.NDArray[np.uint64],
295+
best: int,
296+
cutoff: int,
297+
best_support: npt.NDArray[np.int64],
298+
) -> tuple[int, int]:
299+
"""Scan a layer as ``scan_coset_layer`` does, but weigh each word by its pivot rows and tail.
300+
301+
The tail of a word holds its columns other than the pivot columns of the basis, packed.
302+
``tails`` holds the tails of the rows, with shape ``(1, num_rows, num_words)``, and
303+
``offset_tail`` that of the offset; ``ranks`` is ``[rank]``, for the rank of the basis, and
304+
``widths`` is ``[num_words]``. Each of the first ``rank`` rows has a one on its own pivot
305+
column, where the other rows and the offset are zero. So the Hamming weight of a word is the
306+
number of its rows below ``rank`` plus the weight of its tail. The layer, ``support``,
307+
``prefixes``, ``best``, and ``cutoff`` are as for ``scan_coset_layer``. The scan keeps the
308+
support of each word lighter than ``best`` in ``best_support``, of at least ``len(support)``
309+
entries, rather than the word.
310+
311+
Returns:
312+
The weight of the lightest word found, or ``best`` if none is lighter, and the number of
313+
words weighed.
314+
"""
315+
prefixes[0, 0] = offset_tail
316+
support[0] = 0
317+
best, _, weighed, _, _ = _scan(
318+
tails,
319+
tails,
320+
ranks,
321+
widths,
322+
widths,
323+
support,
324+
prefixes,
325+
0,
326+
best,
327+
cutoff,
328+
0,
329+
_NO_TABLE_BYTES,
330+
_NO_TABLE_OFFSETS,
331+
0,
332+
# This scan neither reads labels nor weighs X parts nor records words.
333+
prefixes[0, 0],
334+
prefixes[0, 0],
335+
best_support,
336+
one_set=True,
337+
pair_steps=False,
338+
deleted_pivots=True,
339+
test_labels=False,
340+
record=False,
341+
css_weight=False,
342+
chunked=False,
343+
ranked=True,
344+
record_support=True,
267345
)
268346
return best, weighed
269347

@@ -290,19 +368,22 @@ def _scan(
290368
block_bits: int,
291369
x_mask: npt.NDArray[np.uint64],
292370
representative: npt.NDArray[np.uint64],
371+
best_support: npt.NDArray[np.int64],
293372
one_set: bool,
294373
pair_steps: bool,
295374
deleted_pivots: bool,
296375
test_labels: bool,
297376
record: bool,
298377
css_weight: bool,
299378
chunked: bool,
379+
ranked: bool,
380+
record_support: bool,
300381
) -> tuple[int, int, int, int, int]:
301382
"""Scan the supports of a layer of a stack of search bases, starting from ``support``.
302383
303-
The array arguments are those of ``scan_family``, ``scan_information_set``, and
304-
``scan_coset_layer_by_css_weight``, and the flags, which callers pass as constants, choose what
305-
the scan does:
384+
The array arguments are those of ``scan_family``, ``scan_information_set``,
385+
``scan_coset_layer_by_css_weight``, and ``scan_coset_layer_by_tails``, and the flags, which
386+
callers pass as constants, choose what the scan does:
306387
307388
- ``one_set``: scan only the first basis, rather than all bases in lockstep.
308389
- ``pair_steps``: with ``one_set``, step through the first of the last two rows of a support
@@ -314,6 +395,12 @@ def _scan(
314395
- ``record``: copy each lighter word into ``representative``.
315396
- ``css_weight``: weigh words by their CSS weight, with ``x_mask``, rather than Hamming weight.
316397
- ``chunked``: return once the weighed supports and the lookups reach ``batch_size`` together.
398+
- ``ranked``: with ``one_set`` and ``deleted_pivots``, and without completion tables, lift the
399+
assumption of a scan of one basis that the basis is an information set: only its first
400+
``ranks[0]`` rows hold pivots, so a word weighs the number of its rows below ``ranks[0]``,
401+
rather than ``len(support)``, plus the weight of its packed tail. A scan of every basis in
402+
lockstep reads ``ranks`` regardless.
403+
- ``record_support``: copy the support of each lighter word into ``best_support``.
317404
318405
Returns:
319406
Updated ``best`` and ``depth``, and the numbers of supports weighed, of bounds looked up,
@@ -369,6 +456,13 @@ def _scan(
369456
# row, returning at the cutoff or at the end of this chunk. The last row stays in a local
370457
# variable, and enters the support only where the support is read.
371458
row = support[depth]
459+
# In a ranked basis, count the pivot rows of the support but the last once, before trying
460+
# each last row.
461+
head_pivots = np.int64(0)
462+
if ranked:
463+
for selected in range(depth):
464+
if support[selected] < ranks[0]:
465+
head_pivots += 1
372466
while row < num_rows:
373467
for set_index in range(num_sets):
374468
width = first_width if one_set else widths[set_index]
@@ -378,7 +472,9 @@ def _scan(
378472
# counts show that the word is no lighter than the best one.
379473
candidate = np.int64(0)
380474
if deleted_pivots:
381-
if one_set or ranks[set_index] == num_rows:
475+
if ranked:
476+
candidate = head_pivots + (1 if row < ranks[0] else 0)
477+
elif one_set or ranks[set_index] == num_rows:
382478
candidate = np.int64(weight)
383479
else:
384480
for selected in range(depth):
@@ -413,6 +509,10 @@ def _scan(
413509
representative[word] = (
414510
prefixes[depth, set_index, word] ^ generators[set_index, row, word]
415511
)
512+
if record_support:
513+
for selected in range(depth):
514+
best_support[selected] = support[selected]
515+
best_support[depth] = row
416516

417517
row += 1
418518
evaluated += 1

‎src/qldpc/codes/distance/_search/affine_search_test.py‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -320,6 +320,74 @@ def test_coset_layer_scans_reach_their_last_support() -> None:
320320
assert representative[0] == 0
321321

322322

323+
def _get_tail_weights(
324+
offset_tail: npt.NDArray[np.uint8], tails: npt.NDArray[np.uint8], rank: int, layer: int
325+
) -> list[tuple[tuple[int, ...], int]]:
326+
"""Each support of a layer of a coset basis by tails, in order, with the weight of its word.
327+
328+
The full rows of the basis have a pivot column for each of the first ``rank`` rows, on which
329+
every other row and the offset are zero. So the word of a support has a one on the pivot of
330+
each of its rows below ``rank``, and its tail on the other columns.
331+
"""
332+
return [
333+
(
334+
rows,
335+
sum(row < rank for row in rows)
336+
+ int(np.sum(offset_tail ^ tails[list(rows)].sum(0) % 2)),
337+
)
338+
for rows in itertools.combinations(range(len(tails)), layer)
339+
]
340+
341+
342+
@pytest.mark.usefixtures("compilation_mode")
343+
def test_coset_tail_scans_weigh_words_by_their_pivot_rows_and_tails(
344+
pytestconfig: pytest.Config,
345+
) -> None:
346+
"""A coset scan by tails gives each word its full Hamming weight, and keeps the first lightest.
347+
348+
The bases have full rank, rank deficiency one, and rank zero, and their tails span two machine
349+
words. Each scan keeps the support of each word lighter than every word before it and than the
350+
initial best weight, and returns after the first word at which the best weight so far is at most
351+
the cutoff, having weighed exactly the supports up to it.
352+
"""
353+
rng = np.random.default_rng(pytestconfig.getoption("randomly_seed"))
354+
num_rows = 5
355+
tails = (rng.random((num_rows, 70)) < 0.3).astype(np.uint8)
356+
offset_tail = rng.integers(0, 2, 70, dtype=np.uint8)
357+
packed_tails, packed_offset = pack_bits(tails)[None], pack_bits(offset_tail[None])[0]
358+
widths = np.array([packed_tails.shape[2]], dtype=np.int64)
359+
for rank, layer in itertools.product((num_rows, num_rows - 1, 0), range(1, num_rows + 1)):
360+
weights = _get_tail_weights(offset_tail, tails, rank, layer)
361+
least = min(weight for _, weight in weights)
362+
for initial_best, cutoff in itertools.product((least, least + 1, 100), (-1, least)):
363+
# The expected best weight, the support of the last word kept, and the words weighed.
364+
expected_best, expected_support, expected_weighed = initial_best, None, len(weights)
365+
for index, (rows, weight) in enumerate(weights):
366+
if weight < expected_best:
367+
expected_best, expected_support = weight, rows
368+
if expected_best <= cutoff:
369+
expected_weighed = index + 1
370+
break
371+
372+
best_support = np.full(layer, -1, dtype=np.int64)
373+
best, weighed = affine_search.scan_coset_layer_by_tails(
374+
packed_offset,
375+
packed_tails,
376+
np.array([rank]),
377+
widths,
378+
np.empty(layer, dtype=np.int64),
379+
np.empty((layer, 1, widths[0]), dtype=np.uint64),
380+
initial_best,
381+
cutoff,
382+
best_support,
383+
)
384+
assert (best, weighed) == (expected_best, expected_weighed)
385+
if expected_support is None:
386+
assert np.all(best_support == -1)
387+
else:
388+
assert tuple(best_support) == expected_support
389+
390+
323391
def _get_completion_bound(
324392
tails: npt.NDArray[np.uint8], support: Sequence[int], block_bits: int
325393
) -> int:

0 commit comments

Comments
 (0)