Speaker
Description
A central problem in quantum error correction is to develop good codes. This problem is often reduced to maximizing the number of logical qubits $k$, and the distance $d$ relative to the number of physical qubits used $n$. Bravyi-Terhal, and Bravyi-Poulin-Terhal developed techniques showing that good codes cannot be locally embedded in a low dimensional Euclidean space.
In this work, we use similar techniques to generalize their results to graph invariants of the factor graph. More generally we hope to draw attention on the potential applications of the tools developed in combinatorial geometry.
We prove for quantum LDPCs that $d$ is bounded by the treewidth of the factor graph. As a consequence we recover Bravyi-Terhal, and we obtain bounds on codes locally embedded in $D$-dimensional hyperbolic space $\mathbb{H}^D$. Namely we find $d \in O(log(n))$ for codes in $\mathbb{H}^2$ and $d \in n^{(D-2)/(D-1)}$ for codes in $\mathbb{H}^{D \geq 3}$.
Further, using graph separators, we prove tradeoffs between $k$ and $d$, notably $k \frac{d^2}{log(d)^2} \in O(n)$ for codes in $\mathbb{H}^2$ and $k d^{1/(D-1)}\in O(n)$ for codes in $\mathbb{H}^{D \geq 3}$.
Aside from these specific bounds, this work has experimental implications. The ability of a quantum computer to implement a good code is closely related to its ability to achieve complex couplings between qubits.