In this notebook you will apply what you have just learned about cqasm and Quantum Inspire. We will consider a simple quantum algorithm, the quantum approximate optimization algorithm (QAOA), for which you will code the circuit in cqasm and send some jobs to real quantum hardware on the Quantum Inspire platform.

1. Recap: QAOA and MAXCUT

Introduction to the Quantum Approximate Optimization Algorithm

$$\newcommand{\ket}[1]{\left|{#1}\right\rangle}$$$$\newcommand{\bra}[1]{\left\langle{#1}\right|}$$$$\newcommand{\braket}[2]{\left\langle{#1}\middle|{#2}\right\rangle}$$

Consider some combinatorial optimization problem with objective function $C:x\rightarrow \mathbb{R}$ acting on $n$-bit strings $x\in \{0,1\}^n$, domain $\mathcal{D} \subseteq \{0,1\}^n$, and objective

\begin{align} \max_{x \in \mathcal{D}} C(x). \end{align}

In maximization, an approximate optimization algorithm aims to find a string $x'$ that achieves a desired approximation ratio $\alpha$, i.e.

\begin{equation} \frac{C(x')}{C^*}\geq \alpha, \end{equation}

where $C^* = \max_{x \in \mathcal{D}} C(x)$. In QAOA, such combinatorial optimization problems are encoded into a cost Hamiltonian $H_C$, a mixing Hamiltonian $H_M$ and some initial quantum state $\ket{\psi_0}$. The cost Hamiltonian is diagonal in the computational basis by design, and represents $C$ if its eigenvalues satisfy

\begin{align} H_C \ket{x} = C(x) \ket{x} \text{ for all } x \in \{0,1\}^n. \end{align}

The mixing Hamiltonian $H_M$ depends on $\mathcal{D}$ and its structure, and is in the unconstrained case (i.e. when $\mathcal{D}=\{0,1\}^n$) usually taken to be the transverse field Hamiltonian $H_M = \sum_{j} X_j$. Constraints (i.e. when $\mathcal{D}\subset \{0,1\}^n$) can be incorporated directly into the mixing Hamiltonian or are added as a penalty function in the cost Hamiltonian. The initial quantum state $\ket{\psi_0}$ is usually taken as the uniform superposition over all possible states in the domain. $\text{QAOA}_p$, parametrized in $\gamma=(\gamma_0,\gamma_1,\dots,\gamma_{p-1}),\beta=(\beta_0,\beta_1,\dots,\beta_{p-1})$, refers to a level-$p$ QAOA circuit that applies $p$ steps of alternating time evolutions of the cost and mixing Hamiltonians on the initial state. At step $k$, the unitaries of the time evolutions are given by

\begin{align} U_C(\gamma_k) = e^{-i \gamma_k H_C }, \label{eq:UC} \\ U_M(\beta_k) = e^{-i \beta_k H_M }. \label{eq:UM} \end{align}

So the final state $\ket{\gamma,\beta}$ of $\text{QAOA}_p$ is given by

\begin{align} \ket{\gamma,\beta} = \prod_{k=0}^{p-1} U_M(\beta_k) U_C(\gamma_k) \ket{\psi_0}. \end{align}

The expectation value $ F_p(\gamma,\beta)$ of the cost Hamiltonian for state $\ket{\gamma,\beta}$ is given by

\begin{align} F_p(\gamma,\beta) = \bra{\gamma,\beta}H_C\ket{\gamma,\beta}, \label{eq:Fp} \end{align}

and can be statistically estimated by taking samples of $\ket{\gamma,\beta}$. The achieved approximation ratio (in expectation) of $\text{QAOA}_p$ is then

\begin{equation} \alpha = \frac{F_p(\gamma,\beta)}{C^*}. \end{equation}

The parameter combinations of $\gamma,\beta$ are usually found through a classical optimization procedure that uses $F_p(\gamma,\beta)$ as a black-box function to be maximized.

Example application: MAXCUT

MaxCut is an NP-hard optimisation problem that looks for an optimal 'cut' for a graph $G(V,E)$, in the sense that the cut generates a subset of nodes $S \subset V$ that shares the largest amount of edges with its complement $ V\setminus S$. In slightly modified form (omitting the constant), it has the following objective function

\begin{align} \max_{s} \frac{1}{2} \sum_{ \langle i,j \rangle \in E} 1-s_i s_j, \end{align}

where the $s_i\in\{-1,1\}$ are the variables and $i,j$ are the edge indices. This function can be easily converted into an Ising cost Hamiltonian, which takes the form

\begin{align} H_C = \frac{1}{2}\sum_{\langle i,j\rangle \in E} I-Z_i Z_j. \end{align}

We use the standard mixing Hamiltonian that sums over all nodes:

\begin{align} H_M = \sum_{v \in V} X_v. \end{align}

As the initial state $\ket{\Psi_0}$ we take the uniform superposition, given by

\begin{align} \ket{\psi_0} = \frac{1}{\sqrt{2^{|V|}}}\sum_{x=0}^{2^{|V|}-1} \ket{x} \end{align}

The goal of this workshop is to guide you through an implemented code that simulates a small quantum computer running the QAOA algorithm applied to the MAXCUT problem. We will use qiskit as well as cqasm as SDK's. For the sake of run time, you will always run the classical optimization part using the qiskit simulator: it would take too long for our purposes to do the actual function evualtions in the classical optimization step on the hardware.

2. Some useful functions and intializations

We first define some useful functions to be used later throughout the code.

Test instances

3. Circuit generators

We provide you with an example written in qiskit. You have to write the one for cqasm yourself.

Qiskit generators

cqasm generators

Now it is up to you to apply what we have learned about cqasm to write the script for the cost and mixing operators:

4. Hybrid-quantum classical optimization

Since QAOA is usually adopted as a hybrid quantum-classical algorithm, we need to construct an outer loop which optimizes the estimated $\bra{\gamma,\beta}H\ket{\gamma,\beta}$.

5. A simple instance on the quantum inspire platform: 2-qubit case

Let us first consider the most simple MAXCUT instance. We have just two nodes, and an optimal cut with objective value 1 would be to place both nodes in its own set.

Using qiskit, the circuit would look the following:

Now let's run our hybrid-quantum algorithm simulation using qiskit:

Now that we have obtained some good values for $\beta$ and $\gamma$ through classical simulation, let's see what Starmon-5 would give us.

The figure below shows the topology of Starmon-5. Since q0 is not connected to q1, we have to relabel the nodes. Networkx as such an option, by using 'nx.relabel_nodes(G,{1:2}' we can relabel node 1 as node 2. Since q0 is connected to q2, this does allow us to run our cqasm code on Starmon-5. For qiskit, this step is irrelevant as we have all-to-all connectivity in the simulation.

Now we run the Cqasm-circuit on the Starmon-5 Hardware.

Inspecting 'counts_QI', we see that it returns the integer corresponding to the bit string result of the measurement

Note that we measure more than just the two relevant qubits, since we had the 'measure all' command in the the cqasm code. The distribution over the strings looks the following:

Let's create another counts dictionary with only the relevant qubits, which are q0 and q2:

We now plot all distributions (qiskit, Starmon-5, and random guessing) in a single plot.

6. Compilation issues: the triangle graph

For the graph with just two nodes we already had some minor compilation issues, but this was easily fixed by relabeling the nodes. We will now consider an example for which relabeling is simply not good enough to get it mapped to the Starmon-5 toplogy.

Due to the topology of Starmon-5 this graph cannot be executed without any SWAPS. Therefore, we ask you to write a new circuit generator that uses SWAPS in order to make the algorithm work with the Starmon-5 topology. Let's also swap back to the original graph configuration, so that we can in the end measure only the qubits that correspond to a node in the graph (this is already written for you)

We now run the same procedure as before to obtain good parameter values

Let's run it on Starmon-5 again!

7. More advanced questions

Some questions you could look at: