Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.09533

On Worst-Case Optimal Polynomial Intersection

Yihang Sun, Mary Wootters

cs.DMcs.ITquant-phSubmitted Apr 10, 2026• Announced Apr 13, 2026• 0 citations
arXivHTMLPDF

Abstract

The Optimal Polynomial Intersection (OPI) problem is the following: Given sets $S_1, \ldots, S_m \subseteq \mathbb{F}$ and evaluation points $a_1, \ldots, a_m \in \mathbb{F}$, find a polynomial $Q \in \mathbb{F}[x]$ of degree less than $n$ so that $Q(a_i) \in S_i$ for as many $i \in \{1, 2, \ldots, m\}$ as possible. Decoded Quantum Interferometry (DQI) is a quantum algorithm that efficiently returns good solutions to the problem, even on worst-case instances (Jordan et. al., 2025). The quality of the solutions returned follows a semicircle law, which outperforms known efficient classical algorithms. But does DQI obtain the best possible solutions? That is, are there solutions better than the semicircle law for worst-case OPI instances? Surprisingly, before this work, the best existential results coincide with (and follow from) the best algorithmic results. In this work, we show that there are better solutions for worst-case OPI instances over prime fields. In particular, DQI and the semicircle law are not optimal. For example, when the lists $S_i$ have size $ρp$ for $ρ\sim 1/2$, our results imply the existence of a solution that asymptotically beats the semicircle law whenever $n/m \geq 0.6225$, and we show that an asymptotically perfect solution exists whenever $n/m \geq 0.7496$. Our results generalize to Max-LINSAT problems derived from any Maximum Distance Separable (MDS) code, and to any $ρ\in (0,1)$. The key insight to our improvement is a connection to local leakage resilience of secret sharing schemes. Along the way, we recover several re-proofs of the existence of solutions achieving the semicircle law.

Comments
45 pages, 4 figures

Related papers

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

Shuji Horinaga, Takashi Yamakawa

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.

quant-pharXiv:2607.14650•Jul 17, 2026•0 citations

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

Yihang Sun, Mary Wootters

We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI). Both problems concern polynomials $Q(X)$ of degree less than $k$, over a prime-order finite field $\mathbb{F}_p$. In LLR for Shamir secret sharing, one asks how much one can learn about $Q(0)$ given a few bits leaked from each of $Q(α_1), \ldots, Q(α_n)$, for distinct non-zero evaluation points $α_i \in \mathbb{F}_p$. In OPI, one is given input list $S_1, \ldots, S_n \subset \mathbb{F}_p$, and wants to find a polynomial $Q(X)$ of degree less than $k$ so that $Q(α_i) \in S_i$ for as many $i$ as possible. Leveraging recent connection between these two problems due to (Sun, Wootters 2026), we improve the state-of-the-art for both problems. For LLR, we show that there is some constant $δ> 0$ so that, as long as $R := k/n \geq 1/2 - δ$, Shamir secret-sharing is one-bit locally leakage resilient (meaning that one can learn only a negligible amount about $Q(0)$). This is the first result to break the so-called "one-half barrier" for LLR, and improves over the previous best known result, requiring $R \geq 0.668$ (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial $Q(X)$ that agrees with at least a $\mathsf{SCL}_ρ(R)-\varepsilon$ fraction of the lists in expectation, for every fixed $\varepsilon>0$, where $\mathsf{SCL}_ρ$ is the \emph{semicircle law} of (Jordan et al., 2025). This improves previous algorithmic (and existential) results of (Jo, 2026) and (Horinaga, Yamakawa, 2026). We also give further improved existential results. We also adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); over large fields, this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.

quant-pharXiv:2610.12357•Oct 9, 2026

Efficient Exact Quantum Sampling from the Sun-Wootters Distribution for Optimal Polynomial Intersection

Sunghyeon Jo

