A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure

2013/06/20 by Rishi Saket, Saket, Rishi · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Graph theory and applications #Markov Chains and Monte Carlo Methods #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum many-body systems #Theoretical and Computational Physics #cs.DS #quant-ph

paper · pdf · doi:10.48550/arxiv.1306.6943

6 pages, corrected PTAS running time

openalex publication_date 2013/06/20 · arxiv created 2013/07/01 · arxiv updated 2013/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a polynomial time approximation scheme (PTAS) for the minimum value of the classical Ising Hamiltonian with linear terms on the Chimera graph structure as defined in the recent work of McGeoch and Wang. The result follows from a direct application of the techniques used by Bansal, Bravyi and Terhal who gave a PTAS for the same problem on planar and, in particular, grid graphs. We also show that on Chimera graphs, the trivial lower bound is within a constant factor of the optimum.

Cited by

• Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
• Benchmarking a quantum annealing processor with the time-to-target metric

Related

• Simulated annealing, optimization, searching for ground states
• Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
• Approximate MAP Estimation for Pairwise Potentials via Baker's Technique
• Algorithmic Thresholds in Mean Field Spin Glasses
• Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs