# Fast Constructions of Quantum Codes Based on Residues Pauli Block Matrices

Authors: Ying Guo; Guihu Zeng; MoonHo Lee
Journal: Advances in Mathematical Physics
 (2010)

---

## Abstract

We demonstrate how to fast construct quantum error-correction codes based on quadratic residues Pauli block transforms. The present quantum codes have an advantage of being fast designed from Abelian groups on the basis of Pauli block matrices that can be yielded from quadratic residues with much efficiency.


---

## Body

## 1. Introduction

The applications of the Legendre symbol have been already suggested in signal processing, communication, image compression, cryptography, and so forth [1, 2].Provided a finite fieldGF(q), Euler’s criterion ℒq(x) for the Legendre symbol is defined by(1.1)ℒq(x)=x(q-1)/2modq,
where q is a power of an odd prime number. Namely, ℒq(0)=0, ℒq(x)=1 if x=y2 for some element y∈GF(q), and ℒq(x)=-1 if x≠y2 for any element in GF(q). Based on quadratic residues in GF(q), one defines a matrix(1.2)Qq=(aij)q×q,
with the elements aij=ℒq(i-j).Lemma 1.1.
Taking any two rows ofQq, that is, a⃗i=(ℒq(x0),ℒq(x1),…,ℒq(xq-1))anda⃗i+s=(ℒq(x0+s),ℒq(x1+s),…,ℒq(xq-1+s)) for s≠0, it follows
(1.3)a⃗i·a⃗i+s=∑i=0q-1ℒq(xi)ℒq(xi+s)=q-1modq.Currently, the striking development in quantum error-correction codes (QECCs) is the employment of the stabilizer formalism, whereby code words are subspaces in Hilbert space specified by Abelian groups. The problem of constructing QECCs was reduced to that of searching for the classical dual-containing (or self-orthogonal) codes [3–8]. The virtue of this approach is that QECCs can be directly constructed from classical codes with a certain property, rather than developing a completely new coding theory of QECCs from scratch. Unfortunately, the need for dual-containing codes presents a substantial obstacle to the quantum coding theory in its entirety, especially in the context of modern codes, such as low-density parity-check quantum codes [7]. To resolve this problem, we consider the construction of QECCs over the finite field GF(q) by employing the matrix Qn in (1.2). Namely, we first replace all entries of Qn with Pauli matrices and obtain the Pauli block matrix 𝒬n. After that, we extend this kind of block matrices for the large-size Pauli block matrices by using the recursive techniques with the fast matrix block transforms [9–12]. Since all row operations that are obtained from rows of 𝒬n are independent and commutative, an Abelian group can be generated elegantly. Therefore, a type of quantum code is generated structurally via the stabilizer formalism. This approach provides the great flexibility in designing quantum codes with large code length and hence allows for an advantage of being simply constructed with the low complexity.This paper is organized as follows. In Section2, three kinds of Pauli block matrices are constructed. In Section 3, according to the properties of Pauli block matrices, Abelian groups can be generated with efficiency. In Section 4, we investigate constructions of quantum codes based on the stabilizer formalism. Finally, conclusions are drawn in Section 5.


## 2. Pauli Block Matrices

Pauli matrices have been widely applied in signal processing [11], quantum information and quantum computing [3, 13], and so forth. In this section, we investigate constructions of several types of Pauli block matrices according to the structure of Hadamard transforms based on these Pauli matrices.


### 2.1. Pauli Matrices

Pauli matrices are defined by𝒫={σj:0≤j≤3}, where(2.1)σ0=(1001),σ1=(0110),σ2=(0-ii0),σ3=(100-1),
where i=-1. For simplicity, we denote the 2×2 identity matrix σ0 by a block matrix ℐ throughout this paper.Pauli matrices in𝒫 have the following basic properties:(2.2)σ12=σ22=σ32=ℐ,σ1σ2=iσ3,σ2σ3=iσ1,σ3σ1=iσ2.


### 2.2. Pauli Block Matrice

