Back to results
US 12,710,748 B1Granted
Optimizer and optimization based on variational rotational landscape
AssigneeMultiverse Computing S.L.
InventorsRoman Orus, Pablo Bermejo, Borja Aizpurua
Life of this patent
Estimating the term…
Abstract
An apparatus or system comprising at least one classical processor and/or at least one quantum processor configured to calculate a first cost of a predetermined cost function associated with both a predetermined optimization problem and a set of variables as parameters, and calculate the cost of the cost function a plurality of times running an optimization by applying gradient descent to a converted set of variables a plurality of times considering the most recent calculated cost of the cost function in each conversion of the set of variables.
Claims20
An apparatus or system configured to:
- calculate a cost of a predetermined cost function, ƒ(x), associated with both a predetermined optimization problem and a set of variables as parameters, wherein the cost is calculated taking a predetermined set of the variables, x, associated with the predetermined optimization problem as parameters;
- include the calculated cost in the set of the variables x;
- and
- repeat the following N times:
- define a first predetermined coordinate system with a set formed by the set of the variables x including the most recent calculated cost of the cost function ƒ(x), thereby obtaining a functional F[ƒ];
- apply gradient descent to the functional F[ƒ], thereby obtaining an optimized functional FO[ƒ];
- convert the optimized functional FO[ƒ] into a second predetermined coordinate system different from the first predetermined coordinate system, and provide the set of the variables x with values from the converted optimized functional FO[ƒ], thereby obtaining an updated set of the variables xU;
- and
- calculate the cost of the cost function ƒ(x) taking the updated set of the variables xU as parameters;
- wherein the repetition takes place at least until a difference between the most recent cost of the cost function ƒ(x) and at least one previous cost of the cost function ƒ(x) is equal to or less than a predetermined convergence threshold;
- wherein the apparatus or system is further configured to replace the set of the variables x by the updated set of the variables xU in at least all repetitions from the first to the N-th minus one, and in each said replacement or after each said replacement, replace the cost of the cost function ƒ(x) by the most recent calculated cost of the cost function ƒ(x) so that the set of the variables x includes the most recent calculated cost of the cost function ƒ(x);
- and
- wherein N is a natural number greater than one.
10 more elements
An apparatus or system configured to:
- calculate a cost of a predetermined cost function, ƒ(x), associated with both a predetermined optimization problem and a set of variables as parameters, wherein the cost is calculated taking a predetermined set of the variables, x, associated with the predetermined optimization problem as parameters;
- include the calculated cost in the set of the variables x;
- repeat the following N times:
- define a first rotation matrix such that there is a turning angle between each variable in the set of the variables x and the most recent calculated cost of the cost function ƒ(x) in a first predetermined reference frame;
- apply the first rotation matrix to the set of the variables x so that it is moved to a second predetermined reference frame;
- apply gradient descent to the cost function ƒ(x) with the set of the variables x in the second predetermined reference frame, thereby obtaining an optimized set of the variables x in the second predetermined reference frame;
- apply a second rotation matrix to the optimized set of the variables x in the second predetermined reference frame thereby obtaining an optimized set of the variables x in the first predetermined reference frame, the second rotation matrix being an inverse of the first rotation matrix;
- and
- calculate the cost of the cost function ƒ(x) in the first predetermined reference frame with the optimized set of the variables x in the first predetermined reference frame;
- wherein the repetition takes place at least until a difference between the most recent cost of the cost function ƒ(x) and at least one previous cost of the cost function ƒ(x) is equal to or less than a predetermined convergence threshold;
- and
- wherein the apparatus or system is further configured to replace the set of the variables x by the optimized set of the variables x in the first predetermined reference frame in at least all repetitions from the first to the N-th minus one, and in each said replacement or after each said replacement, replace the cost of the cost function ƒ(x) by the most recent calculated cost of the cost function ƒ(x) so that the set of the variables x includes the most recent calculated cost of the cost function ƒ(x);
- and
- wherein N is a natural number greater than one.
11 more elements
A method for solving a predetermined optimization problem, the method being run in an apparatus or system in turn comprising at least one classical processor or at least one quantum processor or both the at least one classical processor and the at least one quantum processor, the method comprising:
- calculating a cost of a predetermined cost function, ƒ(x), associated with both a predetermined optimization problem and a set of variables as parameters, wherein the cost is calculated taking a predetermined set of the variables, x, associated with the predetermined optimization problem as parameters;
- including the calculated cost in the set of the variables x;
- repeating the following N times:
- defining a first predetermined coordinate system with a set formed by the predetermined cost function and the set of the variables x including the most recent calculated cost of the cost function ƒ(x), thereby obtaining a functional F[ƒ];
- applying gradient descent to the functional F[ƒ], thereby obtaining an optimized functional FO[ƒ];
- converting the optimized functional F0[ƒ] into a second predetermined coordinate system different from the first predetermined coordinate system, and providing the set of the variables x with values from the converted optimized functional FO[ƒ], thereby obtaining an updated set of the variables xU;
- and
- calculating the cost of the cost function ƒ(x) taking the updated set of the variables xU as parameters;
- and
- replacing, at least in each repetition from the first to the N-th minus one, the set of the variables x by the updated set of the variables xU, and in each said replacement step or after each said replacement step, replacing the cost of the cost function ƒ(x) by the most recent calculated cost of the cost function ƒ(x) so that the set of the variables x includes the most recent calculated cost of the cost function ƒ(x);
- wherein the repeating step is repeated at least until a difference between the most recent cost of the cost function ƒ(x) and at least one previous cost of the cost function ƒ(x) is equal to or less than a predetermined convergence threshold;
- and wherein N is a natural number greater than one.
9 more elements
Dependencies are inferred from the claim text.