UC Riverside

Quantum decoherence and errors represent some of the major challenges arising in quantum computations. Quantum error correcting codes protect quantum states against these errors and make quantum computing more reliable. One of the main problems of quantum error correction is the design of feasible decoding algorithms that can simplify error-correction for general quantum codes. The dissertation addresses decoding of general Codeword Stabilized (CWS) codes. This class of quantum codes also includes some other important classes such as additive Stabilizer codes and non-additive Union Stabilizer (USt) codes.

We first design a generic error-correcting algorithm for CWS codes and analyze the number of decoding measurements and quantum gates. This algorithm performs exhaustive screening of different error patterns, similar to decoding of classical non-linear codes. For an n-qubit quantum code correcting up to t erroneous qubits, this brute-force approach consecutively tests all correctable error patterns and employs a separate n-qubit measurement in each test.

The main result is a new error grouping technique that enables simultaneous testing of large groups of errors in a single measurement. To achieve this reduction, we first proceed with a new error-correction algorithm for the USt codes. Secondly, we design an algorithm that converts generic non-linear CWS codes into the simpler quasi-linear USt codes. Each decoding measurement can then either locate the actual error in a given group of errors or entirely eliminate this group. This technique yields a much simpler algorithm that exponentially reduces the number of measurements about 3^t times in any t-error-correcting CWS code.