2023/12/11 by Eliot Kapit, Kapit, Eliot, Brandon Barton +13 · 2 citations
Computer Science · #Cloud Computing and Resource Management #FOS: Physical sciences #Parallel Computing and Optimization Techniques #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech)
paper · pdf · doi:10.48550/arxiv.2312.06104
openalex publication_date 2023/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical approximation hardness, but the equivalent mechanism(s) for quantum algorithms are poorly understood. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We review known results from the literature, and identify mechanisms that make conventional quantum methods (such as Adiabatic Quantum Computing) weak approximation algorithms in the worst case. We construct a family of spectrally filtered quantum algorithms that escape these issues, and develop analytical theories for their performance. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be E = Nunsat-Nsat, spectrally filtered quantum optimization will return states with E ≤ qm EGS (where E\rm GS is the ground state energy) in sub-quadratic time, where conservatively, qm ≃ 0.59. This is in contrast to qm → 0 for the hardest instances with classical searches. We test all of these claims with extensive numerical simulations. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.