MIT 8.372 - Quantum Information Science 3

Fall 2024

Lecture: TR2:30-4, Room 3-370

Instructor: Aram W Harrow
Office hours: Thursday 1:30-2:30pm and Friday 2-3pm, Room 6-318

TA: Yuanjie (Collin) Ren
Office hours: Monday 3-5pm, Room 4-251

This is a third class in the MIT QIS sequence, following 8.370 and 8.371. It ran before in Fall 2020 [as 8.S372/18.S996] and in Fall 2022.

Psets and lecture notes will be made public. Registered students (including listeners) can access the canvas site and Piazza discussion boards. Any content only for registered students (such as pset solutions) will be labeled by the MIT icon.

Syllabus

This is a third course in quantum information and computing theory, focused on special topics that may change from year to year. This year the focus is on quantum information theory, both understanding the core theory of the field, as well as application to physics.

The first part of the course will introduce the main questions and tools of quantum information theory, such as entropies, capacities, hypothesis testing, decoupling, random states and unitaries, symmetry, and entanglement. The second part will apply these tools, along with those from quantum complexity theory and error correction, to questions in many-body physics.

The grade will be 50% homework, 10% scribing, 30% final paper and 10% presentation.

Assignments

Problem sets are due by 9pm on Tuesdays. Click on the due date to upload your completed homework.

