Quantum Computing for Computer Scientists

CMPUT 604-B1

Winter 2024

---

Instructor: Pierre Boulanger 
Email: pierreb@ualberta.ca

Office hours: after class or by appointment 
Course website: https://cs.ualberta.ca/~pierreb/QC-2024

The course will be every Tuesday and Thursday from 12h30 to 13h50 using Zoom.

The class will start on January 9

Register in advance for the meetings:

https://us02web.zoom.us/meeting/register/tZcqd-qoqz8sE90xGqCua0imKH9Nrl8an6go

After registering, you will receive a confirmation email containing information about joining the meeting.

All lectures will be recorded.

Prerequisites: Students should be comfortable with linear algebra concepts such as unitary and Hermitian matrices. They should also have basic knowledge of probability theory.  Prior knowledge of quantum mechanics is helpful but not required.

Course Description: This course introduces the theory and applications of quantum information and quantum computation from the perspective of computer science. The course will cover classical information theory, compression of quantum information, quantum entanglement, efficient quantum algorithms, quantum error-correcting codes, fault-tolerant quantum computation, and quantum machine learning. The course will also cover physical implementations of quantum computation into real quantum computers and their programming languages using real-world examples utilising state-of-the-art quantum technology through the IBM Q Experience, Microsoft Quantum Development Kit, and D-Wave Leap.

Topics to be covered will likely include:

o Introduction, bracket notation, unitary operations, orthogonal measurements, n-qubit states, entanglement, single-qubit, and controlled operations

o Super-dense coding, incomplete measurements, quantum teleportation

o Quantum Computing Computer Architectures

o Quantum Computing Languages

o Quantum circuit model of computation

o Quantum error-correcting codes and fault-tolerance

o Basic quantum algorithms like Deutsch-Jozsa, Simon, and Grover

o Shor factoring algorithm

o Computational complexity theory

o Quantum entanglement, teleportation, and Bell inequalities

o Quantum Fourier transforms and the hidden subgroup problem

o Quantum query complexity, span programs, and the adversary method

o Density matrices, state discrimination, tomography

o Von Neumann entropy and Huevo bound

o Quantum machine learning

Evaluation

o The course evaluation consists of 8 assignments (5% each) on basic quantum theory and algorithmic. Some assignments will also involve programming real quantum computers using web-enabled IBM Q and D-Wave access.

o Most of the marks will be on a final project (60%) that must include basic quantum computing applications and their implementation on a simulator and a real quantum computer.

Lecture Date	Topics	Course Material	Assignments and Announcements
Jan. 9, 11	o Introduction	Introduction Lecture Recording 1	o Introduction to Google Colab o Introduction to Qiskit o Qiskit Website o Qiskit Course o Quantum Computing in 2 Hours
	o Origin of Quantum Mechanics and History of Quantum Computing	History-of-QC-and-QI This lecture is for your information	o Quantum Computing Report o Open-source software in quantum computing o Mathematic Refresher
