Quantum Maximum Likelihood Decoding for Linear Block Codes

Abstract

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 Durr-Hoyer Algorithm (DHA) to find out a codeword, c(ML) for a received signal vector y maximizing the conditional probability Pr(y vertical bar 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.