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

Sunghyeon Jo

REVIEW 2 major objections 4 minor 1 cited by

Reed–Solomon OPI instances below the dual Johnson radius can be sampled from the Sun–Wootters distribution exactly in polynomial time on a quantum computer, yielding strict improvements from rate 0.6225 and near-perfect satisfaction at 3/4.

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-01 20:39 UTC pith:TZBAUN57

load-bearing objection A genuinely new coherent fiber-summation algorithm that answers the Sun–Wootters sampling question, but the central efficiency claim depends on an unverified strengthened reading of their analytic estimate; worth refereeing seriously. the 2 major comments →

arxiv 2607.16541 v2 pith:TZBAUN57 submitted 2026-07-17 quant-ph cs.ITmath.IT

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

Sunghyeon Jo This is my paper

classification quant-ph cs.ITmath.IT MSC 68Q1281P6894B35

keywords quantum samplingoptimal polynomial intersectionSun–Wootters distributionReed–Solomon codeslist decodingcoherent postselectionJohnson radiussemicircle benchmark

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.

Optimal polynomial intersection asks for a low-degree polynomial that hits as many prescribed target sets as possible at given evaluation points. The paper proves that a previously proposed Fourier-defined target distribution over polynomials—one already known to beat the semicircle benchmark from rate 0.6225 onward—can be sampled by a bounded-error, polynomial-time quantum algorithm for balanced prime-field Reed–Solomon instances below the dual Johnson radius. The key move is coherent list-index projection: the algorithm runs a complete deterministic list decoder, pads every syndrome's error list to the same length, and Hadamard-projects the list index, summing all low-weight errors in a syndrome class with their complex phases intact. Conditioned on the projection flag, the inverse Fourier transform samples the target distribution exactly; finite precision gives any inverse-polynomial total-variation error. As a corollary, every fixed rate from 0.6225 to below 1 gets a strict worst-case algorithmic improvement over the semicircle value, and every rate at least 3/4 yields satisfaction 1−o(1) with high probability.

Core claim

On a balanced OPI instance over a prime field, the target distribution P_u is defined through Fourier coefficients of the discrepancy functions at a chosen cutoff radius. The paper constructs an ideal quantum circuit whose successful branch samples P_u exactly. The circuit prepares a labeled superposition over low-weight error vectors y with coherent weights and syndromes Hy, uses a deterministic complete list decoder for the dual generalized Reed–Solomon code to enumerate every low-weight error in each syndrome fiber, and sorts and pads every fiber to one global list length L. Reversibly indexing each error in its fiber and applying a Hadamard transform to the index register projects the er

What carries the argument

The central mechanism is coherent list-index projection: a reversible circuit maps each supported pair (y,s) with Hy=s to the canonical slot of y in a padded list of all low-weight errors with syndrome s, flags valid matches, and then a Hadamard on the list-index register coherently sums the amplitudes within every fiber with a common factor L^{-1/2}. It combines a deterministic complete decoder for the dual generalized Reed–Solomon code, valid below the Johnson radius m−ℓ > sqrt((m−n−1)m), with the Sun–Wootters denominator estimate Z_I = |K| + O(m^C e^{-cm}), which together bound the list length and the postselection overhead polynomially.

Load-bearing premise

The whole algorithmic guarantee inherits the stronger, distributional reading of the Sun–Wootters analytic estimate asserted in Remark 2.3—namely that the denominator concentrates as Z_I = |K| + O(m^C e^{-cm}) and that the expected score under P_u beats the semicircle value by o(1); if that reading is wrong, the postselection probability and the optimization guarantees fail even though the circuit identity itself remains true.

What would settle it

Simulate or exactly compute the denominator Z_I = E_x |F(x)|^2 for a balanced OPI family with n/m near 0.6225 and a small positive δ satisfying condition (17). If Z_I/Z_0 does not tend to 1 at the asserted exponential rate, Lemma 6.4 and the resulting polynomial-time guarantees collapse; the circuit identity itself would remain true.

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

If this is right

