On the Complexity of Decoded Quantum Interferometry
For quantum computing theorists, this work clarifies the complexity of DQI, revealing limitations in standard quantum supremacy arguments and providing new theoretical connections.
The paper analyzes the complexity of Decoded Quantum Interferometry (DQI), showing it resists classical simulation based on large-probability outputs but can be simulated at a low level of the polynomial hierarchy, challenging quantum supremacy claims. It also connects DQI to coding theory and quantum harmonic oscillators.
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.