International Conference on Consumer Electronics

A New LDPC Code Decoding Method: Expanding the Scope of Ising Machines

Masashi Tawada, Shu Tanaka, Nozomu Togawa

Published Jan 1, 2020• 5 citations

Abstract

Low-density parity-check (LDPC) codes have previously been considered as combinatorial optimization problems (COPs) in respect to its decoding. However, after defining it as such, none have gone so far as to convert the LDPC code into a quadratic unconstrained binary optimization (QUBO) problem. Thus, a new method is created: one that converts the LDPC code to a QUBO problem, inputs the QUBO problem into Ising machines (computers based on the Ising model that are designed to solve the QUBO problem), obtains the QUBO solution and converts it to a LDPC solution. By utilizing an actual Ising machine, LDPC solutions with code length of 256-bits have been obtained with an accuracy of 93.9% by average annealing time 214.0ms. The benefit of this newfound methodology goes beyond its theoretical imprint of obtaining LDPC solutions more accurately. It has only been a few years since the Ising machine has been developed. Therefore, in formulating this method, one expands the currently scope of studies involving Ising machines, helping current and future researchers unlock its full range of capabilities and possibilities.

DOI: 10.1109/icce46568.2020.9043057

Related papers

Maximum-Likelihood Channel Decoding with Quantum Annealing Machine

Naoki Ide, Tetsuya Asayama, Hiroshi Ueno +1 more

We formulate maximum likelihood (ML) channel decoding as a quadratic unconstraint binary optimization (QUBO) and simulate the decoding by the current commercial quantum annealing machine, D-Wave 2000Q. We prepared two implementations with Ising model formulations, generated from the generator matrix and the parity-check matrix respectively. We evaluated these implementations of ML decoding for low-density parity-check (LDPC) codes, analyzing the number of spins and connections and comparing the decoding performance with belief propagation (BP) decoding and brute-force ML decoding with classical computers. The results show that these implementations are superior to BP decoding in relatively short length codes, and while the performance in the long length codes deteriorates, the implementation from the parity-check matrix formulation still works up to 1k length with fewer spins and connections than that of the generator matrix formulation due to the sparseness of parity-check matrices of LDPC.

arXiv:2007.08689Jul 16, 202014 citations

On Quantum-Enhanced LDPC Decoding for Rayleigh Fading Channels

Utso Majumder, Aditya Das Sarma, Vishnu Vaidya +1 more

Quantum and Classical computers continue to work together in tight cooperation to solve difficult problems. The combination is thus suggested in recent times for decoding the Low Density Parity Check (LDPC) codes, for the next generation Wireless Communication systems. In this paper we have worked out the Quadratic Unconstrained Binary Optimization (QUBO) formulation for Rayleigh Fading channels for two different scenarios- channel state fully known and not known. The resultant QUBO are solved using D-Wave 2000Q Quantum Annealer and the outputs from the Annealer are classically postprocessed, invoking the notion of diversity. Simple minimum distance decoding of the available copies of the outputs led to improved performance, compared to picking the minimum-energy solution in terms of Bit Error Rate (BER). Apart from providing these results and the comparisons to fully classical Simulated Annealing (SA) and the traditional Belief Propagation (BP) based strategies, some remarks about diversity due to quantum processing are also spelt out.

arXiv:2209.11994IEEE/ACM Symposium on Edge Computing (SEC)Dec 1, 20221 citation

Quantum Annealing with Post-processing of Maximum Likelihood for LDPC Decoding

Yuhang Guo, Han Zeng, Feng Xiong +3 more

