arXiv:2610.06753
Discovering New Problems for Decoded Quantum Interferometry
Rhik Mazumder, Pradeep Niroula
Abstract
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.
AI Summary
Decoded quantum interferometry (DQI) converts classical decoding capability into optimization quality. This paper asks which optimization problems can support a DQI advantage and develops screening conditions separating coding constraints, decoder guarantees, and classical baselines. For constraint-counting objectives with optimizer-code rate $\alpha$, it inverts the known DQI quality law to obtain the decoding reach required to beat one Prange completion. Distance, packing, Singleton, and Plotkin bounds then exclude parameter regimes; further comparisons address efficient source encoders and subfield linear algebra. Under worst-case Hamming decoding, the asymptotic quality margin over one Prange completion is at most $\sqrt{(\alpha/2)(1-\alpha/2)}-\alpha/2$, universally bounded by $(\sqrt2-1)/2\approx0.2071$. Optimal polynomial intersection attains this cap asymptotically. For shifted real-valued row objectives, an exact tridiagonal spectral formula expresses expected quality through the objective’s mean, variance, and skewness, while its Fourier support specifies the required error alphabet. Two applications follow: alternant max-agreement gives DQI a secret decoder, with public-instance classical comparisons; multiplicative polynomial intersection pairs a cosine objective with a public rational-reconstruction decoder for signed errors. At tested lengths, DQI’s exact expectations exceed tested classical scores—for example, $0.2518$ versus approximately $0.115$ for the latter at $m=6000$. Concentration bounds also establish comparisons against restricted Prange restarts. These are candidate advantages, not hardness proofs: broader classical hardness is assumed, search comparisons are budget-dependent, and quantum resource estimates are absent. The multiplicative construction’s unbounded asymptotics require infinitely many Mersenne primes; the general extension-field indicator analysis assumes the corresponding quality law.
AI tools were used extensively in generating and developing the core ideas of this work, as well as in drafting, revising, and editing the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.