Systems and methods for problem solving, useful for example in quantum computing
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.
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 least one processor-based controller operatively coupled to at least one non-quantum post-processing processor-based device, the at least one processor-based controller which in use for each of the one or more iterations:
causes an execution of at least one post-processing operation on the plurality of samples by the at least one post-processing processor-based device to generate a set of post-processing results;
determines 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, causes the problem to be modified and initiates a further iteration.
18. The computational system of claim 17 wherein the at least one processor-based controller causes the iterations to cease for the problem in response to determining the result meets a determined satisfaction condition or the number of iterations equals a determined limit.
19. The computational system of claim 17 wherein the at least one processor that executes the heuristic optimizer is a quantum processor.
20. The computational system of claim 19 wherein an execution of at least one post-processing operation on the plurality of samples by the at least one post-processing processor-based device to generate a set of post-processing results includes execution 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, or a local field voting post-processing operation.
21. The computational system of claim 19 wherein the at least one heuristic optimizer includes a first optimizer caused by the at least one processor-based controller of the computational system to optimize the problem on a first iteration, and a second heuristic optimizer, different from the first heuristic optimizer, caused by the at least one processor-based controller of the computational system to optimize the problem on a second iteration.
22. The computational system of claim 19 wherein the at least one processor-based controller in use for at least one of the one or more iterations causes the execution of the at least one post-processing operation on the plurality of samples by the at least one post-processing processor-based device to generate a set of post-processing results to at least partially overlap in time with the generation of an immediately subsequent plurality of samples by at least one heuristic optimizer.
23. A computational system, comprising:
at least one processor-based device which includes:
at least one processor; and
at least one nontransitory processor-readable medium communicatively coupled to the at least one processor and which stores at least one of processor-executable instructions or data, and which when executed by the at least one processor causes the at least one processor, for each of a number of problems to:
perform a pre-processing assessment of the problem by a processor-based device;
select, 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; and
cause the problem to be optimized by the at least one selected heuristic optimizer.
24. The computational system of claim 23 wherein the at least one processor is a quantum processor.