Boolean Functions, Projection Operators and Quantum Error Correcting Codes

This paper describes a fundamental correspondence between Boolean functions and projection operators in Hilbert space. The correspondence is widely applicable, and it is used in this paper to provide a common mathematical framework for the design of both additive and non-additive quantum error correcting codes. The new framework leads to the construction of a variety of codes including an infinite class of codes that extend the original ((5,6,2)) code found by Rains [21]. It also extends to operator quantum error correcting codes.


I. INTRODUCTION
The additive or stabilizer construction of quantum error correcting codes (QECC) takes a classical binary code that is self-orthogonal with respect to a certain symplectic inner product, and produces a quantum code, with minimum distance determined by the classical code (for more details see [7], [8] and [14]). The first non-additive quantum error-correcting code was constructed by Rains et al. [21]. This code was constructed numerically by building a projection operator with a given weight distribution. Grassl and Beth [13] generalized this construction by introducing union quantum codes, where the codes are formed by taking the sum of subspaces generated by two quantum codes. Roychowdhury and Vatan [23] gave some sufficient conditions for the existence of nonadditive codes, and Arvind et al. [5] developed a theory of non-additive codes based on the Weyl commutation relations. Most recently, Kribs et al. [16] introduced operator quantum error correction (OQEC) which unifies the standard error correction model, the method of decoherence-free subspaces, and that of noiseless subsystems.
We will describe, what we believe to be the first mathematical framework for code design that encompasses both additive and non-additive quantum error correcting codes. It is based on a correspondence between Boolean functions and projection operators in Hilbert space that is described in Sections II and III. We have used an initial version of this correspondence to construct Grassmannian packings [1] and space-time codes for wireless communication [3]. However, the correspondence in Section III applies to a larger class of projection operators and includes the correspondence described in [3] as a special This work was supported in part by AFOSR under contract 00852833. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Nice, France, June 2007. case (see Section IV). We note that prior work by Danielson [11] interpreted Boolean functions as quantum states and developed a correspondence between Boolean functions and zero-dimensional quantum codes.
After introducing the fundamentals of quantum error correcting codes in Section V, we will derive in Section VI sufficient conditions for existence of QECC in terms of existence of certain Boolean function. This paper goes beyond deriving sufficient conditions, and constructs the quantum code if these properties are satisfied. Hence, we convert the problem of finding a quantum code into a problem of finding Boolean function satisfying certain properties. We also see how certain well-known codes fit into this scheme. We focus on nondegenerate codes which is defensible given that we know of no parameters k, M and d for which there exists a ((k, M, d)) degenerate QECC but not a ((k, M, d)) non-degenerate QECC (see [2]). Further, in Section VII, we describe how this scheme fits into a general framework of operator quantum error correcting codes. More precisely, we give sufficient conditions for the existence of ((k, M, N, d)) stabilizer OQEC and also construct the code if these conditions are satisfied.

II. BOOLEAN FUNCTION
A Boolean function is defined as a mapping f : where y j is the value of the Boolean function at the decimal index j and c 0 (j), c 1 (j), .... , c m−1 (j) ∈ {0, 1} are the coordinates in the binary representation for j (with c m−1 as the most significant bit and c 0 as the least significant bit) with v 1 j = v j and v 0 j =v j (Theorem 7.7, [18]).

Example 1:
The truth vector of the three-variable Boolean Definition 2 ( [20]): Let ⊕ denote modulo two addition. The (periodic) autocorrelation function of a Boolean function f (v) at a is the inner product of f with a shift of f by a. More precisely, r(a) = This means that for any element a in the The complementary set links distinguishability in the quantum world (orthogonality of subspaces) with properties of Boolean functions. The quantity f (v ⊕ a) is the counterpart in the quantum world of the quantum subspace after the error has occurred, which is to be orthogonal to the original subspace corresponding to f (v) as will be described in later sections.
If the supports of f (v), f (v⊕a) intersect in N decimal indices then Hence, N = 0 and a ∈ Cset f .

III. BOOLEAN FUNCTIONS AND A LOGIC OF PROJECTION OPERATORS
The authors of [3] connected Boolean logic to projection operators derived from the Heisenberg-Weyl group. In this section, we generalize these results to a larger class of projection operators.
Let B(H) be the set of bounded linear operators on a Hilbert space H. An operator P ∈ B(H) is called a projection operator (sometimes we will use the terms orthogonal projection operator and self-adjoint projection operator) on H iff P = P P † . We denote the set of projection operators on H by P(H) and the set of all subspaces of H by L(H).
It is easy to see that ∨S is the smallest subspace in H containing S. 2) If S ⊆ H, the orthogonal complement of S is defined as S ⊥ = {x ∈ H|x⊥s for all s ∈ S}. 3) If S is a collection of subsets of H, we write ∨ S∈S S = ∨(∪ S∈S S).
Definition 5: Let P ∈ P(H) and let K = image(P ) = {P x|x ∈ H}. We call P the projection of H onto K. Two projections P and Q onto K and L are orthogonal (denoted P ⊥Q) if P Q = 0. It is easy to verify that P Q = 0 ⇔ K⊥L ⇔ QP = 0. (Theorem 5B.9, [10]) Definition 6: Let P, Q ∈ P(H) with K = image(P ) and L = image(Q). Then The structure (P(H), , ⊥) is a logic with unit I H (identity map on H) and zero Z H (zero map on H) (Theorem 5B.18, [10]). This logic is called Projection Logic. Lemma 2 (Theorem 5B.18, [10]): The map P → image(P ) from P(H) to L(H) is a bijection that preserves order, orthogonality, meet(∧) and join(∨).

Lemma 4 ([10]):
If P, Q ∈ P(H), then Lemma 5: If P and Q are commutative operators, then the distributive law holds (and this law fails to hold for noncommutative operators). Also, in this case, Hence, image(P Q) = image(P ∧ Q) and by Lemma 2, P ∧ Q = P Q.

2) We have
where (a) follows from Lemma 3, (b) follows from Lemma 4 and (c) follows directly from definition of P ⊕ Q. 3)P = I − P follows directly from Definition 6.

4) We have
where (d) follows from Lemma 3 since P ⊕ Q and P ∧ Q are orthogonal ((P + Q − 2P Q)P Q = 0), (e) follows from Lemma 4, and (f ), (g) follows from the distributive laws. Hence, P ∨ Q = P + Q − P Q.
Next we define projection functions following [3].

Definition 7:
Given an arbitrary Boolean function f (v 1 , ...., v m ), we define the projection function f (P 1 , ..., P m ) in which v i in the Boolean function is replaced by P i , multiplication in the Boolean logic is replaced by the meet operation in the projection logic, summation in the Boolean logic (or the or function) is replaced by the join operation in the projection logic and the not operation in Boolean logic is replaced by the tilde (P ) operation in the projection logic.
As is standard when writing Boolean functions, we use xor (modulo 2 addition, represented by ⊕) in place of or, hence by above definition, we will replace the xor in the Boolean logic by the xor operation in the projection logic.
Theorem 1: If (P 1 , ..., P m ) are pairwise commutative projection operators of dimension 2 m−1 such that P 1 P 2 ..P m , P 1 P 2 ..P m , ...P 1P2 ..P m are all one-dimensional projection operators and H is of dimension 2 m , then P f = f (P 1 , ....P m ) is an orthogonal projection on a subspace of dimension T r(P f ) = wt(f ), where wt(f ) is the Hamming weight of the Boolean function f .
Proof: By definition of f (P 1 , ....P m ), we have a representation of P f in terms of meet, join and tilde operations in the corresponding projection logic. By Lemma 2, every function of projection operators in terms of meet, join and tilde will be present in the projection logic. Hence, P f is an orthogonal projection operator and this proves the first part of the theorem. Now, we will find the dimension of this projection operator. f as described in Section II.
If wt(f ) = M , then M terms of y i are 1 and the remaining terms are 0. Also, in this case, . We know by the statement of the theorem that the dimension of P c0 , and all these subspaces are orthogonal. Also, the minimum subspace containing all these operators is the whole Hilbert space. So, the dimension of P f will be the sum of dimensions of for all i (which is 1 when y i = 1, and 0 otherwise). Hence, the dimension of P f is M .
Theorem 1 is a generalization of the Theorem 1 of [3] because we consider any pairwise commutative projection operators, while in [3], a special case of commutative projection operators using Heisenberg-Weyl group was used. This special case is described in Section IV. Hence, to prove Theorem 1, we use abstract properties of projection logic [10] rather than the properties of a particular commutative subgroup.

IV. THE CONSTRUCTION OF COMMUTATIVE PROJECTION OPERATORS FROM THE HEISENBERG-WEYL GROUP
Let X, Y , and Z be the Pauli matrices, given by We form the Heisenberg-Weyl group (sometimes in the literature this group is referred to as an extraspecial 2-group or as the Pauli group) E m of order 4 m+1 , which is realized as the group of linear operators αE, α = ±1, ±i. (For a detailed description of the Heisenberg-Weyl group and its use to construct quantum codes see [7], [8].) Next we define the symplectic product of two vectors and the symplectic weight of a vector.

Definition 8:
The symplectic inner product of vectors (a, b), (a ′ , b ′ ) ∈ F 2m q is given by (1) symplectic weight of a vector (a, b) is the number of indices i at which either a i or b i is nonzero.
The center of the group E m is {±I 2 m , ±iI 2 m } and the quotient group E m is isomorphic to the binary vector space F 2m 2 . We associate with binary vectors (a, b) ∈ F 2m 2 operators E (a,b) defined by where Lemma 6: Lemma 7: Thus E (a,b) and E (a ′ ,b ′ ) commute iff (a, b) and (a ′ , b ′ ) are orthogonal with respect to the symplectic inner product (1).
We will now describe how to construct commutative projection operators. Take m linearly independent vectors y 1 , y 2 , ..., y m of length 2m bits with the property that the symplectic product between any pair is equal to zero. If we take P i = 1 2 (I + E yi ), then P 1 , ... P m satisfy all the properties of Theorem 1 and hence, f (P 1 , ...P m ) is an orthogonal projection operator [3].
Take y 1 , y 2 and y 3 as (1, 0, 0, 0, 1, 0) , (0, 1, 1, 1, 1, 0) and (0, 0, 1, 0, 1, 1) respectively which are linearly independent with all pairwise symplectic products equal to zero. Then P f = P 1 ⊕ P 1 P 2 ⊕ P 3 = P 1 + P 3 − 2P 1 P 3 − P 1 P 2 + 2P 1 P 2 P 3 where P i = 1 2 (I + E yi ), that is M )) quantum error correcting code is an Mdimensional subspace of C 2 k . The parameter k is the codelength and the parameter M is the dimension or the size of the code. Let Q be the quantum code, and P be the corresponding orthogonal projection operator on Q. (For a detailed description, see [4].) Definition 10: An error operator E is called detectable iff P EP = c E P , where c E is a constant that depends only on E.
Following [12], we restrict attention to the errors in the Heisenberg-Weyl group. Next, we define the minimum distance of the code.

Definition 11:
The minimum distance of Q is the maximum integer d such that any error E, with symplectic weight at most d − 1, is detectable.
The parameters of the quantum error correcting code are written ((k, M, d)) where the third parameter d is the minimum distance of Q. We say that a ((k, M, d)) quantum error correcting code exists if there exists a ((k, M )) quantum error correcting code with minimum distance ≥ d. We assume d ≥ 2 throughout the paper. We also focus on non-degenerate ((k, M, d)) codes, for which P EP = 0 for all errors E of symplectic weight ≤ d − 1, which is a sufficient condition for existence of the quantum code.
For any quantum code Q, we define the stabilizer H Q as where E k is the Heisenberg-Weyl group defined in Section IV. Then H Q is an abelian group and is isomorphic to GF(2) m , for some m. A quantum code is called additive or a stabilizer code if it is defined by its stabilizer H Q , i.e.
A quantum code is non-additive if it is not equivalent to an additive code [22].

VI. QUANTUM ERROR CORRECTING CODES WITH MINIMUM DISTANCE d
We use * to denote the standard binary inner product. The projection operator corresponding to the QECC is obtained as follows: (i) Construct the matrix A f as above.
(ii) Define k projection operators each of the form 1 2 (I +E y ) where y is a row of the matrix A f , with P k corresponding to the 1 st row, P k−1 corresponding to the 2 nd row and so on, so that P 1 corresponds to the last row. (iii) Transform the Boolean function f into the projection operator P f using Definition 7 where the commutative projection operators P 1 .... P k are determined by the matrix A f . Proof: Consider a Boolean function f (v) satisfying conditions 1) and 2). It follows easily from Section III and IV that P f constructed as above is an M -dimensional projection operator. It remains to prove that the minimum distance is at least d, so we need to show that P f ηP f η = 0 for any error η in E k with symplectic weight at most d − 1.
An error η in E k transforms the projection operator P f to P ′ f = ηP f η, and the condition P f ηP f η = 0 means that P ′ f is orthogonal to P f . Denote by η i the error represented by the binary 2k-tuple with entry 1 in position i and zeros elsewhere. We emphasize that the subscripts i in x i , η i and A j,i ((j, i) th entry in the matrix A f ) are read modulo 2k, so that x 2k+1 is just x 1 .
If A 1,k+1 = 0 then η 1 commutes with P k and η 1 P k η 1 = P k , and if A 1,k+1 = 1 then η 1 P k η 1 =P k . In general, if A k+1−j,k+i = 0 then η i P j η i = P j , and if A k+1−j,k+i = 1 then η i P j η i =P j . Let η i P j η i = Q i,j where Q i,j = P j orP j and observe that Q i,j = P j if and only if entry (k + 1 − j) of x k+i is zero. Then η i P f η i = f (Q i,1 , Q i,2 , ..., Q i,k ) and the entries of x k+i determine η i P f η i . In fact, this correspondence can easily be understood in terms of the fundamental correspondence between between Boolean functions and projection operators, since the operator η i P f η i corresponds to the Boolean function f (v ⊕ x k+i ).
When d = 2, we need to take care of all errors of symplectic weight 1 by showing P f η i P f η i = 0 and P f η i η i+k P f η i η i+k = 0. Applying the fundamental correspondence between Boolean functions and projection operators, this is equivalent to show- This follows from the assumption that x k+i and x k+i ⊕ x i are in the complementary set Cset f ..
In general we need to show that P f ηP f η = 0 for all errors η of symplectic weight at most d − 1. We write η = i∈A η i , apply the fundamental correspondence, and find that P f ηP f η corresponds to the Boolean function f (v ⊕ ( ⊕ i∈A x i+k )). By assumption, ⊕ i∈A x i+k is in the complementary set Cset f , so x i+k )) = 0 for all v, and hence P f ηP f η = 0.
Note that for M ≥ 1 this construction only gives ((k, M, d)) quantum error correcting codes for which the minimum distance d is at most k+3 2 . This is because any k+1 columns of the matrix A f are linearly dependent, which means that there is a 2k bit vector w of symplectic weight at most k+1 2 such that [x 1 , x 2 , ....x 2k ] * w T = 0, and the zero vector is never in Cset f . A ((k, M, d)) additive QECC exists when 1) M = 2 m for some m 2) There are 2k binary k-tuples x 1 , x 2 , ..., x 2k such that

