Run your first annealing problem with Ocean - Amazon Braket

Run your first annealing problem with Ocean

Quantum annealers are special-purpose quantum computers designed to solve combinatorial optimization problems. In particular, quantum annealers solve problems belonging to the class of Quadratic Unconstrained Optimization (QUBO). Amazon Braket allows you to program the D-Wave QPUs natively using D-Wave’s Ocean software through the Braket-Ocean plugin. Amazon Braket notebook instances are pre-installed with Ocean and the Braket-Ocean plugin.

Get started with a simple example of solving the Minimum Vertex Cover (MVC) problem. Here’s the problem definition:

Given an undirected graph with a vertex set and an edge set, a vertex cover is a subset of the vertices (nodes) such that each edge in the graph is incident to at least one vertex in the subset. The Minimum Vertex Cover problem seeks to find a cover with a minimum number of vertices in the subset. In other words, in a graph like this:


The goal is to color nodes in red such that every edge touches at least one red node. And you want to do it with as little paint as possible. The optimal solution is to paint the central node red as shown in the figure that follows.

            color graph

How to solve such a problem with D-Wave’s 2000Q QPU

To begin, import the following dependencies and specify an S3 location.


Fill in your actual, existing bucket name where the following example shows example-bucket as your bucket name. Bucket names for Amazon Braket always begin with amazon-braket- followed by other identifying characters you add.

# import relevant modules import boto3 from braket.ocean_plugin import BraketSampler, BraketDWaveSampler import networkx as nx import dwave_networkx as dnx from dwave.system.composites import EmbeddingComposite # Please enter any S3 bucket starting with 'amazon-braket-' in your account in the code below my_bucket = f"amazon-braket-Your-Bucket-Name" # the name of the bucket my_prefix = "Your-Folder-Name" # the name of the folder in the bucket s3_folder = (my_bucket, my_prefix)

Now, set the sampler. Then use EmbeddingComposite to minor-embed a problem automatically into a structured sampler, such as a D-Wave system.

# set sampler using BraketSampler sampler = BraketSampler(s3_folder,'arn:aws:braket:::device/qpu/d-wave/DW_2000Q_6') # or alternatively using BraketDWaveSampler sampler = BraketDWaveSampler(s3_folder,'arn:aws:braket:::device/qpu/d-wave/DW_2000Q_6') # EmbeddingComposite automatically maps the problem to the structure of the solver. embedded_sampler = EmbeddingComposite(sampler)

You can create the graph from the family of random Erdoes-Renyi graphs. Such a graph can be generated using the networkx library. As input, set the desired number of vertices and edges connecting pairs of vertices.

# setup Erdos Renyi graph # 5 nodes n = 5 # 10 edges m = 10 # generate graph graph = nx.gnm_random_graph(n, m, seed=42)

Finally, run the problem in D-Wave and print the results.

# run the problem on D-Wave using BraketSampler result = dnx.min_vertex_cover(graph, embedded_sampler, resultFormat="HISTOGRAM") # or alternatively using BraketDWaveSampler result = dnx.min_vertex_cover(graph, embedded_sampler, answer_mode="histogram") print('Result to MVC problem:', result) print('Size of the vertex cover:', len(result))
Result to MVC problem: [0, 1, 3, 4] Size of the vertex cover: 4

Notice that the result to the MVC problem is a list containing the vertices [0, 1, 3, 4]. These vertices form a minimum vertex cover such that the subset can reach every edge in the graph.