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

arXiv:2607.14650 · quant-ph · Submitted 2026-07-16 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry".

Mira: Here's the gist of the paper. The Optimal Polynomial Intersection (OPI) problem asks for a low-degree polynomial whose values lie in prescribed subsets on as many given inputs as possible, and this paper presents a worst-case quantum algorithm that improves upon existing methods like Decoded Quantum Interferometry (DQI).

Kai: How it works The core of the proposed algorithm is based on Regev’s reduction combined with a decoder that decodes correctly with probability 1/poly(n) to establish a worst-case correctness guarantee The algorithm constructs a quantum state by applying the QFT over both registers and then adding the first register to the second, resulting in a state ψ3⟩ = X(x,e)∈Fnq ×Fnq Vˆ (x)Wˆ (e)x⟩ x + e⟩ This process is followed by choosing a random value rand ←

2n: and subtracting the value of Decoderand on the second register from the first register to obtain ψ4,rand⟩ = X(x,e)∈Fnq ×Fnq Vˆ (x)Wˆ (e)x − Decoderand(x + e) x + e⟩ Finally, applying QFT−1 on both registers yields the state ψ5,rand⟩ which is then used to output the second register Algorithmic Bounds and Improvements The paper establishes several key algorithmic bounds comparing its worst-case result against DQI and average-case heuristics For the balanced case where each subset contains roughly half of the field elements, the algorithm finds a solution with satisfaction rate s = 1 whenever the rate satisfies R > 0.75 This matches the previous average-case bound, whereas DQI cannot achieve s = 1 unless R = 1 Furthermore, for general rates R > 0.7149, the satisfaction rate achieved by the worst-case algorithm matches that achieved by the average-case algorithm of

Cha25: The paper also provides an existential bound for OPI, showing that it guarantees the existence of solutions beyond the parameter regime in which DQI is guaranteed to work Specifically, when ρ = 1/2, our existential bound improves upon the previous threshold R > 0.7495 Generalization to MaxLINSAT The results are extended from the OPI problem to the Maximum Linear Satisfaction (MaxLINSAT) problem, which generalizes OPI by involving a matrix A and finding a vector y in its image satisfying a linear satisfaction condition The existential bound extends directly to the MaxLINSAT problem with respect to any maximum distance separable (MDS) codes However, the algorithmic bound extends only to MDS codes whose dual admits an efficient list decoder Existential Bound for MDS MaxLINSAT The paper provides a theorem guaranteeing the existence of a solution for MaxLINSAT under certain parameter conditions The theorem requires conditions on the rate R, such as R ≥ 1 − √τ ρ + p(1 − τ)(1 − ρ)4 + Ω(1) If these conditions hold, then MaxLINSAT has a solution for sufficiently large n This result is stronger than previous existential bounds by improving the saturation bound R1(ρ) and improvement bound R0(ρ) Worst-Case Correctness Proof The proof of the worst-case correctness relies on bounding the quantity X u∈C⊥ Y i:ui̸=0 νi(ui) This is achieved by decomposing it into shift correlations Γ(u) and then bounding Γ(u) via generating polynomials using a variant of the Brascamp–Lieb inequality adapted to MDS codes The final step involves bounding the resulting expression by showing that H(R) + R log Mτ,ρ < 0 This leads to the conclusion that Z ≤ negl(n), confirming Equation (23) Comparison with Related Work The paper compares its findings with previous work, noting that Sun and Wootters

SW26: were the first to observe that no known quantum algorithm for OPI improves upon DQI in the worst case The techniques employed are noted as being different from those of

YZ24: and

Cha25: , although both require controlling Fourier sums over the dual code The paper also discusses the implications for leakage-resilient secret sharing, noting that improving related bounds does not necessarily lead to improvements in that context Thinning Argument A simple thinning argument is presented to show that an algorithmic guarantee for a smaller density can be lifted to any larger density without losing the target satisfaction rate This technique allows the algorithm B to solve OPI with probability at least 1/poly(n) even when using thinned sets S'i By establishing a worst-case quantum polynomial-time algorithm for OPI that improves upon DQI in certain parameter regimes, this paper provides a significant advancement in the field of quantum algorithms for optimization problems The work also yields improved existential bounds for MaxLINSAT and provides a rigorous proof of worst-case correctness through advanced techniques from additive combinatorics This work demonstrates that quantum advantage can be achieved in settings beyond those covered by prior methods Page 53 ---

