pith. sign in

arxiv: 2606.13570 · v1 · pith:UCLPZKEOnew · submitted 2026-06-11 · 🪐 quant-ph · cs.CC· cs.DS

Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry

Maximilian J. Kramer , Carsten Schubert , Jens Eisert This is my paper

Pith reviewed 2026-06-27 06:25 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.DS
keywords max-LINSATbounded degreeNP-hardnessapproximation algorithmsdecoded quantum interferometryfinite fieldsDQIquantum algorithms
0
0 comments X

The pith

It is NP-hard to approximate bounded-degree max-Ek-LINSAT over finite fields better than r/q plus order 1/sqrt(D).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that for max-Ek-LINSAT(q,r) instances with each variable in at most D constraints over any finite field F_q, no polynomial-time algorithm can exceed the random-guessing value r/q by more than an additive O(1/sqrt(D)) term unless P=NP. This extends known Boolean hardness results to general fields while preserving the bounded-degree property. The result provides a complexity benchmark for algorithms like decoded quantum interferometry and QAOA on such instances. Any quantum advantage on these bounded-degree problems must therefore come from improving the constant factor rather than the scaling with D. In the DQI setting on regular instances, the paper shows that classical decoders are limited by a 1/sqrt(D log D) barrier while quantum decoders align with the 1/sqrt(D) hardness scaling.

Core claim

For general max-k-XORSAT with k at least 3, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless P equals NP, but with bounded degree D polynomial-time algorithms can beat the random baseline by order 1/sqrt(D). The paper proves this hardness extends to max-Ek-LINSAT(q,r) with bounded degree D over arbitrary finite fields F_q, establishing that it is NP-hard to exceed r/q plus O_{q,r}(1/sqrt(D)). These results benchmark DQI, QAOA and classical heuristics on the targeted bounded-degree instances. On (k,D)-regular instances DQI with classical decoders faces a 1/sqrt(D log D) information-theoretic barrier while DQI with quantum decoders is

What carries the argument

The NP-hardness reduction that preserves both the bounded-degree property D and the precise approximation gap r/q plus O(1/sqrt(D)) for instances over arbitrary finite fields F_q.

If this is right

  • Quantum advantage on bounded-degree instances is confined to the constant prefactor.
  • DQI with classical decoders cannot match the 1/sqrt(D) hardness scaling due to the extra log D factor in the information-theoretic barrier.
  • DQI with quantum decoders can in principle achieve the optimal 1/sqrt(D) scaling on (k,D)-regular instances.
  • The benchmark applies equally to QAOA and other heuristics targeting the same bounded-degree instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Future decoder designs for DQI should prioritize constant-factor improvements to reach the hardness limit.
  • The classical-versus-quantum decoder distinction may apply to other hybrid algorithms that combine interferometry with post-processing.
  • Explicit construction of (k,D)-regular instances saturating the hardness gap would allow direct numerical tests of whether quantum decoding closes the gap.
  • The result leaves open whether the O(1/sqrt(D)) term can be tightened to a specific leading constant for particular q and r.

Load-bearing premise

The reduction establishing hardness for general finite fields preserves both the bounded-degree property and the precise approximation gap.

What would settle it

A polynomial-time algorithm achieving approximation ratio r/q + c/sqrt(D) for some c smaller than the O_{q,r} constant on bounded-degree max-Ek-LINSAT instances over F_q would falsify the hardness claim.

Figures

Figures reproduced from arXiv: 2606.13570 by Carsten Schubert, Jens Eisert, Maximilian J. Kramer.

