Quantum Computing for Computer Scientists

CMPUT 604-B1

Fall 2021


Instructor: Pierre Boulanger 
Email: pierreb@ualberta.ca

Office hours: after class or by appointment 
Course web site: http://cs.ualberta.ca/~pierreb/QC-2021

 

The course will be every Monday and Wednesday from 14h00 to 15h20 using Zoom

Class will Start on September 8

Register in advance for the meetings: Zoom Link

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 utilizing a 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, braket 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 Holevo's bound

o Quantum machine learning

 

Evaluation

The course evaluation consists of 5 assignments (10% 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 (50%) that must include basic quantum computing applications and their implementation on a simulator and a real quantum computer.

 Lecture Notes

Lecture Date

Topics

Course Material

Assignments and Announcements

Sept. 8, 13, 15

Introduction

Introduction

Class Recording-1

Class Recording-2

Class Recording-3

Quantum Computing Report

Sept. 20

Origin of Quantum Mechanics and History of Quantum Computing

 

 

History-of-QC-and-QI

Class Recording-4

 

 

 

 

 

Assignment 0:

o  How to install Q# Using Jupyter Notebook

o  Q# quantum programming language

o  Fast Introduction to Q#

Quantum Katas, an open-source collection of self-paced tutorials and sets of programming exercises in the form of Q# Jupyter Notebooks.

 

The Quantum Katas tutorial notebooks are a good starting point to learn Q#

Please try the single qbit circuit

Sept. 22, 27

Intro. To Complex Linear Algebra and Hilbert Space

 

Dirac Notation and Shrodinger Equation

 

 

Postulate of Quantum Mechanics Using Dirac Notation

Abstract vector spaces

CLA_and_HS

Class Recording-5

Class Recording-6

More on Dirac Notation and Hilbert Space

Derivation-of-Shrodinger-Eqn.pdf

 

 

The postulate of Quantum Mechanics

Assignment 1: Solve the following mat problems QC Math1

Additional Information for Assignment 1

o  Foundation of QC

o  Measurement

o  Density Matrix

o  Latex Physics Package

Due date: October 5, 2021

Sept. 29

Oct. 4

No class on October 6 due to the Qubits 2021conference

Classical Bit and Quantum Bit Manipulations

 

Circuit model of quantum computation-I

 

CBit and Qbit Manipulations 

Class Recording-7

Class Recording-8

 

Quantum-Circuits-I

 

October 5-7: Qubits 2021

Assignment 2: You first quantum circuits in Q#

 

Introduction to quantum computing with Q#

 

Due Date: October 10, 2021

Oct.11 No class

Thanksgiving

 

 

Oct. 13, 18, 20

Circuit model of quantum computation-I/II

 Quantum-Circuits-I

Class Recording-9

Class Recording-10

 

Quantum-Circuits-II

Marks for Assignment 1 and 2

Solution to Assignment 1

Oct. 25, 27

Nov. 1

No class on Nov. 3

o  More in Simon algorithm

 

o  Phase Estimation and Shor Algorithm

 

o  More on Quantum Fourier transform and periodicities

 

o  More on Shor quantum factoring algorithm

 

o  Quantum Gate Neural Networks

 

 

 

o  Universal Set Gates and Grover search algorithm

Simon Algorithm Implementation

 

Quantum-Circuits-III

Class Recording-11

Class Recording-12

 

 

Quantum Fourier Transform

 

 

Shor Algorithm

Video on Shor Algorithm

 

Quantum-Gate-Neural-Networks

Training Optimization for Gate-Model Quantum Neural Networks

Class Recording-13

 

Quantum Circuits-IV

Class Recording-14

Assignment 3: Quantum Adder and Oracles

 

Due Date: October 24, 2021

 

 

Project Description Due

November 6

 

Souce Material to help you chose your project

 

o  Quantum TensorFlow

o  Quantum Machine Learning 1.0

o  Power of data in quantum machine learning

o  DWAVE Computing

 

Example of Previous Projects

 

Quantum Neural Networks with Continuous-Variable Formalism

Implementing Quantum Computing on Solving Linear Systems of Equations

A Quantum Collaborative Filtering Framework

Root Finding with Quantum Computer

Implementing a Quantum Genetic Algorithm

Integer Factorization through Quantum Annealing

Solving Nonograms with Quantum Annealing

 

Week 8

No class Reading Week (Nov. 8-12)

 

Nov. 15

 

o  Quantum Computer Compiler

o  Fault-tolerant quantum error correction

 

 

 

Quantum-Computer-Compiler

 

Quantum Error Correction

Class Recording-15

Assignment 4: Running a QC Program on IBM Q

Introduction to IBM qiskit

Due Date: November 19, 2021

Nov. 17, 24

o  Adiabatic Quantum Algorithm

 

 

 

o  Adiabatic Quantum Hardware

 

 

o  D-Wave Programming Environment

Quantum Annealing Computer

Class Recording-16

Class Recording-17

Class Recording-18

Quantum Annealing Supplement

 

D-Wave 2000Q System

 

D-Wave Leap

Solving Problems Using QUBO

QUBO Tutorial

Assignment 5: The main goal of this assignment is to learn how to use the D-Wave programming environment

o  Register to D-Wave Leap

o  Install SDK

o  Run the Anneal Schedule Jupyter tutorial

o  Factoring with the D-Wave System

o  Factorisation Using Annealing Paper

You need to submit a pdf report with:

  • Change example code to 4 bits
  • Showing screenshots
  • Various example runs 
  • Study the effects of annealing schedule and other DWAVE solver parameters on the accuracy of the factorization
  • Estimate QPU Timing for various cases
  • Compare complexity and performance to Shor Algorithm
  • Any modifications to the code to make it work better

 

New due Date: December 5, 2021

Nov. 29

o  Quantum Computer Hardware

Quantum Computer Hardware Overview

LC-Circuit-and-QC.pdf

 

Class Recording-19

Dec 1

o  Quantum Cryptography

o  Qauntum Information Theory

Quantum Cryptography

 

Quantum Information Theory

 

Class Recording-20

Quantum Cryptography Explained

Dec. 6, 8

o  Quantum Machine Learning

Quantum-Machine-Learning

Class Recording-21

More on Quantum Machine Learning

Quantum TensorFlow

 QML NASA Presentation

Book by Wittek on QML

Quantum Approaches to Data Science and Data Analytics

Final Project Report Due

December 16


 

Background Reading

Books

Other Lecture Notes

Quantum Computing Devices/Simulators

Papers/Talks

o  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

o  A quantum macro assembler by Scott Pakin, High Performance Extreme Computing Conference (HPEC), 2016, QMASM github code

o  QX: A high-performance quantum computer simulation platform by Khammassi et al., DATE'17

o  Quantum Error Correction for Beginners by Simon J. Devitt, Kae Nemoto, William J. Munro, arXiv:0905.2794

o  Quantum Computing over Finite Fields: Reversible Relational Programming with Exclusive Disjunctions by Roshan P. James, Gerardo Ortiz, Amr Sabry, arXiv:1101.3764

o  Quantum Supremacy through the Quantum Approximate Optimization Algorithm, Edward Farhi, Aram W Harrow, arXiv:1602.07674 (Submitted on 24 Feb 2016)

o  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))

o  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

o  Chemistry: A variational eigenvalue solver on a photonic quantum processor, A. Peruzzo et al., Nature Comms 5, 4213 (2014)

o  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, slidesvideo