[ ]:

%%capture
!pip install  --quiet cirq==0.7


# QAOA Experiment¶

In this experiment, you are going to implement a hardware compatible QAOA algorithm for determining the Max-Cut of the processor’s hardware graph (where you assign random edge weights). You will need to:

1. Define a random set of weights over the hardware graph.

2. Construct a QAOA circuit using Cirq

3. Calculate the expected value of the QAOA cost function.

4. Create an outer loop optimization to minimize your cost function.

5. Compare cuts found from QAOA with the optimal cut.

## 1. Defining a random set of weights over the hardware graph¶

In order to make the problem easily embeddable on a quantum device you are going to look at the problem of Max-Cut on the same graph that the device’s qubit connectivity defines, but with random valued edge weights.

[16]:

import cirq
import sympy
import numpy as np
import matplotlib.pyplot as plt
print(working_device)

                                             (0, 5)────(0, 6)
│         │
│         │
(1, 4)───(1, 5)────(1, 6)────(1, 7)
│        │         │         │
│        │         │         │
(2, 3)───(2, 4)───(2, 5)────(2, 6)────(2, 7)───(2, 8)
│        │        │         │         │        │
│        │        │         │         │        │
(3, 2)───(3, 3)───(3, 4)───(3, 5)────(3, 6)────(3, 7)───(3, 8)───(3, 9)
│        │        │        │         │         │        │        │
│        │        │        │         │         │        │        │
(4, 1)───(4, 2)───(4, 3)───(4, 4)───(4, 5)────(4, 6)────(4, 7)───(4, 8)───(4, 9)───(4, 10)
│        │        │        │        │         │         │        │        │        │
│        │        │        │        │         │         │        │        │        │
(5, 0)───(5, 1)───(5, 2)───(5, 3)───(5, 4)───(5, 5)────(5, 6)────(5, 7)───(5, 8)───(5, 9)───(5, 10)───(5, 11)
│        │        │        │        │         │         │        │        │        │
│        │        │        │        │         │         │        │        │        │
(6, 1)───(6, 2)───(6, 3)───(6, 4)───(6, 5)────(6, 6)────(6, 7)───(6, 8)───(6, 9)───(6, 10)
│        │        │        │         │         │        │        │
│        │        │        │         │         │        │        │
(7, 2)───(7, 3)───(7, 4)───(7, 5)────(7, 6)────(7, 7)───(7, 8)───(7, 9)
│        │        │         │         │        │
│        │        │         │         │        │
(8, 3)───(8, 4)───(8, 5)────(8, 6)────(8, 7)───(8, 8)
│        │         │         │
│        │         │         │
(9, 4)───(9, 5)────(9, 6)────(9, 7)
│         │
│         │
(10, 5)───(10, 6)


Since a circuit covering the entire Bristlecone device cannot be easily simulated, a small subset of the device graph will be used instead.

[17]:

import networkx as nx

# Identify working qubits from the device.
device_qubits = working_device.qubits
working_qubits = sorted(device_qubits)[:12]

# Populate a networkx graph with working_qubits as nodes.
working_graph = nx.Graph()
for qubit in working_qubits:

# Pair up all neighbors with random weights in working_graph.
for qubit in working_qubits:
for neighbor in working_device.neighbors_of(qubit):
if neighbor in working_graph:
# Generate a randomly weighted edge between them. Here the weighting
# is a random 2 decimal floating point between 0 and 5.
qubit, neighbor, weight=np.random.randint(0,500) / 100)

nx.draw_circular(working_graph, node_size=1000, with_labels=True)
plt.show()

/usr/local/lib/python3.6/dist-packages/networkx/drawing/nx_pylab.py:579: MatplotlibDeprecationWarning:
The iterable function was deprecated in Matplotlib 3.1 and will be removed in 3.3. Use np.iterable instead.
if not cb.iterable(width):


## 2. Construct the QAOA circuit¶

Now that you have created a Max-Cut problem graph, it’s time to generate the QAOA circuit following Farhi et al.. For simplicity $$p=1$$ is chosen.