Definition 2.1.
Denote𝒬=([a]ij)k×t, then 𝒬 is a Pauli block matrix if and only if all entries [a]ij belong to 𝒫, that is, [a]ij∈𝒫.
Based on the matrixQq in (1.2), we propose several approaches for constructions of Pauli block matrices for any two entries σi,σj∈𝒫∖{σ0}.Construction.
Taking a matrixQq in (1.2), it follows two kinds of Pauli block matrices: (1)
𝒬q(1), which is constructed by replacing “0,1” in Qq with σi and “-1” with σj,(2)
𝒬q(2), which is constructed by replacing “1” in Qq with σi and “-1,0” with σj.
Specially, one achieves two types of Pauli block matrices.Construction.
Ifq=4m+3 for any positive integer m, then the (q+1)×(q+1) matrix can be constructed as
(2.3)Qq+1=I+(0tT-tQq),
where t denotes the all-1 column vector of the length q and I is the (q+1)×(q+1) identity matrix. As a result, there are two types of Pauli block matrices:  (1)
𝒬q+1(1), which is constructed by replacing “0,1” in Qq+1 with σi and “-1” with σj,(2)
𝒬q+1(2), which is constructed by replacing “1” in Qq+1 with σi and “-1,0” with σj.Construction.
Ifq=4m+1 for any positive integer m, then one constructs the 2(q+1)×2(q+1) matrix Q2(q+1) by replacing “0” in the matrix
(2.4)(0tTtQq)
with the block matrix [R0] and “±1” with the matrix [R±1], where
(2.5)[R0]=(1-1-1-1),[R±1]=±(111-1).
Then, there are two Pauli block matrices: (1)
𝒬2(q+1)(1), which is constructed by replacing “0,1” in Q2(q+1) with σi and “-1” with σj,(2)
𝒬2(q+1)(2), which is constructed by replacing “1” in Q2(q+1) with σi and “-1,0” with σj.


### 2.3. Fast Constructions of Pauli Block Matrices

To construct the large-order Pauli block matrices, we first introduce the Kronecker product of two matricesA=(aij)r×l and B=(bij)s×t, that is,(2.6)A⊗B=(a11Ba12B⋯a1lBa21Ba22B⋯a2lB⋮⋮⋮⋮ar1Bar2B⋯arlB).
With a little abuse, we denote the Kronecker product by using the notation “⊗” throughout this paper.Making use of the Kronecker product of Pauli block matrices [9–12], a family of Pauli block matrices may be extended.Theorem 2.2.
Suppose that𝒬q and 𝒬p are two Pauli block matrices. For any nonnegative integer numbers s and m, a large-order block Jacket matrix 𝒬qspm may be constructed (or decomposed) in the following way:
(2.7)𝒬qspm={ℐqs⊗(∏i=0m-1ℐpm-i-1⊗𝒬p⊗ℐpi)}×{(∏i=0s-1ℐqs-i-1⊗𝒬q⊗ℐqi)⊗ℐpm}={ℐqs⊗(∏i=1mℐpm-i⊗𝒬p⊗ℐpi-1)}×{(∏i=1sℐqs-i⊗𝒬q⊗ℐqi-1)⊗ℐpm}.Proof.
Based on an arbitrary Pauli block matrix𝒬r, the large-order Pauli block matrices 𝒬rl for l≥2 can be obtained by using the recursive relations:
(2.8)𝒬rl=𝒬rl-1⊗𝒬r=∏i=0l-1ℐrl-i-1⊗𝒬r⊗ℐri=∏i=1mℐrl-i⊗𝒬r⊗ℐri-1,
where r∈{p,q} and l∈{s,m}. According to the properties of the Kronecker product, it is easy to calculate
(2.9)𝒬qspm=𝒬qs⊗𝒬pm=(ℐqs⊗𝒬pm)·(𝒬qs⊗ℐpm),
and then this completes the proof of the theorem.Employing Pauli Block matrices𝒬n in Constructions 1, 2, and 3 with respect to the Kronecker product in (2.7), any large-order Pauli block matrices can be constructed with the fast algorithm. The computational complexity of the proposed algorithm is shown in Table 1.Table 1
Computation complexity of the fast algorithm based on Pauli block matrices. For simplicity, Add and Mul denote the number of additions and multiplications. The notationsLpσ and Lqσ express the number of nonidentity matrices σ0 in Pauli block matrices Qp and Qq.
Direct approachProposed algorithmProposed algorithmAdd(n-1)n(p-1)nmpn+qn-2nMuln2LpσnmLpσmn+LqσsnAs an example, the construction of𝒬15=𝒬3⊗𝒬5 is depicted in Figure 1. According to Table 1, the computation of the Pauli block matrix 𝒬15 requires 26 additions and 34 multiplications. Compared with the directed computation, the proposed algorithm is obviously faster.


