1 Introduction to Quantum Computing and Quantum Algorithms (Mark Laczin)

These six videos are the cornerstone of a two-week unit we developed introducing quantum algorithms in the required UMBC core graduate course CMSC-641 Design and Analysis of Algorithms. Using the flipped classroom, students watch the videos before coming to class prepared to engage actively programming the QUIRK quantum circuit simulator and the IBM Q quantum computer using the Qiskit software development kit. We piloted the unit at UMBC in spring 2020, spring 2021, and fall 2021. Whereas there exist full courses in quantum computation or quantum algorithms, our innovation is to develop a two-week unit focused sharply on quantum algorithms targeted at computer science graduate students. The unit highlights three quantum algorithms: Deutsch-Jozsa, Simon, and Shor. To keep the unit manageable within 15 hours of work per week per student, the unit focuses sharply on background sufficient to understand the fundamentals of these three algorithms. Quantum algorithms running on quantum computers offer the potential to solve complex problems with dramatically reduced execution time and energy consumption. For example, Shor's quantum algorithm for factoring integers runs in polynomial time, faster than any known algorithm for classical computers. Shor’s algorithm offers future potential to break the widely-used RSA cryptosystem. Whereas classical computers use discrete 1's and 0's to perform calculations, quantum computers use Q-bits, which involve complex numbers and can simultaneously be 0 or 1. Based on quantum physics, quantum computers operate in a strange universe that includes the curious and potentially useful effects of superposition and entanglement. In pursuit of transformative potential advantages, government and private industry are investing significantly in quantum computer technologies. All computer science students need to know about these vital emerging technologies.