CS 558/443 Quantum Computing: Programs and Systems (2024 Spring)

Quantum Computing: Programs and Systems will be structured around reading and discussing several foundational research papers in realizing quantum computers. Students will also complete programming assignments to implement algorithms in open-source quantum frameworks. The goal of the course is to bring students up-to-speed on recent developments in realizing quantum computers, which will be a strong foundation for pursuing research or to be a subject expert in industry.

Basic course information


Instructor information

  • Yipeng Huang
  • Email: yipeng.huang@rutgers.edu
  • Students can expect a 2-day turnaround from me on emails.
  • Office hours: TBA
  • Please see Canvas site for office hour Zoom info.
  • Office: CoRE 317

Prerequisites

  • Courses in or experience in Python programming, computer architecture, algorithms, linear algebra, probability.
  • Taking first an introductory class in quantum computing such as Rutgers ECE’s Quantum Computing Algorithms (Prof. Emina Soljanin) or Rutgers Physics’s An Introduction to Quantum Computing (Prof. Steve Schnetzer) is ideal but not required.
  • Senior undergraduates interested in quantum computing have successfully taken this class in the past.

Course components

  • (Common for 558/443 sections) We will practice the mathematics for understanding quantum algorithms via graded problem sets consisting of derivations and proofs.
  • (Common for 558/443 sections) We will discuss a mix of introductory, foundational, and recent research articles on realizing quantum computing systems. Participation in reading discussions on the forum and in-class discussions will be important.
  • (Common for 558/443 sections) We will practice implementing and analyzing several quantum algorithms via three programming assignments.
  • (Specific to the 558 section) The class culminates in a final project to be completed in two or three person teams. The open-ended final project will be of students’ design. Typical projects include implementation and simulation of a quantum algorithm. The final project deliverables include a project proposal, interim report, final report, and oral presentation.

Grading rubric

  • Reading discussions. (12% for 558 section; 20% for 443 section).
  • Graded problem sets. (24% for 558 section; 40% for 443 section).
  • Programming assignments; including: QAOA implementation in Google Cirq and VQE implementation in Qiskit. (24% for 558 section; 40% for 443 section).
  • Final open-ended project. (40% for 558 section; 0% for 443 section).
  • For the reading discussions, programming assignment documentation, and project write-ups, full marks will be given for student work that demonstrate evaluation and synthesis of concepts in programming and using quantum systems. Detailed rubrics for assignments will be released before each assignment.
  • This class has no final exam.

Syllabus

DateThemeContentsReading and written assignmentsProgramming projects
Tue. 1/16Fall Semester Begins
Wed. 1/17Introduction [slides] [slides]Preview of the syllabus, course objectives & activities.Harrow. Why now is the right time to study quantum computing. XRDS. 2012.

Problem set 1 released.
Fri. 1/19Postulate 1. State space [slides]The state of a single qubit
1. Superposition
2. Bloch sphere
Wed. 1/24Postulate 2. Composition [slides]The state of multiple qubits
1. Tensor product
2. Entanglement 3. No-cloning theorem
Fri. 1/26Postulate 3. Evolution [slides]1. The state of multiple qubits
• Tensor product
2 The evolution of qubit states
Wed. 1/31Basic quantum algorithms: dense coding, teleportation [slides]1. The evolution of qubit states
• No-cloning theorem
2. The measurement of qubit states
Rieffel and Polak. An Introduction to Quantum Computing for Non-Physicists. (Up to and just short of section 6. Shor’s algorithm).

Problem set 2 released.
Fri. 2/2Basic quantum algorithms: BB84, dense coding, teleportation [slides]1. Quantum cryptography / quantum key exchange / BB84
2. Entanglement protocol: Quantum superdense coding
Wed. 2/7Basic quantum algorithms: Deutsch, Deutsch-Jozsa [slides]1. The universe does not obey local realism
• EPR paradox • CHSH game • Hardy’s paradox
2. Deutsch-Jozsa algorithm: simplest quantum algorithm showing advantage vs. classical
• Problem description
• Circuit diagram and what is in the oracle
• Demonstration of Deutsch-Jozsa for the n = 1 case
• Deutsch-Jozsa programs and systems
Fri. 2/9
Wed. 2/14
Fri. 2/16Basic quantum algorithms: Deutsch-Jozsa, Bernstein-Vazirani [slides]1. Basic quantum algorithms: Deutsch-Jozsa, Bernstein-Vazirani
• Deutsch’s algorithm: simplest quantum algorithm showing advantage vs. classical
• Problem description
• Circuit diagram and what is in the oracle
• Demonstration of Deutsch-Jozsa for the n = 1 case • Deutsch-Jozsa programs and systems
2. Deutsch-Jozsa algorithm: extending Deutsch’s algorithm to more qubits
• The state after applying oracle U
• Lemma: the Hadamard transform
• The state after the final set of Hadamards • Probability of measuring upper register to get 0
Wed. 2/21
Fri. 2/23Quantum algorithms: Shor’s integer factoring classical part [slides]1. The factoring problem
2. Shor’s algorithm classical part: converting factoring to period finding
• Factoring to modular square root
• Modular square root to discrete logarithm
• Discrete logarithm to order finding
• Order finding to period finding
2. Shor’s algorithm quantum part: period finding using quantum Fourier transform
• Calculate modular exponentiation
• Measurement of target (bottom, ancillary) qubit register
Wed. 2/28Quantum algorithms: Shor’s integer factoring quantum
part [slides]
Shor’s algorithm quantum part: period finding using quantum Fourier transform
1. Calculate modular exponentiation
2. Measurement of target (bottom, ancillary) qubit register
3. Quantum Fourier transform to obtain period
4. How to construct the Quantum Fourier transform
5. Evaluation of Shor’s as a fault-tolerant quantum algorithm
Fri. 3/1
Wed. 3/6Quantum algorithms: Noisy intermediate-scale quantum (NISQ) [slides]• Density matrices and quantum noise
• Noisy intermediate scale quantum (NISQ)
Fri. 3/8Quantum algorithms: Quantum approximate optimization algorithm [slides]1. NISQ (Noisy Intermediate Scale Quantum) vs FTQC (Fault Tolerant Quantum Computation)
• NISQ algorithms: attributes, examples
2. Quantum Approximate Optimization Algorithm for MAX-CUT
• The MAX-CUT problem
• Encoding the vertices
Wed. 3/13Spring Recess
Fri. 3/15Spring Recess
Wed. 3/20A systems view of quantum computer engineering [slides]
Fri. 3/22Languages and representations for quantum computing: Stabilizer formalism [slides]
Wed. 3/27Emerging languages and representations for quantum computing: Tensor networks [slides]

