Algorithms

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.

Abstract: We study the complexity of Decoded Quantum Interferometry (DQI), a recently proposed quantum algorithm for approximate optimization. We argue that DQI is hard to classically simulate, and that the hardness comes from locating an exponentially large hidden subset. This type of hardness is shared by Shor's algorithm, but the hidden subset here has no apparent group structure. We first prove that DQI can be simulated in a low level of the polynomial hierarchy, ruling out hardness arguments related to quantum supremacy. Instead, we show that DQI implements an existential coding theory bound based on the MacWilliams identity, and that it prepares a state within an obfuscated quantum harmonic oscillator. Both viewpoints require a coherent application of a discrete Hermite transform, which has no natural classical analog.