09 - Recursive QAOA

In this notebook, we provide a short introduction to recursive QAOA, and demonstrate how this technique is implemented in the OpenQAOA workflows, by solving a standard well-known problem from combinatorial optimization: the Minimum Vertex Cover. For reference, the algorithmic functions used by the workflow are contained inside the rqaoa.py script.

A brief introduction

Recursive QAOA (RQAOA) is an iterative variant of QAOA, first introduced by Bravyi et. al in [1] and further explored in [2,3].

This technique consists in recursively reducing the size of the problem by running QAOA. At each step, the QAOA output distribution is used to compute the expectation values

\[\mathcal{M}_{i} = \langle Z_{i} \rangle \qquad \qquad \qquad \qquad \qquad \mathcal{M}_{ij} = \langle Z_{i}Z_{j} \rangle,\]

associated with the terms present in the Hamiltonian. Note that, by definition, these quantities are bounded between -1 and 1. The expectation values are then ranked according to their magnitude \(|\mathcal{M}_{(i,ij)}|\). In its original formulation, the highest ranked value is selected. This value is then utilized to eliminate a qubit from the Hamiltonian. This is done by first, performing integer rounding of the expectation value, i.e. \(\mathcal{M}_{(i,ij)} \rightarrow \textrm{sign}(\mathcal{M}_{(i,ij)})\), then transforming the rounded value into a constraint on the respective qubits

\[Z_{i} \rightarrow \textrm{sign}(\mathcal{M}_{(i)}) \qquad \qquad \qquad \qquad \qquad \langle Z_{i} Z_{j} \rangle \rightarrow \textrm{sign}(\mathcal{M}_{(ij)}),\]

and last, inserting the constraint into the Hamiltonian, effectively reducing the size of the problem by one qubit. Using the reduced Hamiltonian, QAOA is run again and the same procedure is followed. Once the reduced problem reaches a predefined cutoff size, it is solved exactly solved via classical methods. The final answer is then reconstructed by re-inserting the eliminated qubits into the classical solution following the appropriate order.

This version of RQAOA is included in OpenQAOA. Additionally, OpenQAOA incorporates RQAOA from two different generalized version of these procedure, which enable multiple qubit eliminations during the recursive process. These strategies are denoted as custom and adaptive, in accordance with the precise concept under which the elimination method takes place. In a nutshell, they are described as follows:

• The custom strategy allows the user to define the number of eliminations to be performed at each step. This defined by the parameter steps. If the parameter is set as an integer, the algorithm will use this value as the number of qubits to be eliminated at each step. Alternatively, it is possible to pass a list, which specifies the number of qubits to be eliminated at each step. For steps = 1, the algorithm reduces to the original form of RQAOA presented in [1].

• The adaptive strategy adaptively selects how many qubits to eliminate at each step. The maximum number of allowed eliminations is given by the parameter n_max. At each step, the algorithm selects the top n_max+1 expectation values (ranked in magnitude), computes the mean among them, and uses the ones lying above it for qubit elimination. This corresponds to a maximum of n_max possible elimination per step. For n_max= 1, the algorithm reduces to the original form of RQAOA presented in [1].

NOTE: The specific performance of these generalizations is currently under investigation. In particular, the development of Adaptive RQAOA is associated with an internal research project at Entropica Labs to be released publicly in the near future [4]. We make these strategies already available to the community in order to strengthen the exploration of more complex elimination schemes for RQAOA, beyond its original formulation [1].

import numpy as np
import networkx as nx

from openqaoa import RQAOA, QAOA
from openqaoa.problems import MinimumVertexCover, QUBO
from openqaoa.utilities import ground_state_hamiltonian
from openqaoa.qaoa_components import Hamiltonian
from openqaoa.backends import create_device

Problem: Minimum Vertex Cover of an N = 10 ring

We generate an instance of the Minimum Vertex Cover problem for a ring graph of 10 nodes, making use of the problem library in OpenQAOA.

As a brief reminder, the Minimum Vertex Cover problem consists in finding the minimum set of nodes in a graph such every edge in the graph is incident in at least one node in the set. For a ring, the answer corresponds to selected all the even or all the odd nodes (i.e. an antiferromagnet!), meaning that the answer is doubly degenerate. Explicitly, the solutions reads 1010101010 and 0101010101, and the ground state energy is \(E_{gs} = 5\). If you are curious about the specific QUBO formulation of Minimum Vertex Cover, you can check out [3] (it also contains the QUBO form of many other interesting combinatorial optimization problems!)

