Introducton to Quantum Algorithms

ECE 592-100 (also ECE 492-054, CSC 495-054, and CSC 591-054)

Spring 2025

Instructor: Dror Baron, e-mail: barondror AT ncsu DOT edu.
Class:Monday and Wednesday, 11:45-13:00, EB2 1229.
Office hours: Wednesdays, 14:00-15:00, via Zoom.

Useful Links

• Moodle.
• Panopto videos of class.
• Triangle Quantum Computing Seminar.
• QIP 2025 21 March.
• Tentative schedule.
• Syllabus.
• Course materials for ECE 421 (signal processing), ECE 514 (probability and random processes), ECE 512 (data science).

About this Course

Prerequisites

This course provides an introduction to quantum algorithms primarily through inner product space and signal processing perspectives. As such, it will be advantageous for students to be familiar with linear algebra (e.g., Math 305 or 405), linear systems (ECE 301) and signal processing (e.g., ECE 410), and basics of quantum computing, specifically quantum gates. Because most students lack at least part of this background, we will review these materials during the first half of the course. It will also be helpful for students to be familiar with probability and statistics (e.g., ST 371 or ECE 514). Some programming proficiency, for example in Matlab or Python, could be helpful. For your convenience, here are links to course materials for ECE 421 and ECE 514.

Topics

Below is a list of topics that will be covered. Having said that, as a somewhat new course, we may veer away from our planned route as the semester progresses.

• Motivation and Introduction.
• Mathematical basics: complex numbers, Taylor series, linear algebra.
• Signal processing basics: discrete time signals and systems, discrete time Fourier transforms, frequency interpretation of linear time invariant systems.
• Quantum computing basics: state spaces, quantum evolution, measurement, qubits, single qubit gates, multi-qubit gates, entanglement. Deutsch's algorithm.
• Hadamard transform: finding XOR function patterns, Deutsch-Jozsa algorithm, Bernstein-Vazirani algorithm.
• Grover's quantum search algorithm.
• Quantum Fourier transforms: Fast Fourier transform (classical) and quantum Fourier transform, quantum phase estimation, classical spectral estimation, noisy spectral estimation.

Course Materials

Textbook

The instructor will be trying to provide his interpretation to some topics in the quantum literature, while coming from his (classical) signal processing perspective. Here are some references that may be useful.

• Nielsen and Chuang, Quantum Computing and Quantum Information, 2000.
• Proakis and Manolakis, Digital Signal Processing - Principles, Algorithms, and Applications, 1992 or later editions.

Programming

It is not clear whether we will have programming assignments as part of our course. In any event, for your convenience, I am including resources for Matlab and Python.

• NC State students can download Matlab here.
• Matlab tutorial.
• Python tutorial.

It is possible that some students workin on projects will want to use the quantum programming language Qiskit.

Slides and Modules

• The grand scheme of ECE 421 (undergraduate signal processing) helps offer some perspective.
• Slides for introduction segment of course (Chapter 1 in notes).
• Slides for math segment of course (Chapter 2 in notes, and Notes 2-3).
• Slides for Chapters 1-2 in Proakis & Manolakis. (Introduction to signal processing; discrete time signals and systems.)
• Slides for Chapters 4-5 (old slides) in Proakis & Manolakis. (Fourier transforms; LTI systems in frequency domain.)
• Slides for Chapters 7-8 (old slides) in Proakis & Manolakis. (Discrete Fourier transforms; fast Fourier transform.)
• Slides for the CHSH game by Ryan O'Donnell. More information about his 2018 quantum course is available here.
• Slides for complexity classes.

Assignments and Grading

Grading

For graduate students, the following grade structure will be used.

Component	% of Grade	Due Date
Homework:	40%	Throughout course
Mini Project:	10%	Due last week end of course
Quizzes:	30%	3 quizzes, dates and details in course calendar
Final Exam:	20%	April 30, 12-2:30
Extra credit:	Up to 3%

For undergraduate students, there is no need to submit the mini project. However, undergraduate students are welcome to submit projects, in which case the project grade will be assigned up to 3% extra credit. (For example, an undergraduate with a 90% grade on the project will receive 2.7% extra credit.) Note that the total extra credit will still be capped at 3%, including a possible contribution from the mini project.

Component	% of Grade	Due Date
Homework:	50%	Throughout course
Quizzes:	30%	3 quizzes, dates and details in course calendar
Final Exam:	20%	April 30, 12-2:30
Extra credit:	Up to 3%

Homework

We expect homeworks (HWs) roughly every 1-2 weeks. Submission should be in class electronically on Moodle up to midnight on the day that it is due.

• HW1 is due on Jan. 15.
• HW2 is due on Jan. 22.
• HW3 is due on Jan. 29.
• HW4 is due on Feb. 5.
• HW5 is due on Feb. 21.
• HW6 is now due on Feb. 28.
• HW7 is due on Mar. 5.
• HW8 is due on March 19.
• HW9 is due on March 26.
• HW10 is now due on April 4.
• HW11 is due on April 9.
• HW12 is due on April 16.

Mini Project

The project will involve a topic that a student chooses to work on. This could involve reading a paper and presenting it to the class, implementing some quantum algorithm, or even (ideally, hopefully) presenting new results that you worked on. More details about the project will be provided during the semester.

• Projects will be required from graduate students and optional for undergraduates.
• Projects will be presented in class.
• A reasonable report would be 2-3 pages, including possible figures and references.
• Presentations will be peer graded. Make sure to attend classes toward the end of the semester (per the course schedule) in order to peer grade the presentations.
• The project proposal (due March 17) should specify the name(s) of student(s) involved (2 students should be fine, please check with me), the topic for the project, and why you're enthusiastic about that topic. The project proposal can be brief; a third of a page seems reasonable.

Past tests

• 2023 Quiz 1 and its solution.
• 2023 Quiz 2 and its solution.
• 2023 Final exam and its solution.
• 2024 Quiz 1 and its solution.
• 2024 Quiz 2 and its solution.
• 2024 Quiz 3 and its solution.
• 2024 Final exam and its solution.
• 2025 Quiz 1 and its solution.
• 2025 Quiz 2 and its solution.
• 2025 Quiz 3 and its solution.
• 2025 Final Exam and its solution.

Feedback

Students are encouraged to send feedback to Prof. Baron, barondror dot {gmail dot com, ncsu dot edu}.