CS Paper Radar

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

Gretchen L. Matthews, Julia Shapiro

cs.IT quant-ph ·submitted 2026-09-25 16:26 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

A provable quantum advantage for approximate optimization via decoded quantum interferometry

cs.CC quant-phcs.DS ·2026-10-01 ·Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones, Jens Eisert, Franz J. Schreiber
similarity 0.75
Abstract · 59 pages, 3 figures

Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate $0.3$, DQI achieves expected scores of approximately $0.85$. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.

0.47

Exponential quantum advantages for decoded quantum interferometry in the streaming setting

cs.CC quant-phcs.DS ·2026-10-01 ·Kewen Wu, Guangxu Yang
theoryhot direction similarity 0.69
Abstract

Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Besides time, space is another central resource: storing and manipulating a massive input can be very challenging, especially when logical qubits carry substantial fault-tolerant implementation overhead. This motivates the following question: does DQI yield quantum advantages in memory, and can we prove it unconditionally? We give an affirmative answer to this question in the streaming setting. In particular, we consider a natural generalization of OPI using Hermite interpolation and Hasse derivatives, which asks for a low-degree polynomial satisfying as many constraints on its values and derivatives as possible. As a concrete example, we show [Quantum efficiency.] An adaptation of the DQI algorithm produces a polynomial satisfying $93\%$ of the constraints; moreover, it only reads the input stream in one pass, uses polylogarithmic space, and has polylogarithmic computation time per stream entry. [Classical hardness.] Any classical algorithm that produces an answer satisfying just $76\%$ of the constraints requires polynomial space, even if it can read the input stream with polynomially many passes and can use unlimited time. Our result provides a complete tradeoff curve for the tunable parameters, and implies that DQI has provable quantum advantages for the original OPI problem.

0.51

Plotkin-optimal pure quantum LRCs with large minimum distances from NMDS codes

cs.IT ·2026-11-03 ·Yang Li, Shitao Li, Gaojun Luo, San Ling
similarity 0.63
Abstract

Quantum locally recoverable codes (qLRCs) are a class of quantum error-correcting codes that can recover an erased qudit by accessing only a few other qudits. This paper develops a general framework for constructing optimal pure qLRCs that attain the Plotkin-like bound, referred to as Plotkin-optimal pure qLRCs, from Hermitian dual-containing near maximum-distance separable (NMDS) codes. Focusing on a special class of NMDS codes called extended subcodes of generalized Reed-Solomon (ESGRS) codes, we determine their localities by analyzing certain subset sum problems over finite fields. By further exploiting the algebraic structures of ESGRS codes and related codes, we construct four families of Plotkin-optimal pure qLRCs with large lengths and more flexible minimum distances than existing constructions. These constructions provide strong global error-correction capability while retaining local recovery. To the best of our knowledge, they give the first families of qLRCs attaining the pure Plotkin-like bound. In addition, by using the resulting locality property, we resolve in the negative a related problem on ESGRS codes supporting combinatorial designs.

0.12

Exponential quantum space advantage in random data streams

cs.CC quant-ph ·2026-10-02 ·Adam Bouland, Matthew Ding, Siddhartha Jain
theory similarity 0.62
Abstract · 27+3 pages. v2: fixed minor typos and added concurrent work statement

We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa-Zhandry Code Intersection problem admits exponential quantum advantage in the streaming model when its inputs are streamed in random order. This means quantum computers exhibit exponential space advantage even when simply receiving $(x,f(x))$ pairs for a uniformly random function $f$ in a uniformly random order. Notably, our classical space lower bound does not follow from a communication lower bound. Instead, we utilize density-restoring partitions from communication complexity directly with potential-function analysis in the style used to prove memory-sample tradeoffs for learning. The resulting argument is distinct from both lines of work. Second, we use our framework to show quantum space advantage for the Optimal Polynomial Intersection (OPI) problem in certain regimes via a streaming version of the Decoded Quantum Interferometry algorithm. In particular, we show that for degree $d$ and $n$ evaluation points, attaining $1/2 + Ω(\sqrt{d/n})$ fraction of satisfied OPI constraints via streaming requires $Ω(n)$ classical bits of memory but only $O(d\log n)$ qubits. This yields provable quantum advantage in a "low-rate" regime when the number of evaluation points is much larger than the degree, with a space advantage that can be as large as exponential in certain parameter settings.

0.48

Optimal Pure Quantum $(r,δ)$-LRCs from Euclidean and Hermitian Dual-Containing Cyclic Codes

cs.IT ·2026-09-18 ·Astha Agrawal, Shayan Srinivasa Garani
similarity 0.62
Abstract · 29 pages, 4 tables

