2026/07/17 by Sunghyeon Jo · 1 citation
#quant-ph #cs.IT #math.IT
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 Pu gives a strict worst-case improvement from limiting rate 0.6225 onward and asymptotically perfect solutions from rate 0.7496 onward, and asked whether Pu 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 Pu. The ideal circuit samples Pu 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<1 admits a strict worst-case improvement over the DQI semicircle value, and every limiting rate r≥ 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.