Quantum approximate algorithm for NP optimization problems with constraints

The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the c...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-02
Main Authors: Ruan, Yue, Marsh, Samuel, Xue, Xilin, Li, Xi, Liu, Zhihao, Wang, Jingbo
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Linear functions
Mathematical programming
Optimization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA or QAA, one needs to find a way to encode problem constraints into the scheme. In this paper, we formalize different constraint types to linear equalities, linear inequalities, and arbitrary form. Based on this, we propose constraint-encoding schemes well-fitting into the QAOA framework for solving NP combinatorial optimization problems. The implemented algorithms demonstrate the effectiveness and efficiency of the proposed scheme by the testing results of varied instances of some well-known NP optimization problems. We argue that our work leads to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to combinatorial problems with various types of constraints.
ISSN:2331-8422