Pith. sign in

REVIEW 2 major objections 2 minor 1 cited by

A quantum algorithm solves the optimal polynomial intersection problem in the worst case for any choice of target subsets, achieving perfect solutions whenever the rate exceeds 0.75 when each subset holds half the field.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 01:31 UTC pith:J5TJH3LQ

load-bearing objection First worst-case OPI algorithm beyond DQI—likely correct, but the typeset proof has a repairable conjugation error in Lemma 6.7 that needs fixing before the main theorem goes through. the 2 major comments →

arxiv 2607.14650 v1 pith:J5TJH3LQ submitted 2026-07-16 quant-ph

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

Shuji Horinaga , Takashi Yamakawa This is my paper
classification quant-ph MSC 68Q1281P6894B35
keywords optimal polynomial intersectionquantum algorithmworst-caselist decodingReed–Solomon codesBrascamp–Lieb inequalityFourier biasMDS codes
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper claims that the optimal polynomial intersection (OPI) problem — find a low-degree polynomial whose values lie in prescribed subsets on as many inputs as possible — can be solved in the worst case by a quantum polynomial-time algorithm in parameter regimes that previously only average-case algorithms could reach. In the balanced case where each subset contains about half the field, the algorithm finds a perfect solution whenever the rate R=k/n exceeds 0.75, matching the average-case bound and exceeding what decoded quantum interferometry can guarantee. The proof works for arbitrary subsets, not random ones, by combining a Fourier-domain quantum reduction with a list decoder that outputs a random list element, and bounding the error terms with a new Brascamp–Lieb inequality for maximum distance separable (MDS) codes. As a byproduct, the existential bound for existence of solutions improves from R>0.7495 to R>0.7158 at density 1/2.

Core claim

We prove that for q=p^e with p=ω(1), n/2≤k≤n, R=k/n, if R>0.75 then there is a quantum polynomial-time algorithm that, given membership oracles for arbitrary subsets S_i⊆F_q of size ≈q/2 and any distinct evaluation points α_i, outputs with probability 1/poly(n) a polynomial P of degree <k with P(α_i)∈S_i for every i. More generally, for s<1 the algorithm succeeds under conditions (27) and (28), and an analogous existential result holds for any MDS MaxLINSAT instance under condition (37).

What carries the argument

The load-bearing object is the MDS Brascamp–Lieb inequality: for any MDS code C of dimension k and rate R, the sum over codewords of ∏ h_i(u_i) is at most ∏_i (∑_a h_i(a)^{1/R})^R. This inequality is applied to tilted weight functions that assign extra weight t·|μ_i(a)| on nonzero coordinates, exploiting the minimum distance of the dual code, to bound the sum of Fourier-bias products over nonzero dual codewords. The algorithm itself is a Fourier-domain quantum reduction that decodes the dual generalized Reed–Solomon code by picking a uniformly random element from the list-decoder output, making the failure set exactly the Hamming tail T_{rn} so that a Chernoff argument controls the main erro

Load-bearing premise

The whole worst-case guarantee hinges on the dual generalized Reed–Solomon code being list-decodable at relative radius r=1−√(1−R)−Ω(1) with polynomial list size; if the true list-decoding radius at that rate is smaller, the Hamming-tail failure set would not be suppressed and the R>0.75 threshold would collapse.

What would settle it

A concrete falsifier would be an explicit family of subsets S_i⊆F_q of density ≈1/2 and a rate R>0.75 where the fourth-moment Fourier bound of Lemma 4.3 or the single-coefficient bias bound of Lemma 4.4 is violated by a constant factor; or a demonstration that the dual of a generalized Reed–Solomon code at rate 1−R requires super-polynomial list size at radius 1−√(1−R)−ε. Either would invalidate the proof of the worst-case guarantee.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • For ρ=1/2, a quantum polynomial-time algorithm outputs a perfect solution (s=1) for every R>0.75 in the worst case, matching the average-case bound and exceeding decoded quantum interferometry, which needs R=1.
  • For general ρ, the worst-case algorithm beats the DQI guarantee for 0<ρ<0.6351 and matches the average-case saturation bound in the range 0.1248<ρ<0.5200.
  • The existential bound improves to R>0.7158 at ρ=1/2, down from the previous threshold 0.7495, and extends to MaxLINSAT for any MDS code; the algorithmic version extends to any MDS code whose dual admits an efficient list decoder.
  • The new MDS Brascamp–Lieb inequality, used to bound Fourier-bias sums over dual codewords, is stated as a general tool that may have applications beyond OPI.

