Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This paper introduces soundness rules to identify optimization problems amenable to quantum advantage via decoded quantum interferometry (DQI), focusing on code parameters, decoding guarantees, and classical baselines. For constraint satisfaction, DQI's advantage over Prange completion is bounded by $(\sqrt{2}-1)/2$, with optimal polynomial intersection (OPI) achieving this asymptotically. The authors discover two novel DQI applications, alternant max-agreement and multiplicative polynomial intersection, demonstrating their potential to outperform classical solvers on larger instances.
A single adversarial token can bypass most safety filters.
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.