3
$\begingroup$

Does anyone know of any tools that calculate the distance of an arbitrary stabilizer code?

I have some primitive ways of doing this which can handle codes up to ~32 stabilizers (number of qubits a small multiple of that) but now I need to do the same for larger codes.

$\endgroup$

2 Answers 2

3
$\begingroup$

I have written code for this. I've yet to rigorously unit test it though. What's the code and what are the length and dimension? MAGMA generally requires n < 100. I have gone up to n = 421.

$\endgroup$
7
  • 1
    $\begingroup$ Sorry, I added an answer because I don't have enough rep to add a comment. I'm only vaguely familiar with HaPPY. I don't know it well enough to extract a series of stabilizer matrices for it. If you do, you should consider writing that function and adding it to the coding theory library I'm writing github.com/esabo/CodingTheory. I've been rewriting the quantum min dist function for the past two days though, so the current branch there won't work. Later in the week it'd be up. But if you can provide explicit matrices I can test it. $\endgroup$
    – esabo
    Aug 16, 2022 at 18:11
  • $\begingroup$ Some examples to test your MAGMA code would be trying to calculate concatenated codes. $[[5,1,3]]$ concatenated by itself should give a $[[25,1,9]]$ code (this I can check already). If you concatenate the 25 qubit code by itself that should give you a $[[625,1,81]]$ code; is this something you can calculate? how long would it take? $\endgroup$
    – unknown
    Aug 16, 2022 at 18:13
  • $\begingroup$ A length 625 code will probably take a while. It takes 30 minutes and 2 GB to check the length 421 code. I do it by constructing a graph (trellis) which represents the code. Right now I have it construct the whole graph then find the min path through it. This requires a lot of memory. What I need to do is construct the graph piece-by-piece and then GC the processed pieces to keep the memory footprint in check. Then I could do it... $\endgroup$
    – esabo
    Aug 16, 2022 at 18:20
  • $\begingroup$ +1 for the github link. It looks like a nice package but I don't know why you're going with Julia. I use combinations of C,GAP, and python for what I do. I'll see if I can upload some stabilizer codes on github to test. $\endgroup$
    – unknown
    Aug 16, 2022 at 18:22
  • 1
    $\begingroup$ MAGMA, for the record, maps the additive code to a classical linear code and then uses the standard Brouver-Zimmerman algorithm. I plan on adding that algorithm to my library later as well. The papers by Grassl and Greg White's dissertation are excellent references on how this is done and why it would take so long. $\endgroup$
    – esabo
    Aug 16, 2022 at 18:22
3
$\begingroup$

You can use stim's "undetectable logical error" searching functionality to bound the distance of a stabilizer code. You just need to convert the stabilizer code into a circuit that implements it. Here's my attempt at it:

import stim
from typing import List


def distance_of_stabilizer_code(
        stabilizers: List[stim.PauliString],
        logical_x: stim.PauliString,
        logical_z: stim.PauliString) -> int:
    circuit = stabilizer_code_to_phenomenological_noise_circuit(stabilizers, logical_x, logical_z)
    error_mechanisms = circuit.search_for_undetectable_logical_errors(
        # For bigger codes, you will likely want to do a truncated search where these parameters
        # are tuned to only explore smaller potential errors.
        dont_explore_edges_increasing_symptom_degree=False,
        dont_explore_detection_event_sets_with_size_above=9999,
        dont_explore_edges_with_degree_above=9999,

        canonicalize_circuit_errors=True,
    )
    return len(error_mechanisms)


def stabilizer_code_to_phenomenological_noise_circuit(
        stabilizers: List[stim.PauliString],
        logical_x: stim.PauliString,
        logical_z: stim.PauliString) -> stim.Circuit:
    num_qubits = len(logical_x)
    assert len(logical_z) == len(logical_x)
    assert all(len(stabilizer) == num_qubits for stabilizer in stabilizers)

    circuit = stim.Circuit()

    # Entangle observables with a noiseless ancilla so that they can be simultaneously tested.
    logical_xx = logical_x + stim.PauliString("X")
    logical_zz = logical_z + stim.PauliString("Z")
    measure_stabilizer(logical_xx, out=circuit)
    circuit.append("OBSERVABLE_INCLUDE", [stim.target_rec(-1)], 0)
    measure_stabilizer(logical_zz, out=circuit)
    circuit.append("OBSERVABLE_INCLUDE", [stim.target_rec(-1)], 1)
    circuit.append("TICK")

    # Project stabilizers.
    for stabilizer in stabilizers:
        measure_stabilizer(stabilizer, out=circuit)
    circuit.append("TICK")

    # Apply noise.
    circuit.append("DEPOLARIZE1", range(num_qubits), 1e-3)
    circuit.append("TICK")

    # Measure after noise and compare to before noise.
    for stabilizer in stabilizers:
        measure_stabilizer(stabilizer, out=circuit)
    for k in range(len(stabilizers)):
        circuit.append("DETECTOR", [stim.target_rec(-1 - k),
                                    stim.target_rec(-1 - k - len(stabilizers))])
    circuit.append("TICK")

    measure_stabilizer(logical_xx, out=circuit)
    circuit.append("OBSERVABLE_INCLUDE", [stim.target_rec(-1)], 0)
    measure_stabilizer(logical_zz, out=circuit)
    circuit.append("OBSERVABLE_INCLUDE", [stim.target_rec(-1)], 1)

    return circuit


