Add detector automation

This is a large PR with a lot of new code and a lot of code from #227. I will summarize everything here, even things that have already been summarized in #227.

There are still minor issues to solve, but most of the PR should be ready to review. The minor issues are listed at the end of this (very long, sorry) message.

General considerations

This PR implements the proposal by Austin.

It does so fully in stim, not using cirq, and not using most of the already implemented functions in the TQEC package. This is a deliberate choice as this PR implements a feature that:

would not highly benefit from a cirq intermediary representation,
might very well be outsourced into its own package and distributed separately from the TQEC package to the community eventually.

A lot of code has been taken from #227, either as-is or as a base that has been changed when developing new features.

The code is organized into 4 main problems: the 3 described in this comment and a fourth one that is compiling back the fragments and obtained detectors into a stim.Circuit instance. The following sections highlight the main points used to solve each of these 4 problems.

To illustrate, I will use a simple repetition code of distance 3 and using 5 rounds obtained with:

import stim
circuit = stim.Circuit.generated("repetition_code:memory", distance=3, rounds=5)
# Detail: insert QUBIT_COORDS into the circuit

giving the circuit

QUBIT_COORDS(0) 0
QUBIT_COORDS(1) 1
QUBIT_COORDS(2) 2
QUBIT_COORDS(3) 3
QUBIT_COORDS(4) 4
R 0 1 2 3 4
TICK
CX 0 1 2 3
TICK
CX 2 1 4 3
TICK
MR 1 3
DETECTOR(1, 0) rec[-2]
DETECTOR(3, 0) rec[-1]
REPEAT 4 {
    TICK
    CX 0 1 2 3
    TICK
    CX 2 1 4 3
    TICK
    MR 1 3
    SHIFT_COORDS(0, 1)
    DETECTOR(1, 0) rec[-2] rec[-4]
    DETECTOR(3, 0) rec[-1] rec[-3]
}
M 0 2 4
DETECTOR(1, 1) rec[-2] rec[-3] rec[-5]
DETECTOR(3, 1) rec[-1] rec[-2] rec[-4]
OBSERVABLE_INCLUDE(0) rec[-1]

Sub-problem 1: Splitting the input circuit

The Fragment approach from #227 has been a little bit changed, but the overall idea stayed.

The provided circuit is split into "fragments". A fragment is, loosely speaking, equivalent to the circuit needed to perform one QEC round. In more details, a fragment can either be an instance of Fragment or FragmentLoop.

FragmentLoop is the simplest one: it is a structure that represents REPEAT blocks from stim by storing the loop body (as a list of instances of either Fragment or FragmentLoop) and a number of repetitions.

Fragment represents the "atomic" instances, that cannot be subdivided into sub-fragments. A Fragment instance stores a portion of a stim.Circuit that follow the scheme

(resets) -> (computations) -> measurements

with resets and computations being optional but measurements being a requirement.

This restriction will make more sense in step 2. It basically helps making all the code simpler, at the expense of one more point that need to be handled: combined measurement/reset gates.

Combined measurement/reset gates

In the circuit above, the gate MR implements a measurement directly followed by a reset operation.

These gates are convenient, but they break the pre-condition of Fragment exposed above. In order to restore that pre-condition, input stim.Circuit are transformed by:

splitting combined gates into their non-combined equivalents. For example, MR -> M and then R or MRX -> MX and then RX.

replacing each portion of the circuit that match the following template

R [qubits];
[Annotations / Noisy gates]
REPEAT [N] {
    [Computation gates (no reset, no measurement)]
    M [qubits]
    R [qubits]
    [Annotations / Noisy gates]
}

by the functionally equivalent circuit

REPEAT [N] {
    R [qubits]
    [Annotations / Noisy gates]
    [Computation gates (no reset, no measurement)]
    M [qubits]
}

the only difference being that the last reset of the loop is never applied, which might be an issue in some cases, so we might in the future replace the above circuit by

REPEAT [N] {
    R [qubits]
    [Annotations / Noisy gates]
    [Computation gates (no reset, no measurement)]
    M [qubits]
}
R [qubits];
[Annotations / Noisy gates]

for exact equivalence.

So in the end, users can call split_stim_circuit_into_fragments in order to split any valid stim.Circuit into a list of fragments:

import stim
from tqec.circuit.detectors.utils import (
    split_combined_measurement_reset,
    reorder_resets,
)

circuit = reorder_resets(
    split_combined_measurement_reset(
        stim.Circuit.generated("repetition_code:memory", distance=3, rounds=5)
    )
)

resulting in

R 0 1 2 3 4
TICK
CX 0 1 2 3
TICK
CX 2 1 4 3
TICK
M 1 3
DETECTOR(1, 0) rec[-2]
DETECTOR(3, 0) rec[-1]
TICK
REPEAT 4 {
    R 1 3
    TICK
    CX 0 1 2 3
    TICK
    CX 2 1 4 3
    TICK
    M 1 3
    SHIFT_COORDS(0, 1)
    DETECTOR(1, 0) rec[-2] rec[-4]
    DETECTOR(3, 0) rec[-1] rec[-3]
    TICK
}
M 0 2 4
DETECTOR(1, 1) rec[-2] rec[-3] rec[-5]
DETECTOR(3, 1) rec[-1] rec[-2] rec[-4]
OBSERVABLE_INCLUDE(0) rec[-1]

circuit_in_fragments with Fragment instances in blue boxes and FragmentLoop instances in green boxes and represented in code by:

[
    Fragment(
        circuit=stim.Circuit("""
            R 0 1 2 3 4
            TICK
            CX 0 1 2 3
            TICK
            CX 2 1 4 3
            TICK
            M 1 3
            DETECTOR(1, 0) rec[-2]
            DETECTOR(3, 0) rec[-1]
            TICK
        """)
    ),
    FragmentLoop(
        repetitions=4,
        fragments=[
            Fragment(
                circuit=stim.Circuit("""
                    R 1 3
                    TICK
                    CX 0 1 2 3
                    TICK
                    CX 2 1 4 3
                    TICK
                    M 1 3
                    SHIFT_COORDS(0, 1)
                    DETECTOR(1, 0) rec[-2] rec[-4]
                    DETECTOR(3, 0) rec[-1] rec[-3]
                    TICK
                """)
            )
        ],
    ),
    Fragment(
        circuit=stim.Circuit("""
            M 0 2 4
            DETECTOR(1, 1) rec[-2] rec[-3] rec[-5]
            DETECTOR(3, 1) rec[-1] rec[-2] rec[-4]
            OBSERVABLE_INCLUDE(0) rec[-1]
        """)
    ),
]

Sub-problem 2: Pre-computing important values

Detectors are determined thanks to the knowledge of stabilizer propagation. This means that, in order to hope to automatically compute detectors, we need to know what are the stabilizers that are created, destructed and propagated in each fragment.

This is where the restriction on Fragment from step 1 makes all its sense. As reset gates can only be at the beginning of a Fragment and measurements gates can only be at the end of it, we start by computing two quantities locally on each Fragment:

creation stabilizers are stabilizers that are "created" by reset gates and propagate forward in the circuit represented by the Fragment, until just before the measurements where its propagation is stopped and the resulting propagated stabilizer is stored into a BoundaryStabilizer instance, along with the collapsing operations (here measurements) that the stabilizer will have to go through in the next timestep.
similarly, destruction stabilizers are stabilizers that are "destructed" (or ended) by measurements. They are computed by propagating the stabilizer "destructed" by each measurement backward, and storing the resulting propagated stabilizer just before reaching the resets (or the beginning of the Fragment if there is no reset), storing that information into a BoundaryStabilizer instance, along with the collapsing operations (here resets) that the stabilizer will have to go through in the previous timestep. Another way of viewing destruction stabilizers computation is the following: take the circuit, revert it (not inverting, simply applying the same gates, but in reverse order), change measurements in resets, resets in measurements, and compute the creation stabilizers described above. These are the destruction stabilizers of the initial circuit.

