Systems and methods for quadratic unconstrained binary optimization (qubo) transformation

Abstract

Computer devices, systems and methods for transforming converting and evaluating high complexity computer science optimization problems using quantum and quantum inspired data transformation approaches and corresponding computer data structures are proposed, useful in specific situations, where computational complexity at scale prohibits alternative approaches, the approaches to solving the transformed problems yielding acceptable accuracy output despite a technical tradeoff in potential loss in accuracy. The transformed computer problem can then be solved using specialized quantum or quantum inspired computing architectures. The optimization problem outputs can be converted into specific data messages routed for automatically invoking downstream data processes and data subroutines.

What is claimed is: 
     
         1 . A computing system configured for transforming a high complexity mixed-integer linear programming (MILP) subroutine having a large problem instance into a quadratic unconstrained binary optimization (QUBO) programming subroutine adapted for using quantum or quantum inspired approaches for optimizing allocation of a set of data objects to a set of parties with a plurality of constraints, the computing system comprising:
 a computer processor coupled to non-transitory computer memory and data storage, the computer processor configured to:
 initialize a decision variable matrix data structure containing a plurality of object-party allocation variable as elements, wherein each object-party allocation variable is a continuous variable representing an allocation score of the corresponding data object that is allocated to the corresponding party, wherein the decision variable matrix has a column for each data object, wherein the decision variable matrix has a row for each party; 
 construct a coefficients matrix data structure to store a plurality of tiers, wherein the coefficients matrix data structure has a column for each data object, wherein the coefficients matrix data structure has a row for each party, wherein each tier is a scalar value indicative of quality of the corresponding object-party allocation variable; 
 generate a plurality of constraint equations corresponding to the plurality of constraints; 
 transform the decision variable matrix data structure and the coefficients matrix data structure into the MILP programming subroutine with a linear objective function and the plurality of constraint equations; 
 map the MILP programming subroutine onto the QUBO programming subroutine by replacing all continuous variables in the linear objective function with a plurality of discrete binaries and encoding the plurality of constraint equations; 
 compute an optimized allocation of the set of data objects to the set of parties by solving the QUBO programming subroutine; 
 extrapolate, from the decision variable matrix data structure of the optimized allocation of the set of data objects to the set of parties, allocation parameters to realize the optimized allocation of the set of data objects to the set of parties, the allocation parameters being a vector or list of parameter values; and 
 generate, one or more data messages corresponding to electronic transaction requests to automatically shift allocation in accordance with the optimized allocation of the set of data objects. 
   
     
     
         2 . The computing system of  claim 1 , wherein the set of data objects and set of parties are represented as a bipartite graph comprising two sets of nodes with weighted edges, the two sets of nodes representing the set of data objects and the set of parties. 
     
     
         3 . The computing system of  claim 1 , wherein the computing system further includes an adaptive encoder configured to map individual constraint properties to either a balanced encoding approach or an unbalanced penalization approach, controlling a number of slack variables being used during constraint encoding into the QUBO programming subroutine. 
     
     
         4 . The computing system of  claim 1 , wherein the computer processor is a noisy intermediate-scale quantum (NISQ) device processor using variational quantum algorithms (VQAs). 
     
     
         5 . The computing system of  claim 1 , wherein the computer processor is a quantum computer processor using quantum annealing. 
     
     
         6 . The computing system of  claim 1 , wherein the computer processor utilizes the QUBO programming subroutine with a digital or simulated annealing approach. 
     
     
         7 . The computing system of  claim 1 , wherein encoding the plurality of constraint equations comprises using a plurality of balanced slack variables for penalization. 
     
     
         8 . The computing system of  claim 1 , further comprising a selection circuit that is coupled to a MILP solver, the selection circuit configured to generate a computational starting point using the MILP solver, and then configured to solve the QUBO programming subroutine using the computational starting point as an initial condition. 
     
     
         9 . The computing system of  claim 1 , wherein encoding the plurality of constraint equations comprises using an unbalanced penalization technique comprising creating a plurality of penalty terms, wherein a penalty term takes on a value dependent on violation of the corresponding constraint. 
     
     
         10 . The computing system of  claim 1 , wherein the computer processor comprises a GPU with a plurality of tensor cores that is optimized for mixed-precision training in a machine learning model, the mixed-precision training enabling the GPU to compute a plurality of computer number precision formats. 
     
     
         11 . A method for transforming a high complexity mixed-integer linear programming (MILP) subroutine having a large problem instance into a quadratic unconstrained binary optimization (QUBO) programming subroutine adapted for using quantum or quantum inspired approaches for optimizing allocation of a set of data objects to a set of parties with a plurality of constraints, the method comprising:
 initializing a decision variable matrix data structure containing a plurality of object-party allocation variable as elements, wherein each object-party allocation variable is a continuous variable representing an allocation score of the corresponding data object that is allocated to the corresponding party, wherein the decision variable matrix has a column for each data object, wherein the decision variable matrix has a row for each party;   constructing a coefficients matrix data structure to store a plurality of tiers, wherein the coefficients matrix data structure has a column for each data object, wherein the coefficients matrix data structure has a row for each party, wherein each tier is a scalar value indicative of quality of the corresponding object-party allocation variable;   generating a plurality of constraint equations corresponding to the plurality of constraints;   transforming the decision variable matrix data structure and the coefficients matrix data structure into the MILP programming subroutine with a linear objective function and the plurality of constraint equations;   mapping the MILP programming subroutine onto the QUBO programming subroutine by replacing all continuous variables in the linear objective function with a plurality of discrete binaries and encoding the plurality of constraint equations;   determining an optimized allocation of the set of data objects to the set of parties by solving the QUBO programming subroutine;   extrapolating, from the decision variable matrix data structure of the optimized allocation of the set of data objects to the set of parties, allocation parameters to realize the optimized allocation of the set of data objects to the set of parties, the allocation parameters being a vector or list of parameter values; and   generating, one or more data messages corresponding to electronic transaction requests to automatically shift allocation in accordance with the optimized allocation of the set of data objects.   
     
     
         12 . The method of  claim 11 , wherein the set of data objects and set of parties are represented as a bipartite graph comprising two sets of nodes with weighted edges, the two sets of nodes representing the set of data objects and the set of parties. 
     
     
         13 . The method of  claim 11 , wherein the method further includes an adaptive encoder configured to map individual constraint properties to either a balanced encoding approach or an unbalanced penalization approach, controlling a number of slack variables being used during constraint encoding into the QUBO programming subroutine. 
     
     
         14 . The method of  claim 11 , wherein the computer processor is a noisy intermediate-scale quantum (NISQ) device processor using variational quantum algorithms (VQAs). 
     
     
         15 . The method of  claim 11 , wherein the method is conducted on a quantum computer processor using quantum annealing. 
     
     
         16 . The method of  claim 11 , wherein the computer processor utilizes the QUBO programming subroutine with a digital or simulated annealing approach. 
     
     
         17 . The method of  claim 11 , wherein encoding the plurality of constraint equations comprises using a plurality of balanced slack variables for penalization. 
     
     
         18 . The method of  claim 11 , further comprising a selection circuit that is coupled to a MILP solver, the selection circuit configured to generate a computational starting point using the MILP solver, and then configured to solve the QUBO programming subroutine using the computational starting point as an initial condition. 
     
     
         19 . The method of  claim 11 , wherein encoding the plurality of constraint equations comprises using an unbalanced penalization technique comprising creating a plurality of penalty terms, wherein a penalty term takes on a value dependent on violation of the corresponding constraint. 
     
     
         20 . A non-transitory computer readable medium storing computer interpretable instruction, which when executed by a computer processor, cause the computer processor to perform a method for transforming a high complexity mixed-integer linear programming (MILP) subroutine having a large problem instance into a quadratic unconstrained binary optimization (QUBO) programming subroutine adapted for using quantum or quantum inspired approaches for optimizing allocation of a set of data objects to a set of parties with a plurality of constraints, the method comprising:
 initializing a decision variable matrix data structure containing a plurality of object-party allocation variable as elements, wherein each object-party allocation variable is a continuous variable representing an allocation score of the corresponding data object that is allocated to the corresponding party, wherein the decision variable matrix has a column for each data object, wherein the decision variable matrix has a row for each party;   constructing a coefficients matrix data structure to store a plurality of tiers, wherein the coefficients matrix data structure has a column for each data object, wherein the coefficients matrix data structure has a row for each party, wherein each tier is a scalar value indicative of quality of the corresponding object-party allocation variable;   generating a plurality of constraint equations corresponding to the plurality of constraints;   transforming the decision variable matrix data structure and the coefficients matrix data structure into the MILP programming subroutine with a linear objective function and the plurality of constraint equations;   mapping the MILP programming subroutine onto the QUBO programming subroutine by replacing all continuous variables in the linear objective function with a plurality of discrete binaries and encoding the plurality of constraint equations;   determining an optimized allocation of the set of data objects to the set of parties by solving the QUBO programming subroutine;   extrapolating, from the decision variable matrix data structure of the optimized allocation of the set of data objects to the set of parties, allocation parameters to realize the optimized allocation of the set of data objects to the set of parties, the allocation parameters being a vector or list of parameter values; and   generating, one or more data messages corresponding to electronic transaction requests to automatically shift allocation in accordance with the optimized allocation of the set of data objects.