dBCW02: J.

Mira: Niel de Beaudrap, Richard Cleve, and John Watrous.

Kai: Sharp quantum versus classical query complexity separations.

Title and authors: Kai: So we’ve gone over the title and authors, Horinaga and Yamakawa, and what that means for the optimal polynomial intersection problem.

Mira: They are tackling a really hard version of OPI, focusing on finding a solution even when the input sets are chosen adversarially.

Lev: And the implication is that they’re showing we can do this in a way that goes beyond what decoded quantum interferometry could achieve in terms of worst-case guarantees.

Kai: It’s about moving past the limitations of DQI, which was previously thought to be the best approach for OPI in certain parameter regimes.

Mira: They aren't just finding a better average-case algorithm; they are tackling the worst case setting directly with a quantum algorithm.

Lev: And that means we need to see how this translates when we try to run this on actual hardware, because the overhead for these complex quantum operations can be significant.

Kai: Right, because the paper lays out a specific quantum construction starting with that psi three state <ref:2607.14650#pg2>.

Mira: It starts with applying the Quantum Fourier Transform over both registers and then adding the first register to the second to get psi three = X(x,e) in F n q n F n q n V(x)W(e)x x + e <ref:2607.14650#pg2>.

Lev: That’s the setup for the algorithm they are proposing, but it’s a lot of gates to implement on a real system.

Kai: And then they follow that up by choosing this random value rand from two to n and subtracting the Decoderand on the second register from what you get on the first register.

Mira: Which gets you this state psi 4,rand = X(x,e) in F n q n F n q n V(x)W(e)x - Decoderand(x + e) x + e <ref:2607.14650#pg2>.

Lev: So they’re performing this manipulation using that random value to get the state psi 4,rand <ref:2607.14650#pg2>.

Kai: And the final step is applying the Inverse Quantum Fourier Transform on both registers to get psi 5,rand, which is then used to output something from that second register <ref:2607.14650#pg2>.

Mira: That’s the sequence they use to finally extract the answer from that state.

Lev: From an engineering standpoint, it’s a lot of controlled operations and qubit interactions we have to manage for this specific circuit structure.

Kai: And what they really want to show is that this entire process works in polynomial time for solving the problem.

The paper's summary: Mira: So, summarizing the core of the paper, they’re presenting a worst-case quantum algorithm for OPI that goes beyond DQI.

Kai: They’re using Regev's reduction to build a decoder with a one-in-poly(n) error probability to establish this worst-case correctness guarantee.

Lev: So the key technical mechanism is that they use that decoder to ensure the guarantee holds.

Mira: The algorithm constructs a quantum state by applying the QFT over both registers and then adding the first register to the second, resulting in psi three = X(x,e) in F n q n F n q n V(x)W(e)x x + e <ref:2607.14650#pg2>.

Kai: That initial state is the starting point for their whole process.

Lev: Then they continue by choosing a random value rand from two to n and subtracting the Decoderand on the second register from what you get on the first register.

Mira: This leads to this modified state psi 4,rand = X(x,e) in F n q n F n q n V(x)W(e)x - Decoderand(x + e) x + e <ref:2607.14650#pg2>.

Kai: So that state is what they use to get the final result.

Lev: Finally, applying the Inverse Quantum Fourier Transform on both registers yields psi 5,rand which is then used to output information from that second register <ref:2607.14650#pg2>.

Mira: This entire process is designed to give them a verifiable solution using this state manipulation.

The paper's improvements: Kai: Now for the improvements they suggest, because this paper isn't just about showing a new algorithm, but also showing how it beats existing methods like DQI.

