Warm Starting Variational Quantum Algorithms for Parameterized Combinatorial Optimization

Warm Starting Variational Quantum Algorithms for Parameterized Combinatorial Optimization

Abstract:

In the Noisy Intermediate Scale era of Quantum Computing (NISQ), Variational Quantum Algorithms (VQAs) are a key paradigm for producing useful results in spite of hardware limitations. These algorithms can be adapted to multiple domains, such as condensed matter physics and combinatorial optimization. Problems in these domains can be modeled as Ising Hamiltonians. To model physical systems, Hamiltonians usually contain parameters controlling global forces, such as magnetic fields. In contrast, Hamiltonians modeling combinatorial optimization problems (COPs) are usually not parametrized in the literature, describing a specific problem instance. However, in reality, multiple global variables, such as the time of the day or the direction of the market, can influence instances of COPs. This thesis introduces parametrized Hamiltonians for combinatorial optimization through the Maximum-Cut and Knapsack problems, presenting a framework that can be extended to other COPs. The framework widens current approaches for modeling COPs to describe multiple problem instances using a single Hamiltonian with global parameters. Subsequently, this work investigates the optimization of parametrized COPs using various variants of VQAs, testing alternative objective functions tailored specifically for COPs. Finally, this work investigates the transfer of optimized parameters between problem instances corresponding to different Hamiltonian parameter values, evaluating whether parameters producing satisfactory solutions for one configuration of a problem can produce similar results for different configurations. Two simple modifications to existing techniques are presented for this task, termed Adaptive Start and Aggregated Learning. This thesis presents a different approach to combinatorial optimization and investigates the potential of this new framework.

Author:

Federico Harjes Ruiloba

Advisors:

Tobias Rohe, Jonas Stein, Claudia Linnhoff-Popien

Student Thesis | Published December 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors