⚛️ quantum physics

Satisfying Quantum Codes: Physics-Informed and Hardware-Aware Code Design with SAT Solvers

This paper introduces a general framework that formulates quantum error correction code design as a Boolean satisfiability (SAT) problem, enabling the automated discovery of both physics-inspired and hardware-aware codes that outperform state-of-the-art solutions despite the inherent NP-completeness of the task.

Original authors: Ben DalFavero, William M. Watkins, Margarite L. LaBorde, Vincent Russo, Ethan Egger, Gregory Quiroz, Ryan LaRose

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ben DalFavero, William M. Watkins, Margarite L. LaBorde, Vincent Russo, Ethan Egger, Gregory Quiroz, Ryan LaRose

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

Quantum computers promise to solve problems that would take today's machines thousands of years to crack, from designing new medicines to modeling complex climate systems. However, these machines are incredibly fragile. The tiny particles they use to store information, called qubits, are easily disturbed by heat, vibration, or stray electromagnetic fields. A single mistake can corrupt the entire calculation. To make these machines useful, scientists must build a shield against these errors, a system known as quantum error correction. This system works by spreading a single piece of information across many physical qubits, creating a logical qubit that can survive if a few of its parts fail. For decades, researchers have designed these protective codes by hand, using mathematical intuition and physical principles. This manual process is slow and often fails to account for the specific quirks of the actual hardware being used, leaving potential performance on the table.

A team of researchers has now developed a new way to design these protective codes, moving from manual craftsmanship to automated discovery. Instead of relying on human intuition alone, they turned the problem of code design into a logic puzzle that computers can solve. They treated the search for a perfect error-correcting code as a question of whether a specific set of rules can be satisfied at the same time. By translating the complex requirements of quantum mechanics into a format that modern logic solvers can process, they created a flexible framework capable of designing codes from scratch or improving existing ones. This approach allows them to incorporate the specific symmetries of a physics problem or the unique noise patterns of a real quantum device, tailoring the protection to the exact task at hand.

The researchers proved that finding the perfect code is, in the most general sense, an incredibly difficult mathematical challenge. They demonstrated that this problem belongs to a class of tasks known to be computationally hard, meaning there is no simple, fast algorithm that can solve every possible version of the problem. This finding rules out the hope of a universal, instant solution for designing codes. However, the team showed that for the specific, practical problems scientists face today, powerful computer solvers can find excellent solutions very quickly. They tested their method on a standard laptop and were able to design codes involving up to one hundred physical qubits in a matter of minutes to hours. This scale is significant, as it matches the size of the most advanced quantum processors currently being built.

One of the most striking applications of this work involves codes designed for a specific type of physics problem known as the Fermi-Hubbard model, which describes how electrons move and interact in materials. In previous experiments, scientists could only verify that their calculations were correct by checking for broad symmetries. The new framework allowed the researchers to start with these natural symmetries and automatically extend them into a full error-correcting code. When they simulated this new code in a noisy environment, the results showed a dramatic improvement. The accuracy of the calculated values was much higher than before, and the code required far fewer repeated measurements to get a reliable answer. This suggests that by letting the computer design the code based on the physics of the problem, scientists can get better results from their machines without needing more hardware.

The team also applied their method to the specific hardware limitations of real quantum devices. In many current machines, one type of error happens much more frequently than others. For example, a qubit might be much more likely to flip in one direction than another. Traditional codes treat all errors as equally likely, which is inefficient. The researchers used their framework to design "hardware-aware" codes that specifically target the most common errors. When they tested these custom codes against the current best-known designs for biased noise, the new codes performed better. They produced fewer logical errors, meaning the information remained intact for longer. This result is particularly important because it shows that tailoring the error correction to the specific weaknesses of the hardware can yield immediate performance gains.

Perhaps the most surprising discovery came when the team used their system to design new surface codes, a popular type of error-correcting code that arranges qubits in a grid. They asked the computer to find codes that shared the same physical layout as the best existing surface codes but were optimized for biased noise. The solver returned thousands of different valid codes. When the researchers tested these new designs, many of them outperformed the current state-of-the-art solution, known as the XZZX surface code. These new codes were not just slightly better; they represented a new class of designs that the researchers had not manually conceived. The fact that a computer could find these superior configurations in a short time suggests that there are many more efficient codes waiting to be discovered if we stop trying to design them by hand and start letting the machines do the searching.

This work does not claim to have solved the entire problem of quantum error correction, nor does it suggest that the hardest cases are easy. The researchers confirmed that the most difficult instances of their logic puzzle still require significant computing power. However, they have established a rigorous path forward. By proving that the problem is solvable for practical cases and by providing a tool that can incorporate both physical laws and hardware realities, they have opened a new door. The ability to design codes that are not just mathematically sound but also physically and hardware-aware brings the goal of a large-scale, useful quantum computer closer to reality. The framework is now available for other scientists to use, promising a future where quantum codes are no longer just hand-crafted artifacts, but dynamically engineered solutions tailored to the specific challenges of the machine and the problem they are meant to solve.

Technical Summary: Satisfying Quantum Codes

