Leveraging the Bernstein-Vazirani Algorithm for Intuitive Quantum Computing Education

The Deutsch algorithm has been the algorithm of choice for those seeking to educate the public and undergraduate students about quantum computing. For a single, self-contained introductory lecture, it has no equal. However, while the algorithm itself was a ground-breaking achievement and a valuable teaching tool, its results can seem abstract and unsatisfying to students. We argue that the Bernstein-Vazirani algorithm can pick up where the Deutsch algorithm left off. That is, it is an algorithm that might be mathematically more complex, but is likely to be seen as more intuitive; as well as a more satisfying demonstration of the superiority of quantum computing. Furthermore, in the context of a full undergraduate course, the Bernstein-Vazirani algorithm can be broken down into a series of programming assignments, each of which will force the student to confront fundamental concepts of quantum mechanics and quantum computing. We present a detailed summary of the Bernstein-Vazirani algorithm and compare its complexity to the classical analog.