Formulation of the Social Workers’ Problem in Quadratic Unconstrained Binary Optimization Form and Solve It on a Quantum Computer
Open accessAbstract
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 claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
VQE has been applied to a QUBO formulation for the social workers problem, which explores problem specificities to avoid excessive auxiliary variables.
“VQE has been applied to a QUBO formulation for the social workers problem, which explores problem specificities to avoid excessive auxiliary variables [1], and to multi-coloring graph problems [104].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [1]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830 · cited 9× · see citing works
“Unfortunately, we are still in the NISQ [11] era.”
BackgroundMethodInfluentialA variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552 · see citing works
(2002) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718515 · Cited by 4,049 · see citing works
Scheduling of Vehicles from a Central Depot to a Number of Delivery Points
Clarke, G., & Wright, J. W. (1964) · Operations Research · doi:10.1287/opre.12.4.568 · Cited by 3,921 · cited 2× · see citing works
“This work is licensed under the Creative Commons Attribution-NonCommercial International License (CC BY-NC 4.0). http://creativecommons.org/licenses/by-nc/4.0/ Open Access DOI: 10.4236/jcc.2020.811004 45 Journal of Computer and Communications The social workers’ problem, as the combination of VRP and planning problem,…”
BackgroundInfluentialThe vehicle routing problem: An overview of exact and approximate algorithms
Laporte, G. (1992) · European Journal of Operational Research · doi:10.1016/0377-2217(92)90192-c · Cited by 1,764 · see citing works
An adaptive variational algorithm for exact molecular simulations on a quantum computer
Grimsley, H. R., Economou, S. E., Barnes, E., & Mayhall, N. J. (2019) · Nature Communications · doi:10.1038/s41467-019-10988-2 · Cited by 1,033 · cited 1× · see citing works
“One of the most famous algorithms is the Variational Quantum Eigensolver (VQE) [15] [16] [19] which is based on the variational principle [15].”
MethodAdiabatic Quantum Computation and Quantum Annealing
McGeoch, C. C. (2014) · Synthesis lectures on quantum computing · doi:10.2200/s00585ed1v01y201407qmc008 · Cited by 270 · see citing works
A quantum annealing architecture with all-to-all connectivity from local interactions
Lechner, W., Hauke, P., & Zoller, P. (2015) · Science Advances · doi:10.1126/sciadv.1500838 · Cited by 256 · cited 1× · see citing works
“The Adiabatic Quantum Computing uses a concept of quantum physics known as the adiabatic theorem [17].”
MethodAccelerated Variational Quantum Eigensolver
Wang, D., Higgott, O., & Brierley, S. (2019) · Physical Review Letters · doi:10.1103/physrevlett.122.140504 · Cited by 241 · cited 2× · see citing works
“Although, in principle, QAOA could be considered a gate model or a continuous-time configuration [15] [16], also like the Variational Quantum Eigensolvers (VQE) [11].”
BackgroundMethodA case study in programming a quantum annealer for hard operational planning problems
Rieffel, E. G., Venturelli, D., O’Gorman, B., Do, M. B., Prystay, E. M., & Smelyanskiy, V. (2014) · Quantum Information Processing · doi:10.1007/s11128-014-0892-x · Cited by 221 · cited 2× · see citing works
“There are several derivatives of this technique, but it is not in line with this paper [7] [10] [14] [18].”
MethodOn Rayleigh–Ritz ratios of a generalized Laplacian matrix of directed graphs
Wu, C. W. (2005) · Linear Algebra and its Applications · doi:10.1016/j.laa.2004.12.014 · Cited by 73 · cited 1× · see citing works
“The unknown eigenvectors are prepared by varying the experimental parameters and calculating the Rayleigh-Ritz ratio [20] in a classical minimization (Figure 1).”
MethodQuantum Computer Architecture: Towards Full-Stack Quantum Accelerators
Bertels, K., Sarkar, A., Hubregtsen, T., Serrao, M., Mouedenne, A. A., Yadav, A., Krol, A. M., & Ashraf, I. (2020) · Design, Automation, and Test in Europe · doi:10.23919/date48585.2020.9116502 · Cited by 46 · cited 3× · see citing works
“There are several techniques for building a quantum computer, and the way it is currently done is by combining multiple various multicore processors [9].”
BackgroundMethodParallel Simulated Annealing for the Job Shop Scheduling Problem
Bożejko, W., Pempera, J., & Smutnicki, C. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-01970-8_62 · Cited by 26 · cited 1× · see citing works
“This problem combines, on the one hand, a routing problem such as Vehicle Routing Problem (VRP) [1] [2] [3] and, on the other, a planning problem [4].”
BackgroundRobust optimisation of unconstrained binary quadratic problems
Lewis, M. W., Metcalfe, J., & Kochenberger, G. A. (2019) · International Journal of Operational Research · doi:10.1504/ijor.2019.104050 · Cited by 3 · see citing works
Flagged first, then by citations
Research works printed but not linked: 4
- Brucker, P. (2007) Scheduling Algorithms. Springer, New York.
- Bertels, K., Sarkar, A., Mouedenne, A., Hubregtsen, T., Yadav, A., Krol, A. and A. P. Adelomou et al. DOI: 10.4236/jcc.2020.811004 68 Journal of Computer and Communications
- Nielsen, M.A. and Chuang, I.L. (2000) Quantum Computation and Quantum In- formation. Cambridge University Press, Cambridge.
- Tran, T.T., Do, M., Rieffel, E.G., Frank, J., Wang, Z., O'Gorman, B., Venturelli, D. and Beck, J. (2016) A Hybrid Quantum-Classical Approach to Solving Scheduling Problems. Proceedings of the Ninth International Symposium on Combinatorial Search, Vancover, 20 June 2016, 98-106.
Cited by
Sorted by citations
A Systematic Literature Review of Quantum Computing for Routing Problems
Osaba, E., Villar-Rodríguez, E., & Oregi, I. (2022) · IEEE Access · doi:10.1109/access.2022.3177790 · Cited by 82 · see citing works
“Other interesting problem versions are also posed, such as the formulation known as Social Worker in [41] and [46], or the VRP with Balanced Pick-up in [60].”
BackgroundGPS: A New TSP Formulation for Its Generalizations Type QUBO
González-Bermejo, S., Alonso-Linaje, G., & Atchade-Adelomou, P. (2022) · Mathematics · doi:10.3390/math10030416 · Cited by 29 · see citing works
“By making a few small modifications to the original TSP, we could apply it in many fields such as SWP [21] and DNA sequencing [22, 23] among others.”
MethodQuantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works
“VQE has been applied to a QUBO formulation for the social workers problem, which explores problem specificities to avoid excessive auxiliary variables [1], and to multi-coloring graph problems [104].”
MethodAtchade-Adelomou, P., Alonso-Linaje, G., Albó-Canals, J., & Casado-Faulí, D. (2021) · Algorithms · doi:10.3390/a14070194 · Cited by 9 · see citing works
Quantum case-based reasoning (qCBR)
Atchade-Adelomou, P., Casado-Faulí, D., Golobardes-Ribé, E., & Vilasis-Cardona, X. (2022) · Artificial Intelligence Review · doi:10.1007/s10462-022-10238-w · Cited by 9 · see citing works
Fourier Series Weight in Quantum Machine Learning
Atchade-Adelomou, P. (2024) · Advances in Artificial Intelligence and Machine Learning · doi:10.54364/aaiml.2024.41108 · Cited by 3 · see citing works
Cao, D. L., & Dinh, K. (2023) · Journal of Quantum Information Science · doi:10.4236/jqis.2023.133008 · Cited by 1 · see citing works
Cao, D. L., & Dinh, K. (2023) · Journal of Quantum Information Science · doi:10.4236/jqis.2023.134008
- Authors
- Adelomou, A. P., Ribé, E. G., & Cardona, X. V.
- Venue
- Journal of Computer and Communications
- Publisher
- Scientific Research Publishing, Inc.
- Published
- 2020
- Volume
- 08
- Issue
- 11
- Pages
- 44-68
- ISSN
- 2327-5219 (ISSN-L)
- 2327-5227
- OpenAlex
- W3102494862
- Cited by
- 8
- References
- 14
- Citations by year
- 2024: 1 · 2023: 3 · 2022: 3 · 2021: 1
- FWCI
- 0.69
- Type
- journal article
- Language
- en
- Open access
- diamond
- doi.org
- Licence
- Locations
- Journal of Computer and Communications (publishedVersion, cc-by-nc)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Social Sciences › Decision Sciences › Management Science and Operations Research › Scheduling and Timetabling Solutions
- Keywords
- social workers, QUBO, QUBO formulation, combinatorial optimization, NP-hard problems, Ising model, Hamiltonian mapping, inequality constraints, variational quantum eigensolver, IBM quantum hardware
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
