Quantum reading group
If you are not on the mailing list, click here.
This semester the quantum reading group will work in parallel with the algorithm toolkit class. The main theme we will explore is the interplay between quantum information, complexity and algorithms and classical algorithmic and optimization techniques. We will pmostly revolve around semi-definite programming techniques, the use of duality, matrix multiplicative weights, etc, although there are other topics of interest listed below.
- February 5th. Falk presents the QIP=QMAM result due to Marriott and Watrous.
- February 12th. Piyush shows QIP=PSPACE, following the recent simplified proof based on the multiplicative weights update algorithm. See also the original paper by Jain, Ji, Upadhyay and Watrous. Notes by Anand.
- February 19th. Zeph gives us an introduction to tensor networks, and use them to show perfect parallel repetition of QIP(3) protocols and to introduce the diamond norm. Relevant bacground can be found in the Kitaev-Watrous paper on QIP, or in Watrous' lecture notes (see lectures 18 and 19). See the comprehensive notes handwritten by Piyush for this lecture.
- February 26th. No meeting due to the theory retreat.
- March 2nd. Nisheeth Vishnoi continues his in-depth talk on "Algorithms vs. Hardness: A New Duality in Computation".
- March 9th. Anand presents Kitaev's lower bound for strong coin flipping. Kitaev's notes (plus a video!) are available on the MSRI website. See also the paper by Gutoski and Watrous for a formal account and generalization. Thomas wrote up some notes for the lecture.
- March 19th. Thomas presents the Gutoski-Watrous proof of Kitaev's lower bound on strong coin flipping. We sum up and compare the various SDPs that have been used to characterize quantum interactive proofs in the litterature. Brief notes.
- March 26th. Spring break.
- April 2nd. Dorit Aharonov talks about the complexity of k-QSAT, and commuting Hamiltonians.
- April 9th. Guoming presents a hierarchy of SDPs computing the value of an entangled game, based on the paper by Doherty, Liang, Toner and Wehner. See also the dual hierarchy by Navascues, Pironio and Acin. Notes by Guoming.
- April 16th. Yi-Kai Liu talks about compressed sensing.
Pointers to some of the papers we plan to read:
- One of the main topics in quantum computation in which semi-definite programming plays an important role is that of interactive proofs.
- Maybe the first such use is due to Kitaev and Watrous, who used a semi-definite programming relaxation to prove that QIP was included in EXP in a very nice paper. This was very recently improved to QIP=PSPACE through a technique based on the multiplicative weights update method. One of the key ingredients which made this possible is the public-coin protocol for QIP due to Marriott and Watrous (arXiv:cs/0506068).
- The diamond norm is a norm on super-operators (quantum admissible maps) which was shown to characterize the maximum acceptance probability of QIP protocols. Two papers offer alternate views on how to compute it, by Ben-Aroya and Ta-Shma arXiv:0902.3397 and Watrous arXiv:0901.4709.
- In the setting of two-prover interactive proofs, where the provers might be sharing entanglement, SDPs have so far only been successfully used to analyze XOR games, in a very nice paper by Cleve, Hoyer, Toner and Watrous (Consequences and Limits of Nonlocal Strategies), and later Unique Games, in a paper by Kempe, Regev and Toner (Unique games with entangled provers are easy).
- For the general multi-player setting, nothing much is known apart from some infinite hierarchies of SDPs whose value convergences to that of the multiprover game: see arXiv:0803.4373 and arXiv:0803.4290 (these two papers present hierarchies dual to each other; the latter is somewhat easier to read but the former is much more rigorous). This last hierarchy is used in a very nice recent result showing how a quantum-mechanical apparatus could be used to produce provably random bits, even in the case where the apparatus is untrusted: see Random Numbers Certified by Bell's Theorem.
- SDPs and duality are key to the approach developped by Kitaev and later Mochon to analyze quantum protocols for coin-flipping. This technique is poorly understood but seems very promising; the paper by Mochon (Quantum weak coin flipping with arbitrarily small bias) is hard but clearly worth reading in depth. The theory of quantum games developped by Gutoski and Watrous could be helpful here.
- On a different note, a quantum reduction was used by Regev to show security of a lattice-based cryptosystem based on the hardness of a variant of the shortest vector problem for quantum algorithms in the paper On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. This construction was recently generalized in "On ideal lattices and learning with
errors over rings" by Lyubashevsky, Peikert, and Regev (should be available soon).
- The paper Quantum algorithm for solving linear systems of equations shows how one can in some cases sample from the (suitably normalized) distribution |x_i|^2, where Ax=b and A,b are known, much more efficiently than is known classically. This result is only mildly interesting in itself, but it could possibly be expanded to show how certain important classical algorithms could be drastically sped up using quantum techniques.
- The papers Interactive Proofs For Quantum Computations and Universal blind quantum computation study a setting in which one tries to verify that someone's claim of having built a quantum computer is true, without being able to look directly into the computer, and while oneself having very limited quantum capabilities.