OpenQAOA — An SDK for QAOA

Given a cost Hamiltonian $H_{c}$, the objective of QAOA is to optimise the expectation value $\langle\Psi(\gamma,\beta)|H_{c}|\Psi(\gamma,\beta)\rangle$. In the standard QAOA, the variational ansatz state $|\Psi(\gamma,\beta)\rangle$ is defined as

The circuit is initialised in the state $|+\rangle^{\otimes n}$, where $n$ is the number of qubits. Sets of unitary operators are then alternately applied to the state in a layer-wise manner. A layer in the QAOA circuit denotes the application of the complete set of unitaries, and the parameter $p$ corresponds to the number of layers in the circuit ansatz. Each layer is composed of the alternate evolution under unitaries generated by the cost Hamiltonian $H_{c}$ encoding the problem, and a mixer Hamiltonian $H_{\textrm{m}}$. These unitary operators are parametrised by the variational parameters $\{\gamma_{k}\}$ and $\{\beta_{k}\}$ respectively, with $k=1,\ldots,p$.

Cost Operator: The most commonly envisioned usage of QAOA is to tackle classical binary combinatorial optimisation problems. In this case, the elements of the cost Hamiltonian are derived directly from the cost function associated with the problem at hand. It is well known that these problems can be cast in the Ising form, i.e. as a set of interacting spin-$1/2$ particles or binary variables [22]. This means that the objective function can be encoded as the expectation value of a cost Hamiltonian $H_{c}$ of the form

where $Z_{j}$ denotes the Pauli-Z operator acting on the $j^{th}$ spin, $h_{j}$ is a bias term for single spins indicating their preference for one of the two possible operator eigenvalues, and $J_{jk}$ denotes the coupling strength between the spins $j$ and $k$. Equation 2 may also contain linear and quadratic terms that enforce constraints relevant to the problem. These constraints give a significant positive contribution to the energy if violated, but zero otherwise. When the entire problem can be formulated this way, we say we have a problem in quadratic unconstrained binary optimisation (QUBO) form [23].

The unitary operator associated with the cost Hamiltonian can be generalised beyond its standard form – i.e., as it appears in Eq. 1 – by increasing the number of variational parameters in the ansatz. The corresponding ‘cost operator’ for the $L^{th}$ layer, $U_{c}^{(L)}$, then takes the form

Here, the coefficients $\{h_{j}\}$ and $\{J_{jk}\}$ are as defined in Eq. 2, and $\{\gamma_{j}^{L},\gamma_{jk}^{L}\}$ denote the variational circuit parameters for each term in the cost Hamiltonian for the $L^{th}$ layer.

Mixer Operator: The mixer operator is responsible for exploring the solution space, and creating interference between the computational basis states. In standard QAOA, the mixer operator is constructed from the Hamiltonian $H_{m}=-\sum_{i}X_{i}$, where $X_{i}$ is the Pauli-X operator acting on the $i^{th}$ qubit. As with the cost operator, this unitary ‘mixer operator’ for the $L^{th}$ layer, $U_{m}^{(L)}$, can also be generalised from its standard form as

where $\{\beta_{j}^{L}\}$ are the variational parameters associated with each term in the mixer Hamiltonian for the $L^{th}$ layer. Different applications may call for alternative mixer operators, for example in the context of constrained optimisation, where it is desirable to explore a limited subspace of the full Hilbert space [24, 17].

Parametrisation: It is possible to establish fixed relationships between different sets of the variational parameters, leading to many possible state ansätze. We refer to a particular specification of these relationships as a ‘parametrisation’. For example, in the standard QAOA, we fix all parameters associated with the cost operator within a given layer to be equal, and similarly for the mixer operator. That is, we set $\gamma_{j}^{L}=\gamma_{k}^{L}=\gamma_{jk}^{L}\equiv\gamma^{L}$, and $\beta_{j}^{L}\equiv\beta^{L}$; we refer to this as the ‘standard parametrisation’. While this parameterisation is prevalent in much of the literature, alternative approaches have been proposed, and will be discussed further in Section IV.2.

