Speakers
Description
We study the performance of Decoded Quantum Interferometry (DQI) on typical instances of MAX-$k$-XOR-SAT. We prove that if the decoding step of DQI corrects up to the maximum threshold of the best known computationally efficient decoders (e.g. belief propagation), then DQI is obstructed by a topological feature of the near-optimal space of solutions known as the overlap gap property (OGP). We then show that, for sufficiently large constant $k$, MAX-$k$-XOR-SAT exhibits an OGP. As the OGP is widely conjectured to exactly characterize the asymptotic performance of state-of-the-art classical algorithms, this result suggests that DQI has no quantum advantage on MAX-$k$-XOR-SAT instances exhibiting an OGP using the best known efficient classical LDPC decoders. We also give numerical evidence supporting this conjecture by showing that approximate message passing (AMP)—a classical algorithm conjectured to saturate the OGP threshold—outperforms DQI on a related ensemble of MAX-$k$-XOR-SAT instances. Finally, we prove that depth-$1$ QAOA outperforms DQI at sufficiently large $k$ under the same decoding threshold assumption.
Our result follows by showing that DQI is approximately Lipschitz under the quantum Wasserstein metric over many standard ensembles of codes. We then prove that MAX-$k$-XOR-SAT exhibits both an OGP and a related topological obstruction known as the chaos property; this is the first known OGP threshold for MAX-$k$-XOR-SAT at fixed, sufficiently large $k$, which may be of independent interest. Finally, we prove that both of these topological properties inhibit approximately Lipschitz algorithms such as DQI from optimizing MAX-$k$-XOR-SAT to large approximation ratio with any constant probability.
| Topic | Hybrid quantum-classical approaches for learning and optimization |
|---|