Non-additive quantum codes are interesting because they can encode more quantum information than an additive or stabilizer code can while using the same number of physical qubits. There is a long history of these non-additive quantum codes and a general structure has been elusive until recently. There have been advances in the direction of generalization with the "codeword stabilized code" theory in arXiv:0708.1021.

Grassl and Roetteler's contribution is a significant step in the direction of generalizing the theory of non-additive quantum codes. They extend the recent codeword stabilized code theory and provide several original contributions that we detail.

Contributions

1) The codeword stabilized code theory takes one stabilizer state (the simultaneous +1 eigenstate of a full stabilizer with n generators) and applies Pauli operators to the basic state to generate logical codewords. Grassl and Roetteler's "union stabilizer code" theory takes a quantum subspace (the simultaneous +1 eigenspace of a stabilizer with n-k generators) and applies Pauli operators to find translated subspaces. The union stabilizer code is then the union of the different orthogonal subspaces. Grassl and Roetteler also show how the quantum codes are related to classical codes over GF(4) to give an intuitive picture for those familiar with classical coding theory. We can see from the above argument that the codeword stabilized code theory is a special case of the union stabilizer code theory.

Grassl and Roetteler then detail the error-correcting properties of their union stabilizer codes with a few theorems. They show how to represent a union stabilizer code in terms of the generators for the seed stabilizer code, the logical operators for the seed code, and the translation operators that translate the basic stabilizer code subspace. This decomposition is useful for those familiar with the basic stabilizer formalism.

The idea of a union stabilizer code actually goes back over ten years to one of Grassl's earlier notes on non-additive codes that is available only on the arXiv (arXiv:quant-ph/9703016v1). He didn't detail a stabilizer theory in the earlier paper so the current union stabilizer theory is useful.

The advantage of the union stabilizer coding technique is that it makes the search for good non-additive codes much simpler because it reduces the complexity of the search. Grassl cites a specific example of the search speedup on slide 16 from his presentation at the First International Conference on Quantum Error Correction (not shown or detailed in the paper):

http://qserver.usc.edu/qec07/QEC07/MarkusGrassl.pdf

He compared the search for a ((10, 20, 3)) using the codeword stabilized code technique and the union stablizer code technique. (A ((10, 20, 3)) is a quantum code that encodes a subspace of 20 dimensions or qubits using 10 physical qubits while correcting an arbitrary single-qubit error.) This search problem is equivalent to the problem of finding a maximal clique in a graph and is known to be an NP-hard problem though the search complexity should be reasonable for small codes. The result of the search is that the codeword stabilized search took 1030 seconds to find the code while the union stabilizer technique took an astonishing 1 second. So the union stabilizer technique is quite useful in finding good non-additive quantum codes.

2) Grassl and Roetteler then give a construction for CSS-like union stabilizer codes and show how Steane's construction from arXiv:quant-ph/9802061 is a special case of a union stabilizer code.

3) One of the more interesting contributions of this work is the construction of non-additive quantum codes from classical nonlinear Goethals and Preparata codes. The practical advantage of this construction is that it obviates the need for the NP-hard search problem detailed above. It is then straightforward to develop quantum codes of higher dimension with distance 8 or 6 from these two classes of nonlinear classical codes. They give a table that these codes and compares them against a previous construction by Steane.

4) The last contribution of the paper is perhaps the most significant in my opinion. They give an explicit algorithm that shows how to compute an encoding circuit for an arbitrary non-additive quantum code. The codeword stabilized code paper (arXiv:0708.1021) gives a theorem concerning encoding circuits for their codes that is similar to Grassl and Roetteler's algorithm, but they do not explicitly show the algorithm for an example.

Grassl break the problem into two steps. The first step finds the quantum encoding circuit for the basic stabilizer subspace. This first step is well known and there are several ways of doing it, but perhaps the best way is from page 13 of an earlier paper of Grassl et al. available at arXiv:quant-ph/0211014. The second step uses a breadth-first search to find the minimal realization of a classical circuit using , CNOT, and Toffoli gates.

Criticisms

It would be nice to see the explicit algorithm for computing the classical circuit corresponding to a non-additive code.
Grassl and Roetteler merely state that it is a breadth-first search and don't show any steps.

The authors also need to say that the most significant bit of the generators in (6) corresponds to the top-most bit of the classical circuit in Figure 4 and the least significant bit corresponds to the bottom-most bit in the figure.

It would also be nice to see a bound on the complexity of the classical circuit.

Looking at Figure 4 one can see that the input state for this code can only take on 6 states of the full eight-dimensional subspace. So the tradeoff is that you can use only certain states within the space of the input qubits so that you can have a gain in information space. It may not be natural in some physical systems to impose this encoding but I guess we would need further commentary from an experimentalist. This problem seems to be persistent with non-additive quantum codes.

The other problem with a non-additive code in general is a way to perform efficient measurements to project the encoded qubits and determine the error syndrome. The stabilizer formalism does this elegantly by just measuring each of the stabilizer generators. It would be interesting if there was a non-additive code that had a straightforward way to perform measurements for diagnosing the error.

Suggestions for Future Work

Future work may include searching for different classes of nonlinear classical codes that we could import for use as a non-additive quantum code.