Problem Statement
The design of quantum error correction (QEC) codes is currently a largely manual process, often relying on analytical techniques derived from classical codes or mathematical inspiration. This approach frequently neglects specific problem symmetries and hardware constraints, such as non-uniform noise models or qubit inhomogeneity. While new codes are continuously developed, there has been no clear improvement over the surface code in over three decades, and designing codes that incorporate real-time error rates and hardware specifics remains difficult. Furthermore, the computational complexity of designing such codes has not been rigorously analyzed, leaving open the question of whether efficient general algorithms exist.

Methodology
The authors propose a highly general and flexible computational framework for designing quantum codes by formulating the problem as a Boolean Satisfiability (SAT) problem.

SAT Formulation: The design of a stabilizer code is translated into a set of Boolean constraints. The core requirements—commutativity of stabilizer generators and the ability to detect or correct a specific set of errors—are encoded as clauses in Conjunctive Normal Form (CNF).
- Code Discovery: Starting from an empty stabilizer group, the solver searches for a set of generators that satisfy error correction criteria for a given set of Pauli errors.
- Code Extension: Starting from a non-empty initial set of stabilizers (derived from a pre-existing code or physical symmetries), the solver finds additional stabilizers to extend the code, potentially increasing its distance.
- Hardware Awareness: The framework incorporates specific noise models by assigning weights to error constraints (Maximum Satisfiability), allowing the solver to prioritize the correction of the most probable errors on a specific device.
Complexity Analysis: The authors prove that the general quantum code design problem is NP-complete via a polynomial-time reduction from the $k$ -set cover problem. This establishes that no efficient algorithm exists for the general case. However, they analyze the average-case complexity, identifying a phase transition in satisfiability probability (SAT-UNSAT transition) similar to random $k$ -SAT problems. They observe that instances near this transition are computationally hardest, while under-constrained and over-constrained instances are solved quickly.
Solver Application: The framework leverages state-of-the-art SAT solvers to find solutions. It supports both "physics-inspired" design (incorporating problem symmetries) and "hardware-aware" design (incorporating noise models).

Key Contributions

General Framework: A unified SAT-based formalism that handles code discovery, code extension, physics-informed design, and hardware-aware design within a single flexible structure.
Complexity Proof: A rigorous proof that quantum code design is NP-complete, ruling out efficient general algorithms and providing a theoretical foundation for the field.
Distance-Increasing Extensions: Theoretical proofs and examples demonstrating that quantum codes can be extended to increase their distance, including extensions with and without "mutation" (modifying existing stabilizers).
Scalability: The ability to design codes with over 100 physical qubits in minutes to hours on standard hardware, significantly exceeding the scale of previous computational design methods (e.g., reinforcement learning approaches limited to ~25 qubits).

Results
The authors demonstrate the framework's utility through several applications:

Physics-Informed Codes (Fermi-Hubbard Model):
- The framework was used to extend the stabilizer group of the Fermi-Hubbard Hamiltonian (which naturally possesses particle number conservation symmetries) to correct additional errors.
- Performance: Simulations showed that extending these codes to higher distances ( $d=2, d=3$ ) significantly improved the accuracy of computed expectation values in noisy simulations compared to the baseline $d=1$ code.
- Scalability: Novel physics-inspired codes for $n=48$ and $n=100$ qubits were designed in minutes to hours. The $n=100$ case was solved in under five minutes for a specific target, outperforming prior multi-agent system results that took an hour.
Hardware-Aware Codes (Biased Noise):
- Fermi-Hubbard Extensions: Codes were designed for biased noise models (where $Z$ errors are more frequent than $X/Y$ ). These hardware-aware extensions achieved undetected error rates up to two orders of magnitude lower than hardware-unaware extensions for small noise biases.
- Surface Codes: The framework discovered novel surface-like codes for biased noise. Under a maximum likelihood decoder, many of these newly discovered codes exhibited lower logical error rates than the state-of-the-art XZZX surface code, which is specifically tailored for biased noise.
- Phase Transitions: Empirical analysis confirmed a SAT-UNSAT phase transition in random code design instances, where solver runtime peaks near the critical number of errors per stabilizer.

Significance and Claims
The paper claims that this work provides a rigorous theoretical framework for quantum code design, establishing its NP-completeness while simultaneously offering a practical tool that outperforms current state-of-the-art computational methods in scale and flexibility.

The authors emphasize that their framework accelerates the timeline toward large-scale error-corrected quantum computers by enabling the automated discovery of codes that are:

Tailored to Physics: Leveraging problem symmetries to improve error mitigation.
Tailored to Hardware: Optimized for specific noise profiles (e.g., biased noise) to lower logical error rates below existing benchmarks.
Scalable: Capable of handling problem sizes ( $n=100$ ) that were previously intractable for computational design methods.

The work does not claim to solve the decoding problem for these new codes (noting that efficient decoding for non-CSS codes remains an open challenge) nor does it claim to directly incorporate logical error rates into the SAT formulation (as this requires separate numerical measurement). Instead, it positions the SAT framework as a powerful engine for generating candidate codes that can then be validated and decoded using existing or future techniques.

Technical Summary: Satisfying Quantum Codes

More like this