"Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks," Srikar Kasi and Kyle Jamieson

Thursday, Dec 10, 2020

Paper (arXiv.org): https://arxiv.org/abs/2007.11069


Presentation (YouTube): https://youtu.be/vy1erMe47t4

Proceedings of the 26th Annual ACM International Conference on Mobile Computing and Networking (MobiCom ’20)

Abstract:
We present Quantum Belief Propagation (QBP), a Quantum Annealing (QA) based decoder design for Low Density Parity Check (LDPC) error control codes, which have found many useful applications in Wi-Fi, satellite communications, mobile cellular systems, and data storage systems. QBP reduces the LDPC decoding to a discrete optimization problem, then embeds that reduced design onto quantum annealing hardware. QBP's embedding design can support LDPC codes of block length up to 420 bits on real state-of-the-art QA hardware with 2,048 qubits. We evaluate performance on real quantum annealer hardware, performing sensitivity analyses on a variety of parameter settings. Our design achieves a bit error rate of 10−8 in 20 μs and a 1,500 byte frame error rate of 10−6 in 50 μs at SNR 9 dB over a Gaussian noise wireless channel. Further experiments measure performance over real-world wireless channels, requiring 30 μs to achieve a 1,500 byte 99.99% frame delivery rate at SNR 15-20 dB. QBP achieves a performance improvement over an FPGA based soft belief propagation LDPC decoder, by reaching a bit error rate of 10−8 and a frame error rate of 10−6 at an SNR 2.5--3.5 dB lower. In terms of limitations, QBP currently cannot realize practical protocol-sized (e.g., Wi-Fi, WiMax) LDPC codes on current QA processors. Our further studies in this work present future cost, throughput, and QA hardware trend considerations.

Funding:
This research is supported by National Science Foundation (NSF) Award CNS-1824357, a gift from InterDigital corporation, and an award from the Princeton University School of Engineering and Applied Science Innovation Fund. Support from the USRA Cycle 3 Research Opportunity Program allowed machine time on a D-Wave machine hosted at NASA Ames Research Center.