arXiv:2609.31484
COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry
Gretchen L. Matthews, Julia Shapiro
Abstract
In 2025, Jordan et al. introduced Decoded Quantum Interferometry (DQI), a quantum algorithm for combinatorial optimization based on decoding. They considered Reed-Solomon decoding and its associated optimization problem, called Optimal Polynomial Intersection (OPI), which may be viewed as a polynomial regression problem over a finite field. DQI exhibits provable speedups on certain problem instances and establishes a connection between decoding problems and optimization tasks. Leveraging the well-understood dual structure and decoding theory of algebraic geometry codes from other curve families, we introduce COFI: Curve-based Optimal Function Intersection. By considering two-point Hermitian codes, Suzuki codes, and extended norm-trace codes, we broaden the range of algebraic geometry codes used in DQI and identify families that offer further improvements over one-point Hermitian codes in the Hermitian Optimal Polynomial Intersection framework considered by Jordan and Gu. Depending on the family and parameter regime, these curves can reduce quantum resource requirements or increase the number of constraints that can be considered.
AI Summary
Decoded Quantum Interferometry (DQI) connects structured finite-field optimization to decoding a dual classical code. This paper asks how replacing Reed–Solomon and one-point Hermitian codes with other algebraic-geometry codes changes its optimization guarantees and alphabet requirements. It defines Curve-based Optimal Function Intersection (COFI): choose $f\in\mathcal L(G)$ on a curve to maximize the number of evaluation constraints $f(P_i)\in F_i$ satisfied. This includes multipoint divisors and rational functions with prescribed poles. For a genus-$g$ curve and $2g-2<\deg G<n$, the dual designed-distance bound guarantees a decoding parameter $L=\lfloor(\deg G-2g+1)/2\rfloor$. Substitution into the existing DQI satisfaction law gives the nonsaturated bound $s/n\geq(\sqrt{(L/n)(1-r/q)}+\sqrt{(r/q)(1-L/n)})^2$. The construction combines standard AG-code duality and unique-decoding algorithms with the existing DQI procedure. Specializations cover Suzuki, extended norm–trace, and two-point Hermitian codes. At equal length, Suzuki codes use approximately $\tfrac12\log_2 n$ qubits per field element, versus $\tfrac23\log_2 n$ for Hermitian codes. Conditional divisor-degree comparisons yield larger satisfaction bounds; one two-point example increases the guaranteed decoding radius from $17$ at length $512$ to $18$ at length $511$. The analysis requires efficient coherent unique decoding through the chosen radius; exact-distance-based claims assume decoding to that radius. Comparisons depend on parameter choices and sometimes change alphabet, length, or divisor degree. Resource comparisons concern field-element representation rather than full circuit costs. Incorporating list decoding is explicitly left open.
Central claim may not hold: The main COFI theorem's finite-instance satisfaction lower bound is false: for degree-at-most-two polynomial evaluations at all four affine points over F_4 with two allowed values per point, every permitted degree-one amplification state has expected satisfaction at most 3/4, while the theorem guarantees approximately 0.933013.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.