The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decodingResearch Paper
A quantum error-correcting code stores information in a subspace detected by commuting parity checks. A syndrome records which checks report an error. A decoder must turn that information into a recovery operation. Since a quantum computer generates check outcomes throughout its operation, the classical computation required for recovery is part of its…