Search All Patents in Quantum Computing
Patent US10275423
Issued 2019-04-30
Method And System For Continuous Optimization Using A Binary Sampling Device
A method and system are disclosed for continuous optimization. The method comprises obtaining an optimization problem involving continuous or semi-continuous variables in a digital computer; initiating a stochastic search process in the digital computer in order to solve the optimization problem; until a stopping criterion is met constructing in the digital computer at least one stochastically generated polynomial in binary variables representative of choices of candidate future state of the stochastic search process, providing the at least one polynomial in binary variables to a binary sampling device, sampling from domains of the at least one polynomial in binary variables using the binary sampling device to generate binary sample points, receiving the generated binary sample points in the digital computer and transiting to next state of the stochastic search process and providing a best known solution found as a solution of the optimization problem using the digital computer.
Much More than Average Length Specification
View the Patent Matrix® Diagram to Explore the Claim Relationships
USPTO Full Text Publication >
- 1. A method for continuous optimization using a stochastic search process, the method comprising:
obtaining an optimization problem involving a plurality of discrete variables and at least one continuous or semi-continuous variables in a digital computer; initiating a stochastic search process respecting a neighborhood structure of the plurality of discrete variables in the digital computer in order to solve the optimization problem; until a stopping criterion is met:
constructing in the digital computer at least one stochastically generated polynomial in binary variables representative of choices of candidate future state of the stochastic search process using an affine transformation of domains of the at least one polynomial,
providing the at least one polynomial in binary variables to a binary sampling device, wherein the binary sampling device is configured to simulate or implement quantum annealing,
sampling from the domains of the at least one polynomial in binary variables using the binary sampling device to generate binary sample points,
receiving the generated binary sample points in the digital computer and transiting to next state of the stochastic search process; and
providing a best known solution found as a solution of the optimization problem using the digital computer.
- 7. A digital computer comprising:
a central processing unit; a display device; a communication port for operatively connecting the digital computer to a binary sampling device, wherein the binary sampling device is configured to simulate or implement quantum annealing; a memory unit comprising an application for continuous optimization using a stochastic search process, the application comprising:
instructions for obtaining an optimization problem involving a plurality of discrete variables and at least one continuous or semi-continuous variables;
instructions for initiating a stochastic search process respecting a neighborhood structure of the plurality of discrete variables in order to solve the optimization problem;
instructions for, until a stopping criterion is met:
constructing at least one stochastically generated polynomial in binary variables representative of choices of candidate future state of the stochastic search process using an affine transformation of domains of the at least one polynomial,
providing the at least one stochastically generated polynomial in binary variables to the binary sampling device via the communication port,
receiving generated binary sample points obtained by sampling from the domains of the at least one stochastically generated polynomial in binary variables using the binary sampling device and transiting to next state of the stochastic search process; and
instructions for providing a best known solution found as a solution of the optimization problem.
- 8. A non-transitory computer-readable storage medium for storing computer-executable instructions which, when executed, cause a digital computer to perform a method for continuous optimization using a stochastic search process, the method comprising:
obtaining an optimization problem involving a plurality of discrete variables and at least one continuous or semi-continuous variables; initiating a stochastic search process respecting a neighborhood structure of the plurality of discrete variables in order to solve the optimization problem; until a stopping criterion is met:
constructing at least one stochastically generated polynomial in binary variables representative of choices of candidate future state of the stochastic search process using an affine transformation of domains of the at least one polynomial,
providing the at least one stochastically generated polynomial in binary variables to a binary sampling device, wherein the binary sampling device is configured to simulate or implement quantum annealing, and
receiving generated binary sample points obtained by sampling from the domains of the at least one stochastically generated polynomial in binary variables using the binary sampling device and transiting to next state of the stochastic search process; and
providing a best known solution found as a solution of the optimization problem.
- 9. A method for continuous optimization using a stochastic search process, the method comprising:
obtaining, in a digital computer, an optimization problem involving a plurality of discrete variables and at least one continuous or semi-continuous variables; initiating a stochastic search process in the digital computer in order to solve the optimization problem, wherein the stochastic search process respects a neighborhood structure of the plurality of discrete variables; until a stopping criterion is met:
constructing in the digital computer at least one stochastically generated polynomial in binary variables representative of choices of candidate future state of the stochastic search process using an affine transformation of domains of the at least one polynomial,
providing the at least one stochastically generated polynomial in binary variables to a binary sampling device, wherein the binary sampling device is configured to simulate or implement quantum annealing,
receiving, in the digital computer, generated binary sample points obtained by sampling from the domains of the at least one stochastically generated polynomial in binary variables using the binary sampling device, and
transiting to next state of the stochastic search process; and
providing a best known solution found as a solution of the optimization problem using the digital computer.