Timezone: »

 
Poster
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
in Poster Session 6 »

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.

[ PDF]  [ Poster] 

Author Information

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

More from the Same Authors