Energy Scale Degradation in Sparse Quantum Solvers: A Barrier to Quantum Utility
This identifies a fundamental barrier to achieving quantum advantage in optimization problems, highlighting the need for better hardware and algorithms.
The paper tackles the performance degradation in quantum solvers due to sparse qubit connectivity requiring minor-embedding, which reduces energy gaps and exponentially decays success probability, as validated by experiments on D-Wave annealers.
Quantum computing offers a promising route for tackling hard optimization problems by encoding them as Ising models. However, sparse qubit connectivity requires the use of minor-embedding, mapping logical qubits onto chains of physical qubits, which necessitates stronger intra-chain coupling to maintain consistency. This elevated coupling strength forces a rescaling of the Hamiltonian due to hardware-imposed limits on the allowable ranges of coupling strengths, reducing the energy gaps between competing states, thus, degrading the solver's performance. Here, we introduce a theoretical model that quantifies this degradation. We show that as the connectivity degree increases, the effective temperature rises as a polynomial function, resulting in a success probability that decays exponentially. Our analysis further establishes worst-case bounds on the energy scale degradation based on the inverse conductance of chain subgraphs, revealing two most important drivers of chain strength, \textit{chain volume} and \textit{chain connectivity}. Our findings indicate that achieving quantum advantage is inherently challenging. Experiments on D-Wave quantum annealers validate these findings, highlighting the need for hardware with improved connectivity and optimized scale-aware embedding algorithms.