Search All Patents in Quantum Computing
Patent US7877333
Issued 2011-01-25
Method And System For Solving Integer Programming And Discrete Optimization Problems Using Analog Processors
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.
Much More than Average Length Specification
View the Patent Matrix® Diagram to Explore the Claim Relationships
USPTO Full Text Publication >
- 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.
- 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.