Thinh DINH

Title: Efficient Hamiltonian Reduction for Scalable Quantum Computing on Clique Cover/Graph Coloring Problems in SatCom

Abstract:  Clique cover and graph coloring are complementary problems which have many applications in wireless communications, especially in satellite communications (SatCom). They are NP-hard problems which are intractable for classical computers. Recently, quantum computing has emerged as a novel technology which revolutionizes how to solve challenging optimization problems by formulating Quadratic Unconstrained Binary Optimization (QUBO), then preparing Hamiltonians as inputs for quantum computers. However, due to limited hardware resources, existing quantum computers are unable to tackle large optimization spaces. In this work, we studied how to apply quantum computing to solve Beam Placement (BP) problems, a variant of clique cover problem in Low-Earth Orbit (LEO) SatCom systems. We propose an efficient Hamiltonian Reduction method that allows quantum processors to solve large BP instances encountered in LEO systems. We conduct our simulations on real quantum computers (D-Wave Advantage) using a real dataset of vessel locations in the US. Numerical results show that our algorithm outperforms commercialized solutions of D-Wave by allowing existing quantum annealers to solve 17.5 times larger BP instances while maintaining high solution quality. Although quantum computing cannot theoretically overcome the hardness of BP problems, this work contributes early efforts to applying quantum computing in satellite optimization problems, especially applications formulated as clique cover/graph coloring problems.

Bio: Dr. Thinh Dinh received his PhD degree in Information System Technology and Design at the Singapore University of Technology and Design in 2019, supervised by Prof. Tony Quek. His PhD focused on resource allocation problems in Edge Computing. He was the recipient of IEEE Stephen O. Rice prize in 2020 (Best Paper Award of IEEE Transactions on Communications over the previous 3 years), Best Paper Award of IEEE ATC in 2021 for selected works in that topic. After his PhD, he joined Trusting Social, and Fossil’s Connected Devices Group working on telco and wearable AI applications. Then, he joined University of Luxembourg as a research associate. Currently, he is a researcher at University of Information Technology, a member of Vietnam National University. His research interests focus on applications of quantum computing in wireless communications.

Contact the speaker: