Some New Constructions and Bounds for Locally Generated Quantum Codes

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'. We establish a complementary result to Bravyi and Terhal, 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 approximate unitary 2-designs. This construction, strictly speaking, does not achieve more efficient parameters than existing approximate 2-designs, 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 an extremely interesting construction in the context of experimental randomized benchmarking.