Algebraic Geometry Codes and Decoded Quantum Interferometry

• URL: http://arxiv.org/abs/2510.06603v1
• Date: Wed, 08 Oct 2025 03:25:30 GMT
• Title: Algebraic Geometry Codes and Decoded Quantum Interferometry
• Abstract summary: Decoded Quantum Interferometry (DQI) defines a duality that pairs decoding problems with optimization problems.<n>We show that HOPI is a regression problem over a Hermitian curve, and because the dual to a Hermitian code is another Hermitian code, HOPI problem can also be viewed as approximate list recovery for Hermitian codes.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decoded Quantum Interferometry (DQI) defines a duality that pairs decoding problems with optimization problems. The original work on DQI considered Reed-Solomon decoding, whose dual optimization problem, called Optimal Polynomial Intersection (OPI), is a polynomial regression problem over a finite field. Here, we consider a class of algebraic geometry codes called Hermitian codes, which achieve block length $q^3$ using alphabet $\mathbb{F}_{q^2}$ compared to Reed-Solomon's limitation to block length $q$ over $\mathbb{F}_q$, requiring approximately one-third fewer qubits per field element for quantum implementations. We show that the dual optimization problem, which we call Hermitian Optimal Polynomial Intersection (HOPI), is a polynomial regression problem over a Hermitian curve, and 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, suggesting that the apparent quantum speedup offered by DQI extends beyond Reed-Solomon codes to a broader class of polynomial regression problems on algebraic varieties.

Related papers

• Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry [6.7936678022428225]
  The Optimal Polynomial Intersection (OPI) problem asks us to find a low-degree over a finite field whose values lie in prescribed subsets on as many given inputs as possible.<n>As a byproduct, we also improve the existential bound of Sun and Wootters in certain parameter regimes.<n>Our results extend to the Max-LINSAT problem with respect to arbitrary distance separable (MDS) codes.
  arXiv  Detail & Related papers  (2026-07-16T07:18:57Z)
• Multivariate Decoded Quantum Interferometry for Weighted Optimization [6.4675604105664]
  Quantum Interferometry (DQI) reduces discrete optimization to decoding with potential advantages over the best-known analogue-time classical algorithms for certain Max-LINSAT problems.<n>In its original formulation, DQI treats all constraints uniformly and cannot exploit the weight structure present in most optimization problems of interest.
  arXiv  Detail & Related papers  (2026-05-11T14:45:46Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem [0.0]
  Recently, Jordan et al. introduced a novel quantum-algorithmic technique called Decoded Quantum Interferometry (DQI)<n>They presented a constraint-satisfaction problem called Optimal Polynomial Intersection (OPI) and showed that a DQI algorithm running in time can satisfy a larger fraction of constraints than any known-time classical algorithm.<n>We show how these improvements result in a nearly linear-time DQI algorithm for the OPI problem.
  arXiv  Detail & Related papers  (2026-01-21T16:48:05Z)
• Verifiable Quantum Advantage via Optimized DQI Circuits [2.149968465453488]
  Decoded Quantum Interferometry (DQI) provides a framework for superpolynomial quantum speedups.<n>We apply DQI to the Optimal Polynomial Intersection (OPI) problem, whose code is Reed-Solomon (RS)<n>We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal speedup.
  arXiv  Detail & Related papers  (2025-10-13T03:19:28Z)
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [77.76727425995186]
  Solving variational inequalities (SVIs) is a foundational problem at the heart of optimization.<n>Most research has focused on carving out specific subclasses that elude those intractability barriers.
  arXiv  Detail & Related papers  (2025-04-04T13:24:41Z)
• Quantum advantage from soft decoders [0.7728149002473877]
  We provide improvements for some instantiations of the Optimal Polynomial Interpolation (OPI) problem. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. In order to be able to use a decoder in the setting of Regev's reduction, we provide a novel reduction from a syndrome to a coset sampling problem.
  arXiv  Detail & Related papers  (2024-11-19T15:12:03Z)
• Optimization by Decoded Quantum Interferometry [42.169154389732036]
  We introduce a quantum algorithm called Decoded Quantum Interferometry (DQI)<n>For approximating to data over finite fields, DQI achieves a better approximation ratio than any time known to us.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum message-passing algorithm for optimal and efficient decoding [2.3020018305241328]
  We expand the understanding, formalism, and applicability of the BPQM algorithm. We provide the first formal description of the BPQM algorithm in full detail and without any ambiguity. We show some promising numerical results that indicate that BPQM on factor graphs with cycles can significantly outperform the best possible classical decoder.
  arXiv  Detail & Related papers  (2021-09-16T18:01:12Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [47.81107898315438]
  We develop a method for finding hard families of examples for a wide class of problems by using duality LP. We show that the $L1$-regression is essentially best possible, and therefore that the computational difficulty of learning a concept class is closely related to the degree required to approximate any function from the class in $L1$-norm.
  arXiv  Detail & Related papers  (2021-02-08T18:06:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.