Decoded Quantum Interferometry Under Noise
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908869583699968 |
|---|---|
| author | Bu, Kaifeng Gu, Weichen Koh, Dax Enshan Li, Xiang |
| author_facet | Bu, Kaifeng Gu, Weichen Koh, Dax Enshan Li, Xiang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_10725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decoded Quantum Interferometry Under Noise Bu, Kaifeng Gu, Weichen Koh, Dax Enshan Li, Xiang Quantum Physics Data Structures and Algorithms Mathematical Physics 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. |
| title | Decoded Quantum Interferometry Under Noise |
| topic | Quantum Physics Data Structures and Algorithms Mathematical Physics |
| url | https://arxiv.org/abs/2508.10725 |