## 2.1. Pauli Matrices

Pauli matrices are defined by𝒫={σj:0≤j≤3}, where(2.1)σ0=(1001),σ1=(0110),σ2=(0-ii0),σ3=(100-1),
where i=-1. For simplicity, we denote the 2×2 identity matrix σ0 by a block matrix ℐ throughout this paper.Pauli matrices in𝒫 have the following basic properties:(2.2)σ12=σ22=σ32=ℐ,σ1σ2=iσ3,σ2σ3=iσ1,σ3σ1=iσ2.


## 2.2. Pauli Block Matrice

Definition 2.1.
Denote𝒬=([a]ij)k×t, then 𝒬 is a Pauli block matrix if and only if all entries [a]ij belong to 𝒫, that is, [a]ij∈𝒫.
Based on the matrixQq in (1.2), we propose several approaches for constructions of Pauli block matrices for any two entries σi,σj∈𝒫∖{σ0}.Construction.
Taking a matrixQq in (1.2), it follows two kinds of Pauli block matrices: (1)
𝒬q(1), which is constructed by replacing “0,1” in Qq with σi and “-1” with σj,(2)
𝒬q(2), which is constructed by replacing “1” in Qq with σi and “-1,0” with σj.
Specially, one achieves two types of Pauli block matrices.Construction.
Ifq=4m+3 for any positive integer m, then the (q+1)×(q+1) matrix can be constructed as
(2.3)Qq+1=I+(0tT-tQq),
where t denotes the all-1 column vector of the length q and I is the (q+1)×(q+1) identity matrix. As a result, there are two types of Pauli block matrices:  (1)
𝒬q+1(1), which is constructed by replacing “0,1” in Qq+1 with σi and “-1” with σj,(2)
𝒬q+1(2), which is constructed by replacing “1” in Qq+1 with σi and “-1,0” with σj.Construction.
Ifq=4m+1 for any positive integer m, then one constructs the 2(q+1)×2(q+1) matrix Q2(q+1) by replacing “0” in the matrix
(2.4)(0tTtQq)
with the block matrix [R0] and “±1” with the matrix [R±1], where
(2.5)[R0]=(1-1-1-1),[R±1]=±(111-1).
Then, there are two Pauli block matrices: (1)
𝒬2(q+1)(1), which is constructed by replacing “0,1” in Q2(q+1) with σi and “-1” with σj,(2)
𝒬2(q+1)(2), which is constructed by replacing “1” in Q2(q+1) with σi and “-1,0” with σj.


## 2.3. Fast Constructions of Pauli Block Matrices

