D-Wave Systems Inc.

Published purpose

The project focuses on graph minor-embedding as it relates to commercialscale annealing quantum computers. Graph minor-embedding is a necessary step when running problems on annealing quantum computers and, in general, is an NP-hard problem. Efficient heuristics designed specifically to map user problems to D-Wave’s Quantum Processing Unit (QPU) topologies (the 6-degree Chimera™ and the 15-degree Pegasus™) are currently leveraged by most users, despite the current availability of a more connected 20-degree topology (Zephyr™) released on D-Wave’s latest-generation quantum computers. This project aims to design improved heuristic algorithms for graph minor-embedding onto the Zephyr topology. In particular, the Zephyr topology features a type of graph edge known as the “odd coupler” that allows for more versatility in embeddings. One of its applications is generating additional routing options when processor graphs have low yield. Another application is generating qubit chains with shapes other than “L” (a series of vertical qubits connected to a series of horizontal qubits by an “internal coupler” type), resulting in new types of logical connectivity. These algorithmic improvements will directly impact areas where quantum annealing is expected to provide important acceleration compared to classical techniques. One of them is increasing robustness to graph yield differences in distributed quantum computing scenarios. Another is a greater support of computationally-hard problem classes. Many applications feature densely connected problems with connectivity far beyond what is natively provided, so efficient embedding of dense structures enables quantum annealing to solve larger problems with increased solution quality.