Hybrid techniques to break down large graphs into smaller graphs

With the current D-Wave hardware, a K65 graph is the largest graph that has a minor embedding that can be mapped onto the 2000Q chip. To solve large problems with more than 65 nodes, hybrid classical-quantum techniques have to be used.

Are there hybrid techniques that systematically allow to obtain approximate solutions to large graph problems, by either splitting the original graph into smaller subgraphs and then by combining the results of the anneals on the small subgraphs, or by reducing the size of the original graph down to to a K65? If so, is it possible to use the Ocean SDK to implement such hybrid solutions?

1

Comments

2 comments
  • Hi Matthias,

    The Ocean SDK has a whole package devoted to hybrid solutions. Here's the link: https://docs.ocean.dwavesys.com/projects/hybrid/en/latest/intro/overview.html

    The tool uses the idea of splitting a large problem up into smaller sub problems that you're talking about. Here's a brief example that uses the hybrid workflow: https://docs.ocean.dwavesys.com/en/latest/examples/hybrid1.html#create-a-hybrid-workflow

     

    1
    Comment actions Permalink
  • Hi Matthias, 

    Yesterday we launched Leap 2 and I am happy to tell you that it is now much easier to solve problems that are larger than a D-Wave 2000Q QPU.  Please try using our new hybrid solver, which you will see on your Leap Dashboard as hybrid_v1. It accepts problems of up to 10,000 variables fully connected!

    Submit the problem through Ocean as you would any other problem to the D-Wave system, but specify the new LeapHybridSampler in your Python program:

    from dwave.system import LeapHybridSampler

    Take a look at our Knapsack example in Github, which is designed to demonstrate the usage of the hybrid solver.

    Let us know how it goes, 

    Fiona

    1
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post