Implementations of Quantum Algorithms: A Pedagogical Bridge from Theory to Practice

Abstract

Quantum algorithms promise significant speedups over their classical counterparts, but the gap between theoretical results and practical implementation remains a barrier for students and researchers entering the field. This thesis addresses that gap through hands-on implementation of quantum algorithms and protocols in Qiskit, with an emphasis on the unexpected challenges that arise when translating theory into working code. A core technical contribution is the extension of Qiskit's oracle classes to accept bitstring representations of Boolean functions, augmenting the existing Boolean formula-based interface with a more flexible input method. These extended oracles are used to implement the Deutsch-Jozsa, Bernstein-Vazirani, and Simon's algorithms, each verified through statevector analysis. An interactive BB84 quantum key distribution simulation is also presented, with configurable eavesdropper behavior demonstrating how interception introduces detectable errors. We implement the asymptotically optimal quantum collision algorithm and three approaches to element distinctness: a classical random walk and a naive Grover-based search, both with linear query complexity, and Ambainis's asymptotically optimal sublinear quantum walk algorithm. These implementations surface practical challenges absent from theoretical presentations, including the junk-state problem arising from non-power-of-two search spaces and the combinatorial blowup in oracle construction that makes classical simulation of the quantum walk infeasible beyond small inputs. Finally, the collision algorithm is applied to detecting revisited cells in a robot's grid trajectory, demonstrating how abstract query complexity results connect to concrete applications. All implementations include interactive interfaces allowing users to vary algorithm parameters and observe their effects on correctness, query complexity, and success probability.