Formulation of the Social Workers’ Problem in Quadratic Unconstrained Binary Optimization Form and Solve It on a Quantum Computer

• 作者: Atchade Parfait Adelomou Elisabet Golobardes Ribé Xavier Vilasis Cardona
• 来源期刊: 电脑和通信(英文)
• 学科: 数学
• 关键词: QUBO Quantum Algorithms Variational Quantum Eigensolvers Combinatorial Optimization Algorithms
• 年，卷（期）: dnhtxyw_2020,（11）
• 页码范围: 44-68
• 页数: 25页
• 分类号: O17

摘要

The problem of social workers visiting their patients at home is a class of combinatorial optimization problems and belongs to the class of problems known as NP-Hard. These problems require heuristic techniques to provide an efficient solution in the best of cases. In this article, in addition to providing a detailed resolution of the social workers’ problem using the Quadratic Unconstrained Binary Optimization Problems (QUBO) formulation, an approach to mapping the inequality constraints in the QUBO form is given. Finally, we map it in the Hamiltonian of the Ising model to solve it with the Quantum Exact Solver and Variational Quantum Eigensolvers (VQE). The quantum feasibility of the algorithm will be tested on IBMQ computers.