Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Computer and Communications

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

Parfait Atchade-Adelomou, Elisabet Golobardes Ribé, X. Vilasis-Cardona

Published Jan 1, 2020• 8 citations
Publisher

Abstract

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.

DOI
10.4236/jcc.2020.811004

Related papers

Using the Parameterized Quantum Circuit combined with Variational-Quantum-Eigensolver (VQE) to create an Intelligent social workers' schedule problem solver

Parfait Atchade-Adelomou, Elisabet Golobardes-Ribé, X. Vilasis-Cardona

The social worker scheduling problem is a class of combinatorial optimization problems that combines scheduling with routing issues. These types of problems with classical computing can only be solved, in the best of cases, in an approximate way and significantly when the input data does not grow considerably. Today, the focus on the quantum computer should no longer be only on its enormous computing power, but also on the use of its imperfection for this era, (Noisy Intermediate-Scale Quantum (NISQ)) to create a powerful optimization and learning device that uses variational techniques. We had already proposed a formulation and solution of this problem using the capacity of the quantum computer. In this article, we present some broad results of the experimentation techniques. And above all, we propose an adaptive and intelligence solution, which efficiently recalculates the schedules of social workers. Taking into account new restrictions and changes in the initial conditions, by using a case-based reasoning system and the variational quantum eigensolver based on a finite-depth quantum circuit. That encodes the ground state of the Hamiltonian of social workers. The quantum feasibility of the algorithm will be modelled with docplex and tested on IBMQ computers.

arXiv:2010.05863•Oct 12, 2020•5 citations

Solving the Traveling Salesman Problem Using Quantum Devices: QUBO and HOBO Formulations

G. V. Shuvalov, E. N. Krivtsova, M. A. Remnev +1 more

Abstract The traveling salesman problem (TSP) forms the foundation for many logistics and optimization tasks. At the same time, this problem is NP-hard and requires significant computational resources. Quantum computing promises to substantially accelerate computations or increase solution accuracy. The TSP can be conveniently mapped onto the quadratic unconstrained binary optimization (QUBO) formulation, which in turn can be solved using variational quantum eigensolver (VQE) and quantum approximate optimization algorithm (QAOA) methods, but this mapping requires a quadratic number of qubits. The higher-order binary optimization (HOBO) formulation requires significantly fewer qubits, but it contains higher-order terms. In our work, we thoroughly investigate both formulations and provide a practical recipe for solving the TSP. We give a comprehensive study and compare in detail QUBO and HOBO formulations.

Russian Microelectronics•Dec 1, 2025•0 citations

QUBO formulations of three NP problems

Anuradha Mahasinghe, Vishmi Fernando, Paduma Samarawickrama

With the recent advancements in the field of combinatorial optimization, QUBO (quadratic unconstrained binary optimization) has become a topic of intense interest, as a problem format acceptable to several hardware heuristics such as quantum and digital annealers. Accordingly, transforming hard mathematical problems into QUBO problems is of particular importance. In this paper, we restate three problems in NP-complete and NP-hard classes as QUBO problems with proofs of equivalence. Our problems of interest are the numerical three-dimensional matching problem, the monochromatic triangle problem and the optimum facility location problem. Furthermore, we comment on the feasibility of these formulations on sophisticated QUBO solving platforms.

Journal of Information and Optimization Sciences•Oct 3, 2021•6 citations

Uma reformulação quadrática para variáveis binárias aplicadas ao problema de otimização quadrática irrestrita

Petra Maria Bartmeyer, Christiano Lyra

The Quadratic Unconstrained Binary Optimization problem (QUBO) is the optimization of a quadratic function where the variables are binary; it is frequently used to model combinatorial problems in operational research and graph theory.QUBO is an NP-Complete problem and a challenge to exact methods.Therefore, the problem has been approached with heuristics.Here, we propose new ideas to solve QUBO with exact methods.We develop a new quadratic formulation that maps the binary problem into an equivalent continuous optimization problem with a single quadratic constraint.A further development delves into Lagrangian inspired concepts to obtain an equivalent unconstrained formulation.The case studies illustrate the benefit and limitations of both formulations.Also, the computational experiments show that problems with up to 2500 variables were solved with processing times under 500 seconds to achieve an average gap under 1%; these results also show that the approach allowed to solve, with an exact method, instances of 1500 more binary variables than the instances considered in previous papers.

Anais do Simpósio Brasileiro de Pesquisa Operacional•Jan 1, 2018•0 citations

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813•Jan 19, 2021•12 citations

Modeling Linear Inequality Constraints in Quadratic Binary Optimization for Variational Quantum Eigensolver

Miguel Paredes Quiñones, Catarina Junqueira