Where Pith is reading between the lines

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

  • The exact match between the worst-case threshold R>0.75 and the previous average-case threshold at ρ=1/2 suggests that, at least in the balanced case, randomness in the subsets is not the source of hardness; the average-case and worst-case algorithmic gaps may close entirely.
  • The MDS Brascamp–Lieb inequality is likely to find use in other problems where sums of products over dual codes appear, such as list recovery or leakage-resilient secret sharing, where it could sharpen existing bounds.
  • The R>0.75 threshold is tied to the current list-decoding radius of generalized Reed–Solomon codes; any improvement in that radius would translate directly into a better worst-case OPI threshold.
  • A concrete testable extension: run the algorithm at R just below 0.75 to see which of the two conditions — the Chernoff tail bound or the Brascamp–Lieb entropy condition — is the bottleneck; if the latter, sharper Fourier-bias estimates for density-1/2 sets would lower the threshold.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper presents a quantum algorithm for the Optimal Polynomial Intersection (OPI) problem with worst-case correctness guarantees. For the balanced case ρ=1/2, it claims to find a perfect solution (s=1) for any rate R>0.75, matching the previous average-case bound and going beyond DQI, which requires R=1. For general s, it gives a tradeoff. It also proves an improved existential bound (R>0.7158 for ρ=1/2) and extends the existential result to MaxLINSAT with arbitrary MDS codes. The technical core is a new MDS Brascamp–Lieb inequality, a Regev-style algorithm with a list decoder that outputs a random list element, and worst-case Fourier bias bounds. The main proof is structured through Lemmas 6.3–6.9.

Significance. If correct, this resolves the open question of whether the average-case improvement of Chailloux could be matched in the worst case, and gives the first worst-case quantum algorithm for OPI beyond DQI. The MDS Brascamp–Lieb inequality is a clean and potentially useful contribution. The paper also improves existential thresholds. However, the proof as typeset contains a load-bearing error in the Fourier generating-polynomial argument.

major comments (2)
  1. [§6.1.1, Lemmas 6.3 and 6.7] The expansion of the squared modulus in Eq (20) requires Γ(u)=∑_e 1_{T_rn}(e)1_{T_rn}(e+u) \hat W(e)\overline{\hat W(e+u)}, and the generating polynomial should be K_i^{(b)}(X,Y)=∑_a \hat W_i(a)\overline{\hat W_i(a+b)} X^{1_{a≠0}}Y^{1_{a+b≠0}}. As typeset both omit the conjugate. This is not cosmetic: without the conjugate, the identity K_i^{(b)}=μ_i(b)(κX+κY+(1−2κ)XY) is false for generic S_i, since \hat W_i(b)≠\hat W_i(−b) for real but non-even W_i, and the ℓ1 bound ∥K_i^{(b)}∥_1=|ν_i(b)| fails. Moreover, even after restoring the conjugate, the coefficient calculation yields the factor \hat W_i(0)\overline{\hat W_i(b)}=A/D with A=√(τρ)+√((1−τ)(1−ρ)), D=√(τ/ρ)+√((1−τ)/(1−ρ)), so the correct coefficient is A/D, not the κ_{τ,ρ}=A/(D−1) defined in the paper. The proof of Lemma 6.8 and hence Eq (23) depends on these identities. The fix is to insert the conjugates and set κ_{τ,ρ}=A/D; with t
  2. [§6.1.1 / Remark 6.2] With the paper's stated κ (and λ=max{1,4κ−1}), the claim that Eq (28) holds automatically for ρ=1/2, τ=1, R>0.75 is false. For example, at R=0.76, Q≈4.167, M≈400, giving H(R)+R log M > 6, so Theorem 6.1 would not apply. The correctness of Theorem 1.1 therefore relies on the corrected κ (λ=1 for this case), which yields M≈1/3 at R=0.75 and gives a negative entropy condition. The authors should re-derive the numerical thresholds after the correction.
minor comments (2)
  1. [Throughout] The theorem statements use Ω(1) margins without quantifying the constants. For reproducibility, state explicitly that the constants are universal for the family and that the conditions hold for all sufficiently large n (as is standard for asymptotic complexity).
  2. [Figures and thinning] The abstract and Figure 2 refer to a thinning argument (Lemma A.1) that is not part of the formal statement of Theorem 6.1. It would help to state in Theorem 6.1, or in a remark immediately after, that the algorithm can be combined with Lemma A.1 to handle larger values of ρ.

Circularity Check

0 steps flagged

No significant circularity: the worst-case guarantee is a conditional theorem proved from stated rate/density conditions, proven Fourier and Brascamp–Lieb bounds, and external list-decoding results.

full rationale