Locally recoverable codes (LRCs) combine global error correction with the ability to repair a small number of erased coordinates by accessing only a limited number of other coordinates. Motivated by their quantum counterparts, we construct several families of optimal cyclic $(r,δ)$-LRCs that are Euclidean or Hermitian dual-containing. In the Euclidean case, we obtain four families of optimal dual-containing cyclic $(r,δ)$-LRCs over $\mathbb{F}_q$ with a range of minimum distances extending beyond the local distance $δ$. In the Hermitian case, we derive analogous families over $\mathbb{F}_{q^2}$ that are Hermitian dual-containing, when $(r+δ-1)\mid(q^2-1)$. In addition, we develop a distinct construction for the case $(r+δ-1)\mid(q^2+1)$ using symmetric defining sets and odd $δ$, which yields optimal codes with minimum distances $\ell+2$, $δ+2$, $2δ-2$, and $2δ$. The Euclidean Calderbank-Shor-Steane (CSS) and Hermitian stabilizer constructions then give corresponding quantum cyclic $(r,δ)$-LRCs over~$\mathbb{F}_q$. Further, the resulting stabilizer codes are pure; they meet the relevant quantum Singleton-type bound, and are therefore \textit{optimal}. We also provide a comparison with previous works, highlighting the parameter regimes and minimum distance ranges covered by our results that are not attained by existing constructions. Explicit examples illustrate the constructions and verify the dual-containment and purity conditions.

0.38

Weighted Quantum Signal Processing: Low-Depth Polynomial Approximation with Applications to Kolmogorov-Arnold Networks

cs.CC quant-phcs.LG ·2026-09-18 ·Rohit Sarma Sarkar, Rupayan Bhattacharjee, Elias F. Combarro, Michele Grossi, Lirandë Pira +3 more
similarity 0.61
Abstract

Quantum Signal Processing is a powerful quantum framework for generating and approximating univariate polynomials. However, QSP is often limited by circuit-depth bottlenecks and parity constraints on the class of realizable polynomials. In this work, we introduce Weighted Quantum Signal Processing, an extension of QSP in which a weight function is assigned to the central rotation operator. This formulation provides a deeper understanding of QSP, which emerges as the special case of WQSP with unit weights. The choice of weights determines the structure and expressive capabilities of WQSP circuits. When the weights are natural numbers greater than one, WQSP reduces to a pruned version of QSP, revealing parameter redundancies in the standard framework. Through appropriate selection of integer weights, WQSP achieves linear-to-exponential reductions in the number of parameters required to realize arbitrary bounded univariate polynomials while preserving approximation quality. For generic weights, we establish corresponding approximation error bounds and show that, in many cases, the approximation is exact. We analyze WQSP from both a deterministic perspective, where polynomial generation is formulated as the solution of a linear system, and a quantum machine learning perspective, where WQSP serves as a structured and expressive quantum learning model. We further employ this learning framework to parameterize learnable activation functions in Kolmogorov--Arnold Networks for multivariate function approximation. Our results show that WQSP provides a compact, flexible, and theoretically grounded framework for realizing arbitrary univariate polynomials while requiring significantly fewer trainable parameters than conventional QSP. This yields expressive and parameter-efficient neural architectures, highlighting the potential of WQSP as a scalable primitive for quantum-enhanced machine learning.

0.11

The Intrinsic Cost of Quantum Syndrome Extraction

cs.IT quant-ph ·2026-09-30 ·Chia-Tung Chu
similarity 0.59
Abstract · 70 pages, 2 figures, 5 tables. Revised exposition and references; expanded worked examples

How much time is fundamentally required to extract the syndrome of a stabilizer code on hardware with a given connectivity graph? Previous bounds answer through a chosen list of checks (Delfosse, Beverland, and Tremblay, 2021) or through the global code parameters (Baspin, Fawzi, and Shayeghi, 2023). Here, we show that neither determines the interaction that a particular hardware cut requires. We therefore define the intrinsic cut cost, $χ$, directly from the stabilizer group, independent of the generating set used to describe the code. It is computable from the check matrix alone, and equals the mutual information across the cut in the maximally mixed code state. We show that every exact extraction circuit, however adaptive, needs at least $χ/2$ two-qubit operations across the cut, and alternatively with free local processing exactly $χ$ shared Bell pairs. Guided by this intrinsic cut cost, we construct annular surface codes with constant-depth local extraction that give a counterexample to Corollary 1 of Delfosse, Beverland, and Tremblay. Furthermore, for a fixed quantum Tanner family, $χ$ grows at least linearly with the size of every sufficiently small region, giving a depth guarantee at each corresponding bottleneck in every layout. This strengthens the global perspective of Baspin, Fawzi, and Shayeghi and, together with our matching square-grid construction, yields a tight space--depth tradeoff. Our results connect the interaction required by syndrome extraction to hardware communication capacity and thus provide a way to assess unavoidable circuit costs before committing to a particular layout.

0.30

Quantum MDS codes from complements of unions of finite-field subsets

cs.IT math-phmath.QA ·2026-09-09 ·Naihong Hu, Hong Ji
similarity 0.59
Abstract · 37 pages

Let $q$ be an odd prime power. We use complements of unions of subsets of $\mathbb F_{q^2}$ as locator sets and establish a sufficient condition under which a generalized Reed--Solomon (GRS) code is Hermitian self-orthogonal. Using cosets of multiplicative subgroups and sets with prescribed trace or norm values, we construct five families of Hermitian self-orthogonal GRS codes over $\mathbb F_{q^2}$. The Hermitian construction then yields five corresponding families of $q$-ary quantum maximum-distance-separable (MDS) codes. Under suitable parameter conditions, these quantum codes have minimum distances greater than $q/2+1$. By comparing codes of the same length, we give conditions under which our codes have strictly larger minimum distances than those obtainable from several previously known constructions based on trace maps, linear transformations, and cosets of multiplicative subgroups, either directly or via the propagation rule. We further show that such improvements occur for infinitely many values of $q$.

0.22