Systems and methods for problem solving, useful for example in quantum computing

Patent metadata

Field	Value
Publication number	US-9881256-B2
Application number	US-201515505522-A
Country	US
Kind code	B2
Filing date	Aug 21, 2015
Priority date	Aug 22, 2014
Publication date	Jan 30, 2018
Grant date	Jan 30, 2018

Abstract

Computational systems implement problem solving using heuristic solvers or optimizers. Such may iteratively evaluate a result of processing, and modify the problem or representation thereof before repeating processing on the modified problem, until a termination condition is reached. Heuristic solvers or optimizers may execute on one or more digital processors and/or one or more quantum processors. The system may autonomously select between types of hardware devices and/or types of heuristic optimization algorithms. Such may coordinate or at least partially overlap post-processing operations with processing operations, for instance performing post-processing on an ith batch of samples while generating an (i+1)th batch of samples, e.g., so post-processing operation on the ith batch of samples does not extend in time beyond the generation of the (i+1)th batch of samples. Heuristic optimizers selection is based on pre-processing assessment of the problem, e.g., based on features extracted from the problem and for instance, on predicted success.

First claim

The invention claimed is:

1. A method of operation in a computational system, the method comprising:
receiving a problem; and
for a number of iterations i to a number n where n is a positive integer:
causing a solver to be executed by at least one processor to generate a plurality of samples as potential solutions to the problem;
causing, by at least one controller, a performing of at least one post-processing operation on the plurality of samples by at least one post-processing non-quantum processor-based device to generate a set of post-processing results;
determining whether to modify the problem based at least in part on the set of post-processing results;
upon determining to modify the problem based at least in part on the set of post-processing results, the i th iteration further comprising:
causing the problem to be modified; and
initiating an (i+) th iteration.

2. The method of claim 1 wherein causing a solver to be executed by at least one processor to generate a plurality of samples as potential solutions to the problem includes causing the problem to be optimized by at least one heuristic optimizer executed by at least one processor to generate a plurality of samples as potential solutions to the problem.

3. The method of claim 2 wherein determining whether to modify the problem based at least in part on the set of post-processing results includes at least one of comparing a result to a determined satisfaction condition or comparing the number of iterations performed to a determined limit.

4. The method of claim 2 wherein the at least one processor is a quantum processor.

5. The method of claim 4 wherein causing a performing of at least one post-processing operation by at least one non-quantum processor-based device includes causing a performing of at least one of: a majority voting post-processing operation, a greedy descent post-processing operation, a variable clamping post-processing operation, a variable branching post-processing operation, a local field voting post-processing operation, a local search to find a local minimum post-processing operation, a Markov Chain Monte Carlo simulation at a fixed temperature post-processing operation, and a Metropolis sampling post-processing operation, by at least one digital processor.

6. The method of claim 4 wherein on a first iteration, causing the problem to be optimized by at least one heuristic optimizer executed by at least one processor includes, causing the problem to be optimized by a first heuristic optimizer executed by at least one processor, and on a second iteration, causing the problem to be optimized by at least one heuristic optimizer executed by at least one processor includes, causing the problem to be optimized by a second heuristic optimizer executed by at least one processor, wherein the second heuristic optimizer is different from the first heuristic optimizer.

7. The method of claim 4 , wherein causing the problem to be optimized by at least one heuristic optimizer includes
autonomously selecting, by at least one component of the computational system, a heuristic optimizer from a plurality of types of heuristic optimizers.

8. The method of claim 4 wherein n is an integer greater than 2, and the performing of at least one post-processing operation on the i th plurality of samples by the at least one post-processing non-quantum processor-based device to generate the i th set of post-processing results occurs at least partially overlapping in time with the optimization by at least one heuristic optimizer executed by at least one processor to generate the (i+1) th plurality of samples, for values of i between 2 and (n−1).

9. The method of claim 8 wherein the performing of the at least one post-processing operation on the i th plurality of samples by the at least one post-processing non-quantum processor-based device to generate the i th set of post-processing results does not extend in time beyond the optimization by at least one heuristic optimizer executed by at least one processor to generate the (i+1) th plurality of samples.

10. The method of claim 4 wherein n is an integer greater than 2, and for iterations having values of i between 2 and (n−1), the method further comprising determining a timing of the optimization by at least one heuristic optimizer executed by at least one processor to generate the (i+1) th plurality of samples, wherein the performing of at least one post-processing operation on the i th plurality of samples by the at least one post-processing non-quantum processor-based device to generate the i th set of post-processing results occurs at least partially overlapping in time with the optimization by at least one heuristic optimizer executed by at least one processor to generate the (i+1) th plurality of samples.

11. The method of claim 4 further comprising:
performing a pre-processing assessment of the problem by a processor-based device; and
selecting, by the processor-based device, at least one heuristic optimizer from a plurality of heuristic optimizers based at least in part on the pre-processing assessment of the problem.

12. The method of claim 11 wherein receiving the problem includes:
determining a format of the problem; and
determining whether the determined format of the problem is a supported format, and the method further cormrising;
rejecting the problem in response to determining that the determined format of the problem is not supported; and
providing a notification of the rejection of the problem to a user by at least one component of the computational system.

13. The method of claim 12 , further comprising:
in response to the format of the problem being supported, generating a plurality of representations of the problem by the processor-based device;
for each of the representations of the problem,
extracting a number of features from the problem;
at least one of assessing or evaluating each of a plurality of heuristic optimizers based at least in part on the extracted features;
selecting one or more heuristic optimizers based on at least one of the evaluation or the assessment by the processor-based device; and
causing the selected one or more heuristic optimizers to operate on the problem.

14. The method of claim 13 wherein selecting one or more heuristic optimizers based on the evaluation by the processor-based device includes autonomously selecting one or more heuristic optimizers based on at least one of the assessment or the evaluation by the processor-based device.

15. The method of claim 13 wherein evaluating each of a plurality of heuristic optimizers based at least in part on the extracted features includes predicting how successful each of the heuristic optimizers of the plurality of heuristic optimizers would be in returning an optimal solution for the problem using the extracted features.

16. The method of claim 13 wherein at least two heuristic optimizers are selected, the at least two heuristic optimizers different from one another, and further comprising:
comparing the results from each of the selected at least two heuristic optimizers; and
determining a preferred solution based at least in part on the comparison.

17. A computational system, comprising:
at least one processor-based controller, the at least one processor-based controller communicatively coupled to at least one heuristic optimizer which in operation for each of one or more iterations generates a plurality of samples as potential solutions of a problem, the at least one heuristic optimizer executed by at least one processor, the at

Assignees

• D Wave Systems Inc

Inventors

• Hamze Firas
• King Andrew Douglas
• Raymond Jack
• Roy Aidan Patrick
• Israel Robert
• Andriyash Evgeny
• Mcgeoch Catherine
• Ranjbar Mani

Classifications

• G06F15/76

  Architectures of general purpose stored program computers (with program plugboard G06F15/08; multicomputers G06F15/16) · CPC title

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06N3/12

  using genetic models · CPC title

• G06F9/02

  using wired connections, e.g. plugboards · CPC title

• G06N99/002 Primary

  Physics · mapped topic