Optimal Polynomial Intersection (OPI) is a structured optimization problem for which Decoded Quantum Interferometry (DQI) attains a satisfaction guarantee governed by the semicircle law. Sun and Wootters recently showed that, for balanced OPI over prime fields, a Fourier-defined distribution $P_u$ gives a strict worst-case improvement from limiting rate $0.6225$ onward and asymptotically perfect solutions from rate $0.7496$ onward, and asked whether $P_u$ can be sampled efficiently. We answer this question for Reed--Solomon OPI parameters satisfying their exponent condition strictly below the dual Johnson radius. Under coherent membership-oracle access, we give a bounded-error polynomial-time quantum sampler for $P_u$. The ideal circuit samples $P_u$ exactly conditioned on success, while a finite-precision implementation achieves any prescribed inverse-polynomial total-variation error. Consequently, every fixed limiting rate $0.6225\le r<1$ admits a strict worst-case improvement over the DQI semicircle value, and every limiting rate $r\ge 3/4$ admits solutions of satisfaction $1-o(1)$ with high probability. The algorithm coherently sums the amplitudes of all low-weight errors in each syndrome class using deterministic complete list decoding. Complete Reed--Solomon list decoding and the Sun--Wootters denominator estimate make the list size and postselection overhead polynomial. In concurrent and independent work, Horinaga and Yamakawa obtain worst-case OPI algorithms over prime-power fields and exact satisfaction at every fixed rate strictly above $3/4$.

quant-pharXiv:2607.16541•Jul 21, 2026•0 citations

Quantum Decoding Algorithms: Quantum Speedups in Optimization

Jan Ljubas, Tim Byrnes

Attaining a quantum speedup in solving practically useful optimization problems has been one of the holy grails in the field of quantum computing. While prior approaches have demonstrated speedups for certain structured problem classes, establishing a clear and scalable advantage on broadly useful practical optimization problems remains challenging. Recently, a new approach to solving the max-LINSAT class of optimization problems has emerged, called Decoded Quantum Interferometry (DQI). In DQI, a combination of techniques rooted in (classical) coding theory and interferometry are used to obtain the solution of max-LINSAT. In the special problem instance of the optimal polynomial intersection (OPI) problem, strong evidence exists to show that an superpolynomial speedup exists over the best classical methods in obtaining an approximate solution. In this review, we give a self-contained description of DQI and the necessary background to understand the algorithm. Specifically, we give the essentials of Galois fields, optimization problems such as max-LINSAT and OPI, and coding theory, followed by a step-by-step walkthrough of the quantum algorithm and its operating principle.

quant-pharXiv:2605.00312•May 4, 2026•0 citations

A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem

Ansis Rosmanis

Recently, Jordan et al. (Nature, 2025) introduced a novel quantum-algorithmic technique called Decoded Quantum Interferometry (DQI) for solving specific combinatorial optimization problems associated with classical codes. They presented a constraint-satisfaction problem called Optimal Polynomial Intersection (OPI) and showed that, for this problem, a DQI algorithm running in polynomial time can satisfy a larger fraction of constraints than any known polynomial-time classical algorithm. In this work, we propose several improvements to the DQI algorithm, including sidestepping the quadratic-time Dicke state preparation. Given random access to the input, we show how these improvements result in a nearly linear-time DQI algorithm for the OPI problem. Concurrently and independently with this work, Khattar et al. (arXiv:2510:10967) also construct a nearly linear-time DQI algorithm for OPI using slightly different techniques.

quant-pharXiv:2601.15171•Jan 22, 2026•0 citations

Exponential quantum advantages for decoded quantum interferometry in the streaming setting

Kewen Wu, Guangxu Yang

Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Besides time, space is another central resource: storing and manipulating a massive input can be very challenging, especially when logical qubits carry substantial fault-tolerant implementation overhead. This motivates the following question: does DQI yield quantum advantages in memory, and can we prove it unconditionally? We give an affirmative answer to this question in the streaming setting. In particular, we consider a natural generalization of OPI using Hermite interpolation and Hasse derivatives, which asks for a low-degree polynomial satisfying as many constraints on its values and derivatives as possible. As a concrete example, we show [Quantum efficiency.] An adaptation of the DQI algorithm produces a polynomial satisfying $93\%$ of the constraints; moreover, it only reads the input stream in one pass, uses polylogarithmic space, and has polylogarithmic computation time per stream entry. [Classical hardness.] Any classical algorithm that produces an answer satisfying just $76\%$ of the constraints requires polynomial space, even if it can read the input stream with polynomially many passes and can use unlimited time. Our result provides a complete tradeoff curve for the tunable parameters, and implies that DQI has provable quantum advantages for the original OPI problem.

