# Is fault-tolerant computation easier than we thought?

In this paper, Bravyi and Haah introduce triorthogonal stabilizer codes, which arise from triorthogonal matrices defined as follows.

An $$m \times n$$ binary matrix $$G$$ with rows $$f_1, \dots, f_m$$ is said to be triorthogonal if the Hamming weight of the entry-wise product of any pair or triplet of distinct rows is even. That is, $$\vert f_i \cdot f_j \vert = 0\ \ \ \ \ \ \text{and} \ \ \ \ \ \ \vert f_i \cdot f_j \cdot f_k \vert = 0,$$ for any pair $$(i,j)$$ or any triplet $$(i,j,k)$$ of distinct indices.

From a triorthogonal matrix, one can define a triorthogonal stabilizer code which encodes as many qubits as it has odd weight rows. Given an $$m \times n$$ triorthogonal matrix $$G$$, we can construct a triorthogonal code as follows. Denote by $$G_0$$ the submatrix of $$G$$ consisting of the rows with even weight, and let $$G_1$$ be the submatrix consisting of the remaining rows (of odd weight). As in the definition of a triorthogonal matrix, we will say that vectors $$f$$ and $$g$$ are orthogonal if $$\langle f, g\rangle = 0$$. Let $$G^\perp$$ be the orthogonal complement of $$G$$ in $$\mathbb{F}_2^n$$, in the sense that the rows of $$G^\perp$$ are orthogonal to each of the rows of $$G$$ and that the span of the rows of $$G$$ and $$G^\perp$$ is the full space $$\mathbb{F}_2^n$$.

Now, for each row $$(a_1, a_2, \dots, a_n)$$ of $$G_0$$, add a stabilizer $$X^{a_1}\otimes X^{a_2} \otimes \dots \otimes X^{a_n}$$. Similarly, for each row $$(b_1, b_2, \dots, b_n)$$ of $$G^\perp$$, add a stabilizer $$Z^{b_1}\otimes Z^{b_2} \otimes \dots \otimes Z^{b_n}$$. For instance, the row $$(1,1,0,0,0)$$ of $$G_0$$ induces the stabilizer $$X \otimes X \otimes I \otimes I\otimes I$$, while the row $$(1,1,1,1,1)$$ of $$G^\perp$$ induces $$Z \otimes Z \otimes Z \otimes Z \otimes Z$$.

It can be shown that the above indeed defines a stabilizer code. Now, as proven in this paper, it is possible to transversally implement CCZ on any triorthogonal stabilizer code. It would be desirable to have transversal Hadamard implement logical Hadamard, but the authors claim this is not the case since if it were, one could implement Toffoli and Hadamard transversally, which we know from this paper is universal for quantum computation. But this would contradict the Eastin-Knill theorem which proves that no finite set of gates can be both transversal and universal.

What fails in using transversal Hadamard is that (according to the authors), no triorthogonal code is self-dual, i.e. $$G_0 = G^\perp$$ using the notation above. A simple argument given in the second link proves that if this were the case, transversal Hadamard would be possible.

However, I think I have just found a triorthogonal matrix which is self-dual. Please correct me if I'm wrong, but the matrix

$$G = \left[\begin{array}{rrrrr} 1 & 1 & 1 & 1 & 1\\ 1 & 1 & & &\\ & & 1 & 1 & \end{array}\right]$$ is triorthogonal and the orthogonal complement is exactly the last two (even) rows. Since it has one odd row, the code is non-trivial. So, the derived stabilizer code ought to allow transversal CCZ and transversal Hadamard, contradicting Eastin-Knill.

Where have I gone wrong?

• You might want to correct the example you provide regarding the stabilizers of a triorthogonal code. Note that $Z$ stabilizers are coming from $G^\perp$ not $G_1$. You might have mixed logical $Z$ operators (which come from $G_1$) with $Z$ stabilizers (which come from $G^\perp$). In particular, $G_1$ is never in $G^\perp$ because the rows of $G_1$ have odd weight and hence are not orthogonal to themselves. Commented Apr 24, 2022 at 8:13

The problem is that the code defined by $$G$$ is not error-detecting at all. As is explained bellow, the logical operators of that code are just $$X_5$$ and $$Z_5$$, so it has distance $$1$$ and cannot detect any error. On the other hand, The Eastin-Knill theorem assumes the code is local-error-detecting, so there is no contradiction.
-The code defined by $$G$$: Given the form of $$G_0$$, the $$X$$ stabilizers are $$X_1 X_2$$ and $$X_3 X_4$$. Since the code is self-dual, i.e. $$G_0=G^\perp$$, the $$Z$$ stabilizers are also given by $$G_0$$ and hence are generated by $$Z_1 Z_2$$ and $$Z_3 Z_4$$. The logical operators of the code are constructed from $$G_1$$. Hence the logical $$Z$$ is $$Z_1 Z_2 Z_3 Z_4 Z_5$$ which is equal to $$Z_5$$ upto multiplication by the stabilizers of the code. Similarly, the logical $$X$$ is just $$X_5$$.