Skip to content
Preprint

Discovering New Problems for Decoded Quantum Interferometry

Oct 2026 · 0 citations
Physics

TL;DR

For both decoding guarantees and finite-length comparisons with Prange restarts, and on the larger instances the authors tested, DQI's expected quality exceeds what their classical solvers reach within fixed budgets.

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.

View source

Similar papers

Preprint Sep 2026

Cycle Codes and Decoded Quantum Interferometry

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, thes...

Anuj Apte, Shouvanik Chakrabarti, An-Di Gu et al. · 1 citation
Preprint Oct 2026

A provable quantum advantage for approximate optimization via decoded quantum interferometry

This work establishes a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm, and shows that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances.

Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones et al. · 2 citations
Preprint Oct 2026

Exponential quantum advantages for decoded quantum interferometry in the streaming setting

Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Beside...

Ke-Wen Wu, Guang-Xu Yang · 2 citations · ⚡1
Preprint Nov 2026

No Exponential Quantum Advantage for Decoded Quantum Interferometry with Local Quantum Decoders

Decoded quantum interferometry (DQI) reduces optimization of sparse linear constraint problems, and sampling from their Gibbs measures, to decoding a linear code from a quantum state. We study DQI on random $D$-regular $k$-sparse instances with $k\ge3$, for which local decoders such as belief propagation with quantum m...

Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana et al. · 1 citation · ⚡1
Preprint Nov 2026

On Multi-Constrained Path Finding utilizing Grover Search and Decoded Quantum Interferometry

Finding a path whose totals under several additive metrics all fall inside prescribed ranges is weakly NP-complete. We ask what two quantum algorithms can do for it, against strong classical baselines. For directed acyclic graphs (DAGs) we give a Grover search whose state preparation builds the uniform superposition ov...

D. Chemodanov · 0 citations
Sep 2026

Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry

We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task o...

Leo Zhou, N. Shutty, Mark Sellke et al. · 2 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.