Heuristic methods for converting higher order to quadratic polynomials in binary spaces

Abstract

A method of converting a HOBO problem into a QUBO problem. The method may include creating a data structure of key-value pairs by sorting the plurality of indices of the variables of the HOBO problem, the key in each key-value pair corresponding to combinations of quadratic terms appearing in the HOBO and the value corresponding to all terms of at least degree three that contain the associated key. For each key of the data structure, a quadratization process is performed including identifying a key with the largest number of associated values, replacing the identified key with an auxiliary variable, and updating the data structure so as to correspond with the replacement of the auxiliary variable, storing the auxiliary variable and a quadratic term the auxiliary variable replaced as a pair in a data map. The method may also include constructing a quadratic polynomial for each pair in the data map.

What is claimed is: 
     
         1 . A method of converting a Higher Order Binary Optimization (HOBO) problem into a Quadratic Unconstrained Binary Optimization (QUBO) problem, the method comprising:
 creating a data structure of key-value pairs by sorting a plurality of indices of variables of the HOBO problem, a key in each of the key-value pairs corresponds to all possible combinations of quadratic terms appearing in the HOBO problem and a value in each of the key-value pairs corresponds to all terms of at least degree three that contain an associated key;   for each key of the data structure, performing a quadratization process including:
 identifying a key of the key-value pairs with a largest number of associated values; 
 replacing the identified key with an auxiliary variable, 
 updating each key and value of each of the key-value pairs of the data structure so as to correspond with the auxiliary variable, 
 deleting all degree three terms which involve the identified key in the HOBO problem from the data structure, 
 upon a determination that all values of the identified key have been deleted, deleting the identified key from the data structure, and 
 storing the auxiliary variable and a quadratic term of the identified key as a pair in a data map; and 
 constructing a quadratic polynomial for the pair in the data map. 
   
     
     
         2 . The method of  claim 1 , wherein the HOBO problem is represented in Boolean space, and the quadratic polynomial is obtained by the following equation:
     p ( y   1   ,x   1   ,x   2 )=3 y   1   +x   1   x   2 −2 y   1   x   1 −2 y   1   x   2 ,
   where the auxiliary variable y 1  equals x 1 x 2 .   
     
     
         3 . The method of  claim 1 , wherein the HOBO problem is represented in Ising space and prior to constructing the quadratic polynomial, the HOBO problem is converted into Boolean space, and the quadratic polynomial is obtained by the following equation:
     p ( y   1   ,x   1   ,x   2 )=3 y   1   +x   1   x   2 −2 y   1   x   1 −2 y   1   x   2 ,
   where the auxiliary variable y 1  equals x 1 x 2 .   
     
     
         4 . The method of  claim 1 , wherein the HOBO problem is represented in Ising space, and the quadratic polynomial is also represented in Ising space and is obtained by the following equation:
     p ( x   1   ,x   2   ,y,d )=4+ x   1   +x   2   −y− 2 d+x   1   x   2   −x   1   y−x   2   y− 2 x   1   d− 2 x   2   d+ 2 yd,      where the auxiliary variable y 1  equals x 1 x 2  and d is a dummy variable.   
     
     
         5 . The method of  claim 4 , further comprising converting the quadratic polynomial in Ising space into a quadratic polynomial in Boolean space. 
     
     
         6 . The method of  claim 1 , further consisting of performing a pruning process on the HOBO problem prior performing to the quadritization process so as to reduce the number of variables, terms, or maximum degrees of the HOBO problem. 
     
     
         7 . A method of converting a Higher Order Binary Optimization (HOBO) problem into a Quadratic Unconstrained Binary Optimization (QUBO) problem, the method comprising:
 creating a weighted bipartite graph by sorting a plurality of indices of variables of the HOBO problem, one of left or right nodes represent all possible combinations of quadratic terms of the HOBO problem and the other of the left or right nodes represent monomials, and edges in the weighted bipartite graph exist when a monomial contains a given quadratic term and edge weights are a degree of the monomial minus one;   repeatedly performing a quadratization process until the weighted bipartite graph is disconnected, the quadritization process including:
 identifying a quadratic term with a largest sum of edge weights; 
 replacing the identified quadratic term with an auxiliary variable, 
 updating the weighted bipartite graph so as to correspond with the auxiliary variable, 
 deleting all degree three terms which involve the identified quadratic term, 
 upon a determination that there is no edge originating from the quadratic term, deleting the quadratic term, and 
 store the auxiliary variable and identified quadratic term as a pair in a data map; and 
 constructing a quadratic polynomial for the pair in the data map. 
   
     
     
         8 . The method of  claim 7 , wherein the HOBO problem is represented in Boolean space, and the quadratic polynomial is obtained by the following equation:
     p ( y   1   ,x   1   ,x   2 )=3 y   1   +x   1   x   2 −2 y   1   x   1 −2 y   1   x   2 ,
   where the auxiliary variable y 1  equals x 1 x 2 .   
     
     
         9 . The method of  claim 7 , wherein the HOBO problem is represented in Ising space and prior to constructing the quadratic polynomial, the HOBO problem is converted into Boolean space, and the quadratic polynomial is obtained by the following equation:
     p ( y   1   ,x   1   ,x   2 )=3 y   1   +x   1   x   2 −2 y   1   x   1 −2 y   1   x   2 ,
   where the auxiliary variable y 1  equals x 1 x 2 .   
     
     
         10 . The method of  claim 7 , wherein the HOBO problem is represented in Ising space, and the quadratic polynomial is also represented in Ising space and is obtained by the following equation:
     p ( x   1   ,x   2   ,y,d )=4+ x   1   +x   2   −y− 2 d+x   1   x   2   −x   1   y−x   2   y− 2 x   1   d− 2 x   2   d+ 2 yd,      where the auxiliary variable y 1  equals x 1 x 2  and d is a dummy variable.   
     
     
         11 . The method of  claim 10 , further comprising converting the quadratic polynomial in Ising space into a quadratic polynomial in Boolean space. 
     
     
         12 . The method of  claim 7 , further consisting of performing a pruning process on the HOBO problem prior performing to the quadritization process so as to reduce the number of variables, terms, or maximum degrees of the HOBO problem. 
     
     
         13 . One or more computer-readable media configured to store instructions that when executed by a system cause or direct the system to perform actions, the actions comprising:
 creating a data structure of key-value pairs by sorting a plurality of indices of variables of the HOBO problem, a key in each of the key-value pairs corresponds to all possible combinations of quadratic terms appearing in the HOBO problem and a value in each of the key-value pairs corresponds to all terms of at least degree three that contain an associated key;   for each key of the data structure, performing a quadratization process including:
 identifying a key of the key-value pairs with a largest number of associated values; 
 replacing the identified key with an auxiliary variable, 
 updating each key and value of each of the key-value pairs of the data structure so as to correspond with the auxiliary variable, 
 deleting all degree three terms which involve the identified key in the HOBO problem from the data structure, 
 upon a determination that all values of the identified key have been deleted, deleting the identified key from the data structure, and 
 storing the auxiliary variable and a quadratic term of the identified key as a pair in a data map; and 
   constructing a quadratic polynomial for the pair in the data map.   
     
     
         14 . The one or more computer-readable media of  claim 13 , wherein the HOBO problem is represented in Boolean space, and the quadratic polynomial is obtained by the following equation:
     p ( y   1   ,x   1   ,x   2 )=3 y   1   +x   1   x   2 −2 y   1   x   1 −2 y   1   x   2 ,
   where the auxiliary variable y 1  equals x 1 x 2 .   
     
     
         15 . The one or more computer-readable media of  claim 13 , wherein the HOBO problem is represented in Ising space and prior to constructing the quadratic polynomial, the HOBO problem is converted into Boolean space, and the quadratic polynomial is obtained by the following equation:
     p ( y   1   ,x   1   ,x   2 )=3 y   1   +x   1   x   2 −2 y   1   x   1 −2 y   1   x   2 ,
   where the auxiliary variable y 1  equals x 1 x 2 .   
     
     
         16 . The one or more computer-readable media of  claim 13 , wherein the HOBO problem is represented in Ising space, and the quadratic polynomial is also represented in Ising space and is obtained by the following equation:
     p ( x   1   ,x   2   ,y,d )=4+ x   1   +x   2   −y− 2 d+x   1   x   2   −x   1   y−x   2   y− 2 x   1   d− 2 x   2   d+ 2 yd,      where the auxiliary variable y 1  equals x 1 x 2  and d is a dummy variable.   
     
     
         17 . The one or more computer-readable media of  claim 16 , wherein the actions further comprise converting the quadratic polynomial in Ising space into a quadratic polynomial in Boolean space. 
     
     
         18 . The one or more computer-readable media of  claim 13 , wherein the actions further comprise performing a pruning process on the HOBO problem prior performing to the quadritization process so as to reduce the number of variables, terms, or maximum degrees of the HOBO problem. 
     
     
         19 . The one or more computer-readable media of  claim 18 , wherein the pruning process consists of establishing an error tolerance by finding a lower bound of minimum value of the HOBO problem. 
     
     
         20 . The one or more computer-readable media of  claim 18 , wherein the pruning process consists of deleting terms from the HOBO problem with absolute coefficients which are less than a predetermined value.