Source-linked AI summary
Next-Generation Topology of D-Wave Quantum Processors
Kelly Boothby, Paul Bunyk, Jack Raymond, Aidan Roy
TL;DR
The paper addresses how D-Wave’s next-generation topology compares with Chimera for embeddings and standard Ising-model problems. It describes Pegasus, translates embedding constructions, and evaluates embedding and initial problem-performance behavior. Pegasus consistently reduces heuristic embedding chain length by around 50–60%, while native structured Ising benchmarks differ qualitatively from Chimera and common acceleration techniques appear less potent.
Problem
The paper examines embeddings and simple Ising-model performance for D-Wave’s next-generation topology relative to the existing Chimera topology.
Method
The paper defines Pegasus, translates known Chimera embeddings, provides new embedding constructions, and compares P6 and C16 across diverse problem sets.
Results
Pegasus consistently achieves around a 50–60% reduction in chain length over Chimera in heuristic embeddings.
Takeaways & Limitations
Pegasus supports more efficient embeddings and native structured Ising models with behavior that differs qualitatively from corresponding Chimera models.
Takeaways & Limitations
Thorough studies of the quantum spin-glass transition were incomplete, and the compared Pegasus and Chimera spin-glass problems are different problems.
Abstract
from arXiv · showhide
This paper presents an overview of the topology of D-Wave's next-generation quantum processors. It provides examples of minor embeddings and discusses performance of embedding algorithms for the new topology compared to the existing Chimera topology. It also presents some initial performance results for simple, standard Ising model classes of problems.
1 Introduction
Pegasus is D-Wave’s next-generation processor topology, advancing beyond Chimera through higher connectivity and couplers that support more efficient embeddings and additional logical-constraint encodings.
- Pegasus is a family of processor topologies enabled by flexible architecture and simple design modifications.
- Pegasus advances beyond Chimera with qubits of degree 15 and native K4 and K6,6 subgraphs.
- More efficient embeddings and improved heuristic embedding run times are reported for cliques, bicliques, 3D lattices, and penalty models.
- Novel couplers support error-correction schemes by boosting energy scales and providing parity or auxiliary qubits.
- These novel couplers also support encoding various logical constraints.
2 Pegasus Family of Topologies
The Pegasus family is defined as a parameterized graph topology whose vertically and horizontally oriented qubits connect through internal, external, and odd couplers. Its coordinate and coupling rules specify the processor fabric and chain-supporting paths.
- Pegasus(x) denotes a family of topologies, while Pegasus without a parameter refers to Pegasus(0); P3 contains 144 nodes.
- Pegasus adds odd couplers between parallel qubits in adjacent rows or columns to Chimera’s internal and external couplers.
- Pegasus qubits have nominal length 12 and degree 15, compared with Chimera’s nominal length 4 and degree 6.
- The topology uses 24M(M −1) qubits in broad strokes, with a Pegasus(0) main fabric containing 8(3M −1)(M −1) qubits.
- The formal definition specifies the vertex set, shift parameters, coordinate labeling, main-fabric bounds, and three coupler relations.
- Pegasus qubits are oriented vertically or horizontally, and coordinates identify orientation, tile offsets, and within-tile qubit position.
- Figures depict Pegasus P3 qubits and couplers in roadway and straight-line layouts, and show vertical and horizontal qubit coordinates.
- Each row or column forms a path connected by external couplers, providing a structure useful for creating chains.
3 Minor-Embedding
Pegasus extends Chimera embedding strategies while enabling shorter-chain or native embeddings for cliques, bicliques, cubic lattices, graphene, and grid lattices. These constructions illustrate both improved capacity and new lattice structures supported by the topology.
- Known Chimera embeddings transfer to Pegasus because Chimera is a subgraph of Pegasus.
- Clique and Biclique Embeddings: The maximum biclique embedding is K12M−20,12M−20 with uniform chain length M−1.
- Clique and Biclique Embeddings: Clique embeddings reach size 12M−10 when longer chains are allowed, compared with 12(M−1) using chains of length M and M+1.
- Cubic Lattice Embedding: A 2 × 2 × 12 cubic lattice embeds in P3 with uniform chain length 2, scaling to (M−1) × (M−1) × 12 in PM.
- Selected 2d Lattice Embeddings: Pegasus contains chainlength-1 embeddings of finite graphene portions, including AA-stacked bilayer graphene represented as K2 ⊠Λ.
- Selected 2d Lattice Embeddings: A grid-with-diagonal lattice Γ3(M−1) embeds in PM with chains of length 2, whereas Chimera requires chains of length 6.
4 Heuristic Embedding Results
A small-scale faceoff study compares heuristic embeddings on Pegasus and Chimera across diverse graph classes using chain-length and runtime metrics. Despite fewer qubits and couplers, Pegasus consistently achieves substantially shorter chains.
- Results: The broader study reports Pegasus chains around 40% of Chimera lengths, with runtimes showing a similar improvement.
- Methodology: The study compares average chainlength, maximum chainlength, and average runtime for embeddings generated across problem sets and topologies.
- Methodology: Heuristic embedding may fail on individual attempts, so trials continue until t successful embeddings accumulate and total time includes failures.
- Problem Sets: The faceoff covers complete, complete bipartite, circular complete, not-all-equal-3SAT, and Erdős–Rényi random graph classes.
- Results: 50–60% reduction in chainlength is achieved by P6 relative to C16 despite P6 having fewer qubits and couplers.
5 Treewidth
Pegasus has substantially larger treewidth than Chimera at the same size parameter, with bounds established through complete-graph embeddings and a vertex elimination order.
- Treewidth bounds: Pegasus treewidth lies between 12M −11 and 12M −4, while Chimera treewidth is 4M.In both topologies, treewidth is roughly the number of qubit rows or columns.
- Lower bound: Complete graphs of size 12M −10 embed in Pegasus, giving a treewidth lower bound of 12M −11.A complete graph K_n has treewidth n −1.
- Upper bound: A vertex elimination order gives Pegasus an upper bound of 12M −4.The construction eliminates vertical qubits by parallel-path columns, then horizontal qubits after their adjacent vertical qubits are removed.
6 Error Correction
Pegasus connectivity supports a repetition-style error-correction scheme that encodes each logical qubit in two physical qubits and increases the logical energy scale.
- Logical encoding: Pairs of qubits joined by an odd coupler represent single logical qubits, producing a graph with half as many qubits, no odd couplers, and typical degree 8.The construction uses Pegasus’s additional connectivity to encode logical variables redundantly.
- Error correction: The paired-qubit construction acts as a repetition code enabling error detection and error suppression.Errors can be detected when copies disagree, while chained qubits tend to settle in the same state.
- Energy scaling: The logical Ising energy scale doubles because internal logical couplers use four physical couplers and external logical couplers use two.The physical representation therefore strengthens the encoded logical interactions.
- Energy scaling: When external couplers are used only for chains, the scheme quadruples the problem’s energy scale.Logical problem interactions then use only internal couplers.
7 Topology Implications for Native Structured Ising Models
The paper evaluates native Pegasus Ising models and classical optimization performance against Chimera. Pegasus exhibits rougher low-temperature spin-glass landscapes and typically longer TTS, while standard accelerators help it less.
- Experimental scope: The experiments study phase-transition properties and time-to-solution for standard Ising classes expressed natively on Pegasus and Chimera.The benchmark goal is to examine topology interactions without embedding.
- Time-to-solution: Across typical cases, TTS is longer in Pegasus, and accelerator impacts are diminished relative to Chimera.TTS is defined as the time required to solve one instance with 50% probability; the reported figures use median performance.
- Benchmark models: RAN1 uses i.i.d. couplings Jij ∈ {−1, 1}, whereas RANinf uses i.i.d. couplings Jij ∈ [−1, 1].Both are random spin-glass model classes.
- Equilibrium results: Pegasus spin-glass ordering decays more slowly toward T →0 than Chimera ordering, making the Pegasus landscape rougher at a given low temperature.The large-system spin-glass transition is restricted to T →0 for these models.
- Accelerator moves: Large-area local-search moves have significantly less impact on Pegasus spin glasses than on Chimera spin glasses.Eight-qubit moves package fewer interactions tidily in Pegasus, whereas many Chimera interactions fit within eight-qubit cells.
- Accelerator moves: Houdayer moves are less effective in Pegasus; Pegasus RAN1 is more challenging than Chimera RAN1, while PT-ICM makes typical RANinf behavior similar.The expected stronger relative impact of Houdayer moves in Chimera is attributed to percolation and dimensionality considerations.
- Evaluation caveat: The experiments truncate curves when ground-state identification could bias TTS, with very long runs required above N > 1000 variables.The authors report that resampling indicates the remaining bias is small in the shown results.
- Interpretation: The paper cautions that Pegasus and Chimera medians compare different problems, while Pegasus can model Chimera-like benchmarks but not conversely without embedding.It identifies reduced benefit from standard Chimera accelerator tricks as the more important comparison.
8 Conclusion
Pegasus offers higher connectivity, new couplers, and more efficient embeddings across several useful problem classes. Initial tests show shorter chains than Chimera and qualitatively different behavior on native structured Ising models.
- Pegasus provides more efficient embeddings for cliques, bicliques, lattices, penalty models, and heuristic embedding workloads.
- Cliques embed up to size 12(M −1), while bicliques reach K12M−20,12M−20 with uniform chain length M −1.
- Pegasus supports an (M −1) × (M −1) × 12 cubic lattice with uniform chainlength 2 and also provides 2d lattice embeddings.
- Pegasus PM has treewidth between 12M −11 and 12M −4, compared with 4M for a Chimera CM graph.
- P6 achieved around a 50-60% reduction in chainlength versus C16 across a diverse problem set, while native Pegasus Ising benchmarks differed qualitatively from Chimera.