Jan. 16, 18	o Intro. To Complex Linear Algebra and Hilbert Space o Dirac Notation and Schrodinger Equation	Abstract vector spaces CLA_and_HS More on Dirac Notation and Hilbert Space Derivation-of-Shrodinger-Eqn.pdf Lecture Recording 2 Lecture Recording 3	Assignment 1a: Solve the following math problems Additional Information for Assignment 1 o  Foundation of QC o  Measurement o  Density Matrix o  Latex Physics Package Coding Assignments o Assignment 1b Colab Notebook Due date: Jan. 23
Jan. 23, 25,30	o Classical Bit and Quantum Bit Manipulations o Circuit model of quantum computation-I	CBit and Qbit Manipulations  Lecture Recording 4 Quantum-Circuits-I Lecture Recording 5 Lecture Recording 6	Assignment 2: Implement the following quantum circuits using Qiskit o Coding Assignment 2 Colab Notebook Due Date: Feb. 2 o Quantum Shift Register Notebook o Quantum RAM Notebook
Feb.  1, 6	o Circuit model of quantum computation-II o More in Simon algorithm	Quantum-Circuits-II Simon Algorithm Implementation Quantum-Circuits-III Lecture Recording 7 Lecture Recording 8	Assignment 3: Quantum Fourier Transform and Phase Detection Using Qiskit o Coding Assignment 3 Colab Notebook Due Date: Feb. 26 o Shor Algorithm Notebook o Quantum Phase Estimation Notebook
Feb. 8,13,15	o Phase Estimation and Shor Algorithm o More on Shor quantum factoring algorithm o Grover search algorithm	Quantum Fourier Transform Shor Algorithm Video on Shor Algorithm Quantum Circuits-IV Lecture Recording 9	Assignment 4: Implement Shor Algorithm using Qiskit o Coding Assignment 4 Colab Notebook o Running a QC Program on IBM Q o Pennylane Tutorial on Gover Algorithm Due Date: Feb. 26
No class Reading Week (Feb. 19-23)
Feb. 27 -29	o Quantum Gate Neural Networks	Quantum-Gate-Neural-Networks Training Optimization for Gate-Model Quantum Neural Networks Lecture Recording 10 Lecture Recording 11	Assignment 5: Implement Quantum Neural Network using TensorFlow Quantum o Coding Assignment 5 Colab Notebook Due Date: Mar. 9 Project Description Due Mar. 8 My suggestion for this year is that you choose from https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9207714 a topic that fits with your current research. I would like you to send by the due date the following: 1. A title of the project 2. A short description of its objectives and theoretical foundation (max 3 pages in PDF formal) 3. Two or three reference papers that describes similar work 4. The source of data you will use to test the idea 5. A zip archive that includes the PDF files of the project description and the reference papers
Mar. 7,12,14	o Adiabatic Quantum Algorithm o Adiabatic Quantum Hardware o D-Wave Programming Environment	Quantum Annealing Computer Quantum Annealing Supplement Lecture Recording 12 Lecture Recording 13 Lecture Recording 14 D-Wave 2000Q System D-Wave Leap Solving Problems Using QUBO QUBO Tutorial	Assignment 6: Discrete Optimization and Unsupervised Learning Using DWAVE o Coding Assignment 6 Colab Notebook Due Date: March 15 o To do this assignment you need to get an account on DWAVE virtual machine. Please use the DWAVE Leap website to get your ID and the machine name to run your program. The code contains my ID and the machine to use but only use it for a demo. Use your own!
Mar. 19, 21, 26,28, Apr 2,4	o Quantum Machine Learning o Quantum Information Theory o DWAVE Quantum o Pennylane Certificate	Quantum-Machine-Learning Lecture Recording 15 Lecture Recording 16 Lecture Recording 17 Lecture Recording 18 Lecture Recording 19 More on Quantum Machine Learning Quantum Information Theory Fast Track Your Quantum Journey with Quantum Computing Training Expand your knowledge of quantum computing and get started building quantum applications today. With the Quantum Programming Core Course, you can accelerate quantum application development and ramp up quickly with expert training and guidance. You will also connect with the Leap community and D-Wave experts to gain new ideas and skills while differentiating yourself in the marketplace. Earn the new Introduction to PennyLane Certificate	QML NASA Presentation Book by Wittek on QML Quantum Approaches to Data Science and Data Analytics Examples of Quantum Machine Learning o Variational Quantum Linear Solver o Solving Linear Systems of Equations Using HHL o Classical K-mean o Quantum K-mean o Quantum Kernel Classification o Kernel Classification with Various Encodings o Training with Hybrid Architecture o Quantum Generative Adversarial Networks o Quantum Convolution o Quantum Reinforced Learning Assignment 7: Quantum Auto-Encoders o Coding Assignment 7 Colab Notebook Due Date: March 26 Assignment 8: Training Deep Belief Networks Using Quantum Boltzmann Machine o Coding Assignment 8 Colab Notebook Due Date: April 9
Apr. 9,11	o Quantum Cryptography o Quantum Computer Hardware o Quantum Computer Compiler o   Fault-tolerant quantum error correction	Quantum Cryptography Quantum Computer Hardware Overview LC-Circuit-and-QC.pdf Quantum-Computer-Compiler Quantum Error Correction	Quantum Cryptography Explained o Quantum Error Correction-1 o Qauntum Error Correction-2 o Quantum Error Corrections-3 Final Project Report Due: April 25 The report should be 8-10 pages and follow the IEEE double columns format. You also must supply the notebook with the results and the code.

Background Reading

• A Rosetta Stone for Quantum Mechanics with an Introduction to Quantum Computation by Samuel J. Lomonaco, JR.
• An Introduction to Quantum Computing for Non-Physicists by Eleanor Rieffel and Wolfgang Polak

Books

• Quantum Computer Science by David Mermin (2007)
• Quantum Computing for Computer Scientists by Yanofsky, Noson S. and Mirco A. Mannucci (2008)
• Quantum Computation and Quantum Information by Nielsen and Chuang (2010)
• Classical and Quantum Computation by Kitaev, Shen, and Vyalyi (1999)
• Quantum Information Theory by Mark Wilde (2013)
• An Introduction to Quantum Computing by Phillip Kaye, Raymond Laflamme, and Michele Mosca (2007)
• Quantum Computing Explained by McMahon, David (2008).

Other Lecture Notes

• Quantum Computation by David Mermin
• Quantum Computation by Umesh Vazirani
• Quantum Computation by John Preskill
• Theory of Quantum Information and Introduction to Quantum Computing by John Watrous
• Quantum algorithms by Andrew Childs
• Quantum Computing Since Democritus by Scott Aaronson
• Quantum Computing by David Bacon
• Quantum Computation and Information by Ryan O'Donnell, John Wright
• Quantum Computing by Peter Shor
• Qubits, Quantum Mechanics, and Computers by Birgitta Whaley, Kevin Young, Mohan Sarovar
• Topics in Quantum Computing by Don Towsley and Bo Jiang with videos
• Quantum Computing by Ronald de Wolf with full-fledged lecture notes
• Great Ideas in Theoretical Computer Science by Scott Aaronson with lectures on Quantum Computing and Quantum Algorithms

Quantum Computing Devices/Simulators

• DWave LEAP
• IBM's QX and qiskit plus talk (slides/video)
• Introduction to Quantum Computing
• Quantum Algorithm Implementations for Beginners (with IBM examples)
• Quantum Neural Network (Japan)
• Microsoft's Q#
• ScaffCC Compiler
• QX Quantum Computer Simulator from QuTech / TU Delft (joint with Intel)
• List of Quantum Computing Tools
• qmasm and edif2qmasm (EDIF Verilog to DWave Qmasm) from Scott Pakin (LANL)
• Quirk web-based gate-model simulator w/ Grover algorithm
• recommended for Quirk users: Quantum computing for the determined Utube video series by Michael Nielsen
• QuTiP Quantum Toolbox in Python (for Physics problems)

Papers/Talks

• From Cbits to Qbits: Teaching Computer Scientists Quantum Mechanics by David Mermin
• Design of a Superconducting Quantum Computer by John Martinis (UCSB+Google QUantum AI)
• Adiabatic Quantum Computation by Vicky Choi (VT)
• A Layered Software Architecture for Quantum Computing Design Tools by Svore at al., IEEE Computer ( Volume: 39, Issue: 1, Jan. 2006 )
• ScaffCC: A Framework for Compilation and Analysis of Quantum Computing Programs. Ali JavadiAbhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T. Chong, Margaret Martonosi. ACM International Conference on Computing Frontiers, May 2014. Best Paper Award. ScaffCC on github. related slides
• Software and Architectures for Large-Scale Quantum Computing, Fred Chong, U. Chicago
• Compiler Management of Communication and Parallelism for Quantum Computation. Jeff Heckey, Shruti Patil, Ali JavadiAbhari, Adam Holmes, Daniel Kudrow, Ken Brown, Diana Franklin, Margaret Martonosi, Frederic T. Chong. Architectural Support for Programming Languages and Operating Systems (ASPLOS), March 2015.
• more papers by Fred Chong U Chicago
• A Software Methodology for Compiling Quantum Programs, Thomas Häner, Damian S. Steiger, Krysta Svore, Matthias Troyer, arXiv:1604.01401, some slides
• D-Wave pubs suitable for presentation:
• A practical heuristic for finding graph minors by Jun Cai, Bill Macready, Aidan Roy
• Discrete optimization using quantum annealing on sparse Ising models, Bian et al., Front. Phys., 18 September 2014
• Other D-Wave pubs:
• Experimental Demonstration of a Robust and Scalable Flux Qubit by Harris et al., arXiv:0909.4321v1
• Architectural considerations in the design of a superconducting quantum annealing processor by Bunyk et al., arXiv:1401.5504
• Entanglement in a Quantum Annealing Processor by Lanting et al., arXiv:1401.3500
• Gates for Adiabatic Quantum Computing by Richard H. Warren, arXiv:1405.2354, 2014
• Ground State Spin Logic by J. D. Whitfield, M. Faccin, J. D. Biamonte, arXiv:1205.1742, 2012

• Performance Models for Split-execution Computing Systems by Travis S. Humble, Alexander J. McCaskey, Jonathan Schrock, Hadayat Seddiqi, Keith A. Britt, Neena Imam, arXiv:1607.01084
• A quantum macro assembler by Scott Pakin, High Performance Extreme Computing Conference (HPEC), 2016, QMASM github code
• QX: A high-performance quantum computer simulation platform by Khammassi et al., DATE'17
• Quantum Error Correction for Beginners by Simon J. Devitt, Kae Nemoto, William J. Munro, arXiv:0905.2794
• Quantum Computing over Finite Fields: Reversible Relational Programming with Exclusive Disjunctions by Roshan P. James, Gerardo Ortiz, Amr Sabry, arXiv:1101.3764
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm, Edward Farhi, Aram W Harrow, arXiv:1602.07674 (Submitted on 24 Feb 2016)
• Error mitigation for short-depth quantum circuits, Kristan Temme, Sergey Bravyi, Jay M. Gambetta (Submitted on 6 Dec 2016 (v1), arXiv:1612.02058, last revised 6 Nov 2017 (this version, v3))
• Physics: Hybrid Quantum-Classical Approach to Correlated Materials, Bela Bauer, Dave Wecker, Andrew J. Millis, Matthew B. Hastings, and Matthias Troyer, Phys. Rev. X 6, 031045, 21 September 2016
• Chemistry: A variational eigenvalue solver on a photonic quantum processor, A. Peruzzo et al., Nature Comms 5, 4213 (2014)
• Quantum supremacy: Quantum advantage with shallow circuits by Sergey Bravyi, David Gosset, Robert Koenig in arXiv:1704.00690, Apr 2017, also in Science, 19 Oct 2018: Vol. 362, Issue 6412, pp. 308-311, DOI: 10.1126/science.aar3106, slides, video

---