How to introduce techinical details of quantum computing in a theory of computation class: using the basic case of the Deutsch-Jozsa algorithm
Olga M. Kosheleva, Владик Крейнович · International Journal of Computing and Optimization · 2016
Many students taking the theory of computation class have heard about quantum computing and are curious about it. However, the usual technical description of quantum computing requires a large amount of preliminary information, too much to fit into an already packed class. In this paper, we propose a way to introduce technical details of quantum computing that does not require much time – it can be described in less than an hour. As such an introduction, we use a simplified description of the basic case of one of the pioneering algorithms of quantum computing. 1 Formulation of the Pedagogical Problem Quantum computing is very promising. It is known that quantum computing is a promising direction in computing; see, e.g., [4]. Let us just give two examples: • a quantum computing algorithm proposed by Grover enables us to search in an unsorted array of size n in time √ n [2, 3]; • a quantum computing algorithm proposed by Shor enables us to factorize large integers in polynomial time [5]. Since the difficulty of eavesdropping on RSA-encrypted messages – which underlie most current encryption schemes – relies on the difficulty of factoring large integers, this will enable us to read all encrypted messages.