The high complexity of some classic communication schemes often prevents their implementation. Quantum computers that utilize quantum mechanics such as superposition and entanglement can perform more efficient calculations with low computational complexity than classical computers for specific problems. Recently, quantum algorithms for classic communication problems have been proposed. However, few quantum algorithms for decoding error correcting codes have been proposed. In this paper, therefore, we propose two quantum-assisted decoders for error correcting codes that reduce the computational complexity of the maximum likelihood decoder for the linear codes and the sum-product algorithm decoder for non-binary low-density parity-check codes. Also, simulation results confirm that proposed decoding schemes can significantly reduce the computational complexity with similar performance compared to the classical decoders.
기존의 통신 문제들의 높은 계산 복잡도 때문에, 실제 구현하는 데 있어 어려움을 겪고 있다. 한편 양자의 중첩 및 얽힘과 같은 양자의 물리적 현상을 활용한 양자 컴퓨터는 특정 문제에 대하여 고전 컴퓨터에 비해 더 짧은 시간에 더 효율적인 계산을 할 수 있다. 최근에는 양자 알고리즘을 이용하여 기존의 통신 문제를 해결하는 방법들이 제안되어왔다. 하지만 오류 정정 부호의 복호화 문제를 양자 알고리즘을 이용하여 해결한 방법은 많이 제안되지 않았다. 따라서 본 논문에서는 양자 알고리즘을 이용하여 선형 부호의 최대 우도 복호기와 비이진 저밀도 패리티 검사 부호의 합곱 알고리즘을 이용한 복호기의 계산 복잡도를 낮추는 두 가지의 오류 정정 부호의 양자 복호기를 제안한다. 또한 실험 결과를 통해 기존의 복호기와 유사한 성능을 나타내지만, 계산 복잡도를 획기적으로 줄이는데 효과적임을 보여준다.