Assignment Due Date Solutions Topic
Problem set 1 Tues, Sep 17 solutionsMIT Bit commitment and metrics on states
Problem set 2 Tues, Sep 24 solutionsMIT Gentle measurement and types
Problem set 3 Tues, Oct 1 solutionsMIT Relative entropy, Gibbs distributions, and compression
Problem set 4 Tues, Oct 8 solutionsMIT Mutual information and capacity
Problem set 5 Wed, Oct 16 solutionsMIT Entanglement-assisted capacity and Fisher information
Problem set 6 Tues, Oct 22 solutionsMIT Pinsker and more entanglement-assisted capacities
Problem set 7 Tues, Oct 29 solutionsMIT SWAP test, tomography and MMWU
Problem set 8 Tues, Nov 5 solutionsMIT data hiding, symmetry and monogamy
Project Proposal Tues, Nov 12
Problem set 9 Tues, Nov 19 solutions/td> Random vectors and spectrum estimation
Problem set 10 Tues, Dec 3 solutions/td> Recovery maps and area laws
Project Presentation Mon, Dec 9 (11:59pm)
Project Paper Wed, Dec 11 (11:59pm)
Late policy: You can turn in two assignments up to three days late each for any reason. These no-questions-asked late days are meant for things under your control, like other work taking higher priority. For things out of your control like illness, family emergency, etc. then talk to us (plus SSS if you're an undergrad) and this won't count against your two free extensions. This policy is only for the homeworks, not the project. For the project, extensions are only possible due to circumstances like illness, and may result in a grade of I given how close the end of term is to the grading deadline. This being said, the deadlines are meant to keep you on track and not to make your life difficult, so don't hesitate to reach out if you're having trouble.

Lectures

All scribed lectures together in one file

  1. Sep 5, 2024: introduction, purifications, bit commitment (tablet notes, scribed notes)
    Review material: 8.371 lectures on density matrices, quantum operations
    Related reading: Chap 5 of [Wilde].

  2. Sep 10, 2024: trace distance, fidelity, metrics (tablet notes, scribed notes)
    Review material: Chap 9 of [Wilde], Section 3.2 of [Wat]
    Related reading: early review of the bit-commitment no-go paper.

  3. Sep 12, 2024: classical information theory: entropy, compression and channel coding (scribed notes)
    Review material: Chap 10 of [Wilde]
    Related reading: C. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, 1948. Shannon, The Bandwagon, IRE Transactions on Information Theory, 1956.

  4. Sep 17, 2024: quantum entropy and compression. (tablet notes, scribed notes)
    Review material: Chap 11 of [Wilde]
    Related reading: algorithmic cooling on wikipedia.

  5. Sep 19, 2024: relative entropy (tablet notes, scribed notes)
    Review material: Chaps 10 and 11 of [Wilde]
    Related reading: Robin Blume-Kohout, Patrick Hayden. Accurate quantum state estimation via "Keeping the experimentalist honest", arXiv:quant-ph/0603116, 2006. Masanori Ohya, Dénes Petz. Quantum Entropy and Its Use, 1993.

  6. Sep 24, 2024: quantum relative entropy (tablet notes, scribed notes)
    Proof presented in class: Igor Bjelakovic, Rainer Siegmund-Schultze, Quantum Stein's lemma revisited, inequalities for quantum entropies, and a concavity theorem of Lieb, quant-ph/0307170, 2012.
    Original proof: Fumio Hiai, Dénes Petz. The proper formula for relative entropy and its asymptotics in quantum probability. Comm. Math. Phys. 143(1): 99-114 (1991). Tomohiro Ogawa, Hiroshi Nagaoka. Strong Converse and Stein's Lemma in the Quantum Hypothesis Testing, arXiv:quant-ph/9906090, IEEE Trans. Inf. Th., Vol. 46, No. 7, 2428-2433 (2000).
    Bonus application: Robin Blume-Kohout and Patrick Hayden. Accurate quantum state estimation via “Keeping the experimentalist honest”. arXiv:quant-ph/0603116 (2006).

  7. Sep 26, 2024: Noisy channel coding (tablet notes, scribed notes)
    Review material: Chapters 2, 16 and 20 of [Wilde]

  8. Oct 1, 2024: Classical messages over quantum channels. Fano and Fannes inequality. Conditional mutual information. (tablet notes, scribed notes)
    Review material: Chapters 16 and 20 of [Wilde]
    Related reading: Tomohiro Ogawa, Hiroshi Nagaoka; A New Proof of the Channel Coding Theorem via Hypothesis Testing in Quantum Information Theory. arXiv:quant-ph/0208139, IEEE Trans. Inf. Th. 2002. Jingliang Gao. Quantum union bounds for sequential projective measurements. Phys. Rev. A 92, 052331, 2015, arXiv:1410.5688. Andreas Winter. Coding Theorem and Strong Converse for Quantum Channels. 1409.2536. IEEE Trans. Inf. Th. 1999

  9. Oct 3, 2024: HSW converse and application to random-access coding (tablet notes, scribed notes)
    Related reading: Ashwin Nayak. Optimal lower bounds for quantum automata and random access codes. quant-ph/9904093. FOCS 1999.

  10. Oct 8, 2024: state learning and tomography (tablet notes, scribed notes)
    Related reading: Scott Aaronson. The Learnability of Quantum States. quant-ph/0608142. Proc. Roc. Soc. A. 2007. Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, Nengkun Yu. Sample-optimal tomography of quantum states. 1508.01797. STOC 2016 and IEEE Trans. Inf. Th. 2017.

  11. Oct 10, 2024: quantum sensing and Fisher information (tablet notes, scribed notes)
    Review article: Jasminder S. Sidhu, Pieter Kok. A Geometric Perspective on Quantum Parameter Estimation. arXiv:1907.06628, AVS Quantum Sci. 2, 014701 (2020).
    Connection to fidelity: Sisi Zhou, Liang Jiang. An exact correspondence between the quantum Fisher information and the Bures metric. arXiv:1910.08473.

  12. Oct 17, 2024: Randomness and concentration of measure (scribed notes)
    Related reading: 18.S997 High-dimensional statistics. Chapter 1: Sub-Gaussian Random Variables. Spring 2015 OCW notes. A. W. Harrow, The Church of the Symmetric Subspace, arXiv:1308.6595

  13. Oct 22, 2024: Renyi entropy, anticoncentration and entanglement of random states (tablet notes, scribed notes)
    Related reading: Don N. Page. Average Entropy of a Subsystem. Phys.Rev.Lett.71:1291-1294,1993.

  14. Oct 24, 2024: k-designs, nets and concentration (tablet notes, scribed notes)

  15. Oct 29, 2024: random unitaries, k-designs, randomizing maps (tablet notes, scribed notes)

  16. Oct 31, 2024: representation theory, quantum Fourier transform (tablet notes, scribed notes)
    Review material: Felix Leditzsky notes on representation theory in quantum information.
    Related reading: Robert Beals. Quantum computation of Fourier transforms over symmetric groups. STOC 1997. Cristopher Moore, Daniel Rockmore, Alexander Russell. Generic Quantum Fourier Transforms. arXiv:quant-ph/0304064.

  17. Nov 5, 2024: Schur-Weyl duality (tablet notes, scribed notes)
    Review material: Chapter 5 of the dissertation of A. W. Harrow [quant-ph/0512255], Chapter 1 of the dissertation of M. Christandl quant-ph/0604183.
    Related reading: Roe Goodman, Nolan R. Wallach. Symmetry, Representations, and Invariants, Graduate Texts in Mathematics vol 255, 2009. (pdf available using MIT libraries)

  18. Nov 7, 2024: Algorithms for semidefinite programming. (tablet notes, scribed notes)
    Related reading: Fernando G.S L. Brandão, Richard Kueng, and Daniel Stilck França. Faster quantum and classical SDP approximations for quadratic binary optimization Quantum 6, 625 (2022). Richard Kueng Simons talk.
    Review material. Stephen Boyd and Lieven Vandenberghe Convex Optimization. Cambridge University Press. 2004

  19. Nov 12, 2024: merging (tablet notes)
    Related reading: Merging from decoupling: Anura Abeyesinghe, Igor Devetak, Patrick Hayden, Andreas Winter. The mother of all protocols: Restructuring quantum information's family tree. arXiv:quant-ph/0606225, Proc. R. Soc. A. 2009.
    Merging: I. Turner. Scientist knows less than nothing, Bristol Evening Post, Aug 5, 2005. Informal version: Michal Horodecki, Jonathan Oppenheim, Andreas Winter. Quantum information can be negative. arXiv:quant-ph/0505062 Nature 2005.
    Formal version: Michal Horodecki, Jonathan Oppenheim, Andreas Winter. Quantum state merging and negative information. arXiv:quant-ph/0512247. Comm. Math. Phys. 2007.

  20. Nov 14, 2024: Black holes as mirrors. Quantum capacity. (tablet notes)
    Related reading: Patrick Hayden, John Preskill. Black holes as mirrors: quantum information in random subsystems. arXiv:0708.4025 Don N. Page. Information in Black Hole Radiation. hep-th/9306083. Joel Tropp. User-friendly tail bounds for sums of random matrices. 1004.4389. Daniel Harlow. Jerusalem Lectures on Black Holes and Quantum Information. 1409.1231. Patrick Hayden, Michal Horodecki, Andreas Winter, Jon Yard. A decoupling approach to the quantum capacity. quant-ph/0702005

  21. Nov 19, 2024: monogamy and de Finetti. (tablet notes, scribe notes)
    de Finetti theorem (original version, Watrous notes). de Finetti reduction (and a generalization).

  22. Nov 21, 2024: monogamy, CMI, recovery maps (tablet notes)
    Related reading: Chap 12 of [Wilde]. Patrick Hayden, Richard Jozsa, Denes Petz, Andreas Winter. Structure of states which satisfy strong subadditivity of quantum entropy with equality quant-ph/0304007, CMP 2004. Fernando G. S. L. Brandao, Aram W. Harrow, Jonathan Oppenheim, Sergii Strelchuk. Quantum Conditional Mutual Information, Reconstructed States, and State Redistribution. 1411.4921, PRL 2015. Omar Fawzi, Renato Renner. Quantum conditional mutual information and approximate Markov chains. 1410.0664, CMP 2015. Fernando G. S. L. Brandao, Aram W. Harrow. Quantum de Finetti Theorems under Local Measurements with Applications. 1210.6367, CMP 2016.

  23. Nov 26, 2024: Lieb-Robinson bounds (tablet notes)
    Related reading: M. B. Hastings. Locality in Quantum Systems. lecture notes from Les Houches summer school. 1008.5137. Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low. Quantum algorithm for simulating real time evolution of lattice Hamiltonians 1801.03922, FOCS 2018. Chi-Fang Chen, Andrew Lucas, Chao Yin. Speed limits and locality in many-body quantum dynamics 2303.07386, Rep. Prog. Phys. 2023.

  24. Dec 3, 2024: Correlation decay (tablet notes)

  25. Dec 5, 2024: Matrix product states and areas laws (tablet notes)
    Related reading: D. Perez-Garcia, F. Verstraete, M. M. Wolf, J. I. Cirac. Matrix Product State Representations arXiv:quant-ph/0608197. J. Eisert, M. Cramer, M.B. Plenio. Area laws for the entanglement entropy - a review. 0808.3773, RMP 2010. Itai Arad, Alexei Kitaev, Zeph Landau, Umesh Vazirani. An area law and sub-exponential algorithm for 1D systems. arXiv:1301.1162. Anurag Anshu, Itai Arad, David Gosset. An area law for 2D frustration-free spin systems arXiv:2103.02492.

  26. Dec 10, 2024: Student presentations

References