def measure_stabilizer(stabilizer: stim.PauliString, *, out: stim.Circuit) -> None:
    targets = []
    for q, p in enumerate(stabilizer):
        if p == 1:
            targets.append(stim.target_x(q))
        elif p == 2:
            targets.append(stim.target_y(q))
        elif p == 3:
            targets.append(stim.target_z(q))
        if p != 0:
            targets.append(stim.target_combiner())
    targets.pop()
    out.append("MPP", targets)

I tested it on the perfect 5 qubit code, confirming the distance was 3:

distance_of_perfect_5_qubit_code = distance_of_stabilizer_code(
    stabilizers=[
        stim.PauliString("XZZ_Z"),
        stim.PauliString("XXXZ_"),
        stim.PauliString("_ZXXX"),
        stim.PauliString("Z_ZZX"),
    ],
    logical_x=stim.PauliString("X_X_X"),
    logical_z=stim.PauliString("_ZZZ_"),
)
print(distance_of_perfect_5_qubit_code)
# prints 3

Here's the circuit it generates for that code, by the way:

MPP X0*X2*X4*X5
OBSERVABLE_INCLUDE(0) rec[-1]
MPP Z1*Z2*Z3*Z5
OBSERVABLE_INCLUDE(1) rec[-1]
TICK
MPP X0*Z1*Z2*Z4 X0*X1*X2*Z3 Z1*X2*X3*X4 Z0*Z2*Z3*X4
TICK
DEPOLARIZE1(0.001) 0 1 2 3 4
TICK
MPP X0*Z1*Z2*Z4 X0*X1*X2*Z3 Z1*X2*X3*X4 Z0*Z2*Z3*X4
DETECTOR rec[-1] rec[-5]
DETECTOR rec[-2] rec[-6]
DETECTOR rec[-3] rec[-7]
DETECTOR rec[-4] rec[-8]
TICK
MPP X0*X2*X4*X5
OBSERVABLE_INCLUDE(0) rec[-1]
MPP Z1*Z2*Z3*Z5
OBSERVABLE_INCLUDE(1) rec[-1]

Note that you can also use stim.Circuit.detector_error_model() to get what is effectively a tanner graph for the code, and then feed that into some other tool.

$\endgroup$
4
  • $\begingroup$ This does seem to work; it gets the right distance for [[5,1,3]] in seconds. The python code seems to be limitted to 1 logical x/z; will this approach work for more general case? for example [[8,3,3]] code. I'll try larger codes later; how large a code (number of qubits and number of logicals) do you expect this to work for? $\endgroup$
    – unknown
    Aug 17, 2022 at 3:12
  • $\begingroup$ it seems to hit a limit at $n \leq 15$. I get this error message "error_mechanisms = circuit.search_for_undetectable_logical_errors( ValueError: An error case in a composite error exceeded that max supported number of symptoms (<=15)." $\endgroup$
    – unknown
    Aug 17, 2022 at 3:22
  • $\begingroup$ @unknown Hmmm... okay, so this is a complete hack of a workaround, but if you replace DEPOLARIZE1 with an X_ERROR then a Y_ERROR then a Z_ERROR you will bypass the part of the code that has that limit. Note that the limit has to do with the number of stabilizers flipped by one depolarizing error, not the total number of stabilizers. $\endgroup$ Aug 17, 2022 at 5:28
  • 1
    $\begingroup$ @unknown (btw that is a bug and I will fix it github.com/quantumlib/Stim/issues/332 ) $\endgroup$ Aug 17, 2022 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.