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

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

Anirban Kanjilal

Published Jun 12, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.5281/zenodo.20672476

Related papers

Cycle Codes and Decoded Quantum Interferometry

Anuj Apte, Shouvanik Chakrabarti, Andi Gu +6 more

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.

quant-pharXiv:2609.40036•Oct 1, 2026•0 citations

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

Optimization of Quadratic Constraints by Decoded Quantum Interferometry

Daniel Cohen Hillel

A recent paper by Jordan et al. introduced Decoded Quantum Interferometry (DQI), a novel quantum algorithm that uses the quantum Fourier transform to reduce linear optimization problems -- max-XORSAT and max-LINSAT -- to decoding problems. In this paper, we extend DQI to optimization problems involving quadratic constraints, which we call max-QUADSAT. Leveraging a connection to quadratic Gauss sums, we give an efficient algorithm to prepare the DQI state for max-QUADSAT (DISCLAIMER: A mistake was found in one of the algorithm's steps, which invalidates this result unless a fix is found). To demonstrate that our algorithm achieves a quantum advantage, we introduce the Quadratic Optimal Polynomial Intersection (quadratic-OPI) problem, a restricted variant of OPI for which, to our knowledge, the standard DQI framework offers no algorithmic speedup. We show that quadratic-OPI is an instance of max-QUADSAT and use our algorithm to optimize it. Lastly, we present a new generalized proof of the "semicircle law" for the fraction of satisfied constraints, generalizing it to any DQI state of problems where the distribution of the number of satisfied constraints for a random assignment is sufficiently close to a binomial distribution. This condition holds exactly for the DQI state of max-LINSAT, and approximately holds in the max-QUADSAT case, with the approximation becoming exponentially better as the problem size increases. This establishes performance guarantees for our algorithm.

arXiv:2510.08061•Oct 9, 2025•0 citations

Decoded Quantum Interferometry Beyond Hamming: Rank-Metric and Translation Association Schemes

Alexandre Krajenbrink, Colin Krawchuk, Ansis Rosmanis +1 more

Decoded Quantum Interferometry (DQI) uses coherent decoding and a quantum Fourier transform to find high-quality solutions of structured optimisation problems. Existing analyses are closely tied to Hamming space, which underlies the optimisation objective, Dicke state preparation and the decoding step of the algorithm. Here we extend the core DQI mechanism beyond Hamming space to finite geometries with translation symmetry, where points are grouped into shells by their distance from a basepoint. Mathematically, these geometries are translation association schemes. In this setting the algorithm can be analysed by tracking one amplitude per shell, and biasing the prepared state towards high-quality solutions becomes a finite tridiagonal eigenvalue problem. As a non-Hamming example, we develop an efficient DQI protocol for finding an m x n finite-field matrix with smallest rank difference to a target matrix. Initial states are uniform superpositions over fixed-rank matrices, and Gabidulin codes provide candidates for efficient low-rank decoding up to a cutoff l. For this objective, this finds solutions with an effective-rank proxy near min(m,n)-l, and the corresponding expected score can be converted into a constant-probability bound on the residual rank of a sample. For Gabidulin nearest-codeword instances, a covering-radius obstruction shows that this bound does not imply an additive guarantee for the true optimum, and we do not claim a quantum advantage for the rank-metric construction. The results instead identify the geometric and coding ingredients for DQI beyond Hamming space.

quant-pharXiv:2606.04843•Jun 4, 2026•0 citations
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.
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.
A recent paper by Jordan et al. introduced Decoded Quantum Interferometry (DQI), a novel quantum algorithm that uses the quantum Fourier transform to reduce linear optimization problems -- max-XORSAT and max-LINSAT -- to decoding problems. In this paper, we extend DQI to optimization problems involving quadratic constraints, which we call max-QUADSAT. Leveraging a connection to quadratic Gauss sums, we give an efficient algorithm to prepare the DQI state for max-QUADSAT (DISCLAIMER: A mistake was found in one of the algorithm's steps, which invalidates this result unless a fix is found). To demonstrate that our algorithm achieves a quantum advantage, we introduce the Quadratic Optimal Polynomial Intersection (quadratic-OPI) problem, a restricted variant of OPI for which, to our knowledge, the standard DQI framework offers no algorithmic speedup. We show that quadratic-OPI is an instance of max-QUADSAT and use our algorithm to optimize it. Lastly, we present a new generalized proof of the "semicircle law" for the fraction of satisfied constraints, generalizing it to any DQI state of problems where the distribution of the number of satisfied constraints for a random assignment is sufficiently close to a binomial distribution. This condition holds exactly for the DQI state of max-LINSAT, and approximately holds in the max-QUADSAT case, with the approximation becoming exponentially better as the problem size increases. This establishes performance guarantees for our algorithm.
Decoded Quantum Interferometry (DQI) uses coherent decoding and a quantum Fourier transform to find high-quality solutions of structured optimisation problems. Existing analyses are closely tied to Hamming space, which underlies the optimisation objective, Dicke state preparation and the decoding step of the algorithm. Here we extend the core DQI mechanism beyond Hamming space to finite geometries with translation symmetry, where points are grouped into shells by their distance from a basepoint. Mathematically, these geometries are translation association schemes. In this setting the algorithm can be analysed by tracking one amplitude per shell, and biasing the prepared state towards high-quality solutions becomes a finite tridiagonal eigenvalue problem. As a non-Hamming example, we develop an efficient DQI protocol for finding an m x n finite-field matrix with smallest rank difference to a target matrix. Initial states are uniform superpositions over fixed-rank matrices, and Gabidulin codes provide candidates for efficient low-rank decoding up to a cutoff l. For this objective, this finds solutions with an effective-rank proxy near min(m,n)-l, and the corresponding expected score can be converted into a constant-probability bound on the residual rank of a sample. For Gabidulin nearest-codeword instances, a covering-radius obstruction shows that this bound does not imply an additive guarantee for the true optimum, and we do not claim a quantum advantage for the rank-metric construction. The results instead identify the geometric and coding ingredients for DQI beyond Hamming space.