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.