# Number of qubits
n_qubits = 10

# Ring graph
G = nx.circulant_graph(n_qubits,[1])

# Minimum vertex cover parameters
field = 1.0
penalty = 10

# Define problem instance
vc = MinimumVertexCover(G,field = field,penalty = penalty).qubo

Original RQAOA and setting up the QAOA properties for the recursive process

Let us first demonstrate how we would solve this problem making use of the original formulation of RQAOA. As explained in the introduction, this can be done by either selecting Custom RQAOA and choosing steps = 1 or by using Adaptive RQAOA and choosing n_max=1. Both methods will by default use the original version of RQAOA.

Since RQAOA runs recursively QAOA, we need to set how do we want QAOA to run. This is easily done by making use of the RQAOA methods, the workflow is similar to the QAOA one (see the previous tutorial). By calling the corresponding methods we will set all the QAOA properties, e.g.: number of layers, initialization, parametrization, mixer, device, optimizer, etc.

# Define the RQAOA object (default rqaoa_type = 'adaptive')
r =  RQAOA()

# Set parameters for RQAOA, in this case we fix the n_max to 1 (default), the final cutoff value to 3
r.set_rqaoa_parameters(n_cutoff=3)

## Setting up the QAOA properties

# Set the properties you want - These values are actually the default ones!
r.set_circuit_properties(p=1, param_type='standard', init_type='ramp', mixer_hamiltonian='x')

# Define the device you want to run your problem on using the create_device() function - Here we choose the local wavefunction simulator supported by OpenQAOA
device = create_device(location='local', name='vectorized')
r.set_device(device)

# Set the classical method used to optimiza over QAOA angles and its properties
r.set_classical_optimizer(method='cobyla', maxiter=200)

# Compile problem instance on RQAOA, just like with QAOA
r.compile(vc)

# Solve problem with RQAOA
r.optimize()

# Extract results
r.result

