Topic outline

  • CS-E4500 Advanced Course in Algorithms D

    CS-E4500 Advanced Course in Algorithms D

    Spring 2024 — Algebraic Algorithms: Classical and Quantum


    PLEASE NOTE. All course activity takes place in the A+ system. First lecture: Tuesday 9 January, 12—14, Hall T5 (CS Building).

    Overview. This is an advanced-level optional course that in spring 2024 explores algebraic algorithm designs for univariate polynomials and large-integer arithmetic, multilinear techniques, as well as select mathematically related concepts in quantum computation, with a three-fold motivation:

    1. Multilinear techniques as well as the toolbox of classical near-linear-time algorithms for univariate polynomials and large integers provide a practical showcase of recurrent mathematical ideas in algorithm design such as linearity, duality, divide-and-conquer, dynamic programming, iteration and invariants, approximation, parameterization, tradeoffs between resources and objectives, and randomization. This exposure to key classical ideas enables us to relate and compare the classical notions with their high-dimensional quantum analogs, for example, the fast Fourier transform with the fast quantum Fourier transform.
    2. We gain exposure to a number of classical and more recent applications, such as fast matrix multiplication and quantum algorithms for period-finding and quantum search by amplitude amplification.
    3. Among key motivators for the ongoing push towards quantum computing are (i) Shor's polynomial-time factorization algorithm for integers, a task for which no classical polynomial-time algorithm is known at the moment, as well as (ii) Grover's fast quantum search, which in many applications reduces the search time to essentially the square root of its classical black-box counterpart. We study both algorithm designs in a quantum circuit model of computation, which we develop from mathematical-minimalist first principles.


    Prerequisites: Fundamentals of algorithm design and analysis (e.g. CS-E3190). Mathematical maturity.

    Teacher: Prof. Petteri Kaski.

    First lecture: Tuesday 9 January, 12—14, Hall T5 (CS Building).

    Grading: Total points awarded from weekly problem sets determine the course grade. No exam.

    Learning objectives

    • Terminology and objectives of modern algorithmics, including elements of algebraic, approximation, randomised, and quantum algorithms.
    • The art of solving a large problem by reduction to one or more smaller instances of the same or a related problem.
    • (Linear) independence, dependence, and their abstractions as enablers of efficient algorithms. Computational serendipity of low tensor rank and high-dimensional quantum states.
    • Making use of duality. Often a problem has a corresponding dual problem that is obtainable from the original (the primal) problem by means of an easy transformation. The primal and dual control each other, enabling an algorithm designer to use the interplay between the two representations.
    • Relaxation and tradeoffs between objectives and resources as design tools. Instead of computing the exact optimum solution at considerable cost, often a less costly but principled approximation suffices. Instead of the complete dual, often only a randomly chosen partial dual or other relaxation suffices to arrive at a solution with high probability.


    Short synopsis of lectures

    Polynomials in one variable are among the most elementary and most useful mathematical objects, with a broad range of applications from signal processing to error-correcting codes and advanced applications such as probabilistically checkable proofs. One of the main reasons why polynomials are useful in a myriad of applications is that highly efficient algorithms are known for computing with polynomials. These lectures introduce you to this near-linear-time toolbox and its select applications. By virtue of the positional number system, algorithms for computing with polynomials are closely related to algorithms for computing with integers. In most cases, algorithms for polynomials are conceptually easier and thus form our principal object of study during our weekly lectures, with the corresponding algorithms for integers left for the exercises or for further study.

    Matrices and multilinear algorithms for computing with matrices constitute another family of algorithms with a broad range of applications. These lectures introduce you to the design of bilinear algorithms for key tasks such as matrix multiplication. We start with Strassen's 1969 breakthrough algorithm for multiplying two square matrices with subcubic complexity and via Yates's algorithm develop this into a study of asymptotic tensor rank of tensors representing a matrix multiplication map.

    A tantalizing case where the connection between polynomials and integers apparently breaks down occurs with factoring. Namely, it is known how to efficiently factor a given univariate polynomial over a finite field into its irreducible components, whereas no such classical algorithm is known at the moment for factoring a given integer into its prime factors. Indeed, the best known classical algorithms for factoring integers run in time that scales moderately exponentially in the number of digits in the input. However, integers can be factored efficiently in a quantum circuit model of computation, which presents one of the leading motivators for the push towards quantum computing. Our lectures start from classical Boolean circuits and reversible Boolean gates, extend to quantum circuits and quantum gates, observe the potential serendipity of quantum parallelism, and proceed to use it to our advantage by developing Shor's efficient period-finding algorithm (leading to fast integer factorization) as well as Grover's fast quantum search by amplitude amplification.