CS 583 Quantum Computing: Programs and Systems (2021 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: Wednesdays at 3pm via Zoom
  • 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

  • We will discuss a mix of introductory, foundational, and recent research articles on realizing quantum computing systems.
  • For a handful of the most contentious topics in quantum computing, we will have debates via student presentations representing various viewpoints in the latest research.
  • Participation in reading discussions on the forum, oral presentations, and completion of the short programming assignments will be important.

Grading rubric

  • 50% programming assignments; including: QAOA implementation in Google Cirq and VQE implementation in Qiskit.
  • 50% student presentation of reading assignments.
  • For both programming assignments and presentations, 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.

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/


Tentative syllabus

DateThemeTopicReading assignment
Wed. 9/1Fall Semester Begins
Wed. 9/1Introduction [slides]Preview of the syllabus, course objectives & activities.“Quantum Computing in the NISQ era and beyond” by Preskill
Wed. 9/8 (Monday classes)QC fundamentals: one qubit [slides]1. Universal classical computing
2. A single qubit: the Hadamard gate, superposition, interference, measurement
3. Multiple qubits: the tensor product
Mon. 9/13QC fundamentals: multiple qubits [slides]• Measurement
• Tensor products of state vectors and unitary matrices
• Deutsch-Jozsa algorithm
Wed. 9/15QC fundamentals: Deutsch-Jozsa programs and systems [slides]• Problem description
• Circuit diagram and what is in the oracle
• Demonstration of Deutsch-Jozsa for the n = 1 case
• Deutsch-Jozsa programs and systems
“Quantum computing 40 years later” by John Preskill

“The Limits of Quantum Computers” by Scott Aaronson

“Recent progress in quantum algorithms” by Bacon and van Dam
Mon. 9/20Quantum computing fundamentals: Deutsch-Jozsa programs and systems [slides]

Programming frameworks 1: Cirq [slides]
1. The Deutch-Jozsa algorithm circuit
2. The state after the first set of Hadamards
3. The state after applying oracle U
4. Lemma: the Hadamard transform
5. The state after the final set of Hadamards
6. Probability of measuring upper register to get 0
7. A demonstration in Google Cirq
“Quantum Computer Systems for Scientific Discovery” report from 2019 NSF workshop on Quantum Computing

Optional:

“Challenges and Opportunities of Near-Term Quantum Computing Systems” by Corcoles et al.

“Quantum Computer Architecture: Towards Full-Stack Quantum Accelerators” by Bertels et al.
Wed. 9/22Quantum computing fundamentals: entanglement [slides]1. Orthogonal measurement bases
2. Entangled states: Bell states
3. Superdense coding
4. Quantum teleportation
“A Quantum Approximate Optimization Algorithm” by Farhi, Goldstone, and Gutmann

Optional:

“Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor” by Google AI Quantum and Collaborators
Mon. 9/27Quantum computing fundamentals: teleportation and dense coding [slides]1. Entangled states: Bell states
2. Quantum teleportation
3. Superdense coding 4. Channel capacity of dense coding
5. Dense coding with multipartite qubit entanglement
https://cirq.readthedocs.io/en/master/tutorials/QAOA_Demo.html

Optional:

“TensorFlow Quantum: A Software Framework for Quantum Machine Learning” by Broughton et al.
Wed. 9/29Quantum computing fundamentals: dense coding, Bell’s inequality [slides]1. The lens we take when studying quantum computing
2. Dense coding with multipartite qubit entanglement
3. Dense coding with high-dimensional qudit entanglement
Mon. 10/4Quantum computing fundamentals: Hardy’s paradox / CHSH / Bell’s inequality [slides]1. Quantum computing fundamentals: Hardy’s paradox / CHSH / Bell’s inequality
2. Dense coding with high-dimensional qudit entanglement
3. The lens we take when studying quantum computing Bell inequality testing protocol / game
Lab 1 released.

“Programming languages and compiler design for realistic quantum hardware” by Chong, Franklin, and Martonosi

Optional:

“Quantum Circuits for Dynamic Runtime Assertions in Quantum Computation” by Liu, Byrd, and Zhou

“Formal Verification vs. Quantum Uncertainty” by Rand, Hietala, and Hicks
Wed. 10/6Shor’s factoring algorithm: the classical part [slides]1. The factoring problem
2. The classical part: converting factoring to order finding / period finding
Mon. 10/11Shor’s factoring algorithm: the quantum part [slides]The 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
“Quantum Tensor Networks in a Nutshell” by Biamonte and Bergholm

Optional:

“Lectures on Quantum Tensor Networks: a pathway to modern diagrammatic reasoning” by Biamonte

“The Heisenberg Representation of Quantum Computers” by Gottesman
Wed. 10/13Shor’s factoring algorithm: quantum Fourier transform [slides]The quantum part: period finding using quantum Fourier transform
1. Measurement of target (bottom, ancillary) qubit register 2. Quantum Fourier transform to obtain period
Mon. 10/18Wrapping up Shor’s and QFT; Quantum Approximate Optimization Algorithm [slides]QAOA for MAX-CUT: general strategy
1. Each node in n nodes of the MAX-CUT graph corresponds to one of n qubits in the quantum circuit.
2. The state vector across the qubits |ψ⟩ encodes a node partitioning σ ∈ {−1, +1}^n.
3. Put the initial state vector |ψs⟩ in a superposition of all possible node
partitionings.
“Quantum supremacy using a programmable superconducting processor” by Arute et al.

Optional:

“Characterizing Quantum Supremacy in Near-Term Devices” by Boixo et al.
Wed. 10/20Quantum Approximate Optimization Algorithm [slides]NISQ (Noisy Intermediate Scale Quantum) vs FTQC (Fault Tolerant Quantum Computation)
• NISQ algorithms: attributes, examples

Quantum Approximate Optimization Algorithm for MAX-CUT
1. The MAX-CUT problem
2. Encoding the vertices
3. Encoding the edges
4. A simulated annealing schedule
Mon. 10/25Understanding claims and counterclaims for quantum advantageIn-class team debate: team quantum prototype vs. team classical simulation (initial arguments)“Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits” by Pednault et al.

Optional:

“Validating quantum computers using randomized model circuits” by Cross et al.
Wed. 10/27Understanding claims and counterclaims for quantum advantageIn-class team debate: team quantum prototype vs. team classical simulation (rebuttals)
Mon. 11/1Understanding claims and counterclaims for quantum advantage [slides]“Quantum Chemistry in the Age of Quantum Computing” by Cao et al.

Optional:

“Towards quantum chemistry on a quantum computer” by Lanyon et al.

“A variational eigenvalue solver on a photonic quantum processor” by Peruzzo at al.

“Hartree-Fock on a superconducting qubit quantum computer” by Arute et al.
Wed. 11/3NISQ algorithms 2: VQE
Mon. 11/8NISQ algorithms 2: VQE [slides]1. The Schrodinger equation.
2. Computing ground state energies.
3. Quantum chemistry simplifications and mappings.
4. The variational principle.
https://qiskit.org/textbook/ch-applications/vqe-molecules.html

Optional:

“Open Quantum Assembly Language” by Cross et al.

“Qiskit Pulse: Programming Quantum Computers Through the Cloud with Pulses” by Alexander et al.

“eQASM: An Executable Quantum Instruction Set Architecture” by Fu et al.
Wed. 11/10Programing frameworks 2: QiskitIn-class lab on IBM Qiskit quantum framework
Mon. 11/15Programing frameworks 2: QiskitSetup for at-home lab assignment.Lab 2 released.

“Full-Stack, Real-System Quantum Computer Studies:
Architectural Comparisons and Design Insights” by Murali et al.


Optional:

“Not All Qubits Are Created Equal: A Case for Variability-Aware Policies for NISQ-Era Quantum Computers” by Tannu and Qureshi

“A Quantum Computational Compiler and Design Tool for Technology-Specific Targets” by Smith and Thornton

“Extracting Success from IBM’s 20-Qubit Machines Using Error-Aware Compilation” by Nishio et al.
Wed. 11/17Extracting success [slides]Extracting Success
Compiling from a high-level program to hardware:
1. Native gate sets
2. Device topologies
3. Hardware noise
4. Parallelism constraints
Mon. 11/22Extracting success
Wed. 11/24 – Sun. 11/28Thanksgiving Recess
Mon. 11/29 (Wednesday classes)Extracting success“The Physical Implementation of Quantum Computation” by DiVincenzo

“Experimental comparison of two quantum computing architectures” by Linke et al.

Optional:

“The trapped-ion qubit tool box” by Ozeri

“Architecting Noisy Intermediate-Scale Trapped Ion Quantum Computers” by Murali et al.
Wed. 12/1Prototypes [slides]Prominent implementation technologies:
1. Criteria for physical prototypes
2. Implementation technologies
3. Challenges and progress
Mon. 12/6PrototypesIn-class team debate: team ion trap advantages vs. team superconductor advantages (initial arguments)Optional:

“A Quantum Engineer’s Guide to Superconducting Qubits” by Krantz et al.

“Towards Efficient Superconducting Quantum Processor Architecture Design” by Li, Ding, and Xie

“The electronic interface for quantum processors” by van Dijk, Charbon, and Sebastiano
Wed. 12/8PrototypesIn-class team debate: team ion trap advantages vs. team superconductor advantages (rebuttals)
Mon. 12/13Prototypes
Mon. 12/13Regular Classes End
Tue. 12/14Reading Day
Wed. 12/15Reading Day
Thu. 12/16Fall Exams Begin
Thu. 12/23Fall Exams End

Resources

Health and safety requirements for Fall 2021

  • In order to protect the health and well-being of all members of the University community, masks must be worn by all persons on campus when in the presence of others (within six feet) and in buildings in non-private enclosed settings (e.g., common workspaces, workstations, meeting rooms, classrooms, etc.). Masks must be worn during class meetings; any student not wearing a mask will be asked to leave.
  • Masks should conform to CDC guidelines and should completely cover the nose and mouth: https://www.cdc.gov/coronavirus/2019-ncov/prevent-getting-sick/about-face- coverings.html
  • Each day before you arrive on campus or leave your residence hall, you must complete the brief survey on the My Campus Pass symptom checker self-screening app.
  • If you must be absent from class, you may record your absence: https://sims.rutgers.edu/ssra/ and join via Zoom, and/or catch up via the recording and posted notes.

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.