We promise we’ll finish posting these soon! Day 3 was only a half day of talks with a free afternoon, and the rainy weather of the first two days finally subsided just in time.
Jean-Pierre Tillich
Decoding Quantum LDPC Codes
abstract
LDPC codes are families of sparse codes, meaning that the stabilizers are all low weight, and we usually also require that each qubit partakes in at most a constant number of stabilizers. That is, the parity check matrix is both row and column sparse with constant sparsity per row and column.
The classical versions of these codes are ubiquitous; your cell phone uses LDPC codes, for example. One of the principle advantages of (classical) LDPC codes is that they have good minimum distance, constant rate, and have fast nearly optimal decoders. A new variant called spatially coupled LDPC codes are a universal way (i.e., independent of the channel) to get capacity for most memoryless channels of interest with a low-complexity decoder.
Unfortunately, the quantum case is largely open still, and the speaker admitted in the first moment that he wasn’t going to solve everything during his talk. Leaving aside the question of distance of quantum LDPC codes, one of the reasons why decoding a quantum code is hard is that any error $latex E$ has the same syndrome as $latex ES$ if $latex S$ is in the stabilizer group. This added degeneracy creates an extra freedom that is difficult to account for in a decoder. You want to find the most likely coset, rather than the most likely error.
In a classical LDPC code, the Tanner graph (the bipartite graph whose nodes are bits and checks with edges whenever a collection of bits partake in the same check) is nearly tree-like (it’s an expander) and so message passing algorithms perform nearly at capacity. In the quantum case, the Tanner graph contains many 4-cycles, and message passing decoders get stuck in loops and don’t converge.
Bravyi, Suchara, and Vargo have recently had a breakthrough where they were able to decode a very special quantum LDPC code near the hashing bound: the toric code. But didn’t we already know how to decode the toric code? Yes, of course, there are many good decoders for this code. However, none of them achieve a performance that decodes X and Z errors simultaneously with performance approximately equal to the maximum a posteriori (MAP) decoder.
There are also a new idea, pioneered for polar codes by Renes, Dupuis, and Renner and expanded by Delfosse and Tillich, to use asymmetric codes and decoders. If you are going to decode X first and then Z, why not use a stronger code for X errors, decode them first, and then use the advantage to help you decode the Z after that? Using this idea, you can provably achieve the hashing bound asymptotically.
He concludes with some bright spots: recent global analysis of local decoders (such as the recent work by Hastings on hyperbolic codes), and tricks like entanglement-assisted codes or spatially coupled quantum LDPC codes might lead to capacity achieving decoders soon.
Fernando Pastawski and Beni Yoshida.
Fault-tolerant logical gates in quantum error-correcting codes
abstract arXiv:1408.1720
A great intro: “My paper is at 1408.1720 + PRA…I forgot the full journal reference. You can look it up, which is what people usually do.” Or they just get it from the arxiv!
Fault-tolerant logical gates are central objects in quantum computation. We need them to suppress the spread of errors in computations. Unfortunately, there is a somewhat stringent no-go theorem due to Eastin and Knill that says you cannot have a universal set of transversal gates. (There are various ways around this theorem, such as recent work by Paetznick and Reichard.)
Recently, Bravyi and Koenig have generalized this work. They extend the notion of transversal gate to the idea of a constant-depth circuit and show that constant-depth circuits restrict the allowable gates performable in topological codes to certain levels of the Gottesman-Chuang hierarchy. The main idea of the proof is to use a cleaning lemma. If you can split your code into $latex m+1$ correctable regions, then you can only implement gates in level $latex m$ of the Clifford hierarchy. In particular, $latex D$-dimensional topological codes can be split into $latex D+1$ correctable regions, so we can only implement gates at level $latex D$ in the hierarchy.
What Yoshida and Pastawski have done is show that if you have a code with a loss tolerance threshold $latex p_{\mathrm{loss}} > 1/n$ for some number $latex n$, then any transversal gate must be in $latex P_{n-1}$. If you have a $latex P_n$ logic gate, then $latex p_{\mathrm{loss}} \ge 1/n$.
Another result is that if a stabilizer Hamiltonian in 3-dimensions has a fault-tolerantly implementable non-Clifford gate, then the energy barrier is constant. The proof is simple: we can split the 3-d chunk of code into correctable regions that have string-like shapes, so there must exist a string-like logical operator for these codes, hence the energy barrier is constant. Beautifully simple!
If you have a topological stabilizer code in $latex D$ dimensions with an $latex m$th level logical gate, then the code distance is at most $latex d\le O(L^{D+1-m})$. This improves a bound of Bravyi-Terhal that didn’t take advantage of this $latex m$ factor.
Lastly, we can consider subsystem codes. In $latex D$-dimensions, fault-tolerant gates are in $latex P_D$ (as long as the code distance grows at least logarithmically in the system size).
For the remaining session, it turns out that no Pontiffs were in the audience. However, we had mostly seen these results in other venues or read them before. They are great results, so go read the papers! We hope the trackback to the arxiv is a small compensation to the authors for our failure to blog these interesting talks.
Please let me say that the Quantum Pontiff talk-summaries themselves, and the cross-cutting correlations among the talks, and (hopefully) the Quantum Pontiff comments too all are valuable. For if these things diminish, then
Surely the promises of quantum science are greater than that!
Soberingly, what news from
GondorIBM?