Solving Assignment Problems via Quantum Computing: a Case-Study in Train Seating Arrangement

• Autorzy: Gioda Ilaria , Caputo Davide , Fadda Edoardo , Manerba Daniele , Silva Fernández Blanca , Tadei Roberto

Identyfikatory

DOI

10.15439/2021F74

• Konferencja: Federated Conference on Computer Science and Information Systems (16 ; 02-05.09.2021 ; online)
• Języki publikacji: EN

Abstrakty

EN

In recent years, researchers have oriented their studies towards new technologies based on quantum physics that should resolve complex problems currently considered to be intractable. This new research area is called Quantum Computing. What makes Quantum Computing so attractive is the particular way with which quantum technology operates and the great potential it can offer to solve real-world problems. This work focuses on solving assignment-like combinatorial optimization 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

Słowa kluczowe

EN

combinatorial mathematics; optimisation; quantum computing; search problems

PL

matematyka kombinatoryczna; optymalizacja; obliczenia kwantowe; problemy wyszukiwawcze

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2021
• Tom: Vol. 25
• Strony: 217--220
• Opis fizyczny: Bibliogr. 4 poz., wz., tab.

Twórcy

autor

Gioda Ilaria

• Department of Control and Computer Engineering, Politecnico di Torino, 10129 Torino, Italy

autor

Caputo Davide

• Data Reply s.r.l., 10126 Torino, Italy

autor

Fadda Edoardo

• Department of Control and Computer Engineering, Politecnico di Torino, 10129 Torino, Italy

autor

Manerba Daniele

• Department of Information Engineering, Università degli Studi di Brescia, 25123 Brescia, Italy

autor

Silva Fernández Blanca

• Data Reply s.r.l., 10126 Torino, Italy

autor

Tadei Roberto

• Department of Control and Computer Engineering, Politecnico di Torino, 10129 Torino, Italy

Bibliografia

• 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.

Uwagi

1. Track 1: Artificial Intelligence in Applications

2. Session: 14th International Workshop on Computational Optimization

3. Short Paper