IQIM Postdoctoral and Graduate Student Seminar

Series: IQIM Postdoctoral and Graduate Student Seminar Series

The decoding problem: Computational complexity and practical solutions

Aleksander Kubica, Yale,

Special IQIM Seminar, Thursday, June 4 at 2:30 in 213 Annenberg

Abstract: The decoding problem is a central algorithmic task in fault-tolerant quantum computing, and solving it efficiently is essential for scalability. In this talk, I will discuss the computational complexity of minimum-weight decoding in three quintessential settings: (i) the color code with Pauli Z errors, (ii) the surface code with Pauli X, Y and Z errors, and (iii) the surface code with a transversal CNOT gate, Pauli Z and measurement bit-flip errors. These results show that computational intractability already arises in basic settings for quantum memories and logical circuit implementations. I will then turn to practical solutions and discuss algorithmic fault tolerance for logical circuits with transversal gates.

Based on arXiv:2603.22064, arXiv:2406.17653, and arXiv:2505.13587.

Event Sponsors:

Institute for Quantum Information and Matter (IQIM) - More events from this Sponsor

For more information, please contact Marcia Brown by phone at 626-395-4013 or by email at [email protected].