nelimee
commented
4 weeks ago So I have been exploring this code for the past 2 days. I also made a tentative at implementing a generic method to compute stabilizers a few months ago.
From that, here are my main conclusions.
First, the problem of finding stabilizers can be split into 3 sub-problems:
- Splitting correctly the circuit according to the collapsing operations (resets and measurements) contained in this circuit.
- Pre-computing various quantities on the split sub-circuits (stabilizer propagation for example).
- Using the data pre-computed in step 2. to match stabilizer flows and find detectors.
Now, in more details.
1. Splitting the input circuit
The collapsing operations (measurement and resets) are the main point of interest here. What I did in my attempt, and what I think you also did in this PR, is to constraint the input circuit to avoid a (probably large) number of edge cases.
The constraint I have in mind is: collapsing operations (again, measurements and resets) cannot appear everywhere in the circuit and can only appear in their own moment (sub-circuit between two TICK instructions).
This constraint makes sense as Austin already told us, this is in fact something that most hardware will want to ensure.
With that constraint in mind, there are still a few edge cases that need to be handled:
REPEATblocks need to be treated differently,- combined measurement/reset operations (such as
MRthat performs a measurement in theZbasis directly followed by a reset in theZbasis) makes it difficult to split the input circuit cleanly into sub-circuits.
In the end, I dislike how I split the circuit in my previous attempt because I was using cirq (which would be best avoided here, I agree) and I was storing a lot of stim.Tableau.
I do not fully adhere to your method either, I feel like the code is too complex for what it is doing. In particular, as you noted, the split_stim_circuit_into_fragments is quite hard to reason about.
I think my preferred way of solving that sub-problem would be to re-use your code, but ensuring that Fragment instances start with a moment of resets and end with a moment of measurements, splitting the combined operations into two separate operations if needed. This simple change in the input circuit would remove the need to store begin/end stabilizer sources and to keep track of the sources for the next Fragment. Basically, only performing stim.Circuit manipulation and not computing anything (yet).
2. Pre-computation
We need to pre-compute a lot of information in order to hope to perform step 3 efficiently. In particular, for each collapsing operation, we need to compute how the stabilizer it propagates evolves in the circuit. Here, there is a difference between measurements and resets:
- measurements propagate stabilizers backwards where resets propagate stabilizers forward,
- the final result, the detectors, are composed of measurements, not of resets,
These differences mean that we will need to store enough information to recover the exact measurement associated with a given stabilizer propagation, but we do not really care about the reset associated to a propagation.
In our case, I fully agree with the step-by-step description by Austin. So our Fragment instances have beginning and end stabilizers, the beginning stabilizers being annotated with the measurement that started the (back-)propagation and the end stabilizers storing the measurement(s) that commuted and anti-commuted with the pauli string that propagated from the reset.
The goal of that step is simply to produce as efficiently as possible a data-structure that we will be able to query afterward to match stabilizers together.
If we only restrict ourselves to detectors only including measurements from the current and previous rounds, it is sufficient in this step to pre-compute the stabilizers for each Fragment separately: evolve forward each reset-generated stabilizer, evolve backward each measurement-generated stabilizer, and store the resulting stabilizer with the commuting/anti-commuting measurements in a data-structure that will be accessed at the next step.
3. Matching stabilizer flows
The approach described by Austin and implemented in your different match_* methods works for me. I only have a doubt on a specific part of the code in find_cover:
def find_cover(
target: BoundaryStabilizer,
sources: list[BoundaryStabilizer],
) -> list[BoundaryStabilizer] | None:
subsets = [
source
for source in sources
if target.after_collapse.contains(source.after_collapse)
]I am not sure the restriction to sources that are contained by target is correct, as some sources might cancel out the Pauli terms that are not contained in target and end up forming a stabilizer.
Overall opinion
All in all, I really think that we should look at these 3 sub-problems separately for several reasons:
- it helps tackling one problem at a time,
- it will likely help organising the code in well define, self-contained, portions,
- it will allow us to think about the interfaces between the code solving each sub-problem.
If you agree with what I wrote above, my plan is to reformat the code in this PR following these 3 sub-problems.
inmzhang
afowler
This is a very basic attempt to adress #199. I tried to implement the proposal by Austin at the level of
stiminstead ofcirqbecause I want this part of work can be applied to other stim-based projects more easily. The main pipeline can be splitted into the following steps:stim.Circuitinto fragments. By design, a fragment is the sub-circuit of a single error correction round with related resets/measurements collapsing operations.Currently, there are some problems in the codebase as far as I can notice and remember:
R -- MR -- M, the second detector should beDETECTOR rec[-1][-2]instead ofDETECTOR rec[-1]. Though the two definitions seem equivalent when multiplying the first detector into it, there are critical differences when decoding the circuits. Thus I always try to match the boundary stabilizers between two consequtive fragments even when the weight of the stabilizer is zero.stim. In my plan, I would like to test it more on the various circuits in this paper. Currently I have only included a single circuit in the directoryextra_test_circuitsfor anticommute grouping test purpose(so it should fail for now).Ideally, I would have completed the remaining tasks and submitted a finalized PR. However, I'm quite occupied these days and I'm not sure when I will be able to finish this. Therefore, I'm submitting it as a draft and would appreciate any help from the community to improve, refactor or even complete it.