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 Atchade Parfait Adelomou;Elisabet Golobardes Ribé;Xavier Vilasis Cardona(Research Group in Data Science for the Digital Society (DS4DS), Barcelona, Spain)

机构地区：[1]Research Group in Data Science for the Digital Society (DS4DS), Barcelona, Spain

出　　处：《Journal of Computer and Communications》2020年第11期44-68,共25页电脑和通信（英文）

摘　　要：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.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.

关 键 词：QUBO Quantum Algorithms Variational Quantum Eigensolvers Combinatorial Optimization Algorithms 

分 类 号：O17[理学—数学]