Mira: They show that in the balanced case, where each subset contains roughly half of the field elements, their algorithm finds a solution with satisfaction rate s = one whenever the rate R is greater than zero point seven five.

Lev: That’s a concrete result: they match the average-case bound for that specific setting, which is interesting because DQI can't reach perfect satisfaction unless R is one.

Kai: And for general rates greater than zero point seven one four nine, the satisfaction rate achieved by their worst-case algorithm matches that achieved by the average-case algorithm from Cha25.

Mira: They’re showing a consistent performance across different settings, which gives us more confidence in its practical application.

Lev: And they extend this to MaxLINSAT with MDS codes, although the algorithmic bound only holds for those whose dual has an efficient list decoder.

Kai: For MaxLINSAT specifically, they provide an existential bound guaranteeing existence of a solution beyond the parameter regime where DQI is guaranteed to work.

Mira: When rho is equal to one/two their existential bound improves upon the previous threshold R greater than zero point seven four nine five.

Lev: That improvement in the saturation bound R one(rho) and improvement bound R zero(rho) is what makes this work for them <ref:2607.14650#pg3>.

Kai: And for MaxLINSAT, they give a theorem guaranteeing existence under specific conditions on the rate R.

Conclusion: Mira: So to wrap up, Horinaga and Yamakawa’s paper presents a worst-case quantum algorithm for OPI that improves upon DQI.

Kai: They establish this by using Regev's reduction combined with a decoder that has a one-in-poly(n) error probability to set the worst-case guarantee.

Lev: And they show concrete performance gains in the balanced case, where R is greater than zero point seven five.

Kai: This means we have a quantum algorithm that works in settings where DQI alone couldn't reach a perfect solution unless R is one.

Mira: And they also extend this to MaxLINSAT, providing stronger existential bounds for parameters like rho = one/two <ref:2607.14650#pg1>.

Lev: Overall, this paper gives us a rigorous proof of worst-case correctness through additive combinatorics techniques and those improved existential bounds.

Kai: We’ve got a solid framework for solving OPI even in the hardest scenarios with quantum computation.

Mira: It shows that quantum advantage can be achieved in settings beyond what prior methods were guaranteed to solve.

Lev: I just think it’s important to remember that while this is promising, we still need to figure out the practical overhead of running these complex circuits on actual hardware.

NTT Institute for Fundamental Mathematics · NTT Social Informatics Laboratories

quant-ph

Submitted: 2026-07-16

Updated: 2026-10-22

Comments: 57 pages, 4 figures

License: http://creativecommons.org/licenses/by/4.0/

The gist: The Optimal Polynomial Intersection (OPI) problem asks for a low-degree polynomial whose values lie in prescribed subsets on as many given inputs as possible, and this paper presents a worst-case

Key concepts

Optimal Polynomial Intersection (OPI)
This problem seeks a low-degree polynomial whose output values fall into specific subsets defined on as many given input points as possible. The goal is to find the best possible fit for a function given constraints on its range.
Worst-Case Quantum Algorithm
This refers to an algorithm that guarantees finding a solution even in the most difficult scenario, where the input sets are chosen adversarially. The paper introduces a specific quantum procedure based on Regev’s reduction and a decoder to ensure this worst-case correctness.
Existential Bound
This is a guarantee that a solution exists for a problem under certain parameter conditions, even if the algorithm itself doesn't always find it. The paper improves these bounds for MaxLINSAT, showing solutions exist beyond regimes where previous methods predicted failure.
MaxLINSAT
This is an extension of OPI involving a matrix A and finding a vector y in its image that satisfies a linear satisfaction condition. It generalizes the original problem by incorporating linear constraints related to matrix structure.

Terminology

Summary

The Optimal Polynomial Intersection (OPI) problem asks for a low-degree polynomial whose values lie in prescribed subsets on as many given inputs as possible, and this paper presents a worst-case quantum algorithm that improves upon existing methods like Decoded Quantum Interferometry (DQI).

How it works

