On the Complexity of Decoded Quantum Interferometry
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913077581053952 |
|---|---|
| author | Marwaha, Kunal Fefferman, Bill Gheorghiu, Alexandru Havlicek, Vojtech |
| author_facet | Marwaha, Kunal Fefferman, Bill Gheorghiu, Alexandru Havlicek, Vojtech |
| contents | We study the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization. First, we show that the algorithm resists classical simulation strategies based on locating outputs with large probabilities. We then prove that DQI can be simulated at a low level of the polynomial hierarchy, posing challenges to standard quantum supremacy arguments. We further show that DQI is a constructive solution to a classical coding-theoretic bound based on the MacWilliams identity. Lastly, we interpret DQI as preparing low-energy states of a quantum simple harmonic oscillator, a viewpoint we believe suggests a physics-motivated route to generalizing DQI. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14443 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Decoded Quantum Interferometry Marwaha, Kunal Fefferman, Bill Gheorghiu, Alexandru Havlicek, Vojtech Quantum Physics Computational Complexity We study the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization. First, we show that the algorithm resists classical simulation strategies based on locating outputs with large probabilities. We then prove that DQI can be simulated at a low level of the polynomial hierarchy, posing challenges to standard quantum supremacy arguments. We further show that DQI is a constructive solution to a classical coding-theoretic bound based on the MacWilliams identity. Lastly, we interpret DQI as preparing low-energy states of a quantum simple harmonic oscillator, a viewpoint we believe suggests a physics-motivated route to generalizing DQI. |
| title | On the Complexity of Decoded Quantum Interferometry |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2509.14443 |