{'solution': {'1010101010': 5.0},
 'classical_output': {'minimum_energy': -3.0, 'optimal_states': ['10']},
 'elimination_rules': [[{'pair': (0, 1), 'correlation': -1.0}],
  [{'singlet': (1,), 'bias': -1.0}],
  [{'singlet': (1,), 'bias': 1.0}, {'singlet': (2,), 'bias': -1.0}],
  [{'singlet': (1,), 'bias': 1.0}, {'singlet': (2,), 'bias': -1.0}],
  [{'singlet': (1,), 'bias': 1.0}, {'singlet': (2,), 'bias': -1.0}]],
 'schedule': [1, 1, 2, 2, 2],
 'number_steps': 5,
 'intermediate_steps': [{'counter': 0,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f35f0555310>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f35f054c430>,
   'exp_vals_z': array([0.02352005, 0.02352005, 0.02352005, 0.02352005, 0.02352005,
          0.02352005, 0.02352005, 0.02352005, 0.02352005, 0.02352005]),
   'corr_matrix': array([[-0.00055319, -0.29835057, -0.00055319, -0.00055319, -0.00055319,
           -0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.29835057],
          [-0.00055319, -0.00055319, -0.29835057, -0.00055319, -0.00055319,
           -0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319],
          [-0.00055319, -0.00055319, -0.00055319, -0.29835057, -0.00055319,
           -0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319],
          [-0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.29835057,
           -0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319],
          [-0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319,
           -0.29835057, -0.00055319, -0.00055319, -0.00055319, -0.00055319],
          [-0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319,
           -0.00055319, -0.29835057, -0.00055319, -0.00055319, -0.00055319],
          [-0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319,
           -0.00055319, -0.00055319, -0.29835057, -0.00055319, -0.00055319],
          [-0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319,
           -0.00055319, -0.00055319, -0.00055319, -0.29835057, -0.00055319],
          [-0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319,
           -0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.29835057],
          [-0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319,
           -0.00055319, -0.00055319, -0.00055319, -0.00055319, -0.00055319]])},
  {'counter': 1,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f35f05656a0>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f358fb96f70>,
   'exp_vals_z': array([ 0.        , -0.48762051, -0.48762051, -0.48762051, -0.48762051,
          -0.48762051, -0.48762051, -0.48762051, -0.48762051]),
   'corr_matrix': array([[ 0.        ,  0.30761582,  0.        ,  0.        ,  0.        ,
            0.        ,  0.        ,  0.        , -0.30761582],
          [ 0.        , -0.23777376, -0.19403514, -0.23777376, -0.23777376,
           -0.23777376, -0.23777376, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.19403514, -0.23777376,
           -0.23777376, -0.23777376, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.19403514,
           -0.23777376, -0.23777376, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.19403514, -0.23777376, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.23777376, -0.19403514, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.23777376, -0.23777376, -0.19403514, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.23777376, -0.23777376, -0.23777376, -0.19403514],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.23777376, -0.23777376, -0.23777376, -0.23777376]])},
  {'counter': 2,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f35f054ce80>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f35f0555ac0>,
   'exp_vals_z': array([-0.32579059, -0.26390555, -0.48705248, -0.48705248, -0.48705248,
          -0.48705248, -0.48705248, -0.48705248]),
   'corr_matrix': array([[-0.10613951, -0.08597794, -0.15867711, -0.15867711, -0.15867711,
           -0.15867711, -0.15867711, -0.27071807],
          [-0.08597794, -0.06964614, -0.28520458, -0.12853585, -0.12853585,
           -0.12853585, -0.12853585, -0.12853585],
          [-0.15867711, -0.12853585, -0.23722012, -0.19439452, -0.23722012,
           -0.23722012, -0.23722012, -0.23722012],
          [-0.15867711, -0.12853585, -0.23722012, -0.23722012, -0.19439452,
           -0.23722012, -0.23722012, -0.23722012],
          [-0.15867711, -0.12853585, -0.23722012, -0.23722012, -0.23722012,
           -0.19439452, -0.23722012, -0.23722012],
          [-0.15867711, -0.12853585, -0.23722012, -0.23722012, -0.23722012,
           -0.23722012, -0.19439452, -0.23722012],
          [-0.15867711, -0.12853585, -0.23722012, -0.23722012, -0.23722012,
           -0.23722012, -0.23722012, -0.19439452],
          [-0.15867711, -0.12853585, -0.23722012, -0.23722012, -0.23722012,
           -0.23722012, -0.23722012, -0.23722012]])},
  {'counter': 3,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f358fb20040>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f358fb20f70>,
   'exp_vals_z': array([-0.32984216, -0.2673374 , -0.48891503, -0.48891503, -0.48891503,
          -0.48891503]),
   'corr_matrix': array([[-0.10879585, -0.08817915, -0.16126479, -0.16126479, -0.16126479,
           -0.27146642],
          [-0.08817915, -0.07146929, -0.28692349, -0.13070527, -0.13070527,
           -0.13070527],
          [-0.16126479, -0.13070527, -0.23903791, -0.19083603, -0.23903791,
           -0.23903791],
          [-0.16126479, -0.13070527, -0.23903791, -0.23903791, -0.19083603,
           -0.23903791],
          [-0.16126479, -0.13070527, -0.23903791, -0.23903791, -0.23903791,
           -0.19083603],
          [-0.16126479, -0.13070527, -0.23903791, -0.23903791, -0.23903791,
           -0.23903791]])},
  {'counter': 4,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f358fb201c0>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f358fb20f40>,
   'exp_vals_z': array([-0.33897148, -0.27513089, -0.4915539 , -0.4915539 ]),
   'corr_matrix': array([[-0.11490167, -0.09326153, -0.16662276, -0.27207819],
          [-0.09326153, -0.07569701, -0.29005985, -0.13524166],
          [-0.16662276, -0.13524166, -0.24162524, -0.18056019],
          [-0.16662276, -0.13524166, -0.24162524, -0.24162524]])}],
 'atomic_ids': {0: '270e82a3-cb47-4dc4-bf08-9b1120e65620',
  1: 'c584bfee-f2ca-442d-ae77-46f77bcf363c',
  2: '109a4e98-9f18-479c-a5f3-a58b1076a802',
  3: '4f7eb288-cecf-407d-95df-75cc357a2fdd',
  4: 'fc37eb36-9c9a-4cd7-97e3-f17455bad792'}}

