No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914066449039360 |
|---|---|
| author | Parekh, Ojas |
| author_facet | Parekh, Ojas |
| contents | Decoded Quantum Interferometry (DQI) is a framework for approximating special kinds of discrete optimization problems that relies on problem structure in a way that sets it apart from other classical or quantum approaches. We show that the instances of MaxCut on which DQI attains a nontrivial asymptotic approximation guarantee are solvable exactly in classical polynomial time. We include a streamlined exposition of DQI tailored for MaxCut that relies on elementary graph theory instead of coding theory to motivate and explain the algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_19966 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | No Quantum Advantage in Decoded Quantum Interferometry for MaxCut Parekh, Ojas Quantum Physics Data Structures and Algorithms Decoded Quantum Interferometry (DQI) is a framework for approximating special kinds of discrete optimization problems that relies on problem structure in a way that sets it apart from other classical or quantum approaches. We show that the instances of MaxCut on which DQI attains a nontrivial asymptotic approximation guarantee are solvable exactly in classical polynomial time. We include a streamlined exposition of DQI tailored for MaxCut that relies on elementary graph theory instead of coding theory to motivate and explain the algorithm. |
| title | No Quantum Advantage in Decoded Quantum Interferometry for MaxCut |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.19966 |