In the forthcoming 6G era, driven by the escalating demands for enhanced performance and reliability in communication systems, Low-Density Parity-Check (LDPC) codes emerge as a robust error correction coding scheme poised to effectively meet these requirements. In recent years, with the advancement of quantum computing, a proposal has emerged to integrate classical and quantum computing for the decoding of LDPC. The LDPC decoding can be treated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, thereby allowing the utilization of the D-Wave 2000Q quantum annealer for solving it. Expanding on this groundwork, the paper proposes an approach to enhance quantum annealing performance using classical algorithms. Specifically, it involves performing quantum annealing on the problem first, followed by post-processed using Maximum Likelihood Estimation (MLE) for the multiple outputs, known as QAML. Furthermore, to fully exploit the advantages of quantum annealing, this paper incorporates the energy and frequency of occurrence of candidate codewords as prior information into the Maximum Likelihood Estimation. These are called QAMLE and QAMLF respectively, further enhancing decoding performance. The proposed method is evaluated and compared with direct Quantum Annealing (QA) and Quantum Annealing with post-processing using Minimum Distance (QAMD). Research findings indicate that QAML exhibits a lower bit error rate compared to QA and QAMD.

Information Communication Technologies Conference (ICTC)May 10, 20241 citation

Investigating the Characteristics of Ising Machines

Kazuhiko Komatsu, Makoto Onoda, Masahito Kumagai +1 more

Recently, Ising machines have garnered attention as accelerators for resolving combinatorial optimization problems by converting them into Quadratic Unconstrained Binary Optimization (QUBO) problems. Ising machines have been rapidly developed with various implementations. For instance, there are different Ising machines like quantum annealing machines that use analog quantum circuits, simulated annealing machines that use digital processors like CPU, GPU, and VE, and digital annealing machines that use digital circuits such as CMOS and FPGA. However, the characteristics of Ising machines have not been fully comprehended, because a standardized evaluation method and a commonly used benchmark program for Ising machines have not been established yet. This research focuses on combinatorial clustering as a benchmark program for the evaluation of Ising machines, aiming to investigate the characteristics of Ising machines.

IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 17, 20233 citations

Linearizing Binary Optimization Problems Using Variable Posets for Ising Machines

Kentaro Ohno, Nozomu Togawa

Ising machines are next-generation computers expected to efficiently sample near-optimal solutions of combinatorial optimization problems. Combinatorial optimization problems are modeled as quadratic unconstrained binary optimization (QUBO) problems to apply an Ising machine. However, current state-of-the-art Ising machines still often fail to output nearoptimal solutions due to the complicated energy landscape of QUBO problems. Furthermore, the physical implementation of Ising machines severely restricts the size of QUBO problems to be input as a result of limited hardware graph structures. In this study, we take a new approach to these challenges by injecting auxiliary penalties preserving the optimum, which reduces quadratic terms in QUBO objective functions. The process simultaneously simplifies the energy landscape of QUBO problems, allowing the search for near-optimal solutions, and makes QUBO problems sparser, facilitating encoding into Ising machines with restriction on the hardware graph structure. We propose linearization of QUBO problems using variable posets as an outcome of the approach. By applying the proposed method to synthetic QUBO instances and to multi-dimensional knapsack problems, we empirically validate the effects on enhancing minorembedding of QUBO problems and the performance of Ising machines.

arXiv:2307.05125IEEE Transactions on Emerging Topics in ComputingMay 30, 20244 citations

基于QUBO建模与量子退火的LDPC码混合译码研究

宇桐张

Low-Density Parity-Check (LDPC) codes, as a class of high-efficiency error-correcting codes with sparse parity-check matrices, have demonstrated enormous potential in the field of communications since their rediscovery, and have become a core coding scheme especially in the fifth-generation (5G) wireless communication systems. To address the decoding problem of LDPC codes in complex channel environments, this paper proposes an innovative quantum-classical hybrid decoding architecture. By transforming the decoding problem into a Quadratic Unconstrained Binary Optimization (QUBO) problem, the architecture leverages the parallel processing capability of coherent optical quantum computers to accelerate the iterative decoding process. The research focuses on two typical scenarios specified in the 5G standard: the high-throughput scenario (dominated by BG1 with long code length and high code rate) and the low-complexity scenario (dominated by BG2 with short code length and low code rate). Through establishing a rigorous mathematical model, a hybrid decoder based on quantum annealing and the belief propagation algorithm is designed in this paper, and the Bayesian optimization method is adopted to adaptively adjust key parameters such as the maximum number of iterations and damping factor. This research provides an important theoretical foundation and practical scheme for the practical application of quantum computing in the field of communications.

科学与技术探索Jan 8, 20260 citations