Hi all,

My apologies if you receive this email twice.  I will be defending my thesis in LISE 303 (at Harvard) on April 25th at 10 am.  Refreshments will be provided.  The talk will be roughly half material Ive talked about at group meetings/seminars and half some new results concerning the construction of unitary 2 designs. 

Abstract
The existence of quantum locally generated codes is a long standing open problem in quantum information theory. In this thesis, we consider a bound concerning this conjecture as well as a few constructions with codes that are 'barely non-local'. First we formulate and analyze a bound concerning the possible topologies of locally generated codes. It is well known that quantum codes which can be defined on lattices (geometrically local codes) must have sub-linear distance, and hence must be bad quantum codes. We establish a complementary result to this one, and show quantum codes which are strongly not embeddable into finite dimensional lattices must also have poor distance. Along the way we derive some results concerning "pseudorandom" classical codes.

Given that quantum codes seem to be difficult to construct, it seems useful to examine "bad" quantum codes for applications in information and communication. Indeed, most of the work in quantum error correction by researchers today is in this direction. We construct a nearly local quantum erasure code which can achieve the capacity of the quantum erasure channel. This code has very poor (adversarial) distance, but still manages to correct random erasure errors with high probability. The codes use random Erdos-Renyi graphs to construct quantum states which are nearly local, but also highly entangled across fixed cuts with high probability. We derive some new results concerning classical codes with log-sparse parity check matrices which may be of independent interest.

Inspired by this construction, we are able to construct new approximate unitary 2-designs or scramblers. The study of scrambling is the study of the mixing properties of different distributions of random unitaries. There is an inherent duality between the study of scrambling and the study of error correction: A good quantum code will make a good scrambler and vice versa. We study the scrambling properties of our random Erdos-Renyi graph state encoding circuits. We are able to show that these circuits, when supplemented by some local Expander Graph quantum circuits, form "weak" approximate unitary 2-designs with O(n log(n)) many gates and depth O(log(n)). This construction, strictly speaking, does not achieve more efficient parameters than existing approximate 2-designs (it matches them), but might have implementation advantages over other designs and points to a conjecture which could yield approximate unitary designs with time independent qubit-to-qubit coupling. This would be a very interesting construction in the context of experimental randomized benchmarking.

Best,
Kevin