Bu, K., Gu, W., Enshan Koh, D., & Li, X. (2026). Decoded quantum interferometry under noise. Quantum Science and Technology, 11(2), 25010. https://doi.org/10.1088/2058-9565/ae4536
Abstract:
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. We demonstrate this decay through numerical simulations on two special cases: the optimal polynomial intersection problem and the maximum XOR satisfiability problem. The Fourier-analytic methods we develop can be readily adapted to other classes of random Pauli noise, making our framework applicable to a broad range of noisy quantum settings and offering guidance on preserving DQI’s potential quantum advantage under realistic noise.
License type:
Attribution 4.0 International (CC BY 4.0)
Funding Info:
This research / project is supported by the Agency for Science, Technology and Research - Central Research Fund
Grant Reference no. : NA
This research is supported by core funding from: Quantum Innovation Centre (Q.InC) Strategic Research and Translational Thrust (SRTT)
Grant Reference no. :