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.
Claims20
A method of operation of a hybrid computing system, the hybrid computing system comprising a quantum processor and a classical processor, the method comprising:
- applying an algorithm to a problem having an input with n population variables via the classical processor;
- converting the input with n population variables to a reduced input with k population variables, where k≤n, via the classical processor, wherein converting the input with n population variables to a reduced input with k population variables, where k≤n, includes partitioning the n population variables into k clusters and contracting each of the k clusters to produce a reduced input with k population variables;
- obtaining samples Sr from the reduced input via the quantum processor;
- and
- expanding the samples Sr to obtain a set of modified states to the problem via the classical processor.
A hybrid computing system, the hybrid computing system comprising a quantum processor and a classical processor, the classical processor operable to:
- apply an algorithm to a problem having an input with n population variables;
- convert the input with n population variables to a reduced input with k population variables, where k≤n, wherein the classical processor is operable to partition the repopulation variables into k clusters and contract each of the k clusters to produce a reduced input with k variables;
- obtain samples Sr from the reduced input from the quantum processor;
- and
- expand the samples Sr to obtain a set of modified states to the problem.
A method of operation of a hybrid computing system, the hybrid computing system comprising a quantum processor and a classical processor, the method comprising:
- applying an algorithm to a problem having an input with n population variables via the classical processor;
- converting the input with n population variables to a reduced input with k population variables, where k≤n, via the classical processor;
- obtaining samples Sr from the reduced input via the quantum processor, wherein obtaining samples Sr from the reduced input via the quantum processor includes applying an embedding algorithm to the problem with the reduced input via the classical processor before obtaining samples Sr from the reduced input via the quantum processor;
- and
- expanding the samples Sr to obtain a set of modified states to the problem via the classical processor.
Dependencies are inferred from the claim text.