Parameter initialisation: For a given parametrisation, one must select initial values for the corresponding parameters. We refer to this as ‘parameter initialisation’, or simply ‘initialisation’ when the context is clear. The initialisation strategy can strongly impact the performance of the algorithm. For example, assigning random initial values could lead to acute issues in the scalability of the optimisation procedure [25, 26].

Initial state: Before applying the cost and mixer operations, the quantum circuit must be prepared in some initial state. In standard QAOA, one uses the equal superposition state $|+\rangle^{\otimes n}$, however this may be undesirable for certain applications, e.g. constrained optimisation problems.

QAOA consists of a hybrid process where quantum and classical routines are performed in a loop. The algorithm itself can be divided into three main phases, summarised in Fig. 2.

• •

  Preparation phase — A circuit ansatz is selected by specifying fixed problem inputs and variational parameters. The inputs include the cost Hamiltonian, the number of layers, the structure of the mixer layer, the parametrisation, and the initialisation strategy.

• •

  Classical-quantum loop phase — The circuit is prepared and executed either on a QPU or on a simulator. After the execution, measurement data is obtained from a QPU or a simulator (the wavefunction is obtained if a wavefunction simulator is being used). The measurement outcomes are then used to compute the cost Hamiltonian expectation value corresponding to the current set of variational parameters. Based on this expectation value, the classical optimiser proposes an updated set of variational parameters to be used in the next iteration. The algorithm thus consists of a loop over the circuit’s creation-execution, followed by optimisation of the variational parameters. This loop exits when the optimiser’s stopping criterion is met, and the variational parameters are considered optimised. We refer to these final values of the parameters as the ‘optimised’ or ‘optimal’ parameters, and the corresponding output quantum state as the ‘optimised’ or ‘optimal’ state.

• •

  Result phase — The third and final stage is the collection of the results and their parsing and presentation to the user. The raw output of QAOA is a distribution over all the computational basis states $\{|z\rangle\}$, where $|z\rangle$ denotes an eigenstate of $H_{c}$, and the set of associated optimal parameters, which we denote $\{\beta^{*}\}$ and $\{\gamma^{*}\}$. Therefore, finding a unique bitstring solution encoding the answer to the original QUBO problem involves using a post-selection scheme after completing the optimisation process. Common choices are either the most probable bitstring, or the one corresponding to the lowest expectation value measured, depending on the goals at hand.

Several modifications, enhancements, and extensions of the standard QAOA have been proposed [27, 28, 9]. Intuitively, these modifications form a family of QAOAs, related in their structure through the layer-wise application of mixer and cost operations. Recursive QAOA (RQAOA) [9], which we introduce within the context of OpenQAOA in Section IV.6, is a prominent member of this family.

OpenQAOA comes with two pre-defined workflows: QAOA and RQAOA (see Section IV.6). Support for the Alternating Operator Ansatz [27] and ADAPT-QAOA [28] is planned for future releases. While workflows implement QAOAs with the hybrid structure highlighted in Section III, the API structure is slightly different. Given a QUBO problem, the simplest executable workflow is the following:

A QAOA object is instantiated via the initialisation step q = QAOA(). In the simplest case, all the required variational parameters and circuit properties are set to default values. In the following sections, we will show how to customise these parameters and properties within the OpenQAOA workflow and implement different flavours of QAOA. This process includes customising circuit properties, choosing particular backends and devices, and configuring classical optimisers.

The compilation step q.compile(qubo) is where the internal abstract representation of the QAOA is generated. The QUBO problem qubo used in the compilation step is prepared either through the OpenQAOA problem classes located in openqaoa.problems.problem, or it can be directly specified in terms of Python primitives by the user. OpenQAOA natively supports a set of popular problem classes modelled as QUBO problems. Note that, until this stage, the description of the QAOA is device independent and solely defined in terms of OpenQAOA primitives.

