Quantum Maximum Likelihood Decoding for Linear Block Codes
Hyun-Woo Jung, Jeonghwan Kang, Jeongseok Ha · 2020
While the maximum likelihood decoding (MLD) is optimal, it suffers from a high decoding complexity. In this work, we propose a quantum MLD (QMLD) for linear block codes, which provides an optimal decoding performance at reduced asymptotic complexity. To this end, we utilize the Diirr-Høyer Algorithm (DHA) to find out a codeword, cMLfor a received signal vector y maximizing the conditional probability Pr(y|c) among codewords in a linear code C. Meanwhile, the DHA requires a quantum state representing the equiprobable superposition of all possible codewords as its input. To resolve the technical challenge, this work proposes a novel quantum circuit that produces the input quantum state to the DHA. Complexities of the proposed QMLD and classic MLD will be compared, which clearly demonstrates the computational superiority of the proposed QMLD.