We have solved our first problem using RQAOA! Let us now digest the output from the results.

First, the r.results['solution'] dictionary contains to the final solution(s) of the problem, here 1010101010 (the antiferromagnetic solution we expected!), and the associated energy(-ies), here 5.0. The r.results['classical_output'] dictionary contains the results from the classical optimization at the cutoff size. The r.results['elimination_rules'] dictionary displays how qubits were eliminated throughout the recursive process. Taking the first entry {'pair': (0, 1), 'correlation': -1.0} as an example, it should be read as: qubit 1 was eliminated in favor of qubit 0, and the correlation between them is negative. When the label of the remaining qubit reads None, like in {'singlet': (1,), 'bias': -1.0}, the qubit 1 was not eliminated in favor of a remaining one, but was instead fixed to the specified value -1.0, resulting from a single-qubit expectation value being the highest ranked. The r.results['schedule'] corresponds to the number of eliminations that took place at each step. The r.results['intermediate_steps'] is a list, each item is storing information of each recursive step of the RQAOA algorithm. Each item is a dictonary with a QUBO problem object (object storing the problem solved in the corresponding step), a QAOA result object (object storing the corresponding qaoa solutions after solving the QUBO problem), a list of the expectation values in z and the correlation matrix of the corresponding step. Finally, r.results['number_steps'] tells us the number of steps that it took to reach the cutoff value and r.results['atomic_ids'] gives us the identification for the QAOA objects that have been optimized in the process, we can ignore them for now.

The r.results object has some methods that help to get the intermediate steps: .get_qaoa_results(step), .get_qaoa_optimized_angles(step), .get_problem(step), plot_corr_matrix(step), etc. (see documentation). Example:

# get the QAOA Resukt object for the 2 step
q_result_2 = r.result.get_qaoa_results(step=2)
# get the QUBO problem for the 2 step
problem_2 = r.result.get_problem(step=2)

# getting information about the QAOA object and the QUBO problem
print('solution of the QAOA optimization in recursive step 2: ', q_result_2.most_probable_states)
print('terms of of the QUBO problem in recursive step 2: ', problem_2.terms)

#plotting the correlation matrix
fig, ax = r.result.plot_corr_matrix(step=2)
fig.show()