Figure 1
Figure 1. Figure 1: Degree reduction ϕ → ϕw → ϕR → ϕD˜ on an example with n = 6, m = 5, arity k = 3, with variable degree vector (o1, . . . , o6) = (3, 3, 3, 2, 2, 2) and degree bound D˜ = 3. Each panel transition represents a larger step of the construction. The first panel visualizes the input instance as a graph, showing which variables belong to which constraints. In the second panel, the weighted instance ϕw is shown: Ea… view at source ↗
Figure 2
Figure 2. Figure 2: Approximability landscape for bounded-degree max-E [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
read the original abstract

For general max-k-XORSAT with $k \geq 3$, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless $\mathsf{P} = \mathsf{NP}$: approximating beyond the random-assignment value of $1/2$ is $\mathsf{NP}$-hard. The picture changes when each variable appears in at most $D$ constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order $1/\sqrt{D}$. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields $\mathbb{F}_q$, proving that it is $\mathsf{NP}$-hard to exceed $r/q + \mathcal{O}_{q,r}(1/\sqrt{D})$. These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on $(k,D)$-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic $1/\sqrt{D \log D}$ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the $1/\sqrt{D}$ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that approximating max-Ek-LINSAT(q,r) over F_q on instances of maximum degree D is NP-hard beyond the random-assignment value r/q + O_{q,r}(1/sqrt(D)). It positions this as a complexity-theoretic benchmark for decoded quantum interferometry (DQI), QAOA and classical heuristics on bounded-degree instances, and shows that on (k,D)-regular instances DQI with classical decoders is limited by a 1/sqrt(D log D) information-theoretic barrier while quantum decoders remain compatible with the 1/sqrt(D) scaling.

Significance. If the hardness result and the decoder comparison hold, the work supplies a tight classical benchmark that confines any quantum advantage on these instances to constant-factor improvements and identifies quantum decoding as the ingredient needed to match the optimal scaling. The explicit link between bounded-degree CSP hardness and DQI performance models is a useful contribution to the literature on quantum algorithms for constraint satisfaction.

major comments (2)
  1. [reduction section (likely §3–4)] The central hardness claim rests on a reduction from Boolean bounded-degree max-k-XORSAT (known to have gap 1/2 + Θ(1/sqrt(D))) to max-Ek-LINSAT(q,r) that must simultaneously preserve maximum degree ≤ D and produce an optimum at most r/q + O_{q,r}(1/sqrt(D)). The manuscript must exhibit the explicit construction and verify that neither the degree bound nor the additive gap is degraded by a q-dependent factor or by a weaker exponent.
  2. [DQI decoder analysis (likely §5)] The information-theoretic barrier statements for classical versus quantum decoders in DQI are stated for (k,D)-regular instances; the derivation of the 1/sqrt(D log D) classical barrier and the compatibility of the quantum decoder with 1/sqrt(D) must be shown to follow from the same gap that the hardness reduction produces, rather than from separate modeling assumptions.
minor comments (2)
  1. [abstract and introduction] Notation for the O_{q,r}(·) term should be defined explicitly when first introduced, including dependence on the field size and the parameter r.
  2. [introduction] The manuscript should include a short table or paragraph comparing the new hardness gap with the Boolean case of Trevisan and the algorithmic guarantee of Barak et al. to make the extension clear.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments identify points where additional explicitness will strengthen the manuscript. We address each below and have revised the relevant sections accordingly.

read point-by-point responses

  1. Referee: [reduction section (likely §3–4)] The central hardness claim rests on a reduction from Boolean bounded-degree max-k-XORSAT (known to have gap 1/2 + Θ(1/sqrt(D))) to max-Ek-LINSAT(q,r) that must simultaneously preserve maximum degree ≤ D and produce an optimum at most r/q + O_{q,r}(1/sqrt(D)). The manuscript must exhibit the explicit construction and verify that neither the degree bound nor the additive gap is degraded by a q-dependent factor or by a weaker exponent.

    Authors: The reduction is given explicitly in Section 3: each Boolean variable is replaced by a single element of F_q and each Boolean equation is lifted to an equation over F_q whose solution set projects onto the original Boolean solutions. The construction is stated as a linear map that preserves the support of each variable, so the maximum degree remains exactly D. In the proof of Theorem 4.1 we bound the additive gap by O_{q,r}(1/sqrt(D)) with the implicit constant depending only on q and r; the exponent on D is unchanged. A new paragraph has been inserted after the statement of the reduction to make these two verifications explicit. revision: yes

  2. Referee: [DQI decoder analysis (likely §5)] The information-theoretic barrier statements for classical versus quantum decoders in DQI are stated for (k,D)-regular instances; the derivation of the 1/sqrt(D log D) classical barrier and the compatibility of the quantum decoder with 1/sqrt(D) must be shown to follow from the same gap that the hardness reduction produces, rather than from separate modeling assumptions.

    Authors: Section 5 derives both barriers from the identical gap produced by Theorem 4.2 on (k,D)-regular instances. The classical mutual-information calculation uses the same additive gap r/q + Θ(1/sqrt(D)) to obtain the 1/sqrt(D log D) information-theoretic limit; the quantum decoder analysis shows that the same gap is compatible with a 1/sqrt(D) scaling once the decoder is permitted to act on the full superposition. A new subsection 5.3 has been added that repeats the gap statement from the hardness theorem and then re-derives each barrier directly from it, eliminating any separate modeling assumptions. revision: yes

Circularity Check

0 steps flagged

No circularity: hardness extends external Trevisan/Barak results; DQI comparison is downstream analysis

full rationale

The paper's central claim is an extension of known Boolean bounded-degree hardness (Trevisan) and algorithmic results (Barak et al.) to general finite fields F_q, with a new reduction establishing the r/q + O(1/sqrt(D)) gap while preserving degree D. These priors are external and not self-citations. No equations or steps in the provided abstract reduce a prediction or uniqueness claim to a fitted parameter or self-citation chain by construction. The DQI decoder comparison (classical vs quantum) is presented as an implication of the hardness benchmark rather than a self-referential derivation. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only; the result rests on standard complexity assumptions and prior work rather than new free parameters or invented entities.

axioms (1)
  • domain assumption P ≠ NP
    Invoked for all NP-hardness statements in the abstract.

pith-pipeline@v0.9.1-grok · 5885 in / 1269 out tokens · 24949 ms · 2026-06-27T06:25:39.647031+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

58 extracted references · 10 linked inside Pith

  1. [1]

    Opti- mization by decoded quantum interferometry

    Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmid- huber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush. “Opti- mization by decoded quantum interferometry”. Nature646, 831–836 (2025)

    2025

  2. [2]

    Some optimal inapproximability results

    Johan H˚ astad. “Some optimal inapproximability results”. J. ACM48, 798–859 (2001)

    2001

  3. [3]

    Tight inapproxima- bility of max-linsat and implications for decoded quantum interferometry

    Maximilian J Kramer, Carsten Schubert, and Jens Eisert. “Tight inapproxima- bility of max-linsat and implications for decoded quantum interferometry” (2026). arXiv:2603.04540

    arXiv 2026

  4. [4]

    Probabilistic checking of proofs: a new character- ization of NP

    Sanjeev Arora and Shmuel Safra. “Probabilistic checking of proofs: a new character- ization of NP”. J. ACM45, 70–122 (1998)

    1998

  5. [5]

    Proof verification and the hardness of approximation problems

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. “Proof verification and the hardness of approximation problems”. J. ACM45, 501–555 (1998)

    1998

  6. [6]

    An in-principle super-polynomial quantum advantage for approximating combina- torial optimization problems via computational learning theory

    Niklas Pirnay, Vincent Ulitzsch, Frederik Wilde, Jens Eisert, and Jean-Pierre Seifert. “An in-principle super-polynomial quantum advantage for approximating combina- torial optimization problems via computational learning theory”. Science Adv.10, eadj5170 (2024)

    2024

  7. [7]

    Quantum advantage for combinatorial optimization problems, sim- plified

    Mario Szegedy. “Quantum advantage for combinatorial optimization problems, sim- plified” (2022). arXiv:2212.12572

    arXiv 2022

  8. [8]

    Verifiable quantum advantage without struc- ture

    Takashi Yamakawa and Mark Zhandry. “Verifiable quantum advantage without struc- ture”. J. ACM71, 1–50 (2024)

    2024

  9. [9]

    Formal framework for quantum advantage

    Harry Buhrman, Niklas Galke, and Konstantinos Meichanetzidis. “Formal framework for quantum advantage” (2025). arXiv:2510.01953

    arXiv 2025

  10. [10]

    Quantum advantage from soft de- coders

    Andr´ e Chailloux and Jean-Pierre Tillich. “Quantum advantage from soft de- coders” (2024). arXiv:2411.12553. 15

    arXiv 2024

  11. [11]

    Quantum circuit design for decoded quantum interferometry

    Natchapol Patamawisut, Naphan Benchasattabuse, Michal Hajduˇ sek, and Rodney Van Meter. “Quantum circuit design for decoded quantum interferometry”. In 2025 IEEE Int.l Conf. Quant. Comp. Eng. (QCE). Page 291–301. IEEE (2025)

    2025

  12. [12]

    Bridging quantum chemistry and MaxCut: Classical performance guarantees and quantum algorithms for the Hartree–Fock method

    Alexis Ralli, Tim Weaving, Peter V. Coveney, and Peter J. Love. “Bridging quantum chemistry and MaxCut: Classical performance guarantees and quantum algorithms for the Hartree–Fock method”. J. Chem. Th. Comp.21, 9511–9524 (2025)

    2025

  13. [13]

    Decoded quantum inter- ferometry under noise

    Kaifeng Bu, Weichen Gu, Dax Enshan Koh, and Xiang Li. “Decoded quantum inter- ferometry under noise” (2025). arXiv:2508.10725

    arXiv 2025

  14. [14]

    Quantum advantage via solving multivariate polynomials

    Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, and Amit Sahai. “Quantum advantage via solving multivariate polynomials” (2025). arXiv:2509.07276

    arXiv 2025

  15. [15]

    Towards solving industrial integer linear programs with decoded quantum interfer- ometry

    Francesc Sabater, Ouns El Harzli, Geert-Jan Besjes, Marvin Erdmann, Johannes Klepsch, Jonas Hiltrop, Jean-Francois Bobier, Yudong Cao, and Carlos A. Riofrio. “Towards solving industrial integer linear programs with decoded quantum interfer- ometry” (2025). arXiv:2509.08328

    Pith/arXiv arXiv 2025

  16. [16]

    On the complexity of decoded quantum interferometry

    Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu, and Vojtech Havlicek. “On the complexity of decoded quantum interferometry” (2025). arXiv:2509.14443

    Pith/arXiv arXiv 2025

  17. [17]

    Decoded quantum inter- ferometry requires structure

    Eric R. Anschuetz, David Gamarnik, and Jonathan Z. Lu. “Decoded quantum inter- ferometry requires structure” (2025). arXiv:2509.14509

    arXiv 2025

  18. [18]

    Efficient and optimal quantum state discrimination via quantum belief propagation

    Christophe Piveteau and Joseph M. Renes. “Efficient and optimal quantum state discrimination via quantum belief propagation” (2025). arXiv:2509.19441

    arXiv 2025

  19. [19]

    No quantum advantage in decoded quantum interferometry for max- cut

    Ojas Parekh. “No quantum advantage in decoded quantum interferometry for max- cut” (2025). arXiv:2509.19966

    arXiv 2025

  20. [20]

    Algebraic geometry codes and decoded quantum interferometry

    Andi Gu and Stephen P. Jordan. “Algebraic geometry codes and decoded quantum interferometry” (2025). arXiv:2510.06603

    arXiv 2025

  21. [21]

    No exponential quantum speedup forSIS∞anymore

    Robin Kothari, Ryan O’Donnell, and Kewen Wu. “No exponential quantum speedup forSIS∞anymore” (2025). arXiv:2510.07515

    arXiv 2025

  22. [22]

    Hamiltonian decoded quantum interferometry

    Alexander Schmidhuber, Jonathan Z. Lu, Noah Shutty, Stephen Jordan, Alexander Poremba, and Yihui Quek. “Hamiltonian decoded quantum interferometry” (2025). arXiv:2510.07913

    arXiv 2025

  23. [23]

    Verifiable quantum advantage via optimized DQI circuits

    Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush, and Stephen P. Jordan. “Verifiable quantum advantage via optimized DQI circuits” (2025). arXiv:2510.10967

    arXiv 2025

  24. [24]

    OPI x soft decoders

    Andr´ e Chailloux. “OPI x soft decoders” (2025). arXiv:2511.22691

    arXiv 2025

  25. [25]

    A nearly linear-time decoded quantum interferometry algorithm for the optimal polynomial intersection problem

    Ansis Rosmanis. “A nearly linear-time decoded quantum interferometry algorithm for the optimal polynomial intersection problem” (2026). arXiv:2601.15171

    arXiv 2026

  26. [26]

    Hamiltonian decoded quantum interferom- etry for general Pauli Hamiltonians

    Kaifeng Bu, Weichen Gu, and Xiang Li. “Hamiltonian decoded quantum interferom- etry for general Pauli Hamiltonians” (2026). arXiv:2601.18773

    arXiv 2026

  27. [27]

    On worst-case optimal polynomial intersec- tion

    Yihang Sun and Mary Wootters. “On worst-case optimal polynomial intersec- tion” (2026). arXiv:2604.09533

    Pith/arXiv arXiv 2026

  28. [29]

    Regev’s reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups

    M. Isabel Franco Garrido and Andr´ e Chailloux. “Regev’s reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups” (2026). arXiv:2605.03972

    Pith/arXiv arXiv 2026

  29. [30]

    From constraint to code: DQI-Kit – A soft- ware framework for decoded quantum interferometry

    Simon Thelen and Wolfgang Mauerer. “From constraint to code: DQI-Kit – A soft- ware framework for decoded quantum interferometry” (2026). arXiv:2605.16955. 16

    Pith/arXiv arXiv 2026

  30. [31]

    Decoded quantum interferometry beyond hamming: Rank-metric and translation association schemes

    Alexandre Krajenbrink, Colin Krawchuk, Ansis Rosmanis, and Matthias Rosenkranz. “Decoded quantum interferometry beyond hamming: Rank-metric and translation association schemes” (2026). arXiv:2606.04843

    Pith/arXiv arXiv 2026

  31. [32]

    Adiabatic quantum state generation and statistical zero knowledge

    Dorit Aharonov and Amnon Ta-Shma. “Adiabatic quantum state generation and statistical zero knowledge”. In Proceedings of the Thirty-Fifth Annual ACM Sympo- sium on Theory of Computing. Page 20–29. STOC ’03 New York, NY, USA (2003). Association for Computing Machinery

    2003

  32. [33]

    Quantum computation and lattice problems

    Oded Regev. “Quantum computation and lattice problems”. SIAM J. Comp.33, 738–760 (2004)

    2004

  33. [34]

    Lattice problems in NP∩coNP

    Dorit Aharonov and Oded Regev. “Lattice problems in NP∩coNP”. J. ACM52, 749–765 (2005)

    2005

  34. [35]

    On lattices, learning with errors, random linear codes, and cryptogra- phy

    Oded Regev. “On lattices, learning with errors, random linear codes, and cryptogra- phy”. J. ACM56(2009)

    2009

  35. [36]

    Mind the gaps: The fraught road to quantum advan- tage

    Jens Eisert and John Preskill. “Mind the gaps: The fraught road to quantum advan- tage” (2025). arXiv:2510.19928

    Pith/arXiv arXiv 2025

  36. [37]

    The vast world of quantum advantage

    Hsin-Yuan Huang, Soonwon Choi, Jarrod R. McClean, and John Preskill. “The vast world of quantum advantage” (2025). arXiv:2508.05720

    arXiv 2025

  37. [38]

    Challenges and opportunities in quantum optimization

    Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas B¨ artschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Con- stantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Ger- hard Kircher, Thomas Kleinert, Thors...

    2024

  38. [39]

    On bounded occurrence constraint satisfaction

    Johan H˚ astad. “On bounded occurrence constraint satisfaction”. Inf. Proc. Lett.74, 1–6 (2000)

    2000

  39. [40]

    A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem” (2015). arXiv:1412.6062

    Pith/arXiv arXiv 2015

  40. [41]

    Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree

    Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. “Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree”. In Naveen Garg, Klaus Jansen, Anup Rao, and Jos´ e D. P. Rolim, editors, Approximation, Randomization, and Co...

    2015

  41. [42]

    A quantum approximate optimization algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate optimization algorithm” (2014). arXiv:1411.4028

    Pith/arXiv arXiv 2014

  42. [43]

    Non-approximability results for optimization problems on bounded degree instances

    Luca Trevisan. “Non-approximability results for optimization problems on bounded degree instances”. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. Page 453–461. STOC ’01 New York, NY, USA (2001). Association for Computing Machinery

    2001

  43. [44]

    Approximation resistance from pairwise-independent subgroups

    Siu On Chan. “Approximation resistance from pairwise-independent subgroups”. J. ACM63(2016). 17

    2016

  44. [45]

    How many theoreticians does it take to approximate Max 3LIN?

    Luca Trevisan. “How many theoreticians does it take to approximate Max 3LIN?”. Blog post,in theory(2015). Accessed May 2026

    2015

  45. [46]

    Improved bounds for bounded occurrence constraint satisfac- tion

    Johan H˚ astad. “Improved bounds for bounded occurrence constraint satisfac- tion” (2015). Unpublished manuscript

    2015

  46. [47]

    The use of information sets in decoding cyclic codes

    Eugene Prange. “The use of information sets in decoding cyclic codes”. IRE Trans. Inf. Th.8, S5–S9 (1962)

    1962

  47. [48]

    The quantum approximate optimization algorithm at high depth for MaxCut on large-girth regular graphs and the Sherrington-Kirkpatrick model

    Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. “The quantum approximate optimization algorithm at high depth for MaxCut on large-girth regular graphs and the Sherrington-Kirkpatrick model”. In Fran¸ cois Le Gall and Tomoyuki Morimae, editors, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography ...

    2022

  48. [49]

    Comment on: Optimization using locally-quantum decoders

    Christophe Piveteau. “Comment on: Optimization using locally-quantum decoders”. SciRate comment on arXiv:2604.24633 (2026). Accessed May 2026

    Pith/arXiv arXiv 2026

  49. [50]

    Belief propagation decoding of quantum channels by passing quantum messages

    Joseph M. Renes. “Belief propagation decoding of quantum channels by passing quantum messages”. New J. Phys.19, 072001 (2017)

    2017

  50. [51]

    Belief propagation with quan- tum messages for symmetric classical-quantum channels

    Sarah Brandsen, Avijit Mandal, and Henry D. Pfister. “Belief propagation with quan- tum messages for symmetric classical-quantum channels” (2022). arXiv:2207.04984

    arXiv 2022

  51. [52]

    Belief propagation with quantum messages for symmetric q-ary pure-state channels

    Avijit Mandal and Henry D. Pfister. “Belief propagation with quantum messages for symmetric q-ary pure-state channels” (2026). arXiv:2601.21330

    arXiv 2026

  52. [53]

    Bounds on approximating max-k-xor with quantum and classical local algorithms

    Kunal Marwaha and Stuart Hadfield. “Bounds on approximating max-k-xor with quantum and classical local algorithms”. Quantum6, 757 (2022)

    2022

  53. [54]

    A mathematical theory of communication

    C. E. Shannon. “A mathematical theory of communication”. The Bell System Tech- nical Journal27, 379–423 (1948)

    1948

  54. [55]

    Elements of information theory

    Thomas M. Cover and Joy A. Thomas. “Elements of information theory”. Wiley. Hoboken (2006)

    2006

  55. [56]

    Bounds for the quantity of information transmitted by a quantum communication channel

    Alexander S. Holevo. “Bounds for the quantity of information transmitted by a quantum communication channel”. Problemy Peredachi Informatsii9, 3–11 (1973)

    1973

  56. [57]

    Fine-grained unambiguous measure- ments

    Quentin Buzet and Andr´ e Chailloux. “Fine-grained unambiguous measure- ments” (2025). arXiv:2510.07298

    arXiv 2025

  57. [58]

    Classical algorithms and quantum limitations for maximum cut on high-girth graphs

    Boaz Barak and Kunal Marwaha. “Classical algorithms and quantum limitations for maximum cut on high-girth graphs”. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Volume 215 of LIPIcs, pages 14:1–14:21. Dagstuhl, Germany (2022). Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik

    2022

  58. [59]

    Local algorithms for max- imum cut and minimum bisection on locally treelike regular graphs of large de- gree

    Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. “Local algorithms for max- imum cut and minimum bisection on locally treelike regular graphs of large de- gree” (2023). arXiv:2111.06813. 18

    arXiv 2023