A provable quantum advantage for approximate optimization via decoded quantum interferometry
This work establishes a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm, and shows that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances.