COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry
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.
Related
- Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
- Bias-Corrected Subspace Intersection: Minimax-Optimal Shared Subspace Estimation in Multi-View Data
- Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
- Optimal score function estimation via derivatives constraints
- C1 Virtual Element Methods for the Optimal Control of Oseen Equations with Stream-Function Formulation
BibTeX
@misc{matthews2026cofidqi,
title = {{COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry}},
author = {Gretchen L. Matthews and Julia Shapiro},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31484},
eprint = {2609.31484},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31484},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry
AU - Gretchen L. Matthews
AU - Julia Shapiro
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31484
UR - https://arxiv.org/abs/2609.31484
AB - 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.
ER -