Title: Hardness of decoding stabilizer codes

Speaker: Dr. Pavithran Iyer

Abstract: Noise is pervasive in quantum computing, and the framework of quantum error correction guarantees that computation can be done reliably in the presence of noisy components. The stabilizer formalism of quantum error correction prescribes that logical information be encoded in an entangled state of multiple physical qubits that can be expressed as an eigenstate of a commuting set of Pauli operators known as Stabilizers. The task of computing a recovery operation: decoding, can be phrased as a statistical inference problem of identifying the most likely fault conditioned on measuring the stabilizers. A remarkable distinction between quantum error correction and its classical counterpart, binary linear code decoding, lies in the nature of errors. In the quantum setting, distinct errors related to a stabilizer are indistinguishable or degenerate. In simpler terms, the probability of an error is the total probability of all errors that are related by a stabilizer. This intriguing characteristic of degeneracy makes the decoding problem for quantum stabilizers inherently more challenging than the classical decoding problem.

This presentation is based on the research of [1,2], where we demonstrated that the degeneracy feature significantly increases the difficulty of decoding quantum stabilizers when compared to classical decoding. While classical decoding already represents a classic example of an NP-Complete problem, the optimal quantum decoding problem goes beyond that and becomes a #P-Complete problem. A formal proof entails a polynomial time reduction from the #P-Complete problem of computing the weight enumerator of a binary linear code.

Related works: 1. Hardness of decoding quantum stabilizer codes. IEEE Transactions on Information Theory, 619:5209–5223, September 2015.

2. Complexité du dècodage des codes stabilisateurs quantiques. April 2014.