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:2609.40036

Cycle Codes and Decoded Quantum Interferometry

Anuj Apte, Shouvanik Chakrabarti, Andi Gu, Stephen P. Jordan, Ojas Parekh, Ruslan Shaydulin, Jacob Watkins, Noureldin Yosri, Adam Zalcman

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Decoded Quantum Interferometry (DQI) reduces optimization problems with two-variable constraints to decoding cycle codes. For one such problem, namely MaxCut, prior work showed that DQI achieves a nontrivial satisfaction fraction guarantee only on linear-girth graphs, for which MaxCut is classically easy. However, these no-go results rely on minimum distance assumptions that do not represent true decodability thresholds for common noise channels, thus underestimating actual DQI performance. To estimate the true performance, we derive DQI satisfaction guarantees in the presence of imperfect decoding for fixed instances and generalize prior results for random instances. We then study homological cycle codes over arbitrary finite fields, and show that minimum-weight decoding is NP-hard for every field of size $q>2$, in contrast with known results for binary cycle codes. On the Linial--Simkin ensemble of regular graphs with logarithmic girth, we prove maximum-likelihood recovery bounds and a strong converse for a family of non-uniform additive noise channels. Moreover, LP decoders provide polynomial-time recovery of a positive fraction of randomly located errors with arbitrary values. These results allow us to prove upper and lower bounds on the approximate optima achievable by DQI when restricted to classical decoders. These bounds rule out quantum advantage in the regimes we analyze but also identify a family of regular Max-$k$-Cut instances on which DQI efficiently achieves a nontrivial satisfaction fraction guarantee.

Comments
27 (main) + 23 (appendices) pages, 2 figures, 2 tables

Related papers

Weighted performance bounds for decoded quantum interferometry with imperfect decoding

Maoxin Gao, Yan Chang, Wei Huang +3 more

Decoded quantum interferometry (DQI) offers an approach to a class of combinatorial optimization problems by reducing quantum state preparation to a decoding task. However, the existing performance bound for imperfect decoding uses the maximum failure rate over error-weight layers to bound the performance loss uniformly, which may overestimate the effect of decoding failures in layers with low probability. Building on the existing analysis, we combine the failure rate of each layer with its probability weight in the chosen state to derive tighter performance lower bounds. For binary linear constraint problems with uniformly random target values, we obtain a finite-size lower bound on the average satisfaction ratio for fixed state parameters and a fixed decoder, and establish its improvement over the existing bound. In part of the parameter region where the existing bound falls to the random-assignment baseline, the weighted bound still provides a guarantee above that baseline. We further extend the analysis to general finite fields under a model of uniformly random translations of allowed sets of equal size. Trials in individual layers using a fixed belief propagation decoder illustrate the size of the improvement and provide confidence guarantees after accounting for sampling uncertainty. These results reveal the role of retaining the correspondence between the failure distribution and the state probabilities, and suggest directions for more refined performance analyses of other DQI constructions.

quant-pharXiv:2604.15025•Apr 17, 2026•0 citations

Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry

Maximilian J. Kramer, Carsten Schubert, Jens Eisert

For general max-k-XORSAT with $k \geq 3$, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless $\mathsf{P} = \mathsf{NP}$: approximating beyond the random-assignment value of $1/2$ is $\mathsf{NP}$-hard. The picture changes when each variable appears in at most $D$ constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order $1/\sqrt{D}$. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields $\mathbb{F}_q$, proving that it is $\mathsf{NP}$-hard to exceed $r/q + \mathcal{O}_{q,r}(1/\sqrt{D})$. These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on $(k,D)$-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic $1/\sqrt{D \log D}$ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the $1/\sqrt{D}$ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.

quant-pharXiv:2606.13570•Jun 12, 2026•0 citations

Discovering New Problems for Decoded Quantum Interferometry

Rhik Mazumder, Pradeep Niroula

Decoded quantum interferometry (DQI) uses classical error correction to solve optimization problems, but it is hard to tell which problems could give it a quantum advantage. We develop soundness rules that screen candidate problems by their code parameters, decoding guarantees and classical baselines. For the standard objective of counting satisfied constraints, we prove that under worst-case Hamming decoding DQI's guarantee can exceed Prange completion by at most $(\sqrt{2}-1)/2$. Optimal polynomial intersection (OPI) attains this margin cap asymptotically, so no candidate in this setting can exceed OPI's margin. We also derive a performance law for real-valued objectives: the objective fixes both the solution quality and which errors the decoder must correct. An AI-agent search guided by these rules found two candidate applications. Alternant max-agreement on McEliece-type public keys tests what a secret decoder is worth to DQI against classical solvers that see only the public instance. Multiplicative polynomial intersection, a knapsack-type problem built from discrete logarithms, pairs a cosine objective with a public decoder for signed errors. For both we prove decoding guarantees and finite-length comparisons with Prange restarts, and on the larger instances we tested, DQI's expected quality exceeds what our classical solvers reach within fixed budgets.

