Method and system for solving integer programming and discrete optimization problems using analog processors
AssigneeD-Wave Systems Inc.
InventorWilliam Macready
Life of this patent
Estimating the term…
Abstract
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.
Claims19
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.
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.
Dependencies are inferred from the claim text.