Systems and methods for hybrid algorithms using cluster contraction
Systems and methods are described for operating a hybrid computing system using cluster contraction for converting large, dense input to reduced input that can be easily mapped into a quantum processor. The reduced input represents the global structure of the problem. Techniques involve partitioning the input variables into clusters and contracting each cluster. The input variables can be partitioned using an Unweighted Pair Group Method with Arithmetic Mean algorithm. The quantum processor returns samples based on the reduced input and the samples are expanded to correspond to the original input.
1. A method of operation of a hybrid computing system, the hybrid computing system comprising a quantum processor and a classical processor, the method comprising:
generating a plurality of variable modification proposals relative to a state s on a problem via the classical processor, wherein no two proposals modify the same variable and no more than two proposals impact a term of a Quadratic Unconstrained Binary Optimization problem's cost function;
formulating a Quadratic Unconstrained Binary Optimization problem corresponding to an energy change of accepting a subset of the plurality of variable modification proposals via the classical processor; and
solving the Quadratic Unconstrained Binary Optimization problem via the quantum processor.
2. The method of claim 1 wherein generating a plurality of variable modification proposals on a problem includes generating a plurality of variable modification proposals on a problem consisting of one of: a Quadratic Constrained Binary Optimization problem and an Integer Quadratic Programming problem.
3. The method of claim 1 wherein generating a plurality of variable modification proposals relative to a state s includes generating a plurality of variable modification proposals on a problem relative to a random state s.
4. The method of claim 1 further comprising modifying the state s by accepting the subset of the plurality of variable modification proposals specified by solving the Quadratic Unconstrained Binary Optimization problem; and iteratively repeating, until an exit condition has been met:
generating a plurality of variable modification proposals relative to a state s n−1 via the classical processor;
formulating a Quadratic Unconstrained Binary Optimization problem corresponding to an energy change of accepting a subset of the variable modification proposals via the classical processor;
solving the Quadratic Unconstrained Binary Optimization problem via the quantum processor; and
modifying the state s n−1 to a state s n by accepting the subset of the proposals specified by solving the Quadratic Unconstrained Binary Optimization problem.
5. The method of claim 4 further comprising determining whether the exit condition has been met.
6. The method of claim 5 wherein determining whether the exit condition has been met includes determining whether at least one condition from the group of: a number of iterations and the state s n satisfying a measure of quality, has been met.
7. A hybrid computing system, the hybrid computing system comprising a classical processor and a quantum processor, the classical processor operable to:
generate a plurality of variable modification proposals relative to a state s on a problem, wherein no two proposals modify the same variable and no more than two proposals impact a term of a Quadratic Unconstrained Binary Optimization problem's cost function;
formulate a Quadratic Unconstrained Binary Optimization problem corresponding to an energy change of accepting a subset of the plurality of variable modification proposals; and
cause the quantum processor to solve the Quadratic Unconstrained Binary Optimization problem.
8. The system of claim 7 wherein the problem is at least one of: a Quadratic Constrained Binary Optimization problem and an Integer Quadratic Programming problem.
9. The system of claim 7 wherein the state s is a random state s.
10. The system of claim 7 wherein the classical processor is further operable to modify the state s by accepting the subset of the plurality of variable modification proposals specified by solving the Quadratic Unconstrained Binary Optimization problem; and iteratively repeat, until an exit condition has been met:
generate a plurality of variable modification proposals relative to a state s n−1 ;
formulate a Quadratic Unconstrained Binary Optimization problem corresponding to the an energy change of accepting a subset of the variable modification proposals;
cause the quantum processor to solve the Quadratic Unconstrained Binary Optimization problem; and
modify the state s n−1 to a state s n by accepting the subset of the proposals specified by solving the Quadratic Unconstrained Binary Optimization problem.
11. The system of claim 10 further comprising the classical processor operable to determine whether the exit condition has been met.
12. The system of claim 11 wherein the classical processor is operable to determine whether one of a group of exit conditions comprising: an elapsed number of iterations and the state s n satisfying a measure of quality, has been met.