Back to results
US 11,769,070 B2Granted
Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems
AssigneeCornell University
InventorsFengqi You, Akshay Ajagekar
Life of this patent
Estimating the term…
Abstract
Technologies for a quantum/classical hybrid approach to solving optimization problems is disclosed. In the illustrative embodiment, an optimization problem is decomposed into two sub-problems. The first sub-problem is solved on a classical computer, and a result from the first sub-problem is provided to a quantum computer. The quantum computer then solves the second sub-problem based on the result of the first sub-problem from the classical computer. The quantum computer can then provide a result to the classical computer to re-solve the first problem. The iterative calculation is continued until an end condition is met.
Claims31
A system for solving optimization problems, the system comprising:
- a classical computer comprising a classical processor and one or more non-transitory storage media comprising a plurality of instructions that, when executed, cause the classical computer to:
- initialize a plurality of parameters of an optimization problem, wherein the optimization problem is decomposed into a first sub-problem to be solved by a first algorithm on the classical computer and a second sub-problem to be solved by a second algorithm utilizing quantum computing processing, wherein the first sub-problem has a first set of one or more variables and the second sub-problem has a second set of one or more variables, wherein at least one variable of the second set of one or more variables is different from the variables of the first set of one or more variables and wherein at least one variable of the first set of one or more variables is different from the variables of the second set of one or more variables;
- execute the first algorithm for the first sub-problem with use of the classical computer to determine a current result of the first algorithm;
- and
- further comprising a quantum processor to execute the second algorithm for the second sub-problem with use of the quantum processor based on the current result of the first algorithm to determine a current result of the second algorithm;
- wherein the plurality of instructions further cause the classical computer to execute the first algorithm for the first sub-problem with use of the classical computer and with use of the current result of the second algorithm to determine the current result of the first algorithm;
- wherein the classical computer and the quantum processor are configured to repeat the execution of the first algorithm based on the current result of the second algorithm and repeat execution of the second algorithm based on the current result of the first algorithm, respectively, one or more times;
- and
- wherein the second algorithm comprises a quadratic unconstrained binary optimization (QUBO) problem solver.
6 more elements
A method for solving optimization problems, the method comprising:
- (i) initializing, by a classical computer, a plurality of parameters of an optimization problem, wherein the optimization problem has a first sub-problem comprising a first set of one or more variables and a second sub-problem comprising a second set of one or more variables, the first sub-problem to be solved by a first algorithm on the classical computer and the second sub-problem to be solved by a second algorithm on a quantum processor, the first set of one or more variables has at least one variable that is different from the second set of one or more variables and the second set of one or more variables has at least one variable that is different from the first set of one or more variables;
- (ii) executing the first algorithm for the first sub-problem with use of the classical computer to determine a current result of the first algorithm;
- (iii) executing the second algorithm for the second sub-problem with use of the quantum processor based on the current result of the first algorithm to determine a current result of the second algorithm;
- (iv) executing the first algorithm for the first sub-problem with use of the classical computer and with use of the current result of the second algorithm to determine the current result of the first algorithm;
- and
- (v) repeating steps (iii) and (iv) one or more times;
- wherein the second algorithm comprises a quadratic unconstrained binary optimization (QUBO) problem solver.
4 more elements
A method for solving optimization problems, the method comprising:
- (i) initializing, by a classical computer, a plurality of parameters of an optimization problem, wherein the optimization problem has a first sub-problem comprising a first set of one or more variables and a second sub-problem comprising a second set of one or more variables, the first sub-problem to be solved by a first algorithm on the classical computer and the second sub-problem to be solved by a second algorithm on a quantum processor, the first set of one or more variables has at least one variable that is different from the second set of one or more variables and the second set of one or more variables has at least one variable that is different from the first set of one or more variables;
- (ii) executing the first algorithm for the first sub-problem with use of the classical computer to determine a current result of the first algorithm;
- (iii) executing the second algorithm for the second sub-problem with use of the quantum processor based on the current result of the first algorithm to determine a current result of the second algorithm;
- (iv) executing the first algorithm for the first sub-problem with use of the classical computer and with use of the current result of the second algorithm to determine the current result of the first algorithm;
- and
- (v) repeating steps (iii) and (iv) one or more times;
- wherein the second algorithm is configured to solve a quadratic unconstrained binary optimization (QUBO) problem;
- and
- wherein the first algorithm is an optimization algorithm stored in one or more non-transitory storage media and configured to solve the optimization problem, the optimization problem comprising at least one of a mixed-integer linear programming (MILP) problem, a relaxed mixed-integer linear programming (MILP) problem, a mixed-integer non-linear programming (MINLP) problem, a linear programming (LP), a non-linear programming (NLP) problem, a binary quadratic programming (BQP) problem, a mixed-integer quadratic programming (MIQP) problem, and a mixed-integer fractional programming (MIFP) problem.
6 more elements
A system for solving optimization problems, the system comprising:
- a classical computer comprising a classical processor and one or more non-transitory storage media comprising a plurality of instructions that, when executed, cause the classical computer to:
- initialize a plurality of parameters of an optimization problem, wherein the optimization problem is decomposed into a first sub-problem to be solved by a first algorithm on the classical computer and a second sub-problem to be solved by a second algorithm utilizing quantum computing processing, wherein the first sub-problem has a first set of one or more variables and the second sub-problem has a second set of one or more variables, wherein at least one variable of the second set of one or more variables is different from the variables of the first set of one or more variables and wherein at least one variable of the first set of one or more variables is different from the variables of the second set of one or more variables;
- execute the first algorithm for the first sub-problem with use of the classical computer to determine a current result of the first algorithm;
- and
- further comprising a quantum processor to execute the second algorithm for the second sub-problem with use of the quantum processor based on the current result of the first algorithm to determine a current result of the second algorithm;
- wherein the plurality of instructions further cause the classical computer to execute the first algorithm for the first sub-problem with use of the classical computer and with use of the current result of the second algorithm to determine the current result of the first algorithm;
- wherein the classical computer and the quantum processor are configured to repeat the execution of the first algorithm based on the current result of the second algorithm and repeat execution of the second algorithm based on the current result of the first algorithm, respectively, one or more times;
- wherein the second algorithm is configured to solve a quadratic unconstrained binary optimization (QUBO) problem;
- and
- wherein the first algorithm is an optimization algorithm configured to solve the optimization problem, the optimization problem comprising at least one of a mixed-integer linear programming (MILP) problem, a relaxed mixed-integer linear programming (MILP) problem, a mixed-integer non-linear programming (MINLP) problem, a linear programming (LP), a non-linear programming (NLP) problem, a binary quadratic programming (BQP) problem, a mixed-integer quadratic programming (MIQP) problem, and a mixed-integer fractional programming (MIFP) problem.
7 more elements
Dependencies are inferred from the claim text.