{"ID":2866501,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.19966","arxiv_id":"2509.19966","title":"No Quantum Advantage in Decoded Quantum Interferometry for MaxCut","abstract":"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.","short_abstract":"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 g...","url_abs":"https://arxiv.org/abs/2509.19966","url_pdf":"https://arxiv.org/pdf/2509.19966v2","authors":"[\"Ojas Parekh\"]","published":"2025-09-24T10:21:31Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\"]","methods":"[]","has_code":false}