IQI Weekly Seminar

Abstract: In order to build a large scale quantum computer, it is essential to be able to correct for errors extremely quickly. This task of decoding requires a classical algorithm to interpret measurement outcomes. I will present a fast decoding algorithm for topological codes to correct for both Pauli errors and erasure. The algorithm has a worst case complexity of  O(nα(n)), where n is the number of physical qubits and  α is the inverse of Ackermnn's function, which is very slowly growing. I will discuss the implications of this almost-linear time decoding for the feasibility of building a fault tolerant quantum computer.