⚛️ quantum physics

Bacon-Shor Board Games

This paper introduces a period-4 measurement schedule for the Bacon-Shor code, derived from a coloring game on a square grid, which achieves a numerical fault-tolerance threshold of approximately 0.3% under circuit-level noise without relying on code concatenation.

Original authors: M. Sohaib Alam, Jun Zen, Thomas R. Scruby

Published 2026-02-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: M. Sohaib Alam, Jun Zen, Thomas R. Scruby

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Fixing a Leaky Boat

Imagine you are trying to build a boat out of wooden planks (these are your quantum bits, or qubits) to sail across a stormy ocean. The problem is that the wood is rotting and the ocean is splashing water everywhere (this is noise and errors). If you don't fix the holes, the boat sinks.

To keep the boat afloat, you need a crew constantly checking for leaks and patching them. In quantum computing, this crew is called Quantum Error Correction (QEC). They measure the boat to see if a plank has shifted or rotted.

However, there's a catch: The act of checking the boat can sometimes cause new leaks. If the crew is too clumsy or if they have to check a huge section of the boat all at once, they might break more planks than they fix.

The Problem with the "Bacon-Shor" Boat

The paper focuses on a specific type of boat design called the Bacon-Shor code.

The Design: It's a grid of planks. The crew checks for leaks by looking at pairs of neighboring planks (horizontal and vertical neighbors).
The Flaw: In the standard way of using this code, the crew has to check the entire length of a row or column to find a leak. As the boat gets bigger (more planks), the crew has to check longer and longer lines.
The Result: On a small boat, this works fine. But on a giant boat, the long lines of checking become so prone to mistakes that the crew eventually causes more damage than they fix. The boat has no "threshold"—it can't get big enough to be reliable.

The Solution: A New "Board Game" Strategy

The authors realized that the problem wasn't the boat itself, but the schedule the crew used to check it. They asked: "Can we change the order in which we check the planks so we never have to check a long line all at once?"

To solve this, they invented a Board Game.

The Game Rules

Imagine a checkerboard where every square represents a "gauge qubit" (a virtual helper on the boat).