The final stage is the optimisation step, where the backend-specific circuit is created and submitted to either a simulator or a QPU. Subsequently, the optimisation loop is performed, and when the desired exit criteria are satisfied, the results will be accessible as attributes q.result_information of the QAOA object.

The initialisation step is where the parameters of the QAOA can be modified to suit the user’s needs. Codeblock 4 illustrates an example of how a workflow can be customised, and Sections IV.2 — IV.5 are dedicated to explaining each customisation step in detail.

In OpenQAOA, the circuit ansatz can be modified easily through the workflow routines. This is done by using the set_circuit_properties method.

The user can specify the type of circuit parametrisation and its initialisation through the keywords param_type and init_type, and the number of layers is set through p. OpenQAOA offers several classes of parametrisation.

• •

  The default is the Standard parametrisation. In a given layer, each qubit is assigned the same mixer rotation angle $\beta$, and each term in the cost Hamiltonian is assigned the same angle $\gamma$.

• •

  The Fourier parametrisation is defined through the discrete cosine and sine transforms of the $\gamma$ and $\beta$ parameters across several layers, as proposed in Ref. [7].

• •

  The Annealing parametrisation emulates a discretised adiabatic annealing schedule using a QAOA circuit.

• •

  Some parametrisations can further be generalised by increasing the number of free variational parameters. The With-Bias sub-class parametrises the linear terms independently from the quadratic terms in the Hamiltonian.

• •

  The Extended sub-class parametrises each term in the Hamiltonian individually. In a standard QAOA circuit, there are $2p$ variational parameters, where $p$ is the number of layers. In the extended parametrisation, the number of parameters equals the number of terms in the Hamiltonian of Eq. 2. For fully-connected cost Hamiltonians, where all variables appear together in quadratic terms, the total number of parameters is $O(n^{2})$, where $n$ is the number of variables. In general, the connectivity of the cost Hamiltonian for classical optimisation problems is defined by the pairs of $(i,j)$ in the second term of Eq. 2.

More information on the construction of these parametrisations may be found in the OpenQAOA documentation [29].

Besides setting the parametrisation class, initial values for the parameters must also be provided at the beginning of the optimisation loop. OpenQAOA allows for three initialisation strategies: random, custom, and linear ramp. The linear ramp strategy draws inspiration from quantum annealing, and linearly increases the values of the $\gamma$ parameters across the QAOA layers, while linearly decreasing the $\beta$ parameters [30, 31].

OpenQAOA builds circuits compatible with many devices. The quantum computing cloud services supported are Amazon Braket, IBMQ, and Rigetti Computing’s Quantum Cloud Services. With access to different cloud providers, users can perform QAOA on a variety of simulators and QPUs supported by these organisations. Local simulators are also available. The user can select the desired backend devices through a workflow as follows:

The OpenQAOA backend is responsible for creating and executing the device-specific circuit, computing the expectation value, and interacting with the classical optimiser. The method set_backend_properties() can then be used to set common backend properties, such as the number of shots or the CVaR $\alpha$-parameter [32]. It also enables the preparation of an arbitrary initial state through the prepend_state parameter.

OpenQAOA provides access to simulators from popular open-source libraries such as Qiskit’s QASM Simulator and PyQuil’s Statevector Simulator, as well as a alternative option referred to as vectorized. The vectorized backend is a fast, QAOA-specific simulator developed by Entropica Labs, primarily based on the common Python library NumPy [33].

OpenQAOA automatically runs the classical-quantum optimisation loop by invoking the method q.optimize() as shown in Codeblock 3. The choice of optimiser lies with the user, and OpenQAOA supports all optimisers found in SciPy’s minimize method [34].

OpenQAOA features native implementation of custom optimisation methods, including gradient descent, root mean squared propagation (RMSProp), Newton descent, quantum natural gradient descent [35], and simultaneous perturbation stochastic approximation (SPSA) [36]. The codebase also provides both approximate and exact methods to implement derivative computations. These include finite difference, SPSA, and the recently developed parameter shift  [37, 38, 39] and stochastic parameter shift methods for quantum circuits [40].

