Embedding Undirected Graphs onto Extended Grids

D-Wave Systems is currently involved in the research and development of quantum computing technology. Quantum computers allow for not just a fast computer, but potentially, a change in the computational complexity of problems. Graph theory plays a crucial role in the development and understanding of the capabilities and behaviour of the quantum computing hardware being developed, both from an operational and an applications perspective. The device being developed by D-Wave Systems is, graph theoretically, an extended grid and any undirected graph can be embedded onto the infinite extended graph. Without knowing how to efficiently embed an input graph onto the extended grid, D-Wave would be unable to solve real-world problems. The research will look into all aspects of the embedding problem, specifically as it relates to the hardware being developed. Gaining a deeper understanding of the problem through analysis and experimentation will provide a greater ability to successfully develop these and future optimization methods for the current algorithm, and possibly, the development of new algorithms.

Faculty Supervisor:

Dr. Pavol Hell

Student:

Michael Coury

Partner:

D-Wave Systems Inc.

Discipline:

Computer science

Sector:

Information and communications technologies

University:

Simon Fraser University