METHOD AND SYSTEM FOR GENERATING AN EMBEDDING PATTERN USED FOR SOLVING A QUADRATIC BINARY OPTIMIZATION PROBLEM

摘要

A method and system are disclosed for generating an embedding pattern used for solving a quadratic binary optimization problem using a quadratic solver characterized by an architecture. The method comprises obtaining an indication of a quadratic binary optimization problem; decomposing the quadratic binary optimization problem into a product of graphs representative of the input problem; selecting a graph of the product of graphs representative of the quadratic binary optimization problem; determining a nexus for embedding the selected graph of the product of graphs representative of the input problem in the architecture of the quadratic solver; determining a corresponding pattern for the nexus and buses to generate an embedding pattern and providing an indication of the embedding pattern.

主权项

1. A method for generating an embedding pattern used for solving a quadratic binary optimization problem using a quadratic solver characterized by an architecture comprising a plurality of blocks, each block comprising a plurality of registers, the method comprising:
use of a processing device for:
obtaining an indication of a quadratic binary optimization problem representative of an input problem to solve using the quadratic solver; wherein the quadratic binary optimization problem is defined as a graph G=(V,E) comprising a set of nodes V representing variables of the input problem and corresponding edges E representing terms of the input problem;decomposing the quadratic binary optimization problem into a product of graphs representative of the input problem;selecting a graph of the product of graphs representative of the quadratic binary optimization problem, the selected graph having corresponding selected graph variables; the other graph having a plurality of edges;determining a nexus for embedding the selected graph of the product of graphs representative of the input problem in the architecture of the quadratic solver; wherein the determined nexus comprises one or more than one adjacent blocks; further wherein the determined nexus provides a mapping of the corresponding selected graph variables of the selected graph to corresponding assigned registers of the determined nexus; further wherein the determined nexus comprises a set of terminals for providing a connection to the corresponding assigned registers of the nexus;determining a pattern of more than one of the determined nexus and corresponding connecting buses using the other graph of the product of graphs to generate an embedding pattern; wherein each connecting bus is used for creating a connection between corresponding sets of terminals such that the connecting buses create a set of connections representative of the plurality of edges of the other graph; andproviding an indication of the embedding pattern.