Because we intentionally restrict ourselves to detectors that only involve measurements from the current and previous QEC round (loosely speaking, the current and previous Fragment), we do not have to compute any "propagated" stabilizer, i.e. a structure that would compute and store, for each Fragment a map of input stabilizers and the corresponding output stabilizer.

All this creation/destruction stabilizers are called flows, and stored in FragmentFlows instances.

For FragmentLoop, it is considered as an atomic operation and its creation (resp. destruction) flows are the creation (resp. destruction) flows of the last (resp. first) fragment of its body. These are stored in FragmentLoopFlows instances.

For example, the flows computed on the example of fragments above are:

[
    FragmentFlows(
        creation=[
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={0: "Z"}),
                collapsing_operations=[],
                involved_measurements=[],
            ),
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={0: "Z", 1: "Z", 2: "Z"}),
                collapsing_operations=[PauliString(qubits={1: "Z"})],
                involved_measurements=[
                    RelativeMeasurementLocation(offset=-2, qubit_index=1)
                ],
            ),
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={2: "Z"}),
                collapsing_operations=[],
                involved_measurements=[],
            ),
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={2: "Z", 3: "Z", 4: "Z"}),
                collapsing_operations=[PauliString(qubits={3: "Z"})],
                involved_measurements=[
                    RelativeMeasurementLocation(offset=-1, qubit_index=3)
                ],
            ),
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={4: "Z"}),
                collapsing_operations=[],
                involved_measurements=[],
            ),
        ],
        destruction=[
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={0: "Z", 1: "Z", 2: "Z"}),
                collapsing_operations=[
                    PauliString(qubits={0: "Z"}),
                    PauliString(qubits={1: "Z"}),
                    PauliString(qubits={2: "Z"}),
                ],
                involved_measurements=[
                    RelativeMeasurementLocation(offset=-2, qubit_index=1)
                ],
            ),
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={2: "Z", 3: "Z", 4: "Z"}),
                collapsing_operations=[
                    PauliString(qubits={2: "Z"}),
                    PauliString(qubits={3: "Z"}),
                    PauliString(qubits={4: "Z"}),
                ],
                involved_measurements=[
                    RelativeMeasurementLocation(offset=-1, qubit_index=3)
                ],
            ),
        ],
        total_number_of_measurements=2,
    ),
    FragmentLoopFlows(
        fragment_flows=[
            FragmentFlows(
                creation=[
                    BoundaryStabilizers(
                        stabilizer=PauliString(qubits={0: "Z", 1: "Z", 2: "Z"}),
                        collapsing_operations=[PauliString(qubits={1: "Z"})],
                        involved_measurements=[
                            RelativeMeasurementLocation(offset=-2, qubit_index=1)
                        ],
                    ),
                    BoundaryStabilizers(
                        stabilizer=PauliString(qubits={2: "Z", 3: "Z", 4: "Z"}),
                        collapsing_operations=[PauliString(qubits={3: "Z"})],
                        involved_measurements=[
                            RelativeMeasurementLocation(offset=-1, qubit_index=3)
                        ],
                    ),
                ],
                destruction=[
                    BoundaryStabilizers(
                        stabilizer=PauliString(qubits={0: "Z", 1: "Z", 2: "Z"}),
                        collapsing_operations=[PauliString(qubits={1: "Z"})],
                        involved_measurements=[
                            RelativeMeasurementLocation(offset=-2, qubit_index=1)
                        ],
                    ),
                    BoundaryStabilizers(
                        stabilizer=PauliString(qubits={2: "Z", 3: "Z", 4: "Z"}),
                        collapsing_operations=[PauliString(qubits={3: "Z"})],
                        involved_measurements=[
                            RelativeMeasurementLocation(offset=-1, qubit_index=3)
                        ],
                    ),
                ],
                total_number_of_measurements=2,
            )
        ],
        repeat=4,
    ),
    FragmentFlows(
        creation=[],
        destruction=[
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={0: "Z"}),
                collapsing_operations=[],
                involved_measurements=[
                    RelativeMeasurementLocation(offset=-3, qubit_index=0)
                ],
            ),
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={2: "Z"}),
                collapsing_operations=[],
                involved_measurements=[
                    RelativeMeasurementLocation(offset=-2, qubit_index=2)
                ],
            ),
            BoundaryStabilizers(
                stabilizer=PauliString(qubits={4: "Z"}),
                collapsing_operations=[],
                involved_measurements=[
                    RelativeMeasurementLocation(offset=-1, qubit_index=4)
                ],
            ),
        ],
        total_number_of_measurements=3,
    ),
]

Sub-problem 3: Matching stabilizer flows

This is the main computational step. This PR mostly follows Austin's proposal.

The only real change from #227 is that the function to find a cover has been radically changed. The initial implementation was performing an exhaustive search on all the possible combinations of stabilizers. First, there was an initial filtering on candidates for the cover that was not entirely correct. Removing this filtering increased the number of stabilizers to consider, and blew up the computational cost of finding the cover. I tried to filter again stabilizers, but this time on the assumption that most detectors will be spatially local (which is false for a variety of QEC codes, but true for our initial focus). This locality assumption improved the runtime, but was still not enough, some detector computations taking tens of seconds. So I ended up rephrasing the cover problem as a SAT problem, solved by a specific solver that accept SAT formulations with XOR clauses instead of OR clauses: pycryptosat accessed through the pysat interface. It turns out that this rephrasing allowed to solve any (even non-filtered with more than 40 stabilizers considered for the cover) cover problems in a very small time (not user-noticeable anymore, I have not benchmarked it properly).

Sub-problem 4: re-building the circuit

Re-building the circuit from the fragments is super easy:

def compile_fragments_to_circuit(
    fragments: list[Fragment | FragmentLoop],
) -> stim.Circuit:
    circuit = stim.Circuit()

    for fragment in fragments:
        if isinstance(fragment, Fragment):
            circuit += fragment.circuit
        else:  # isinstance(fragment, FragmentLoop):
            loop_body = compile_fragments_to_circuit(fragment.fragments)
            circuit += loop_body * fragment.repetitions
    return circuit

Computing and inserting detectors is not really more difficult:

def compile_fragments_to_circuit_with_detectors(
    fragments: list[Fragment | FragmentLoop],
    qubit_coords_map: dict[int, tuple[float, ...]],
) -> stim.Circuit:
    flows = build_flows_from_fragments(fragments)
    detectors = match_detectors_from_flows_shallow(flows, qubit_coords_map)

    circuit = stim.Circuit()

    for fragment, detectors in zip(fragments, detectors):
        detectors_circuit = _detectors_to_circuit(detectors, [0.0])
        if isinstance(fragment, Fragment):
            circuit += (
                _remove_last_tick_instruction(fragment.circuit)
                + detectors_circuit
                + _tick_circuit()
            )
        else:  # isinstance(fragment, FragmentLoop):
            shift_circuit = _shift_time_instruction(len(detectors[0].coords))
            loop_body = compile_fragments_to_circuit_with_detectors(
                fragment.fragments, qubit_coords_map
            )
            circuit += (
                _remove_last_tick_instruction(loop_body)
                + shift_circuit
                + detectors_circuit
                + _tick_circuit()
            ) * fragment.repetitions
    return circuit

Issues still present

Missing tests

