Saved in:
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.24633 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913065846439936 |
|---|---|
| author | Shutty, Noah Mandal, Avijit Ragavan, Seyoon Buzet, Quentin Chailloux, André Rubin, Nicholas C. Khan, Abid Boulebnane, Sami Shaydulin, Ruslan Azariah, John Jordan, Stephen P. |
| author_facet | Shutty, Noah Mandal, Avijit Ragavan, Seyoon Buzet, Quentin Chailloux, André Rubin, Nicholas C. Khan, Abid Boulebnane, Sami Shaydulin, Ruslan Azariah, John Jordan, Stephen P. |
| contents | It was pointed out in [JSW+25] that widely-studied optimization problems such as D-regular max-k-XORSAT can be reduced to decoding of LDPC codes, using quantum algorithms related to Regev's reduction. LDPC codes have very good decoders, such as Belief Propagation (BP), and this therefore makes D-regular max-k-XORSAT an enticing target for this class of quantum algorithms. However, BP was found insufficient to achieve quantum advantage. Here, we develop an intrinsically quantum decoding technique, which decodes classical LDPC codes subject to coherent superpositions of bit flip errors. For average-case instances of D-regular max-k-XORSAT drawn from Gallager's ensemble, this quantum decoder strongly outperforms classical belief propagation at many values of k and D. For some (k,D) the approximate optima achievable using this decoder surpass both Prange's algorithm and simulated annealing. However, we stop short of achieving quantum advantage because we identify an enhancement to Prange's algorithm that recovers a precise tie, much as a precise tie was observed between the standard version of Prange's algorithm and a more limited version of locally-quantum decoding in [CT24]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_24633 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimization Using Locally-Quantum Decoders Shutty, Noah Mandal, Avijit Ragavan, Seyoon Buzet, Quentin Chailloux, André Rubin, Nicholas C. Khan, Abid Boulebnane, Sami Shaydulin, Ruslan Azariah, John Jordan, Stephen P. Quantum Physics It was pointed out in [JSW+25] that widely-studied optimization problems such as D-regular max-k-XORSAT can be reduced to decoding of LDPC codes, using quantum algorithms related to Regev's reduction. LDPC codes have very good decoders, such as Belief Propagation (BP), and this therefore makes D-regular max-k-XORSAT an enticing target for this class of quantum algorithms. However, BP was found insufficient to achieve quantum advantage. Here, we develop an intrinsically quantum decoding technique, which decodes classical LDPC codes subject to coherent superpositions of bit flip errors. For average-case instances of D-regular max-k-XORSAT drawn from Gallager's ensemble, this quantum decoder strongly outperforms classical belief propagation at many values of k and D. For some (k,D) the approximate optima achievable using this decoder surpass both Prange's algorithm and simulated annealing. However, we stop short of achieving quantum advantage because we identify an enhancement to Prange's algorithm that recovers a precise tie, much as a precise tie was observed between the standard version of Prange's algorithm and a more limited version of locally-quantum decoding in [CT24]. |
| title | Optimization Using Locally-Quantum Decoders |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2604.24633 |