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 icon.
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.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 | solutions | Bit commitment and metrics on states |
Problem set 2 | Tues, Sep 24 | solutions | Gentle measurement and types |
Problem set 3 | Tues, Oct 1 | solutions | Relative entropy, Gibbs distributions, and compression |
Problem set 4 | Tues, Oct 8 | solutions | Mutual information and capacity |
Problem set 5 | Wed, Oct 16 | solutions | Entanglement-assisted capacity and Fisher information |
Problem set 6 | Tues, Oct 22 | solutions | Pinsker and more entanglement-assisted capacities |
Problem set 7 | Tues, Oct 29 | solutions | SWAP test, tomography and MMWU |
Problem set 8 | Tues, Nov 5 | solutions | data hiding, symmetry and monogamy |
Project Proposal | Tues, Nov 12 | ||
Problem set 9 | Tues, Nov 19 | Random vectors and spectrum estimation | |
Problem set 10 | Tues, Dec 3 | ||
Project Presentation | Mon, Dec 9 (11:59pm) | ||
Project Paper | Wed, Dec 11 (11:59pm) |
All scribed lectures together in one file
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].
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.
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.
Sep 17, 2024: quantum entropy and compression.
(tablet notes, scribed notes)
Review material: Chap 11 of [Wilde]
Related reading: algorithmic cooling on wikipedia.
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.
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).
Sep 26, 2024: Noisy channel coding
(tablet notes, scribed notes)
Review material: Chapters 2, 16 and 20 of [Wilde]
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
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.
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.
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.
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
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.
Oct 24, 2024: k-designs, nets and concentration
(tablet notes, scribed notes)
Oct 29, 2024: random unitaries, k-designs, randomizing maps
(tablet notes, scribed notes)
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.
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)
Nov 7, 2024: Algorithms for semidefinite programming.
(tablet 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
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.
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
Nov 19, 2024: monogamy and de Finetti.
(tablet notes)
de Finetti theorem
(original version).
de Finetti reduction (and a generalization).
Nov 21, 2024:
Nov 26, 2024:
Dec 3, 2024:
Dec 5, 2024:
Dec 10, 2024: Student presentations