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.
Announcements
- 2 January 2025:
Course webpage is online.
- 4 January 2025:
Moodle;
Panopto
videos of class;
tentative schedule; and
syllabus.
- 9 January 2025:
Homework1 (HW1)
is due on January 15; and slides for the
introduction
segment of the course.
- 13 January 2025:
HW2
is due on January 22; and slides for the
introduction (updated) and
math (new)
segments of the course.
- 16 January 2025:
updated slides for the
math
segment of the course; and course notes for the class on
1.15.2025 are on Moodle (called Notes2).
- 22 January 2025:
updated slides for the
math
segment of the course;
course notes for the class on 1.22.2025 are on Moodle (Notes3);
HW3 is due on Jan. 29; and an
updated schedule.
- 27 January 2025:
updated slides for the
math
segment of the course;
and course notes for the class on 1.27.2025 are on Moodle (Notes4).
- 29 January 2025:
last update (hopefully) for
math slides;
course notes for today's class are on Moodle (Notes5); and
HW4 is due on Feb. 5.
- 3 February 2025:
last update (hopefully) for
math slides;
course notes for today's class are on Moodle (Notes6).
- 5 February 2025:
course notes for today's class are on Moodle (Notes7).
- 8 February 2025:
2025 Quiz 1 and its
solution.
- 11 February 2025:
course notes for yesterday's class (Proakis Manolakis Ch4) are on Moodle (Notes8).
- 13 February 2025:
course notes for yesterday's class (Proakis Manolakis Ch5) are on Moodle (Notes9); an
updated schedule; and
HW5 is due on Feb. 21.
- 17 February 2025:
course notes for Proakis Manolakis Ch7-8 are on Moodle (Notes10).
- 19 February 2025:
course notes for today's class are on Moodle (Notes11); an
updated schedule; and
HW6 is due on Feb. 26.
- 24 February 2025:
course notes for today's class are on Moodle (Notes12).
- 26 February 2025:
HW7 is due on Mar. 5.
- 2 March 2025:
2025 Quiz 2 and its
solution.
- 4 March 2025:
course notes for yesterday's class are on Moodle (Notes13).
- 6 March 2025:
Project proposals are due on March 17; and
HW8 is due on Mar. 19.
- 17 March 2025:
course notes for today's class are on Moodle (Notes14);
slides for the
CHSH ga
by Ryan O'Donnell; and more information about his 2018 quantum course is available
here.
- 20 March 2025:
course notes for yesterday's class are on Moodle (Notes15); and
HW9 is due on Mar. 26.
- 21 March 2025:
2025 Quiz 3 and its
solution.
- 25 March 2025:
course notes for yesterday's class are on Moodle (Notes16).
- 26 March 2025:
course notes for today's class are on Moodle (Notes17).
- 27 March 2025:
HW10 is due on April 2; and
updated schedule.
- 31 March 2025:
course notes for today's class are on Moodle (Notes18).
- 2 April 2025:
HW10 is now due on April 4; and
HW11 is due on April 9.
- 10 April 2025:
course notes for this week's classed are on Moodle (Notes19 and Notes20);
and HW12 is due on April 16.
- 14 April 2025:
course notes for today's class are on Moodle (Notes21).
- 1 May 2025:
2025 Final Exam and its
solution.
Useful Links
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.
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
Feedback
Students are encouraged to send feedback to Prof. Baron,
barondror dot {gmail dot com, ncsu dot edu}.