⚛️ quantum physics

A quantum annealing approach to the minimum distance problem of quantum codes

This paper proposes a solver-independent QUBO formulation with logarithmic variable overhead to compute the minimum distance of quantum stabilizer codes, demonstrating its feasibility on D-Wave quantum annealers while highlighting connectivity and embedding as current hardware limitations.

Original authors: Refaat Ismail, Ashish Kakkar, Anatoly Dymarsky

Published 2026-10-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Refaat Ismail, Ashish Kakkar, Anatoly Dymarsky

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 supercomputers thousands of years to crack, but they are incredibly fragile. To make them useful, scientists must protect the information they hold from the slightest bit of noise or interference. They do this by building "quantum error-correcting codes," which act like a safety net, spreading a single piece of information across many physical particles so that if one fails, the data can still be recovered. The strength of this safety net is measured by a value called the "minimum distance." Think of this distance as the number of separate errors a code can withstand before the information is lost. The larger the distance, the better the code. However, figuring out exactly how strong a specific code is, especially as it grows larger, is a task so difficult that it belongs to a class of problems known as "NP-hard," meaning the time required to solve them grows explosively as the problem gets bigger.

A team of researchers at the University of Kentucky has taken a new approach to this challenge by asking if the very machines we hope will one day solve these hard problems can help us design better ones today. They developed a method to translate the question of "how strong is this code?" into a format that modern quantum machines can understand and attempt to solve. This format, known as a quadratic unconstrained binary optimization problem, is essentially a way of arranging a set of switches to find the most efficient configuration. The researchers reformulated the code-strength problem into this language, adding only a manageable amount of extra complexity. They then tested their method on a real quantum machine, the D-Wave Advantage 4.1, which uses a process called quantum annealing to search for the best solution by slowly evolving a system from a simple state to a complex one.

The results of this experiment offer a clear picture of where quantum technology stands right now. When the researchers ran their new method on the quantum annealer, it successfully found the exact strength of the codes for smaller sizes, up to a certain point. However, as the codes grew larger, the machine began to struggle, often providing a safe but conservative estimate rather than the precise answer. The team found that the performance of the quantum machine was heavily influenced by how long they let it run. If the process was too short, the machine didn't have enough time to find the best answer; if it ran too long, the machine's inherent noise began to corrupt the result. They discovered that a specific duration of about 4.5 microseconds was the sweet spot for their tests.

To see if this quantum approach was truly useful, the team compared it against two other methods: a hybrid approach that splits the problem between a classical computer and the quantum machine, and a purely classical method that uses standard, well-established algorithms. The hybrid quantum-classical method performed similarly to a purely classical heuristic method, meaning the quantum part did not provide a significant speed advantage over the classical part in this specific test. More importantly, when compared to specialized classical algorithms designed specifically to find code distances, the quantum methods fell short. The specialized classical tools were able to find the exact answers for all the codes tested within the same amount of time, while the quantum methods could not.

The study suggests that while the new method of translating the problem into a format suitable for quantum machines is mathematically sound and efficient in theory, the current hardware is not yet powerful enough to beat the best classical computers at this specific task. The main bottleneck is not the number of variables in the problem, but the way the quantum machine connects its internal parts. To run the problem on the hardware, the researchers had to use a technique called "minor embedding," which links many physical components together to represent a single logical variable. This process caused the number of physical components needed to grow much faster than the problem size itself, creating a significant overhead that limited the size of the codes they could test.

Despite not outperforming classical computers in this instance, the work provides a valuable proof of concept. It demonstrates that the difficult problem of certifying quantum code quality can be successfully mapped onto a quantum framework with only a logarithmic increase in complexity. The researchers conclude that the current limitations are likely due to the specific hardware used, particularly its connectivity and noise levels, rather than a fundamental flaw in the approach. As quantum machines become more connected and less noisy in the future, this method could become a powerful tool for designing the robust quantum computers of tomorrow. For now, the study serves as a realistic benchmark, showing that while quantum annealing is a promising avenue, the specialized classical tools remain the most effective way to certify the quality of quantum codes today.

Technical Summary: A Quantum Annealing Approach to the Minimum Distance Problem of Quantum Codes

Problem Statement
The minimum distance ( $d$ ) of a quantum error-correcting code (QECC) is a critical parameter defining the code's capacity to preserve quantum information. Specifically, $d$ represents the smallest weight of an undetectable error (a logical Pauli operator). Determining $d$ for a general binary stabilizer code is known to be an NP-hard problem. While specialized classical algorithms exist (e.g., those by Grassl and White), the authors aim to explore whether contemporary quantum platforms can offer a viable alternative or a new pathway for evaluating or bounding this quantity, particularly as quantum hardware scales.

