Extended Quantum Computing Patterns

"Fine-tune an optimization algorithm by warm starting it" (Weigold et al. 2021)

The best solution for an optimization problem must be found or approximated. For classical methods, the Unique Game Conjecture (UGC) states that there is a theoretical upper bound for the approximation ratio which can not be further improved. This implies that classical methods can only approximate up to this bound, i.e., up to a certain extent. However, since the UGC is not true when entanglement is used, quantum algorithms have the potential to surpass these bounds, i.e., they can approximate better solutions than classical algorithms.

–

Start by using a classical approach to approximate the best solution. The classical approximation result can often be found as a solution for a related problem, e.g., by weakening or eliminating constraints of the problem.

Using the warm starting approach, a proceeding optimization is initialized with the classical approximation result which should be nearer to the optimum than a random starting point. The warm starting procedure should also be taken into account for the overall runtime complexity.

–

Warm start can be used to provide initial starting solutions for Quantum Approximate Optimization Algorithm (QAOA) or Variational Quantum Eigensolver (VQE).

Warm starting was shown to be beneficial for the MaxCut problem Tate et al. 2020 and another optimization use case Egger, Marecek and Woerner 2020. The approach presented in Barkoutsos 2018 can also be regarded as a warm start for Variational Quantum Eigensolver (VQE) Egger, Marecek and Woerner 2020.

Quantum approximate optimization algorithm (PlanQK) Hybrid Transfer Learning (PlanQK)