PHY680-1 Quantum Computing

Home Teaching PHY680: Announcement/Update AcademicCalendar

PHY680-1 Quantum Computing, Spring 2014

TuTh 8:30 - 9:50AM Physics Building P123
Instructors: Vladimir Korepin and Tzu-Chieh Wei
Office hour: Tue 10-11am Math Building 6-101 (Tzu-Chieh Wei) and by appointment

For Prof. Korepin's website, please see here.
For the content taught in Spring 2012, see here or below.

Brief description of the course:
Quantum Information and Computation exploits quantum mechanical rules to process information. It has emerged in recent years as a new branch of interdisciplinary science. It has both fundamental and technological implications. This course will start with an overview of quantum computation and quantum information. Then quantum mechanics of open systems and general quantum operations will be discussed. Topics will also include POVM, super-operators and Bell inequalities. Entanglement theory (such as entanglement of formation/distillation and entanglement entropy) will be explained and the connections to physics of quantum spin chains, quantum phase transitions and thermodynamics will be explored. Classical and quantum information theory [such as Shannon theorems on channel capacity and Schumacher’s quantum data compression] will then follow. Important subjects such as algorithm theory (Shor's and Grover's quantum algorithms) and quantum error correction will be covered. Various models of quantum computation will be explained, including circuit, adiabatic, topological and measurement-based quantum computation. Different physical implementations of quantum computers will be presented, such as fractional quantum Hall system, Josephson junction, quantum optics, and trapped ions. Furthermore, quantum simulations—an idea proposed by Feynman—will be discussed. Some selected advanced topics will be covered if time permits.

This course requires only basic knowledge from quantum mechanics and aims to reach students with different backgrounds such as physics, chemistry, mathematics and computer science.

Learning outcomes:
Students who have completed this course
• Should understand foundations of quantum mechanics such as measurement theory, interaction with environment and the role of entanglement
• Should understand the physical principles of quantum computation and the working of quantum algorithms such as Shor's and Grover's
• Should understand the basics of information theory and their relation to statistical mechanics and probability theory

