Logo PTI Logo FedCSIS

Proceedings of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 25

Solving assignment problems via Quantum Computing: a case-study in train seating arrangement

, , , , ,

DOI: http://dx.doi.org/10.15439/2021F74

Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 217220 ()

Full text

Abstract. In recent years, researchers have oriented their studies towards Quantum Computing because it should allow the resolution of complex problems currently considered to be intractable. This work focuses on solving an assignment problems, by exploiting this novel computational approach. A case-study, denoted as the Seating Arrangement Optimization problem, is considered. It is modeled through the Quadratic Unconstrained Binary Optimization paradigm and solved through two tools made available by the D-Wave Systems company, QBSolv and a quantum-classical hybrid system. The obtained experimental results are compared in terms of solution quality and computational efficiency.

References

  1. Marchenkova A., "What’s the difference between quantum annealing and universal gate quantum computers?", https://medium.com/quantum-bits/what-s-the-difference-between-quantum-annealing-and-universal-gate-quantum-computers-c5e5099175a1
  2. Booth, M. & Reinhardt, S.P. "Partitioning Optimization Problems for Hybrid Classical / Quantum Execution", Technical Report (2017)
  3. Glover, F., Kochenberger, G. & Du, Y. "Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models." 4OR-Q J Oper Res 17, 335–371 (2019). https://doi.org/10.1007/s10288-019-00424-y
  4. S. B. Hengeveld, N. Rubiano da Silva, D. S. Gonçalves, P. H. Souto Ribeiro, A. Mucherino, Solving the One-dimensional Distance Geometry Problem by Optical Computing, arXiv e-print, https://arxiv.org/abs/2105.12118, version 1, May 2021.