Towards Quantum Machine Learning for Constrained Combinatorial Optimization: a Quantum QAP Solver

Xinyu Ye, Ge Yan, Junchi Yan
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:39903-39912, 2023.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-ye23g, title = {Towards Quantum Machine Learning for Constrained Combinatorial Optimization: a Quantum {QAP} Solver}, author = {Ye, Xinyu and Yan, Ge and Yan, Junchi}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {39903--39912}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/ye23g/ye23g.pdf}, url = {https://proceedings.mlr.press/v202/ye23g.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Towards Quantum Machine Learning for Constrained Combinatorial Optimization: a Quantum QAP Solver %A Xinyu Ye %A Ge Yan %A Junchi Yan %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-ye23g %I PMLR %P 39903--39912 %U https://proceedings.mlr.press/v202/ye23g.html %V 202 %X 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.
APA
Ye, X., Yan, G. & Yan, J.. (2023). Towards Quantum Machine Learning for Constrained Combinatorial Optimization: a Quantum QAP Solver. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:39903-39912 Available from https://proceedings.mlr.press/v202/ye23g.html.

Related Material