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

This paper establishes that approximating bounded-degree max-LINSAT over arbitrary finite fields beyond a $1/\sqrt{D}$ additive factor is NP-hard, thereby setting a complexity-theoretic benchmark that confines potential quantum advantage to constant prefactors and identifies quantum decoding as the essential component for decoded quantum interferometry to match this optimal scaling.

The Gist

Imagine you are a detective trying to solve a massive puzzle. The puzzle consists of hundreds of rules (constraints) involving a bunch of variables (clues). Your goal is to find a single arrangement of clues that satisfies as many rules as possible. This is the essence of the max-LINSAT problem described in the paper.

In the "worst-case" scenario, the rules are designed to be as tricky as possible, with no obvious patterns. In this chaotic world, the best you can do is just guess randomly, getting about 50% of the rules right (or $r/q$ in more complex versions). It's like trying to guess the combination of a safe with no hints; you can't do significantly better than luck.

However, the paper focuses on a specific, more realistic version of this puzzle: Bounded-Degree Instances.

The "Social Network" Analogy

Imagine the clues in your puzzle are people at a party.

• The Rules: Each rule is a conversation between a small group of people (say, 3 people).
• The Degree ($D$): This is the limit on how many conversations any single person can be part of. In a "bounded-degree" puzzle, no one is talking to everyone else; everyone is only chatting with a limited number of neighbors (at most $D$ people).

The paper asks: Does having these limited connections make the puzzle easier to solve than the chaotic, unbounded version?

The Main Discovery: The "Square Root" Wall

The authors prove a fundamental limit on how smart an algorithm (whether run by a human, a classical computer, or a quantum computer) can be in this bounded setting.

1. The Random Baseline: If you just guess randomly, you get a certain score (say, 50%).
2. The Improvement: Because the puzzle has structure (limited connections), smart algorithms can do better than random guessing. They can find a solution that is slightly better.
3. The Limit: The paper proves that the maximum amount of improvement you can get is proportional to $1/\sqrt{D}$.

Think of $D$ as the "crowdedness" of the party.

• If everyone is only talking to 4 people ($D=4$), you can improve your score by a certain amount.
• If everyone is talking to 100 people ($D=100$), the improvement you can squeeze out gets smaller, specifically shrinking by the square root of that number.

The Big Takeaway: No matter how clever your computer is, you cannot break this "Square Root Wall." You can't get an improvement that scales with $1/D$ (which would be tiny) or $1/\log(D)$ (which would be huge). The best possible improvement is strictly tied to the square root of the connections.

The Quantum Question: Can Quantum Computers Win?

This is where the paper gets interesting for the future of computing. Since classical computers are hitting this "Square Root Wall," could a Quantum Computer break through it and get a much bigger improvement?

The authors say: No, not in the way you might hope.

• The Constant Factor: The paper shows that quantum computers cannot change the shape of the improvement (the $1/\sqrt{D}$ part). They can only improve the constant number in front of it.
  • Analogy: Imagine running a race. Classical computers run at a speed of $10 \times \sqrt{D}$. Quantum computers might run at $12 \times \sqrt{D}$. They are faster, but they are still running on the same track with the same fundamental physics. They don't invent a new mode of transportation that ignores the track entirely.

The Secret Ingredient: The Decoder

The paper dives deep into a specific quantum method called Decoded Quantum Interferometry (DQI). This method tries to solve the puzzle by turning it into a "decoding" problem (like fixing a corrupted message).

The authors found a crucial difference based on how the decoding is done:

1. Classical Decoders (The "Old School" Way): If the quantum computer uses a classical brain to decode the message, it hits a slightly worse wall: $1/(\sqrt{D} \times \log D)$. It's like trying to run through a hallway with a heavy backpack; the "log" factor is the extra weight slowing it down. It cannot reach the theoretical best speed.
2. Quantum Decoders (The "True Quantum" Way): If the quantum computer uses a quantum brain to decode the message, it can remove that extra "backpack." It can reach the $1/\sqrt{D}$ speed limit.

Conclusion: For quantum computers to truly match the best possible performance on these puzzles, they must use quantum decoding. If they use classical decoding, they leave performance on the table.

Summary for the Everyday Reader

• The Problem: Solving complex logic puzzles where variables are only connected to a few others.
• The Limit: There is a hard ceiling on how much better than random guessing you can get. That ceiling is determined by the square root of the number of connections.
• The Quantum Verdict: Quantum computers cannot break this ceiling to get a fundamentally different type of advantage. They can only be slightly faster (a better constant factor) than the best classical computers.
• The Catch: To get that slight speed boost, the quantum computer must use a fully quantum "decoder." If it uses a classical decoder, it will be slower than the theoretical limit.

In short, the paper draws a map of the territory. It tells us that while quantum computers are useful, they aren't magic wands that can solve these specific puzzles instantly. They are powerful tools, but they still have to play by the same fundamental rules of complexity as classical computers.

Technical Summary

Technical Summary: Approximability Limits for Bounded-Degree Max-LINSAT and Implications for Decoded Quantum Interferometry

Problem Definition
The paper investigates the approximability of Max-LINSAT (Maximum Linear Satisfiability) over finite fields $\mathbb{F}_q$. Specifically, it focuses on the bounded-degree regime, where each variable appears in at most $D$ constraints. The problem involves finding an assignment $x \in \mathbb{F}_q^n$ that satisfies the maximum number of linear constraints of the form $\sum B_{i,j} x_j \in F_i$, where $F_i$ is a subset of $\mathbb{F}_q$ of size $r$.

