A provable quantum advantage for approximate optimization via decoded quantum interferometry
This research introduces Decoded Quantum Interferometry (DQI) to solve approximate optimization problems using quantum computers. It proves a provable separation between DQI's performance and classical polynomial-time algorithms when dealing with folded optimal polynomial intersection tasks in an oracle setting, demonstrating a quantum advantage.