Decoding Quantum Low Density Parity Check Codes

00:49:52
https://www.youtube.com/watch?v=b9N2Ps3FTto

Summary

TLDRJoschka Roffe's presentation provides a comprehensive overview of quantum LDPC codes and their significance in quantum computation. LDPC codes can offer a much more efficient alternative to surface codes, requiring significantly fewer physical qubits. Roffe discusses the structure of LDPC codes, how they can be derived from classical codes, and presents the challenges faced in decoding them. The talk covers the theoretical underpinnings of classical error correction, the complexities of quantum error correction, and the vital role of stabilizers in identifying and correcting errors. Additionally, Roffe outlines the existing techniques for decoding, such as belief propagation, and introduces concepts like circuit-level noise and trapping sets that complicate decoding efforts. The necessity for ongoing research into more efficient decoding algorithms is emphasized as an open problem in the field, highlighting the importance of further innovation in quantum error correction methods.

Takeaways

  • 🧩 Quantum LDPC codes can significantly reduce qubit requirements in quantum computing.
  • 💡 They can be decoded using techniques based on classical error correction methods.
  • 🔍 Trapping sets can complicate decoding by leading to failures in error correction protocols.
  • 📈 Belief propagation, although efficient, encounters challenges with complex noise models.
  • 🔗 OSD adds complexity but is crucial for improving decoding accuracy in quantum systems.
  • ⚙️ Circuit-level noise impacts error propagation and requires detailed decoding graphs.
  • 💻 Ongoing research is vital for developing more efficient decoders for practical quantum computers.

Timeline

  • 00:00:00 - 00:05:00

    The introduction to the tutorial on decoding quantum LDPC codes emphasizes the efficiency benefits over traditional surface codes, potentially reducing the number of physical qubits needed per logical qubit significantly. Various quantum computing methods that can utilize such codes are discussed, including silicon spin qubits and ion traps.

  • 00:05:00 - 00:10:00

    A brief overview of quantum LDPC codes is presented, explaining their error-correcting capabilities and differences from surface codes. The speaker will outline a plan to delve into both classical and quantum error correction concepts, and explore the decoding challenges for quantum LDPC codes using a belief propagation approach.

  • 00:10:00 - 00:15:00

    The section covers classical binary error correction codes and how they can be visually represented as Tanner graphs. The relationship between codewords and a parity check matrix is outlined, showcasing how errors can be detected using syndrome measurements through the graph-based representation.

  • 00:15:00 - 00:20:00

    Shifting focus to quantum error correction, the discourse highlights additional challenges, specifically the need to handle phase flip errors along with bit flip errors. The concept of stabilizer codes is introduced, and the mechanics of syndrome measurement and recovery operations are explained to demonstrate the quantum decoding cycle.

  • 00:20:00 - 00:25:00

    The discussion elaborates on the CSS stabilizer codes, highlighting their ability to separately address bit flip and phase flip errors, using parity check matrices to define error recovery operations. The talk also introduces examples such as the Steane code and describes how this class of codes aids in the design of quantum error correction protocols.

  • 00:25:00 - 00:30:00

    The talk then transitions to describing the decoding problem in the simplest error model, analyzing X and Z error syndromes separately to derive recovery operations, emphasizing the importance of a rapid and efficient decoding process for practical quantum computing applications.

  • 00:30:00 - 00:35:00

    The decoding methods are evaluated, contrasting belief propagation with traditional surface code decoders, like minimum weight perfect matching. The benefits of belief propagation as a general decoding algorithm applicable to any sparse graph are outlined, paving the way for the following detailed technical analyses.

  • 00:35:00 - 00:40:00

    A deeper exploration of belief propagation is introduced, detailing its operation through message-passing on Tanner graphs, which allows for efficient probability distributions to be computed in decoding scenarios, enhancing the understanding of the error estimation process in quantum LDPC codes.

  • 00:40:00 - 00:49:52

    The final sections address the integration of order statistics with belief propagation, showing how this hybrid approach can significantly improve decoding performance while facing challenges from circuit level noise introduced in quantum systems. The runtime complexities of the various components are considered to ascertain practical applications in real-world quantum error correction strategies.

Show more

Mind Map

Video Q&A

  • What are quantum LDPC codes used for?

    Quantum LDPC codes are used to perform quantum computation more efficiently than traditional methods like surface codes.

  • How many physical qubits does a quantum LDPC code require per logical qubit?

    It is estimated that a quantum LDPC code could reduce the requirement to around 50 physical qubits per logical qubit.

  • What is the primary decoding technique discussed in the video?

    The primary decoding technique discussed is belief propagation, enhanced with order statistics decoding.

  • What are trapping sets in quantum error correction?

    Trapping sets refer to configurations of qubit errors that lead to decoding failures, often due to the presence of cycles.

  • What limitations does belief propagation face in quantum codes?

    Belief propagation can struggle with complex noise models and is less effective in non-tree-like structures.

  • What is the challenge of using OSD with belief propagation?

    The challenge is that OSD introduces cubic complexity due to matrix inversion, making it slower in practice.

  • What is the open problem in quantum LDPC code decoding?

    The open problem is to improve or find an alternative to OSD to make decoders more efficient.

  • Can common decoding algorithms for surface codes be used for quantum LDPC codes?

    No, traditional surface code decoders like union find and minimum weight perfect matching are not applicable due to the lack of matching properties in quantum LDPC codes.

  • What algorithm benefits from the structure of sparse graphs in decoding?

    Belief propagation is an efficient algorithm that leverages the structure of sparse graphs for decoding.

  • What are the future directions suggested for quantum error correction?

    Future research may build on general classical algorithms or integrate machine learning techniques to improve decoding performance.

View more video summaries