Finally, we emphasise that the optimiser has flags for tracking and logging the optimisation status, which we anticipate to be useful for research and debugging purposes. We discuss the content of these logs in the next section.

In its most basic form, the result of a QAOA computation consists of a list of measurement outcomes (or the optimal statevector, if a statevector simulator was employed), and the corresponding optimal variational parameters and optimal cost. In addition to these, OpenQAOA also returns the $k$ bitstrings associated with the $k$ most probable states in the optimised distribution, and the unique bitstring corresponding to the lowest cost function value observed in the entire optimisation process.

As an iterative algorithm, QAOA generates additional data during the optimisation loop, which can also be stored for later use. The OpenQAOA optimiser is thus equipped with logger methods to provide metrics from the classical optimisation process, such as the cost expectation value and the corresponding variational parameters for the $i^{th}$ iteration, and the measurement counts for the observed bitstrings. A summary of the attributes of the result object is given in Figure 8.

RQAOA consists of running QAOA recursively and using the output statistics at each step to eliminate variables from the problem. When the reduced problem reaches a pre-defined cutoff size, it is solved exactly via classical methods. The final answer is then reconstructed from the solution obtained from this classical computation by re-inserting the eliminated variables in the appropriate order. Notably, the final output of RQAOA is a unique bitstring.

In OpenQAOA, RQAOA is implemented through a workflow built on top of the QAOA workflow. In its simplest code formulation, it reads as follows:

OpenQAOA incorporates the RQAOA initially formulated in Ref [9], and two generalised versions, which enable multiple variable (qubit) eliminations during the recursive process. These strategies are called custom and adaptive [21]. The custom strategy allows the user to define the number of eliminations performed at each step. The adaptive strategy adaptively selects how many qubits to eliminate at each step based on a statistical criterion, with the user specifying the maximum number of eliminations allowed per step.

Note how the RQAOA workflow requires a QAOA object to be instantiated: this can be customised in the same way as a regular QAOA workflow, as described in the preceding sections.

OpenQAOA workflows help orchestrate the entire QAOA routine on the user’s backend of choice. They automate sequential creation and initialisation of different components that make up a QAOA computation, based on the inputs provided by the user. These components include the problem statement, variational parameters, device-specific backends and authentication, and classical optimiser initialisation.

However, OpenQAOA also gives the user the option of building the QAOA computation manually, by-passing the pre-defined workflows. We refer to this as factory mode, and Codeblock 10 presents an example to demonstrate the required steps. Factory mode allows greater flexibility, with more room for experimentation for advanced users. Since one of the central goals of OpenQAOA is to enable research, we consider this a significant feature. We now briefly discuss a few instances wherein a user may wish to employ the factory mode.

Using a custom classical optimiser: OpenQAOA can facilitate creating the variational parameters and an authenticated backend with the ability to initialise QAOA circuits. The custom classical optimiser can subsequently call the expectation method of the backend, bypassing the need for the optimisers supported by OpenQAOA.

Plotting cost landscapes: OpenQAOA backends support computing the cost value with respect to a set of parameter values (under the specified circuit parametrisation) for a QAOA circuit. A user may choose to define a grid of values for the parameters – for example, $\beta$ and $\gamma$ for a $p=1$ standard QAOA circuit – and obtain a plot of the cost landscape over the specified region.

More workflows: Accessing the components directly, a user can build more complex workflows, for instance, a layerwise QAOA approach to optimise parameters for a depth-$p$ circuit.

Obtain the QAOA circuit: With a greater degree of control in the factory mode, users may also choose to export the QAOA circuit. Note, however, that the circuit will be defined in the language of the chosen device. For instance, a qiskit.QuantumCircuit if the selected device was an IBMQ QPU or simulator.

Once the optimisation loop has terminated, the result is available as optimizer_obj.qaoa_result, following a similar structure as the results obtained through a workflow.