Algebraic Geometry Codes and Decoded Quantum Interferometry

Decoded Quantum Interferometry (DQI) defines a duality that pairs optimization
problems with optimization problems. The original work on DQI considered Reed-
Solomon decoding, whose dual optimization problem, called Optimal Polynomial In-
tersection (OPI), is a polynomial regression problem over a finite field. Here, we
consider a class of algebraic geometry codes called Hermitian codes. We show that the
dual optimization problem, which we call Hermitian Optimal Polynomial Intersection
(HOPI), is a polynomial regression problem over a Hermitian curve. Because the dual
to a Hermitian code is another Hermitian code, the HOPI problem can also be viewed
as approximate list recovery for Hermitian codes. By comparing to Prange’s algorithm,
simulated annealing, and algebraic list recovery algorithms, we find a large parameter
regime in which DQI efficiently achieves a better approximation than these classical
algorithms. Our findings suggest that the apparent quantum speedup offered by DQI
on the OPI problem may be a special case of a broader quantum speedup for a more
general class of problems regarding polynomial regression on algebraic varieties.