Hi all,
next Monday Kai Ott will present his master thesis at IBM entitled “Decision-tree decoders for general quantum LDPC codes”. The talk will take place at 16:00 in HIT E41.1 and on zoom https://ethz.zoom.us/j/362994444, see below for the abstract.
Best, Ladina
****
Title: Decision-tree decoders for general quantum LDPC codes
Abstract: As diverse approaches to fault-tolerant quantum computing rapidly evolve, flexible decoders for a wide range of settings are becoming increasingly desirable. We introduce Decision Tree Decoders (DTDs), a new class of decoding algorithms for general quantum low-density parity-check (qLDPC) codes that require only sparsity of the binary check matrix. DTDs construct corrections incrementally by adding faults one-by-one, forming a path through a Decision Tree (DT). Each DTD algorithm is defined by its strategy for exploring the tree, with well-designed algorithms typically needing to explore only a small portion before finding a correction. We propose two explicit DTD algorithms for general qLDPC codes: (1) A provable decoder: Guaranteed to find a minimum-weight correction. While it can be slow in the worst case, numerical results show surprisingly fast median-case runtime, exploring only w DT nodes to find a correction for weight-w errors in notable qLDPC codes, such as bivariate bicycle and color codes. This decoder may be valuable for ensemble decoding and determining provable code distances. The tools underpinning this decoder can also be repurposed to compute all minimum-weight logical operators of a code. (2) A heuristic decoder: Achieves higher accuracy and faster performance than BP-OSD on the gross code with circuit noise in realistic parameter regimes.