Tensor Network Simplification [slides]
1. Tensor networks
• Tensors
• Tensor networks
• Tensor network contraction
• Tensor network contraction order
2. Unification of stabilizers and tensors
• Example: inverting a CNOT
• Splitting a CNOT into network of two rank-3 tensors
• Tensor simplification rules
• Automatic simplification of circuits
Fri. 3/29
Wed. 4/3Change in Designation of Class Day (Friday Classes)Final project interim reports due
Fri. 4/5
Wed. 4/10Quantum Chemistry [slides]1. Motivation for quantum chemistry
2. Ground state estimation
3. Simplification of problem representation
4. Qubit representation of orbitals
5. Variational quantum eigensolver
6. VQE ansatz
Fri. 4/12Quantum architecture [slides]
Quantum microarchitecture [slides]
• Challenges of quantum computer architecture
1. Scheduling
2. Qubit mapping
3. Topological constraints resolving
4. Physical-gate decomposition
5. Physical-level optimization

• Anatomy of a quantum computer
1. Essential hardware components of a quantum computer 2. DiVincenzo’s criteria

• Device technologies
1. Trapped ion quantum computers 2. Superconducting quantum computers
3. Other technologies
Wed. 4/17Final project presentations
Fri. 4/19Final project presentations
Wed. 4/24Final project presentations
Fri. 4/26Final project presentations
Tue. 4/30Reading Day
Wed. 5/1Reading Day
Thu. 5/2Fall Exams BeginFinal project reports due
Wed. 5/8Final Exams End

Rutgers CS diversity and inclusion statement

Rutgers Computer Science Department is committed to creating a consciously anti-racist, inclusive community that welcomes diversity in various dimensions (e.g., race, national origin, gender, sexuality, disability status, class, or religious beliefs). We will not tolerate micro-aggressions and discrimination that creates a hostile atmosphere in the class and/or threatens the well-being of our students. We will continuously strive to create a safe learning environment that allows for the open exchange of ideas and cherished freedom of speech, while also ensuring equitable opportunities and respect for all of us. Our goal is to maintain an environment where students, staff, and faculty can contribute without the fear of ridicule or intolerant or offensive language. If you witness or experience racism, discrimination micro-aggressions, or other offensive behavior, you are encouraged to bring it to the attention to the undergraduate program director and/or the department chair. You can also report it to the Bias Incident Reporting System http://inclusion.rutgers.edu/report-bias-incident/


Resources

Academic integrity


Counseling, ADAP & Psychiatric Services (CAPS)


Violence Prevention & Victim Assistance (VPVA)

  • (848) 932-1181
  • 3 Bartlett Street, New Brunswick, NJ 08901
  • www.vpva.rutgers.edu/
  • The Office for Violence Prevention and Victim Assistance provides confidential crisis intervention, counseling and advocacy for victims of sexual and relationship violence and stalking to students, staff and faculty.  To reach staff during office hours when the university is open or to reach an advocate after hours, call 848-932-1181.

Disability services

  • (848) 445-6800
  • Lucy Stone Hall, Suite A145, Livingston Campus, 54 Joyce Kilmer Avenue, Piscataway, NJ 08854
  • https://ods.rutgers.edu/
  • Rutgers University welcomes students with disabilities into all of the University’s educational programs. In order to receive consideration for reasonable accommodations, a student with a disability must contact the appropriate disability services office at the campus where you are officially enrolled, participate in an intake interview, and provide documentation: https://ods.rutgers.edu/students/documentation-guidelines. If the documentation supports your request for reasonable accommodations, your campus’s disability services office will provide you with a Letter of Accommodations. Please share this letter with your instructors and discuss the accommodations with them as early in your courses as possible. To begin this process, please complete the Registration form on the ODS web site at: https://ods.rutgers.edu/students/registration-form.