The core of the proposed algorithm is based on Regev’s reduction combined with a decoder that decodes correctly with probability 1/poly(n) to establish a worst-case correctness guarantee The algorithm constructs a quantum state by applying the QFT over both registers and then adding the first register to the second, resulting in a state ψ3⟩ = X(x,e)∈Fnq ×Fnq Vˆ (x)Wˆ (e)x⟩ x + e⟩ This process is followed by choosing a random value rand ← [2n] and subtracting the value of Decoderand on the second register from the first register to obtain ψ4,rand⟩ = X(x,e)∈Fnq ×Fnq Vˆ (x)Wˆ (e)x − Decoderand(x + e) x + e⟩ Finally, applying QFT−1 on both registers yields the state ψ5,rand⟩ which is then used to output the second register

Algorithmic Bounds and Improvements

The paper establishes several key algorithmic bounds comparing its worst-case result against DQI and average-case heuristics For the balanced case where each subset contains roughly half of the field elements, the algorithm finds a solution with satisfaction rate s = 1 whenever the rate satisfies R > 0.75 This matches the previous average-case bound, whereas DQI cannot achieve s = 1 unless R = 1 Furthermore, for general rates R > 0.7149, the satisfaction rate achieved by the worst-case algorithm matches that achieved by the average-case algorithm of [Cha25] The paper also provides an existential bound for OPI, showing that it guarantees the existence of solutions beyond the parameter regime in which DQI is guaranteed to work Specifically, when ρ = 1/2, our existential bound improves upon the previous threshold R > 0.7495

Generalization to MaxLINSAT

The results are extended from the OPI problem to the Maximum Linear Satisfaction (MaxLINSAT) problem, which generalizes OPI by involving a matrix A and finding a vector y in its image satisfying a linear satisfaction condition The existential bound extends directly to the MaxLINSAT problem with respect to any maximum distance separable (MDS) codes However, the algorithmic bound extends only to MDS codes whose dual admits an efficient list decoder

Existential Bound for MDS MaxLINSAT

The paper provides a theorem guaranteeing the existence of a solution for MaxLINSAT under certain parameter conditions The theorem requires conditions on the rate R, such as R ≥ 1 − √τ ρ + p(1 − τ)(1 − ρ)4 + Ω(1) If these conditions hold, then MaxLINSAT has a solution for sufficiently large n This result is stronger than previous existential bounds by improving the saturation bound R1(ρ) and improvement bound R0(ρ)

Worst-Case Correctness Proof

The proof of the worst-case correctness relies on bounding the quantity X u∈C⊥ Y i:ui̸=0 νi(ui) This is achieved by decomposing it into shift correlations Γ(u) and then bounding Γ(u) via generating polynomials using a variant of the Brascamp–Lieb inequality adapted to MDS codes The final step involves bounding the resulting expression by showing that H(R) + R log Mτ,ρ < 0 This leads to the conclusion that Z ≤ negl(n), confirming Equation (23)

Comparison with Related Work

The paper compares its findings with previous work, noting that Sun and Wootters [SW26] were the first to observe that no known quantum algorithm for OPI improves upon DQI in the worst case The techniques employed are noted as being different from those of [YZ24] and [Cha25], although both require controlling Fourier sums over the dual code The paper also discusses the implications for leakage-resilient secret sharing, noting that improving related bounds does not necessarily lead to improvements in that context

Thinning Argument

A simple thinning argument is presented to show that an algorithmic guarantee for a smaller density can be lifted to any larger density without losing the target satisfaction rate This technique allows the algorithm B to solve OPI with probability at least 1/poly(n) even when using thinned sets S'i

Conclusion

By establishing a worst-case quantum polynomial-time algorithm for OPI that improves upon DQI in certain parameter regimes, this paper provides a significant advancement in the field of quantum algorithms for optimization problems The work also yields improved existential bounds for MaxLINSAT and provides a rigorous proof of worst-case correctness through advanced techniques from additive combinatorics This work demonstrates that quantum advantage can be achieved in settings beyond those covered by prior methods

--- Page 53 ---

[dBCW02] J. Niel de Beaudrap, Richard Cleve, and John Watrous. Sharp quantum versus classical query complexity separations. Algorithmica, 34(4):449–461, 2002.