[18]:

from cirq.contrib.svg import SVGCircuit

alpha = sympy.Symbol('alpha')
beta = sympy.Symbol('beta')

qaoa_circuit = cirq.Circuit(
# Prepare uniform superposition on working_qubits == working_graph.nodes
cirq.H.on_each(working_graph.nodes()),

# Do ZZ operations between neighbors u,v in the graph. u is a qubit v is
# its neighbor qubit and w is the weight between these qubits.
(cirq.ZZ(u, v) ** (alpha * w['weight']) for (u, v, w) in working_graph.edges(data=True)),

# Apply X operations along all nodes of the graph. Again working_graph's
# nodes are the working_qubits. Not here we use a moment
# which will force all of the gates into the same line.
cirq.Moment(cirq.X(qubit) ** beta for qubit in working_graph.nodes()),

# All relevant things can be computed in computational basis.
(cirq.measure(qubit) for qubit in working_graph.nodes()),
)
SVGCircuit(qaoa_circuit)

[18]:


## 3. Calculating the expected value of the QAOA cost function¶

Now that you have created your parameterized QAOA circuit, you are going to need a way to calculate the expectation values of the cost function. Since the cost function is the (weighted) sum of all $$ZZ$$ pairs in the graph you can compute all of these values simultaneously.

First you need a way to estimate the expectation value given the samples from each qubit.

[ ]:

def estimate_cost(graph, samples):
"""Estimate the cost function of the QAOA on the given graph using the
provided computational basis bitstrings."""
cost_value = 0.0

# Loop over edge pairs and compute contribution.
for u, v, w in graph.edges(data=True):
u_samples = samples[str(u)]
v_samples = samples[str(v)]

# Determine if it was a +1 or -1 eigenvalue.
u_signs = (-1)**u_samples
v_signs = (-1)**v_samples
term_signs = u_signs * v_signs

# Add scaled term to total cost .
term_val = np.mean(term_signs) * w['weight']
cost_value += term_val

return -cost_value


Now if you run qaoa_circuit with a certain set of values for your placeholders you can use estimate_expectation to calculate the expectation value of the cost function for the circuit:

[20]:

alpha_value = np.pi / 4
beta_value = np.pi / 2
sim = cirq.Simulator()
sample_results = sim.sample(qaoa_circuit, params={alpha: alpha_value, beta: beta_value}, repetitions=20000)
print(f'Alpha={alpha_value} Beta={beta_value}')
print(f'Estimated cost: {estimate_cost(working_graph, sample_results)}')

Alpha=0.7853981633974483 Beta=1.5707963267948966
Estimated cost: -1.2681320000000003


## 4. Outer loop optimization¶

There are lots of different techniques to choose parameters for qaoa_circuit. When there are only two parameters you can keep things simple and sweep over incremental pairings using np.linspace and track the minimum value you’ve found along the way.

[ ]:

grid_size = 5
exp_values = np.empty((grid_size, grid_size))
par_values = np.empty((grid_size, grid_size, 2))
for i, alpha_value in enumerate(np.linspace(0, 2*np.pi, grid_size)):
for j, beta_value in enumerate(np.linspace(0, 2*np.pi, grid_size)):
samples = sim.sample(
qaoa_circuit,
params={alpha: alpha_value, beta: beta_value},
repetitions=20000)
exp_values[i][j] = estimate_cost(working_graph, samples)
par_values[i][j] = alpha_value, beta_value


You can also examine the cost function values w.r.t $$\alpha$$ and $$\beta$$:

[22]:

plt.title('Heamap of QAOA Cost Function Value')
plt.xlabel(r'$\alpha$')
plt.ylabel(r'$\beta$')
plt.imshow(exp_values)

[22]:

<matplotlib.image.AxesImage at 0x7fadd136c5f8>


## 5. Compare cuts¶

Since you are going to be comparing graph cuts in working_graph a helper function to draw them and print their the size would be useful:

[23]:

