A quantum algorithm for single parity check code
Makhamisa Senekane, Mhlambululi Mafu, Motobatsi Maseli, Benedict Molibeli Taele · 2021
In coding theory, error-detecting and error-correcting codes are used to enable digital communication over a noisy communication channel. One of the most uncomplicated error-detecting codes is the single parity check code. The single parity check code detects the number of ones (1s) in a string of bits. If the number of ones is even, then the bit string is said to have even parity. On the other hand, if the number of ones is odd, then the string is said to have odd parity. The challenge with this approach is that it cannot be detected if there are an even number of errors. Also, it can not tell which bit is in error (the error may even be the parity bit itself); thus, it cannot fix the error. This means the single parity check has a one-bit error detection capability but no error correction capability. Therefore, in this work, we propose a novel quantum algorithm that can be used to implement a single parity check code. Quantum algorithms run on a quantum computer and achieve a speedup, or other efficiency improvements, over any possible classical algorithm. The critical advantage of this algorithm is that it maintains a constant circuit depth regardless of the length of the bit string. Thus, the circuit depth of our proposed algorithm does not increase with bit string length. This demonstrates the power and efficiency of quantum computing in performing a single parity check.