Every limiting rate r with 0.6225 ≤ r < 1 has a uniform polynomial-time quantum algorithm whose expected satisfaction ratio beats the semicircle-law benchmark by a positive constant depending only on r.
Every limiting rate r ≥ 3/4 has a uniform polynomial-time quantum algorithm that outputs a polynomial of satisfaction ratio 1−o(1) with probability 1−o(1), including the limiting Johnson point r = 3/4.
The ideal circuit samples the Sun–Wootters distribution exactly on success, and a finite-precision implementation samples it to any inverse-polynomial total-variation error, so the sampler converts any analytic bound on P_u's expected score into an algorithmic guarantee.
The construction is uniform and runs in polynomial time in m, log p, log(1/η), and log(1/β) under coherent membership-oracle access, with only polynomial overhead from error correction.

Where Pith is reading between the lines

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

The exact circuit identity itself does not depend on the Sun–Wootters exponent condition; that condition is used only for the success probability and score guarantee. If a coherent weighted-sum routine whose complexity depended on amplitudes rather than maximum list size were available beyond the Johnson radius, the same fiber-summing idea could give exact sampling in the missing radius-1/2 region
The requirement of a single global padding length L is essential because syndrome-dependent normalization would distort the target distribution. This suggests a testable extension: non-uniform padding with a known correction factor could trade list size against success probability while still reproducing P_u.
The optimization corollary uses classical evaluation of polynomially many samples and taking the best; an amplitude-amplified version of the sampler could reduce the number of attempts, though that route is not explored in the paper.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

A genuinely new coherent fiber-summation algorithm that answers the Sun–Wootters sampling question, but the central efficiency claim depends on an unverified strengthened reading of their analytic estimate; worth refereeing seriously.

read the letter

Bottom line: this is a genuinely new algorithm — an exact coherent way to sum over all low-weight errors in a syndrome class — and it answers the explicit open question from Sun and Wootters. The main theorem is real, but it leans on a strengthened reading of the SW analytic estimate that the paper does not verify. If that reading is wrong, the polynomial-time claim collapses, though the circuit identity would still hold.

The coherent fiber-summation mechanism is the real novelty: using one padded list length L for all syndromes and projecting onto the uniform index state preserves the phases and gives the exact Sun–Wootters distribution conditioned on success. Lemma 5.1 and Theorem 5.2 are clean, and the reversible indexing construction is sound. The transfer from existence to algorithmic separation (Lemmas 8.2–8.5 and Corollaries 8.6, 8.8) is also well done; the numerical endpoint checks in Lemma 8.3 use rigorous interval arithmetic. The paper is clearly written and honest about its scope.

The soft spot is the external dependency. Theorem 2.1 is stated as a consequence of the proof of Sun–Wootters’s Theorem 1.6, but the paper does not reproduce the derivation. Remark 2.3 even concedes that the original theorem is existential and asserts the stronger distributional conclusion without proof. Everything downstream — Lemma 6.4’s success probability and hence Theorem 7.1’s polynomial restart — depends on equation (18) being a uniform worst-case denominator estimate in exactly the normalization used here. If SW’s estimate is average-case or has a different proportionality constant, the sampler may still be exact on success but the success probability could be exponentially small, and the algorithm would not be polynomial time. This is not a flaw in the internal logic; it is a missing verification of a load-bearing citation. The paper would be materially stronger with an appendix deriving equations (18) and (19) from SW’s lemmas, or a statement from the SW authors confirming the strengthened form.

The CHK list-decoder reliance is less worrying; it is a standard external result and the reduction in Corollary 4.3 looks correct.

Who this is for: people working on DQI, quantum optimization, and quantum algorithms for structured problems. It deserves a serious referee; my own verdict is conditional, not reject.

Referee Report

2 major / 4 minor

Summary. The paper presents a quantum algorithm for sampling the Sun–Wootters distribution P_u for balanced prime-field Reed–Solomon Optimal Polynomial Intersection (OPI), under coherent membership-oracle access and for cutoffs strictly below the dual Johnson radius. The construction combines a complete deterministic list decoder for the dual generalized Reed–Solomon code with a reversible, uniformly padded list-index projection to coherently sum amplitudes over each syndrome fiber. The main theorem (Thm 7.1) asserts a bounded-error polynomial-time sampler that, conditioned on success, samples P_u exactly (or to inverse-polynomial total-variation error in finite precision). The paper then uses the Sun–Wootters analytic estimates and a monotonicity argument to claim strict expected-score improvements over DQI at every fixed rate r ≥ 0.6225, and satisfaction 1−o(1) at rate r ≥ 3/4 (Corollaries 8.6 and 8.8).