[GR05] Ben Green and Imre Z Ruzsa. Sum-free sets in abelian groups. Israel Journal of Mathematics, 147(1):157–188, 2005.

[JSW+25] Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush. Optimization by decoded quantum interferometry. Nature, 646:831–836 October 2025.

[vDHI06] Wim van Dam, Sean Hallgren, and Lawrence Ip. Quantum algorithms for some hidden shift problems. SIAM J. Comput., 36(3):763–778, 2006.

[vH16] Ramon van Handel. Probability in high dimensions. Lecture Notes, Princeton University, 2016

[YZ24] Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. J. ACM, 71(3):20, 2024

[Zha19] Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019 Part II, volume 11693 of LNCS, pages 239–268 Springer Cham August 2019

[Sho94] Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th FOCS, pages 124–134 IEEE Computer Society Press November 1994

[SSTX09] Damien Stehl´e, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key encryption based on ideal lattices. In Mitsuru Matsui editor ASIACRYPT 2009 volume 5912 of LNCS pages 617–635 Springer Berlin Heidelberg December 2009

[SW26] Yihang Sun and Mary Wootters. On worst-case optimal polynomial intersection, 2026 arXiv:2604.09533]

[vH16] Ramon van Handel. Probability in high dimensions. Lecture Notes, Princeton University, 2016

[YZ24] Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. J. ACM, 71(3):20, 2024

[Zha19] Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio editors CRYPTO 2019 Part II volume 11693 of LNCS pages 239–268 Springer Cham August 2019

[Sho94] Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th FOCS, pages 124–134 IEEE Computer Society Press November 1994

[SSTX09] Damien Stehl´e, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key encryption based on ideal lattices.

Improvements for AI systems

  1. Worst-case Polynomial Intersection Solver: The system can find a low-degree polynomial over a finite field whose values lie in prescribed subsets on as many given inputs as possible, even when the input sets are chosen adversarially (worst-case setting). This is achieved by using the novel quantum algorithm described in Section 6.

  2. Improved Existence Guarantee for Hard Problems: The system can guarantee the existence of a solution to problems like MaxLINSAT beyond parameter regimes where current algorithms fail, specifically improving the existential bound of Sun and Wootters. For instance, when each subset contains roughly half of the field elements, it finds a solution with satisfaction rate s = 1 whenever R > 0.75.

  3. Enhanced Quantum Advantage Thresholds: The system can solve Optimal Polynomial Intersection for a broader range of input parameters than Decoded Quantum Interferometry (DQI) alone allows, specifically by matching or improving the average-case bound in certain regimes where DQI cannot reach a perfect solution unless R = 1.

Abstract

The Optimal Polynomial Intersection (OPI) problem asks us to find a low-degree polynomial over a finite field whose values lie in prescribed subsets on as many given inputs as possible. Decoded quantum interferometry (DQI) gives a quantum algorithm for OPI in parameter regimes beyond those achieved by the best known classical heuristics. Follow-up works improve the parameter regimes, but their analyses are limited to average-case settings. Recently, Sun and Wootters showed that, even in the worst case, OPI has a solution in a larger parameter regime than the one covered by DQI. However, they left open whether one can design a quantum algorithm that solves OPI in the worst-case beyond the DQI regime. We give such a quantum algorithm. As a byproduct, we also improve the existential bound of Sun and Wootters in certain parameter regimes. In particular, when each subset contains roughly half of the field elements, our algorithm finds a solution with satisfaction rate s=1 whenever the rate satisfies R>0.75. This matches the previous average-case bound, whereas DQI cannot achieve s=1 unless R=1. Our existential bound guarantees the existence of a solution when R> 0.7158, improving over the previous threshold R>0.7495. More generally, our existential results extend to the Max-LINSAT problem with respect to arbitrary maximum distance separable (MDS) codes. The corresponding algorithmic results apply only to MDS codes whose dual admits an efficient list decoder. Our results are obtained through a novel application of a Brascamp--Lieb-type inequality in the MDS setting, which may have further applications.

Sources

Related papers