def output_cut(S_partition):
"""Plot and output the graph cut information."""

# Generate the colors.
coloring = []
for node in working_graph:
if node in S_partition:
coloring.append('blue')
else:
coloring.append('red')

# Get the weights
edges = working_graph.edges(data=True)
weights = [w['weight'] for (u,v, w) in edges]

nx.draw_circular(
working_graph,
node_color=coloring,
node_size=1000,
with_labels=True,
width=weights)
plt.show()
size = nx.cut_size(working_graph, S_partition, weight='weight')
print(f'Cut size:{size}')

# Test with the empty S and all nodes placed in T.
output_cut([])

/usr/local/lib/python3.6/dist-packages/networkx/drawing/nx_pylab.py:579: MatplotlibDeprecationWarning:
The iterable function was deprecated in Matplotlib 3.1 and will be removed in 3.3. Use np.iterable instead.
if not cb.iterable(width):

Cut size:0


To get cuts using the QAOA you will first need to extract the best control parameters you found during your sweep:

[24]:

best_exp_index = np.unravel_index(np.argmax(exp_values), exp_values.shape)
best_parameters = par_values[best_exp_index]
print(f'Best control parameters:{best_parameters}')

Best control parameters:[3.14159265 6.28318531]


Each bitstring can be seen as a candidate cut in your graph. The qubits that measured 0 correspond to that qubit being in one cut partition and a qubit that measured to 1 corresponds to that qubit being in the other cut partition. Now that you’ve found good parameters for your circuit, you can just sample some bistrings, iterate over them and pick the one that gives the best cut:

[ ]:

# Number of candidate cuts to sample.
num_cuts = 100
candidate_cuts = sim.sample(
qaoa_circuit,
params={alpha: best_parameters[0], beta: best_parameters[1]},
repetitions=num_cuts)

# Variables to store best cut partitions and cut size.
best_qaoa_S_partition = set()
best_qaoa_T_partition = set()
best_qaoa_cut_size = -9999

# Analyze each candidate cut.
for i in range(num_cuts):
candidate = candidate_cuts.iloc[i]
one_qubits = set(candidate[candidate==1].index)
S_partition = set()
T_partition = set()
for node in working_graph:
if str(node) in one_qubits:
# If a one was measured add node to S partition.
else:
# Otherwise a zero was measured so add to T partition.

cut_size = nx.cut_size(
working_graph, S_partition, T_partition, weight='weight')

# If you found a better cut update best_qaoa_cut variables.
if cut_size > best_qaoa_cut_size:
best_qaoa_cut_size = cut_size
best_qaoa_S_partition = S_partition
best_qaoa_T_partition = T_partition


The QAOA is known to do just a little better better than random guessing for Max-Cut on 3-regular graphs at p=1. You can use very similar logic to the code above, but now instead of relying on the QAOA to decied your S_partition and T_partition you can just pick then randomly:

[ ]:

import random

best_random_S_partition = set()
best_random_T_partition = set()
best_random_cut_size = -9999

# Randomly build candidate sets.
for i in range(num_cuts):
S_partition = set()
T_partition = set()
for node in working_graph:
if random.random() > 0.5:
else:

cut_size = nx.cut_size(
working_graph, S_partition, T_partition, weight='weight')

# If you found a better cut update best_random_cut variables.
if cut_size > best_random_cut_size:
best_random_cut_size = cut_size
best_random_S_partition = S_partition
best_random_T_partition = T_partition

[27]:

print('-----QAOA-----')
output_cut(best_qaoa_S_partition)

print('-----RANDOM-----')
output_cut(best_random_S_partition)

-----QAOA-----

/usr/local/lib/python3.6/dist-packages/networkx/drawing/nx_pylab.py:579: MatplotlibDeprecationWarning:
The iterable function was deprecated in Matplotlib 3.1 and will be removed in 3.3. Use np.iterable instead.
if not cb.iterable(width):

Cut size:29.93
-----RANDOM-----

Cut size:32.809999999999995

[ ]: