Quantum Computing: A New Era of Computing

Authors: Jyoti Chaturvedi Gursaran

Abstract:

Nature conducts its action in a very private manner. To reveal these actions classical science has done a great effort. But classical science can experiment only with the things that can be seen with eyes. Beyond the scope of classical science quantum science works very well. It is based on some postulates like qubit, superposition of two states, entanglement, measurement and evolution of states that are briefly described in the present paper. One of the applications of quantum computing i.e. implementation of a novel quantum evolutionary algorithm(QEA) to automate the time tabling problem of Dayalbagh Educational Institute (Deemed University) is also presented in this paper. Making a good timetable is a scheduling problem. It is NP-hard, multi-constrained, complex and a combinatorial optimization problem. The solution of this problem cannot be obtained in polynomial time. The QEA uses genetic operators on the Q-bit as well as updating operator of quantum gate which is introduced as a variation operator to converge toward better solutions.

Keywords: Quantum computing, qubit, superposition, entanglement, measurement of states, evolution of states, Scheduling problem, hard and soft constraints, evolutionary algorithm, quantum evolutionary algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1087386

References:

[1] Nilesh Gambhava and Gopi Sanghani, "University Examination Timetabling using Genetic Algorithm", in proc International Conference on Applied Artificial Intelligence ICAAI '03„ Kolhapur, INDIA, Monday, 15th December 2003.
[2] Yu Zheng , Jing-fa Liu ,Wue-hua Geng and Jing-yu Yang , "Quantum-Inspired Genetic Evolutionary Algorithm for Course Timetabling", in Proc of 3rd International Conference on Genetic and Evolutionary Computing, 2009. WGEC '09, pp 750 – 753, 14-17 Oct. 2009
[3] Liviu Lalescu and Costin Badica, "An Evolutionary Approach for School Timetabling", in Proc. 14th International Conference on Control Systems and Computer Science, vol. II, pp 114, July 2-5, 2003.
[4] E.K. Burke, J. Kingston and K. Jackson, "Automated university timetabling: the state of the art", The Computer Journal, Vol. 40, No. 9, pp. 565-571, 1997
[5] Kuk-Hyun Han and Jong-Hwan Kim , "On the Analysis of the Quantum-inspired Evolutionary Algorithm with a Single Individual", in Proceedings of the 2001 International Conference on Artificial Intelligence, July 16-21, 2006.
[6] Kuldeep Kumar, Sikander, Ramesh Sharma AND Kaushal Mehta, " Genetic Algorithm Approach to Automate University Timetable", International Journal of Technical Research(Iftr), Vol. 1, Issue 1,PP. 33¬37, Mar-Apr2012.
[7] Ho Sung C. Lee, "Timetabling Constrained System via Genetic Algorithm", Masters Thesis. University of Philippines, Diliman, Quezon City, 2000.
[8] Liviu Lalescu and Costin Badica, "Timetabling Experiments Using Genetic Algorithms ", University of Craiova, Faculty of Control, Computers and Electronics Software Engineering Department, Romania, July 2003.
[9] Branimir Sigl, Marin Golub, Vedran Momar, "Solving Timetable Scheduling Problem by Using Genetic Algorithms", in proc. of 25th Int. Conf Information Technology Interfaces IT1, Cavtat, Croatia, pp. 519¬524, June 2003.
[10] C. Y. Cheong, K. C. Tan and B. Veeravalli, "Solving the Exam Timetabling Problem via a Multi-Objective Evolutionary Algorithm – a more general approach", in Proceedings of the IEEE Symposium on Computational Intelligence in Scheduling, CI-Sched, Honolulu, HI, USA, pp. 165 –172, 2007.
[11] M. Al-Betar, A. Khader and T. Gani, "A Harmony Search Algorithm for University Course Timetabling ", in proc. of 7th Intl. Conf on the Practice and Theory of Automated Timetabling.MoNTREAL, CANADA, Aug. 2008.
[12] Kuldeep Singh Sandhu, " Automating Class Schedule Generation in the Context of a University Timetabling Information System", Ph.D. Dissertation, Nathan Campus, Griffith University., 21st September 2001.
[13] Kuk-Hyun Han and Jong-Hwan Kim, "Quantum-inspired Evolutionary Algorithm for a Class of Combinatorial Optimization", IEEE transaction on Evolutionary Computation, Vol. 6, No. 6, December 2002.
[14] Mark Oskin, Lecture Notes for Quantum Computing , Department of Computer Science and Engineering, University of Washington, Washington.
[15] U.V. Vazirani, lecture notes on Qubits, Quantum Mechanics, and Computers for Chem/CS/Phys191, University of California, Berkeley, 2012.
[16] Vishal Sahni, Quantum Computing. New Delhi: TATA McGRAW –HILL Publishing Company LTD., 2007.
[17] Ajoy Ghatak and S. Lokanathan, Quantum Mechanics Theory and Application. New Delhi: MACMILAN INDIA LTD., 2004.