While general Max-$k$-XORSAT (and Max-LINSAT) with unbounded variable degrees is known to be inapproximable beyond the random assignment threshold ($1/2$ for Boolean, $r/q$ for general fields) assuming $P \neq NP$, the landscape changes when the degree $D$ is bounded. In this setting, polynomial-time algorithms can provably exceed the random baseline. The central question addressed is whether the observed scaling of this improvement—specifically an additive term of order $1/\sqrt{D}$—is a fundamental limit imposed by complexity theory or merely an artifact of current algorithmic techniques. Furthermore, the paper examines the implications of these limits for Decoded Quantum Interferometry (DQI), a quantum algorithmic framework for approximation.

Methodology
The authors employ a combination of complexity-theoretic reductions and information-theoretic analysis:

1. Complexity-Theoretic Hardness: The core technical contribution involves composing three known results to establish hardness for bounded-degree instances:

   • Håstad's Inapproximability: Utilizing the seminal result that distinguishing between satisfiable and $(1/q + \epsilon)$-satisfiable instances of Max-E3-LIN-$q$ is NP-hard.
   • Trevisan's Degree Reduction: Applying a randomized degree-reduction technique (variable splitting, weighted replication, sampling, and pruning) to convert unbounded-degree hard instances into bounded-degree instances. This technique incurs a loss in the approximation gap of order $O(1/\sqrt{D})$.
   • Deterministic Lifting: Extending the result from singleton acceptance sets ($r=1$) to arbitrary acceptance set sizes ($r$) using a reduction that preserves the degree scaling.
   • The authors carefully analyze the error probabilities introduced by the randomized steps, noting that the resulting hardness holds under the assumption $NP \not\subseteq BPP$ (or $NP \not\subseteq BQP$ for quantum contexts) due to imperfect completeness in the source hardness.

2. Algorithmic and Information-Theoretic Analysis:

   • The paper reviews existing algorithmic guarantees, including greedy methods, QAOA, and the algorithm by Barak et al., which achieves a $1/2 + \Theta(1/\sqrt{D})$ scaling for Boolean instances.
   • It extends the analysis of DQI (specifically the "semicircle law" governing its performance) to bounded-degree Max-LINSAT.
   • Information-theoretic ceilings are derived for DQI by analyzing the decoding capacity of the dual code associated with the constraint matrix. The authors compare the performance of classical decoders (limited by Shannon capacity) versus quantum decoders (limited by Holevo capacity) in the context of the induced channel model.

Key Contributions and Results

1. Extension of Hardness to General Fields and Acceptance Sets:
   The authors prove that for Max-Ek-LINSAT($q, r$) with bounded degree $D$, it is NP-hard to approximate the solution beyond the threshold:
   $$\frac{r}{q} + O_{q,r}\left(\frac{1}{\sqrt{D}}\right)$$
   This result generalizes previous folklore hardness for bounded-degree Max-XORSAT ($q=2, r=1$) to arbitrary finite fields and acceptance set sizes. It establishes that the $1/\sqrt{D}$ scaling is a complexity-theoretic ceiling for worst-case instances.

2. Confinement of Quantum Advantage:
   The results imply that for bounded-degree instances, any potential quantum advantage over classical algorithms is confined to the constant prefactor of the $1/\sqrt{D}$ term. No algorithm (quantum or classical) can achieve a scaling better than $O(1/\sqrt{D})$ in the worst case.

3. Information-Theoretic Barriers for DQI:
   The paper derives specific limits for DQI performance based on the type of decoder used:

   • Classical Decoders: DQI with classical decoders faces an information-theoretic barrier of $O(1/\sqrt{D \log D})$. This is strictly worse than the complexity-theoretic hardness bound of $O(1/\sqrt{D})$, meaning classical decoders cannot match the optimal worst-case scaling even if an efficient algorithm existed.
   • Quantum Decoders: DQI with quantum decoders is compatible with the $O(1/\sqrt{D})$ scaling. The Holevo capacity of the induced channel allows quantum decoders to avoid the logarithmic penalty ($\log D$) inherent to classical decoding.
   • Conclusion: The paper identifies quantum decoding as the necessary ingredient for DQI to theoretically match the complexity-theoretic scaling limits.

Significance and Claims
The paper claims to provide the first explicit complexity-theoretic benchmark for bounded-degree Max-LINSAT over general finite fields. Its significance lies in:

• Defining the Limits of Improvement: It clarifies that the $1/\sqrt{D}$ scaling is not an artifact of current techniques but a fundamental barrier. Therefore, research into quantum advantage for these problems should focus on optimizing the constant prefactor rather than seeking asymptotic improvements in $D$.
• Validating Quantum Decoding: It provides a theoretical justification for the use of quantum decoders in DQI. While classical decoders are information-theoretically insufficient to reach the hardness scaling, quantum decoders are compatible with it.
• Bridging Complexity and Quantum Algorithms: The work connects the literature on PCP-based inapproximability with the emerging field of quantum algorithms for optimization (DQI, QAOA), showing that the "intermediate regime" of bounded-degree instances is where the most scientifically interesting interplay between structure and hardness occurs.

The authors remain modest regarding open questions, noting that while the scaling is established, the tight worst-case constant $c^*(k)$ remains unknown, and no efficient quantum decoder currently exists that achieves the Holevo-capacity scaling for the specific codes arising in bounded-degree DQI instances. Additionally, the gap between the hardness bound and the best known algorithm for $q > 2$ (which is currently $O(1/D)$) remains a significant open problem.