Grants and Contributions:
Title:
Improved Embedding Algorithms for Posing Ising Problems to Commercial-Scale Quantum Annealing Processors
Agreement Number:
1042506
Agreement Value:
$299,025.00
Agreement Date:
May 19, 2026 - Mar 31, 2028
Description:
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.
Organization:
National Research Council Canada
Expected Results:
In the short term, anticipated outcomes will be strengthened collaborations across industry, academia, and government to support research excellence. In the medium term, anticipated outcomes will be the development of new and potentially disruptive technologies with collaborators. In the long term, find collaborative solutions to public policy challenges and create stronger innovation systems.
Location:
Burnaby, British Columbia, CA V5G 4M9
Reference Number:
172-2026-2027-Q1-1042506
Agreement Type:
Contribution
Report Type:
Grants and Contributions
Recipient Business Number:
871875076
Recipient Type:
For-profit organization
Recipient's Legal Name:
D-Wave Systems Inc.
Federal Riding Name:
Burnaby Central
Federal Riding Number:
59002
Program:
Collaborative Science, Technology and Innovation Program - Collaborative R&D Initiatives
Program Purpose:
Collaborate on multiparty research and development programs to catalyze transformative, high-risk, high-reward research with the potential for game-changing scientific discoveries and technological breakthroughs in priority areas.
NAICS Code:
541710 - R&D in the physical, engineering and life sciences