Systems and methods for hybrid algorithms using cluster contraction
AssigneeD-Wave Systems Inc.
InventorsJames A. King, William W. Bernoudy, Kelly T. R. Boothby, Pau Farré Pérez
Life of this patent
Estimating the term…
Abstract
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.
Claims12
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.
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.
Dependencies are inferred from the claim text.