Home | Publications | Research Summary | Teaching | Journals | Collaborators

Theory of Quantum Computation—PHYS 7895

The field of quantum computation exploded in 1994 when Peter Shor published his algorithm that can break RSA encryption codes. Since then, physicists, mathematicians, and engineers have been determining the ultimate capabilities for quantum computation and many quantum algorithms have been established as well. Quantum computation has now fundamentally altered our understanding of computation and complexity theory. Furthermore, it is inevitable that Moore's law will break down (in fact with the former chief architect at Intel recently suggesting that this will occur within a decade), and at this point quantum mechanical effects will be unavoidable. The idea of quantum computation is to harness these effects (rather than avoid them) in order to speed up computations for certain tasks. If you take this course, you will learn about the well known quantum algorithms for factoring integers and database search and in addition you will learn how quantum computation has altered our understanding of computation. The only prerequisites necessary are a course in linear algebra and probability theory (which are standard components in any graduate education in electrical engineering, computer science, mathematics, or physics).

Course Syllabus
Guideline for Final Presentations

Office hours from 10:30-11:30am on Mondays in 447 Nicholson Hall

Homeworks

Homework 3

Homework 2

Homework 1

Lectures

Lecture 24 (28 Apr 2014)

  • Guest lecturer Thomas Cooney
  • nonlocal quantum games
  • CHSH game and its rigidity
  • QMIP = MIP*
Reading Material: Cleve, Hoyer, Toner, Watrous,
Reichardt, Unger, and Vazirani,
Ito and Vidick

Lecture 23 (23 Apr 2014)

  • Guest lecturer Thomas Cooney
  • complexity class QMA(k) (QMA with k unentangled provers)
  • examples of promise problems relevant for QMA(2)
  • proof that QMA(k) = QMA(2)
  • product test and error reduction
Reading Material: QMA(2) article by Harrow and Montanaro

Lecture 22 (21 Apr 2014)

  • finishing the proof of QMA hardness of Local Hamiltonian (LH)
Reading Material: QMA review article (Aharonov and Naveh), Section 1.5.5 of the PhD thesis of Sev Gharibian, Chapter 15 of Kitaev, Shen, and Vyalvi

Lecture 21 (9 Apr 2014)

  • QMA hardness of Local Hamiltonian (LH)
  • Feynman-Kitaev circuit-to-Hamiltonian construction
  • history state (the encoding of a quantum computation)
  • local quantum checks to penalize invalid configurations of a QMA proof system
Reading Material: QMA review article (Aharonov and Naveh), Section 1.5.5 of the PhD thesis of Sev Gharibian, original paper of Feynman, Chapter 15 of Kitaev, Shen, and Vyalvi

Lecture 20 (7 Apr 2014)

  • QMA-complete promise problem Local Hamiltonian (LH)
  • simple proof that LH is NP-hard (by appealing to MAX-k-CSP)
  • proof that LH is in QMA
Reading Material: Quantum computational complexity theory review article (Watrous), QMA review article (Aharonov and Naveh), and Section 1.5.5 of the PhD thesis of Sev Gharibian

Lecture 19 (2 Apr 2014)

  • strong error reduction for QMA
Reading Material: Quantum computational complexity theory review article (Watrous), Marriott-Watrous strong error reduction

Lecture 18 (31 Mar 2014)

  • complexity class QMA (Quantum Merlin-Arthur)
  • group non-membership problem, not known to be in NP but in QMA
  • simple error reduction for QMA
Reading Material: Quantum computational complexity theory review article (Watrous), Group non-membership problem and Quantum complexity theory tutorial (Part 1), Quantum complexity theory tutorial (Part 2)

Lecture 17 (26 Mar 2014)

  • optimality of Grover's algorithm
  • brief discussion of quantum simulation (Lie-Trotter formula)
Reading Material: Dave Bacon's lecture notes and Andrew Childs' lecture notes

