⚛️ quantum physics

Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry

This paper presents a worst-case quantum algorithm that solves the Optimal Polynomial Intersection problem beyond the limits of Decoded Quantum Interferometry, achieving a satisfaction rate of $s=1$ for rates $R>0.75$ and improving the existential bound to $R>0.7158$ through a novel application of Brascamp–Lieb-type inequalities.

Original authors: Shuji Horinaga, Takashi Yamakawa

Published 2026-07-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Shuji Horinaga, Takashi Yamakawa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where computers don't just crunch numbers but dance with probability, exploring many possibilities at once like a choir singing every note of a song simultaneously. This is the realm of quantum computing, a field that promises to solve certain puzzles far faster than our current machines ever could. One such puzzle is the "Optimal Polynomial Intersection" problem. To understand it, picture a giant grid of coordinates, where each spot on the grid has a specific rule about which colors are allowed. Your job is to draw a single, smooth, wiggly line (a polynomial) that passes through as many of these spots as possible, hitting only the "allowed" colors. In the real world, this isn't just a game; it's the mathematical heart of decoding messages sent over noisy channels, like fixing a corrupted text message or recovering a lost file. For years, scientists have been trying to find the best way to draw this line. While classical computers (the ones in your phone) have to check possibilities one by one, quantum computers can use a trick called "interference" to cancel out wrong answers and amplify the right ones, potentially finding the perfect line much faster.

However, there's a catch. The best-known quantum method, called Decoded Quantum Interferometry (DQI), works great when the rules are random and easy to predict, but it stumbles when the rules are tricky or "worst-case" scenarios. It's like having a map that works perfectly in a sunny park but fails completely in a dense, foggy forest. Recently, researchers proved that a solution must exist in these foggy forests, but they couldn't show how to find it. This paper, by Shuji Horinaga and Takashi Yamakawa, bridges that gap. They have designed a new quantum algorithm that can navigate the worst-case foggy forests and find the perfect line, not just in theory, but with a guaranteed chance of success. They prove that for a specific type of difficult puzzle, their method can find a solution that satisfies the rules almost perfectly, even when the conditions are tougher than what previous quantum methods could handle. They also discovered that solutions exist in even wider ranges than previously thought, pushing the boundaries of what we know is possible in this mathematical landscape.

The Puzzle of the Wiggly Line

Let's dive into the story of the "Optimal Polynomial Intersection" (OPI). Imagine you are an architect trying to build a bridge (the polynomial) across a river. The river has $n$ specific checkpoints (inputs), and at each checkpoint, there is a fence (a subset of allowed values). Your bridge must pass through the fence at as many checkpoints as possible. The goal is to find a bridge that is smooth and simple (low-degree) but hits the fences at a high percentage of the checkpoints.

For a long time, the best tool we had for this was a quantum method called Decoded Quantum Interferometry (DQI). Think of DQI as a magical compass that works brilliantly when the fences are placed randomly. If you throw darts at a board to decide where the fences go, DQI can almost always find the perfect bridge. But if someone deliberately arranges the fences to be the most annoying, tricky configuration possible (the "worst-case"), DQI gets lost. It can only guarantee a solution if the bridge is allowed to be very complex, which defeats the purpose.

The New Quantum Explorer

The authors of this paper, Horinaga and Yamakawa, asked a bold question: "Can we build a quantum explorer that doesn't get lost even in the trickiest, worst-case forests?" Their answer is a resounding yes. They have created a new quantum algorithm that improves upon DQI.

Here is how they did it, using a few clever tricks:

