2395. Penalty Factor Optimization for Quantum Annealing – A Multiobjective Approach
Invited abstract in session WB-16: Beyond the limits of QUBO formalism, stream Quantum OR .
Wednesday, 10:30-12:00Room: Esther Simpson 2.07
Authors (first author is the speaker)
| 1. | Pascal Halffmann
|
| Financial Mathematics, Fraunhofer Institute for Industrial Mathematics ITWM | |
| 2. | Michael Trebing
|
| Fraunhofer ITWM |
Abstract
Quadratic unconstrained binary optimization problems (QUBOs) are the working horses for solving optimization problems on quantum computers. An efficient transformation from other problem formulations to QUBOs requires to model constraints as penalty terms with penalty factors as part of the objective function. While constraints can be incorporated in a quantum circuit on gate-based quantum computers using e.g. constraint-preserving mixers, such a direct approach does not exist for quantum annealing. Picking suitable penalty factor is the key challenge in the transformation. Previous approaches rely on the user’s experience or utilize machine learning.
We present a novel approach that identifies a QUBO as a weighted sum scalarization of a multiobjective optimization problem with both aggregations of penalty terms and the original objective function as objective functions. Penalty factors serve as weights in the weighted sum problem. We adapt existing methods from multiobjective optimization finding so-called lexicographic optimal solutions by iteratively changing the weights. QUBOs are iteratively solved using quantum annealing, where the penalty factors are adjusted based on the previous outcome. These methods do neither rely on existing data nor on the user’s experience on penalty factors, domain knowledge on the problem is sufficient. We compare the methods against each other as well as against the Nelder-Mead method as a standard approach in a computational study.
Keywords
- Algorithms
- Programming, Multi-Objective
- Programming, Quadratic
Status: accepted
Back to the list of papers