Optimal Circuit Synthesis of Linear Codes for Error Detection and Correction

• URL: http://arxiv.org/abs/2604.03608v1
• Date: Sat, 04 Apr 2026 06:46:43 GMT
• Title: Optimal Circuit Synthesis of Linear Codes for Error Detection and Correction
• Abstract summary: Fault injection attacks deliberately inject faults into a device via physical channels to disturb its regular execution.<n>We formalize the optimal code circuit problem (OptiCC) based on two domain-specific minimization objectives on individual inputs and parity size.<n>We then propose a novel algorithm CiSC for solving OptiCC, prioritizing the minimization of individual inputs.
• Score: 11.02232592575343
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fault injection attacks deliberately inject faults into a device via physical channels to disturb its regular execution. Adversaries can effectively deduce secrets by analyzing both the normal and faulty outputs, posing serious threats to cryptographic primitives implemented in hardware. An effective countermeasure to such attacks is via redundancy, commonly referred to as concurrent error detection schemes, where Binary linear codes have been used to defend against fault injection attacks. However, designing an optimal code circuit is often time-consuming, error-prone, and requires substantial expertise. In this paper, we formalize the optimal code circuit synthesis problem (OptiCC) based on two domain-specific minimization objectives on individual inputs and parity size. We then propose a novel algorithm CiSC for solving OptiCC, prioritizing the minimization of individual inputs. Our approach features both correct-by-construction and secure-by-construction. In a nutshell, CiSC gradually reduces individual inputs and parity size by checking, via SMT solving, the existence of feasible Boolean functions for implementing a desired code. We further present an effective technique to lazily generate combinations of inputs to Boolean functions, while quickly identify equivalent ones. We implement our approach in a tool CiSC, and evaluate it on practical benchmarks. Experimental results show our approach can synthesize code circuits that significantly outperform those generated by the latest state-of-the-art techniques.

Related papers

• Optimal Decoding of Small Codes by Density Matrix Propagation [0.0]
  We study the accuracy of practical decoding algorithms under circuit-level noise.<n>We apply this framework to small instances of the repetition code and a cellular automaton code.<n>We find significant deviations for the cellular code, with BP+OSD deteriorating already in experimentally relevant noise regimes.
  arXiv  Detail & Related papers  (2026-06-12T13:43:44Z)
• Synthesis and Optimization of Encoding Circuits for Fault-Tolerant Quantum Computation [4.561664406615985]
  We develop methods for synthesizing efficient encoders for arbitrary stabilizer codes.<n>For families with a modular structure, such as tableaud and holographic codes, we show how large encoders can be assembled from optimized local constituent encoders.<n>We obtain improvements of up to 43% in two-qubit gate count and up to 70% in depth.
  arXiv  Detail & Related papers  (2026-05-14T18:00:01Z)
• Degeneracy Cutting: A Local and Efficient Post-Processing for Belief Propagation Decoding of Quantum Low-Density Parity-Check Codes [0.9558392439655014]
  Quantum low-density parity-check (qLDPC) codes are promising for realizing scalable fault-tolerant quantum computation.<n>A common approach to decoding qLDPC codes is to use the belief propagation (BP) decoder, followed by a post-processing step to enhance decoding accuracy.<n>For real-time decoding, the post-processing algorithm is desirable to have a small computational cost and rely only on local operations on the Tanner graph to facilitate parallel implementation.<n>We propose degeneracy cutting (DC), an efficient post-processing technique for the BP decoder that operates on information restricted to the support of each stabilizer
  arXiv  Detail & Related papers  (2025-10-09T18:01:30Z)
• Planar Fault-Tolerant Quantum Computation with Low Overhead [5.232949916418351]
  We introduce code craft, a framework for designing fault-tolerant logical operations on planar BB codes.<n>We show that logical operations, including controlled-NOT gates, state transfers, and Pauli measurements, can be efficiently implemented within this framework.
  arXiv  Detail & Related papers  (2025-06-22T15:07:03Z)
• 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)
• Threshold Selection for Iterative Decoding of $(v,w)$-regular Binary Codes [84.0257274213152]
  Iterative bit flipping decoders are an efficient choice for sparse $(v,w)$-regular codes.<n>We propose concrete criteria for threshold determination, backed by a closed form model.
  arXiv  Detail & Related papers  (2025-01-23T17:38:22Z)
• Efficient Approximate Degenerate Ordered Statistics Decoding for Quantum Codes via Reliable Subset Reduction [5.625796693054094]
  We introduce the concept of approximate degenerate decoding and integrate it with ordered statistics decoding (OSD)<n>We present an ADOSD algorithm that significantly improves OSD efficiency in the code capacity noise model.
  arXiv  Detail & Related papers  (2024-12-30T17:45:08Z)
• Accelerating Error Correction Code Transformers [56.75773430667148]
  We introduce a novel acceleration method for transformer-based decoders. We achieve a 90% compression ratio and reduce arithmetic operation energy consumption by at least 224 times on modern hardware.
  arXiv  Detail & Related papers  (2024-10-08T11:07:55Z)
• Low-Overhead Transversal Fault Tolerance for Universal Quantum Computation [36.3664581543528]
  We show that logical operations can be performed fault-tolerantly with only a constant number of extraction rounds.<n>Our work sheds new light on the theory of quantum fault tolerance and has the potential to reduce the space-time cost of practical fault-tolerant quantum computation by over an order of magnitude.
  arXiv  Detail & Related papers  (2024-06-25T15:43:25Z)
• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  Low-Density Parity-Check (LDPC) codes possess several advantages over other families of codes. The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
  arXiv  Detail & Related papers  (2024-06-09T12:08:56Z)
• Fault-Tolerant Computing with Single Qudit Encoding [49.89725935672549]
  We discuss stabilizer quantum-error correction codes implemented in a single multi-level qudit. These codes can be customized to the specific physical errors on the qudit, effectively suppressing them. We demonstrate a Fault-Tolerant implementation on molecular spin qudits, showcasing nearly exponential error suppression with only linear qudit size growth.
  arXiv  Detail & Related papers  (2023-07-20T10:51:23Z)
• Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimization [60.72410937614299]
  We propose a new tractable bi-level optimization problem, design and analyze a new set of algorithms termed Bi-level AT (FAST-BAT) FAST-BAT is capable of defending sign-based projected descent (PGD) attacks without calling any gradient sign method and explicit robust regularization.
  arXiv  Detail & Related papers  (2021-12-23T06:25:36Z)
• Targeted Attack against Deep Neural Networks via Flipping Limited Weight Bits [55.740716446995805]
  We study a novel attack paradigm, which modifies model parameters in the deployment stage for malicious purposes. Our goal is to misclassify a specific sample into a target class without any sample modification. By utilizing the latest technique in integer programming, we equivalently reformulate this BIP problem as a continuous optimization problem.
  arXiv  Detail & Related papers  (2021-02-21T03:13:27Z)

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.