quant-pharXiv:2610.06753•Oct 6, 2026•0 citations

Limitations of Decoded Quantum Interferometry for MaxCut

Ojas Parekh

Decoded Quantum Interferometry (DQI) is a framework for approximating special kinds of discrete optimization problems that relies on problem structure in a way that sets it apart from other classical or quantum approaches. We show that any family of instances of MaxCut on which DQI attains a nontrivial asymptotic approximation guarantee is also solvable exactly in classical polynomial time. We include a streamlined exposition of DQI tailored for MaxCut that relies on elementary graph theory instead of coding theory to motivate and explain the algorithm.

Leibniz international proceedings in informatics•Jan 1, 2026•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

Decoded Quantum Interferometry with Polar Codes: Capacity-Approaching Decoders Meet a Minimum-Distance Ceiling

Anirban Kanjilal

Abstract Decoded Quantum Interferometry (DQI) [Jordan et al., Nature 646, 831 (2025)] turns efficient decoders for a code C⊥ into samplers for high-quality solutions of a dual optimization problem, with performance governed by the largest error weight ℓ at which uniformly random errors are decodable from their syndrome. We give the first instantiation and evaluation of DQI with polar codes, whose successive-cancellation (SC) decoders are capacity-achieving on average-case errors despite poor minimum distance. This is precisely the regime in which DQI’s average-case requirement diverges most sharply from worst-case decoding guarantees. We characterize the dual instance family, a dense hierarchical max-XORSAT whose variable degrees are powers of two, and evaluate DQI’s guarantee via the semicircle law with empirically measured, layer-resolved decoder failure rates weighted by the DQI tridiagonal eigenvector. Three findings emerge. (i) At practical block lengths (m ≤ 2048) the achievable weight fraction plateaus at ℓ∗/m ≈ 0.049 at rate 1/2, far below the ceiling h−1(1/2) ≈ 0.110, reflecting slow polarization. (ii) At the operating point, all observed list-decoding (SCL-8) failures are maximum-likelihood ambiguities, that is, consistent solutions of equal or lesser weight induced by minimum-weight dual codewords (dmin=8 at m=1024, rate 1/2). The binding constraint on ℓ is therefore information-theoretic and cannot be lifted by any decoder. (iii) The resulting net guarantee, ⟨s⟩/m ∈ [0.691, 0.708] after fidelity accounting, is matched or exceeded by simulated annealing at modest compute (best 0.724, mean 0.706, at a 10°ø budget of ∼100 s; mean best 0.698 across five instances). Polar codes at practical block lengths are thus a structurally explained negative example for DQI: capacity-achieving average-case decoding is necessary but not sufficient, because the dual code’s distance spectrum independently caps the usable error weight. This motivates DQI with distance-enhanced (CRC-aided or pre-transformed) polar variants, whose dual optimization problems we identify.