solution of the QAOA optimization in recursive step 2:  {'solutions_bitstrings': ['11111111'], 'bitstring_energy': -14.0}
terms of of the QUBO problem in recursive step 2:  [[0, 7], [0], [1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [2], [3], [4], [5], [6], [7]]

But wait! We claimed to be using the original form of RQAOA, where only one elimination takes place at each step. However, in the schedule we can observe that in the third, fourth and fifth step two qubits were eliminated instead of one. How is this possible? To clarify, the algorithm did select a single expectation value to generate a constraint and eliminate a single qubit form the model! This extra eliminations turn out to be an interesting property of the RQAOA. When one qubit is eliminated as a function of another, this corresponds to fusing two nodes in the underlying graph, making the reduced graph denser. On the contrary, when a qubit is fixed to a value, we effectively remove the node from the graph, thus making the reduced graph sparser. It turns out that the combination of these processes can sometimes lead to nodes getting isolated from the main graph component. This means that, if the assumptions we made (i.e. the imposed constraints) are correct, the specific value of this qubit is independent of the rest, and can then be fixed respecting the corresponding linear term (or arbitrarily if no linear term is present!).

In summary, spontaneous eliminations can take place as a result of fixing nodes that ended up isolated consequence of the topology changes throughout the elimination process.

(NOTE: If you think about this carefully, you will notice that this event is mostly prominent in uniform-like graphs, where terms can cancel, but for randomly weighted problems, this will most likely not take place at all!)

Standard / custom method

As presented in the introduction, the Custom strategy allows to generalize the number of eliminations at each step. The specific number of eliminations (up the spontaneous ones described in the previous section) can either be a constant value at each step, or we can set a custom schedule defining what to do at each step. Note that, when customizing a schedule, total number of eliminations need to be enough to reach the cutoff size! In general, the algorithm will choose to never go beyond the cutoff, e.g. if we ask for 5 qubits to be eliminated but we are 2 qubits away from the cutoff only 2 will be eliminated. The only exception to this is when spontaneous eliminations occur.

# Define RQAOA instance
r =  RQAOA()

# Set parameters for RQAOA

# Fixed step - Choosing an integer value sets the default number of eliminations at each step to that value
r.set_rqaoa_parameters(steps = 2, n_cutoff = 3)

# Schedule - Choosing a schedule, the algorithm reads through the list to select the number of eliminations at each step
schedule = [1,2,3,4,5]
r.set_rqaoa_parameters(steps = schedule, n_cutoff = 3) # WE USE THIS ONE

# Compile problem instance on RQAOA
r.compile(vc)

# Solve problem with RQAOA
r.optimize()

# Extract results
r.result

{'solution': {'1011011110': 7.0, '0111011101': 7.0, '1011011101': 7.0},
 'classical_output': {'minimum_energy': -5.0,
  'optimal_states': ['110', '001', '101']},
 'elimination_rules': [[{'pair': (0, 1), 'correlation': -1.0}],
  [{'singlet': (1,), 'bias': -1.0}, {'singlet': (2,), 'bias': -1.0}],
  [{'singlet': (1,), 'bias': 1.0},
   {'singlet': (2,), 'bias': -1.0},
   {'singlet': (3,), 'bias': -1.0},
   {'singlet': (4,), 'bias': -1.0}]],
 'schedule': [1, 2, 4],
 'number_steps': 3,
 'intermediate_steps': [{'counter': 0,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f35f0555310>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f358fb6f550>,
   'exp_vals_z': array([0.02352669, 0.02352669, 0.02352669, 0.02352669, 0.02352669,
          0.02352669, 0.02352669, 0.02352669, 0.02352669, 0.02352669]),
   'corr_matrix': array([[-0.00055351, -0.29835734, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.29835734],
          [-0.00055351, -0.00055351, -0.29835734, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.29835734, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.29835734,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.29835734, -0.00055351, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.29835734, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.29835734, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.29835734, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.29835734],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351]])},
  {'counter': 1,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f358fb6f850>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f35f0555130>,
   'exp_vals_z': array([ 0.        , -0.48762051, -0.48762051, -0.48762051, -0.48762051,
          -0.48762051, -0.48762051, -0.48762051, -0.48762051]),
   'corr_matrix': array([[ 0.        ,  0.30761582,  0.        ,  0.        ,  0.        ,
            0.        ,  0.        ,  0.        , -0.30761582],
          [ 0.        , -0.23777376, -0.19403514, -0.23777376, -0.23777376,
           -0.23777376, -0.23777376, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.19403514, -0.23777376,
           -0.23777376, -0.23777376, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.19403514,
           -0.23777376, -0.23777376, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.19403514, -0.23777376, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.23777376, -0.19403514, -0.23777376, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.23777376, -0.23777376, -0.19403514, -0.23777376],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.23777376, -0.23777376, -0.23777376, -0.19403514],
          [ 0.        , -0.23777376, -0.23777376, -0.23777376, -0.23777376,
           -0.23777376, -0.23777376, -0.23777376, -0.23777376]])},
  {'counter': 2,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f358fb6f5b0>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f358fb7e760>,
   'exp_vals_z': array([-0.32771145, -0.2655229 , -0.48820323, -0.48820323, -0.48820323,
          -0.48820323, -0.48820323]),
   'corr_matrix': array([[-0.10739479, -0.08701489, -0.15998979, -0.15998979, -0.15998979,
           -0.15998979, -0.2707761 ],
          [-0.08701489, -0.07050241, -0.28566525, -0.12962914, -0.12962914,
           -0.12962914, -0.12962914],
          [-0.15998979, -0.12962914, -0.2383424 , -0.19269507, -0.2383424 ,
           -0.2383424 , -0.2383424 ],
          [-0.15998979, -0.12962914, -0.2383424 , -0.2383424 , -0.19269507,
           -0.2383424 , -0.2383424 ],
          [-0.15998979, -0.12962914, -0.2383424 , -0.2383424 , -0.2383424 ,
           -0.19269507, -0.2383424 ],
          [-0.15998979, -0.12962914, -0.2383424 , -0.2383424 , -0.2383424 ,
           -0.2383424 , -0.19269507],
          [-0.15998979, -0.12962914, -0.2383424 , -0.2383424 , -0.2383424 ,
           -0.2383424 , -0.2383424 ]])}],
 'atomic_ids': {0: 'a762df10-8633-4902-ab09-3715eb050524',
  1: '8b9f3175-0f2d-45f7-8e30-cf31f54b7b84',
  2: 'a8ef482c-f188-4b34-8c6d-6767a726c0f7'}}

