# US 2023/0419155 A1 · Quantum computing-enhanced systems and methods for large-scale constrained optimization

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0419155 A1
- Document ID: US20230419155A1
- Status: Published application
- Kind: A1
- Application number: 18/367,155
- Filed: 2023-09-12
- Published: 2023-12-28
- Earliest claimed: 2019-10-09
- Assignees: Cornell University
- Applicants: Cornell University
- Inventors: Fengqi You; Akshay Ajagekar
- Web page: https://patentgrep.com/patent/US20230419155A1

## CPC

- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

Technologies for a quantum/classical hybrid approach to solving optimization problems are 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.

## Claims

### Claim 1

An apparatus comprising:
at least one processing device comprising a processor coupled to a memory;
the at least one processing device being configured:
to identify an optimization problem;
to decompose the identified optimization problem into two or more sub-problems, each of the two or more sub-problems being associated with a disjoint subset of a plurality of variables;
to perform two or more iterations of (i) executing a first algorithm for a first one of the two or more sub-problems with a first subset of the plurality of variables on a classical computing device comprising a classical processor and (ii) executing a second algorithm for a second one of the two or more sub-problems with a second subset of the plurality of variables on a quantum computing device comprising a quantum processor; and
to determine a solution for the optimization problem based at least in part on results of execution of the first algorithm and the second algorithm in at least one of the two or more iterations;
wherein, in each of at least a first subset of the two or more iterations, execution of the first algorithm for the first sub-problem on the classical computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device; and
wherein, in each of at least a second subset of the two or more iterations, execution of the second algorithm for the second sub-problem on the quantum computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device.

### Claim 2 (depends on 1)

The apparatus of claim 1 wherein the two or more iterations are performed until at least one designated end condition is reached.

### Claim 3 (depends on 2)

The apparatus of claim 2 wherein the at least one designated end condition comprises determining that a number of the two or more iterations which have been performed exceeds a designated iteration threshold.

### Claim 4 (depends on 2)

The apparatus of claim 2 wherein the at least one designated end condition comprises one or more preset convergence criteria, the one or more preset convergence criteria being based at least in part on at least one of:
a gap between a solution for the first sub-problem and a solution for the second sub-problem for a most recently completed one of the two or more iterations; and
a gap between a first data value derived from the solution for the first sub-problem and a second data value derived from the solution for the second sub-problem for the most recently completed one of the two or more iterations.

### Claim 5 (depends on 2)

The apparatus of claim 2 wherein the at least one designated end condition comprises one or more preset convergence criteria, the one or more preset convergence criteria being based at least in part on determining that an improvement of at least one of a solution for the first sub-problem and a solution for the second sub-problem in a designated number of most recently completed ones of the two or more iterations is less than a designated improvement threshold.

### Claim 6 (depends on 1)

The apparatus of claim 1 wherein the at least one processing device is implemented at least in part internally to at least one of the classical computing device and the quantum computing device.

### Claim 7 (depends on 1)

The apparatus of claim 1 wherein, in at least a given one of the two or more iterations:
said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device is utilized as a parameter for the first sub-problem; and
said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device is utilized as a parameter for the second sub-problem.

### Claim 8 (depends on 1)

The apparatus of claim 1 wherein decomposing the identified optimization problem into the two or more sub-problems comprises decomposing the identified optimization problem such that:
the first subset of the plurality of variables associated with the first sub-problem to be solved by the classical computing device comprises more continuous variables than discrete variables; and
the second subset of the plurality of variables associated with the second sub-problem to be solved by the quantum computing device comprises one of (i) more discrete variables than continuous variables and (ii) all discrete variables and no continuous variables.

### Claim 9 (depends on 1)

The apparatus of claim 1 wherein:
said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device comprises one of an upper bound and a lower bound on at least one objective of the optimization problem; and
said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device comprises the other one of the upper bound and the lower bound on the at least one objective of the optimization problem.

### Claim 10 (depends on 1)

