Timezone: »

Towards Quantum Machine Learning for Constrained Combinatorial Optimization: a Quantum QAP Solver
Xinyu Ye · Ge Yan · Junchi Yan

Thu Jul 27 04:30 PM -- 06:00 PM (PDT) @ Exhibit Hall 1 #211

Combinatorial optimization (CO) on the graph is a crucial but challenging research topic. Recent quantum algorithms provide a new perspective for solving CO problems and have the potential to demonstrate quantum advantage. Quantum Approximate Optimization Algorithm (QAOA) is a well-known quantum heuristic for CO constructed by a parametric quantum circuit. However, QAOA is originally designed for unconstrained problems and the circuit parameters and solutions are jointly solved with time-consuming iterations. In this paper, we propose a novel quantum neural network (QNN) for learning CO problems in a supervised manner to achieve better and faster results. We focus on the Quadratic Assignment Problem (QAP) with matching constraints and the node permutation invariance property. To this end, a quantum neural network called QAP-QNN is devised to translate the QAP into a constrained vertex classification task. Moreover, we study two QAP tasks: Graph Matching and Traveling Salesman Problem on TorchQauntum simulators, and empirically show the effectiveness of our approach.

Author Information

Xinyu Ye (Shanghai Jiaotong University)
Ge Yan (Shanghai Jiao Tong University)
Junchi Yan (Shanghai Jiao Tong University)

More from the Same Authors