class QuantumAnnealer[source]

QuantumAnnealer(graph=None, task=None, qubo=None, backend='local', device_arn=None, s3_folder=None)

quantum-based combinatorial optimization with Amazon Braket

Usage:

>>> qo = QuantumAnnealer(g,
                        task='maximum_clique',
                        device_arn='device_arn', # optional
                        s3_folder='s3_folder')   # optional
    qo.execute()
    results = qo.results()

Parameters:

• graph : a networkx Graph object
• task : task as str. Invoke supported_tasks static method to see options.
• qubo : Coefficients of a quadratic unconstrained binary optimization

         (QUBO) problem. Should be a dict of the form `{(u, v): bias, ...}`
         where `u`, `v`, are binary-valued variables and `bias` is their
         associated coefficient.
         If qubo supplied, then graph and task parameters are not needed.

• backend : One of {'local', 'aws', 'dwave'} where:

             - `local`: use a local solver (simulated annealing on your laptop)
             - `aws`: use Amazon Braket (`device_arn` and `3_folder` args required)
             - `dwave`: use D-Wave Leap System default solver as specified in `<home_directory/.config/dwave/dwave.conf

• device_arn : Device ARN. Only required if not running locally.

• s3_folder : S3 folder. Only required if not running locally.

QuantumAnnealer.execute[source]

QuantumAnnealer.execute(verbose=1, force_exact=False, **kwargs)

Approximate a solution to given task. Simulated Annealing (or exact solver for small problems) is used when QuantumAnnealer.local=True. Quantum Annealing is used when QuantumAnnealer.local=False. If force_exact=True, an exact solver will be used regardless of QuantumAnnealer.local.

QuantumAnnealer.results[source]

QuantumAnnealer.results(**kwargs)

Return approximated solution

QuantumAnnealer.supported_tasks[source]

QuantumAnnealer.supported_tasks()

Prints supported tasks (valid values for the task parameter).

Example: Minimum Vertex Cover with Quantum Annealing

The task is to find the nodes comprising the minimum vertex cover in a graph. Let's construct a small star graph as input.

import networkx as nx

n = 6
g = nx.star_graph(n-1) 
seed = 1967
positions = nx.spring_layout(g, seed=seed)
nx.draw(g, with_labels=True, pos=positions)

qo = QuantumAnnealer(g, task='minimum_vertex_cover')

qo.execute()

Executing locally.

<__main__.QuantumAnnealer at 0x7f9e3738c160>

nodes = qo.results()

nodes

[0]

sub = g.subgraph(nodes)
nx.draw(g, pos=positions, with_labels=True)
nx.draw(sub, pos=positions, node_color="r", edge_color="r")

assert set(nodes) == set([0])

Using a BinaryQuadraticModel

For more flexibility, you can formulate your task as a quadratic unconstrained binary optimization problem (QUBO) and supply that to QuantumAnnealer instead. Here, we will solve the same minimum vertex cover problem by formulating it as a QUBO expressed as a Python dictionary. See this reference for more details on how to formulate problems as binary quadratic models.

cost = dict(g.nodes(data=None, default=1))
scale = max(cost.values())
Q = {(node, node): min(-cost[node] / scale, 0.0) for node in g}
Q.update({edge: 2.0 for edge in g.edges}) # use 2.0 as "tuning" LaGrange value for this problem

# solve qubo
independent_set = QuantumAnnealer(qubo=Q).execute().results()

# nodes NOT in the independent set comprise the minimum vertex cover
solution_nodes = [v for v in g if v not in independent_set]
assert set(solution_nodes) == set([0])

# plot solution as graph
sub = g.subgraph(solution_nodes)
nx.draw(g, pos=positions, with_labels=True)
nx.draw(sub, pos=positions, node_color="r", edge_color="r")

Executing locally.