COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry

1. Introduction

• The paper studies finite-field max-LINSAT, which seeks assignments satisfying as many linear constraints as possible, in the context of DQI’s decoding-based approach to structured optimization.DQI connects optimization to decoding problems for related classical error-correcting codes.Source: §1 · pp. 1–3
• COFI generalizes OPI and HOPI by optimizing agreement over rational functions on curves, including functions in Riemann–Roch spaces without polynomial representations.For some curve families the functions can be expressed as multivariate polynomials; the framework is not restricted to that case.Source: §1 · p. 3
• The paper introduces general DQI satisfaction-fraction formulas for algebraic-geometry codes and focuses on explicit curves with many rational evaluation points because these determine constraint counts.Source: §1 · p. 4
• Suzuki, extended norm–trace, and two-point Hermitian codes can exceed one-point Hermitian satisfaction fractions under suitable divisor-degree conditions.Two-point Hermitian codes yield a strictly larger expected fraction in the nonsaturated regime; if both comparisons are saturated, both fractions equal 1.Source: §1 · p. 4
• Suzuki codes can improve satisfaction fractions while requiring fewer qubits than comparable-length Hermitian codes; Suzuki codes also use fewer qubits per field element than same-length Reed–Solomon codes.Source: §1 · pp. 3–4

Organization.

• The paper is organized into background on codes, general DQI results, code-family comparisons, and a conclusion.Source: Organization · p. 4

2.1. Linear Codes.

• A linear code is a subspace of Fq^n with length, dimension, and minimum distance parameters, and its dual is another code over the same field.The Singleton bound gives k + d ≤ n + 1 for an [n, k, d] code.Source: §2.1 · pp. 4–5

2.2. Algebraic Geometry Codes.

• Algebraic-geometry codes evaluate functions from a curve’s Riemann–Roch space at rational points, with code parameters determined by the evaluation set and divisor.Their duals remain algebraic-geometry codes from the same curve; Reed–Solomon codes have length at most q, while one-point Hermitian codes have length q^3.Source: §2.2 · pp. 6–7
• COFI’s curve-function setting includes the OPI and HOPI cases while allowing Riemann–Roch functions beyond polynomial representations.The cited discussion also identifies HOPI with an approximate list-recovery interpretation.Source: §2.2 · p. 7

2.3. Max-LINSAT and DQI.

• Max-LINSAT maximizes satisfied constraints, equivalently minimizing the Hamming weight of the residual vector in its nearest-neighbor decoding view.When each acceptable set is a singleton, this is the problem of maximizing satisfied equations in a linear system.Source: §2.3 · p. 8
• DQI weights assignments through a polynomial of the objective, then uses syndrome decoding in the dual code to prepare a state biased toward high-scoring solutions.The polynomial degree is limited by the dual code’s decoding radius, and the final measurement samples satisfy the semicircle law.Source: §2.3 · pp. 9–10

3. DQI with Codes from Curves

• COFI seeks a function in L(G) whose evaluations satisfy the maximum number of coordinatewise constraints, encompassing OPI and HOPI while allowing rational functions and multipoint divisors.Unlike the polynomial representations in OPI and HOPI, elements of L(G) may have prescribed poles at points in supp(G).Source: §3 · p. 11
• Under 2g − 2 < deg(G) < n and efficient decoding up to ℓ errors, Theorem 3.2 bounds DQI’s expected satisfaction fraction for COFI instances with n constraints and constraint sets of size r.The bound uses the dual code’s minimum distance; a self-dual AG code permits evaluating it using the self-dual specialization in Corollary 3.3.Source: §3 · p. 12
• For the dual of a one-point Suzuki code on Sq over Fq with G = αP∞ and minimum distance d⊥, Corollary 3.4 says DQI produces solutions with an expected fraction of satisfied constraints.Source: §3 · p. 13
• Corollary 3.5 gives an expected satisfaction-fraction bound for extended norm–trace codes, while t = 2 and u = q + 1 recovers the Hermitian-curve result [10, Theorem 1].For the recovered one-point Hermitian case, s/n is an equality because exact minimum distances are known.Source: §3 · p. 14
• For two-point Hermitian codes with n = q^3 − 1, Corollary 3.6 gives a DQI expected satisfaction-fraction bound based on the dual code’s minimum distance.Source: §3 · pp. 14–15

3.1. Examples.

• The examples formulate COFI as max-LINSAT for a Suzuki code with parameters [64, 10, ≥42] and a two-point Hermitian instance whose L(G) includes nonpolynomial rational functions.The Hermitian example has dim(C) = 62 and dual-code parameters [511, 449, ≥38]; the section also reports satisfaction-fraction advantages for Suzuki and extended norm–trace codes without exposing table values here.Source: §3.1 · pp. 15–18
• For extended norm–trace codes, the DQI decoding step uses the dual code C⊥ = C_L(D, γP∞), with γ denoting its pole order.The passage specifies that γ refers directly to the one-point extended norm–trace code being decoded.Source: §3.1 · p. 19
• For q = 8, t = 3, and r = 256 (r/8^3 = 1/2), the lower bound s/n > 0.933 holds for a broad range of pole orders, up to γ/n < 1/2; Table 2 illustrates u = 1 and u = 73.Source: §3.1 · pp. 19–20

4.1. Comparisons across Families of Curves.

• For fixed ρ in the nonsaturated regime, extended norm–trace COFI has a strictly larger satisfaction fraction than Hermitian HOPI; when both are saturated, both fractions equal 1.Source: §4.1 · p. 20
• At equal block length and matched constraint density, Suzuki codes yield a strictly larger guaranteed expected satisfaction fraction than one-point Hermitian codes.The comparison is stated for the hypotheses of Proposition 4.3.Source: §4.1 · pp. 21, 23
• A two-point Hermitian code can yield a strictly larger expected DQI satisfaction fraction than a one-point Hermitian code of the same dimension fraction.The example reports relative decoding radii of at least 18/511 ≈ 0.03523 versus 17/512 ≈ 0.03320.Source: §4.1 · p. 24

4.2. Comparisons of DQI and Prange’s Algorithm.

• Figure 1 compares Suzuki-code DQI with Prange in the balanced case r = q/2 = 4 over F8, plotting satisfaction fraction and the DQI–Prange advantage.Source: Figure 1 · p. 25

• Extended norm–trace, Suzuki, and a family of two-point Hermitian codes outperform one-point Hermitian codes in expected satisfaction fraction under suitable divisor-degree assumptions.Source: §5 · p. 26
• The authors identify comparisons across broader code families and incorporating algebraic-geometry list decoding as directions for future work.They note that list decoding could potentially allow larger decoding radii and improve optimization guarantees.Source: §5 · p. 26