You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit f09b467
Browse filesBrowse the repository at this point in the historyBrowse files
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]>
Copy file name to clipboardExpand all lines: docs/source/exact_search_tuning.rst
+2-1Lines changed: 2 additions & 1 deletion
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -33,7 +33,8 @@ Start from a symptom
33
33
- Raise :attr:`~SearchTuning.overlapping_minimum_work` or :attr:`~SearchTuning.partition_work_ratio`, or lower :attr:`~SearchTuning.max_information_sets`.
34
34
* - Queries of ``CosetLeaderSearch`` by the Brouwer--Zimmermann method at moderate maximum weights are slow, as in residual-weight estimates
35
35
- 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`).
37
38
For larger overlapping families, raise :attr:`~SearchTuning.max_information_sets` or :attr:`~SearchTuning.overlapping_attempts_per_set`.
38
39
* - A search or count uses too much memory
39
40
- 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.
Copy file name to clipboardExpand all lines: src/qldpc/codes/distance/README.md
+1-1Lines changed: 1 addition & 1 deletion
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -44,7 +44,7 @@ Users reach it through the `get_distance_exact` method of binary codes in `src/q
44
44
| Information sets with bounded column coverage, by matroid partitioning |`_search/matroid_partition.py`|
45
45
| Exhaustive enumeration, for small codes, fallbacks, and the `brute_force` method |`_search/brute_force.py`|
46
46
| 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`|
48
48
| The counter, its deformed counters, or `compile_search_setup`|`logical_counts.py`|
49
49
| The scan of a count, or how its basis families follow local gates |`_counting/scan.py`|
50
50
| The local Clifford gates of deformed counters |`_counting/local_cliffords.py`|
0 commit comments