Decoded Quantum Interferometry Under Noise

Understand

Decoded Quantum Interferometry (DQI) is a recently proposed quantum optimization algorithm that exploits sparsity in the Fourier spectrum of objective functions, with the potential for exponential speedups over classical algorithms on suitably structured problems.

• While highly promising in idealized settings, its resilience to noise has until now been largely unexplored.
• To address this, we conduct a rigorous analysis of DQI under noise, focusing on local depolarizing noise.
• For the maximum linear satisfiability problem, we prove that, in the presence of noise, performance is governed by a noise-weighted sparsity parameter of the instance matrix, with solution quality decaying exponentially as sparsity decreases.