Lemma 8:
Cset have pairwise symplectic product zero and are linearly independent.

Remark 1:
The projection operator corresponding to the QECC is k i=m+1 1 2 (I + E yi ) where y i is k + 1 − i th row of A f . The quantum code obtained in this way is that formed in the stabilizer framework using E y k , E y k−1 , ..., E ym+1 as the stabilizers of the code.
Proof: By Theorem 2 there exists a ((k, M, d))-QECC. The construction method of Theorem 2 gives the corresponding projection operator as P f = k i=m+1 P i = k i=m+1 1 2 (I + E yi ). Any vector in the code subspace is given by |x >= P f |u > for some |u >∈ H. Since E yi and E yj are commutative, we have E yi |x >= |x > for m < i ≤ k. Hence, E y k , E y k−1 , ..., E ym+1 are the stabilizers of the quantum code and the quantum code is additive.
Remark 2: If the boolean function can be represented as a single monomial, it gives an additive code. The converse is not true in general; see for example, [22], where it is shown that every ((4, 4, 2)) code is equivalent to an additive code.
We can also see that the second property is satisfied, so we have constructed a ((2m, 4 m−1 , 2)) QECC that is not additive.
Lemma 9: 1) If there exists a ((k, M, 2)) QECC, then there exists a ((k + 2, 4M, 2)) QECC determined by  (1, 0, x 2k )). All the columns and the sum of columns i and i + k are in Cset f ′ . The symplectic product of any two rows is zero and all the rows are linearly independent, since this was true for A f = (x 1 , x 2 , . . . , x 2k ) 2) Given this choice of f ′ (v), we have Cset f ′ ⊇ Cset f , and this means that the same matrix A f ′ = A f will satisfy all the earlier properties.
Consider the Boolean function f It is a function of 2m+1 variables with weight 3 × 2 2m−3 .
Example 9: The perfect ((5, 2, 3)) additive code of R. Laflamme et al. [17] can be obtained by the above approach. it is easy to see that all rows are linearly independent, and that the symplectic inner product of any two rows is zero. Note that the stabilizers corresponding to the code are ZXXZI, IZXXZ, ZIZXX, and XZIZX.

VII. OPERATOR QUANTUM ERROR CORRECTION (OQEC)
The theory of operator quantum error correction [16] uses the framework of noiseless subsystems to improve the performance of decoding algorithms which might help improve the threshold for fault-tolerant quantum computation. It requires a fixed partition of the systems Hilbert space H = A ⊗ B ⊕ C ⊥ . Information is encoded on the A subsystem; the logical quantum state ρ A ∈ B A is encoded as ρ A ⊗ ρ B ⊕ 0 C ⊥ with an arbitrary ρ B ∈ B B (where B A and B B are the sets of all endomorphisms on subsystems A and B respectively). We say that the error E is correctable on subsystem A (called the logical subsystem) when there exists a physical map R that reverses its action, up to a transformation on the B subsystem (called the Gauge subsystem). In other words, this error correcting procedure may induce some nontrivial action on the B subsystem in the process of restoring information encoded in the A subsystem. This leads to recovery routines which explicitly make use of the subsystem structure [6] [24]. In the case of standard quantum error correcting codes, the dimension of B is 1. A ((k, M, N, d))-OQEC is defined as a OQEC in C 2 k with M and N as the dimension of the logical and gauge subsystems.