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. How to solve such a problem with D-Wave’s 2000Q QPU

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

Note

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.