Information Communication Technologies Conference (ICTC)

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

Yuhang Guo, Han Zeng, Feng Xiong, Tian Luan, Zaichen Zhang, Xiaojun Wang

Published May 10, 2024• 1 citation

Abstract

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.

DOI: 10.1109/ictc61510.2024.10601825

Related papers

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

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

Practical MU-MIMO Detection and LDPC Decoding Through Digital Annealing

Po-Shao Chen, Wei Tang, Zhengya Zhang

Digital annealing has been successfully applied to solving combinatorial optimization (CO) problems. It is more flexible, robust, and easier to deploy on edge platforms compared to its counterparts including quantum annealing and analog and in-memory Ising machines. In this work, we apply digital annealing to compute-intensive communication digital signal processing problems, including multi-user detection in multiple-input and multiple-output (MU-MIMO) wireless communication systems and decoding low-density parity-check (LDPC) codes. We show that digital annealing can achieve near maximum likelihood (ML) accuracy for MIMO detection with even lower complexity than the conventional minimum mean square error (MMSE) detection. In LDPC decoding, we enhance digital annealing by introducing a new cost function that improves decoding accuracy and reduces computational complexity compared to the standard formulations.

Design, Automation, and Test in EuropeMar 31, 20250 citations

Evaluation of Quantum Annealer Performance via the Massive MIMO Problem

Zsolt Tabi, Ádám Marosits, Zsófia Kallus +3 more

Quantum annealing offers an appealing route to handle large-scale optimization problems. Existing Quantum Annealing processing units are readily available via cloud platform access for solving Quadratic Unconstrained Binary Optimization (QUBO) problems. In particular, the novel D-Wave Advantage device has been recently released. Its performance is expected to improve upon the previous state-of-the-art D-Wave 2000Q annealer, due to higher number of qubits and the Pegasus topology. Here, we present a comparative study via an ensemble of Maximum Likelihood (ML) Channel Decoder problems for MIMO scenarios in Centralized Radio Access Network (C-RAN) architectures. The main challenge for exact optimization of ML decoders with ever-increasing demand for higher data rates is the exponential increase of the solution space with problem sizes. Since current 5G solutions mainly use approximate methodologies, Kim et al. leveraged Quantum Annealing for large MIMO problems with Phase Shift Keying and Quadrature Amplitude Modulation scenarios. Here, we extend their work and analyze experiments for more complex modulations and larger MIMO antenna array sizes. By implementing the extended QUBO formulae on the novel annealer architecture, we uncover the limits of state-of-the-art quantum optimization for the massive MIMO ML decoder. We report on the improvements and discuss the uncovered limiting factors learned from the 64-QAM extension. We include the enhanced evaluation of raw annealer sampling via implementation of post-processing methods in the comparative analysis between D-Wave 2000Q and D-Wave Advantage system.

IEEE AccessJan 1, 202130 citations

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

Ismail, Refaat, Ashish Kakkar, Anatoly Y. Dymarsky

Quantum error-correcting codes (QECCs) are at the heart of fault-tolerant quantum computing. As the size of quantum platforms is expected to grow, one of the open questions is to design new optimal codes of ever-increasing size. A related challenge is to certify the quality of a given code by evaluating its minimum distance, a quantity characterizing code's capacity to preserve quantum information. This problem is known to be NP-hard. 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. Namely, we introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem and leveraging established QUBO algorithms and heuristics as well as quantum annealing (QA) to address the latter. The reformulation as a QUBO introduces only a logarithmic multiplicative overhead in the required number of variables. We demonstrate the formulation using the D-Wave Advantage 4.1 quantum annealer and the hybrid quantum-classical algorithm Qbsolv, and benchmark the resulting QUBO-based implementations against specialized classical distance-finding methods. The QA- and SA-assisted implementations show broadly comparable performance, while the classical comparison clarifies the relative strengths of heuristic optimization and exact distance certification. Our results establish a solver-independent QUBO formulation with only a logarithmic multiplicative overhead in the number of variables and characterize connectivity and minor embedding as central limitations of its present implementation on quantum-annealing hardware.

arXiv:2404.17703Apr 26, 20240 citations

Towards Quantum Computing: Solving Satisfiability Problem by Quantum Annealing

Juexiao Su

To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.

Jan 1, 20184 citations