Discovering New Problems for Decoded Quantum Interferometry
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 (√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.
Related
- COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry
- A provable quantum advantage for approximate optimization via decoded quantum interferometry
- Exponential quantum advantages for decoded quantum interferometry in the streaming setting
- Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
- Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry
BibTeX
@misc{mazumder2026discovering,
title = {{Discovering New Problems for Decoded Quantum Interferometry}},
author = {Rhik Mazumder and Pradeep Niroula},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06753},
eprint = {2610.06753},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06753},
}
RIS
TY - UNPB
TI - Discovering New Problems for Decoded Quantum Interferometry
AU - Rhik Mazumder
AU - Pradeep Niroula
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06753
UR - https://arxiv.org/abs/2610.06753
AB - 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. 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.
ER -