Method and system for solving integer programming and discrete optimization problems using analog processors
View Patent ↗Discrete optimization problem are solved using an analog optimization device such as a quantum processor. Problems are solved using an objective function and at least one constraint corresponding to the discrete optimization problems. The objective function is converted into a first set of inputs and the at least one constraint is converted into a second set of inputs for the analog optimization device. A third set of inputs is generated which are indicative of at least one penalty coefficient. A final state of the analog optimization device corresponds to at least a portion of the solution to the discrete optimization problem.
1. A method of solving a discrete optimization problem using a quantum computer, the method comprising:
receiving an objective function and at least one constraint corresponding to the discrete optimization problem;
converting the objective function into a first set of inputs for the quantum computer;
converting the at least one constraint into a second set of inputs for the quantum computer;
categorizing the constraints as either linear constraints or non-linear constraints, and wherein there are at least two constraints and the second set of inputs is comprised of a first subset of linear constraint inputs and a second subset of non-linear constraint inputs;
generating a third set of inputs wherein the thirds set of inputs is at least indicative of at least one penalty coefficient;
processing the first set of inputs, the second set of inputs and the third set of inputs with the quantum computer; and
reading out a final state of the quantum computer wherein at least a portion of a solution to the discrete optimization problem corresponds to the final state of the quantum computer.
2. The method of claim 1 wherein the non-linear constraint has a predetermined penalty representation corresponding to a known set of inputs for the quantum computer.
3. The method of claim 1 wherein converting the at least one constraint includes converting at least one n-local interaction into a plurality of 2-local interactions, wherein n is greater than 2.
4. The method of claim 1 , further comprising:
converting at least one of the first set of inputs, the second set of inputs and the third set of inputs into binary values.
5. The method of claim 1 , further comprising:
generating a fourth set of inputs for the quantum computer wherein the fourth set of inputs is an increasing of the value of at least one of the at least one penalty coefficient;
processing the first set of inputs, the second set of inputs and the fourth set of inputs on the quantum computer; and
reading out a second final state of the quantum computer.
6. The method of claim 1 wherein processing the first set of inputs, the second set of inputs and the third set of inputs on the quantum computer comprises:
combining the first set of inputs, the second set of inputs and the third set of inputs into an energy function to be minimized by the quantum computer.
7. The method of claim 6 , further comprising:
performing a meta-optimization procedure on the energy function to decompose the energy function into a plurality of energy subfunctions.
8. The method of claim 1 wherein the quantum computer includes at least one of an analog optimization device and an adiabatic quantum computer.
9. The method of claim 1 wherein the discrete optimization problem is an integer programming problem.
10. A method of solving a discrete optimization problem, the method comprising:
receiving an objective function and at least one constraint corresponding to the discrete optimization problem on a digital computer;
converting the objective function into a first set of inputs for a quantum computer;
converting the at least one constraint into a second set of inputs for the quantum computer;
generating a third set of inputs for the quantum computer wherein the third set of inputs is indicative of at least one penalty coefficient;
sending the first set of inputs, the second set of inputs and the third set of inputs to the quantum computer;
generating an initial Hamiltonian;
embedding the initial Hamiltonian onto the quantum computer;
evolving the quantum computer from the initial Hamiltonian to a final Hamiltonian wherein the final Hamiltonian corresponds to combining at least in part the first set of inputs, the second set of inputs and the third set of inputs;
performing a meta-optimization procedure on the final Hamiltonian to decompose the final Hamiltonian into a plurality of energy functions wherein each energy function is minimizable on the quantum computer;
reading out a final state of the final Hamiltonian wherein the final state of the quantum computer corresponds to at least a portion of a solution to the discrete optimization; and
returning at least a portion of the solution to the digital computer.
11. The method of claim 10 wherein at least one constraint is an inequality constraint, the method further comprising:
converting the inequality constraint into an equality constraint.
12. The method of claim 10 wherein converting the objective function includes converting at least one n-local interaction into a plurality of 2-local interactions, wherein n is greater than 2.
13. The method of claim 10 wherein sending the first set of inputs, the second set of inputs and the third set of inputs to the quantum processor occurs in a plurality of acts and wherein each act includes sending at least a portion of the first set of inputs, at least a portion of the second set of inputs and at least a portion of the third set of inputs to the quantum computer.
14. The method of claim 10 wherein the second set of inputs penalize each final state of the quantum computer that violates one of the constraints.
15. The method of claim 10 wherein the first set of inputs causes the final state of the quantum computer to be a minimum of the objective function.
16. The method of claim 15 wherein the minimum of the objective function is either a local minimum or a global minimum.
17. The method of claim 10 , further comprising:
generating a fourth set of inputs for the quantum computer wherein the fourth set of inputs is an increase of the value of at least one of the at least one penalty coefficient;
generating a second initial Hamiltonian;
embedding the second initial Hamiltonian onto the quantum computer;
evolving the quantum computer from the second initial Hamiltonian to a second final Hamiltonian wherein the second final Hamiltonian corresponds to combining at least in part the first set of inputs, the second set of inputs and the fourth set of inputs; and
reading out a second final state of the second final Hamiltonian.
18. The method of claim 10 wherein performing a meta-optimization procedure comprises at least one of cutset conditioning, large neighborhood local searching and min-propagation.
19. The method of claim 10 wherein the quantum computer includes at least one of an analog optimization device and an adiabatic quantum computer.