Extended Quantum Computing Patterns

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

To solve a combinatorial optimization problem, a bit string \(z=z_1\ldots z_n\) must be found which assigns each binary variable \(z_i\) to either 0 or 1 and fulfills a maximum number of \(m\) clauses. Hereby, each clause involves a subset of the variables. In contrast to the potentially constrained domain of solutions in Alternating Operator Ansatz (AOA), every bit string \(z=z_1\ldots z_n\) of length \(n\) is a solution to the problem.

–

The overall structure of the Quantum Approximate Optimization Algorithm (QAOA) (Farhi and Goldstone 2014) approach is depicted in the solution sketch.

First, a Uniform Superposition realizing all possible solutions in Basis Encoding is prepared. E.g., the solution with all binary values assigned to 0 is represented by \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{0 \ldots 0 0}\) and is contained in the superposition.

Then, an ansatz circuit is applied that is constructed based on the two operators \(U(C,\gamma)\) and \(U(B,\beta)\):

The first operator is a phase shift \(e^{-i\gamma}\) on every computational basis state for every clause that is fulfilled. However, this marks but does not change the amplitude of computational basis states (which each represent a solution), thus, the second operator \(U(B,\gamma)\) is required. \(U(B,\gamma)\) defines a rotation around the \(X\)-axis for every qubit whereby the angle for the rotation depends on \(\gamma\). Based on the structure defined in Alternating Operator Ansatz (AOA), a trial state \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{\gamma,\beta}\) is prepared. Measuring this state results in a single bitstring, i.e., a solution that can be evaluated by the objective function. The parameters \(\beta\) and \(\gamma\) which are initialized randomly for the first iteration can then be adjusted. This iterative process continues until the termination condition is satisfied.

Pattern sketch, taken from: Weigold, Manuela; Barzen, Johanna; Leymann, Frank; and Vietz, Daniel: Patterns For Hybrid Quantum Algorithms. In: Proceedings of the 15th Symposium and Summer School on Service-Oriented Computing (SummerSOC 2021).

The depth of the overall circuit is at most \(mp + p\) (Farhi and Goldstone 2014) which is rather shallow. This is one reason why this algorithm is considered a promising candidate for NISQ devices. From a theoretical point of view, it can be noticed that the algorithm approximates the best solution if suitable small values for the parameters \(\gamma, \beta\) are chosen with \(p\rightarrow \infty\). Nevertheless, note that the performance of the algorithm also depends on the objective function and the optimization strategy.

–

In this pattern Uniform Superposition is used to represent the bitstrings of solutions in Basis Encoding. The higher-level structure of this pattern is described by Alternating Operator Ansatz (AOA) which also uses Phase Shift .

This algorithm was first proposed by Farhi, Goldstone, and Gutmann (Farhi and Goldstone 2014) and applied to the problem of finding a maximum cut of a graph (MaxCut). In a follow-up paper, an advantage over classical algorithms for the bounded occurrence problem (Farhi, Goldstone and Gutmann 2015) was shown. Shortly afterward, a classical algorithm (Barak et al. 2015) was published from which even better results can be expected for this particular problem instance.

Quantum approximate optimization algorithm (PlanQK)