The derivation is self-contained in the sense relevant to circularity. Theorem 6.1 is a conditional worst-case guarantee: if (27) and (28) hold, then the algorithm succeeds with s = tau - Omega(1). These conditions are not fitted: (27) is a rate/density inequality inherited from Corollary 5.2's Chernoff step, and (28) is the log-moment condition obtained by optimizing t in Lemma 6.8. The two main technical inputs are proved in the paper: the MDS Brascamp-Lieb inequality (Theorem 3.1) is derived from MDS projection injectivity, entropy subadditivity, and the Gibbs variational principle, with Lemma 3.2 proved in Appendix B; the Fourier-bias bounds in Section 4 are proved using Parseval, Green-Ruzsa/Pollard, and Lemma 4.4, which is an external result of Sun-Wootters generalized here. The list-decodability of the dual GRS code at radius r = 1 - sqrt(1-R) - Omega(1) is cited to GS99/CHK26 and is used as an explicit hypothesis of the reduction (Theorem 5.1/Corollary 5.2), not derived from the conclusion. The existential Theorem 7.1 uses the same proven machinery plus Lemma 7.3; it does not assume a solution exists. Self-citations to YZ24 are for standard Fourier facts and as the conceptual Regev-reduction antecedent; Theorem 5.1 is proved in Section 5.1 rather than imported. The typesetting/conjugation defect in Lemma 6.7 identified by the skeptic is a localized correctness error--repaired by conjugating hat W(e+u)--and does not amount to a definitional or fitted-input circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The central claim is built on standard coding theory (list decoding of GRS codes), additive combinatorics (Green–Ruzsa), and a proven new inequality (MDS BL). No entity is invented, and no parameter is fitted to data; the only 'chosen' constants are the asymptotic Ω(1) margins which hold for all sufficiently large n.

axioms (5)
  • domain assumption Generalized Reed–Solomon codes are list-decodable at relative radius 1−√(rate)−Ω(1) with list size poly(n) (Guruswami–Sudan; [GS99, CHK26]).
    Used in Section 6.1 (proof of Theorem 6.1) and Corollary 5.2 to set r=1−√(1−R)−Ω(1) for the dual code C^⊥; the whole worst-case analysis depends on this radius.
  • standard math Green–Ruzsa theorem (Theorem 4.5), generalizing Pollard's and Kneser's theorems, giving lower bounds on ∑ min{t, r_{A,B}(x)}.
    Used to prove the additive-energy bound (Lemma 4.8) and hence the fourth-moment Fourier bound (Lemma 4.3), which feeds into M_{τ,ρ}.
  • domain assumption Prime-field Fourier-bias bound from Sun–Wootters [SW26, Fact 4.12]: for A⊆F_p, |∑_{a∈A}ω^{-ta}|/p ≤ sin(π|A|/p)/π + O(p^{-2}).
    Lemma 4.4 generalizes this to extension fields; the balanced-case saturation threshold R>0.75 uses this pointwise bound to control max |μ_i(a)|.
  • standard math Gibbs variational principle and entropy subadditivity (Lemma 3.2, Eq (10))
    Core of the MDS Brascamp–Lieb inequality proof (Section 3).
  • standard math Chernoff bound (Lemma 2.5) and Parseval's identity (Lemma 2.1)
    Used to convert Eq (19) into a tail bound and to normalize Fourier sums in Cor 5.2.

pith-pipeline@v1.3.0-alltime-deepseek · 38762 in / 42095 out tokens · 341730 ms · 2026-08-02T01:31:19.447332+00:00 · methodology

0 comments
read the original 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.

Figures

Figures reproduced from arXiv: 2607.14650 by Shuji Horinaga, Takashi Yamakawa.