In comparison with the output from the previous problem, we now obtained multiple degenerate solutions (the beauty of RQAOA!), which sadly do not correspond to the actual solution to the problem (but hey, we just went ahead with a random elimination schedule). Note that the schedule now looks like the input schedule in the steps parameter, as it should! The only difference being that in the last step there was a spontaneous elimination and the value increased from 3 to 4, thus reaching the cutoff value earlier.

Adaptive method

Finally, as explained in the introduction, the adaptive scheme provides a balanced way of performing eliminations with RQAOA, with the parameter n_max setting the maximum number of potential eliminations. The final number will depend on the specific ranking structure of the expectation values, and n_max sets what portion of these we would like to explore. As with the Custom strategy, the algorithm ensures to not go overboard the cutoff size value, up to spontaneous eliminations.

# Define RQAOA instance - We use the default QAOA settings again
r =  RQAOA()

# Set parameters for adaptive RQAOA, the maximum number of eliminations allowed and final cutoff value
r.set_rqaoa_parameters(n_cutoff = 3, n_max = 4, rqaoa_type = 'adaptive')

# Compile problem instance on RQAOA
r.compile(vc)

# Solve problem with RQAOA
r.optimize()

# Extract results
r.result

{'solution': {'1010101010': 5.0, '0101010101': 5.0},
 'classical_output': {'minimum_energy': -7.5,
  'optimal_states': ['110', '001']},
 'elimination_rules': [[{'pair': (0, 1), 'correlation': -1.0},
   {'pair': (0, 2), 'correlation': 1.0},
   {'pair': (0, 3), 'correlation': -1.0},
   {'pair': (0, 9), 'correlation': -1.0}],
  [{'pair': (0, 1), 'correlation': 1.0},
   {'pair': (0, 2), 'correlation': -1.0},
   {'pair': (0, 5), 'correlation': 1.0}]],
 'schedule': [4, 3],
 'number_steps': 2,
 'intermediate_steps': [{'counter': 0,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f35f0555310>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f35d045c9d0>,
   'exp_vals_z': array([0.02352669, 0.02352669, 0.02352669, 0.02352669, 0.02352669,
          0.02352669, 0.02352669, 0.02352669, 0.02352669, 0.02352669]),
   'corr_matrix': array([[-0.00055351, -0.29835734, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.29835734],
          [-0.00055351, -0.00055351, -0.29835734, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.29835734, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.29835734,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.29835734, -0.00055351, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.29835734, -0.00055351, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.29835734, -0.00055351, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.29835734, -0.00055351],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.29835734],
          [-0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351]])},
  {'counter': 1,
   'problem': <openqaoa.problems.qubo.QUBO at 0x7f358f8af340>,
   'qaoa_results': <openqaoa.optimizers.result.Result at 0x7f358f97be20>,
   'exp_vals_z': array([-0.02352669,  0.02352669,  0.02352669,  0.02352669,  0.02352669,
           0.02352669]),
   'corr_matrix': array([[-0.00055351,  0.29835733,  0.00055351,  0.00055351,  0.00055351,
            0.29835733],
          [ 0.00055351, -0.00055351, -0.29835733, -0.00055351, -0.00055351,
           -0.00055351],
          [ 0.00055351, -0.00055351, -0.00055351, -0.29835733, -0.00055351,
           -0.00055351],
          [ 0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.29835733,
           -0.00055351],
          [ 0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.29835733],
          [ 0.00055351, -0.00055351, -0.00055351, -0.00055351, -0.00055351,
           -0.00055351]])}],
 'atomic_ids': {0: '86906672-344f-47de-9e85-5146754ccf0e',
  1: '8c80a61c-4345-464c-a26d-3990c66a4c43'}}