To construct the large-order Pauli block matrices, we first introduce the Kronecker product of two matricesA=(aij)r×l and B=(bij)s×t, that is,(2.6)A⊗B=(a11Ba12B⋯a1lBa21Ba22B⋯a2lB⋮⋮⋮⋮ar1Bar2B⋯arlB).
With a little abuse, we denote the Kronecker product by using the notation “⊗” throughout this paper.Making use of the Kronecker product of Pauli block matrices [9–12], a family of Pauli block matrices may be extended.Theorem 2.2.
Suppose that𝒬q and 𝒬p are two Pauli block matrices. For any nonnegative integer numbers s and m, a large-order block Jacket matrix 𝒬qspm may be constructed (or decomposed) in the following way:
(2.7)𝒬qspm={ℐqs⊗(∏i=0m-1ℐpm-i-1⊗𝒬p⊗ℐpi)}×{(∏i=0s-1ℐqs-i-1⊗𝒬q⊗ℐqi)⊗ℐpm}={ℐqs⊗(∏i=1mℐpm-i⊗𝒬p⊗ℐpi-1)}×{(∏i=1sℐqs-i⊗𝒬q⊗ℐqi-1)⊗ℐpm}.Proof.
Based on an arbitrary Pauli block matrix𝒬r, the large-order Pauli block matrices 𝒬rl for l≥2 can be obtained by using the recursive relations:
(2.8)𝒬rl=𝒬rl-1⊗𝒬r=∏i=0l-1ℐrl-i-1⊗𝒬r⊗ℐri=∏i=1mℐrl-i⊗𝒬r⊗ℐri-1,
where r∈{p,q} and l∈{s,m}. According to the properties of the Kronecker product, it is easy to calculate
(2.9)𝒬qspm=𝒬qs⊗𝒬pm=(ℐqs⊗𝒬pm)·(𝒬qs⊗ℐpm),
and then this completes the proof of the theorem.Employing Pauli Block matrices𝒬n in Constructions 1, 2, and 3 with respect to the Kronecker product in (2.7), any large-order Pauli block matrices can be constructed with the fast algorithm. The computational complexity of the proposed algorithm is shown in Table 1.Table 1
Computation complexity of the fast algorithm based on Pauli block matrices. For simplicity, Add and Mul denote the number of additions and multiplications. The notationsLpσ and Lqσ express the number of nonidentity matrices σ0 in Pauli block matrices Qp and Qq.
Direct approachProposed algorithmProposed algorithmAdd(n-1)n(p-1)nmpn+qn-2nMuln2LpσnmLpσmn+LqσsnAs an example, the construction of𝒬15=𝒬3⊗𝒬5 is depicted in Figure 1. According to Table 1, the computation of the Pauli block matrix 𝒬15 requires 26 additions and 34 multiplications. Compared with the directed computation, the proposed algorithm is obviously faster.


## 3. Abelian Group Based on Pauli Block Matrices