Textbooks and references:
Quantum Computation and Quantum Information, M. Nielsen and I. Chuang (Cambridge University Press)
An Introduction to Quantum Computing, P. Kaye, R. Laflamme and M. Mosca (Oxford)
Classical and Quantum Computation, A. Yu. Kitaev, A. H. Shen and M. N. Vyalyi (AMS)
Feynman Lectures On Computation
J. Preskill lecture notes (http://www.theory.caltech.edu/~preskill/ph229/#lecture)
Andrew Steane’s paper on Quantum Computing (http://arxiv.org/pdf/quant-ph/9708022 or published version in Report on Progress in Physics)
From Classical to Quantum Shannon Theory (a book) by Mark Wilde, arXiv:1106.1445.

Grades: (tentative)
Homework 25%
Midterm 30%
Presentation (plus a short report) 30% (for suggested topics/papers, see below)
Participation 15%

Topics to be covered and tentative syllabus
(This is a tentative syllabus. Exam dates and due dates may change. Check later for update.)

(week 1) (Overview, qubits, simple gates, quantum teleportation, simple quantum algorithms)
(week 2) (Review of Postulates of QM, POVM, distinguishing nonorthogonal states, no-cloning, interaction-free measurement, density matrices, purification, Schmidt decomposition, entanglement, superdense coding)
(week 3) (Irreversibility of superoperators, quantum channels & master equation, Shannon's theory, Holevo bound on accessible information, Schmacher's quantum data compression)
(week 4) (Universal gates for quantum computation, Quantum Fourier Transform)
(week 5) (Phase estimation & Shor's algorithm for factoring)
(week 6) (Grover's algorithm, Complexity Classes)
(week 7) (One-way quantum computer)
(week 8) (Adiabatic quantum computation)
(week 9-10) (Quantum error correction and fault-tolerant quantum computation)
(week 11) (Topological quantum computation, quantum Hall effect, anyons, Braid group)
(week 12) (Cryptography and quantum key distribution, quantum simulations, physical implementations: Josephson junctions, cold atoms, trapped ions, photons, etc.)
(week 13) (Tensor network methods)
(week 14) (Student presentation)

Topics covered previously in Spring 2012: There will be update and changes in this year's course and we may not follow exactly what we did there.
Lecture 26 Physical implementations
Lecture 25 Quantum Error Correction
Lecture 24 Braid group and Topological Quantum Computation
Lecture 23 Topological Phase and Kitaev Toric Code Model
Lecture 22 Grover's algorithm; Quantum Hall Effect, Anyons
Lecture 21 Complexity Classes and Grover's algorithm (may add discussion on complexity QMA [quantum-Merlin-Arthur] this time)
Lecture 20 Classical Complexity Classes
Lecture 19 Cryptography and RSA
Lecture 18 One-way quantum computer
Lecture 17 Phase estimation and Shor's factoring algorithm
Lecture 16 Quantum Fourier Transform (may add semiclassical implementation of QFT this time)
Lecture 15 Universal gates (may add discussion on Hadamard and Toffoli being universal this time)
Lecture 14 Quantum circuit
Lecture 13 Holevo bound on accessible information
Lecture 11 and 12 Thermodynamic interpretation of quantum error correcting criterion: arXiv: quant-ph/0202054
Lecture 10 Shannon's theory
Lecture 9 Entanglement measures
Lecture 8 Entanglement entropy in physical models
Lecture 7 Irreversiblity of Superoperators, quantum channels & master equation
Lecture 6 Schmidt decomposition and superoperators
Lecture 5 Distinguish nonorthogonal states and POVM (may add the connection to trace distance this time)
Lecture 4 Postulates of QM and POVM
Lecture 2& 3 Qubits, density matrices, gates and superdense coding, Quantum teleportation, simple quantum algorithms
Lecture 1 Overview
Return to top

Incomplete list of addtional reading:
Microsoft Makes Bet Quantum Computing Is Next Breakthrough by John Markoff, The New York Times, June 23, 2014
The Quantum Quest for a Revolutionary Computer by Lev Grossman, Time Magazine
NOBEL 2012 Physics: Manipulating individual quantum systems
"Quantum Computing Promises New Insights, Not Just Supermachines" by Scott Aaronson (Professor of Computer Science at MIT) in New York Times
"Quantum Entanglement: A Modern Perspective" by Barbara M. Terhal, Michael M. Wolf and Andrew C. Doherty, Physics Today v56, p46 (2003)
"Recent Progress in Quantum Algorithms" by Dave Bacon and Wim van Dam, Communications of the ACM, Vol. 53, Pp. 84-93(2010)
Scott Aaronson's Complexity Zoo
Stephen Jordan's Quantum Algorithm Zoo
Problems in Quantum Information
Michael Nielsen's YouTube video courses: quantum computing for the determined
"Why Now is the Right Time to Study Quantum Computing" by Aram Harrow, The ACM Magazine for Students - The Legacy of Alan Turing: Pushing the Boundaries of Computation archive Volume 18 Issue 3, Spring 2012 Pages 32-37
"The First Quantum Machine" (Breaktrhough of the year 2010), Adrian Cho, Science vol. 330, p. 1604 (2010)
"Silicon Quantum Computer a Possibility" by E.S. Reich, Nature News (2011) doi:10.1038/news.2011.29
"Quantum Entanglement Links 2 Diamonds" by John Matson, Scientific American, Dec. 1, 2011
"Moving Beyond Trust in Quantum Computing" by Vlatko Vedral, Science Vol.335, pp.294-295 (2012).
"Quantum Computers" by Ladd, Jelezko, Laflamme, Nakamura, Monroe & O'Brien, Nature 464, 45-53 (2010)
"Entangled states of trapped atomic ions" by Rainer Blatt & David Wineland, Nature 453, 1008-1015 (2010)
"Engineered two-dimensional Ising interactions in a trapped-ion quantum simulator with hundreds of spins" by Joseph W. Britton, Brian C. Sawyer, Adam C. Keith, C.-C. Joseph Wang, James K. Freericks, Hermann Uys, Michael J. Biercuk & John J. Bollinger, Nature 484, 489-492 (2012).
"Quantum coherence and entanglement with ultracold atoms in optical lattices" by Immanuel Bloch, Nature 453, 1016-1022 (2010)
"The quantum internet" by H. J. Kimble, Nature 453, 1023-1030 (2010)
"Superconducting quantum bits" by John Clarke & Frank K. Wilhelm, Nature 453, 1031-1042 (2008)
"Coherent manipulation of single spins in semiconductors" by Ronald Hanson & David D. Awschalom, Nature 453, 1043-1049 (2008)
"Physics: Quantum Computing" by E. Knill, Nature 463, 441-443 (2010)
"Quantifying entanglement in macroscopic systems" by Vlatko Vedral, Nature 453, 1004-1007 (2010)

Return to top

Announcement, Update and Additional Information

-May 1, Professor Korepin discussed Topological Quantum Computation today. I took notes here.

-April 29, Today I introduced Shor's 9-qubit code and proved Th10.1 and Th10.2 in Nielsen and Chuang. I concluded the discussions on QEC with fault tolerance and threshold theorem. The notes were in the last set.

-April 24, Today I finished discussions on one-way quantum computer and started quantum error correction. Notes for QEC are here.

-April 22, I finished Shor's algorithm today and discussed the basics of one-way quantum computer. Notes are here.

-April 17, I discussed quantum Fourier transform and phase estimation. Next time I will finish Shor's factoring algorithm. Notes are here.

-April 15, Prof. Korepin discussed Grover's search algorithm today, including its adiabatic version. I took notes here.
Student presentation will be on May 6th and May 8th.

-April 10, Homework 2 was distributed in class. I finished the proof the {H,T} is universal for one-qubit gates. The proof is different from that presented in Nielsen and Chuang, but explictly constructed rotation around two orthogonal axes. The notes are contained in the last set here. Prof. Korepin then continued with the Solovay-Kitaev theorem and Grover's search algorithm. I took notes here.

-April 8, I discussed universal gates and described proof of them. I finished showing arbitrary one-qubit gates plus two-qubit CNOT are universal. I will continue showing the discrete case next time. The notes are here.

FYI, there are some corrections to Nielsen and Chuang, see their errata here. Those that are relevant here are pp 195-196 and pp 176 (use search when you are at their webpage).

-April 3, Prof Korepin finished proof of Holevo bound. Unfortunately, my windows journal broke and the notes were not saved. Please refer to Lecture 13 notes of Spring 2012. I started discussing quantum circuits and universal gates.

-April 1, Discussion of midterm exam problems and continuation of quantum information (Holevo bound on accessible information). Notes are here.

-March 27, Midterm exam.

-March 25, I reviewed materials that will be covered in the midterm. The notes are here.
Midterm (closed book) is 8:30-9:50am on March 27.
After midterm, we will start discussing universal gates and quantum algorithms (Shor's and Grover's).

-March 13, Professor Korepin discussed Schumacher compression, and how the typical subspace ideas can be used in quantum statistical mechanics. He also started some discussions on Holevo information. I took down notes here.

There will be a midterm (closed book) on March 27. We will have a review session on March 25.

-March 11, Professor Korepin discussed classical information theory (Shannon) and some properties of entropy. I took down notes here.

-March 4 & 6, Professor Korepin discussed physical models. I was away, so no notes were available.

-Feb. 27, Today Professor Korepin discussed entanglement entropy, Renyi entropy/Tsallis entropy, etc for ground states of various 1D models. It was seen that for models with gapless excitations, entropy of subsystem scales logarithmically with the subsystem size. I took down notes here.

-Feb. 25, Today I discussed a few aspects of entanglement: (1) relation to violation of Bell-inequality; (2) entanglement of distillation/concentration; (3) entanglement cost/entanglement of formation; (4) majorization. Lecture notes can be found here.

-Feb. 20, Today Prof. Korepin continued discussions on superoperators, gave three example channels: depolarizing, phase damping and amplitude damping ones. I took down notes here.

-Feb. 18 Today Prof. Korepin finished Bell-inequality. He then discussed superoperators and their Krauss decompositions. In particular he showed invertible superoperators are unitary. I took down notes here.

Homework 1 was distributed today and due Feb. 27 in class.

-Feb. 13 (Morning) Class is cancelled due to snow storm.

-Feb. 11 Today I discussed Schmidt decomposition, partial trace, entanglement entropy, partial transpose and PPT criterion for detecting entanglement. The lecture notes were already included in last lecture notes here. Prof. Korepin started discussion on Bell's inequality, which I took notes of.

-Feb. 6 I discussed no cloning, discrimination of non-orthogonal states, density matrices and non-uniqueness of their decompositions.
Lecture notes (including material for next lecture) can be downloaded here.

-Feb. 4 Today I started from the very beginning of Quantum Mechanics, discussing the postulates and how they are placed in the context of quantum information. I also discussed the interaction-free measurement invented by Vaidman.
Lecture notes can be downloaded here.

-Jan. 30 Prof. Korepin continued the overview and discussed Quantum Teleportation, Deutsch algorithm and Deutsch-Jozsa algorithm. I took notes and they can be downloaded here (restricted access to registered students).

-Jan. 28 Prof. Korepin gave an overview of many different selected topics. 1. Landauer's principle (it costs work k_B T ln 2 to erase memory), which explains the Maxwell's Demon cannot infinitely convert a uniform system to heat up somewhere and cold down in anohter place. 2. Revserible computation is in principle possible (e.g. using Toffoli gates can recast any classical non-reversible computation reversible) 3. Positive-Operator-Value-Measure (POVM) measurement: measurement needs not be orthogonal. 4. Density matrix: a statistical ensemble of pure states, and how they generally evolve by a superoperator (using operators related to POVM). 5. Entanglement: classically entropy has the property that the entropy of the whole is not less than any of the subsystem entropy; however, in QM, the whole system can have zero entropy while the subsystem has maximal entropy. The weird property of entanglement distinguishes itself from class theory. 6. Undecidable questions: e.g. Is the set of all natural set a natural set itself? Halting problem. 7. Cryptography: classical (including RSA) vs. quantum (BB84). 8. Complexity classes. 9. Turing machine. 10. Quantum teleportation. [Refs. Andrew Steane's paper and Preskill chapter 1]

I found a YouTube video of Richard Feynman Lecture on Computer.

-First meeting of the class will be 8:30-9:50am Tu 28th Jan in Physics Room 123.
Return to top

For your information:

A brief guide to 'Student Success Resources' that are available on our campus:
https://ucolleges.stonybrook.edu/links/academic-success-resources.pdf

Americans with Disabilities Act:
If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Disability Support Services (631) 632-6748. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.

Students requiring emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information, go to the following web site http://studentaffairs.stonybrook.edu/dss/

Academic Integrity:
Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Faculty are required to report any suspected instances of academic dishonesty to the Academic Judiciary. Faculty in the Health Sciences Center (School of Health Technology & Management, Nursing, Social Welfare, Dental Medicine) and School of Medicine are required to follow their school-specific procedures. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/

Critical Incident Management:
Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Judicial Affairs any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Faculty in the HSC Schools and the School of Medicine are required to follow their school-specific procedures.

Electronic Communication:
Email to your University email account is an important way of communicating with you for this course. For most students the email address is ‘firstname.lastname@stonybrook.edu’, and the account can be accessed here: http://www.stonybrook.edu/mycloud. *It is your responsibility to read your email received at this account.*

For instructions about how to verify your University email address see this:
http://it.stonybrook.edu/help/kb/checking-or-changing-your-mail-forwarding-address-in-the-epo . You can set up email forwarding
using instructions here: http://it.stonybrook.edu/help/kb/setting-up-mail-forwarding-in-google-mail . If you choose to forward your University email to another account, we are not responsible for any undeliverable messages.

Religious Observances:
See the policy statement regarding religious holidays at http://www.stonybrook.edu/registrar/forms/RelHolPol%20081612%20cr.pdf Students are expected to notify the course professors by email of their intention to take time out for religious observance. This should be done as soon as possible but definitely before the end of the ‘add/drop’ period. At that time they can discuss with the instructor(s) how they will be able to make up the work covered.

Return to top