The Value of Duplicate Measurements When Decoding Second-Order Reed-Muller Codes
In the authors' words
We compare the performance of the RPA and CHIRRUP decoding algorithms for second-order Reed--Muller codes. The RPA algorithm recovers a binary quadratic form associated with a skew-symmetric matrix , whereas CHIRRUP recovers a -valued quadratic form associated with a symmetric matrix . We describe how the Gray map connects the evaluation vectors of these forms, inducing a rank-preserving correspondence between and . We analyze how Euclidean distance between evaluation vectors is governed by matrix rank differences using Delsarte--Goethals sets . We demonstrate that CHIRRUP uses repeated measurements more effectively than RPA on these ensembles. While a kernel-aware variant of RPA improves performance on singular quadratic forms by aggregating projection directions across cosets of , CHIRRUP's tree search combines multiple row estimates more efficiently on when , outperforming vanilla RPA.
Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.