2015/07/16 by Kelly Boothby, Andrew D. King, Boothby, Kelly +3 · 7 citations
Computer Science · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum many-body systems
paper · pdf · doi:10.48550/arxiv.1507.04774
openalex publication_date 2015/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The current generation of D-Wave quantum annealing processor is designed to minimize the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a \em Chimera graph \mathcal CM,N,L. In order to solve an Ising spin problem with arbitrary pairwise interaction structure, the corresponding graph must be minor-embedded into a Chimera graph. We define a combinatorial class of \em native clique minors in Chimera graphs with vertex images of uniform, near minimal size, and provide a polynomial-time algorithm that finds a maximum native clique minor in a given induced subgraph of a Chimera graph. These minors allow improvement over recent work and have immediate practical applications in the field of quantum annealing.