Search All Patents in Quantum Computing
Patent US10275422
Issued 2019-04-30
Systems And Methods For Finding Quantum Binary Optimization Problems
Methods and systems represent constraint as an Ising model penalty function and a penalty gap associated therewith, the penalty gap separating a set of feasible solutions to the constraint from a set of infeasible solutions to the constraint; and determines the Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor, where the penalty gap exceeds a predetermined threshold greater than zero. Such may be employed to find quantum binary optimization problems and associated gap values employing a variety of techniques.
Much More than Average Length Specification
View the Patent Matrix® Diagram to Explore the Claim Relationships
USPTO Full Text Publication >
- 1. A method of operation in a problem solving system which includes at least a first processor and at least one non-transitory processor-readable medium communicatively coupled to the first processor and which stores at least one of processor-executable instructions or data, wherein one of a number of hardware limitations of a second processor imposes a number of bounds on a set of programmable parameters, the method comprising:
receiving, by the first processor, a problem to be solved; representing, by the first processor, the problem to be solved as an Ising model, the Ising model having a number of constraints associated with the Ising model; and for each of the constraints associated the Ising model, determining, by the first processor, a respective Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor, where the respective Ising model penalty function for each constraint has a penalty gap associated with the respective Ising model penalty function that exceeds a predetermined threshold greater than zero wherein:
receiving a problem to be solved includes receiving a relation and a graph;
determining a respective Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor, includes iteratively determining the respective Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor to maximize the respective penalty gap of the respective Ising model penalty function; and
iteratively determining the respective Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor to maximize the respective penalty gap of the respective Ising model penalty function includes:
initializing a probe set, by the first processor, the probe set representing a subset of the relation, and associated with a linear programming problem that constitutes a relaxation of a linear programming problem associated with the problem to be solved; initializing a lower bound, by the first processor; for a number of cycles until an end condition is reached:
iterating over an expansion of the probe set and a configuration of ancillary variables to solve a first linear program to find a number of coefficients of the Ising model penalty function and the penalty gap which corresponds to the Ising model penalty function, by the first processor;
selecting an expanded probe set with less than a defined total number of solutions for which the penalty gap exceeds the lower bound, by the first processor;
determining whether for an expanded probe set there are no solutions for which the penalty gap exceeds the lower bound, by the first processor;
in response to determining that there are no solutions for which the penalty gap exceeds the lower bound, backtracking in the probe set, by the first processor;
selecting a respective configuration of ancillary variables;
solving a second linear program to determine a first new lower bound for the problem, by the first processor, the second linear program associated with all members of the relation and the selected configuration of ancillary variables;
in response to the first new lower bound exceeding the lower bound, setting the lower bound equal to the first new lower bound, by the first processor;
performing a local search over all members of the relation and the configuration of ancillary variables to determine a second new lower bound, by the first processor; and
in response to the second new lower bound exceeding the lower bound, setting the lower bound equal to the second new lower bound, by the first processor.
- 11. A method of operation in a problem solving system which includes at least a first processor and at least one non-transitory processor-readable medium communicatively coupled to the first processor and which stores at least one of processor-executable instructions or data, wherein one of a number of hardware limitations of a second processor imposes a number of bounds on a set of programmable parameters, the method comprising:
receiving, by the first processor, a problem to be solved; representing, by the first processor, the problem to be solved as an Ising model, the Ising model having a number of constraints associated with the Ising model; and for each of the constraints associated the Ising model, determining, by the first processor, a respective Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor, where the respective Ising model penalty function for each constraint has a penalty gap associated with the respective Ising model penalty function that exceeds a predetermined threshold greater than zero wherein:
receiving a problem to be solved includes receiving a relation and a graph;
determining a respective Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor, includes iteratively determining the respective Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor to maximize the respective penalty gap of the respective Ising model penalty function; and
iteratively determining the respective Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor to maximize the respective energy gap of the respective Ising model penalty function includes:
determining, by the at least one processor, one or more members of a feasible set for the constraint; determining, by the at least one processor, one or more members of an infeasible set for the constraint; determining, by the at least one processor, an effective energy for one or more decision variables wherein the effective energy is a marginal probability distribution for the decision variables determined by marginalizing over one or more ancillary variables; determining, by the at least one processor, an objective function having a value, the value which evaluated at the one or more programmable parameters is inversely related to a gap between the one or more members of the feasible set and the one or more members of the infeasible set, wherein the gap is related to a difference between the effective energy of at least one of the one or more members of the feasible set and the effective energy of at least one of the one or more members of the infeasible set; and determining, by the at least one processor, a minimum value of the objective function with respect to the one or more programmable parameters.
