Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.00502

Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability

Seyoon Ragavan, Noah Shutty

quant-phSubmitted Sep 30, 2026• Announced Oct 2, 2026• 0 citations• Revised Oct 2, 2026 (v2)
v1 · Sep 30, 2026v2 · Oct 2, 2026
arXivHTMLPDF

Abstract

Regev's reduction quantumly finds codewords satisfying nonlinear constraints by decoding the dual code. To date, applications that have not been dequantized have relied on efficient classical decoders and coordinate-wise constraints. We overcome these restrictions separately. Our first contribution uses a quantum decoder to find solutions $\mathbf{y}\in(\mathbb{F}_q\setminus\{0\})^m$ to $\mathbf{B}\mathbf{y}=0$, where $\mathbf{B}\in\mathbb{F}_q^{n\times m}$. For fixed prime $q>2$, Chen, Liu, and Zhandry solve this problem for random matrices with $m=Ω(n^2)$, a regime now covered by classical algorithms. We adapt their template to codes (spanned by the rows of $\mathbf{B}$) that satisfy a "two-fold multiplication property": the coordinate-wise products of pairs of codewords span a space of dimension smaller than $m$. Under suitable distance conditions, this allows us to solve instances with $m\leq n^{2-Ω(1)}$, beyond the established guarantees of classical algorithms. We also give an efficient classical algorithm under a stronger three-fold multiplication property, leaving intermediate regimes as candidates for quantum advantage. For Reed-Muller codes punctured at random points, our algorithm finds a word in the unpunctured dual code supported exactly on those points. This works beyond known efficient classical decoding regimes. Our second contribution retains classical decoding but allows global constraints on symbol frequencies. We study "histogram-local" constraints, which specify the allowed numbers of occurrences of each symbol. For broad families, stability under resampling one coordinate yields efficient quantum algorithms for variants of optimal polynomial intersection (OPI) combining coordinate-wise and histogram-local constraints. Adapting Yamakawa-Zhandry, we prove a quantum-classical separation for these problems relative to a classical random oracle.

Related papers

OPI x Soft Decoders

André Chailloux

In recent years, a particularly interesting line of research has focused on designing quantum algorithms for code and lattice problems inspired by Regev's reduction. The core idea is to use a decoder for a given code to find short codewords in its dual. For example, Jordan et al. demonstrated how structured codes can be used in this framework to exhibit some quantum advantage. In particular, they showed how the classical decodability of Reed-Solomon codes can be leveraged to solve the Optimal Polynomial Intersection (OPI) problem quantumly. This approach was further improved by Chailloux and Tillich using stronger soft decoders, though their analysis was restricted to a specific setting of OPI. In this work, we reconcile these two approaches. We build on a recent formulation of the reduction by Chailloux and Hermouet in the lattice-based setting, which we rewrite in the language of codes. With this reduction, we show that the results of Jordan et al. can be recovered under Bernoulli noise models, simplifying the analysis. This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework, yielding improved algorithms.

quant-pharXiv:2511.22691•Nov 28, 2025•0 citations

A provable quantum advantage for approximate optimization via decoded quantum interferometry

Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones +2 more

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.

quant-pharXiv:2610.02145•Oct 2, 2026•0 citations

Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry

Shuji Horinaga, Takashi Yamakawa

The Optimal Polynomial Intersection (OPI) problem asks us to find a low-degree polynomial over a finite field whose values lie in prescribed subsets on as many given inputs as possible. Decoded quantum interferometry (DQI) gives a quantum algorithm for OPI in parameter regimes beyond those achieved by the best known classical heuristics. Follow-up works improve the parameter regimes, but their analyses are limited to average-case settings. Recently, Sun and Wootters showed that, even in the worst case, OPI has a solution in a larger parameter regime than the one covered by DQI. However, they left open whether one can design a quantum algorithm that solves OPI in the worst-case beyond the DQI regime. We give such a quantum algorithm. As a byproduct, we also improve the existential bound of Sun and Wootters in certain parameter regimes. In particular, when each subset contains roughly half of the field elements, our algorithm finds a solution with satisfaction rate $s=1$ whenever the rate satisfies $R>0.75$. This matches the previous average-case bound, whereas DQI cannot achieve $s=1$ unless $R=1$. Our existential bound guarantees the existence of a solution when $R> 0.7158$, improving over the previous threshold $R>0.7495$. More generally, our existential results extend to the Max-LINSAT problem with respect to arbitrary maximum distance separable (MDS) codes. The corresponding algorithmic results apply only to MDS codes whose dual admits an efficient list decoder. Our results are obtained through a novel application of a Brascamp--Lieb-type inequality in the MDS setting, which may have further applications.

