Quantum algorithm improves polynomial intersection using curve codes
COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry
Information Theory
Summary
Finding where two mathematical functions intersect can be a tricky problem, especially in cases involving many constraints. Jordan and colleagues created a quantum algorithm called Decoded Quantum Interferometry (DQI) to speed up solving such problems. This paper introduces COFI, which expands the kinds of algebraic curves used in DQI, making it easier or more efficient to solve these intersection problems in some cases. The new approach can reduce the quantum computing effort needed or handle more complex constraints.
What this means in practice
- •For quantum software developers: Optimize quantum algorithms for decoding problems by using curve-based codes to reduce resource requirements or increase constraints handled.
- •For coding theory engineers: Design improved error-correcting codes informed by quantum algorithmic insights from new families of algebraic geometry codes.
Authors
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.