As we can see, we happen to reach the end of the process in only two steps (and also happened to find the right answer! Though bear in mind we did choose an easy problem), where the algorithm chose to eliminate 4 qubits in the first step (the maximum possible) and 3 on the second one.

Problem: Sherrington-Kirkpatrick, with \(J_{ij} = \pm 1\) and \(N = 10\), using RQAOA

To wrap it up, let us now do a walk through the whole process for a different problem, the Sherrington-Kirkpatrick model. This corresponds to a fully-connected system, where we choose the couplings \(J_{ij}\) to be of magnitude 1, but with a randomly assigned signs. The workflow requires us to define the problem as an instance of the QUBO class, which can be easily done by defining the connectivity of the problem as a set of tuples, and the and the associated weights (i.e. coupling constants) as a list. Here, we approach this problem using Adaptive RQAOA.

# Number of qubits
n_qubits = 10

# Define fully-connected terms
terms = [(i,j) for j in range(n_qubits) for i in range(j)]

# Assign weight signs at random
seed = 42
np.random.seed(seed)
weights = [(-1)**np.round(np.random.random()) for _ in range(len(terms))]

# Define QUBO problem
sk = QUBO(n_qubits,terms,weights)

To check the quality of our results we additionally make use of the utility function ground_state_hamiltonian, which can compute the exact result for any Hamiltonian of reasonable size. To use this function we define the problem as an instance of the Hamiltonian class, using the classical_hamiltonian method (given that our Hamiltonian is only composed of \(Z\) operators). This class is widely used across OpenQAOA to generate mixer and cost Hamiltonians that define the QAOA structure.

# Obtain exact solution for comparison

# Define Hamiltonian object from terms and weights
hamiltonian = Hamiltonian.classical_hamiltonian(terms,weights,constant = 0)

# Compute the exact result
exact_energy, ground_state_strings = ground_state_hamiltonian(hamiltonian)

print(f'The exact energy is {exact_energy} and the solutions are {ground_state_strings}')

The exact energy is -17.0 and the solutions are ['1101100000', '1110011010', '0001100101', '0010011111']

# Define RQAOA instance
r =  RQAOA()

# Set parameters for adaptive RQAOA, the maximum number of eliminations allowed and final cutoff value
n_cutoff = 3
n_max = 3
r.set_rqaoa_parameters(n_cutoff = n_cutoff, n_max = n_max, rqaoa_type = 'adaptive')

# Compile problem instance on RQAOA
r.compile(sk)

# Solve problem with RQAOA
r.optimize()

# Extract results
result = r.result
solutions = result.get_solution()

states = list(solutions.keys())
energy = list(solutions.values())[0]

print(f'The solution found by Ada-RQAOA for nmax = {n_max} is energy = {energy} and ground states = {states}')

The solution found by Ada-RQAOA for nmax = 3 is energy = -17.0 and ground states = ['1101100000', '0010011111']

And that’s it! We happened to obtain again the correct result (at least a few solutions), but a quick play around with n_cutoff and n_max will show you this might not always be the case!

To conclude, we have shown how to use the RQAOA workflow and how to run problem instances using the different RQAOA strategies available. As with any iterative problem, we expect many more to emerge in the near future (e.g. see [5] for a non-deterministic proposal to determine the eliminations). We hope OpenQAOA helps you to explore this powerful algorithm further and ultimately enables you to contribute to the quantum computing community! :)

References

[1] S. Bravyi, A. Kliesch, r. Koenig, and E. Tang, Physical Review Letters 125, 260505 (2020)

[2] S. Bravyi, A. Kliesch, r. Koenig, and E. Tang, (2020), 10.22331/q-2022-03-30-678

[3] D. J. Egger, J. Marecek, and S. Woerner, Quantum 5, 479 (2021)

[4] E. I. Rodriguez Chiacchio, V. Sharma, E. Munro (Work in progress)

[5] A. Lucas, Frontiers in Physics 2 (2014)

[6] J. r. McClean, M. P. Harrigan, M. Mohseni, N. C. Rubin, Z. Jiang, S. Boixo, V. N. Smelyanskiy, r. Babbush, and H. Neven, PRX Quantum 2, 030312 (2021)