Quantum Computing for Computer Scientists

CMPUT 604-B1

Winter 2020


Instructor: Pierre Boulanger 
Email: pierreb@ualberta.ca

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

Course will be every Friday in CSC 3-49 from 10h00 to 11h45

 

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 is an introduction to 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

o The course evaluation consists of 4 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 (60%) that must include basic quantum computing applications and its implementation on a simulator and a real quantum computer.

 Lecture Notes

Lecture Date

Topics

Slides and Texts

Assignments

Lecture 1

Introduction

Introduction.pptx

 

Lecture 2

Origin of Quantum Mechanics and History of Quantum Computing

History-of-QC-and-QI.pptx

 

Lecture 3

Intro. To Complex Linear Algebra and Hilbert Space

 

Special case for Classical Bits (CBit) and Quantum Bit (Qubit)

Abstract vector spaces

CLA_and_HS.pptx

More on Dirac Notation and Hilbert Space

Derivation-of-Shrodinger-Eqn.pdf

The postulate of Quantum Mechanics Using Dirac Notation

 

Lecture 4

Classical Bit and Quantum Bit Manipulations

 

 

Basic Quantum Bit Operations

First Classical Bits

CBit and Qbit Manipulations 

 

Basic-Quantum-Operations.pptx

Assignment 1: Solve the following mat problems QC Math1

In addition, please follow the tutorials and document the results.

o  IBM-Q Introduction Tutorial

Due date Feb. 10

Lecture 5

Circuit model of quantum computation

Quantum-Circuits-I.pptx

 

 

Solution to Assignment 1

Lecture 6

o  The Deutsch-Jozsa algorithm

o  Simon algorithm

o  Quantum Fourier transform and periodicities

o  Shor quantum factoring algorithm

o  IBM Programming Environment

Quantum-Circuits-II.pptx

Simon Algorithm Implementation

 

Quantum-Circuits-III.pptx

 

Shor Algorithm

Quantum Fourier Transform

 

Introduction to IBM qiskit

Assignment 2:

Part I: Homework2

Part II: Read the following:

Read Introduction to Quantum Computing Using qcl

Part III: Run the following quantum circuits on IBM Q and explain how it works by documenting the results

o  Quantum teleportation

o  Deutsch-Jozsa algorithm

o  Simon algorithm

o  Quantum Fourier Transform

Due date Feb. 24

No class Reading Week (Feb. 17-21)

 

Project Description Due Mar. 8

Lecture 7

o  Universal Set Gates

o  Grover quantum search algorithm

o  Microsoft Q# Language

Quantum-Circuits-IV.pptx

 

 

Introduction to Microsoft Q#

Quantum Computing at Microsoft

Tutorial on Q#

Quantum-Computer-Compiler.pptx

 

Solution to Assignment 2 Part I

Assignment 3:

Part I: Run the following quantum circuits on IBM Q and explain how it works by documenting the results.

o  Quantum phase estimation

o  Grover Algorithm

Part II: Implement Gover Algorithm Using Microsoft Q#

Due date Mar. 8

Lecture 8

o  Adiabatic Quantum Algorithm

o  Adiabatic Quantum Hardware

 

 

 

 

 

 

 

o  D-Wave Programming Environment

Quantum Annealing

How The Quantum Annealing Process Works.mp4

Measuring Quantum Physics in a Quantum Annealer.mp4

Physics of Quantum Annealing - Hamiltonian and Eigenspectrum.mp4

LC-Circuit-and-QC.pdf

D-Wave 2000Q System

 

D-Wave Leap

Solving Problems Using QUBO

QUBO Tutorial

Assignment 4: 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  Factoring with the D-Wave System

o  Anneal Schedule

o  Factorisation Using Annealing

Report the results with an analysis

Due date Mar. 22

Lecture 9

o  Quantum Computer Hardware

o  How to Design a Qbit

o  Fault-tolerant quantum error correction

o  Fault-tolerant quantum gates, Eastin-Knill theorem

 

o  Microsoft QC Hardware

 

o  Future

Quantum Computer Hardware Overview

How to Make a Qubit IBM Style?

How To Make a Quantum Bit

Quantum Dots

IBM-Q Hardware

Qbit with Light

Quantum Error Correction

 

Topological Quantum Computer

 

Future spintronics devices using quantum dot structures

Lecture 10

o  Quantum Cryptography

Quantum Cryptography

Quantum Cryptography Explained

Lecture 11

o  Quantum Machine Learning

Quantum-Machine-Learning.pptx

More on Quantum Machine Learning

Quantum Information Theory

Google announced its own quantum computing library based on TensorFlow

 QML NASA Presentation

Book by Wittek on QML

 

Final Project Report Due April 15

Last Year Project Presentations

Shrimanti Ghosh

Quantum Neural Networks with Continuous-Variable Formalism

 

Thea Wang

Implementing Quantum Computing on Solving Linear Systems of Equations

 

Zhaorui Chen

A Quantum Collaborative Filtering Framework

 

Zhi Han

Root Finding with Quantum Computer

 

Ayantha Randika

Implementing a Quantum Genetic Algorithm

 

Satchel Jeanne Armena

Integer Factorization through Quantum Annealing

 

Bradley Swanson

Solving Nonograms with Quantum Annealing

 


 

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