Extended Quantum Computing Patterns

Alternating Operator Ansatz (AOA)

Aliases: –

Tags:

© Weigold, M.; Barzen, J.; Leymann, F.; and Vietz, D: Patterns For Hybrid Quantum Algorithms. In: Proceedings of the 15th Symposium and Summer School on Service-Oriented Computing (SummerSOC 2021), https://doi.org/10.1007/978-3-030-87568-8_2

Intent

"Approximate the solution of an optimization problem" (Weigold et al. 2021)

Context

To solve a combinatorial optimization problem, a bit string $z=z_1\ldots z_n$ must be found that fulfills a maximum number of $m$ clauses by assigning every binary variable $z_i$ to either 0 or 1. Each of the $m$ clauses involves a subset of these variables. The domain, e.g., all feasible solutions, is either every possible bit string $z$ of length $n$ or a subset of the bit strings. For a bit string $z$, the value of the objective function $C(z)$ equals the number of clauses that it fulfills:

$$ \newcommand{\colVec}[1]{% inline column vector \bigl( \begin{smallmatrix}#1\end{smallmatrix}\bigr) } \newcommand{\bigColVec}[1]{% inline column vector \left( \begin{matrix}#1\end{matrix}\right) } \newcommand{\state}[1]{{\left| #1 \right>}} C(z)=\sum_{j=1}^m C_{j}(z) \text{ where } C_{\alpha}(z) = \begin{cases} 1,& \text{if }C_{\alpha}\text{ is fulfilled by z}\\ 0, & \text{otherwise} \end{cases} $$

For larger problem instances, a brute force approach (which evaluates the objective function of every solution to find the best solution) is computationally too expensive. Therefore, a heuristic approach that approximates the best solution is also acceptable.

Solution

An Variational Quantum Algorithm (VQA) approach is used to solve the problem: As a first step, the quantum register is initialized with $\newcommand{\state}[1]{{\left| #1 \right>}} \state{s}$ (see solution sketch) which is either a single solution or a superposition of multiple solutions. Preparing the state $\newcommand{\state}[1]{{\left| #1 \right>}} \state{s}$ is assumed to be efficient, i.e., in constant or at most logarithmic depth. Note that this assumption does not hold for all quantum states. After the Initialization, an ansatz is applied. To construct the circuit of the ansatz, a phase-separating operator $U(C,\gamma)$ as well as a mixing operator $U(B,\beta)$ are used where $\gamma$ and $\beta$ are the parameter sets. The phase-separating operator applies a Phase Shift where the phase of a computational basis state $\newcommand{\state}[1]{{\left| #1 \right>}} \state{y}$ is changed according to its value of the objective function $C(y)$:

E.g., an operator $U(C,\gamma)$ can be defined that applies a shift for every clause fulfilled by a solution $\newcommand{\state}[1]{{\left| #1 \right>}} \state{y}$.

The second operator is the mixing operator which alters the amplitude of the solutions. Thereby, it provides transitions between solutions and especially allows to transition between an arbitrary pair of solutions within the problem domain for some well-chosen parameter $\beta^*$. As a result, this operator reflects the domain's structure.

Each iteration on the quantum computer starts with an Initialization of the state $\newcommand{\state}[1]{{\left| #1 \right>}} \state{s}$ and, then, applies an ansatz circuit which is based on $C(\gamma)$ and $B(\beta)$. The ansatz circuit consists of $p$ alternating unitaries which are drawn from the operators and lead to the following state:

$$ \newcommand{\colVec}[1]{% inline column vector \bigl( \begin{smallmatrix}#1\end{smallmatrix}\bigr) } \newcommand{\bigColVec}[1]{% inline column vector \left( \begin{matrix}#1\end{matrix}\right) } \newcommand{\state}[1]{{\left| #1 \right>}} \state{\gamma, \beta} = U(B,\beta_p)U(C,\gamma_p) \ldots U(B,\beta_1)U(C,\gamma_1) \state{s} $$

In the first iteration, the parameter sets $\gamma, \beta$ are chosen randomly and $p\in \mathbb{N}$ defines a hyperparameter.
Measuring this state gives $z$ as a single solution which can be evaluated by the objective function $C$. Sampling this state allows to determine the expectation values for $\gamma$ and $\beta$ which is by definition smaller or equal to the maximum of the objective function:

$$ \newcommand{\state}[1]{{\left| #1 \right>}} \left< C\right>_{\state{\gamma, \beta}} = \left< \gamma, \beta |C |\gamma, \beta \right> = \bigg \langle \sum x_z \state{z} \bigg | \sum x_z f(z)\state{z} \bigg \rangle \\ = \sum |x_z|^2 f(z) \leq \sum |x_z|^2 f(z') = f(z') = C_{max} $$

Based on the expectation values, the parameters $\gamma$ and $\beta$ can be optimized until the termination condition is satisfied.

Result

This approach is applicable for NISQ devices and can be adjusted for a particular problem domain. Since NISQ devices are limited by their hardware, only small values for $p$ can be chosen as this hyperparameter determines the width of the circuit. Nevertheless, choosing suitable mixing and phase-separating operators is not trivial for a problem at hand and, currently, an open research question. The convergence of the solution depends on the chosen operators (based on which the ansatz is constructed), the objective function, and the optimization strategy for updating the parameters.

Related Patterns

This pattern is a refinement of Variational Quantum Algorithm (VQA); the varied parameters for the ansatz are $\beta$ and $\gamma$. Note that Phase Shift Leymann 2019 is used within the ansatz to mark solutions based on their value of the objective function. To encode solutions, Basis Encoding Weigold et al. 2020 is used. This pattern can be combined with Warm Start.

Known Uses

In the original publication Hadfield et al. 2019, various applications of this approach are discussed for different optimization problems. Use-cases of this pattern can be found in Wang et al. 2020 and Fingerhuth, Babej and Ing 2018.

Quantum approximate optimization algorithm (PlanQK)