11 - Using Different Mixer Hamiltonians
One of the defining features of QAOA ansatz is the alternate application of the cost and mixer Hamiltonians. While the cost Hamiltonian tends to be defined by the problem at hand, the choice of mixer Hamiltonians is not as obvious. In OpenQAOA, we provide multiple utility functions that help create commonly used mixer Hamiltonians, such as the X and XY mixer Hamiltonians.
In this notebook, we provide the user with examples on how they can use these utility functions to quickly construct their mixer Hamiltonians. Furthermore, we will introduce a feature in OpenQAOA, inspired by Hadfield et. al in [1], which allows the user to design their own custom mixer operators.
[1]:
%matplotlib inline
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from openqaoa.utilities import plot_graph, ground_state_hamiltonian
from openqaoa.backends import create_device
from openqaoa.problems import MinimumVertexCover
from openqaoa import QAOA
Setting Up the Problem
For the examples in this notebook, we will be using the Minimum Vertex Cover problem. The problem statement goes as follows: Given a graph, identify the smallest subset of nodes such that all other nodes are connected to any node in that subset by at least 1 edge.
[2]:
nodes = 6
edge_probability = 0.7
g = nx.generators.fast_gnp_random_graph(n=nodes,p=edge_probability, seed=34)
pos = nx.spring_layout(g)
plot_graph(g)
[3]:
# Brute Force Solution
mini_cov = MinimumVertexCover(g, field = 1., penalty = 1.)
mini_cov_qubo = mini_cov.qubo
energy, configuration = ground_state_hamiltonian(mini_cov_qubo.hamiltonian)
print('Energy: {}'.format(energy), '\nConfigurations: {}'.format(configuration))
Energy: 4.0
Configurations: ['011100', '011110', '101001', '011001', '111001', '011101', '100011', '101011', '100111']
[4]:
# Possible Solution (Red Nodes represents the Vertex Cover)
g_sol = np.copy(g)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '1'], node_color="tab:red")
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '0'], node_color="tab:blue")
nx.draw_networkx_edges(g, pos)
[4]:
<matplotlib.collections.LineCollection at 0x7f803ee84550>
Solving the Problem with QAOA
In the standard QAOA, the X-mixer hamiltonian is used. Using the vectorized statevector simulator, we can solve the same problem as follows:
[5]:
q = QAOA()
q.set_circuit_properties(mixer_hamiltonian = 'x')
q.compile(mini_cov_qubo)
[6]:
q.optimize()
[7]:
q.result.most_probable_states
[7]:
{'solutions_bitstrings': ['011110', '100111'], 'bitstring_energy': 4.0}
[8]:
configuration = q.result.most_probable_states['solutions_bitstrings']
[9]:
# Plotting the Vectorized Backend Solution
g_sol = np.copy(g)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '1'], node_color="tab:red")
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '0'], node_color="tab:blue")
nx.draw_networkx_edges(g, pos)
[9]:
<matplotlib.collections.LineCollection at 0x7f803eef8820>
Using A Different Mixer
OpenQAOA also provides an alternative to the X-mixer, the XY-mixer which utilizes 2-qubit interactions instead of the 1-qubit interactions used for the X-mixer hamiltonian.
[10]:
q = QAOA()
q.set_circuit_properties(mixer_hamiltonian = 'xy')
q.compile(mini_cov_qubo)
[11]:
q.optimize()
[12]:
q.result.most_probable_states
[12]:
{'solutions_bitstrings': ['100111'], 'bitstring_energy': 4.0}
[13]:
configuration = q.result.most_probable_states['solutions_bitstrings']
[14]:
# Plotting the Solution with Default Connectivity of the XY-mixer
g_sol = np.copy(g)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '1'], node_color="tab:red")
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '0'], node_color="tab:blue")
nx.draw_networkx_edges(g, pos)
[14]:
<matplotlib.collections.LineCollection at 0x7f803ed672b0>
Since the XY-mixer is made up of 2-qubit interactions, it is possible to change the connectivity of the mixer hamiltonian. By default, this value is “full”. Which applies XX and YY interactions between every pair of qubit. Depending on the device connectivity, this may not be the best topology to use.
It may be worth exploring the different pre-defined connectivities.
[15]:
# mixer_qubit_connectivity: ['full', 'star', 'chain']
q = QAOA()
q.set_circuit_properties(mixer_hamiltonian = 'xy', mixer_qubit_connectivity='chain')
q.compile(mini_cov_qubo)
[16]:
q.optimize()
[17]:
q.result.most_probable_states
[17]:
{'solutions_bitstrings': ['101001'], 'bitstring_energy': 4.0}
[18]:
configuration = q.result.most_probable_states['solutions_bitstrings']
[19]:
# Plotting the Solution with Star-shaped Connectivity of the XY-mixer
g_sol = np.copy(g)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '1'], node_color="tab:red")
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '0'], node_color="tab:blue")
nx.draw_networkx_edges(g, pos)
[19]:
<matplotlib.collections.LineCollection at 0x7f80a07c62f0>
In this notebook, we introduce an algorithm titled the Quantum Alternating Operator Ansatz, QAOA. (Not to be confused with the Quantum Approximation Optimization Algorithm)
Introduction
The Quantum Alternating Operator Ansatz (QAOA) proposed by S. Hadfield et al. in [1] generalizes the alternating mixer and cost operator layers of the original QAOA by E. Farhi et al.
The algorithm involves the application of a phase seperation operator (cost operator), defined by an objective function, and mixing operators that depend on the domain and structure of the objective function. This is a slight departure from the original QAOA algorithm where the mixer unitary is defined by Mixer Hamiltonians, the former allowing for more variations to the mixer unitary.
In the following examples, we show how one can define their own custom mixer blocks, a block containing gates that would be used to define the mixer unitary, using the OpenQAOA GateMap objects.
Creating Custom Mixers
[20]:
# You can specify a custom mixer block using the GateMap Objects
# Using manual mode
from openqaoa.qaoa_components.ansatz_constructor import RZXGateMap, RXXGateMap
from openqaoa.qaoa_components import QAOADescriptor, create_qaoa_variational_params
from openqaoa.backends import create_device
from openqaoa.optimizers import get_optimizer
from openqaoa.backends.qaoa_backend import get_qaoa_backend
custom_mixer_block_gatemap = [RZXGateMap(0, 1), RZXGateMap(0, 2),
RZXGateMap(0, 3), RZXGateMap(0, 4),
RZXGateMap(0, 5), RXXGateMap(1, 2)]
custom_mixer_block_coeffs = [1., 1., 1., 1., 1., 1.]
qaoa_descriptor = QAOADescriptor(mini_cov_qubo.hamiltonian,
custom_mixer_block_gatemap, p=1,
mixer_coeffs=custom_mixer_block_coeffs)
device_local = create_device(location='local', name='qiskit.shot_simulator')
variate_params = create_qaoa_variational_params(qaoa_descriptor, 'standard', 'rand')
backend_local = get_qaoa_backend(qaoa_descriptor, device_local, n_shots=500)
optimizer = get_optimizer(backend_local, variate_params, {'method': 'cobyla',
'maxiter': 100})
[21]:
optimizer.optimize()
[21]:
Optimizer for VQA of type: QAOABaseBackendShotBased
Backend: QAOAQiskitBackendShotBasedSimulator
Method: COBYLA with Max Iterations: 100
[22]:
optimizer.qaoa_result.most_probable_states
[22]:
{'solutions_bitstrings': ['011100'], 'bitstring_energy': 4.0}
[23]:
configuration = optimizer.qaoa_result.most_probable_states['solutions_bitstrings']
[24]:
# Plotting the Solution
g_sol = np.copy(g)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '1'], node_color="tab:red")
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '0'], node_color="tab:blue")
nx.draw_networkx_edges(g, pos)
[24]:
<matplotlib.collections.LineCollection at 0x7f803eddbf40>
Due to the potential complexity of implementing these mixer blocks, we will add convenience functions in OpenQAOA that help construct some popular mixers discussed in QAOA literature.
[25]:
from openqaoa.utilities import quick_create_mixer_for_topology
# This function creates a star pattern mixer block with qubit 0 as its center
# If no coefficients are specified, the function uses default coefficients for
# all gatemaps in it
zx_gatemap_list, zx_gatemap_coeffs = quick_create_mixer_for_topology(RZXGateMap, 6, qubit_connectivity='star')
xx_gatemap_list, xx_gatemap_coeffs = quick_create_mixer_for_topology(RXXGateMap, 6, qubit_connectivity='full')
zx_gatemap_list.extend(xx_gatemap_list)
zx_gatemap_coeffs.extend(xx_gatemap_coeffs)
final_gatemap_list = zx_gatemap_list
final_gatemap_coeffs = zx_gatemap_coeffs
[26]:
qaoa_descriptor = QAOADescriptor(mini_cov_qubo.hamiltonian,
final_gatemap_list, p=1,
mixer_coeffs=final_gatemap_coeffs)
device_local = create_device(location='local', name='vectorized')
variate_params = create_qaoa_variational_params(qaoa_descriptor, 'standard', 'rand')
backend_local = get_qaoa_backend(qaoa_descriptor, device_local)
optimizer = get_optimizer(backend_local, variate_params, {'method': 'cobyla',
'maxiter': 100})
[27]:
optimizer.optimize()
[27]:
Optimizer for VQA of type: QAOABaseBackendStatevector
Backend: QAOAvectorizedBackendSimulator
Method: COBYLA with Max Iterations: 100
[28]:
optimizer.qaoa_result.most_probable_states
[28]:
{'solutions_bitstrings': ['011001'], 'bitstring_energy': 4.0}
[29]:
configuration = optimizer.qaoa_result.most_probable_states['solutions_bitstrings']
[30]:
# Plotting the Solution
g_sol = np.copy(g)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '1'], node_color="tab:red")
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '0'], node_color="tab:blue")
nx.draw_networkx_edges(g, pos)
[30]:
<matplotlib.collections.LineCollection at 0x7f803e33d9f0>
Its also possible to specify the 2-qubit gatemap connections using a networkx graph.
[31]:
# Create 2-Qubit Connection Graph for Mixer
nodes = 6
edge_probability = 0.7
mixer_g = nx.generators.fast_gnp_random_graph(n=nodes,p=edge_probability, seed=42)
plot_graph(mixer_g)
[32]:
# Input the EdgeMap into the convinience function
edge_map = [edge for edge in mixer_g.edges()]
edge_coeffs = [1.0]*len(edge_map)
final_gatemap_list, final_gatemap_coeffs = quick_create_mixer_for_topology(RXXGateMap, 6, edge_map, edge_coeffs)
[33]:
qaoa_descriptor = QAOADescriptor(mini_cov_qubo.hamiltonian,
final_gatemap_list, p=1,
mixer_coeffs=final_gatemap_coeffs)
device_local = create_device(location='local', name='vectorized')
variate_params = create_qaoa_variational_params(qaoa_descriptor, 'standard', 'rand')
backend_local = get_qaoa_backend(qaoa_descriptor, device_local)
optimizer = get_optimizer(backend_local, variate_params, {'method': 'cobyla',
'maxiter': 100})
[34]:
optimizer.optimize()
[34]:
Optimizer for VQA of type: QAOABaseBackendStatevector
Backend: QAOAvectorizedBackendSimulator
Method: COBYLA with Max Iterations: 100
[35]:
optimizer.qaoa_result.most_probable_states
[35]:
{'solutions_bitstrings': ['011000'], 'bitstring_energy': 5.0}
[36]:
configuration = optimizer.qaoa_result.most_probable_states['solutions_bitstrings']
[37]:
# Plotting the Solution
g_sol = np.copy(g)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '1'], node_color="tab:red")
nx.draw_networkx_nodes(g, pos, nodelist=[idx for idx,bit in enumerate(configuration[0]) if bit == '0'], node_color="tab:blue")
nx.draw_networkx_edges(g, pos, width=2)
nx.draw_networkx_edges(mixer_g, pos, edge_color=(1, 0, 1), style="--")
[37]:
<matplotlib.collections.LineCollection at 0x7f803ca46230>
Both the problem’s connectivity and mixer connectivity superimposed on the same diagram. The pink dotted lines representing the Mixer’s connectivity.
References
[1] S. Hadfield, Z. Wang, B. O’Gorman, E. Rieffel, D. Venturelli and R. Biswas, (2019), 10.3390/a12020034