The List Decoder: Instead of trying to guess the exact path immediately, their algorithm uses a "list decoder." Imagine you are trying to find a specific house in a neighborhood. Instead of guessing one house, you generate a short list of the top 5 most likely candidates. The algorithm does something similar: it generates a list of possible solutions and then picks one at random from that list. If the list is short (which it is, thanks to the math of the problem), this random pick has a good chance of being the right one.
The Brascamp–Lieb Inequality: This is the secret sauce. It's a complex mathematical rule that acts like a super-accurate ruler. The authors used a new version of this ruler, adapted for their specific type of problem (MDS codes), to prove that the "bad" paths (the ones that lead to dead ends) are so rare that they can be ignored. It's like proving that in a massive maze, the number of dead-end corridors is so small that if you walk randomly, you are almost guaranteed to find the exit.
The Result: They proved that their algorithm works in the worst-case scenario. Specifically, when the fences cover about half of the possible colors (a "balanced" case), their algorithm can find a bridge that hits the fences at 100% of the checkpoints, provided the bridge's complexity (the rate $R$ ) is greater than 0.75. However, it is important to note that the algorithm finds this perfect solution with a probability that is inversely proportional to a polynomial of the problem size (meaning it succeeds often, but not with absolute certainty every single time).

Why This Matters

Before this paper, the best quantum algorithm (DQI) could only guarantee a perfect solution (100% hit rate) if the bridge was allowed to be extremely complex ( $R=1$ ). If you wanted a simpler bridge, you had to settle for missing some checkpoints. The average-case algorithms (which only work on random puzzles) could hit 100% at $R > 0.75$ , but they failed in the worst-case.

Horinaga and Yamakawa's algorithm changes the game. They showed that in the worst-case, you can find a solution that hits 100% of the checkpoints as long as the complexity is greater than 0.75, with a success probability that is significant enough to be useful (specifically, inverse-polynomial). This matches the performance threshold of the best average-case methods but works even when the puzzle is designed to be as hard as possible.

Furthermore, they didn't just build the algorithm; they also proved that solutions exist even in slightly harder regimes. They showed that a solution is guaranteed to exist whenever the complexity is greater than 0.7158, improving on the previous best guarantee of 0.7495.

The Bigger Picture

This work is a significant step forward in understanding the limits of quantum computing. It moves us from "we think a solution exists" to "here is a quantum machine that can find it with high probability." While their algorithm currently works best for specific types of mathematical structures (Reed-Solomon codes and their generalizations), the techniques they developed—especially the new way of using the Brascamp–Lieb inequality—could help solve other difficult problems in coding theory and cryptography.

In short, they have built a quantum flashlight that works in the darkest, most confusing forests, proving that even when the rules are rigged against you, a quantum computer can still find the perfect path with a reliable chance of success.

Technical Summary: Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry

Problem Definition
The paper addresses the Optimal Polynomial Intersection (OPI) problem. Given a finite field $\mathbb{F}_q$ , a set of distinct evaluation points $\alpha = (\alpha_1, \dots, \alpha_n)$ , and subsets $S_i \subseteq \mathbb{F}_q$ for each $i \in [n]$ , the goal is to find a polynomial $P \in \mathbb{F}_q[X]$ of degree less than $k$ such that $P(\alpha_i) \in S_i$ for at least a fraction $s$ of the inputs. The problem is parameterized by the rate $R = k/n$ and the density $\rho = |S_i|/q$ .

