CS 583/443 Quantum Computing: Programs and Systems (2022 Fall)

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 583/443 sections) We will practice the mathematics for understanding quantum algorithms via graded problem sets consisting of derivations and proofs.
  • (Common for 583/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 583/443 sections) We will practice implementing and analyzing several quantum algorithms via three programming assignments.
  • (Specific to the 583 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 583 section; 20% for 443 section).
  • Graded problem sets. (24% for 583 section; 40% for 443 section).
  • Programming assignments; including: QAOA implementation in Google Cirq and VQE implementation in Qiskit. (24% for 583 section; 40% for 443 section).
  • Final open-ended project. (40% for 583 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. 9/6Fall Semester Begins
Wed. 9/7Introduction [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.
Mon. 9/12Postulate 1. State space [slides]1. Classical computing (over)simplified
• Functional completeness
• The physics of information
• Reversible operations
2. Postulates of quantum mechanics
3. The state of a single qubit
• Bloch sphere
Wed. 9/14Postulate 1. State space, superpositions [slides]1. The state of a single qubit
Bloch sphere
The state of multiple qubits
Tensor product
Mon. 9/19Postulate 2. Composite systems. Postulate 3. Evolution [slides]1. The state of multiple qubits
• Tensor product
2 The evolution of qubit states
Wed. 9/21Postulate 3. Evolution. Postulate 4. Measurement [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.
Mon. 9/26Basic quantum algorithms: BB84, dense coding, teleportation [slides]1. Quantum cryptography / quantum key exchange / BB84
2. Entanglement protocol: Quantum superdense coding
Wed. 9/28
Mon. 10/3Basic quantum algorithms: teleportation, Bell’s inequality [slides]1. Entanglement protocol: Quantum teleportation
2. Bell inequality testing protocol / game
Wed. 10/5Basic quantum algorithms: Bell’s inequality, 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
Mon. 10/10Basic 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. 10/12
Mon. 10/17Quantum 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. 10/19Quantum 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
Mon. 10/24
Wed. 10/26Quantum algorithms: Noisy intermediate-scale quantum (NISQ) [slides]• Density matrices and quantum noise
• Noisy intermediate scale quantum (NISQ)
Mon. 10/31Quantum 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. 11/2
Mon. 11/7
Wed. 11/9A systems view of quantum computer engineering [slides]
Mon. 11/14Languages and representations for quantum computing: Stabilizer formalism [slides]
Wed. 11/16Emerging 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
Mon. 11/21
Wed. 11/23Change in Designation of Class Day (Friday Classes)Final project interim reports due
Thu. 11/24 – Sun. 11/27Thanksgiving Recess
Mon. 11/28Quantum 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
Wed. 11/30Quantum 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
Mon. 12/5Final project presentations
Wed. 12/7Final project presentations
Mon. 12/12Final project presentations
Wed. 12/14Final project presentations
Thu. 12/15Reading DayFinal project reports due
Fri. 12/16Fall Exams Begin
Fri. 12/23Final 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

In the last few years, we have all been going through a lot, individually and together. It is important to acknowledge that events and circumstances outside of the classroom can impact our ability to be present and engaged at any given moment. At Rutgers, we are focused on the whole student. If, at any point, you experience anything impacting your performance or ability to participate in this class, please reach out to me. Please also see the academic, health, and mental wellness resources on the syllabus as well as others searchable at https://success.rutgers.edu/ for further support.


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.