Significance. If the Sun–Wootters denominator and expectation estimates are available in the uniform, worst-case form stated in Theorem 2.1, the paper's circuit construction is elegant and significant: it gives the first efficient exact sampler for P_u, completes the algorithmic realization of the Sun–Wootters improvement, and provides a stricter separation than concurrent work. The paper's intrinsic contributions—Lemma 5.1's reversible indexing, Theorem 5.2's coherent fiber sum, Prop. 6.2's state preparation, and the finite-precision analysis of Thm 6.6—are rigorous, self-contained, and useful beyond this application. The clarity of the circuit identity and the reliance on machine-checkable reversible compiling are strengths. However, the overall efficiency claim rests on an imported analytic estimate that is not proved in this manuscript, which is a substantial risk.

major comments (2)

[§2.3, Theorem 2.1, Remark 2.3] The load-bearing analytic input is unproven. Theorem 1.6 of [SW26] is existential; Remark 2.3 concedes that (18) and (19) are a stronger distributional reading of the proof. These equations are essential: Lemma 6.4 derives p_fib ≥ 1/(2L) from (18), and Theorem 7.1 uses (19) for the score bound. The 'Derivation from the cited estimates' asserts that SW's Proposition 4.7, Lemmas 4.10/4.11/5.2, and equation (4.35) yield uniform worst-case bounds for all balanced input sets with the normalization (12), but it does not verify: (i) that those lemmas are indeed stated for arbitrary balanced sets; (ii) that the normalization of u_k in (12) matches the one used in SW's denominator and expectation estimates; (iii) that (19) is actually what the proof establishes. If any of these fails, the postselection probability may be exponentially small for some instances, and the polynomial-time guarantee of
[§8, Lemma 8.4] The proof of Lemma 8.4 is too compressed to be checkable. The envelope-theorem step leading to (59) is not derived, and the rational bounds in (61)–(62) are stated without intermediate interval arithmetic. Since Corollary 8.6 (the 0.6225 threshold) depends on this lemma, the authors should expand the proof or provide the full computation. This is not a correctness claim against the lemma, but a reproducibility concern.

minor comments (4)

[Cross-references] Several cross-references are mislabeled: 'theorem 3.1' in Lemma 6.4 should be 'Lemma 3.1'; 'theorem 4.1' in Corollary 4.3 should be 'Lemma 4.1'; 'theorem 8.2' and 'theorem 8.3' in the proof of Lemma 8.4 should be 'Lemma 8.2' and 'Lemma 8.3'; 'theorem 7.2' in Corollary 8.6 should be 'Corollary 7.2'.
[§2.3, Eq. (12)] The text says 'the proportionality constant in their u_k is immaterial, and we fix it as in equation (12).' This is only true if the normalization does not affect the denominator estimate's constants; since the denominator estimate is central, the authors should state explicitly how the normalization changes if SW's u_k differs.
[§8.3 (Lemma 8.3)] The proof of Lemma 8.3 gives decimal upper bounds but says 'rational upper bounds'; the rational numbers themselves are not displayed. It would be helpful to show the resulting rational intervals or the final rational values.
[§5.1] In Lemma 5.1, the action (37) writes |0⟩_{F_p^m} but the symbol should be |0^m⟩ to avoid confusion with the zero vector of length m; this is a minor notation issue.

Circularity Check

0 steps flagged

No circularity: the sampler is exact by construction and the load-bearing analytic estimates are imported from independent prior work, not produced by the sampler.

full rationale

