Fast clique minor generation in Chimera qubit connectivity graphs

Abstract

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{C}}_{M,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.

14 pages v2 corrected first author's name

References in corpus (5)

• A practical heuristic for finding graph minors
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Algorithm engineering for a quantum annealing platform
• A Performance Estimator for Quantum Annealers: Gauge selection and Parameter Setting
• Computational Role of Collective Tunneling in a Quantum Annealer

Cited by in corpus (7)

• Prime factorization using quantum annealing and computational algebraic geometry
• Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
• Evaluating Ising Processing Units with Integer Programming
• Homology Computation of Large Point Clouds using Quantum Annealing
• Noise Dynamics of Quantum Annealers: Estimating the Effective Noise Using Idle Qubits
• Advanced unembedding techniques for quantum annealers
• Hard combinatorial problems and minor embeddings on lattice graphs