Get instant access to free YouTube video summaries powered by AI!
Subtitles
en
Auto Scroll:
  • 00:00:00
  • 00:00:32
    MODERATOR: Hey.
  • 00:00:33
    Welcome back, everybody.
  • 00:00:34
    So this is the second talk of today,
  • 00:00:36
    and we are very happy to have Joschka Roffe giving us
  • 00:00:39
    a tutorial on how to decode quantum LDPC codes.
  • 00:00:41
  • 00:00:47
    JOSCHKA ROFFE: OK.
  • 00:00:47
    Thanks for the intro.
  • 00:00:49
    So this talk will be a high level introduction
  • 00:00:51
    to decoding quantum LDPC codes.
  • 00:00:56
    OK.
  • 00:00:57
    So I guess, why do we want to use quantum LDPC codes?
  • 00:01:00
    And the main motivation is that we could potentially
  • 00:01:03
    do quantum computation much more efficiently
  • 00:01:05
    than is possible with the service codes.
  • 00:01:08
    So with the service code, it's been
  • 00:01:09
    estimated that we might need about a thousand
  • 00:01:12
    physical qubits per logical qubit,
  • 00:01:14
    whereas with quantum LDPC codes, this
  • 00:01:16
    could be reduced considerably, perhaps to something like 50
  • 00:01:19
    qubits per logical qubits.
  • 00:01:22
    The disadvantage, of course, is that we
  • 00:01:24
    go from a nice, structured layout of the surface code
  • 00:01:28
    to something that looks like this pile of spaghetti.
  • 00:01:30
    So we need something that can perform long range
  • 00:01:34
    interactions.
  • 00:01:37
    OK.
  • 00:01:37
    And fortunately there are various quantum computing
  • 00:01:39
    devices being developed around the world that
  • 00:01:42
    will enable this.
  • 00:01:43
    So examples include silicon spin qubits, neutral atoms,
  • 00:01:46
    as we're seeing from the recent QuEra experiments.
  • 00:01:49
    Ion traps, in principle, have the ability
  • 00:01:51
    to perform arbitrary qubit-qubit interactions
  • 00:01:54
    within the traps themselves.
  • 00:01:56
    And I didn't used to include superconducting qubits
  • 00:01:58
    on this list, but recent experiments or recent proposals
  • 00:02:02
    from IBM and other groups have shown
  • 00:02:04
    that it would be, in principle, possible to perform
  • 00:02:07
    beyond nearest neighbor interactions using
  • 00:02:10
    3D integration and similar techniques.
  • 00:02:12
  • 00:02:14
    OK.
  • 00:02:15
    So what is a quantum LDPC code?
  • 00:02:16
    So this was nicely explained in the previous slide,
  • 00:02:19
    but a bit of redundancy never does any harm.
  • 00:02:22
    So a quantum LDPC code is an error correction code
  • 00:02:26
    where each qubit is connected to a bounded number
  • 00:02:28
    of stabilizers.
  • 00:02:30
    So if we take this definition at face value,
  • 00:02:32
    then technically speaking, the surface code
  • 00:02:34
    is also a quantum low density parity check code
  • 00:02:36
    because each qubit in surface code
  • 00:02:38
    is only connected to at most four stabilizers.
  • 00:02:42
    However, what we usually mean in practice
  • 00:02:43
    when we refer to a quantum LDPC code is one of these codes
  • 00:02:48
    where we construct the code using a product construction
  • 00:02:52
    or otherwise where there's usually some sort of randomness
  • 00:02:54
    in the construction.
  • 00:02:56
    And this gives rise to the quantum
  • 00:02:58
    low density parity check codes that
  • 00:02:59
    have the good encoding densities and nice distance scaling
  • 00:03:02
    properties as you increase the size of the code.
  • 00:03:04
  • 00:03:08
    OK.
  • 00:03:08
    So just to give a quick overview of the talk.
  • 00:03:13
    So I'll start off with some background.
  • 00:03:14
    So go over the classical code, classical binary code
  • 00:03:18
    formulism, the telegraph way of representing this,
  • 00:03:22
    and then explain how we can represent our quantum codes
  • 00:03:26
    in terms of pairs of classical codes via the CSS stabilizer
  • 00:03:30
    framework.
  • 00:03:31
    Following this we'll have all the background
  • 00:03:33
    we need to understand the quantum decoding problem,
  • 00:03:35
    and then I'll go on to explain how this can be tackled
  • 00:03:38
    with a modified form of the classical belief propagation
  • 00:03:42
    decoder called belief propagation, plus ordered
  • 00:03:44
    statistics decoding.
  • 00:03:47
    Following this, I'll talk briefly about circuit level
  • 00:03:49
    noise before going on to discuss the open problem
  • 00:03:53
    within the field, which is how we go beyond this belief
  • 00:03:57
    propagation plus order statistics decoder
  • 00:03:58
    and build a truly efficient decoder that
  • 00:04:01
    could, in principle, be used on a real device.
  • 00:04:03
  • 00:04:07
    OK.
  • 00:04:08
    So just to recap this again.
  • 00:04:11
    So a binary linear code, a classical binary
  • 00:04:15
    linear code is a redundant mapping from a k bit data
  • 00:04:18
    string to an n bit code word.
  • 00:04:20
    So here we have an example for the three bit repetition code.
  • 00:04:23
    This maps a single bit to three bits.
  • 00:04:27
    So 0 to 000 and 1 to 111.
  • 00:04:31
    And any binary linear code can be represented
  • 00:04:33
    in terms of a parity check matrix, which
  • 00:04:35
    is defined such that all the code
  • 00:04:37
    words are in its null space.
  • 00:04:39
    So if the code word is uncorrupted, so it's just 000,
  • 00:04:43
    then when we multiply it by the parity check matrix,
  • 00:04:46
    we just map to the zero vector so we know that
  • 00:04:48
    nothing's wrong.
  • 00:04:49
    However, if our code word is corrupted,
  • 00:04:53
    then it no longer maps to the zero code word
  • 00:04:55
    and we get a so-called nontrivial syndrome that
  • 00:04:57
    tells us that something's gone wrong with our encoding,
  • 00:05:00
    and we have to do something about it.
  • 00:05:02
    And a nice way of representing binary linear codes
  • 00:05:05
    of this type is with a Tanner graph, which we saw
  • 00:05:08
    explained in the previous talk.
  • 00:05:11
    I like to draw them like this where the round nodes represent
  • 00:05:14
    the bits which map to the columns of the parity check
  • 00:05:18
    matrix, and the square nodes represent
  • 00:05:20
    the parity checks which are the rows of this matrix.
  • 00:05:26
    And the rule is that each parity check,
  • 00:05:30
    when you sum over the bits that it's connected to,
  • 00:05:32
    that system should be equal to zero.
  • 00:05:35
    OK?
  • 00:05:36
    So if we set the bit nodes to be 111, so the second code word,
  • 00:05:41
    then we see that this parity check, for example,
  • 00:05:44
    is satisfied because 1 plus 1 mod 2 is zero.
  • 00:05:48
    However, if we then flip a qubit--
  • 00:05:50
    sorry.
  • 00:05:51
    A bit, in this case.
  • 00:05:53
    Then this check is no longer satisfied
  • 00:05:56
    and we get a non-zero syndrome.
  • 00:05:59
    OK.
  • 00:06:00
    So that's classical error correction.
  • 00:06:02
    Now on to quantum error correction.
  • 00:06:04
    So as with many things with quantum computing,
  • 00:06:06
    things get more complicated and annoying.
  • 00:06:09
    For quantum error correction, the specific problem
  • 00:06:11
    we're faced with is the fact that we
  • 00:06:13
    have an additional error type.
  • 00:06:14
    So in a very simplistic way of looking at things,
  • 00:06:17
    in classical error correction we only really never need
  • 00:06:19
    to worry about bit flip errors.
  • 00:06:21
    In quantum error correction, we have an additional error type
  • 00:06:24
    to worry about, which is the phase flip.
  • 00:06:26
    So we can think of this as being a flip
  • 00:06:31
    around the axis of the block sphere
  • 00:06:32
    that's perpendicular to the one that gives you bit flips.
  • 00:06:35
    OK?
  • 00:06:35
    So any quantum error correction code
  • 00:06:37
    has to have the ability to detect and correct
  • 00:06:40
    both of these error types.
  • 00:06:42
    OK.
  • 00:06:42
    And the way that we can do this is with a so-called stabilizer
  • 00:06:45
    code.
  • 00:06:46
    Here the idea is that we create an entangled logical state,
  • 00:06:49
    and then we measure sequences of Pauli operators on the state
  • 00:06:53
    that we can think of--
  • 00:06:54
    that we call stabilizers, and we can
  • 00:06:56
    think of these as the quantum analog of a parity check
  • 00:07:00
    measurement.
  • 00:07:01
    So these stabilizer measurements are measured out
  • 00:07:04
    via non-destructive projective measurement via this
  • 00:07:09
    by an auxiliary qubit.
  • 00:07:11
    These are measured out to give us a syndrome.
  • 00:07:13
    The syndrome is passed to a decoder,
  • 00:07:15
    which is just an algorithm run on a classical computer.
  • 00:07:19
    This tells us what the best recovery operation
  • 00:07:22
    is given the measured syndrome.
  • 00:07:24
    And then we can then apply that recovery operation
  • 00:07:26
    and hopefully restore our quantum information
  • 00:07:28
    to its uncorrupted state.
  • 00:07:30
    So this is the full decoding cycle,
  • 00:07:32
    and the important thing is that we do this full operation,
  • 00:07:36
    so stabilizer measurement, decoding, and recovery
  • 00:07:40
    within a time frame that's shorter than the time
  • 00:07:42
    it takes for the qubits to decode.
  • 00:07:46
    OK?
  • 00:07:47
    And we're going to focus on a specific type of stabilizer
  • 00:07:50
    code called the CSS stabilizer codes.
  • 00:07:56
    These are a type of stabilizer code
  • 00:07:58
    where you can separate out the detection of bit flips
  • 00:08:02
    and phase flips into separate stabilizer extraction
  • 00:08:05
    processes.
  • 00:08:06
    You then get a separate syndrome readout
  • 00:08:10
    for a bit flip errors, and another bit syndrome
  • 00:08:13
    readout for phase flip errors.
  • 00:08:14
    They can then be decoded separately
  • 00:08:16
    to give you two recovery operations.
  • 00:08:18
  • 00:08:20
    OK.
  • 00:08:21
    And the reason why we like to focus
  • 00:08:22
    on this particular subclass of stabilizer codes, this CSS
  • 00:08:29
    subclass, is that it provides a nice way
  • 00:08:32
    of representing your quantum code
  • 00:08:34
    as a pair of classical codes.
  • 00:08:36
    So you can think of one of these CSS codes
  • 00:08:39
    as being described or being a combination
  • 00:08:42
    of two classical codes described by two parity check matrices.
  • 00:08:46
    So one parity check matrix that detects
  • 00:08:48
    phase flip errors and another that detects bit flip errors.
  • 00:08:52
    OK.
  • 00:08:53
    So a famous example of one of these codes
  • 00:08:55
    is the Steane 7,1,3 Code.
  • 00:08:56
    This encodes one logical qubits in seven,
  • 00:08:59
    and it's defined so that both this Hx and Hz components are
  • 00:09:03
    the classical Hamming codes.
  • 00:09:04
    And just like with the classical telegraph,
  • 00:09:08
    we can create a quantum telegraph.
  • 00:09:10
    So we have our seven qubits here, we add three stabilizers
  • 00:09:14
    to detect phase flips, and then we
  • 00:09:15
    can also add an additional three stabilizers
  • 00:09:18
    to detect bit flips.
  • 00:09:19
  • 00:09:22
    OK.
  • 00:09:23
    So this provides a nice way of viewing
  • 00:09:25
    the construction of quantum codes
  • 00:09:27
    in terms of the classical coding framework.
  • 00:09:30
    Unfortunately it is impossible just
  • 00:09:32
    to select your two favorite codes as the Hx and Hz matrix,
  • 00:09:36
    because these Hx and Hz matrices actually
  • 00:09:38
    correspond to physical operations
  • 00:09:40
    that we measure on our quantum states.
  • 00:09:42
    So when we're measuring the observables on a quantum state,
  • 00:09:48
    we have to make sure that they commute.
  • 00:09:51
    And we can make sure that this property is satisfied in terms
  • 00:09:55
    of the CSS formalism simply by checking that this property is
  • 00:09:59
    satisfied.
  • 00:09:59
    I.e. when we multiply the matrix by the transpose of the matrix,
  • 00:10:04
    we map to the zero vector.
  • 00:10:06
    So this is a challenge in designing quantum codes
  • 00:10:09
    because finding pairs of codes that give us this property is
  • 00:10:12
    not always easy.
  • 00:10:14
    So this is where the product constrictions come in,
  • 00:10:16
    and we can think of these as being
  • 00:10:18
    a recipe for turning classical codes into quantum codes.
  • 00:10:22
    So here's an explicit example.
  • 00:10:24
    So here are two classical codes, and I've represented the parity
  • 00:10:28
    check matrix using this image.
  • 00:10:29
    By each black pixel it's a one in the parity check matrix,
  • 00:10:33
    and the blue background just represents all the locations
  • 00:10:35
    where there's a zero.
  • 00:10:37
    So you can see that both of these parity
  • 00:10:39
    check matrices are actually two copies of the same parity check
  • 00:10:42
    matrix.
  • 00:10:42
    But we can see it's sparse because the vast majority
  • 00:10:46
    of the pixels are blue.
  • 00:10:48
    OK?
  • 00:10:49
    And we can put it through a product construction
  • 00:10:52
    to turn it into a CSS code.
  • 00:10:54
    And this gives us two Hx and Hz matrices that look like this.
  • 00:11:00
    So we go from this gives us a 4, 16, 18, 20 code.
  • 00:11:04
    And there are two things I want you to note about this.
  • 00:11:06
    First of all, the Hx and the Hz matrix are somewhat bigger.
  • 00:11:09
    In this case, we've increased the number of bits
  • 00:11:13
    necessary by a factor of about eight.
  • 00:11:15
    The second thing to notice is that the Hx and Hz
  • 00:11:18
    matrices are still sparse.
  • 00:11:20
    So they're still adding the seed codes,
  • 00:11:21
    and then can in principle be decoded
  • 00:11:23
    using any existing classical technique.
  • 00:11:26
  • 00:11:29
    OK.
  • 00:11:31
    So in the first instance, it's always
  • 00:11:33
    useful to study the decoding problem
  • 00:11:36
    in the simplest possible error model.
  • 00:11:38
    We call this the code capacity error model.
  • 00:11:43
    In the code capacity error model,
  • 00:11:44
    we just assume that errors occur just before we
  • 00:11:47
    measure the stabilizers.
  • 00:11:50
    OK?
  • 00:11:50
    And because we're measuring the x and the z stabilizer
  • 00:11:54
    separately, we have two separate decoding problems.
  • 00:11:58
    So we get our x and our z syndrome,
  • 00:12:00
    and then we use the respective Hz and Hx CSS
  • 00:12:03
    matrices to decode these as two independent, classical decoding
  • 00:12:07
    problems.
  • 00:12:09
    And what we get out from this is some sort of binary vector
  • 00:12:12
    that we then map to a recovery operation which is then
  • 00:12:15
    applied to the quantum state.
  • 00:12:18
    OK.
  • 00:12:19
    So given this process, how do we actually
  • 00:12:22
    determine whether our decoding has been successful?
  • 00:12:24
    Well, in simulation what we can do
  • 00:12:26
    is we can calculate what we call the residual error.
  • 00:12:28
    So our CSS decoder will return two Pauli operations,
  • 00:12:34
    Pauli operation to correct x errors and one to correct
  • 00:12:36
    z errors.
  • 00:12:37
    And the residual error is just the combined effect
  • 00:12:40
    of these recovery operations and the actual error.
  • 00:12:45
    If we're doing a simulation, we know exactly what that is.
  • 00:12:47
    And we say that decoding is successful
  • 00:12:50
    if the action of this residual error
  • 00:12:53
    is to map onto the plus 1 eigenspace
  • 00:12:56
    of the logical states.
  • 00:12:58
    OK?
  • 00:12:58
    So this is the same as saying that the residual error is
  • 00:13:01
    equivalent to a stabilizer.
  • 00:13:03
  • 00:13:05
    And conversely, decoding fails, if the residual error
  • 00:13:09
    is equivalent to a logical operator
  • 00:13:11
    such that this logical state, the information
  • 00:13:15
    encoded there has changed, so our error correction protocol
  • 00:13:18
    has failed.
  • 00:13:21
    OK, so what decoders can we use to do
  • 00:13:25
    the decoding for these two separate error detection
  • 00:13:29
    components?
  • 00:13:30
    So one question you might have is,
  • 00:13:32
    can we use the surface code decoders that have been around
  • 00:13:35
    for a while and have been highly optimized
  • 00:13:37
    and are now getting to the point where they might actually
  • 00:13:39
    be fast enough to run on a real quantum computer decoding
  • 00:13:43
    syndromes in real time?
  • 00:13:44
    And the answer is unfortunately no.
  • 00:13:46
    And the reason for this is that both union find
  • 00:13:50
    and minimum weight perfect matching
  • 00:13:52
    are matching algorithms, and these
  • 00:13:54
    require a very specific structure
  • 00:13:56
    from your quantum error correction codes.
  • 00:13:57
    And the specific requirement they have
  • 00:14:00
    is that your quantum error correction code
  • 00:14:01
    produces pair like syndromes.
  • 00:14:03
    So we can see that this is the case, for example,
  • 00:14:05
    in the surface code.
  • 00:14:07
    So here we have a bit flip error that lights up two syndromes,
  • 00:14:10
    and as we increase the length of this error chain,
  • 00:14:13
    the syndrome weight remains the same.
  • 00:14:15
    So we see that the syndrome is still weight two,
  • 00:14:17
    and if we increase it by one, it's still weight two.
  • 00:14:20
    So decoding is just a process of joining
  • 00:14:22
    these pairs of syndromes.
  • 00:14:27
    OK?
  • 00:14:27
    Unfortunately, quantum LDPC codes in general
  • 00:14:31
    don't have this matching property.
  • 00:14:33
    So we can see this very easily by looking at the Hamming code
  • 00:14:36
    that we saw before.
  • 00:14:37
    If we just put an error on the first qubit there,
  • 00:14:39
    we see that three syndromes are activated.
  • 00:14:42
    So we can't use a matching based decoder for this.
  • 00:14:45
    What this means is that we need to use a much more
  • 00:14:48
    general decoding algorithm, and I'll
  • 00:14:50
    be focusing in this tutorial on the classical belief
  • 00:14:53
    propagation decoder.
  • 00:14:55
  • 00:14:57
    OK.
  • 00:14:58
    So why belief propagation?
  • 00:14:59
    Well, it's a very general algorithm
  • 00:15:01
    that can be applied to any sparse graph.
  • 00:15:04
    So we don't need the matching structure.
  • 00:15:06
    And the other reason is that it's extremely fast.
  • 00:15:09
    So belief propagation runs in linear time,
  • 00:15:11
    if run sequentially, and if you have
  • 00:15:13
    access to a parallel architecture it
  • 00:15:15
    can, in principle, be almost constant in its complexity.
  • 00:15:19
  • 00:15:21
    OK.
  • 00:15:22
    So to provide some intuition for how this algorithm works,
  • 00:15:24
    let's focus on the classical decoding case.
  • 00:15:26
    Here we have a classical syndrome equation,
  • 00:15:29
    and given the syndrome, the goal of decoding
  • 00:15:31
    is to find some minimum weight estimates of the error given
  • 00:15:36
    this measured syndrome.
  • 00:15:38
    OK.
  • 00:15:39
    And assuming that we have a uniformly distributed error
  • 00:15:42
    model, as might be, for example, the case in the binary
  • 00:15:47
    symmetric channel, then we can express this
  • 00:15:49
    as a marginalization problem where
  • 00:15:51
    we marginalize over a multivariate probability
  • 00:15:54
    distribution that relates the probability of each bit being
  • 00:15:57
    an error to the syndrome that's being measured.
  • 00:16:01
    OK, so we wouldn't want to do this exhaustively
  • 00:16:03
    because that would scale exponentially
  • 00:16:06
    in its complexity.
  • 00:16:08
    So the basic idea behind belief propagation
  • 00:16:11
    is that we can leverage some of the structure
  • 00:16:13
    in the probability distribution given to us by the Tanner graph
  • 00:16:18
    to compute these marginals more efficiently.
  • 00:16:21
  • 00:16:27
    OK.
  • 00:16:27
    So in practice, this is done using a message passing
  • 00:16:32
    algorithm where information is exchanged
  • 00:16:35
    between the bits and the variable nodes of the Tanner
  • 00:16:39
    graph.
  • 00:16:40
    So a type of belief propagation called the product sum
  • 00:16:45
    algorithm actually computes the marginals exactly
  • 00:16:50
    if the graph is tree-like in practice.
  • 00:16:52
    Quantum error correction codes usually aren't tree-like.
  • 00:16:54
    However, what we find is that even if the graph has cycles
  • 00:16:59
    in the classical case, at least, it usually
  • 00:17:01
    works reasonably well.
  • 00:17:04
    OK.
  • 00:17:05
    So this animation here is designed
  • 00:17:10
    to give you some sort of intuition as to how the belief
  • 00:17:14
    propagation decoder works.
  • 00:17:16
    So this here is the Tanner graph for a repetition code,
  • 00:17:19
    and we have this error pattern here shown by the bits
  • 00:17:24
    with x's on them.
  • 00:17:26
    And that activates the syndrome that we see at the top.
  • 00:17:32
    OK.
  • 00:17:33
  • 00:17:36
    Yes.
  • 00:17:36
    In the first step of belief propagation,
  • 00:17:38
    we assume that each bit in the Tanner graph
  • 00:17:43
    has the same probability of being an error.
  • 00:17:45
    So what this essentially means is
  • 00:17:47
    that we set the probability of error
  • 00:17:48
    to being the initial error channel.
  • 00:17:52
    OK?
  • 00:17:53
    And then we run the lead propagation,
  • 00:17:56
    and information is exchanged between the nodes
  • 00:17:58
    and this probability distribution
  • 00:17:59
    redistributes itself.
  • 00:18:01
    And eventually once we start seeing that the probability
  • 00:18:03
    distribution isn't really changing very much,
  • 00:18:05
    we terminate the iterations.
  • 00:18:07
    And at that point, we can then make a hard decision
  • 00:18:10
    on the basis of the output probability distribution
  • 00:18:13
    by thresholding the probabilities such
  • 00:18:16
    that all bits that have a probability
  • 00:18:18
    above a certain value are set to 1.
  • 00:18:21
    And then that gives us a hard decision,
  • 00:18:26
    which is the recovery operation which can then be
  • 00:18:28
    applied to remove the syndrome.
  • 00:18:30
  • 00:18:32
    OK.
  • 00:18:32
    So the reason I chose this particular error configuration
  • 00:18:36
    is that we can see something interesting happening
  • 00:18:39
    when we start the iteration.
  • 00:18:40
  • 00:18:44
    OK.
  • 00:18:45
    So we see that in the first iteration, what happens
  • 00:18:49
    is that we immediately--
  • 00:18:51
    the probability distribution immediately shifts to this bit
  • 00:18:54
    here.
  • 00:18:55
    And the reason for this is that in the first step--
  • 00:18:57
    well, can you actually see the mouse?
  • 00:18:59
  • 00:19:03
    Yeah.
  • 00:19:03
    In the first step, what happens is that this bit sends
  • 00:19:06
    a message to this variable node and this variable node says,
  • 00:19:10
    OK, I'm--
  • 00:19:11
    sorry.
  • 00:19:12
    This variable node sends a message to this check node.
  • 00:19:14
    This check node says, OK, I'm not satisfied,
  • 00:19:17
    so it sends a message back.
  • 00:19:18
    And then that information reinforces the belief
  • 00:19:22
    that this bit is an error.
  • 00:19:24
    OK?
  • 00:19:25
    Right.
  • 00:19:26
    However, when we then run the algorithm further, what we find
  • 00:19:32
    is that we get more information from other variable nodes
  • 00:19:36
    and checks in the graph, and then eventually the information
  • 00:19:39
    propagates from this syndrome through to this syndrome.
  • 00:19:43
    But this one is also unsatisfied.
  • 00:19:46
    And if we go to the step just before the final one,
  • 00:19:49
    what we see is that we have--
  • 00:19:54
    yes, all four.
  • 00:19:55
  • 00:19:59
    Yeah.
  • 00:19:59
    Now we see that all four of these bits
  • 00:20:02
    have high probability of being an error.
  • 00:20:05
    What then happens is a message is sent to here.
  • 00:20:07
    It says, OK, look.
  • 00:20:08
    These three all have high probability.
  • 00:20:12
    And if we just have these three bits being an error,
  • 00:20:15
    then these two syndromes are removed.
  • 00:20:17
    But that isn't compatible with this bit also being an error.
  • 00:20:20
    So in the final step, that information
  • 00:20:22
    is propagated to the final bit, and then its probability
  • 00:20:27
    goes to zero.
  • 00:20:27
  • 00:20:31
    OK.
  • 00:20:32
    And so this is great.
  • 00:20:33
    This algorithm can be applied to any graph.
  • 00:20:36
    So we can apply it in principle to a surface code decoding
  • 00:20:43
    problem.
  • 00:20:43
    So this is the Hx component of a distance five surface code.
  • 00:20:48
    We can do the same thing again.
  • 00:20:49
    Can initialize belief propagation and then run it.
  • 00:20:54
    And we see that for this particular error configuration,
  • 00:20:57
    it just works.
  • 00:20:58
    So we can make a hard decision and then we
  • 00:21:01
    see the combined effect of the initial error plus the recovery
  • 00:21:04
    operation just gives us a stabilizer,
  • 00:21:06
    and the syndrome is removed.
  • 00:21:07
    So from this it appears that belief propagation actually
  • 00:21:10
    works for the surface code.
  • 00:21:12
    So let's look at what happens when
  • 00:21:13
    we draw a threshold plot of a toric code
  • 00:21:19
    decoded with belief propagation.
  • 00:21:21
    So for those of you who haven't seen these sorts of plots
  • 00:21:24
    before, this is a quantum error correction threshold plot.
  • 00:21:29
    On the x-axis we have the qubit error rate,
  • 00:21:31
    which is the physical error rate on each qubit.
  • 00:21:34
    On the y-axis we have the logical error rates.
  • 00:21:38
    And what we typically do is we draw lines
  • 00:21:40
    on this plot for a number of different error correction
  • 00:21:44
    codes of different size.
  • 00:21:47
    Once we start looking at this particular decoding plot,
  • 00:21:49
    we see that this error correction protocol,
  • 00:21:52
    i.e. the toric code decoded with belief propagation,
  • 00:21:54
    doesn't actually work that well.
  • 00:21:56
    And the reason for this is we see
  • 00:21:59
    that as we increase the size of the code--
  • 00:22:01
    so this blue line is 162 qubit code
  • 00:22:03
    and the red line is a 450 qubit code.
  • 00:22:07
    And what we see is that as we increase the size of our error
  • 00:22:10
    correction codes, the logical error rate
  • 00:22:12
    is actually getting higher.
  • 00:22:14
    So this is, in effect, an error worsening code rather than
  • 00:22:17
    an error correction code.
  • 00:22:18
    And this toric code decoded with the belief propagation decoder
  • 00:22:22
    doesn't actually have a threshold.
  • 00:22:24
  • 00:22:30
    And the reason for this was touched on
  • 00:22:32
    in the previous talk.
  • 00:22:34
    It's because of the presence of these so-called trapping
  • 00:22:36
    sets in quantum codes, and these arise
  • 00:22:38
    when we have cycles that support degenerate errors.
  • 00:22:44
    OK?
  • 00:22:44
    So the classic example is this configuration
  • 00:22:48
    in the surface code where we have a so-called corner error.
  • 00:22:54
    So once we've run the leave propagation
  • 00:22:56
    on this, what we find is that the probability
  • 00:23:01
    distribution eventually converges
  • 00:23:04
    to showing that there's high probability of these four
  • 00:23:08
    qubits around this square or being errors.
  • 00:23:10
    So what then happens when we make
  • 00:23:12
    a hard decision is that we apply a z error on every single one
  • 00:23:17
    of the qubits around the square, and it doesn't actually
  • 00:23:19
    remove the [INAUDIBLE].
  • 00:23:24
    So these trapping sets cause the belief propagation decoder
  • 00:23:27
    to fail, and this is why we don't get a threshold.
  • 00:23:29
  • 00:23:35
    OK, so we have to find some way of dealing with these trapping
  • 00:23:37
    sets.
  • 00:23:38
    And perhaps the best way that we know of at the moment
  • 00:23:41
    is the so-called order statistics
  • 00:23:44
    post-processing technique.
  • 00:23:46
    So the OSD decoder is a technique
  • 00:23:49
    for decoding parity check matrix that
  • 00:23:51
    always guarantees a solution that satisfies the syndrome.
  • 00:23:55
    It's existed for a while.
  • 00:23:56
    So it was initially developed as a method
  • 00:23:58
    for lowering the error flaw in classical LDPC codes,
  • 00:24:02
    and it was first applied in the quantum setting by Pantaleev
  • 00:24:04
    and Kalachev in 2019.
  • 00:24:08
    OK.
  • 00:24:08
    And the idea behind the belief propagation
  • 00:24:10
    plus order statistics decoder is we first
  • 00:24:12
    run belief propagation.
  • 00:24:14
    If that belief propagation outputs satisfies
  • 00:24:16
    a syndrome, then great.
  • 00:24:17
    We simply output the BP solution.
  • 00:24:19
    If not, then we call the LSD decoder
  • 00:24:23
    and output the OSD decoding.
  • 00:24:27
    OK.
  • 00:24:27
    And the basic idea behind OSD is that we can always
  • 00:24:30
    solve the decoding problem using matrix inversion.
  • 00:24:33
    So consider this parity check matrix here.
  • 00:24:37
    Of course we can't immediately invert this matrix
  • 00:24:41
    because it's not full rank square.
  • 00:24:42
    But what we can always do is we can
  • 00:24:44
    choose a full rank subset of the columns of this matrix
  • 00:24:47
    and decode that instead.
  • 00:24:49
    OK.
  • 00:24:49
    So the question now might be, why don't we
  • 00:24:52
    just do this all the time?
  • 00:24:53
    And the reason for this is that there
  • 00:24:54
    are lots of different ways of choosing
  • 00:24:56
    this subset of columns.
  • 00:24:58
    So we could just pick four random linearly independent
  • 00:25:01
    columns, and it would give you a solution to the decoding
  • 00:25:03
    problem, but it's not necessarily
  • 00:25:05
    going to be a minimum weight solution.
  • 00:25:07
    And in the context of quantum error correction,
  • 00:25:08
    that would probably mean that you're introducing
  • 00:25:10
    a logical error, in most cases.
  • 00:25:14
    OK.
  • 00:25:15
    So how do we get around this?
  • 00:25:16
    Well, the idea is to use the probability distribution that's
  • 00:25:19
    output by BP to intelligently select this subset of columns.
  • 00:25:24
    OK?
  • 00:25:24
    So let's stick with this parity check matrix here.
  • 00:25:27
    If we want to decode this syndrome,
  • 00:25:29
    then we can put this into the belief propagation decoder
  • 00:25:32
    and it might output this sequence
  • 00:25:35
    of probabilities, error probabilities on each bit.
  • 00:25:38
    So this fourth bit, in this case,
  • 00:25:40
    would be the one that's most likely to be an error according
  • 00:25:43
    to belief propagation.
  • 00:25:45
    We can then use that belief propagation probability
  • 00:25:50
    distribution output to rank our qubits or columns of the parity
  • 00:25:55
    check matrix from least to--
  • 00:25:57
    from most to least likely of being in error.
  • 00:26:00
    OK?
  • 00:26:00
    And then the idea is that we rearrange
  • 00:26:02
    the columns of this parity check matrix
  • 00:26:04
    according to this ordering.
  • 00:26:06
    So this is the original ordering,
  • 00:26:07
    and now this is the ordering such
  • 00:26:09
    that this column corresponds to the bit that's
  • 00:26:12
    most likely to be an error.
  • 00:26:14
    At this point, we can then perform Gaussian elimination
  • 00:26:17
    column wise on this matrix to find a full rank
  • 00:26:20
    submatrix consisting of the bits that belief propagation has
  • 00:26:25
    told us that are highly likely to be an error.
  • 00:26:29
    OK.
  • 00:26:29
    And this improves decoding.
  • 00:26:31
    So this is just the decoding plot
  • 00:26:32
    we saw before where we just had the belief propagation decoder.
  • 00:26:35
    But we can turn on the OSD post-processing.
  • 00:26:39
    And what we see is, first of all,
  • 00:26:41
    we immediately get a much more considerable reduction
  • 00:26:46
    in the error.
  • 00:26:48
    So we get much more logical error suppression.
  • 00:26:50
    So we see that this, at 1% we're suppressing
  • 00:26:55
    by about five orders of magnitude more.
  • 00:26:59
    The second thing is that we also now
  • 00:27:01
    have a working error correction protocol in that we actually
  • 00:27:03
    have a threshold.
  • 00:27:04
    So remember the blue line is a smaller code
  • 00:27:06
    and the red line is the biggest code.
  • 00:27:08
    Now as we increase the size of our toric codes, what we see
  • 00:27:11
    is we get improved logical expression.
  • 00:27:14
    So our error correction protocol is now working.
  • 00:27:17
    So this is the way in which we can hack belief propagation
  • 00:27:20
    to work for quantum codes.
  • 00:27:21
  • 00:27:27
    OK.
  • 00:27:28
    So the big advantage of this belief propagation
  • 00:27:31
    plus all the statistics decoder is
  • 00:27:33
    that it can work for pretty much anything.
  • 00:27:35
    So all the examples I've given up to this point
  • 00:27:37
    have been for the topological codes.
  • 00:27:40
    However, it can be used to decode pretty much anything
  • 00:27:44
    that is LDPC.
  • 00:27:45
    So examples include fractal codes, 3D color codes,
  • 00:27:49
    various topological codes, as well as circuit level noise
  • 00:27:53
    decoding graphs.
  • 00:27:56
    Now for some advertisements.
  • 00:27:57
    If you want to try out this decoder,
  • 00:27:59
    we have an open source software package
  • 00:28:02
    that allows you to go from defining a parity check
  • 00:28:05
    matrix in Python using NumPy to actually doing some decoding
  • 00:28:11
    in less than 10 lines of code.
  • 00:28:13
    Yeah?
  • 00:28:15
    AUDIENCE: Maybe I missed something.
  • 00:28:17
    Apologies if I did.
  • 00:28:18
    I thought the reason you wanted to look at the belief
  • 00:28:20
    propagation was that it's a local algorithm,
  • 00:28:22
    but then this OSD where you have to sort the probabilities, that
  • 00:28:26
    doesn't seem very local.
  • 00:28:27
    JOSCHKA ROFFE: Sure.
  • 00:28:28
    Yeah.
  • 00:28:28
    We'll get on to that later.
  • 00:28:30
  • 00:28:34
    OK, so up to this point I've described
  • 00:28:38
    decoding in the very idealized setting of circuit level noise
  • 00:28:43
    and of code capacity noise, sorry.
  • 00:28:46
    So of course, this isn't very realistic
  • 00:28:50
    because we actually have to use quantum circuits
  • 00:28:52
    to measure our stabilizers.
  • 00:28:55
    So in the code capacity noise case, what we assume
  • 00:28:58
    is that the errors only occur in a very specific location.
  • 00:29:01
    So this is an example of an error correction circuit
  • 00:29:03
    for one of the simplest quantum codes,
  • 00:29:05
    which is the 4, 2, 2 error detection codes.
  • 00:29:09
    Yep?
  • 00:29:09
    AUDIENCE: What is the time complexity of this [INAUDIBLE]
  • 00:29:12
    algorithm?
  • 00:29:14
    JOSCHKA ROFFE: OK.
  • 00:29:15
    I have a slide on that later, so we'll get to it.
  • 00:29:19
    So this is a 4, 2, 2 error detection code.
  • 00:29:23
    The Hx and Hz matrices are just these.
  • 00:29:28
    So the first part is an error correction circuits
  • 00:29:30
    is creating an encoder.
  • 00:29:31
    We then get our logical state, and then
  • 00:29:33
    we measure the x and the z stabilizers, which in this case
  • 00:29:37
    just zzzz and xxxx out via projective measurements.
  • 00:29:43
    OK?
  • 00:29:43
    So what this looks like in a little more detail
  • 00:29:45
    is that we can use CNOTs to measure these.
  • 00:29:48
    So this is the encoder now.
  • 00:29:50
    This is the measurement of the z stabilizers,
  • 00:29:52
    and this is the measurement of the x stabilizers.
  • 00:29:54
    And this is still a code capacity noise model,
  • 00:29:56
    because we're assuming that errors only
  • 00:29:57
    occur in this location.
  • 00:29:59
    Of course this is completely unrealistic,
  • 00:30:01
    because these auxiliary qubits that
  • 00:30:05
    are used to measure out the stabilizers are also qubits,
  • 00:30:08
    and are therefore just as susceptible to error
  • 00:30:11
    as the qubits on the register.
  • 00:30:14
    So what a more realistic picture of the circuit might look like,
  • 00:30:18
    just for bit flip errors, is like this.
  • 00:30:20
    So we have errors in every single location in the circuit,
  • 00:30:23
    and we have to adapt our decoders
  • 00:30:25
    to take account of this.
  • 00:30:28
    And the reason this is problematic
  • 00:30:30
    is because of error propagation through the circuit.
  • 00:30:33
    To understand this, we need to understand
  • 00:30:35
    two rules for the propagation of Pauli errors
  • 00:30:39
    through CNOT gates.
  • 00:30:41
    So the way that this works is if we
  • 00:30:43
    have an x error at this location, then a CNOT gate
  • 00:30:45
    will propagate it like this.
  • 00:30:48
    So we get an x error at the control and an x error
  • 00:30:52
    at the target.
  • 00:30:53
    And similarly for z errors, what we find
  • 00:30:55
    is that if we have a z error down here,
  • 00:30:58
    it will climb up the CNOT to give you
  • 00:31:01
    an error pattern like this.
  • 00:31:03
    So what this means is that single errors in our quantum
  • 00:31:06
    error correction extraction circuit
  • 00:31:08
    can spread to heavier weight errors
  • 00:31:11
    and activate more syndromes than you might expect.
  • 00:31:14
    OK.
  • 00:31:15
    So as an example, what we find if we have an x error here
  • 00:31:19
    in this part of the 4, 2, 2 syndrome extraction circuit
  • 00:31:22
    is that it will propagate like this.
  • 00:31:24
    So I'll activate both this syndrome measurement
  • 00:31:27
    and this syndrome measurement.
  • 00:31:30
    OK, so given this more complicated circuit level noise
  • 00:31:34
    model, is it sufficient to decode the seed code using
  • 00:31:40
    the techniques that we've been describing so far?
  • 00:31:42
    I.e. just decoding the Hx and Hz matrices as classical codes.
  • 00:31:46
    And the answer to this is unfortunately no.
  • 00:31:49
    So what we need is we need a much more detailed decoding
  • 00:31:52
    graph that relates each sequence of measurements here
  • 00:31:56
    to each specific error mechanism in our circuit.
  • 00:32:00
  • 00:32:02
    OK.
  • 00:32:03
    So what typically happens is that these circuit level
  • 00:32:07
    noise decoding graphs get much bigger.
  • 00:32:09
    However, one important thing to note
  • 00:32:11
    is that they are still binary matrices, so they
  • 00:32:13
    can be decoded using BP+OSD.
  • 00:32:16
    And the other thing to note is that these decoding graphs
  • 00:32:21
    get much bigger.
  • 00:32:22
    So in this paper, which will be the subject of the next talk,
  • 00:32:26
    they decoded a 144, 12, 12 code under circuit level noise
  • 00:32:31
    and had to use an 8785 column decoding matrix.
  • 00:32:36
    So we see that our decoding matrix
  • 00:32:38
    increases from 144 to 8785.
  • 00:32:42
    So that's a pretty huge expansion
  • 00:32:44
    in the complexity of the decoding problem.
  • 00:32:48
    OK.
  • 00:32:49
    So this leads on nicely to the next section,
  • 00:32:51
    which is the question as to whether BP+OSD is enough.
  • 00:32:54
    And now to answer your question about the runtime
  • 00:32:57
    of this algorithm.
  • 00:32:58
    So to recap, the belief propagation component
  • 00:33:02
    is extremely fast.
  • 00:33:03
    So it runs in linear time in the block length and almost
  • 00:33:08
    constant when run in parallel.
  • 00:33:11
    However, the big bottleneck in our belief propagation
  • 00:33:13
    plus order statistics decoder is the OSD component,
  • 00:33:16
    because that requires Gauss elimination which is,
  • 00:33:19
    by comparison, really slow.
  • 00:33:21
    So it's cubic in the block length in the worst case
  • 00:33:24
    and also very difficult to parallelize.
  • 00:33:28
    So the OSD component is really the bottleneck,
  • 00:33:30
    and that raises the question as to
  • 00:33:33
    whether this particular decoder that
  • 00:33:35
    works so well for simulations and for benchmarking quantum
  • 00:33:38
    LDPC codes is the actual decoding technique that we'd
  • 00:33:41
    want to use in a real quantum computer
  • 00:33:44
    when we're decoding real syndromes.
  • 00:33:48
    So the open problem is, is there an OSD alternative
  • 00:33:51
    that improves performance with reduced complexity?
  • 00:33:56
    OK.
  • 00:33:56
    So the dream would be to have a completely local decoder using
  • 00:34:01
    a combination of belief propagation and something
  • 00:34:03
    like the flip decoder that was described in the previous talk.
  • 00:34:08
    So the advantage of this would be
  • 00:34:09
    that it would be a completely local algorithm.
  • 00:34:11
    So the flip decoder only needs to know about individual bits
  • 00:34:15
    in its immediate environment.
  • 00:34:17
    So it could be arbitrarily parallelized,
  • 00:34:19
    and this would, in combination with BP, which
  • 00:34:22
    can also be very easily parallelized,
  • 00:34:24
    lead to very fast decoders.
  • 00:34:26
    So this idea has been explored in various works.
  • 00:34:30
    However, what we find is that there's usually
  • 00:34:33
    a pretty serious performance penalty.
  • 00:34:35
    So this is a plot from some work I'm currently
  • 00:34:38
    doing with Tom Scruby from Okinawa University
  • 00:34:42
    where we're comparing the performance of BP+OSD
  • 00:34:44
    with the BP plus flip decoder.
  • 00:34:48
    So the red line is BP+OSD and the green line
  • 00:34:50
    is the BP flip decoder.
  • 00:34:52
    And you see that we're reducing performance
  • 00:34:55
    by about two orders of magnitude.
  • 00:34:57
    OK?
  • 00:34:57
    However, the interesting thing is
  • 00:34:59
    that for this particular code, which is a very small quantum
  • 00:35:01
    LDPC code, we're still getting improved performance compared
  • 00:35:04
    to a comparably sized surface code decoded with matching.
  • 00:35:08
    So I guess the question to be more further explored is, yeah,
  • 00:35:13
    what is the compromise that we're-- what is the performance
  • 00:35:16
    hit that we're willing to settle on?
  • 00:35:18
    Is it potentially a faster decoder
  • 00:35:21
    where if it means a reduction in the quality of the decoding?
  • 00:35:27
    OK.
  • 00:35:27
    The second approach that we could look at
  • 00:35:29
    is repeat until success belief propagation.
  • 00:35:32
    So here the idea is that we can run belief propagation
  • 00:35:34
    multiple times, and after each run of BP,
  • 00:35:38
    we modify something about our decoding problem.
  • 00:35:41
    So one example is to modify the error
  • 00:35:43
    channel and other techniques.
  • 00:35:46
    Modify the decoding graph itself.
  • 00:35:49
    On the right here, I have an example
  • 00:35:51
    from this paper, the stabilizing activation decoding technique.
  • 00:35:55
    And here, the idea is that you, after every round of BP,
  • 00:35:58
    delete some problematic check nodes that
  • 00:36:01
    are involved in trapping sets.
  • 00:36:02
    And for a particular code family,
  • 00:36:04
    they actually showed that you can
  • 00:36:06
    improve upon the performance of belief propagation plus all
  • 00:36:08
    the statistics decoding.
  • 00:36:10
    What isn't explored, however, is the performance's code
  • 00:36:13
    in a wider variety of settings or in the circuit level noise.
  • 00:36:20
    Another approach is to abandon the idea of decoding your bit
  • 00:36:26
    flip and phase flip errors separately,
  • 00:36:29
    because this comes with a performance penalty.
  • 00:36:31
    So some decoders have been proposed where you instead
  • 00:36:34
    decode over a quaternary graph rather than a binary graph.
  • 00:36:39
    So in some settings, this can give us performance
  • 00:36:42
    that is comparable to BP+OSD.
  • 00:36:45
    What I find, however, is that these decoders are
  • 00:36:48
    very difficult to calibrate and they're often
  • 00:36:50
    very dependent upon the initial conditions.
  • 00:36:54
    And the final--
  • 00:36:56
    AUDIENCE: [INAUDIBLE]
  • 00:36:57
  • 00:37:00
    JOSCHKA ROFFE: Because the belief propagation
  • 00:37:01
    update rules get more complicated.
  • 00:37:05
    AUDIENCE: [INAUDIBLE]
  • 00:37:08
    JOSCHKA ROFFE: I don't know the exact number,
  • 00:37:10
    but yeah, it's more.
  • 00:37:11
    It's slower.
  • 00:37:14
    So the final thing I'll mention are this idea
  • 00:37:19
    to use machine learning to actually improve the belief
  • 00:37:21
    propagation algorithm itself.
  • 00:37:23
    So as mentioned previously, belief propagation
  • 00:37:27
    works by exchanging information between check
  • 00:37:29
    nodes and variable nodes.
  • 00:37:31
    So the idea here is to use some sort
  • 00:37:33
    of machine learning technique to learn better update rules.
  • 00:37:38
    So here's one paper where they trained a belief propagation
  • 00:37:43
    decoder using a graph neural network,
  • 00:37:45
    and they do get performance that is approaching the BP+OSD line.
  • 00:37:49
    The problem, of course, with this
  • 00:37:50
    is that, as with many things to do with neural networks,
  • 00:37:54
    scalability can be a problem.
  • 00:37:56
    Can you ensure that it still works
  • 00:37:57
    once you start increasing the size of the nodes?
  • 00:37:59
  • 00:38:02
    OK.
  • 00:38:03
    And that's the end of my talk.
  • 00:38:04
    So to summarize, quantum LDPC codes
  • 00:38:07
    require general decoders that go beyond union
  • 00:38:09
    fines and minimum weight perfect matching.
  • 00:38:13
    BP+OSD works reasonably well and gives us nice decoding plots
  • 00:38:17
    for papers in our early simulations
  • 00:38:20
    of these quantum LDPC code protocols.
  • 00:38:23
    However, because of the cubic complexity
  • 00:38:26
    of the post-processing, it's unlikely they will actually
  • 00:38:29
    be practical when we're building real quantum computers based
  • 00:38:34
    on LDPC code architectures.
  • 00:38:36
    So the open problem is, can we improve upon OSD?
  • 00:38:42
    [APPLAUSE]
  • 00:38:44
  • 00:38:52
    AUDIENCE: I was curious if the BP+OSD algorithm is
  • 00:38:57
    relatively easy to include information
  • 00:38:59
    about the noise model?
  • 00:39:00
    So if you have bias noise, where do you put that in?
  • 00:39:05
    JOSCHKA ROFFE: Yes, it's very easy to include.
  • 00:39:07
    So when you start belief propagation,
  • 00:39:10
    you set all the bits to be equal to the initial error channel.
  • 00:39:13
    If that initial error channel is biased,
  • 00:39:15
    you just set the initial probability distribution bias.
  • 00:39:18
    It works out of the box, basically.
  • 00:39:20
  • 00:39:22
    AUDIENCE: So I'm kind of curious.
  • 00:39:24
    I think Calderbank has a paper on spatially coupled codes
  • 00:39:28
    where he just runs belief propagation.
  • 00:39:32
    And I think the Tanner graphs have girth eight,
  • 00:39:35
    I want to say.
  • 00:39:36
    And it seems to perform pretty well.
  • 00:39:39
    What do you think the prospects are
  • 00:39:41
    for getting rid of any post-processing completely
  • 00:39:45
    in both the ideal setting where you're not
  • 00:39:48
    worrying about circuit level noise,
  • 00:39:50
    and then in the setting of circuit level noise
  • 00:39:52
    where you actually have to worry about quite a bit more?
  • 00:39:56
    JOSCHKA ROFFE: Yeah.
  • 00:39:57
    I think this is a good strategy.
  • 00:39:59
    So yeah, if you can design your code such
  • 00:40:01
    that it works well in the first instance,
  • 00:40:05
    then that's the best way of going about it.
  • 00:40:07
    So yeah, I guess this is the motivation behind many
  • 00:40:10
    of these biased noise papers.
  • 00:40:12
    As you get more bias, it becomes more classical,
  • 00:40:14
    therefore easier to decode.
  • 00:40:16
    So yeah, that is the best strategy
  • 00:40:19
    if we can find a technique to actually do that.
  • 00:40:23
    AUDIENCE: If I may comment.
  • 00:40:25
    So when you add the circuit level
  • 00:40:28
    noise, then the girth of the graph,
  • 00:40:31
    no matter what the original graph was, it becomes three.
  • 00:40:35
    So the generators for the circuit level noise
  • 00:40:39
    always have-- all of them have three or two.
  • 00:40:42
    The two you can eliminate, but the three remain,
  • 00:40:45
    and that makes it very difficult.
  • 00:40:49
    Basically out of the box belief propagation always fails.
  • 00:40:53
    BP+OSD requires a lot of extra because the original BP
  • 00:41:02
    fails very often.
  • 00:41:03
  • 00:41:05
    MODERATOR: There's a question in the back.
  • 00:41:06
    AUDIENCE: Yeah.
  • 00:41:07
    So what is the argument that BP converges in a linear time?
  • 00:41:14
    You said like BP is a [INAUDIBLE]..
  • 00:41:17
    JOSCHKA ROFFE: Yeah.
  • 00:41:18
    AUDIENCE: How can we guarantee that things--
  • 00:41:20
    iteration converges after one time?
  • 00:41:24
    JOSCHKA ROFFE: OK.
  • 00:41:25
    There are proofs of this.
  • 00:41:27
    Yeah.
  • 00:41:27
    I can't reproduce them on the fly.
  • 00:41:30
    AUDIENCE: Another question is BP+OSD possibility better
  • 00:41:33
    than the minimum perfect matching in the toric code
  • 00:41:35
    case?
  • 00:41:36
    JOSCHKA ROFFE: No.
  • 00:41:37
    So yeah, I guess this is the price
  • 00:41:40
    to pay for the fact it's a very general decoder.
  • 00:41:42
    So yeah.
  • 00:41:44
    For the specific case of the surface codes
  • 00:41:47
    having a decoder that's optimized specifically
  • 00:41:51
    for that decoding problem, it can improve the performance
  • 00:41:55
    of the matching decoder by combining it
  • 00:41:56
    with the propagation.
  • 00:41:58
    So yeah.
  • 00:42:00
    Oscar, who is also here, proposed
  • 00:42:03
    that combining belief propagation [INAUDIBLE]
  • 00:42:05
    decoder performance improves the performance even more.
  • 00:42:10
  • 00:42:15
    AUDIENCE: So I have a question about criteria decoder.
  • 00:42:18
    So this decoding problem is an estimation
  • 00:42:21
    of recovery operation from syndrome.
  • 00:42:26
    If I understand correctly, you describe the protocol
  • 00:42:28
    to construct the estimator in this talk.
  • 00:42:31
    But there must be some criteria on the decoder.
  • 00:42:34
    For example, random guess may also provide some estimator,
  • 00:42:38
    but we don't call it as a decoder.
  • 00:42:40
    It must be some criteria to call some procedure as decoder.
  • 00:42:45
    Do you have some criteria in your mind for how
  • 00:42:50
    BP+OSD satisfies the criteria?
  • 00:42:52
  • 00:42:54
    JOSCHKA ROFFE: Sorry, I don't really understand the question.
  • 00:42:56
    So criteria for?
  • 00:43:00
    AUDIENCE: Estimating recovery operations as a decoder.
  • 00:43:03
    This estimation needs to satisfy some condition in order
  • 00:43:08
    for this estimator to grow--
  • 00:43:10
    in order to call some protocol.
  • 00:43:12
    JOSCHKA ROFFE: OK.
  • 00:43:13
    Yeah.
  • 00:43:14
    AUDIENCE: What's the criteria?
  • 00:43:16
    JOSCHKA ROFFE: I guess-- yes.
  • 00:43:17
    So in this particular setting, we're
  • 00:43:20
    just assuming that the decoding matrices are classical matrices
  • 00:43:24
    and we're just trying to find the lowest weight
  • 00:43:27
    solution in the hope that this will not introduce.
  • 00:43:32
    Much clearer and more accurate decoders
  • 00:43:35
    can look at the actual code sets and try and differentiate
  • 00:43:38
    between the logical classes that you have
  • 00:43:41
    and separate the different parts of the code space.
  • 00:43:46
    So some of the tensor network decoders and the surface codes,
  • 00:43:50
    for example, are much more accurate, but also much slower.
  • 00:43:53
    Is that the--
  • 00:43:54
  • 00:43:57
    AUDIENCE: OK, you--
  • 00:43:59
    JOSCHKA ROFFE: Perhaps we can--
  • 00:44:01
    AUDIENCE: So maybe this is a basis
  • 00:44:05
    of your coding procedures.
  • 00:44:07
    Is that right?
  • 00:44:08
    JOSCHKA ROFFE: Yeah.
  • 00:44:09
    I guess the approach here is to make a decoder
  • 00:44:12
    and then see whether it works in terms of the decoding graphs.
  • 00:44:15
    Yeah.
  • 00:44:15
    If it does.
  • 00:44:17
    But yeah, it's very difficult to actually prove things
  • 00:44:19
    about belief propagation.
  • 00:44:20
    AUDIENCE: [INAUDIBLE].
  • 00:44:22
    Thank you.
  • 00:44:22
  • 00:44:25
    AUDIENCE: You mentioned union find
  • 00:44:27
    can be applied to general LDPC codes,
  • 00:44:29
    but there's this generalization for more general codes.
  • 00:44:33
    So is there a combination of belief propagation
  • 00:44:36
    with this general union find?
  • 00:44:38
    Just like belief propagation with matching?
  • 00:44:42
    JOSCHKA ROFFE: Yes.
  • 00:44:43
    So belief propagation plus matching decoders
  • 00:44:45
    have been proposed.
  • 00:44:48
    The generalization of the union find
  • 00:44:51
    algorithm proposed does have the problem that it's
  • 00:44:54
    quite slow because you have to do
  • 00:44:56
    repeated Gauss elimination on all the clusters as it grows.
  • 00:44:59
    AUDIENCE: Yeah.
  • 00:45:00
    Yeah.
  • 00:45:00
  • 00:45:07
    AUDIENCE: The algorithms like B propagation,
  • 00:45:09
    but they also have--
  • 00:45:11
    can they be naturally implemented
  • 00:45:12
    on channels like amplitude damping?
  • 00:45:15
    JOSCHKA ROFFE: Potentially.
  • 00:45:16
    That's not something I've explored, though.
  • 00:45:18
  • 00:45:21
    AUDIENCE: So in the measurement circle
  • 00:45:23
    you show, you always separate x measurements apart
  • 00:45:26
    and z measurement apart.
  • 00:45:29
    And I can imagine that this kind of arrangement
  • 00:45:32
    could be good at correcting one type of errors
  • 00:45:38
    but might be bad on correcting the other type of errors.
  • 00:45:44
    So is there any reason of you not mixing the measurement
  • 00:45:50
    surface of the two types of errors?
  • 00:45:54
    JOSCHKA ROFFE: For simplicity.
  • 00:45:55
    That was the reason for this particular example, but yes.
  • 00:45:58
    Scheduling is important.
  • 00:46:00
    The actual order in which you measure these syndromes
  • 00:46:03
    can also affect the distance of the decoding graph.
  • 00:46:07
    So yeah.
  • 00:46:08
    In the next talk we may see some discussion about this.
  • 00:46:12
    They explored lots of different ways
  • 00:46:15
    of extracting these stabilizers in several other ways.
  • 00:46:19
  • 00:46:23
    AUDIENCE: Some of these machine learning encoders,
  • 00:46:25
    how easy is it to, say, train on one code
  • 00:46:28
    and transfer it to a different code?
  • 00:46:30
    Are they all trained for the specific code
  • 00:46:32
    that they're trying decode?
  • 00:46:33
    Are they?
  • 00:46:34
    JOSCHKA ROFFE: So yeah.
  • 00:46:35
    My understanding is that each instance of a LDPC code,
  • 00:46:38
    you'd have to train a specific model.
  • 00:46:43
    Yeah.
  • 00:46:44
    This is another problem with LDPC codes.
  • 00:46:46
    It's just random.
  • 00:46:47
    It's not like a surface code where
  • 00:46:49
    once you figured out how to decode a small patch,
  • 00:46:51
    you can essentially do it everywhere.
  • 00:46:52
  • 00:46:55
    Any more questions?
  • 00:46:56
  • 00:46:59
    MODERATOR: Yes?
  • 00:47:01
    AUDIENCE: So you said matching based algorithms might not
  • 00:47:04
    work in general cases, but as far as I understand,
  • 00:47:11
    this matching comes from the fact
  • 00:47:13
    that surface code is based on the homology
  • 00:47:17
    and the homology is present in every quantum code in general.
  • 00:47:25
    So does it make sense to find minimum weight, cycle,
  • 00:47:30
    or path in general pod codes?
  • 00:47:35
    JOSCHKA ROFFE: There are some ways
  • 00:47:36
    of hacking more general homological codes
  • 00:47:41
    to work with matching.
  • 00:47:44
    It's not something I'm too familiar with.
  • 00:47:48
    Amanda Quintavalle, who's sitting to your right,
  • 00:47:50
    is working on that exact problem,
  • 00:47:52
    so it'd be best to discuss with her.
  • 00:47:54
  • 00:47:57
    AUDIENCE: I think that the problem
  • 00:47:59
    is how the single graph relates to the minimum weight solution
  • 00:48:06
    of the decoding problem.
  • 00:48:08
    So on the coding you always have each qubit error
  • 00:48:12
    exact two syndromes, so you can map
  • 00:48:14
    the problem of finding a minimum weight recovery
  • 00:48:18
    operator to the 1 to obtain a minimum weight
  • 00:48:22
    path between the two syndromes.
  • 00:48:24
    But for general codes that lead to more than one mode
  • 00:48:28
    for two syndromes, you don't have the same mapping.
  • 00:48:33
    OK.
  • 00:48:34
    It's not [INAUDIBLE],, to guess what the number of--
  • 00:48:39
    but there are a lot of matching people in this.
  • 00:48:42
  • 00:48:46
    AUDIENCE: Yeah, one quick question
  • 00:48:48
    to poke at the open problem a little bit.
  • 00:48:51
    I mean, I think perfectly decoding to minimum weight
  • 00:48:56
    of general CSS code is known to be NP hard.
  • 00:49:00
    Right?
  • 00:49:01
    So the question is where do we find hope
  • 00:49:06
    to look for widely applicable decoders?
  • 00:49:12
    You know what I mean?
  • 00:49:13
    Like, where might we need to look?
  • 00:49:19
    JOSCHKA ROFFE: Well, my hope is that some technique
  • 00:49:21
    from the classical literature, as
  • 00:49:24
    of yet been untested in the quantum setting,
  • 00:49:26
    will work well.
  • 00:49:28
    So OSD, for example, was such a technique.
  • 00:49:32
    But yeah, I don't know specifically
  • 00:49:33
    how it's going to be solved.
  • 00:49:35
  • 00:49:38
    MODERATOR: OK.
  • 00:49:40
    Any more questions?
  • 00:49:43
    If not, let's thank Joschka again.
  • 00:49:45
    [APPLAUSE]
  • 00:49:49
Tags
  • Quantum LDPC Codes
  • Error Correction
  • Belief Propagation
  • Circuit Level Noise
  • Stabilizer Codes
  • Quantum Computation
  • Trapping Sets
  • OSD
  • Decoding Techniques
  • Machine Learning