CSE4500  Advanced Course in Algorithms D, 12.01.202108.04.2021
This course space end date is set to 08.04.2021 Search Courses: CSE4500
Topic outline

CSE4500 Advanced Course in Algorithms D
Spring 2021  Algebraic Algorithms: Classical and Quantum
PLEASE NOTE. All course activity takes place in the A+ system. The material will be available in A+ in the week of 4 January 2021. Course activity starts 12 January 2021.
Overview. This is an advancedlevel optional course that in spring 2021 explores algebraic algorithm designs for univariate polynomials and largeinteger arithmetic, as well as select mathematically related concepts in quantum computation, with a threefold motivation:
 The toolbox of classical nearlineartime algorithms for univariate polynomials and large integers provides a practical showcase of recurrent mathematical ideas in algorithm design such as linearity, duality, divideandconquer, 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 highdimensional quantum analogs, for example, the fast Fourier transform with the fast quantum Fourier transform.
 We gain exposure to a number of classical and more recent applications, such as secretsharing, errorcorrecting codes, as well as quantum algorithms for periodfinding and quantum search by amplitude amplification.
 Among key motivators for the ongoing push towards quantum computing are (i) Shor's polynomialtime factorization algorithm for integers, a task for which no classical polynomialtime 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 blackbox counterpart. We study both algorithm designs in a quantum circuit model of computation, which we develop from mathematicalminimalist first principles.
Prerequisites: Fundamentals of algorithm design and analysis (e.g. CSE3190). Mathematical maturity.
Teacher: Prof. Petteri Kaski.
First lecture: Tuesday 12 January, 1214, online in Zoom. (Link can be found in A+.)
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 highdimensional 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 broadranging applications from signal processing to errorcorrecting 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 nearlineartime toolbox and its select applications, with some algorithmic ideas dating back millennia, and some introduced only in the last few years.
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.
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 periodfinding algorithm (leading to fast integer factorization) as well as Grover's fast quantum search by amplitude amplification.
Lecture schedule (tentative)
Lecture 1 (Tue 12 Jan): Polynomials and integers. We start with elementary computational tasks involving polynomials, such as polynomial addition, multiplication, division (quotient and remainder), greatest common divisor, evaluation, and interpolation. We observe that polynomials admit two natural representations: coefficient representation and evaluation representation. We encounter the morethan2000yearold algorithm of Euclid for computing a greatest common divisor. We observe the connection between polynomials in coefficient representation and integers represented in the positional number system.
Lecture 2 (Tue 19 Jan): The fast Fourier transform and fast multiplication. We derive one of the most fundamental and widely deployed algorithms in all of computing, namely the fast Fourier transform and its inverse. We explore the consequences of this nearlineartimecomputable duality between the coefficient and evaluation representations of a polynomial. A key consequence is that we can multiply two polynomials in nearlineartime. We obtain an algorithm for integer multiplication by reduction to polynomial multiplication.
Lecture 3 (Tue 26 Jan): Quotient and remainder. We continue the development of the fast polynomial toolbox with nearlineartime polynomial division (quotient and remainder). The methodological protagonist for this lecture is Newton iteration. We explore Newton iteration and its convergence both in the continuous and in the discrete settings, including fast quotient and remainder over the integers.
Lecture 4 (Tue 2 Feb): Batch evaluation and interpolation. We derive nearlineartime algorithms for batch evaluation and interpolation of polynomials using recursive remaindering along a subproduct tree. In terms of methodological principles, we encounter algebraic divideandconquer, dynamic programming, and spacetime tradeoffs. As an application, we encounter secret sharing.
Lecture 5 (Tue 9 Feb): Extended Euclidean algorithm. This lecture continues our development of the nearlineartime toolbox for univariate polynomials and integers. First, we develop a divideandconquer version of the extended Euclidean algorithm for polynomials that recursively truncates the inputs to achieve nearlinear running time. Second, time permitting, we develop an analogous algorithm for computing the greatest common divisor of two given integers in nearlinear time.
Lecture 6 (Tue 16 Feb): Interpolation from erroneous data. This lecture culminates our development of the nearlineartime toolbox for univariate polynomials. We present a nearlineartime polynomial interpolation algorithm that is robust to errors in the input data up to the informationtheoretic maximum number of errors for correct recovery. As an application, we encounter ReedSolomon errorcorrecting codes together with nearlineartime encoding and decoding algorithms. Time permitting, we will look at the an analogous setting over the integers, namely Chinese remaindering with errors.
Tue 23 Feb: Exam week, no lecture.
Lecture 7 (Tue 2 Mar): Circuits, from classical to quantum. This lecture develops a basic circuit model of quantum computation by starting with classical Boolean circuits, transforming to reversiblegate Boolean circuits, and extending to quantum circuits. For the latter, we give a mathematicalminimalist review of the standard (finitedimensional) Hilbertspace model for isolated quantum systems and state evolution by unitary transformations alternating with measurement by orthogonal observables. From a computational standpoint a key observation is the massive parallelism offered by the high dimensionality of the state space compared with classical models of computation.
Tue 9 Mar: Break, no lecture.
Lecture 8 (Tue 16 Mar): The quantum Fourier transform and periodfinding. This lecture gives our first encounter with nontrivial quantum algorithms and the advantage of quantum parallelism. We encounter the quantum Fourier transform (QFT) as a higherdimensional analog of the classical DFT, study Coppersmith's quantum circuit design for a radix2 QFT and Shor's periodfinding algorithm, which we then develop by further classical considerations into an algorithm for efficiently factoring a given integer.
Lecture 9 (Tue 23 Mar): Quantum search by amplitude amplification. This lecture develops Grover's iterative amplitude amplification technique for searching a massively parallel quantum state for basisstates of interest. We observe that quantum searching can be carried out in many cases with essentially a square root of the resources which would be required by classical blackbox search.