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 SyllabusGuideline for Final Presentations

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

### Homeworks

### Lectures

- Guest lecturer Thomas Cooney
- nonlocal quantum games
- CHSH game and its rigidity
- QMIP = MIP*

Reichardt, Unger, and Vazirani,

Ito and Vidick

- 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

- finishing the proof of QMA hardness of Local Hamiltonian (LH)

- 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

- 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

- strong error reduction for QMA

- complexity class QMA (Quantum Merlin-Arthur)
- group non-membership problem, not known to be in NP but in QMA
- simple error reduction for QMA

- optimality of Grover's algorithm
- brief discussion of quantum simulation (Lie-Trotter formula)

- amplitude amplification as an extension of Grover's algorithm
- amplitude estimation and quantum counting

- continuing with Grover's algorithm
- two different pictures to illustrate how it works

- hidden subgroup problem
- solution for the abelian case
- introduction to Grover's algorithm

- finishing Shor's quantum order finding algorithm
- classical reduction of factoring to order finding

- Shor's quantum order finding algorithm
- review of modular arithmetic
- multiplication mod N
- modular exponentiation circuits

- error estimates for quantum phase estimation

- quantum Fourier transform
- phase estimation

- phase kickback trick
- Deutsch-Jozsa algorithm
- Simon's algorithm

- proof that polynomial-size circuits cannot generate all n-qubit unitaries
- definition of BQP
- BQP subroutine theorem
- simple proof that BQP is in PSPACE

- discrete, dense subgroups of SU(2)
- approximations of unitaries
- importance of the Solovay-Kitaev theorem for quantum computation
- the Solovay-Kitaev algorithm

- 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

- definition of BPP
- probability amplification with the Chernoff bound
- Landauer's erasure principle from minimal assumptions
- reversible computation and “uncomputing”

- 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

- circuit model of computation
- universality of AND, OR, NOT, SWAP, and COPY
- uniform circuit families
- complexity classes P and NP
- reductions

- notion of algorithm / Turing machine
- Church-Turing thesis
- computable functions
- universal Turing machine
- halting problem and undecidability

- course overview and discussion of potential final project topics

*Last modified: May 08, 2014.*