<; office hours Mon 7-8pm, WWH 303
- [Piazza forum for questions](https://piazza.com/nyu/fall2019/csciga3033022/home). We ask that you first try to post all questions on Piazza, and only contact the instructor if necessary.
## Overview
This course will be an introduction to quantum computation. A sample of topics we will try to cover:
- The quantum circuit model of computation
- The Fourier transform
- Basic quantum algorithms like Deutsch-Jozsa, Simon, and Grover
- Shor's factoring algorithm and discrete log
- Quantum entanglement, teleportation, superdense coding
- Quantum query complexity and the adversary method
- Density matrices, state discrimination
- Quantum nonlocal games, Einstein-Podolsky-Rosen, and Bell
- Quantum cryptography, quantum key distribution
The course will be of interest to students working in computer science, mathematics, or physics.
## Prerequisites
A strong undergraduate background in linear algebra (e.g., NYU’s MATH-UA.0140 Linear Algebra), and some familiarity with discrete probability (e.g., NYU’s MATH-UA 235 Probability and Statistics). Familiarity with theory of computation (e.g., NYU’s CSCI-UA.0310 Basic Algorithms) would also be useful. No background in physics is required.
## Resources
- [**Quantum Computation and Quantum Information**](https://www.cs.cmu.edu/~odonnell/quantum18/), by Ryan O'Donnell. Fantastic lecture notes and videos.
- **[Quantum Computation and Quantum Information](https://www.amazon.com/Quantum-Computation-Information-10th-Anniversary/dp/1107002176)**, by Nielsen and Chuang. A great textbook.
- [Video lectures](https://www.youtube.com/playlist?list=PLDAjb_zu5aoFazE31_8yT0OfzsTcmvAVg) by Umesh Vazirani, and notes from an [old course](http://http.cs.berkeley.edu/~vazirani/qc.html).
- [Topics in Quantum Information](http://www.math.uwaterloo.ca/~anayak/co781/), by Ashwin Nayak
- [Quantum Computation](http://www.theory.caltech.edu/people/preskill/ph229/), by John Preskill. More lecture notes on his page.
- [Quantum Computing](https://cims.nyu.edu/~regev/teaching/quantum_fall_2005/index.html), a one-year course I taught many years ago
- Scans of our [Lectures 1-4](lectures_1_4.pdf), [Lectures 5-7](lectures_5_7.pdf), [Lectures 8-13](lectures_8_13.pdf), [Final summary slides](final_slides.pptx)
<!-- - Web site at NYU classes -->
<!-- ; simulating classical circuit by quantum circuits; CNOT does not duplicate a qubit, quantum teleporation, effects of garbage, [Deutsch](http://www.qubit.org/people/david/)'s algorithm; The Fourier transform over Z_2^n, Deutsch-Jozsa algorithm, Bernstein-Vazirani algorithm, Simon's algorithm -->
<!-- Phase estimation
; Universal gates; the black-box model, [BBBV](http://arxiv.org/abs/quant-ph/9701001), lower bound for the OR function; Estimating the number of solutions using phase estimation. A [general lower bound](http://arxiv.org/abs/quant-ph/9802049) on quantum black-box computation by polynomials. Black-box computation can not provide more than a polynomial speedup for total, Boolean functions; A sqrt(n) [quantum communication protocol](http://arxiv.org/abs/quant-ph/9802040) for the disjointness function
-->
## Tentative plan of lectures
Class | Date | Topics | Notes | Assignments
--- | --- | --- | --- | ---
1 | Sep 9 | History, one qubit, Dirac's ket notation, measurements of one qubit in standard basis | O'D 1,2,3 | [HW1](homework1.pdf)
2 | Sep 16 | measurements of one qubit in other bases, unitary transformations, Elitzur-Vaidman bomb, multiple qubits, pure states, X, Y, Z, some more math (Dirac's bra/ket notation, tensors) | O'D 4,5 | [HW2](homework2.pdf)
3 | Sep 23 | CNOT; superdense coding | O'D 6 | [HW3](homework3.pdf)
4 | Sep 30 | EPR, Bell inequalities, and the CHSH game | O'D 7 | [HW4](homework4.pdf)
5 | Oct 7 | HW3 discussion (~1 hour); Basics of quantum computation | O'D 10 | [HW5](homework5.pdf)
6 | **Oct 15** | HW4 and HW5 discussion (~1 hour); baby Bernstein-Vazirani | O'D 11 | [HW6](homework6.pdf)
7 | Oct 21 | HW6 discussion; Bernstein-Vazirani | O'D 12 | [HW7](homework7.pdf)
8 | Oct 28 | Simon's algorithm | O'D 13 | [HW8](homework8.pdf)
9 | Nov 4 | HW7 and HW8 discussion (80 minutes); Fourier transform over Z_N and the QFT circuit| O'D 14 |
10 | Nov 11 | Period finding | O'D 15 | [HW9](homework9.pdf)
11 | Nov 18 | Shor's algorithm; RSA, Discrete Log | O'D 16 |
12 | Nov 25 | Hidden Subgroup Problem (HSP), Dihedral HSP, Kuperberg's algorithm | O'D 17 | [HW10](homework10.pdf)
13 | Dec 2 | Lattices and Dihedral HSP; Grover's algorithm and other query upper bounds | O'D 18,19 |
14 | Dec 9 | Lower bounds on query complexity, adversary method; Lattice-based crypto and LWE | O'D 20 |
15 | **Dec 16** | Exam - Good Luck ! ||
## Course Policies
### Homework
There will be challenging weekly homework assignments.
Homework submissions must be typeset in LaTeX (you might want to use this [Overleaf template](https://www.overleaf.com/read/pcytmtwmppwc); also check out [qpic](https://github.com/qpic/qpic) for drawing quantum circuits), or if absolutely necessary, Word. You are strongly encouraged to insert scanned figures or illustrations. Please
submit through Gradescope.
### Grading
Tentative grade split is 5% participation, 45% homework and 50% final exam. Participation includes both in class and on Piazza.
### Late Submission Policy
Late submissions of homework solutions will be graded with a 20% penalty per day of late submission. Solutions will not be graded if they are submitted later than two days after the specified deadline.
### Academic Integrity
Please review the departmental [academic integrity policy](http://www.cs.nyu.edu/web/Academic/Graduate/academic_integrity.html).
### Collaboration
We strongly encourage you to discuss assignments with your peers. However, all work that you submit must be your own. You must list all discussions you had.
You **should not** consult previous years' students, code, assignments, etc. You may help other students and groups on specific technical issues but you must acknowledge such interactions.
### Plagiarism
**Anything** you use from other sources (other students, web, etc.) must be clearly acknowledged.
Failure to do so will result in a zero grade for the submitted work and, except in cases of obvious mistakes, a University investigation.
### Laptops
We discourage the use of laptops. Pen and paper are more efficient for taking notes, and less distracting to students around you.
If you do decide to bring a laptop, we ask that you use it for taking notes only, and not browsing the web (even if it is
related to the course). If you cannot follow this rule, we ask that you sit in the back row, so there are no students behind you to get distracted by the monitor.
### Participation
Students are expected to attend every meeting of the class.
Students are also expected to participate actively in course discussion, either in person or on Piazza. Participation will be taken into account in the final grade.
## Applicable University Policies
### Academic Integrity
Work you submit should be your own. Please consult the [CAS academic integrity policy](https://cas.nyu.edu/content/nyu-as/cas/academic-integrity.html) for more information. Penalties for violations of academic integrity may include failure of the course, suspension from the University, or even expulsion.
### Religious Observance
As a nonsectarian, inclusive institution, NYU policy permits members of any religious group to absent themselves from classes without penalty when required for compliance with their religious obligations. The policy and principles to be followed by students and faculty may be found in the [University Calendar Policy on Religious Holidays](http://www.nyu.edu/about/policies-guidelines-compliance/policies-and-guidelines/university-calendar-policy-on-religious-holidays.html)
### Disability Disclosure Statement
Academic accommodations are available to any student with a chronic, psychological, visual, mobility, learning disability, or who is deaf or hard of hearing. Students should please register with the Moses Center for Students with Disabilities at 212-998-4980.
> NYU's Henry and Lucy Moses Center for Students with Disabilities
> 726 Broadway, 2nd Floor
> New York, NY 10003-6675
> Telephone: 212-998-4980
> Voice/TTY Fax: 212-995-4114
> Web site: http://www.nyu.edu/csd
]]>