quant-pharXiv:2607.14650•Jul 17, 2026•0 citations

OPI × Soft Decoders

André Chailloux

In recent years, a particularly interesting line of research has focused on designing quantum algorithms for code and lattice problems inspired by Regev's reduction. The core idea is to use a decoder for a given code to find short codewords in its dual. For example, Jordan et al. [JSW + 24] demonstrated how structured codes can be used in this framework to exhibit some quantum advantage. In particular, they showed how the classical decodability of Reed-Solomon codes can be leveraged to solve the Optimal Polynomial Intersection (OPI) problem quantumly. This approach was further improved by Chailloux and Tillich [CT25] using stronger soft decoders, though their analysis was restricted to a specific setting of OPI. In this work, we reconcile these two approaches. We build on a recent formulation of the reduction by Chailloux and Hermouet [CH25] in the lattice-based setting, which we rewrite in the language of codes. With this reduction, we show that the results of Jordan et al. can be recovered under Bernoulli noise models, simplifying the analysis. This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework, yielding improved algorithms.

•Dec 1, 2025•0 citations

A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem

Ansis Rosmanis

Recently, Jordan et al. (Nature, 2025) introduced a novel quantum-algorithmic technique called Decoded Quantum Interferometry (DQI) for solving specific combinatorial optimization problems associated with classical codes. They presented a constraint-satisfaction problem called Optimal Polynomial Intersection (OPI) and showed that, for this problem, a DQI algorithm running in polynomial time can satisfy a larger fraction of constraints than any known polynomial-time classical algorithm. In this work, we propose several improvements to the DQI algorithm, including sidestepping the quadratic-time Dicke state preparation. Given random access to the input, we show how these improvements result in a nearly linear-time DQI algorithm for the OPI problem. Concurrently and independently with this work, Khattar et al. (arXiv:2510:10967) also construct a nearly linear-time DQI algorithm for OPI using slightly different techniques.

quant-pharXiv:2601.15171•Jan 22, 2026•0 citations

The Quantum Decoding Problem: Tight Achievability Bounds and Application to Regev's Reduction

Agathe Blanvillain, André Chailloux, Jean–Pierre Tillich

We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry’s work showing a quantum advantage for the Short Integer Solution (SIS) problem for thel∞norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev’s reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev’s reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.

