Introduction

Quantum algorithms offer provable advantages over classical algorithms in the query model of computation. But what about a more standard model of computation, where problem inputs are given explicitly rather than in the form of an oracle or black box? This turns out to be a much more difficult question to answer, and to address it we must first establish a solid foundation on which to base our investigation. This is the primary purpose of this lesson.

We'll begin by discussing computational cost, for both classical and quantum computations, and how it can be measured. This is a general notion that can be applied to a wide range of computational problems — but to keep things simple we'll mainly examine it through the lens of computational number theory, which addresses computational tasks that are likely to be familiar to most readers, including basic arithmetic, computing greatest common divisors, and integer factorization. While computational number theory is a narrow application domain, these problems serve well to illustrate the basic issues (and they also happen to be highly relevant to the lesson following this one).

Our focus is on algorithms, as opposed to the ever-improving hardware on which they're run. Correspondingly, we'll be more concerned with how the cost of running an algorithm scales as the specific problem instances it's run on grow in size, rather than how many seconds, minutes, or hours some particular computation requires. We focus on this aspect of computational cost in recognition of the fact that algorithms have fundamental importance, and will naturally be deployed against larger and larger problem instances using faster and more reliable hardware as technology develops.

Finally, we'll turn to a critically important task, which is running classical computations on quantum computers. The reason this task is important is not because we hope to replace classical computers with quantum computers — which seems extremely unlikely to happen any time soon, if ever — but rather because it opens up many interesting possibilities for quantum algorithms. Specifically, classical computations running on quantum computers become available as subroutines, effectively leveraging decades of research and development on classical algorithms in pursuit of quantum computational advantages.

Lesson video

In the following video, John Watrous steps you through the content in this lesson on quantum algorithmic foundations. Alternatively, you can open the YouTube video for this lesson in a separate window. Download the slides for this lesson.