The Colors: You can paint a square Red (fixing an X-check) or Blue (fixing a Z-check).
The Move: If you have a Red square, you can "grow" it into a vertical strip of Red squares in the same column. If you have a Blue square, you can grow it into a horizontal strip.
The Goal: You need to find a repeating pattern (a cycle) of painting the board such that:
- Every column and row gets fully painted at least once (to check the whole boat).
- But at any single moment, the painted strips are short and manageable (so the crew doesn't get overwhelmed).
- The pattern repeats quickly (every 4 steps).

The Breakthrough

The authors found a specific 4-step pattern (a "Period-4 Schedule") that solves this game perfectly.

Instead of checking the whole row at once, the crew checks small chunks, passes the information along, and stitches the results together over four rounds.
The Result: No matter how big the boat gets, the crew only ever has to check a small, constant number of planks at a time. The "weight" of the check stays small (constant), rather than growing with the size of the boat.

The "Magic" of the New Schedule

By using this new 4-step schedule, the authors discovered something amazing:

The Threshold: The boat now has a "threshold." This means if the ocean isn't too stormy (specifically, if the error rate is below about 0.3%), the boat can be made as big as you want, and it will become more reliable, not less.
The Comparison: Previous attempts to fix this code involved "concatenation" (stacking tiny boats inside tiny boats), which was complicated. This new method is like finding a better way to row the same boat. It's simpler and works better.

How They Proved It

The Math: They proved that this "Board Game" solution works for any size grid. If you have a solution for a 5x5 grid, you can stack it to make a 9x9, 100x100, or even larger grid, and the "check size" stays small.
The Simulation: They used a computer to simulate this boat in a storm.
- Old Way: As the boat got bigger, it sank faster.
- New Way: As the boat got bigger, it stayed afloat much longer.
- The Verdict: They found the "tipping point" (threshold) where the code starts working reliably. It's around 0.3%, which is high enough to be useful with current technology.

Summary

The paper is about solving a puzzle: How do you check a giant quantum computer for errors without the checking process itself breaking the computer?

The authors solved this by treating the error-checking schedule like a coloring game on a grid. They found a clever, repeating 4-step pattern that keeps the checks small and simple. This turns a code that was previously too fragile to scale up into a robust system that can handle large sizes, provided the hardware isn't too noisy.

Key Takeaway: You don't need a bigger boat to survive the storm; you just need a smarter crew schedule.

Technical Summary: Bacon-Shor Board Games

Problem Statement

The Bacon-Shor code is a prototypical quantum error correcting subsystem code defined on a square lattice with nearest-neighbor $XX$ and $ZZ$ check operators. While it offers attractive experimental features, such as low-weight, geometrically local measurements, it historically lacks a fault-tolerance threshold.

The fundamental issue arises from the standard measurement schedule (a period-2 cycle measuring all $X$ -type checks followed by all $Z$ -type checks). In this regime, the stabilizers—which are products of checks spanning entire rows or columns—have a weight that scales linearly with the lattice dimension $d$ ( $O(d)$ ). Consequently, the detectors (products of stabilizer measurements across rounds) also scale as $O(d)$ . As the lattice size increases, the probability of obtaining erroneous detector measurements grows, eventually causing the logical error rate to surpass the physical error rate. This prevents the code from exhibiting a threshold, a prerequisite for scalable fault-tolerant quantum computation.

Previous attempts to remedy this involved code concatenation or lattice surgery (e.g., [135]), but these approaches either required complex connectivity or resulted in detector weights and measurement periods that still scaled with $d$ . The central question addressed by this work is whether a measurement schedule exists that reduces detector weights to $O(1)$ while maintaining a constant measurement period, thereby enabling a threshold for the Bacon-Shor code without concatenation.

Methodology

The authors propose a novel approach to determining the measurement schedule by framing the problem as a "coloring game" on a square grid.

The Board Game Formulation

The lattice is treated as a board where each square plaquette corresponds to a gauge qubit. The game involves a sequence of colorings (states) where each plaquette is painted either red (fixing the $X$ operator of the gauge qubit) or blue (fixing the $Z$ operator).

Allowed Moves: A coloring $C_{j+1}$ follows $C_j$ if red (or blue) boxes in $C_j$ can expand into vertical (or horizontal) strips in $C_{j+1}$ within the same column (or row). This expansion corresponds to measuring the intermediate check operators ($XX$ or $ZZ$) to propagate the gauge fixing.
Objectives: The goal is to find a periodic sequence of colorings with period $R$ $R$ such that:
1. Every column and row is entirely one color (all red or all blue) in at least one step of the cycle. This ensures the full Bacon-Shor stabilizers are measured at least once per cycle.
2. Every column and row contains at least one box of the opposite color in every step. This ensures the existence of smaller-weight stabilizers within every instantaneous stabilizer group (ISG).
3. The lattice size $d$ and period $R$ are minimized.

Theoretical Construction

The authors demonstrate that a solution to this game on a small $d \times d$ lattice can be generalized to arbitrarily large lattices via stacking (Theorem 3).

Dynamical Detectors: Unlike standard stabilizer codes where detectors are simple repeated measurements of the same operator, the proposed schedule creates "dynamical detectors." These are products of measurements of different operators across multiple rounds that commute with the current round's measurements and evaluate to $+1$ in the absence of errors.
Weight Reduction: By ensuring that gauge-fixed operators (and their complements relative to the full stabilizer) exist in every ISG, the authors construct detectors with weights that do not grow with the lattice size.

Key Contributions

Period-4 Measurement Schedule: The authors identify a specific period-4 measurement schedule for the Bacon-Shor code that fully covers spacetime with constant-weight detectors.
Constant Weight Detectors: The proposed schedule reduces the detector weight from $O(d)$ to a constant (numerically observed to be $\le 20$ for the generalized solution), independent of the lattice size.
Threshold Discovery: Through numerical simulation, the authors demonstrate that this modified schedule endows the Bacon-Shor code with a fault-tolerance threshold, a property previously absent in the unmodified code.
Game-Theoretic Solution: The paper introduces a novel "board game" framework to solve for optimal measurement schedules, providing a constructive method for finding low-weight detector sequences.

Numerical Results

The performance of the modified code was evaluated using Monte Carlo simulations with a uniform circuit-level noise model.

Threshold Estimation: Using a minimum-weight perfect matching decoder (PyMatching), the authors observed a threshold of approximately 0.3% ( $p_{th} \approx 3 \times 10^{-3}$ ).
Error Suppression: The logical error rate decreases exponentially with increasing lattice size $d$ (from $d=5$ to $d=35$ ), confirming the presence of a threshold.
Comparison: The modified code achieves logical error rates two orders of magnitude lower than the self-concatenation approach described in [135].
Decoder Limitations: The authors note that while PyMatching performed well, the detectors form hyperedges in the decoding graph rather than simple pairwise edges. They conjecture that a tailored hypergraph-based decoder could further improve the threshold.

Significance and Claims

The paper claims that the Bacon-Shor code, previously considered to lack a threshold due to its $O(d)$ weight stabilizers, can be made fault-tolerant through a minor adjustment to its measurement schedule.

Threshold Competitiveness: The observed threshold of ~0.3% is competitive with surface codes and within the reach of noise rates achievable on current hardware platforms.
Subsystem Structure: The work highlights that the dynamical aspect of measurement schedules is a critical, often overlooked, degree of freedom in subsystem codes. It demonstrates that the same set of check operators can yield vastly different error-correcting properties depending on the temporal order of measurement.
No Concatenation Required: Unlike previous solutions, this method achieves a threshold without code concatenation, relying instead on the intrinsic subsystem structure and a constant-period schedule.
Future Directions: The authors modestly suggest that their solution is not necessarily optimal. They note that other gauge-fixing strategies (beyond the specific "board game" moves) and more sophisticated decoders could potentially yield higher thresholds. They emphasize the need for a broader theoretical framework to unify the temporal and algebraic aspects of quantum error correction.