Prior to this work, the Decoded Quantum Interferometry (DQI) algorithm [JSW+25] provided a quantum solution for OPI in specific parameter regimes, surpassing the best known classical heuristics (Prange's algorithm). However, DQI's worst-case performance is limited; for instance, when $\rho = 1/2$ , DQI cannot achieve a satisfaction rate $s=1$ unless $R=1$ . While recent average-case analyses [Cha25] improved these bounds (allowing $s=1$ for $R > 0.75$ when $\rho=1/2$ ), they rely on the random choice of the sets $S_i$ . A purely existential result by Sun and Wootters [SW26] demonstrated that solutions exist in a wider parameter regime than DQI covers, even in the worst case, but did not provide a corresponding quantum algorithm.

Methodology
The authors propose a quantum algorithm that improves upon DQI in the worst-case setting. The approach is a variant of the Regev-style quantum reduction [Reg09] combined with a list-decoding strategy, similar to the frameworks of Yamakawa and Zhandry [YZ24] and Chailloux [Cha25].

Algorithmic Framework: The algorithm prepares a quantum state proportional to the intersection of the code (Reed-Solomon code $C$ ) and the constraint set $S = \prod S_i$ . It utilizes the Quantum Fourier Transform (QFT) over finite fields and a decoder for the dual code $C^\perp$ .
List-Decoding Strategy: Unlike previous worst-case attempts that relied on unique decoding, this algorithm employs a list decoder for the dual code $C^\perp$ . The decoder outputs a random element from the list of candidates. The algorithm succeeds if the list size is polynomial and the decoder succeeds with inverse-polynomial probability.
Worst-Case Analysis via Brascamp–Lieb Inequality: The core technical challenge is bounding the "error" terms in the worst-case scenario, where the sets $S_i$ $S_{i}$ are adversarially chosen. The authors introduce a novel application of a Brascamp–Lieb-type inequality adapted to Maximum Distance Separable (MDS) codes.
- They decompose the error probability into shift correlations $\Gamma(u)$ over the dual code.
- They bound these correlations using bivariate generating polynomials and the $\ell_1$ norm of their coefficients.
- Crucially, they apply the MDS Brascamp–Lieb inequality (Theorem 3.1) to bound the sum of products of Fourier biases over the dual code. This inequality leverages the MDS property (high minimum distance) to control the sum, allowing the authors to show that the error is negligible even for worst-case sets.
Fourier Bias Bounds: To complete the analysis, the paper derives tight bounds on the sum of the $Q$ -th powers of Fourier coefficients of the indicator functions of the sets $S_i$ . These bounds rely on additive combinatorics (specifically, bounds on additive energy via Pollard's theorem and Green-Ruzsa results) and Fourier bias estimates.

Key Contributions and Results

First Worst-Case Quantum Algorithm Beyond DQI: The paper presents the first quantum polynomial-time algorithm that solves OPI in the worst case with parameters strictly improving upon DQI.
- Balanced Case ( $\rho = 1/2$ ): The algorithm finds a perfect solution ( $s=1$ ) whenever the rate $R > 0.75$ . This matches the best known average-case bound [Cha25] but holds for any choice of subsets $S_i$ . DQI, by contrast, requires $R=1$ for $s=1$ in this regime.
- General Regime: For $R > 0.6979$ (when $\rho=1/2$ ), the algorithm improves upon the DQI regime. The paper provides explicit conditions (Equations 1 and 2 in Theorem 1.1) involving the binary entropy function $H(R)$ and Fourier bias moments that determine the achievable satisfaction rate $s$ .
Improved Existential Bounds: As a byproduct of the algorithmic analysis, the authors derive improved existential bounds for the existence of solutions to OPI (and the generalized MaxLINSAT problem for MDS codes).
- For $\rho = 1/2$ , they prove that a solution exists whenever $R > 0.7158$ , improving upon the previous threshold of $R > 0.7495$ established by Sun and Wootters [SW26].
- This existential result holds for any MDS code, whereas the algorithmic result is currently restricted to codes whose duals admit efficient list decoders (e.g., Reed-Solomon codes).
Technical Novelty: The paper introduces a new application of the Brascamp–Lieb inequality in the context of coding theory and quantum algorithms. This technique allows for the control of Fourier sums over the dual code in the worst case, a task that previous average-case analyses avoided by assuming random set choices.

Significance
The paper claims to close a significant gap between existential guarantees and algorithmic performance for the OPI problem in the worst-case setting. While Sun and Wootters [SW26] showed that solutions exist in regimes where DQI fails, they left open the question of whether a quantum algorithm could find them. This work answers that question affirmatively.

The authors note that their results are specific to fields with super-constant characteristic (where $p = \omega(1)$ ) and rely on the list-decodability of the dual code. They do not claim to solve MaxLINSAT for arbitrary codes or fields of small characteristic (like $\mathbb{F}_2$ ) in the worst case, noting that DQI and their own results currently do not extend to those settings. The work establishes a new benchmark for quantum advantage in polynomial intersection problems, demonstrating that quantum algorithms can achieve performance in the worst case that previously was only known to be possible on average or existentially.

The Puzzle of the Wiggly Line

The New Quantum Explorer

Why This Matters

The Bigger Picture

Technical Summary: Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry

More like this