The derivation chain is linear and does not reduce any output to its own input. The target distribution P_u is defined directly in Section 2.3 via F(x) = sum_k u_k q_k(x). Lemma 3.1 proves, by Fourier inversion and character orthogonality, that F(x) = sum_y a_y chi_{Hy}(x) and Z_I = E_x |F(x)|^2. Lemma 3.2 computes Z_0 = |K| from the normalization of the u_k and from sum_z |hat g_i(z)|^2 = 1. Theorem 5.2 then shows that the coherent list-index projection exactly produces the normalized syndrome state (1/sqrt Z_I) sum_s A_s |s>, whose final inverse QFT measurement law is P_u by definition; the success probability is the algebraic ratio Z_I/(L Z_0). No fitted parameter is later renamed as a prediction, and the global padding length L is chosen canonically from the Johnson list bound, not from the target distribution. The only potentially fragile link is Lemma 6.4, which needs Z_I/Z_0 = 1+o(1); that estimate is taken from Theorem 2.1, which the paper explicitly imports from [SW26] ('We use the following consequence of the proof of Sun and Wootters's Theorem 1.6'). Remark 2.3 concedes that SW's published theorem is existential and that equation (19) is an asserted stronger distributional reading. That is a verification/completeness dependency on independent external work, not circularity: the Sun–Wootters estimate is a hypothesis of the algorithmic theorem, not a consequence of the sampler. Likewise, the deterministic list decoder of [CHK26] is external support. There is no load-bearing self-citation: the author has no overlapping prior work invoked to force the construction, and no uniqueness claim is imported from the present authors. The optimization consequences (Theorems 7.1, 8.6, 8.8) follow by combining exact sampling of P_u with the external expectation bound (19), so the improvement claim is inherited from [SW26] rather than manufactured by the algorithm. Hence no step exhibits the specific reduction required by the circularity criteria, and the appropriate score is 0.

Axiom & Free-Parameter Ledger

4 free parameters · 4 axioms · 0 invented entities

The paper's central claim is conditional on two external results: the Sun–Wootters analytic estimate (including the stronger distributional reading) and the deterministic complete list decoding algorithm of Chatterjee–Harsha–Kumar. Both are cited but not reproduced. The proof also uses standard quantum primitives and classical coding theory facts. No new entities are postulated.

free parameters (4)

δ at μ0 = 249/800 = 10^{-6}
Fixed rational used in Lemma 8.3 to certify E+G < -1/10000 at the left endpoint μ0 = 249/800. Chosen by interval arithmetic; not fitted to data.
λ at μ0 = 249/800 = 3429/20000
Fixed rational satisfying the entropy-domain bounds; used with δ to establish inequality (55). Not fitted to data.
δ at μ = 3/8 = 1/8
Cutoff value that reaches radius 1/2 at the limiting rate 3/4; used in inequality (56).
λ at μ = 3/8 = 99/250
Fixed rational used in inequality (56) for the r=3/4 endpoint.

axioms (4)

domain assumption Sun–Wootters analytic estimate (Theorem 2.1): under condition (17), Z_I = |K| + O(m^C e^{-cm}) and E_{x~P_u} s(x) >= SCL_{1/2}(μ+δ) - o(1), including the stronger distributional reading of Remark 2.3.
This is the source of the polynomial success probability (Lemma 6.4) and the satisfaction guarantee (eq (51) in Theorem 7.1). The paper does not prove it; it cites [SW26] and sketches the derivation from their lemmas.
domain assumption Deterministic complete list decoding of Reed–Solomon codes (CHK26, Theorem 4.2): a poly(M, log|F|)-time algorithm outputs all codewords agreeing with a received word in more than sqrt((K-1)M) coordinates.
Corollary 4.3 and the polynomial complexity of fiber enumeration depend on this black-box result; the paper does not reproduce or verify it.
standard math Exact amplitude amplification with known marked fraction prepares uniform superpositions over S_i and its complement with O(1) membership queries (BHMT02).
Used in Proposition 6.3 to implement Fourier-state access from the membership oracle.
standard math Approximate prime-modulus QFT and single-qubit rotations can be synthesized to operator-norm error ε with poly(log(1/ε)) overhead over a universal gate set (HH00).
Used in the finite-precision implementation (Theorem 6.6, §6.4).

pith-pipeline@v1.3.0-alltime-deepseek · 16574 in / 19666 out tokens · 183607 ms · 2026-08-01T20:39:55.606377+00:00 · methodology

0 comments

read the original abstract

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$.

Figures

Figures reproduced from arXiv: 2607.16541 by Sunghyeon Jo.

discussion (0)

Forward citations

Cited by 1 Pith paper

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

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

15 extracted references · cited by 1 Pith paper

[1]

Bennett , title =

Charles H. Bennett , title =. IBM Journal of Research and Development , volume =
[2]

Quantum Amplitude Amplification and Estimation , booktitle =

Gilles Brassard and Peter H. Quantum Amplitude Amplification and Estimation , booktitle =. 2002 , note =

2002
[3]

Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages =

Soham Chatterjee and Prahladh Harsha and Mrinal Kumar , title =. Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages =. 2026 , doi =

2026
[4]

The Quantum Decoding Problem , booktitle =

Andr. The Quantum Decoding Problem , booktitle =. 2024 , doi =

2024
[5]

Quantum Advantage from Soft Decoders , booktitle =

Andr. Quantum Advantage from Soft Decoders , booktitle =. 2025 , doi =

2025
[6]

2025 , eprint =

Andr. 2025 , eprint =

2025
[7]

IEEE Transactions on Information Theory , volume =

Venkatesan Guruswami and Madhu Sudan , title =. IEEE Transactions on Information Theory , volume =. 1999 , doi =

1999
[8]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science , pages =

Lisa Hales and Sean Hallgren , title =. Proceedings of the 41st Annual Symposium on Foundations of Computer Science , pages =
[9]

2026 , eprint =

Shuji Horinaga and Takashi Yamakawa , title =. 2026 , eprint =

2026
[10]

Jordan and Noah Shutty and Mary Wootters and Adam Zalcman and Alexander Schmidhuber and Robbie King and Sergei V

Stephen P. Jordan and Noah Shutty and Mary Wootters and Adam Zalcman and Alexander Schmidhuber and Robbie King and Sergei V. Isakov and Tanuj Khattar and Ryan Babbush , title =. Nature , volume =. 2025 , doi =

2025
[11]

Jordan , title =

Tanuj Khattar and Noah Shutty and Craig Gidney and Adam Zalcman and Noureldin Yosri and Dmitri Maslov and Ryan Babbush and Stephen P. Jordan , title =. 2025 , eprint =

2025
[12]

Journal of the ACM , volume =

Oded Regev , title =. Journal of the ACM , volume =. 2009 , doi =

2009
[13]

2026 , eprint =

Ansis Rosmanis , title =. 2026 , eprint =

2026
[14]

2026 , eprint =

Yihang Sun and Mary Wootters , title =. 2026 , eprint =

2026
[15]

Journal of the ACM , volume =

Takashi Yamakawa and Mark Zhandry , title =. Journal of the ACM , volume =. 2024 , doi =

2024

[1] [1]

Bennett , title =

Charles H. Bennett , title =. IBM Journal of Research and Development , volume =

[2] [2]

Quantum Amplitude Amplification and Estimation , booktitle =

Gilles Brassard and Peter H. Quantum Amplitude Amplification and Estimation , booktitle =. 2002 , note =

2002

[3] [3]

Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages =

Soham Chatterjee and Prahladh Harsha and Mrinal Kumar , title =. Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages =. 2026 , doi =

2026

[4] [4]

The Quantum Decoding Problem , booktitle =

Andr. The Quantum Decoding Problem , booktitle =. 2024 , doi =

2024

[5] [5]

Quantum Advantage from Soft Decoders , booktitle =

Andr. Quantum Advantage from Soft Decoders , booktitle =. 2025 , doi =

2025

[6] [6]

2025 , eprint =

Andr. 2025 , eprint =

2025

[7] [7]

IEEE Transactions on Information Theory , volume =

Venkatesan Guruswami and Madhu Sudan , title =. IEEE Transactions on Information Theory , volume =. 1999 , doi =

1999

[8] [8]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science , pages =

Lisa Hales and Sean Hallgren , title =. Proceedings of the 41st Annual Symposium on Foundations of Computer Science , pages =

[9] [9]

2026 , eprint =

Shuji Horinaga and Takashi Yamakawa , title =. 2026 , eprint =

2026

[10] [10]

Jordan and Noah Shutty and Mary Wootters and Adam Zalcman and Alexander Schmidhuber and Robbie King and Sergei V

Stephen P. Jordan and Noah Shutty and Mary Wootters and Adam Zalcman and Alexander Schmidhuber and Robbie King and Sergei V. Isakov and Tanuj Khattar and Ryan Babbush , title =. Nature , volume =. 2025 , doi =

2025

[11] [11]

Jordan , title =

Tanuj Khattar and Noah Shutty and Craig Gidney and Adam Zalcman and Noureldin Yosri and Dmitri Maslov and Ryan Babbush and Stephen P. Jordan , title =. 2025 , eprint =

2025

[12] [12]

Journal of the ACM , volume =

Oded Regev , title =. Journal of the ACM , volume =. 2009 , doi =

2009

[13] [13]

2026 , eprint =

Ansis Rosmanis , title =. 2026 , eprint =

2026

[14] [14]

2026 , eprint =

Yihang Sun and Mary Wootters , title =. 2026 , eprint =

2026

[15] [15]

Journal of the ACM , volume =

Takashi Yamakawa and Mark Zhandry , title =. Journal of the ACM , volume =. 2024 , doi =

2024