Source-linked AI summary
Fast clique minor generation in Chimera qubit connectivity graphs
Kelly Boothby, Andrew D. King, Aidan Roy
TL;DR
Arbitrary Ising interaction graphs may not match the couplers in Chimera hardware, requiring graph-minor embeddings. The paper defines native clique embeddings based on uniform ell-shaped chains and develops polynomial-time optimization for induced subgraphs. These embeddings improve clique yield relative to plus-shaped chains, while arbitrary intra-cell edge failures remain a harder case.
Problem
Arbitrary Ising interaction graphs may not be directly representable by Chimera couplers, motivating efficient large-clique minor generation for defective hardware.
Method
The paper generalizes triangle embeddings into native clique embeddings using ell-shaped bundles and dynamic programming over induced Chimera subgraphs.
Results
Ell-shaped chains produce much larger clique minors than plus-shaped chains across fixed qubit-failure rates, although increasing grid size yields diminishing returns.
Takeaways & Limitations
Native clique embeddings provide uniform chain lengths and polynomial-time optimization for induced Chimera subgraphs, supporting practical minor embedding on defective hardware.
Takeaways & Limitations
For arbitrary Chimera subgraphs, maximum ell-bundle finding is polynomially equivalent to a problem the authors expect to be NP-complete.
Abstract
from arXiv · showhide
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.
1 Introduction and motivation
D-Wave processors use Chimera connectivity, so arbitrary Ising interaction graphs must be embedded as graph minors when their edges are not directly available. This paper develops native clique embeddings that preserve uniform chains and can be optimized efficiently despite defective qubits.
- 1 Introduction and motivation: D-Wave processors sample low-energy Ising spin configurations, with local fields and couplings determining the energy of each spin assignment.The hardware returns a low-energy state consisting of one Ising spin per qubit.
- 1 Introduction and motivation: Graph-minor embedding lets an interaction graph with unavailable direct couplers be represented on the processor hardware graph.Direct input requires the interaction graph to be a subgraph of the hardware graph; otherwise it must be embedded as a minor.
- 1 Introduction and motivation: Clique minors provide embeddings for fully connected problems, and prior work showed that large clique minors can be generated in polynomial time.The paper evaluates whether its approach uses fewer physical qubits and supports larger minors than recent work.
- 1.1 The Chimera graph and triangle embeddings: Chimera was selected partly because it contains a uniform, near-optimal triangle-based K_LM minor in C_M,M,L.The triangle embedding uses chains of size M + 1, while degree arguments require at least M for any uniform K_LM minor.
- 1.1 The Chimera graph and triangle embeddings: Defective qubits can invalidate chains, motivating alternative triangle embeddings and generalized ell-shaped bundles with selectable corner matchings.These generalizations increase the available embeddings exponentially while remaining optimizable in polynomial time through dynamic programming.
- 1.1 The Chimera graph and triangle embeddings: The paper formalizes native clique embeddings and seeks maximum-sized embeddings in induced Chimera subgraphs while retaining uniform chain lengths.Uniform chains are intended to provide predictable chain dynamics throughout the anneal.
2 Native Clique Embeddings
Native clique embeddings organize uniform-length chains into overlapping ell-shaped bundles whose structure guarantees clique connectivity. The paper characterizes these embeddings combinatorially through ell blocks and constructs them from a constrained word representation.
- Native clique embeddings group vertex-disjoint ells sharing an ell block, with same-bundle pairs joined twice and different-bundle pairs joined once.
- A block clique embedding contains n ell blocks of n unit cells, with every pair intersecting exactly once in complementary horizontal and vertical components.
- 4n−1 block clique embeddings containing n ell blocks exist in Cn,n,L, represented by words in {E, W} × {NE, NW, SE, SW}n−2 × {N, S}.
- Each block has a distinct height, and the construction labels block Xi with height i and width n−i+1.
- The word construction places the first corner at an extreme column, then iteratively updates a working rectangle while adding ell blocks.
- The resulting corners form a permutation, and every earlier-later block pair intersects at a designated cell, proving the constructed set is a block clique embedding.
3 Finding optimal native clique embeddings in induced subgraphs
The algorithm uses dynamic programming over working rectangles and ell blocks to find a maximum-sized native clique embedding in an induced Chimera subgraph. It is polynomial-time, with a rough running-time bound of O(n^2MNL), while arbitrary subgraphs introduce additional complexity from missing intra-cell couplers.
- The algorithm takes an induced subgraph G of C_M,N,L and a parameter n that determines chain length n + 1.
- Dynamic programming stores maximum partial block clique embeddings for each working rectangle and extends them through compatible ell blocks.The algorithm processes rectangles in increasing height and selects maximum extensions.
- Maximum bundles are precomputed for each ell block in O(nL) time before constructing block clique embeddings.
- The algorithm finds a maximum-sized native clique embedding with chain length n + 1 in polynomial time.
- The rough total running-time bound is O(n^2MNL), based on polynomially many rectangles and ell blocks and O(nL) work per algorithm-line evaluation.There are at most nMN rectangles and 4nMN ell blocks.
- For arbitrary Chimera subgraphs, finding a maximum ell bundle is polynomially equivalent to a maximum-clique problem whose complexity the authors expect to be NP-complete.The difficulty arises when arbitrary edge deletion affects the pairing of horizontal and vertical wires.
4 Comparison with previous work
The paper compares ell-shaped and plus-shaped clique chains, finding similar diminishing returns as grids grow but substantially larger clique minors from ell-shaped chains.
- Comparison with previous work: The prior greedy algorithm uses plus-shaped chains with nearly twice as many qubits and runs in O(N^3) time for C_N,N,4.The paper’s algorithm is slower at O(N^4) for C_N,N,4 but is exhaustive and empirically embeds larger cliques.
- Comparison with previous work: Figure 7 reports medians with shaded regions covering the middle two quartiles for ell-shaped and plus-shaped chain yields.Ell-shaped chains are shown in red and plus-shaped chains in blue.
- Comparison with previous work: Ell-shaped chains produce much larger clique minors than plus-shaped chains across the compared grid sizes and operational-qubit rates.The comparison uses clique yield, defined as the largest clique minor in the selected family.
- Comparison with previous work: For a fixed qubit failure rate, increasing grid size yields diminishing returns in clique yield for both chain families.The similar asymptotic behavior appears across several fixed percentages of operational qubits.