arXiv:2509.24796•IEEE Transactions on Information Theory•May 5, 2026•0 citations
Regev's reduction quantumly finds codewords satisfying nonlinear constraints by decoding the dual code. To date, applications that have not been dequantized have relied on efficient classical decoders and coordinate-wise constraints. We overcome these restrictions separately.
Our first contribution uses a quantum decoder to find solutions y∈(Fq∖{0})m\mathbf{y}\in(\mathbb{F}_q\setminus\{0\})^my∈(Fq​∖{0})m to By=0\mathbf{B}\mathbf{y}=0By=0, where B∈Fqn×m\mathbf{B}\in\mathbb{F}_q^{n\times m}B∈Fqn×m​. For fixed prime q>2q>2q>2, Chen, Liu, and Zhandry solve this problem for random matrices with m=Ω(n2)m=Ω(n^2)m=Ω(n2), a regime now covered by classical algorithms. We adapt their template to codes (spanned by the rows of B\mathbf{B}B) that satisfy a "two-fold multiplication property": the coordinate-wise products of pairs of codewords span a space of dimension smaller than mmm. Under suitable distance conditions, this allows us to solve instances with m≤n2−Ω(1)m\leq n^{2-Ω(1)}m≤n2−Ω(1), beyond the established guarantees of classical algorithms. We also give an efficient classical algorithm under a stronger three-fold multiplication property, leaving intermediate regimes as candidates for quantum advantage. For Reed-Muller codes punctured at random points, our algorithm finds a word in the unpunctured dual code supported exactly on those points. This works beyond known efficient classical decoding regimes.
Our second contribution retains classical decoding but allows global constraints on symbol frequencies. We study "histogram-local" constraints, which specify the allowed numbers of occurrences of each symbol. For broad families, stability under resampling one coordinate yields efficient quantum algorithms for variants of optimal polynomial intersection (OPI) combining coordinate-wise and histogram-local constraints. Adapting Yamakawa-Zhandry, we prove a quantum-classical separation for these problems relative to a classical random oracle.
In recent years, a particularly interesting line of research has focused on designing quantum algorithms for code and lattice problems inspired by Regev's reduction. The core idea is to use a decoder for a given code to find short codewords in its dual. For example, Jordan et al. demonstrated how structured codes can be used in this framework to exhibit some quantum advantage. In particular, they showed how the classical decodability of Reed-Solomon codes can be leveraged to solve the Optimal Polynomial Intersection (OPI) problem quantumly. This approach was further improved by Chailloux and Tillich using stronger soft decoders, though their analysis was restricted to a specific setting of OPI. In this work, we reconcile these two approaches. We build on a recent formulation of the reduction by Chailloux and Hermouet in the lattice-based setting, which we rewrite in the language of codes. With this reduction, we show that the results of Jordan et al. can be recovered under Bernoulli noise models, simplifying the analysis. This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework, yielding improved algorithms.
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.30.30.3, DQI achieves expected scores of approximately 0.850.850.85. In contrast, exceeding the classical threshold of 0.650.650.65 by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.
The Optimal Polynomial Intersection (OPI) problem asks us to find a low-degree polynomial over a finite field whose values lie in prescribed subsets on as many given inputs as possible. Decoded quantum interferometry (DQI) gives a quantum algorithm for OPI in parameter regimes beyond those achieved by the best known classical heuristics. Follow-up works improve the parameter regimes, but their analyses are limited to average-case settings. Recently, Sun and Wootters showed that, even in the worst case, OPI has a solution in a larger parameter regime than the one covered by DQI. However, they left open whether one can design a quantum algorithm that solves OPI in the worst-case beyond the DQI regime. We give such a quantum algorithm. As a byproduct, we also improve the existential bound of Sun and Wootters in certain parameter regimes. In particular, when each subset contains roughly half of the field elements, our algorithm finds a solution with satisfaction rate s=1s=1s=1 whenever the rate satisfies R>0.75R>0.75R>0.75. This matches the previous average-case bound, whereas DQI cannot achieve s=1s=1s=1 unless R=1R=1R=1. Our existential bound guarantees the existence of a solution when R>0.7158R> 0.7158R>0.7158, improving over the previous threshold R>0.7495R>0.7495R>0.7495. More generally, our existential results extend to the Max-LINSAT problem with respect to arbitrary maximum distance separable (MDS) codes. The corresponding algorithmic results apply only to MDS codes whose dual admits an efficient list decoder. Our results are obtained through a novel application of a Brascamp--Lieb-type inequality in the MDS setting, which may have further applications.
In recent years, a particularly interesting line of research has focused on designing quantum algorithms for code and lattice problems inspired by Regev's reduction. The core idea is to use a decoder for a given code to find short codewords in its dual. For example, Jordan et al. [JSW + 24] demonstrated how structured codes can be used in this framework to exhibit some quantum advantage. In particular, they showed how the classical decodability of Reed-Solomon codes can be leveraged to solve the Optimal Polynomial Intersection (OPI) problem quantumly. This approach was further improved by Chailloux and Tillich [CT25] using stronger soft decoders, though their analysis was restricted to a specific setting of OPI. In this work, we reconcile these two approaches. We build on a recent formulation of the reduction by Chailloux and Hermouet [CH25] in the lattice-based setting, which we rewrite in the language of codes. With this reduction, we show that the results of Jordan et al. can be recovered under Bernoulli noise models, simplifying the analysis. This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework, yielding improved algorithms.
Recently, Jordan et al. (Nature, 2025) introduced a novel quantum-algorithmic technique called Decoded Quantum Interferometry (DQI) for solving specific combinatorial optimization problems associated with classical codes. They presented a constraint-satisfaction problem called Optimal Polynomial Intersection (OPI) and showed that, for this problem, a DQI algorithm running in polynomial time can satisfy a larger fraction of constraints than any known polynomial-time classical algorithm. In this work, we propose several improvements to the DQI algorithm, including sidestepping the quadratic-time Dicke state preparation. Given random access to the input, we show how these improvements result in a nearly linear-time DQI algorithm for the OPI problem. Concurrently and independently with this work, Khattar et al. (arXiv:2510:10967) also construct a nearly linear-time DQI algorithm for OPI using slightly different techniques.
We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry’s work showing a quantum advantage for the Short Integer Solution (SIS) problem for thel∞norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev’s reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev’s reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.