The code is currently quite well documented, I tried to document thoroughly each and every function / class, but there is no test at all. Most of the tests from #227 can likely be adapted, but way more tests will have to be implemented for all the functions / classes introduced in this PR.

Temporal coordinate of detectors

Currently, detectors only have 0.0 in their temporal coordinate. I am trying to find a nice way to devise the temporal coordinate of each detector. I will definitely have a look at how this is done in #227 in the next few days and see if I can use the same method here.

Awesome! I'll review the code at this weekend :).

I'll also try to review this on the weekend, props for all the work

I will add documentation (if needed) and tests in the next few hours. It might help you getting into it, as this is a large piece of code.

One thing to note is that the input doesn't have to be assumed to be a Stim file with repeat blocks that needs to be parsed into rounds of QEC. Our own tools will be building the circuits, and these tools will produce circuits already packaged into rounds that first reset, interact, then measure.

On Sun, Jun 16, 2024 at 2:13 AM Yiming Zhang @.***> wrote:

@.**** commented on this pull request.

Great job! Thanks for your hard work on this.

I have carefully reviewed the code, although I haven't tested it yet. Overall, the code and documentation are quite good. As you mentioned, the main missing part is the tests. We need these to try out some more practical and complex cases to see if there are any missing parts or bugs.

In src/tqec/circuit/detectors/utils.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641204371:

TICK instructions can only appear at the end of a stim.Circuit

or within the body of a stim.CircuitRepeatBlock.

⬇️ Suggested change

TICK instructions can only appear at the end of a stim.Circuit

or within the body of a stim.CircuitRepeatBlock.

In the yield items, TICK instructions can only appear at the end of a stim.Circuit

or within the body of a stim.CircuitRepeatBlock.

In src/tqec/circuit/detectors/utils.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641206753:

+def _is_measurement(instruction: stim.CircuitInstruction) -> bool:

return instruction.name in ["M", "MR", "MRX", "MRY", "MRZ", "MX", "MY", "MZ"]

Note that MPP instruction might need to be supported in the future if we want to distribute "detector automation" package separately and extend its usage.

In src/tqec/circuit/detectors/construction.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641272808:

detectors = match_detectors_from_flows_shallow(flows, qubit_coords_map)

circuit = stim.Circuit()

for fragment, detectors in zip(fragments, detectors):

⬇️ Suggested change

detectors = match_detectors_from_flows_shallow(flows, qubit_coords_map)

circuit = stim.Circuit()

for fragment, detectors in zip(fragments, detectors):

detectors_from_flows = match_detectors_from_flows_shallow(flows, qubit_coords_map)

circuit = stim.Circuit()

for fragment, detectors in zip(fragments, detectors_from_flows):

Name shadowing in Python always makes me struggle, so I think it's better to make the slight change.

In src/tqec/circuit/detectors/fragment.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641593938:

)

@property

def resets(self) -> list[PauliString]:

"""Get the reset instructions at the front on the Fragment.

Returns:

all the reset instructions that appear at the beginning of the represented

circuit, in the order of appearance, and in increasing qubit order for resets

that are performed in parallel.

"""

return self._resets

@property

def measurements(self) -> list[PauliString]:

"""Get the measurement instructions at the front on the Fragment.

⬇️ Suggested change

"""Get the measurement instructions at the front on the Fragment.

"""Get the measurement instructions at the back on the Fragment.

In src/tqec/circuit/detectors/fragment.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641595306:

"""Split the circuit into fragments.

The provided circuit should check a few pre-conditions:

If there is one measurement (resp. reset) instruction between two TICK

annotation, then only measurement (resp. reset) instructions, annotations

and noisy gates can appear between these two TICK. Any other instruction

will result in an exception being raised.

The circuit should be (recursively if it contains one or more instance of

stim.CircuitRepeatBlock) composed of a succession of layers that should

have the same shape:

starts with zero or more moments containing exclusively reset operations,

continuing with zero or more moments containing any non-collapsing operation

(i.e., anything except reset and measurement operations).

ends with one or more moments containing exclusively measurement operations.

Is this true? By the code, it seems the current fragment will end whenever a single measurement moment is encountered.

In src/tqec/circuit/detectors/flow.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641596070:

destruction=[bs for bs in self.destruction if bs.is_trivial()],

total_number_of_measurements=self.total_number_of_measurements,

)

def try_merge_anticommuting_flows(self):

_try_merge_anticommuting_flows_inplace(self.creation)

_try_merge_anticommuting_flows_inplace(self.destruction)

@.*** +class FragmentLoopFlows:

