Scheduling has always been deemed as a perfunctory task for most organizations. It could nevertheless become an extremely arduous task if involves the management of events and of the dynamic variables that control it. Herein, we present an idea/solution to the Travelling Tournament Problem (TTP), which is a unique combinatorial problem tackling both feasibility and optimality of the solution. As the TTP belongs to the category of NP-Hard problems, generating solutions usually tend to be extremely costly, with most of the solutions having a time complexity of as high as O(n!). However, two of the many burgeoning fields, artificial intelligence and quantum computing are making headway and we believe that quantum computers possess enough potential to be competent enough to solve such scheduling problems. The aforementioned technologies have provided us with an excellent framework, which we have consequently adopted in our implementation. In the following paper, we portray a hybrid solution that utilizes the immense computational power of a quantum computer while also tweaking the classical algorithm to dynamically reduce the number of iterations and subsequently the cost. We draw parallels between the Travelling Salesman Problem (TSP) and the TTP by utilizing the insights obtained from a detailed analysis of the existing Simulated Annealing based approach, and thus propose certain unique modifications to the best known classical only solutions.

Quantum Computing, NP-Hard Problem, Travelling Tournament Problem, Simulated annealing

[1] C. Fernandes, D. Lobo, S. Gawane and K. Wagaskar, "Proposed Quantum AI solution for the Travelling Tournament Problem," International Conference for Emerging Technology (INCET), Belgaum, India, pp. 1-5, 2020.
[2] Leong, G, "Constraint programming for the traveling tournament problem.", Project Thesis, National University of Singapore, 2003.
[3] Hamiez, J.P. and Hao, J.K., “A linear-time algorithm to solve the Sports League Scheduling Problem (prob026 of CSPLib)”, Discrete Applied Mathematics, 143(1-3), pp.252-265, 2004.
[4] Thakare, L., Umale, J., Thakare, B., & Maxwel, J. C. , "Solution to Traveling Tournament Problem using Genetic Algorithm on Hadoop." , International Conference on Emerging trends in Electrical, Electronics and Communication Technologies-ICECIT, vol. 2, pp. 68-73, 2012.
[5] Rutjanisarakul, T. and Jiarasuksakun, T., “A Sport Tournament Scheduling by Genetic Algorithm with Swapping Method”, arXiv preprint arXiv:1704.04879, 2017.
[6] Goerigk, M., Hoshino, R., Kawarabayashi, K.I. and Westphal, S., 2014, June. Solving the travelling tournament problem by packing three-vertex paths. In Twenty-Eighth AAAI Conference on Artificial Intelligence.
[7] Anagnostopoulos, A., Michel, L., Van Hentenryck, P. and Vergados, Y., “A simulated annealing approach to the traveling tournament problem” , Journal of Scheduling, 9(2), pp.177-193, 2006
[8] Kwiat, P.G., Mitchell, J.R., Schwindt, P.D.D. and White, A.G., “Grover`s search algorithm: an optical approach”, Journal of Modern Optics, 47(2-3), pp.257-266, 2000
[9] Wiebe, N., Kapoor, A. and Svore, K., “Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning”, arXiv preprint arXiv:1401.2142, 2014.
[10] E. Padmalatha, S. Sailekya, "A Review on Quantum Computers and Machine Learning", International Journal of Computer Sciences and Engineering, Vol.6, Issue.3, pp.396-399, 2018.
[11] Megha Roy, Soumen Santra, Sarasij Majumdar, "Quantum Computers", International Journal of Computer Sciences and Engineering, Vol.07, Special Issue.01, pp.57-62, 2019.
[12] Cross, A. , “The IBM Q experience and QISKit open-source quantum computing software”, APS Meeting Abstracts, vol. 2018, pp. L58-003, 2018
[13] Gilliam, A., Venci, C., Muralidharan, S., Dorum, V., May, E., Narasimhan, R. and Gonciulea, “"Foundational patterns for efficient quantum computing”, arXiv preprint arXiv:1907.11513, 2019.
[14] Easton, K. Nemhauser, G. and Trick, M.,“The travelling tournament problem description and benchmarks”, International Conference on Principles and Practice of Constraint Programming, pp. 580-584, 2001
[15] Goerigk, M., Hoshino, R., Kawarabayashi, K.I. and Westphal, S., “Solving the travelling tournament problem by packing three-vertex paths”, Twenty-Eighth AAAI Conference on Artificial Intelligence, Vol. 28. No. 1, 2014.
[16] Nannicini, G., “Performance of hybrid quantum-classical variational heuristics for combinatorial optimization”, Physical Review E, 99(1), p.013304, 2019.
[17] Miceli, R. and McGuigan, M., ”Quantum computation and visualization of hamiltonians using discrete quantum mechanics and ibm qiskit”, 2018 New York Scientific Data Summit (NYSDS), pp. 1-6. IEEE, 2018.
[18] Barabasi, I., Tappert, C.C., Evans, D. and Leider, A.M., “Quantum Computing and Deep Learning Working Together to Solve Optimization Problems”, 2019 International Conference on Computational Science and Computational Intelligence (CSCI) (pp. 493-498). IEEE, 2019.
[19] Draper, T.G., “Addition on a quantum computer”, arXiv preprint quant-ph/0008033, 2000.
[20] Ruiz-Perez, L. and Garcia-Escartin, J.C., "Quantum arithmetic with the quantum Fourier transform." , Quantum Information Processing, 16(6), p.152, 2017
[21] Koch, D., Wessing, L. and Alsing, P.M., “Introduction to Coding Quantum Algorithms: A Tutorial Series Using Qiskit”, arXiv preprint arXiv:1903.04359, 2019.
[22] Weinstein, Y.S., Pravia, M.A., Fortunato, E.M., Lloyd, S. and Cory, D.G., “Implementation of the quantum Fourier transform”, Physical review letters, 86(9), p.1889, 2001.