The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding

• URL: http://arxiv.org/abs/2603.22064v1
• Date: Mon, 23 Mar 2026 14:57:38 GMT
• Title: The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
• Abstract summary: We show that minimum-weight decoding is NP-hard in three quintessential settings.<n>Our results highlight a sharp computational complexity separation between minimum-weight decoding and its approximate realizations.
• Score: 42.44256445495892
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The decoding problem is a ubiquitous algorithmic task in fault-tolerant quantum computing, and solving it efficiently is essential for scalable quantum computing. Here, we prove that minimum-weight decoding is NP-hard in three quintessential settings: (i) the color code with Pauli $Z$ errors, (ii) the surface code with Pauli $X$, $Y$ and $Z$ errors, and (iii) the surface code with a transversal CNOT gate, Pauli $Z$ and measurement bit-flip errors. Our results show that computational intractability already arises in basic and practically relevant decoding problems central to both quantum memories and logical circuit implementations, highlighting a sharp computational complexity separation between minimum-weight decoding and its approximate realizations.

Related papers

• Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes [0.0]
  We study the computational complexity of minimum-weight decoding for topological quantum codes.<n>For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding.
  arXiv  Detail & Related papers  (2026-08-17T20:37:08Z)
• Quantum error correction at ultra-low overhead [0.0]
  Suppressing errors is the central challenge for useful large-scale quantum computing.<n>We introduce Cornucopia codes, a family of practical, hardware-efficient quantum low-density parity-check codes.<n>Results bring demonstrations of ultra-low overhead quantum error correction within the reach of near-term quantum processors.
  arXiv  Detail & Related papers  (2026-08-03T18:13:57Z)
• A polynomial-time approximation scheme for minimum-weight decoding of topological codes [42.44256445495892]
  Two-dimensional topological translationally in (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation.<n>Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings.
  arXiv  Detail & Related papers  (2026-06-16T16:44:08Z)
• Minimum Weight Decoding in the Colour Code is NP-hard [0.0]
  We show that exact decoding of the colour code is NP-hard -- that is, there does not exist an algorithm unless P=NP.<n>This highlights a notable contrast to some of the colour code's key competitors, such as the surface code.
  arXiv  Detail & Related papers  (2026-03-04T16:18:18Z)
• Bidirectional Decoding for Concatenated Quantum Hamming Codes [6.26319455798863]
  We introduce a hard-decision decoder ford quantum codes with time complexity for scaling.<n>For thed $[15,3]]$ quantum Hamming code under independent bit-flip noise, the bidirectional decoder improves the threshold.<n>Our results can enhance the competitiveness of low-overhead fault-tolerant quantum computation.
  arXiv  Detail & Related papers  (2026-01-14T04:09:37Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks.<n>We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings.<n>We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• Generative Decoding for Quantum Error-correcting Codes [6.964959672843989]
  We propose a decoding algorithm utilizing generative modeling in machine learning.<n>We employ autoregressive neural networks to learn the joint probability of logical operators and syndromes in an unsupervised manner.<n>Our approach highlights generative artificial intelligence as a potential solution for the real-time decoding of realistic and high-rate quantum error correction codes.
  arXiv  Detail & Related papers  (2025-03-27T11:08:03Z)
• Efficient and Universal Neural-Network Decoder for Stabilizer-Based Quantum Error Correction [44.698141103370546]
  GraphQEC is a code-agnostic decoder leveraging machine-learning on the graph structure of stabilizer codes with linear time complexity.<n>Our approach represents the first universal solution for real-time quantum error correction across arbitrary stabilizer codes.
  arXiv  Detail & Related papers  (2025-02-27T10:56:53Z)
• Demonstrating dynamic surface codes [118.67046728951689]
  We experimentally demonstrate three time-dynamic implementations of the surface code.<n>First, we embed the surface code on a hexagonal lattice, reducing the necessary couplings per qubit from four to three.<n>Second, we walk a surface code, swapping the role of data and measure qubits each round, achieving error correction with built-in removal of accumulated non-computational errors.<n>Third, we realize the surface code using iSWAP gates instead of the traditional CNOT, extending the set of viable gates for error correction without additional overhead.
  arXiv  Detail & Related papers  (2024-12-18T21:56:50Z)
• Near-optimal decoding algorithm for color codes using Population Annealing [44.99833362998488]
  We implement a decoder that finds the recovery operation with the highest success probability. We study the decoder performance on a 4.8.8 color code lattice under different noise models.
  arXiv  Detail & Related papers  (2024-05-06T18:17:42Z)
• Comparative study of quantum error correction strategies for the heavy-hexagonal lattice [41.94295877935867]
  Topological quantum error correction is a milestone in the scaling roadmap of quantum computers.<n>The square-lattice surface code has become the workhorse to address this challenge.<n>In some platforms, however, the connectivities are kept even lower in order to minimise gate errors.
  arXiv  Detail & Related papers  (2024-02-03T15:28:27Z)
• Facilitating Practical Fault-tolerant Quantum Computing Based on Color Codes [0.6963971634605797]
  In this work, we address several key issues to facilitate practical fault-tolerant quantum computing based on color codes. First, by introducing decoding graphs with error-rate-related weights, we obtained the threshold of $0.57%$ of the triangular color code. Second, our work firstly investigates the circuit-level decoding of color code lattice surgery, and gives an efficient decoding algorithm. Third, a new state injection protocol of the triangular color code is proposed, reducing the output magic state error rate in one round of 15 to 1 distillation by two orders of magnitude compared to a previous rough protocol.
  arXiv  Detail & Related papers  (2023-09-11T03:56:18Z)
• Constant-Overhead Fault-Tolerant Quantum Computation with Reconfigurable Atom Arrays [5.542275446319411]
  We propose a hardware-efficient scheme to perform fault-tolerant quantum computation with high-rate qLDPC codes on reconfigurable atom arrays. Our work paves the way for explorations of low-overhead quantum computing with qLDPC codes at a practical scale.
  arXiv  Detail & Related papers  (2023-08-16T19:47:17Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.