This paper introduces the use of tailored variational forms for variational quantum eigensolver that have properties of representing certain constraints on the search domain of a linear constrained quadratic binary optimization problem solution. Four constraints that usually appear in several optimization problems are modeled. The main advantage of the proposed methodology is that the number of parameters on the variational form remain constant and depend on the number of variables that appear on the constraints. Moreover, this variational form always produces feasible solutions for the represented constraints differing from penalization techniques commonly used to translate constrained problems into unconstrained one. The methodology is implemented in a real quantum computer for two known optimization problems: the Facility Location Problem and the Set Packing Problem. The results obtained for this two problems with VQE using 2-Local variational form and a general QAOA implementation are compared, and indicate that less quantum gates and parameters were used, leading to a faster convergence.

arXiv:2007.13245•Jul 26, 2020•6 citations
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 social worker scheduling problem is a class of combinatorial optimization problems that combines scheduling with routing issues. These types of problems with classical computing can only be solved, in the best of cases, in an approximate way and significantly when the input data does not grow considerably. Today, the focus on the quantum computer should no longer be only on its enormous computing power, but also on the use of its imperfection for this era, (Noisy Intermediate-Scale Quantum (NISQ)) to create a powerful optimization and learning device that uses variational techniques. We had already proposed a formulation and solution of this problem using the capacity of the quantum computer. In this article, we present some broad results of the experimentation techniques. And above all, we propose an adaptive and intelligence solution, which efficiently recalculates the schedules of social workers. Taking into account new restrictions and changes in the initial conditions, by using a case-based reasoning system and the variational quantum eigensolver based on a finite-depth quantum circuit. That encodes the ground state of the Hamiltonian of social workers. The quantum feasibility of the algorithm will be modelled with docplex and tested on IBMQ computers.
Abstract The traveling salesman problem (TSP) forms the foundation for many logistics and optimization tasks. At the same time, this problem is NP-hard and requires significant computational resources. Quantum computing promises to substantially accelerate computations or increase solution accuracy. The TSP can be conveniently mapped onto the quadratic unconstrained binary optimization (QUBO) formulation, which in turn can be solved using variational quantum eigensolver (VQE) and quantum approximate optimization algorithm (QAOA) methods, but this mapping requires a quadratic number of qubits. The higher-order binary optimization (HOBO) formulation requires significantly fewer qubits, but it contains higher-order terms. In our work, we thoroughly investigate both formulations and provide a practical recipe for solving the TSP. We give a comprehensive study and compare in detail QUBO and HOBO formulations.
With the recent advancements in the field of combinatorial optimization, QUBO (quadratic unconstrained binary optimization) has become a topic of intense interest, as a problem format acceptable to several hardware heuristics such as quantum and digital annealers. Accordingly, transforming hard mathematical problems into QUBO problems is of particular importance. In this paper, we restate three problems in NP-complete and NP-hard classes as QUBO problems with proofs of equivalence. Our problems of interest are the numerical three-dimensional matching problem, the monochromatic triangle problem and the optimum facility location problem. Furthermore, we comment on the feasibility of these formulations on sophisticated QUBO solving platforms.
The Quadratic Unconstrained Binary Optimization problem (QUBO) is the optimization of a quadratic function where the variables are binary; it is frequently used to model combinatorial problems in operational research and graph theory.QUBO is an NP-Complete problem and a challenge to exact methods.Therefore, the problem has been approached with heuristics.Here, we propose new ideas to solve QUBO with exact methods.We develop a new quadratic formulation that maps the binary problem into an equivalent continuous optimization problem with a single quadratic constraint.A further development delves into Lagrangian inspired concepts to obtain an equivalent unconstrained formulation.The case studies illustrate the benefit and limitations of both formulations.Also, the computational experiments show that problems with up to 2500 variables were solved with processing times under 500 seconds to achieve an average gap under 1%; these results also show that the approach allowed to solve, with an exact method, instances of 1500 more binary variables than the instances considered in previous papers.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.
This paper introduces the use of tailored variational forms for variational quantum eigensolver that have properties of representing certain constraints on the search domain of a linear constrained quadratic binary optimization problem solution. Four constraints that usually appear in several optimization problems are modeled. The main advantage of the proposed methodology is that the number of parameters on the variational form remain constant and depend on the number of variables that appear on the constraints. Moreover, this variational form always produces feasible solutions for the represented constraints differing from penalization techniques commonly used to translate constrained problems into unconstrained one. The methodology is implemented in a real quantum computer for two known optimization problems: the Facility Location Problem and the Set Packing Problem. The results obtained for this two problems with VQE using 2-Local variational form and a general QAOA implementation are compared, and indicate that less quantum gates and parameters were used, leading to a faster convergence.