quant-pharXiv:2610.01902•Oct 2, 2026•0 citations
The Optimal Polynomial Intersection (OPI) problem is the following: Given sets S1,…,Sm⊆FS_1, \ldots, S_m \subseteq \mathbb{F}S1​,…,Sm​⊆F and evaluation points a1,…,am∈Fa_1, \ldots, a_m \in \mathbb{F}a1​,…,am​∈F, find a polynomial Q∈F[x]Q \in \mathbb{F}[x]Q∈F[x] of degree less than nnn so that Q(ai)∈SiQ(a_i) \in S_iQ(ai​)∈Si​ for as many i∈{1,2,…,m}i \in \{1, 2, \ldots, m\}i∈{1,2,…,m} as possible. Decoded Quantum Interferometry (DQI) is a quantum algorithm that efficiently returns good solutions to the problem, even on worst-case instances (Jordan et. al., 2025). The quality of the solutions returned follows a semicircle law, which outperforms known efficient classical algorithms. But does DQI obtain the best possible solutions? That is, are there solutions better than the semicircle law for worst-case OPI instances? Surprisingly, before this work, the best existential results coincide with (and follow from) the best algorithmic results.
In this work, we show that there are better solutions for worst-case OPI instances over prime fields. In particular, DQI and the semicircle law are not optimal. For example, when the lists SiS_iSi​ have size ρpρpρp for ρ∼1/2ρ\sim 1/2ρ∼1/2, our results imply the existence of a solution that asymptotically beats the semicircle law whenever n/m≥0.6225n/m \geq 0.6225n/m≥0.6225, and we show that an asymptotically perfect solution exists whenever n/m≥0.7496n/m \geq 0.7496n/m≥0.7496. Our results generalize to Max-LINSAT problems derived from any Maximum Distance Separable (MDS) code, and to any ρ∈(0,1)ρ\in (0,1)ρ∈(0,1). The key insight to our improvement is a connection to local leakage resilience of secret sharing schemes. Along the way, we recover several re-proofs of the existence of solutions achieving the semicircle law.
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=1s=1s=1 whenever the rate satisfies R>0.75R>0.75R>0.75. This matches the previous average-case bound, whereas DQI cannot achieve s=1s=1s=1 unless R=1R=1R=1. Our existential bound guarantees the existence of a solution when R>0.7158R> 0.7158R>0.7158, improving over the previous threshold R>0.7495R>0.7495R>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.
We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI). Both problems concern polynomials Q(X)Q(X)Q(X) of degree less than kkk, over a prime-order finite field Fp\mathbb{F}_pFp​. In LLR for Shamir secret sharing, one asks how much one can learn about Q(0)Q(0)Q(0) given a few bits leaked from each of Q(α1),…,Q(αn)Q(α_1), \ldots, Q(α_n)Q(α1​),…,Q(αn​), for distinct non-zero evaluation points αi∈Fpα_i \in \mathbb{F}_pαi​∈Fp​. In OPI, one is given input list S1,…,Sn⊂FpS_1, \ldots, S_n \subset \mathbb{F}_pS1​,…,Sn​⊂Fp​, and wants to find a polynomial Q(X)Q(X)Q(X) of degree less than kkk so that Q(αi)∈SiQ(α_i) \in S_iQ(αi​)∈Si​ for as many iii as possible. Leveraging recent connection between these two problems due to (Sun, Wootters 2026), we improve the state-of-the-art for both problems. For LLR, we show that there is some constant δ>0δ> 0δ>0 so that, as long as R:=k/n≥1/2−δR := k/n \geq 1/2 - δR:=k/n≥1/2−δ, Shamir secret-sharing is one-bit locally leakage resilient (meaning that one can learn only a negligible amount about Q(0)Q(0)Q(0)). This is the first result to break the so-called "one-half barrier" for LLR, and improves over the previous best known result, requiring R≥0.668R \geq 0.668R≥0.668 (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial Q(X)Q(X)Q(X) that agrees with at least a SCLρ(R)−ε\mathsf{SCL}_ρ(R)-\varepsilonSCLρ​(R)−ε fraction of the lists in expectation, for every fixed ε>0\varepsilon>0ε>0, where SCLρ\mathsf{SCL}_ρSCLρ​ is the \emph{semicircle law} of (Jordan et al., 2025). This improves previous algorithmic (and existential) results of (Jo, 2026) and (Horinaga, Yamakawa, 2026). We also give further improved existential results. We also adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); over large fields, this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.
Optimal Polynomial Intersection (OPI) is a structured optimization problem for which Decoded Quantum Interferometry (DQI) attains a satisfaction guarantee governed by the semicircle law. Sun and Wootters recently showed that, for balanced OPI over prime fields, a Fourier-defined distribution PuP_uPu​ gives a strict worst-case improvement from limiting rate 0.62250.62250.6225 onward and asymptotically perfect solutions from rate 0.74960.74960.7496 onward, and asked whether PuP_uPu​ can be sampled efficiently. We answer this question for Reed--Solomon OPI parameters satisfying their exponent condition strictly below the dual Johnson radius. Under coherent membership-oracle access, we give a bounded-error polynomial-time quantum sampler for PuP_uPu​. The ideal circuit samples PuP_uPu​ exactly conditioned on success, while a finite-precision implementation achieves any prescribed inverse-polynomial total-variation error. Consequently, every fixed limiting rate 0.6225≤r<10.6225\le r<10.6225≤r<1 admits a strict worst-case improvement over the DQI semicircle value, and every limiting rate r≥3/4r\ge 3/4r≥3/4 admits solutions of satisfaction 1−o(1)1-o(1)1−o(1) with high probability. The algorithm coherently sums the amplitudes of all low-weight errors in each syndrome class using deterministic complete list decoding. Complete Reed--Solomon list decoding and the Sun--Wootters denominator estimate make the list size and postselection overhead polynomial. In concurrent and independent work, Horinaga and Yamakawa obtain worst-case OPI algorithms over prime-power fields and exact satisfaction at every fixed rate strictly above 3/43/43/4.
Attaining a quantum speedup in solving practically useful optimization problems has been one of the holy grails in the field of quantum computing. While prior approaches have demonstrated speedups for certain structured problem classes, establishing a clear and scalable advantage on broadly useful practical optimization problems remains challenging. Recently, a new approach to solving the max-LINSAT class of optimization problems has emerged, called Decoded Quantum Interferometry (DQI). In DQI, a combination of techniques rooted in (classical) coding theory and interferometry are used to obtain the solution of max-LINSAT. In the special problem instance of the optimal polynomial intersection (OPI) problem, strong evidence exists to show that an superpolynomial speedup exists over the best classical methods in obtaining an approximate solution. In this review, we give a self-contained description of DQI and the necessary background to understand the algorithm. Specifically, we give the essentials of Galois fields, optimization problems such as max-LINSAT and OPI, and coding theory, followed by a step-by-step walkthrough of the quantum algorithm and its operating principle.
Recently, Jordan et al. (Nature, 2025) introduced a novel quantum-algorithmic technique called Decoded Quantum Interferometry (DQI) for solving specific combinatorial optimization problems associated with classical codes. They presented a constraint-satisfaction problem called Optimal Polynomial Intersection (OPI) and showed that, for this problem, a DQI algorithm running in polynomial time can satisfy a larger fraction of constraints than any known polynomial-time classical algorithm. In this work, we propose several improvements to the DQI algorithm, including sidestepping the quadratic-time Dicke state preparation. Given random access to the input, we show how these improvements result in a nearly linear-time DQI algorithm for the OPI problem. Concurrently and independently with this work, Khattar et al. (arXiv:2510:10967) also construct a nearly linear-time DQI algorithm for OPI using slightly different techniques.
Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Besides time, space is another central resource: storing and manipulating a massive input can be very challenging, especially when logical qubits carry substantial fault-tolerant implementation overhead. This motivates the following question: does DQI yield quantum advantages in memory, and can we prove it unconditionally? We give an affirmative answer to this question in the streaming setting. In particular, we consider a natural generalization of OPI using Hermite interpolation and Hasse derivatives, which asks for a low-degree polynomial satisfying as many constraints on its values and derivatives as possible. As a concrete example, we show [Quantum efficiency.] An adaptation of the DQI algorithm produces a polynomial satisfying 93%93\%93% of the constraints; moreover, it only reads the input stream in one pass, uses polylogarithmic space, and has polylogarithmic computation time per stream entry. [Classical hardness.] Any classical algorithm that produces an answer satisfying just 76%76\%76% of the constraints requires polynomial space, even if it can read the input stream with polynomially many passes and can use unlimited time. Our result provides a complete tradeoff curve for the tunable parameters, and implies that DQI has provable quantum advantages for the original OPI problem.