TY - CONF
T1 - Towards quantum belief propagation for LDPC decoding in wireless networks
AU - Kasi, Srikar
AU - Jamieson, Kyle
N1 - Funding Information:
We thank the anonymous shepherd and reviewers of this paper for their extensive technical feedback, which has enabled us to significantly improve the work. We also thank Davide Venturelli, Catherine McGeoch, the NASA Quantum AI Laboratory (QuAIL), D-Wave Systems, and the Princeton Advanced Wireless Systems (PAWS) Group for useful discussions. 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.
Publisher Copyright:
© 2020 ACM.
PY - 2020
Y1 - 2020
N2 - 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 108 in 20 μs and a 1,500 byte frame error rate of 106 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 108 and a frame error rate of 106 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.
AB - 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 108 in 20 μs and a 1,500 byte frame error rate of 106 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 108 and a frame error rate of 106 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.
KW - belief propagation
KW - channel coding
KW - embedding
KW - LDPC codes
KW - quantum annealing
KW - quantum computation
KW - wireless networks
UR - http://www.scopus.com/inward/record.url?scp=85102543675&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102543675&partnerID=8YFLogxK
U2 - 10.1145/3372224.3419207
DO - 10.1145/3372224.3419207
M3 - Paper
AN - SCOPUS:85102543675
SP - 663
EP - 676
T2 - 26th Annual International Conference on Mobile Computing and Networking, MobiCom 2020
Y2 - 21 September 2020 through 25 September 2020
ER -