Systems and methods for hybrid quantum-classical computing
Hybrid quantum-classical approaches for solving computational problems in which results from a quantum processor are combined with an exact method executed on a classical processor are described. Quantum processors can generate candidate solutions to a combinatorial optimization problem, but since quantum processors can be probabilistic, they are unable to certify that a solution is an optimal solution. A hybrid quantum-classical exact solver addresses this problem by combining outputs from a quantum annealing processor with a classical exact algorithm that is modified to exploit properties of the quantum computation. The exact method executed on a classical processor can be a Branch and Bound algorithm. A Branch and Bound algorithm can be modified to exploit properties of quantum computation including a) the sampling of multiple low-energy solutions by a quantum processor, and b) the embedding of solutions in a regular structure such as a native hardware graph of a quantum processor.
1. A method of operation in a computational system to solve a problem having at least one optimal solution, the computational system comprising a quantum processor and at least one non-quantum processor, the method performed by the at least one non-quantum processor and comprising:
embedding the problem into a regular structure on the quantum processor as an embedded problem;
instructing, by the at least one non-quantum processor, performance of quantum annealing by the quantum processor to generate a plurality of samples, wherein each sample of the plurality of samples is representative of a potential solution to the embedded problem;
determining, by the at least one non-quantum processor, one or more solver parameters of a Branch-and-Bound algorithm based at least on the plurality of samples generated by the quantum processor, wherein the determining the one or more solver parameters includes computation of one or more of: an initial bound of the Branch-and-Bound algorithm, magnetizations of the plurality of samples, and correlations of the plurality of samples; and
executing, by the at least one non-quantum processor, the Branch-and-Bound algorithm having the determined one or more solver parameters to generate the at least one optimal solution to the problem.
2. The method of claim 1 wherein embedding, by the at least one non-quantum processor, the problem into a regular structure to produce an embedded problem includes embedding the problem into a topology of the quantum processor to produce the embedded problem.
3. The method of claim 1 wherein the determining by the at least one non-quantum processor, one or more solver parameters of a Branch-and-Bound algorithm based at least on the plurality of samples generated by the quantum processor, comprises statistically analyzing the plurality of samples.
4. The method of claim 1 further comprising iteratively performing the instructing, by the at least one non-quantum processor, performance of quantum annealing by the quantum processor to generate the plurality of samples, wherein each sample of the plurality of samples is representative of a potential solution to the embedded problem, before the determining by the at least one non-quantum processor, the one or more solver parameters of the Branch-and-Bound algorithm based at least one the plurality of samples generated by the quantum processor.
5. The method of claim 1 wherein the executing, by the at least one non-quantum processor, the Branch-and-Bound algorithm having the determined one or more solver parameters to generate the at least one optimal solution to the problem, includes executing, by the at least one non-quantum processor, the Branch-and-Bound algorithm having the determined one or more solver parameters to generate multiple optimal solutions.
6. The method of claim 1 wherein the instructing, by the at least one non-quantum processor, performance of quantum annealing by the quantum processor and the executing, by the at least one non-quantum processor, the Branch-and-Bound algorithm having the determined one or more solver parameters are concurrent operations, overlapping at least a portion thereof.
7. The method of claim 6 further comprising updating, by the at least one non-quantum processor, the one or more solver parameters of the Branch-and-Bound algorithm as the plurality of samples are generated from the quantum processor.
8. A computational system comprising a quantum processor and at least one non-quantum processor, the at least one non-quantum processor operable to:
embed a problem having at least one optimal solution into a regular structure on the quantum processor as an embedded problem;
instruct performance of quantum annealing by the quantum processor to generate a plurality of samples, wherein each sample of the plurality of samples is representative of a potential solution to the embedded;
determine one or more solver parameters of a Branch-and-Bound algorithm based at least on the plurality of samples generated by the quantum processor, wherein the one or more solver parameters are one or more of: an initial bound of the Branch-and-Bound algorithm, magnetizations of the plurality of samples, and correlations of the plurality of sample; and
execute the Branch-and-Bound algorithm having the determined one or more solver parameters to generate the at least one optimal solution to the problem.
9. The computational system of claim 8 wherein the at least one non-quantum processor is operable to embed the problem into a topology of the quantum processor to produce the embedded problem.
10. The computational system of claim 8 wherein the at least one non-quantum processor is operable to statistically analyzes the plurality of samples.
11. The computational system of claim 8 , wherein the at least one non-quantum processor is further operable to iteratively instruct performance of quantum annealing by the quantum processor to generate a plurality of samples as potential solutions to the problem.
12. The computational system of claim 8 wherein the at least one non-quantum processor is operable to execute the Branch-and-Bound algorithm having the determined one or more solver parameters to generate multiple optimal solutions.
13. The system of claim 8 wherein the at least one non-quantum processor is operable to instruct performance of quantum annealing by the quantum processor to generate a plurality of samples concurrently with execution of the Branch-and-Bound algorithm having the determined one or more solver parameters, overlapping at least a portion thereof.
14. The system of claim 13 wherein the at least one non-quantum processor is operable to update the one or more solver parameters of the Branch-and-Bound algorithm as the plurality of samples are generated from the quantum processor.