The apparatus of claim 1 wherein at least one of (i) said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem and (ii) said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem comprises at least one of an integer cut, a cutting plane, a partial optimal solution for the optimization problem, an optimal solution for the optimization problem, and a feasible optimal solution for the optimization problem.

### Claim 11 (depends on 1)

The apparatus of claim 1 wherein the optimization problem comprises a job scheduling problem, and wherein the first algorithm comprises a relaxed mixed-integer linear programming (MILP) solver configured to solve a MILP problem.

### Claim 12 (depends on 1)

The apparatus of claim 1 wherein the optimization problem comprises a manufacturing problem, and wherein the first algorithm comprises a dual linear programming (LP) solver configured to solve a LP problem.

### Claim 13 (depends on 1)

The apparatus of claim 1 wherein the optimization problem comprises a vehicle routing problem, and wherein the first algorithm comprises an operation for assigning a value to a parameter of an integer quadratic fractional program (IQFP) problem.

### Claim 14 (depends on 1)

The apparatus of claim 1 wherein the second algorithm comprises a quadratic unconstrained binary optimization (QUBO) problem solver.

### Claim 15

A method comprising:
identifying an optimization problem;
decomposing the identified optimization problem into two or more sub-problems, each of the two or more sub-problems being associated with a disjoint subset of a plurality of variables;
performing two or more iterations of (i) executing a first algorithm for a first one of the two or more sub-problems with a first subset of the plurality of variables on a classical computing device comprising a classical processor and (ii) executing a second algorithm for a second one of the two or more sub-problems with a second subset of the plurality of variables on a quantum computing device comprising a quantum processor; and
determining a solution for the optimization problem based at least in part on results of execution of the first algorithm and the second algorithm in at least one of the two or more iterations;
wherein, in each of at least a first subset of the two or more iterations, execution of the first algorithm for the first sub-problem on the classical computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device; and
wherein, in each of at least a second subset of the two or more iterations, execution of the second algorithm for the second sub-problem on the quantum computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device; and
wherein the method is performed by at least one processing device comprising a processor coupled to a memory.

### Claim 16 (depends on 15)

The method of claim 15 wherein:
said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device comprises one of an upper bound and a lower bound on at least one objective of the optimization problem; and
said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device comprises the other one of the upper bound and the lower bound on the at least one objective of the optimization problem.

### Claim 17 (depends on 15)

The method of claim 15 wherein at least one of (i) said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem and (ii) said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem comprises at least one of an integer cut, a cutting plane, a partial optimal solution for the optimization problem, an optimal solution for the optimization problem, and a feasible optimal solution for the optimization problem.

### Claim 18

A computer program product comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code, when executed by at least one processing device comprising a processor coupled to a memory, causes the at least one processing device:
to identify an optimization problem;
to decompose the identified optimization problem into two or more sub-problems, each of the two or more sub-problems being associated with a disjoint subset of a plurality of variables;
to perform two or more iterations of (i) executing a first algorithm for a first one of the two or more sub-problems with a first subset of the plurality of variables on a classical computing device comprising a classical processor and (ii) executing a second algorithm for a second one of the two or more sub-problems with a second subset of the plurality of variables on a quantum computing device comprising a quantum processor; and
to determine a solution for the optimization problem based at least in part on results of execution of the first algorithm and the second algorithm in at least one of the two or more iterations;
wherein, in each of at least a first subset of the two or more iterations, execution of the first algorithm for the first sub-problem on the classical computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device; and
wherein, in each of at least a second subset of the two or more iterations, execution of the second algorithm for the second sub-problem on the quantum computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device.

### Claim 19 (depends on 18)

The computer program product of claim 18 wherein:
said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device comprises one of an upper bound and a lower bound on at least one objective of the optimization problem; and
said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device comprises the other one of the upper bound and the lower bound on the at least one objective of the optimization problem.

### Claim 20 (depends on 18)

The computer program product of claim 18 wherein at least one of said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem and said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem comprises at least one of an integer cut, a cutting plane, a partial optimal solution for the optimization problem, an optimal solution for the optimization problem, and a feasible optimal solution for the optimization problem.