•Jun 12, 2026•0 citations
Decoded Quantum Interferometry (DQI) reduces optimization problems with two-variable constraints to decoding cycle codes. For one such problem, namely MaxCut, prior work showed that DQI achieves a nontrivial satisfaction fraction guarantee only on linear-girth graphs, for which MaxCut is classically easy. However, these no-go results rely on minimum distance assumptions that do not represent true decodability thresholds for common noise channels, thus underestimating actual DQI performance. To estimate the true performance, we derive DQI satisfaction guarantees in the presence of imperfect decoding for fixed instances and generalize prior results for random instances. We then study homological cycle codes over arbitrary finite fields, and show that minimum-weight decoding is NP-hard for every field of size q>2q>2q>2, in contrast with known results for binary cycle codes. On the Linial--Simkin ensemble of regular graphs with logarithmic girth, we prove maximum-likelihood recovery bounds and a strong converse for a family of non-uniform additive noise channels. Moreover, LP decoders provide polynomial-time recovery of a positive fraction of randomly located errors with arbitrary values. These results allow us to prove upper and lower bounds on the approximate optima achievable by DQI when restricted to classical decoders. These bounds rule out quantum advantage in the regimes we analyze but also identify a family of regular Max-kkk-Cut instances on which DQI efficiently achieves a nontrivial satisfaction fraction guarantee.
Decoded quantum interferometry (DQI) offers an approach to a class of combinatorial optimization problems by reducing quantum state preparation to a decoding task. However, the existing performance bound for imperfect decoding uses the maximum failure rate over error-weight layers to bound the performance loss uniformly, which may overestimate the effect of decoding failures in layers with low probability. Building on the existing analysis, we combine the failure rate of each layer with its probability weight in the chosen state to derive tighter performance lower bounds. For binary linear constraint problems with uniformly random target values, we obtain a finite-size lower bound on the average satisfaction ratio for fixed state parameters and a fixed decoder, and establish its improvement over the existing bound. In part of the parameter region where the existing bound falls to the random-assignment baseline, the weighted bound still provides a guarantee above that baseline. We further extend the analysis to general finite fields under a model of uniformly random translations of allowed sets of equal size. Trials in individual layers using a fixed belief propagation decoder illustrate the size of the improvement and provide confidence guarantees after accounting for sampling uncertainty. These results reveal the role of retaining the correspondence between the failure distribution and the state probabilities, and suggest directions for more refined performance analyses of other DQI constructions.
For general max-k-XORSAT with k≥3k \geq 3k≥3, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless P=NP\mathsf{P} = \mathsf{NP}P=NP: approximating beyond the random-assignment value of 1/21/21/2 is NP\mathsf{NP}NP-hard. The picture changes when each variable appears in at most DDD constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order 1/D1/\sqrt{D}1/D​. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-Ekkk-LINSAT(q,r)(q,r)(q,r) with bounded degree DDD and over arbitrary finite fields Fq\mathbb{F}_qFq​, proving that it is NP\mathsf{NP}NP-hard to exceed r/q+Oq,r(1/D)r/q + \mathcal{O}_{q,r}(1/\sqrt{D})r/q+Oq,r​(1/D​). These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on (k,D)(k,D)(k,D)-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic 1/Dlog⁡D1/\sqrt{D \log D}1/DlogD​ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the 1/D1/\sqrt{D}1/D​ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.
Decoded quantum interferometry (DQI) uses classical error correction to solve optimization problems, but it is hard to tell which problems could give it a quantum advantage. We develop soundness rules that screen candidate problems by their code parameters, decoding guarantees and classical baselines. For the standard objective of counting satisfied constraints, we prove that under worst-case Hamming decoding DQI's guarantee can exceed Prange completion by at most (2−1)/2(\sqrt{2}-1)/2(2​−1)/2. Optimal polynomial intersection (OPI) attains this margin cap asymptotically, so no candidate in this setting can exceed OPI's margin. We also derive a performance law for real-valued objectives: the objective fixes both the solution quality and which errors the decoder must correct. An AI-agent search guided by these rules found two candidate applications. Alternant max-agreement on McEliece-type public keys tests what a secret decoder is worth to DQI against classical solvers that see only the public instance. Multiplicative polynomial intersection, a knapsack-type problem built from discrete logarithms, pairs a cosine objective with a public decoder for signed errors. For both we prove decoding guarantees and finite-length comparisons with Prange restarts, and on the larger instances we tested, DQI's expected quality exceeds what our classical solvers reach within fixed budgets.
Decoded Quantum Interferometry (DQI) is a framework for approximating special kinds of discrete optimization problems that relies on problem structure in a way that sets it apart from other classical or quantum approaches. We show that any family of instances of MaxCut on which DQI attains a nontrivial asymptotic approximation guarantee is also solvable exactly in classical polynomial time. We include a streamlined exposition of DQI tailored for MaxCut that relies on elementary graph theory instead of coding theory to motivate and explain the algorithm.
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.
Abstract Decoded Quantum Interferometry (DQI) [Jordan et al., Nature 646, 831 (2025)] turns efficient decoders for a code C⊥ into samplers for high-quality solutions of a dual optimization problem, with performance governed by the largest error weight ℓ at which uniformly random errors are decodable from their syndrome. We give the first instantiation and evaluation of DQI with polar codes, whose successive-cancellation (SC) decoders are capacity-achieving on average-case errors despite poor minimum distance. This is precisely the regime in which DQI’s average-case requirement diverges most sharply from worst-case decoding guarantees. We characterize the dual instance family, a dense hierarchical max-XORSAT whose variable degrees are powers of two, and evaluate DQI’s guarantee via the semicircle law with empirically measured, layer-resolved decoder failure rates weighted by the DQI tridiagonal eigenvector. Three findings emerge. (i) At practical block lengths (m ≤ 2048) the achievable weight fraction plateaus at ℓ∗/m ≈ 0.049 at rate 1/2, far below the ceiling h−1(1/2) ≈ 0.110, reflecting slow polarization. (ii) At the operating point, all observed list-decoding (SCL-8) failures are maximum-likelihood ambiguities, that is, consistent solutions of equal or lesser weight induced by minimum-weight dual codewords (dmin=8 at m=1024, rate 1/2). The binding constraint on ℓ is therefore information-theoretic and cannot be lifted by any decoder. (iii) The resulting net guarantee, ⟨s⟩/m ∈ [0.691, 0.708] after fidelity accounting, is matched or exceeded by simulated annealing at modest compute (best 0.724, mean 0.706, at a 10°ø budget of ∼100 s; mean best 0.698 across five instances). Polar codes at practical block lengths are thus a structurally explained negative example for DQI: capacity-achieving average-case decoding is necessary but not sufficient, because the dual code’s distance spectrum independently caps the usable error weight. This motivates DQI with distance-enhanced (CRC-aided or pre-transformed) polar variants, whose dual optimization problems we identify.