Figure 1
Figure 1. Figure 1: Comparison of achievable algorithmic satisfaction rates in the balanced case [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of algorithmic saturation bounds as functions of [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of existential satisfaction rates in the balanced case [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of existential saturation bounds as functions of [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

    quant-ph 2026-07 accept novelty 7.0

    Block-Gibbs MCMC matches DQI approximation ratios on max-XORSAT and OPI, with OPI runtime empirically ~1.1^n, without refuting asymptotic quantum-advantage claims.

Reference graph

Works this paper leans on

17 extracted references · 1 linked inside Pith · cited by 1 Pith paper

  1. [4]

    [CHK26] Soham Chatterjee, Prahladh Harsha, and Mrinal Kumar

    arXiv:2511.22691. [CHK26] Soham Chatterjee, Prahladh Harsha, and Mrinal Kumar. Deterministic list decoding of Reed-Solomon codes. In Aditya Bhaskara and Artur Czumaj, editors,Proc.58th ACM Symp. on Theory of Computing (STOC), pages 2040–2051,

    arXiv 2040

  2. [7]

    An improvement upon the bounds for the local leakage resilience of shamir’s secret sharing scheme

    [Kas24] Dustin Kasser. An improvement upon the bounds for the local leakage resilience of shamir’s secret sharing scheme. In Elette Boyle and Mohammad Mahmoody, editors, TCC 2024, Part IV, volume 15367 ofLNCS, pages 395–422. Springer, Cham, December

    2024

  3. [9]

    [Lin10] Yehuda Lindell

    arXiv:2510.07515. [Lin10] Yehuda Lindell. Introduction to coding theory lecture notes,

    arXiv

  4. [12]

    Maji, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang

    [MPSW21] Hemanta K. Maji, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang. Con- structing locally leakage-resilient linear secret-sharing schemes. In Tal Malkin and Chris Peikert, editors,CRYPTO 2021, Part III, volume 12827 ofLNCS, pages 779– 808, Virtual Event, August

    2021

  5. [13]

    51 [Ngu24] Hai H

    Springer, Cham. 51 [Ngu24] Hai H. Nguyen. Towards breaking the half-barrier of local leakage-resilient shamir’s secret sharing. In Leonid Reyzin and Douglas Stebila, editors,CRYPTO 2024, Part V, volume 14924 ofLNCS, pages 257–285. Springer, Cham, August

    2024

  6. [14]

    A decade of lattice cryptography

    [Pei15] Chris Peikert. A decade of lattice cryptography. Cryptology ePrint Archive, Report 2015/939,

    2015

  7. [16]

    [vDHI06] Wim van Dam, Sean Hallgren, and Lawrence Ip

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

    Pith/arXiv arXiv

  8. [17]

    How to record quantum queries, and applications to quantum indiffer- entiability

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

    2019

  9. [1994]

    Efficient public key encryption based on ideal lattices

    [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 ofLNCS, pages 617–635. Springer, Berlin, Heidelberg, December

    2009

  10. [2009]

    On the quantum equivalence betweens|lwe⟩and isis

    [CH26] Andr´ e Chailloux and Paul Hermouet. On the quantum equivalence betweens|lwe⟩and isis. InCRYPTO 2026 (to appear),

    2026

  11. [2010]

    [LPR13] Vadim Lyubashevsky, Chris Peikert, and Oded Regev

    https://yehudalindell.com/wp-content/uploads/2023/06/coding_ theory-lecture-notes.pdf. [LPR13] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings.J. ACM, 60(6):43:1–43:35,

    2023

  12. [2013]

    Maji, Hai H

    [MNPW22] Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, and Mingyuan Wang. Improved bound on the local leakage-resilience of shamir’s secret sharing. InIEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, June 26 - July 1, 2022, pages 2678–2683. IEEE,

    2022

  13. [2021]

    Learning with errors and extrapolated dihedral cosets

    [BKSW18] Zvika Brakerski, Elena Kirshanova, Damien Stehl´ e, and Weiqiang Wen. Learning with errors and extrapolated dihedral cosets. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part II, volume 10770 ofLNCS, pages 702–727. Springer, Cham, March

    2018

  14. [2022]

    The quantum decoding problem

    [CT24] Andr´ e Chailloux and Jean-Pierre Tillich. The quantum decoding problem. In Fr´ ed´ eric Magniez and Alex Bredariol Grilo, editors,19th Conference on the Theory of Quan- tum Computation, Communication and Cryptography, TQC 2024, Okinawa, Japan, September 9-13, 2024, LIPIcs, pages 6:1–6:14. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik,

    2024

  15. [2024]

    New bounds on the local leakage resilience of Shamir’s secret sharing scheme

    [KK23] Ohad Klein and Ilan Komargodski. New bounds on the local leakage resilience of Shamir’s secret sharing scheme. In Helena Handschuh and Anna Lysyanskaya, edi- tors,CRYPTO 2023, Part I, volume 14081 ofLNCS, pages 139–170. Springer, Cham, August

    2023

  16. [2025]

    [BDG+26] Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, and Amit Sahai

    arXiv:2510.13775. [BDG+26] Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, and Amit Sahai. Quantum advantage via solving multivariate polynomials. In Kasper Green Larsen and Barna Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 1383–1423. SIAM,

    arXiv 2026

  17. [2026]

    Quantum algorithms for variants of average-case lattice problems via filtering

    [CLZ22] Yilei Chen, Qipeng Liu, and Mark Zhandry. Quantum algorithms for variants of average-case lattice problems via filtering. In Orr Dunkelman and Stefan Dziembowski, editors,EUROCRYPT 2022, Part III, volume 13277 ofLNCS, pages 372–401. Springer, Cham, May / June

    2022