Methodology
The authors propose reformulating the minimum distance problem for binary quantum stabilizer codes as a Quadratic Unconstrained Binary Optimization (QUBO) problem. This reformulation allows the problem to be solved using established QUBO solvers, including classical heuristics, hybrid quantum-classical algorithms, and quantum annealing (QA).

The core algorithmic steps involve:

Pauli Weight Representation: The weight of a Pauli operator is expressed using binary vectors representing $X$ and $Z$ supports. The standard weight formula involves products of parity functions, which are non-quadratic.
Parity Decomposition: To achieve a quadratic form, the authors decompose the product of parities into a sum of three parity functions associated with matrices $A$ , $B$ , and $A+B$ .
Modular Arithmetic Elimination: The modulo-2 operations inherent in parity calculations are replaced by minimizing over auxiliary non-negative integer variables. These integers are then encoded using binary variables, introducing a logarithmic multiplicative overhead in the total number of variables. The total variable count scales as $O(n \log n)$ , where $n$ is the number of physical qubits.
Constraint Handling: The requirement that the solution must be a non-trivial logical operator (i.e., not in the stabilizer group) is handled in two ways:
- Penalty Method: Adding a penalty term to the cost function if the constraint is violated.
- Sector Decomposition: Splitting the problem into multiple unconstrained QUBOs by fixing the position of the first non-zero component of the solution vector. For circulant self-dual codes, symmetries allow the constraint to be satisfied by fixing a single variable ( $x_1=1$ ), reducing the problem to a single unconstrained QUBO.

Experimental Implementation and Results
The authors tested their formulation using the D-Wave Advantage 4.1 quantum annealer and the Qbsolv hybrid quantum-classical algorithm. They benchmarked these against:

Simulated Annealing (SA): A classical heuristic.
Specialized Classical Methods: The exact Brouwer–Zimmermann algorithm (BZDistMW) and the heuristic QDistRnd.

Key findings include:

Pure Quantum Annealing: For small code sizes ( $n \leq 12$ ), the QA successfully found the exact minimum distance. However, for larger sizes ( $n \geq 13$ ), performance degraded, and QA could only provide conservative upper bounds. The authors attribute this to limited qubit connectivity requiring "minor embedding," which increases the physical qubit count quadratically ( $O(n^2 \log^2 n)$ effective physical requirement) and introduces noise.
Hybrid vs. Classical: The QA-assisted and SA-assisted Qbsolv implementations showed broadly comparable performance. Both were less effective than specialized classical distance-finding methods (specifically QDistRnd) on the tested instances within matched wall-clock time budgets.
Runtime Analysis: Numerical simulations of the annealing dynamics suggested that theoretically required annealing times are in the nanosecond range. However, on the actual hardware, the optimal performance was observed at an annealing time of approximately $4.5 \, \mu s$ , suggesting that performance is currently dominated by noise accumulation rather than non-adiabatic transitions.

Key Contributions

QUBO Formulation: The paper introduces a solver-independent QUBO formulation for the minimum distance problem of binary stabilizer codes.
Variable Scaling: The method introduces only a logarithmic multiplicative overhead in the number of variables ( $O(n \log n)$ ), making it theoretically scalable for larger logical problems, provided hardware connectivity improves.
Empirical Benchmarking: The work provides a rigorous comparison of quantum, hybrid, and classical approaches for this specific NP-hard problem, highlighting the current limitations of quantum annealing hardware (specifically connectivity and noise) relative to mature classical algorithms.

Significance and Claims
The authors modestly frame the significance of their work as a proof-of-concept for the QUBO formulation rather than a demonstration of quantum advantage.

They explicitly state that their results do not show a computational advantage for the current quantum-annealing implementation over specialized classical methods.
The primary value lies in establishing a framework that can be utilized by future, more powerful quantum platforms and general-purpose QUBO solvers.
The paper identifies minor embedding and connectivity as the central limitations of the current implementation on quantum annealing hardware.
The authors suggest that this approach could be extended to other NP-hard problems in information theory, such as the shortest lattice vector problem, which shares conceptual similarities with the code minimum distance problem.

In conclusion, while the current hardware does not outperform classical solvers, the reformulation provides a viable pathway for future exploration as quantum hardware connectivity and quality improve.

Technical Summary: A Quantum Annealing Approach to the Minimum Distance Problem of Quantum Codes

More like this