Refat Ismail, Ashish Kakkar, and Anatoly Dymarsky of the University of Kentucky have devised a new method to assess the quality of quantum error-correcting codes, a critical component for building practical quantum computers. The researchers tackled the notoriously difficult, NP-hard problem of determining a code’s minimum distance, a measure of its ability to preserve quantum information, by reformulating it as a Quadratic Unconstrained Binary Optimization (QUBO) problem.

Their approach, tested with the D-Wave Advantage 4.1 quantum annealer and a hybrid quantum-classical algorithm called Qbsolv, achieved performance on par with the best available classical algorithms solving QUBO. Here we propose to harness the power of contemporary quantum platforms to address this question, and in this way help design quantum platforms of the future.

Quantum Stabilizer Codes and Logical Hilbert Space

Stabilizer codes, a prevalent class of quantum error-correcting codes, rely on restricting quantum algorithms to a specific subspace within the full computational Hilbert space, a concept central to protecting quantum information. This restriction defines the logical Hilbert space where quantum operations take place, and the efficiency of this restriction directly impacts the resources needed for error correction. Designing codes that maximize the ratio of logical to physical qubits, while simultaneously increasing the minimum distance, a measure of error resilience, remains a significant challenge.

Currently, finding the optimal balance between these factors for ever-increasing code sizes is an open problem. The minimum distance of a quantum code, denoted as ‘d’, directly determines its capacity to preserve quantum information, yet calculating this value for stabilizer codes is known to be an NP-hard problem, meaning the computational effort grows exponentially with code size.

Self-dual stabilizer codes, a specific type where the number of logical qubits is zero, are used for error detection protocols, initializing a quantum processor in a known state and checking for deviations over time. The ability to efficiently determine the minimum distance of quantum stabilizer codes is important for certifying the quality of quantum platforms.

This work offers a pathway toward designing and validating future quantum systems. The researchers emphasize that stabilizer codes are widely considered the best strategy to achieve fault tolerance in the near term, making improvements to their design and certification particularly impactful.

Minimum Distance ‘d’ Defines Quantum Information Capacity

Further work will explore extending this approach to other NP-hard problems in information theory and discrete mathematics, such as the shortest lattice vector problem, which shares conceptual similarities with the code minimum distance problem. “Looking ahead, an important step would be to extend our approach to other problems of classical and quantum information theory and discrete mathematics,” the authors state. The team expresses gratitude to D-Wave for providing access to their quantum cloud services, Leap, facilitating this research.

QUBO Reformulation Enables Quantum Annealing Approach

This approach uses existing QUBO algorithms and heuristics, alongside quantum annealing, to tackle a challenge central to designing and certifying future quantum platforms. The work extends a growing effort to recast numerous computationally difficult, NP-hard problems, including those in machine learning and RNA folding, into the QUBO framework, facilitating exploration with both classical and quantum solvers. Understanding this potential scaling and definitively certifying a quantum advantage for the QUBO-based approach remains an important task for future research.

The researchers state, positioning their work as a contribution to a broader trend in computational problem-solving. The QUBO formulation is also directly applicable to linear classical codes, broadening its potential impact beyond the quantum realm.

D-Wave Advantage 4.1 and Qbsolv Hybrid Algorithm Testing

The D-Wave Advantage 4.1 quantum annealer, paired with the Qbsolv hybrid algorithm, achieved performance comparable to the best classical algorithms solving quadratic unconstrained binary optimization (QUBO) problems, a result demonstrating competitive viability for quantum approaches to code design. Shifting focus to mitigate these connectivity limitations, the team employed Qbsolv, a hybrid algorithm developed by, to combine the strengths of both quantum and classical computation. The use of Qbsolv allowed researchers to address the minimum distance problem while circumventing some of the limitations inherent in a purely quantum approach.

Performance of Hybrid Approach Matches Classical QUBO Solvers

This parity in performance was achieved by comparing results from the D-Wave Advantage 4.1 quantum annealer and the Qbsolv algorithm against established classical methods, including simulated annealing. While currently lagging behind the most effective deterministic algorithms for finding minimal distances, the QUBO-based approach may become more advantageous as quantum platforms continue to grow in scale.

Simulations focused on optimal self-dual codes, using known minimum distances for smaller codes as a benchmark for comparison, and revealed that a purely quantum approach often yielded conservative values, failing to reach the optimum. The team’s work suggests that certain QUBO problems inherent to this code structure may be fundamentally difficult, regardless of the implementation used to solve them.

However, the demonstrated competitive performance of the hybrid approach provides a viable pathway toward designing and certifying larger, more complex quantum platforms. “Our study has shown that the hybrid quantum/classical approach is already demonstrating performance at the level of purely classical optimization scheme, possibly opening a new avenue for near-future practical applications of quantum annealing,” the researchers stated.

Logarithmic Variable Overhead in QUBO Problem Formulation

This efficiency stems from the method’s ability to represent the complex calculations with a scalable number of optimization variables, specifically O(n ln n), where ‘n’ represents the size of the code. While the study bypassed certain code lengths due to computational resource limitations, the consistent performance of the hybrid method demonstrates a promising pathway toward harnessing the capabilities of contemporary quantum platforms. The underlying motivation, according to the paper, is to ultimately design better quantum error-correcting protocols by reformulating a well-known NP-hard problem in a way suitable for quantum processors.

The ability to translate the minimum distance problem into a QUBO format represents a step toward using quantum computation for coding theory. “Our QUBO reformulation requires O(n ln n) optimization variables,” the researchers state, “representing only a logarithmic multiplicative overhead.” This efficient variable scaling is critical for managing the complexity of quantum algorithms and potentially unlocking new possibilities in quantum error-correcting codes. The work emphasises the potential of combining classical and quantum techniques to address challenges in quantum information science.

Adiabatic Quantum Computing and Quantum Annealing Principles

Adiabatic Quantum Computing (AQC) relies on gradually evolving a quantum system’s Hamiltonian from a simple, easily prepared state to one whose ground state represents the solution to a computational problem. This process, guided by the adiabatic theorem, aims to maintain the system in its ground state throughout the evolution, ensuring an accurate result. The University of Kentucky team used AQC principles through quantum annealing, a heuristic approach designed to find approximate solutions to optimization problems.

This method begins with an initial Hamiltonian and slowly transitions it over time toward a problem Hamiltonian, with the final ground state ideally encoding the solution. Analysis focused on how the quality of the solution correlated with the annealing time, an important parameter controlling the adiabatic evolution. The study’s findings suggest that, for this specific problem, contemporary quantum platforms can deliver competitive results, potentially opening the way to more efficient quantum error correction schemes.

👉 More information
🗞 Quantum annealing approach to the minimum distance problem of quantum codes
✍️ Refaat Ismail, Ashish Kakkar and Anatoly Dymarsky
🧠 DOI: http://link.aps.org/doi/10.1103/573l-6cc2

More like this