Let𝒫⊗n denote the set of the n-fold tensor products (the Kronecker product) of Pauli operators (matrices) in 𝒫 [13]. Then 𝒫⊗n, together with possible multiplicative factors in {±i,±1}, form a group of n-qubit operations, denoted by 𝒢n. An arbitrary operation αu∈𝒢n can be uniquely expressed by(3.1)αu=iλ[σ1xu1σ2zu1]⊗⋯⊗[σ1xunσ2zun],
where xut,zut∈{0,1} for 1≤t≤n. Omitting factor iλ, we denote αu by a concatenated 2n-dimensional vector α⃗u [6]:(3.2)α⃗u=(x⃗u∣z⃗u)=(xu1,…,xun∣zu1,…,zun).The Hamming weight ofα⃗u is the number of (xuh∣zuh) (1≤h≤n) such that (xuh∣zuh)≠(0∣0). The symplectic inner product of any two vectors α⃗u=(x⃗u∣z⃗u) and α⃗v=(x⃗v∣z⃗v) is defined by(3.3)α⃗u·α⃗v=x⃗u·z⃗v+z⃗u·x⃗v,
where x⃗u·z⃗v=∑i=1nxuizvi and z⃗u·x⃗v=∑i=1nzuixvi. According to [6], two operations αu and αv commute if and only if(3.4)α⃗u·α⃗v=0.The symplectic inner product of two vectors is important since it can be used conveniently to search for generators of an Abelian subgroup𝒮⊆𝒢n.Assume that each row of a Pauli block matrix𝒬n is denoted by (σi1,…,σin) for 1≤i≤n, from which an n-qubit operation, called as the row operator, can be obtained as(3.5)αi=σi1⊗⋯⊗σin.Based on properties of the Kronecker product [11, 14, 15], we achieve the commutativity of row operators for Pauli block matrices 𝒬n.Theorem 3.1.
For Pauli block matrices𝒬n proposed in Construction 1 (also for Constructions 2 and 3), all independent row operators of 𝒬n are commuting and hence generate an Abelian group.Proof.
Employing Pauli block matrices𝒬n that are constructed via substituting Pauli matrices for the entries of the Hadamard matrices, all row operators of 𝒬n can be expressed by the concatenated vectors in (3.2), from which the n×2n matrices (Hx∣Hz) can hence be constructed. According to the properties of the Hadamard matrices, it is easy to calculate
(3.6)Hx·HzT+Hz·HxT=0mod2,
which implies that all independent n-qubit row operators of 𝒬n are commuting [5].Corollary 3.2.
Considering any two given Pauli block matrices𝒬p and 𝒬q, all independent pq-qubit row operators of the Kronecker product 𝒬pq=𝒬p⊗𝒬q are commuting.Example 3.3.
We considerGF(3)={0,1,2} with the nonzero squares 12=1mod3 and 22=1mod3, and hence ℒ3(0)=0,ℒ3(1)=1, and ℒ3(2)=-1. With the rows and columns of a matrix Q3 being indexed by {0,1,2}, one obtains
(3.7)Q3=(01-1-1011-10).
According to Construction 1, one gains the Pauli block matrix:
(3.8)𝒬3(1)=(σiσiσjσjσiσiσiσjσi).
Taking i=1 and j=3, one has the concatenated matrix:
(3.9)H3=(H3x∣H3z)=110001011100101100.
It is easy to check that H3x·H3zT+H3z·Hx3T=0mod2, which means that three row operators of 𝒬3(1)(3.10)α1=σ1⊗σ1⊗σ3,α2=σ3⊗σ1⊗σ1,α3=σ1⊗σ3⊗σ1
are commuting.
For another, based on Construction2, one obtains
(3.11)Q4=(1111-111-1-1-111-11-11),
from which the Pauli block matrix 𝒬4(1) can be achieved:
(3.12)𝒬4(1)=(σiσiσiσiσjσiσiσjσjσjσiσiσjσiσjσi).
Taking i=1 and j=3, one has the concatenated matrix:
(3.13)H4=11110000011010010011110001011010,
from which it is easy to check that all row operators of 𝒬4(1) are commuting.Example 3.4.
According toGF(5) with ℒ5(1)=ℒ5(4)=1mod5 and ℒ5(2)=ℒ5(3)=-1mod5, if the rows and columns of Q5 are indexed by GF(5), one gets
(3.14)Q5=(01-1-11101-1-1-1101-1-1-11011-1-110).
Employing Construction 1, we get the Pauli block matrix:
(3.15)𝒬5(1)=(σiσiσjσjσiσiσiσiσjσjσjσiσiσiσjσjσjσiσiσiσiσjσjσiσi).
Taking i=1 and j=3, one has
(3.16)H5=11001001101110000011011101000100111110001001101100,
which means that five row operators of 𝒬5(1) for i=1 and j=3 are commuting.
Furthermore, according to Construction3 with respective Q5 in (3.14), one obtains a Pauli block matrix 𝒬10(1) for i=1 and j=3 with the concatenated matrix H10 expressed as
(3.17)H10=10110000110100111100001001011011011010011110110000000100111110001001010111011010001110110011000100110110001001100111011000001110111111000100010110001010100111011100001110001111000110010110000110100111.
It is obvious that all row operators of 𝒬10(1) are commuting.


## 4. The Stabilizer Quantum Codes