"""Store stabilizer flows for a FragmentLoop instance.

This class is currently quite dumb and does not provide a sufficient

API for generic stabilizer matching, but is enough for detectors

that only include measurements from the current round and fron the

⬇️ Suggested change

that only include measurements from the current round and fron the

that only include measurements from the current round and from the

In src/tqec/circuit/detectors/match.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641600351:

+

coords: tuple[float, ...]

measurements: frozenset[RelativeMeasurementLocation]

def hash(self) -> int:

return hash(self.measurements)

def eq(self, other: object) -> bool:

if not isinstance(other, MatchedDetector):

return False

if self.measurements != other.measurements:

return False

return numpy.allclose(self.coords, other.coords)

+def match_detectors_from_flows_shallow(

Note that "shallow" works for now but can be a problem when we consider more complex circuits, e.g. the one I included in the extra test cases https://github.com/QCHackers/tqec/blob/e53a50bf4fc30cd91f230b19bbe60a516fce112c/src/tqec/circuit/detector/extra_test_circuits/r%3D12%2Cd%3D3%2Cp%3D0.001%2Cnoise%3DSI1000%2Cb%3DX%2Cstyle%3D3-CZ%2Cq%3D17.stim from #227 https://github.com/QCHackers/tqec/pull/227, where there are two rounds of QEC within the repeat block.

In src/tqec/circuit/detectors/match.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641600896:

flows: pre-computed flows for the fragment of interest. If any detector is

is found, the involved flow(s) will be removed from the provided instance.

⬇️ Suggested change

flows: pre-computed flows for the fragment of interest. If any detector is

is found, the involved flow(s) will be removed from the provided instance.

flows: pre-computed flows for the fragment of interest. If any detector

is found, the involved flow(s) will be removed from the provided instance.

In src/tqec/circuit/detectors/pauli.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641619200:

def intersects(self, other: PauliString) -> bool:

return bool(self._pauli_by_qubit.keys() & other._pauli_by_qubit.keys())

⬇️ Suggested change

def intersects(self, other: PauliString) -> bool:

return bool(self._pauli_by_qubit.keys() & other._pauli_by_qubit.keys())

Duplication of overlaps().

In src/tqec/circuit/detectors/match.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641633746:

Note that this function ignores "trivial" flows to avoid trivial detectors to be

matched on some particular cases (e.g., 1-round repetition code).

I noted that the case "trivial flows result in wanted detectors" did exist in some circuits, look at this https://algassert.com/crumble#circuit=Q(0,0)0;Q(0,1)1;Q(0,2)2;Q(0.5,0.5)3;Q(0.5,1.5)4;Q(0.5,2.5)5;Q(1,0)6;Q(1,1)7;Q(1,2)8;Q(1.5,0.5)9;Q(1.5,1.5)10;Q(1.5,2.5)11;Q(2,0)12;Q(2,1)13;Q(2,2)14;Q(2.5,0.5)15;Q(2.5,1.5)16;R_0_1_2_3_4_5_6_7_8_9_10_11_12_13_14_15_16;TICK;H_1_4_6_9_13_14_15_16;TICK;M_3_5_10_11_4_9_15_16;DT(0.5,0.5,0)rec%5B-8%5D;DT(0.5,2.5,0)rec%5B-7%5D;DT(1.5,1.5,0)rec%5B-6%5D;DT(1.5,2.5,0)rec%5B-5%5D;TICK;R_4_9_15_16_3_5_10_11;TICK;H_3_4_5_9_10_11_15_16;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_0_2_6_7_13;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_3_4_5_7_8_9_10_13_14_16;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_1_7_8_12_14;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_1_3_4_6_8_9_10_11_15;TICK;M_4_5_9_11_3_10_15_16;DT(0.5,0.5,1)rec%5B-8%5D_rec%5B-16%5D;DT(0.5,2.5,1)rec%5B-7%5D_rec%5B-15%5D;DT(1.5,0.5,1)rec%5B-6%5D;DT(1.5,2.5,1)rec%5B-5%5D_rec%5B-13%5D_rec%5B-14%5D;TICK;R_3_10_15_16_4_5_9_11;TICK;H_1_3_4_5_6_8_9_10_11_15_16;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_0_1_7_8_12_14;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_3_4_7_8_9_10_11_13_14_15;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_2_6_7_13;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_3_4_5_9_10_16;TICK;M_3_5_10_11_4_9_15_16;DT(0.5,0.5,2)rec%5B-8%5D;DT(0.5,2.5,2)rec%5B-7%5D_rec%5B-15%5D_rec%5B-16%5D;DT(1.5,0.5,2)rec%5B-6%5D_rec%5B-14%5D;DT(1.5,2.5,2)rec%5B-5%5D_rec%5B-13%5D;DT(0.5,1.5,2)rec%5B-4%5D;DT(1,0.5,2)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,2)rec%5B-2%5D_rec%5B-10%5D;DT(2.5,1.5,2)rec%5B-1%5D_rec%5B-9%5D_rec%5B-11%5D;TICK;R_4_9_15_16_3_5_10_11;TICK;H_3_4_5_9_10_11_15_16;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_0_2_6_7_13;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_3_4_5_7_8_9_10_13_14_16;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_1_7_8_12_14;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_1_3_4_6_8_9_10_11_15;TICK;M_4_5_9_11_3_10_15_16;DT(0.5,0.5,3)rec%5B-8%5D_rec%5B-16%5D;DT(0.5,2.5,3)rec%5B-7%5D_rec%5B-15%5D;DT(1.5,0.5,3)rec%5B-6%5D;DT(1.5,2.5,3)rec%5B-5%5D_rec%5B-13%5D_rec%5B-14%5D;DT(0.5,0.5,4)rec%5B-4%5D;DT(0.5,1.5,3)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,3)rec%5B-2%5D_rec%5B-10%5D_rec%5B-11%5D;DT(2.5,1.5,3)rec%5B-1%5D_rec%5B-9%5D;TICK;R_3_10_15_16_4_5_9_11;TICK;H_1_3_4_5_6_8_9_10_11_15_16;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_0_1_7_8_12_14;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_3_4_7_8_9_10_11_13_14_15;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_2_6_7_13;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_3_4_5_9_10_16;TICK;M_3_5_10_11_4_9_15_16;DT(0.5,0.5,5)rec%5B-8%5D;DT(0.5,2.5,5)rec%5B-7%5D_rec%5B-15%5D_rec%5B-16%5D;DT(1.5,0.5,5)rec%5B-6%5D_rec%5B-14%5D;DT(1.5,2.5,5)rec%5B-5%5D_rec%5B-13%5D;DT(0.5,1.5,5)rec%5B-4%5D;DT(1,0.5,5)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,5)rec%5B-2%5D_rec%5B-10%5D;DT(2.5,1.5,5)rec%5B-1%5D_rec%5B-9%5D_rec%5B-11%5D;TICK;R_4_9_15_16_3_5_10_11;TICK;H_3_4_5_9_10_11_15_16;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_0_2_6_7_13;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_3_4_5_7_8_9_10_13_14_16;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_1_7_8_12_14;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_1_3_4_6_8_9_10_11_15;TICK;M_4_5_9_11_3_10_15_16;DT(0.5,0.5,6)rec%5B-8%5D_rec%5B-16%5D;DT(0.5,2.5,6)rec%5B-7%5D_rec%5B-15%5D;DT(1.5,0.5,6)rec%5B-6%5D;DT(1.5,2.5,6)rec%5B-5%5D_rec%5B-13%5D_rec%5B-14%5D;DT(0.5,0.5,7)rec%5B-4%5D;DT(0.5,1.5,6)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,6)rec%5B-2%5D_rec%5B-10%5D_rec%5B-11%5D;DT(2.5,1.5,6)rec%5B-1%5D_rec%5B-9%5D;TICK;R_3_10_15_16_4_5_9_11;TICK;H_1_3_4_5_6_8_9_10_11_15_16;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_0_1_7_8_12_14;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_3_4_7_8_9_10_11_13_14_15;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_2_6_7_13;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_3_4_5_9_10_16;TICK;M_3_5_10_11_4_9_15_16;DT(0.5,0.5,8)rec%5B-8%5D;DT(0.5,2.5,8)rec%5B-7%5D_rec%5B-15%5D_rec%5B-16%5D;DT(1.5,0.5,8)rec%5B-6%5D_rec%5B-14%5D;DT(1.5,2.5,8)rec%5B-5%5D_rec%5B-13%5D;DT(0.5,1.5,8)rec%5B-4%5D;DT(1,0.5,8)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,8)rec%5B-2%5D_rec%5B-10%5D;DT(2.5,1.5,8)rec%5B-1%5D_rec%5B-9%5D_rec%5B-11%5D;TICK;R_4_9_15_16_3_5_10_11;TICK;H_3_4_5_9_10_11_15_16;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_0_2_6_7_13;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_3_4_5_7_8_9_10_13_14_16;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_1_7_8_12_14;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_1_3_4_6_8_9_10_11_15;TICK;M_4_5_9_11_3_10_15_16;DT(0.5,0.5,9)rec%5B-8%5D_rec%5B-16%5D;DT(0.5,2.5,9)rec%5B-7%5D_rec%5B-15%5D;DT(1.5,0.5,9)rec%5B-6%5D;DT(1.5,2.5,9)rec%5B-5%5D_rec%5B-13%5D_rec%5B-14%5D;DT(0.5,0.5,10)rec%5B-4%5D;DT(0.5,1.5,9)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,9)rec%5B-2%5D_rec%5B-10%5D_rec%5B-11%5D;DT(2.5,1.5,9)rec%5B-1%5D_rec%5B-9%5D;TICK;R_3_10_15_16_4_5_9_11;TICK;H_1_3_4_5_6_8_9_10_11_15_16;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_0_1_7_8_12_14;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_3_4_7_8_9_10_11_13_14_15;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_2_6_7_13;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_3_4_5_9_10_16;TICK;M_3_5_10_11_4_9_15_16;DT(0.5,0.5,11)rec%5B-8%5D;DT(0.5,2.5,11)rec%5B-7%5D_rec%5B-15%5D_rec%5B-16%5D;DT(1.5,0.5,11)rec%5B-6%5D_rec%5B-14%5D;DT(1.5,2.5,11)rec%5B-5%5D_rec%5B-13%5D;DT(0.5,1.5,11)rec%5B-4%5D;DT(1,0.5,11)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,11)rec%5B-2%5D_rec%5B-10%5D;DT(2.5,1.5,11)rec%5B-1%5D_rec%5B-9%5D_rec%5B-11%5D;TICK;R_4_9_15_16_3_5_10_11;TICK;H_3_4_5_9_10_11_15_16;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_0_2_6_7_13;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_3_4_5_7_8_9_10_13_14_16;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_1_7_8_12_14;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_1_3_4_6_8_9_10_11_15;TICK;M_4_5_9_11_3_10_15_16;DT(0.5,0.5,12)rec%5B-8%5D_rec%5B-16%5D;DT(0.5,2.5,12)rec%5B-7%5D_rec%5B-15%5D;DT(1.5,0.5,12)rec%5B-6%5D;DT(1.5,2.5,12)rec%5B-5%5D_rec%5B-13%5D_rec%5B-14%5D;DT(0.5,0.5,13)rec%5B-4%5D;DT(0.5,1.5,12)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,12)rec%5B-2%5D_rec%5B-10%5D_rec%5B-11%5D;DT(2.5,1.5,12)rec%5B-1%5D_rec%5B-9%5D;TICK;R_3_10_15_16_4_5_9_11;TICK;H_1_3_4_5_6_8_9_10_11_15_16;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_0_1_7_8_12_14;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_3_4_7_8_9_10_11_13_14_15;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_2_6_7_13;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_3_4_5_9_10_16;TICK;M_3_5_10_11_4_9_15_16;DT(0.5,0.5,14)rec%5B-8%5D;DT(0.5,2.5,14)rec%5B-7%5D_rec%5B-15%5D_rec%5B-16%5D;DT(1.5,0.5,14)rec%5B-6%5D_rec%5B-14%5D;DT(1.5,2.5,14)rec%5B-5%5D_rec%5B-13%5D;DT(0.5,1.5,14)rec%5B-4%5D;DT(1,0.5,14)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,14)rec%5B-2%5D_rec%5B-10%5D;DT(2.5,1.5,14)rec%5B-1%5D_rec%5B-9%5D_rec%5B-11%5D;TICK;R_4_9_15_16_3_5_10_11;TICK;H_3_4_5_9_10_11_15_16;TICK;CZ_0_3_1_4_2_5_6_9_7_10_13_16;TICK;H_0_2_6_7_13;TICK;CZ_2_4_3_6_5_8_7_9_10_13_14_16;TICK;H_3_4_5_7_8_9_10_13_14_16;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_1_7_8_12_14;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_1_3_4_6_8_9_10_11_15;TICK;M_4_5_9_11_3_10_15_16;DT(0.5,0.5,15)rec%5B-8%5D_rec%5B-16%5D;DT(0.5,2.5,15)rec%5B-7%5D_rec%5B-15%5D;DT(1.5,0.5,15)rec%5B-6%5D;DT(1.5,2.5,15)rec%5B-5%5D_rec%5B-13%5D_rec%5B-14%5D;DT(0.5,0.5,16)rec%5B-4%5D;DT(0.5,1.5,15)rec%5B-3%5D_rec%5B-12%5D;DT(2.5,0.5,15)rec%5B-2%5D_rec%5B-10%5D_rec%5B-11%5D;DT(2.5,1.5,15)rec%5B-1%5D_rec%5B-9%5D;TICK;R_3_10_15_16_4_5_9_11;TICK;H_1_3_4_6_8_9_10_11_15_16;TICK;CZ_0_3_1_4_6_9_7_10_8_11_12_15;TICK;H_0_1_7_8_12_14;TICK;CZ_1_3_4_7_8_10_9_12_11_14_13_15;TICK;H_1_2_4_8_9_11_13;TICK;M_0_1_2_3_4_5_6_7_8_9_10_11_12_13_14_15_16;DT(0.5,2.5,17)rec%5B-12%5D;DT(1,0,17)rec%5B-11%5D_rec%5B-14%5D_rec%5B-17%5D;DT(1,1,17)rec%5B-10%5D_rec%5B-13%5D_rec%5B-14%5D_rec%5B-16%5D;DT(0.5,1.5,17)rec%5B-9%5D_rec%5B-12%5D_rec%5B-13%5D_rec%5B-15%5D_rec%5B-24%5D_rec%5B-25%5D;DT(1.5,2.5,17)rec%5B-6%5D_rec%5B-22%5D;DT(2,0,17)rec%5B-5%5D_rec%5B-8%5D_rec%5B-11%5D;DT(1.5,0.5,17)rec%5B-4%5D_rec%5B-7%5D_rec%5B-8%5D_rec%5B-10%5D_rec%5B-23%5D;DT(2,2,17)rec%5B-3%5D_rec%5B-6%5D_rec%5B-7%5D_rec%5B-9%5D;OI(0)rec%5B-15%5D_rec%5B-16%5D_rec%5B-17%5D for example. You can see there are several R (directly followed by) M patterns at the very beginning and end of the circuit.

However, I do think the circuit can work as well if we remove these patterns. Then we just need to be cautious that we do not take the circuits with this pattern for the tests.

In src/tqec/circuit/detectors/flow.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641637808:

Checking a few invariants that are expected:

1. all the provided flows are defined on the same boundary. This is

checked by comparing the collapsing operations for each anti-commuting

stabilizer and asserting that they are all equal.

for i in range(1, len(collapsing_operations)):

if collapsing_operations[0] != collapsing_operations[i]:

raise TQECException(

"Cannot merge anti-commuting flows defined on different collapsing "

"operations. Found the following difference:\nFlow 0 has the "

"collapsing operations:\n\t"

"\n\t".join(f"- {c}" for c in collapsing_operations[0])

f"\nFlow {i} has the collapsing operations:\n\t"

"\n\t".join(f"- {c}" for c in collapsing_operations[i])

"\n"

)

Is this right? By the construction of BoundaryStabilizer in _build_flows_from_fragment(), the collapsing_operations of a BoundaryStabilizer is the subset of all collapsing operations at the boundary that the stabilizer acts on non-trivially, which can be different for the different flows.

In src/tqec/circuit/detectors/match_utils/sat.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641662965:

if expected_effect == "I":

Both the X and Z effect on that qubit should be OFF (i.e., identity).

solver.add_xor_clause(x_clause_literals, value=False)

solver.add_xor_clause(z_clause_literals, value=False)

Just for a check of my understanding, this branch will never be reached in practice since qubits_to_consider = expected_pauli_string.qubits which already filtered out the identity terms. Is that right?

In src/tqec/circuit/detectors/flow.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641721599:

+ +from tqec.circuit.detectors.boundary import BoundaryStabilizer +from tqec.circuit.detectors.fragment import Fragment, FragmentLoop +from tqec.circuit.detectors.match_utils.cover import (

find_commuting_cover_on_target_qubits_sat, +) +from tqec.circuit.detectors.measurement import get_relative_measurement_index +from tqec.circuit.detectors.pauli import PauliString, pauli_product +from tqec.exceptions import TQECException

+def _anti_commuting_stabilizers_indices(flows: list[BoundaryStabilizer]) -> list[int]:

return [i for i in range(len(flows)) if flows[i].has_anticommuting_operations]

+def _try_merge_anticommuting_flows_inplace(flows: list[BoundaryStabilizer]):

If I understand it correctly, the current implementation does not make the assumption that the anti-commuting flows can be exhausted by the merging process.

This make sense for the first round of a QEC circuit, where the flows from data qubit resets can never satisfy the requirements of exhausted merging since there are non-deterministic stabilizer measurements of the opposite basis. However, within the QEC circuit bulk, does a left-over anti-commuting flow really makes sense? This point is also mentioned by Austin in the proposal:

If there are any left, search for groups of three end stabilizers, and so on. Throw an error if things get too expensive.

What's your opinion of that?

In src/tqec/circuit/detectors/flow.py https://github.com/QCHackers/tqec/pull/249#discussion_r1641743315:

involved_measurements = [

m for m in fragment.measurements if final_stabilizer.overlaps(m)

]

This only preserve the collapsing operations that the stabilizer acts on non-trivially. I'm not sure whether this is intended or by mistake, as it makes the merge of stabilizers too restrictive.

— Reply to this email directly, view it on GitHub https://github.com/QCHackers/tqec/pull/249#pullrequestreview-2120465113, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTADH6CXSJZU7JBBCU3ZHVJLDAVCNFSM6AAAAABJKA6UT2VHI2DSMVQWIX3LMV43YUDVNRWFEZLROVSXG5CSMV3GSZLXHMZDCMRQGQ3DKMJRGM . You are receiving this because you are subscribed to this thread.Message ID: @.***>

One thing to note is that the input doesn't have to be assumed to be a Stim file with repeat blocks that needs to be parsed into rounds of QEC. Our own tools will be building the circuits, and these tools will produce circuits already packaged into rounds that first reset, interact, then measure.

Yes I fully agree. The Fragment pre-conditions have also been thought to be able to implement a method like to_fragment for each Plaquette. And then, I think it should not be a huge challenge to have a dedicated processing part in tqec to take into account the fact that detectors might be spatially local (and so we can only worry about a reduced number of plaquettes/fragments) and the fact that the same detectors will likely appear multiple times on a given circuit (and so finding a way to compute a detector once, and re-use that information over the whole code).

I started reviewing and will complete this tomorrow. One thing I noticed: Since we support python 3.9 we cannot use the new typing builtins.

I started reviewing and will complete this tomorrow. One thing I noticed: Since we support python 3.9 we cannot use the new typing builtins.

Relates to #124. I think from __future__ import annotations should resolve the problem.

If you find a stabilizer in one round that exactly matches a stabilizer in the previous round, then yes, you should remove both. These should never be reused as part of any larger detector. This is one of the key things to do first to reduce the complexity as most of the time it removes most of the stabilizers.

By contrast, when you need to assemble multiple stabilizers (most typical case being multiple individual measurements of data qubits) to cover a single stabilizer, you don't remove the multiple individual stabilizers, but you do remove the single stabilizer. Here the terminating condition is that every stabilizer (including every single data qubit measurement) has been included in at least one detector.

On Tue, Jun 18, 2024 at 6:57 AM Adrien Suau @.***> wrote:

@.**** commented on this pull request.

In src/tqec/circuit/detectors/match.py https://github.com/QCHackers/tqec/pull/249#discussion_r1644517396:

for i in sorted(left_reduced_indices_to_remove, reverse=True):

left_boundary_stabilizers.pop(i)

left_flows.remove_creation(left_boundary_indices_map[i])

This is a real question I also had. @inmzhang https://github.com/inmzhang in #227 https://github.com/QCHackers/tqec/pull/227 did not remove the matched counterparts, so I followed. It seems to work correctly that way, but maybe the stabilizers used to cover should also be considered "used" and removed from the list of stabilizers to consider. Does anyone have an answer to that? If not, I will ask Austin.

— Reply to this email directly, view it on GitHub https://github.com/QCHackers/tqec/pull/249#discussion_r1644517396, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTEQCZE25F2FXR55O2DZIA4FRAVCNFSM6AAAAABJKA6UT2VHI2DSMVQWIX3LMV43YUDVNRWFEZLROVSXG5CSMV3GSZLXHMZDCMRVGYYDOMBVGM . You are receiving this because you commented.Message ID: @.***>

If you find a stabilizer in one round that exactly matches a stabilizer in the previous round, then yes, you should remove both. These should never be reused as part of any larger detector. This is one of the key things to do first to reduce the complexity as most of the time it removes most of the stabilizers. By contrast, when you need to assemble multiple stabilizers (most typical case being multiple individual measurements of data qubits) to cover a single stabilizer, you don't remove the multiple individual stabilizers, but you do remove the single stabilizer. Here the terminating condition is that every stabilizer (including every single data qubit measurement) has been included in at least one detector.

This is very clear, thank you!

Quick checkpoint for this PR.

A few unit-tests are still missing. Coverage from tests obtained with

python -m pytest --cov-report term:skip-covered --cov=src/tqec/circuit/detectors src/tqec/circuit/detectors

reports

---------- coverage: platform linux, python 3.12.3-final-0 -----------
Name                                              Stmts   Miss  Cover
---------------------------------------------------------------------
src/tqec/circuit/detectors/boundary.py               62      6    90%
src/tqec/circuit/detectors/construction.py           47     35    26%
src/tqec/circuit/detectors/construction_test.py      56     45    20%
src/tqec/circuit/detectors/flow.py                  112     67    40%
src/tqec/circuit/detectors/fragment.py              128     15    88%
src/tqec/circuit/detectors/match.py                 118     91    23%
src/tqec/circuit/detectors/match_utils/cover.py      46      7    85%
src/tqec/circuit/detectors/match_utils/sat.py        27      2    93%
src/tqec/circuit/detectors/pauli.py                 103      2    98%
src/tqec/circuit/detectors/utils.py                 211    109    48%
---------------------------------------------------------------------
TOTAL                                              1293    379    71%

In particular, utils.py, match.py, flow.py and construction.py are the main files clearly missing tests. construction.py is important, but does not contain very complex functions, and will be tested with integration tests at the end, so it is not a priority. The other 3 files are important to test as they are quite central in the implementation.

In terms of missing features, I only see the detectors coordinates. Currently, the temporal coordinate of detectors is very poorly handled. If possible, it would be nice to match stim coordinates from stim.Circuit.generated, but I do not think this is easily possible on all edge-cases (the 1-round repetition code being a nice edge-case that will likely never have the same temporal coordinate as the ones used in stim).

Check out this pull request on

See visual diffs & provide feedback on Jupyter Notebooks.

Powered by ReviewNB

I have one remaining issue with that PR: the current code requires a few pre-conditions to be checked by input quantum circuits, and these pre-conditions are not verified by the circuits generated by stim, and changing the generated circuits to verify these conditions is a real pain, lead to a lot of code that is not directly related to the library, and that is too specialised.

One potential goal is to extract the written code out of the tqec package to allow anyone to use it, but the first goal is to apply that code to the specific circuits generated by the tqec package, which we build (so we can guarantee that they check the pre-conditions). Also, for the moment, stim generated circuits are only used as a test input (tests recovered from #227).

Below are the pre-conditions assumed by the library on the input quantum circuit.

1. No combined measurement/reset instruction

Reason: the combined measurement/reset instructions break the assumptions needed to split the input quantum circuit into well defined Fragment/FragmentLoop instances.

Functions implemented to solve that: split_combined_measurement_reset (along with split_combined_measurement_reset_in_moment), reorder_resets, remove_final_resets. Note that the previously-cited functions are large, and are probably the most "complex" functions of the module.

2. `QUBIT_COORDS` instructions should appear for each qubit

Reason: the detector annotations are parameterized by coordinates that depend on the qubits on which the collapsing operations that generated the matching flows are applied to. Without qubit coordinates, the detector annotations would not be parameterized.

Functions implemented to solve that: prepend_qubit_coords_for_repetition_code

3. Last-round measurements on data-qubits should appear in their own moment

Reason: in some very specific cases (mostly the QEC circuits generated by stim for rounds=2), the detector matching functions might output an unwanted detector. For example with the repetition code:

is not a detector we want. Separating the data-qubit measurements in their own final moment would remove that matching flow because they would not be on adjacent fragment anymore (and we only match adjacent fragments together).

Functions implemented to solve that: none yet, but I tried locally, and the function is hard to reason about, hard to implement correctly, and highly specialised to this specific case, which is not really desirable.

4. Other pre-conditions

There are other pre-conditions, but these are checked by stim-generated output, so they are not really the focus here.

So now, after spending nearly two days trying to automatically adapt stim circuits to check the above pre-conditions in order to have a large (and correct) test dataset, I am nearly convinced this is not the right path. 2 reasons for that:

it would have been quicker to simply write down the test circuits by hand,
the first and most important use-case for the moment is to feed tqec-generated circuits to this library, circuits that will check the pre-conditions (because we construct them ourselves).

What would be your opinion w.r.t a test such as the one found in construction_test.py in #227:

even if it requires hard to read and complex code, you prefer to use stim-generated circuits as input?
just have folder that contains valid / invalid circuits (that can be generated by stim and then edited by hand once) and use that folder to test?

A general comment for the preconditions: tKet uses the concept of Predicates for each circuit, which are then checked by optimization passes. They won't be applied if the required predicates for a pass are not met.

For the tests, I prefer option 1. We want to ensure correctness, and if we know the test was correct before, it should be after, no matter what the input is.

I prefer option 2. Specifically, the test cases can include:

Valid circuits that satisfy all the required conditions.
Invalid circuits that can be transformed into valid circuits using the provided functions.
Invalid circuits that our package does not handle and should be avoided or transformed using the user's own boilerplate code. The error messages should clearly indicate the violated conditions.

Hi Adrien,

Going back to the single qubit detectors that you get from a short repetition code, they are valid detectors, so there is no specific reason to write a lot of code to avoid their creation. If you include them, the simulation will still work, indeed will work better.

As such, you could simplify things a bit by allowing these detectors and not forcing final round data qubit measurements to be in a separate moment as I believe your code would work just fine as is without enforcing these things.

Note that the proposed cubic blocks of quantum circuitry include data qubit measurements at the same time as measure qubit measurements in the final round. I think forcing final round data qubit measurements will always be in a separate moment may be going a step too far. It does help with the round by round analysis of detectors, and if you don't do this, you do end up with two rounds of detectors from a single round of measurements when you measure both data and measure qubits, but these are circuits we do actually wish to include in our library of standard circuits.

Best, Austin.

On Mon, Jun 24, 2024, 6:33 AM Yiming Zhang @.***> wrote:

I prefer option 2. Specifically, the test cases can include:

Valid circuits that satisfy all the required conditions.

Invalid circuits that can be transformed into valid circuits using the provided functions.

Invalid circuits that our package does not handle and should be avoided or transformed using the user's own boilerplate code. The error messages should clearly indicate the violated conditions.

— Reply to this email directly, view it on GitHub https://github.com/QCHackers/tqec/pull/249#issuecomment-2186596842, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTB6YEOSRDUPC2CGF7TZJAN35AVCNFSM6AAAAABJKA6UT2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCOBWGU4TMOBUGI . You are receiving this because you commented.Message ID: @.***>

For the tests, I prefer option 1. We want to ensure correctness, and if we know the test was correct before, it should be after, no matter what the input is.

The test was correct, but with a different code from #227 that will not be merged. Also, taking into account the comment from Austin, some circuits generated by stim do not include some detectors that are valid detectors, so we can at least consider the test half-correct.

I kind of lost hope to get the transformation functions correct and simple to understand, and I spent too much time trying to reach this goal. I will try option 2, and if it ends up testing correctly the code, use it in this PR.

Invalid circuits that can be transformed into valid circuits using the provided functions.

I have a strong doubt that we want to provide and maintain such functions. For the moment, I removed them from the code base as they were hard to get right and validate, and were not the goal of that specific PR.

I agree with your point. In #227, I only used those transformation for tests and did not plan to put these functions in the public API. If it's easier to edit the circuits for test by hand or there is any more handy way to generate the circuits, we can definitely discards all of the transformation code and avoid using the circuits generated by stim.

A few things have been changed in the last batch of commits:

some minor fixes (extra TICK inserted at the end of the circuit sometimes, deletion of glue code to transform stim circuits, ...),
a rework of the SAT-solving procedures,
a fix (and internal rework) of BoundaryStabilizer that had an invalid merge implementation,
introduction of functional tests.

In more details.

SAT solving:

Before, the SAT reformulation of the problem of finding anti-commuting terms to merge together to form commuting flows was solved and the first solution returned was picked. This had an issue: the first solution might include a large number of anti-commuting flows and might even include flows that do not interact with each other. The solution, as written in Austin's proposal, is to try to find the smallest number of anti-commuting terms that generate a commuting flow.

This can be done by solving a WMSAT problem, but I could not find a solver that can do that and support XOR clauses. Another solution is to iterate over all the solutions of the SAT reformulation and pick the smallest one. This works for most of the problems, but some instances allow a large (>200.000) number of solutions.

For the moment, this is approximated by iterating over all the solutions for a time t=0.1 and pick the smallest solution found in this time frame. In practice, on the test files, this lead to a maximum of 4 anti-commuting flows being merged together.

BoundaryStabilizer.merge fix:

The merge method was incorrectly including measurements in detectors. This is now fixed.

Functional tests:

As discussed above, some .stim files have been included, and are used for tests.

Note that in some cases the code is returning additional, valid, detectors. These seem to be obtained from matching commuting flows that have been obtained by merging anti-commuting flows. In order to not mark the test as failed in such cases, the test is checking that all the detectors from the original circuit are in the annotated circuit. A few improvements that will eventually need to be implemented:

check detectors recursively in REPEAT block, as this is not done yet,
check that the annotated circuit only contains valid detectors (or in other words, checking if the additional detectors found by the library and that are not in the original circuit are valid or not). I guess this one can be performed through the use of stim directly, by for example calling stim.Circuit.detector_error_model and checking that it does not fail, but I did not have the time to search for such a thing for the moment.

Another question I had was about test files: where should I include them in your opinion?

Hi Adrien,

In the past, when I had found an operator that was being measured that did not commute with neighboring operators, I would use the specific list of neighboring operators to create a graph. This works great when there are two neighboring operators that anti commute. Each of these neighboring operators are then also tested for anti-communication with their neighbors, with edges added. The goal is to then find a cycle with each node only having two edges within the cycle. Taking every second element of this cycle gives you two commuting stabilizers. This may not cover every case you encounter, but does give you a fast algorithm to take care of the majority of cases.

Best, Austin.

On Wed, Jun 26, 2024, 5:32 AM Adrien Suau @.***> wrote:

A few things have been changed in the last batch of commits:

some minor fixes (extra TICK inserted at the end of the circuit sometimes, deletion of glue code to transform stim circuits, ...),

a rework of the SAT-solving procedures,

a fix (and internal rework) of BoundaryStabilizer that had an invalid merge implementation,

introduction of functional tests.

In more details.

SAT solving:

Before, the SAT reformulation of the problem of finding anti-commuting terms to merge together to form commuting flows was solved and the first solution returned was picked. This had an issue: the first solution might include a large number of anti-commuting flows and might even include flows that do not interact with each other. The solution, as written in Austin's proposal, is to try to find the smallest number of anti-commuting terms that generate a commuting flow.

This can be done by solving a WMSAT problem, but I could not find a solver that can do that and support XOR clauses. Another solution is to iterate over all the solutions of the SAT reformulation and pick the smallest one. This works for most of the problems, but some instances allow a large (>200.000) number of solutions.

For the moment, this is approximated by iterating over all the solutions for a time t=0.1 and pick the smallest solution found in this time frame. In practice, on the test files, this lead to a maximum of 4 anti-commuting flows being merged together.

BoundaryStabilizer.merge fix:

The merge method was incorrectly including measurements in detectors. This is now fixed.

Functional tests:

As discussed above, some .stim files have been included, and are used for tests.

Note that in some cases the code is returning additional, valid, detectors. These seem to be obtained from matching commuting flows that have been obtained by merging anti-commuting flows. In order to not mark the test as failed in such cases, the test is checking that all the detectors from the original circuit are in the annotated circuit. A few improvements that will eventually need to be implemented:

check detectors recursively in REPEAT block, as this is not done yet,

check that the annotated circuit only contains valid detectors (or in other words, checking if the additional detectors found by the library and that are not in the original circuit are valid or not). I guess this one can be performed through the use of stim directly, by for example calling stim.Circuit.detector_error_model and checking that it does not fail, but I did not have the time to search for such a thing for the moment.

Another question I had was about test files: where should I include them in your opinion?

— Reply to this email directly, view it on GitHub https://github.com/QCHackers/tqec/pull/249#issuecomment-2191576697, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTGQ7Y36QB6UTX24EM3ZJKYHBAVCNFSM6AAAAABJKA6UT2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCOJRGU3TMNRZG4 . You are receiving this because you commented.Message ID: @.***>

Another question I had was about test files: where should I include them in your opinion?

Since we include the test files inplace next to the source files, it's straightforward to put the test file directory right in the same place. And this is what I did with dae parsing tests.

Hi Adrien, In the past, when I had found an operator that was being measured that did not commute with neighboring operators, I would use the specific list of neighboring operators to create a graph. This works great when there are two neighboring operators that anti commute. Each of these neighboring operators are then also tested for anti-communication with their neighbors, with edges added. The goal is to then find a cycle with each node only having two edges within the cycle. Taking every second element of this cycle gives you two commuting stabilizers. This may not cover every case you encounter, but does give you a fast algorithm to take care of the majority of cases. Best, Austin.

Right now one of the problematic test cases is trying to find a way to combine the anti-commuting flows listed below to obtain something that commutes with the target stabilizer:

Trying to cover Z1*Z3*Z5*Z7*Z9*Z11*Z13*Z15*Z17*Z19*Z21*Z23*Z25*Z27*Z29*Z31*Z33*Z35*Z37*Z39*Z41*Z43*Z45*Z47*Z49*Z51*Z53*Z55*Z57*Z59*Z61*Z63*Z65*Z67*Z69*Z71*Z73*Z75*Z77*Z79 with:
- X0*X9
- X2*X11
- X4*X13
- X6*X15
- X8*X17
- X9*X10*X11
- X11*X12*X13
- X13*X14*X15
- X15*X16*X17
- X9*X18*X27
- X11*X20*X29
- X13*X22*X31
- X15*X24*X33
- X17*X26*X35
- X27*X28*X29
- X29*X30*X31
- X31*X32*X33
- X33*X34*X35
- X27*X36*X45
- X29*X38*X47
- X31*X40*X49
- X33*X42*X51
- X35*X44*X53
- X45*X46*X47
- X47*X48*X49
- X49*X50*X51
- X51*X52*X53
- X45*X54*X63
- X47*X56*X65
- X49*X58*X67
- X51*X60*X69
- X53*X62*X71
- X63*X64*X65
- X65*X66*X67
- X67*X68*X69
- X69*X70*X71
- X63*X72
- X65*X74
- X67*X76
- X69*X78
- X71*X80

The code is "dumb" in the sense that it does not assume any spatial locality and simply check all the available flows.

For the moment I did not understand the algorithm you proposed, I will try to understand it in the next few days.

Hi Adrien,

I see you are shooting for a little more generality than I was :-)

The algorithm I proposed is for a surface code where you break qubits and use the standard subsystem method to create rings of lower weight operators that anticommute with their neighbors.

Regards, Austin.

On Thu, Jun 27, 2024 at 7:28 AM Adrien Suau @.***> wrote:

Hi Adrien, In the past, when I had found an operator that was being measured that did not commute with neighboring operators, I would use the specific list of neighboring operators to create a graph. This works great when there are two neighboring operators that anti commute. Each of these neighboring operators are then also tested for anti-communication with their neighbors, with edges added. The goal is to then find a cycle with each node only having two edges within the cycle. Taking every second element of this cycle gives you two commuting stabilizers. This may not cover every case you encounter, but does give you a fast algorithm to take care of the majority of cases. Best, Austin.

Right now one of the problematic test cases is trying to find a way to combine the anti-commuting flows listed below to obtain something that commutes with the target stabilizer:

Trying to cover Z1Z3Z5Z7Z9Z11Z13Z15Z17Z19Z21Z23Z25Z27Z29Z31Z33Z35Z37Z39Z41Z43Z45Z47Z49Z51Z53Z55Z57Z59Z61Z63Z65Z67Z69Z71Z73Z75Z77*Z79 with:

X0*X9

X2*X11

X4*X13

X6*X15

X8*X17

X9X10X11

X11X12X13

X13X14X15

X15X16X17

X9X18X27

X11X20X29

X13X22X31

X15X24X33

X17X26X35

X27X28X29

X29X30X31

X31X32X33

X33X34X35

X27X36X45

X29X38X47

X31X40X49

X33X42X51

X35X44X53

X45X46X47

X47X48X49

X49X50X51

X51X52X53

X45X54X63

X47X56X65

X49X58X67

X51X60X69

X53X62X71

X63X64X65

X65X66X67

X67X68X69

X69X70X71

X63*X72

X65*X74

X67*X76

X69*X78

X71*X80

The code is "dumb" in the sense that it does not assume any spatial locality and simply check all the available flows.

For the moment I did not understand the algorithm you proposed, I will try to understand it in the next few days.

— Reply to this email directly, view it on GitHub https://github.com/QCHackers/tqec/pull/249#issuecomment-2194869152, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKAXTGWXOHAMQBRWOH3NY3ZJQOSJAVCNFSM6AAAAABJKA6UT2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCOJUHA3DSMJVGI . You are receiving this because you commented.Message ID: @.***>

I think this PR is close to reach its final state.

Right now, test coverage on the tqec.circuit.detectors module returns

---------- coverage: platform linux, python 3.12.3-final-0 -----------
Name                                              Stmts   Miss  Cover
---------------------------------------------------------------------
src/tqec/circuit/detectors/boundary.py               73      6    92%
src/tqec/circuit/detectors/construction.py           53      8    85%
src/tqec/circuit/detectors/flow.py                  114     13    89%
src/tqec/circuit/detectors/fragment.py              104      6    94%
src/tqec/circuit/detectors/match.py                 138      6    96%
src/tqec/circuit/detectors/match_utils/cover.py      55      6    89%
src/tqec/circuit/detectors/match_utils/sat.py        27      2    93%
src/tqec/circuit/detectors/measurement.py            14      0   100%
src/tqec/circuit/detectors/pauli.py                 103      2    98%
src/tqec/circuit/detectors/predicates.py             30      2    93%
src/tqec/circuit/detectors/utils.py                 125     12    90%
---------------------------------------------------------------------
TOTAL                                               836     63    92%

which, I think, is enough to not block the merge.

The anti-commuting merging research leading to a large number of solutions in the reformulated SAT problem might not even be an issue as our goal will be to reduce as much as possible the size of the circuits that will be provided to this function (see #259). My point of view is that we can merge as-is, knowing that this part might be a performance bottleneck, and if we find out later that we need more performance, we open a new issue.

@inmzhang and @Gistbatch would you mind re-doing a quick round of review when you have the time?

Yeah I'll do the review at tomorrow.

I'll review tomorrow :+1:

Thanks for your reviews @Gistbatch and @inmzhang !

QCHackers / tqec