Lecture 16 (24 Mar 2014)

  • amplitude amplification as an extension of Grover's algorithm
  • amplitude estimation and quantum counting
Reading Material: Sections 8.2-8.4 of Kaye, Laflamme, and Mosca

Lecture 15 (19 Mar 2014)

  • continuing with Grover's algorithm
  • two different pictures to illustrate how it works
Reading Material: Section 8.1 of Kaye, Laflamme, and Mosca

Lecture 14 (17 Mar 2014)

  • hidden subgroup problem
  • solution for the abelian case
  • introduction to Grover's algorithm
Reading Material: Sections 7.5 and 8.1 of Kaye, Laflamme, and Mosca

Lecture 13 (12 Mar 2014)

  • finishing Shor's quantum order finding algorithm
  • classical reduction of factoring to order finding
Reading Material: Section 5.3.2 of Nielsen and Chuang

Lecture 12 (10 Mar 2014)

  • Shor's quantum order finding algorithm
  • review of modular arithmetic
  • multiplication mod N
  • modular exponentiation circuits
Reading Material: Section 5.3.1 of Nielsen and Chuang

Lecture 11 (7 Mar 2014)

  • error estimates for quantum phase estimation
Reading Material: Chapter 7 of Kaye, Laflamma, and Mosca

Lecture 10 (5 Mar 2014)

  • quantum Fourier transform
  • phase estimation
Reading Material: Chapter 7 of Kaye, Laflamma, and Mosca

Lecture 9 (19 Feb 2014)

  • phase kickback trick
  • Deutsch-Jozsa algorithm
  • Simon's algorithm
Reading Material: Chapter 6 of Kaye, Laflamma, and Mosca

Lecture 8 (17 Feb 2014)

  • proof that polynomial-size circuits cannot generate all n-qubit unitaries
  • definition of BQP
  • BQP subroutine theorem
  • simple proof that BQP is in PSPACE
Reading Material: Chapter 4 of Nielsen and Chuang

Lecture 7 (14 Feb 2014)

  • discrete, dense subgroups of SU(2)
  • approximations of unitaries
  • importance of the Solovay-Kitaev theorem for quantum computation
  • the Solovay-Kitaev algorithm
Reading Material: Chapter 4 of Nielsen and Chuang, arXiv:quant-ph/0505030, video lecture of Ben Reichardt

Lecture 6 (12 Feb 2014)

  • circuit model of quantum computation
  • decomposition of a single-qubit unitary as a product of rotations
  • controlled unitaries
  • any n-qubit unitary can be realized with CNOTs and single-qubit unitaries
Reading Material: Chapter 4 of Nielsen and Chuang

Lecture 5 (10 Feb 2014)

  • definition of BPP
  • probability amplification with the Chernoff bound
  • Landauer's erasure principle from minimal assumptions
  • reversible computation and “uncomputing”
Reading Material: Chapter 3 of Nielsen and Chuang and Sections 2 and 3 of arXiv:1306.4352

Lecture 4 (27 Jan 2014)

  • Cook-Levin theorem - 3SAT is NP-complete
  • simulation of a Turing machine with uniform circuit families
  • reduction of any NP algorithm to CircuitSAT
  • reduction to 3SAT
Reading Material: Chapter 3 of Nielsen and Chuang

Lecture 3 (21 Jan 2014)

  • circuit model of computation
  • universality of AND, OR, NOT, SWAP, and COPY
  • uniform circuit families
  • complexity classes P and NP
  • reductions
Reading Material: Chapter 3 of Nielsen and Chuang

Lecture 2 (17 Jan 2014)

  • notion of algorithm / Turing machine
  • Church-Turing thesis
  • computable functions
  • universal Turing machine
  • halting problem and undecidability
Reading Material: Chapter 3 of Nielsen and Chuang

Lecture 1 (15 Jan 2014)

  • course overview and discussion of potential final project topics


Last modified: May 08, 2014.