In this section, we construct quantum codesC(𝒮) by using Pauli block matrices 𝒬n with commutative row operators, from which n-k independent row operators can be selected as generators of an Abelian group 𝒮.Given an Abelian subgroup𝒮 of 𝒢n, the stabilizer quantum code C(𝒮) is a set of n-qubit quantum states {|ψ〉} associated with 𝒮, that is,(4.1)C(𝒮)={|ψ〉:M|ψ〉=|ψ〉,∀M∈𝒮},
which is the subspace fixed by 𝒮 (called as the stabilizer). For an [[n,k,d]] stabilizer quantum code, which encodes k logical qubits into n physics qubits, C(𝒮) has dimension 2k and 𝒮 has 2n-k independent operators.To construct such a quantum code, the sticking point is to search for an Abelian group, the stabilizer𝒮, from which the code C(𝒮) can be structurally generated through (4.1).Theorem 4.1.
Given a Pauli block matrix𝒬n with commutative row operators, the stabilizer quantum code C(𝒮) can be constructed with parameters [[n,k,d]] where the stabilizer 𝒮 is a set of n-qubit operators generated from n-k independent row operators of Pauli block matrix 𝒬n.Proof.
Suppose that there arer (r≥n-k) independent rows of 𝒬n. Then n-k generators of the stabilizer 𝒮 can be generated by selecting n-k rows from these r independent rows of 𝒬n provided n-k≤r. Namely, any n-k operators αi1,αi2,…,αin-k can be selected to generate an Abelian group:
(4.2)𝒮=〈αi1,αi2,…,αin-k〉,
which is a stabilizer in essence. By making use of (4.1), a stabilizer quantum code [[n,k,d]] can be generated from 𝒮. According to the quantum Singleton bound proposed in [6], it follows that k≤n-2d+2. This completes the proof of the theorem.Example 4.2.
We consider the Pauli block matrix𝒬5 in (3.15) with the concatenated matrix H5=(H5x∣H5x) in (3.16). It is known that all rows of H5 are independent. Thus, any 5-k rows of H5, denoted by ℋ5=(h5x∣h5z), can be selected to generate the stabilizer 𝒮 with 5-k generators. According to the construction conditions of quantum codes in [5], we get the generator matrix of quantum codes 𝒢5=(g5x∣g5z) satisfying
(4.3)h5x·g5z+h5z·g5x=0,
which can be rewritten as
(4.4)ℋ5·R·𝒢5=0,
where R=(05×5I5×5I5×505×5). To construct such a quantum code, we assume that there exists one unitary matrix U such that
(4.5)U(hR)=(I(5-k)×(5-k)∣Λ(5-k)×(5+k)).
According to (4.4), the generator matrix g is calculated:
(4.6)𝒢5=(Λ(5-k)×(5+k)T∣I(5+k)×(5+k)),
from which quantum codes can be constructed with the parameters [[5,0,4]], [[5,1,2]], [[5,2,1]], [[5,3,1]], and [[5,4,1]].
Taking the quantum code[[5,1,2]] as an example, we select 4 rows to generate the matrix:
(4.7)ℋ5=1100100110111000001101110100010011111000.
From (4.4), we get
(4.8)𝒢5=011010000000010100001101001000101100010010000000100011000001.
Therefore, a quantum code [[5,1,2]] can be constructed from (4.8), where d=2, the Hamming weight of 𝒢5, can be calculated from the Hamming weight of the bitwise or of g5x with g5z.Example 4.3.
Supposen=10, and then we consider Pauli block matrix 𝒬10(1) for i=1 and j=3 with the concatenated matrix in (3.17). It is obvious that all rows of H10 are independent and commutative. Selecting any 10-k (0≤k≤10) row operators αi1,αi2,…,αi10-k from 𝒬10(1), we obtain the stabilizer 𝒮=〈αi1,αi2,…,αi10-k〉, from which quantum codes can be constructed with the parameters [[10,0,4]], [[10,1,4]], [[10,2,4]], [[10,3,3]], [[10,4,3]], [[10,5,3]], [[10,6,3]], [[10,7,3]], [[10,8,1]], and [[10,9,1]].


## 5. Conclusion

A family of quantum codes is investigated with fast Pauli block transforms by using quadratic residues in the finite fieldGF(q). We first investigate the construction approaches based on three kinds of Pauli block matrices with commutative row operators. Then the large-order Pauli block matrices are structurally constructed via the fast Pauli block constructing transforms based on the recursive relationship of identity matrices and successively lower-order Pauli block matrices. These Pauli block matrices have such a characteristic that all row operators are independent and commutative, which can generate an Abelian operator group. Finally, an instructive approach for constructions of quantum codes is suggested via the stabilizer formalism according to the Abelian group 𝒮 yielded from Pauli block matrices. This code may provide the great flexibility in designing quantum codes with large block length through implementing the proposed fast construction algorithms.Figure 1
Signal flow graph for Pauli block transform for𝒬15.



---

*Source: 469124-2010-02-21.xml*