Designing quantum circuits for decoding binary linear codes

Abstract In the coding theory, it is one of the most important research problems to find an efficient algorithm for the decoding process. A quantum computer is an innovative computing device that performs calculations using the principles of quantum mechanics. In this paper, we find a decoding algorithm for binary linear codes using quantum circuits; this is the first time that quantum circuits are used as a main tool for decoding binary linear codes. Our decoding algorithm is mainly based on Grover’s search algorithm. In detail, we study the process of implementing the exhaustive search using quantum circuits for decoding binary linear codes. For our purpose, we design a modified Grover’s algorithm (algorithm 1) using three tools: the matrix multiplier, the Hamming weight counter, and the state indicator. We present algorithm 2, which is a quantum decoding algorithm for binary linear codes. We illustrate algorithm 1 using the [7, 4, 3] Hamming code, and algorithm 2 is implemented by IBM Quantum Composer.