QUASI-CYCLIC CONSTRUCTIONS OF QUANTUM CODES

arXiv:1712.06907v1 [] 19 Dec 2017

CARLOS GALINDO, FERNANDO HERNANDO AND RYUTAROH MATSUMOTO
Abstract. We give sufficient conditions for self-orthogonality with respect to symplectic, Euclidean and Hermitian inner products of a wide family of quasi-cyclic codes of index
two. We provide lower bounds for the symplectic weight and the minimum distance of
the involved codes. Supported in the previous results, we show algebraic constructions
of good quantum codes and determine their parameters.

Introduction
Attention to quantum information processing, especially quantum computing, is rapidly
growing, as several companies seem to build quantum computers with many qubits [6]. One
of the important theoretical techniques to realize quantum computation is the quantum
error correction, which protects quantum memory and quantum computational process
from noise.
Quantum error correction was proposed by Shor [22]. Its connection to classical error
correction was mainly described in [5, 3, 4, 10, 24]. Afterwards that connection was
generalized to the non-binary case (see [20, 2, 1]). Since then, the use of classical (errorcorrecting) codes has become one of standard methods for constructing quantum codes,
see [15] for a survey.
Quasi-cyclic codes (QC codes) are a generalization of classical cyclic codes. It is wellknown that there are asymptotically good codes attaining the Gilbert-Varshamov bound
among QC codes [14, 19], so it is natural to use QC codes to construct good quantum
codes. Hagiwara et al. [12, 13] studied constructions of quantum codes by QC LDPC
codes. They focused on long codes and probabilistic constructions.
In this paper, we consider a wide class of QC codes of index 2 (see Subsections 1.1 and
1.3) and give sufficient conditions for their self-orthogonality with respect to symplectic,
Euclidean and Hermitian inner products. Sections 2, 3 and 4 are devoted to the symplectic,
Euclidean and Hermitian cases, respectively. In addition, we get lower bounds for the
symplectic weight and the minimum distance of the involved codes. As a consequence,
we provide an algebraic construction of short stabilizer quantum codes coming from the
previously introduced QC codes (see Theorems 5, 12 and 15). To testify the interest of
our construction, we complete this paper by showing several examples of quantum codes
with good parameters. Indeed, we get quantum codes exceeding the Gilbert-Varshamov
bounds [8, 9, 20] and/or improving the parameters of those codes which could be obtained
by the CSS procedure from the best known linear codes under the assumption of being
self-orthogonal.
2010 Mathematics Subject Classification. 94B65; 94B15; 81P70.
Key words and phrases. Quasi-cyclic codes; Trace; Symplectic, Hermitian and Euclidean duality; Quantum codes.
Supported by the Spanish Ministry of Economy/FEDER: grants MTM2015-65764-C3-2-P and
MTM2015-69138-REDT, and the University Jaume I: grant PB1-1B2015-02.
1

2

CARLOS GALINDO, FERNANDO HERNANDO AND RYUTAROH MATSUMOTO

1. Preliminaries
In this section, we review the concept of quasi-cyclic (QC) code and the existing connections between stabilizer quantum codes and classical codes. We also introduce the class
of QC codes we will use.
Throughout the paper, Fq will denote the finite field with q elements, q being a positive
power pr of a prime number p. Recall than an [n, k, d]q classical code is a linear space
C ⊂ Fnq of dimension k and minimum (Hamming) distance d. For a set S ⊂ Fnq , w(S) will
denote the minimum of the Hamming weights of those vectors in S.
1.1. Quasi-cyclic codes. For a vector ~x = (x1 , x2 , . . . , xn ) ∈ Fnq , we denote
σ1 (~x) = (xn , x1 , . . . , xn−1 ).
A linear space C ⊂ Fnq is said to be a cyclic code if C = σ1 (C).
For a vector ~x ∈ F2n
q , we denote
σ2 (~x) = (xn , x1 , . . . , xn−1 , x2n , xn+1 , . . . , x2n−1 ).
A linear space C ⊂ F2n
q is said to be a quasi-cyclic (QC) code (of index 2) if C = σ2 (C).
We denote by (xn − 1) the ideal of the polynomial ring Fq [x] generated by xn − 1, and
by R = Fq [x]/(xn − 1) the quotient ring of Fq [x] modulo (xn − 1). Given a polynomial
g(x) in Fq [x], by [g(x)] we mean its residue class in R. When studying cyclic codes, a
vector ~a = (a0 , . . . , an−1 ) is identified with the residue class
(1)

[a(x)] = [a0 + a2 x + a3 x2 + · · · + an−1 xn−1 ],

and σ1 (~a) corresponds to the class [xa(x)]. Thus, a cyclic code can be identified with an
ideal of R via the correspondence (1). Since R is a principal ideal domain, any cyclic
code can be generated by a single [g(x)] ∈ R. In the sequel, the minimum Hamming
distance of the cyclic code generated by g(x) will be denoted by d(g(x)). The expression
g(x)|h(x), g(x), h(x) ∈ Fq [x] means that g(x) divides h(x). When g(x)|h(x), the cyclic
code generated by [g(x)] contains that by [h(x)].
A vector ~c = (a0 , . . . , an−1 , b0 , . . . , bn−1 ) in F2n
q can be identified with ([a(x)], [b(x)]) ∈
2
R , where
a(x) = a0 + a2 x + a3 x2 + · · · + an−1 xn−1 , b(x) = b0 + b2 x + b3 x2 + · · · + bn−1 xn−1 .
Then σ2 (~c) corresponds to the element ([xa(x)], [xb(x)]) in R2 . By this correspondence,
we see that a QC code C can be identified with an R-submodule of R2 .
Note that a QC code generated by m elements in R2 ,
([f1 (x)], [g1 (x)]), [f2 (x)], [g2 (x)]), . . . , ([fm (x)], [gm (x)]),
can be regarded as the R-module
)
(m
X
([ai (x)fi (x)], [ai (x)gi (x)]) | ai (x) ∈ Fq [x] .
i=1

1.2. Quantum code constructions from classical linear codes. A stabilizer (quantum) code C 6= {0} is the common eigenspace of a commutative subgroup of the error
n
group generated by a nice error basis on the space Cq , where C denotes the complex
numbers, q is a positive power of a prime number and n is a positive integer [15]. The
code C has minimum distance d as long as errors with weight less than d can be detected
or have no effect on C but some error with weight d cannot be detected. Furthermore,

QUASI-CYCLIC CONSTRUCTIONS OF QUANTUM CODES

3

if C has dimension q k as a C-vector space, then we say that the code C has parameters
[[n, k, d]]q .
For a linear space C ⊂ Fnq , C ⊥ denotes its Euclidean dual, that is {~x ∈ Fnq | h~x,
~yi = 0, for all ~y ∈ C}, where h~x, ~yi denotes the Euclidean (standard) inner product. From
two classical linear codes C1 and C2 over Fq and assuming that C2 ⊂ C1 ⊂ Fnq , we can
construct a stabilizer quantum code with parameters
[[n, dim C1 − dim C2 , min{w(C1 \ C2 ), w(C2⊥ , C1⊥ )}]]q .
This construction was shown in [1, 5, 24].
Stabilizer quantum codes can also be constructed from classical self-orthogonal codes
with respect to the Hermitian inner product (see for instance [15, Corollary 16]). Indeed, recall that the Hermitian inner product of two vectors ~x = (x1 , x2 , . . . xn ) and
~y = (y1 , y2 , . . . yn ) in Fnq2 is defined as
h~x, ~y ih :=

n
X

xqi yi .

i=1

Now, if C ⊂

Fnq2

is a classical code with parameters [n, k, d]q2 such that
o
n
C ⊥h := ~x ∈ Fnq2 | h~x, ~y ih = 0 ⊂ C,

then, it can be constructed a stabilizer quantum code with parameters [[n, 2k − n, d]]q .
Finally, we have another construction that can be seen in [1]. For ~x, ~y ∈ F2n
q , their
symplectic inner product is defined as
h~x, ~y is =

n
X

xi yn+i − xn+i yi .

i=1

Given a linear space C ⊂ F2n
q , we denote

C ⊥s = {~x ∈ F2n
x, ~y is = 0, for all ~y ∈ C}.
q | h~
For ~x ∈ F2n
x) = card{i | (xi , xn+i ) 6= (0, 0)} and for a set S ⊂ F2n
q , set ws (~
q , we denote
ws (S) = min{ws (~x) | ~x ∈ S}. We call ws as the symplectic weight. The result concerning
⊥s
stabilizer codes states that when C ⊂ F2n
q is a linear code such that C ⊃ C , we can
construct an [[n, dim C − n, ws (C \ C ⊥s )]]q stabilizer quantum code.
1.3. The supporting QC codes. We devote this brief section to introduce the family
of QC codes we are going to use for constructing stabilizer quantum codes. Recall that p
is a prime and q = pr . Fix a positive integer n, consider the polynomial xn − 1 ∈ Fq [x]
and assume that the splitting field of that polynomial is Fpmr for some positive integer m.
Let f (x), g(x) and h(x) be monic polynomials in Fq [x] whose degree is less than n and
such that both f (x) and g(x) divide xn − 1. Recall that the class [f (x)] of a polynomial
f (x) as above that divides xn − 1 generates a cyclic code of length n and dimension
n − deg(f ). Consider the check polynomial f ′ (x) which satisfies f (x) · f ′ (x) = xn − 1 and
define
 
⊥
deg f ′ ′ 1
.
f
f (x) := x
x
Then, it is well-known that [f ⊥ (x)] generates the dual code of the cyclic code generated by
[f (x)]. Next we define the mentioned family of QC codes. We will use suitable subfamilies
for obtaining our quantum codes.

4

CARLOS GALINDO, FERNANDO HERNANDO AND RYUTAROH MATSUMOTO

Definition 1. With the above notation, Qq (f, g, h) will be the QC code over Fq of length
2n generated by ([f (x)], [h(x)f (x)]) and (0, [g(x)]). When q and the polynomials be clear,
we will denote it simply by Q.
Notice that, according to [16, Section 2], the generator set of Qq (f, g, h) is a Groebner
basis for the Fq [x]-submodule ψ −1 (Qq (f, g, h)), which is the preimage in (Fq [x])2 of the
R-submodule Qq (f, g, h) under the class map ψ : (Fq [x])2 → R2 .
To the best of our knowledge, this is the first family of QC codes of short length giving
quantum codes by algebraic techniques. There was a first attempt in [21] but it seems to be
wrong because the proposed codes contradict the dimension formula for simple generator
QC codes [16]. Indeed, if one considers a QC code generated by a single polynomial vector
([f1 (x)], [f2 (x)], . . . , [fℓ (x)]), then dim C ≤ n by [16, Corollary 2.14]. However C ⊃ C ⊥
implies dim C ≥ ℓn/2, which is not satisfied by the codes in [21].
In our development and attached to polynomials h(x) ∈ Fq [x] with degree less than n,
we will consider the polynomials h̄(x) defined as
 
1
n
h̄(x) := x h
.
x
They are instrumental as the following result shows.
Proposition 2. Let f (x), g(x) and h(x) be monic polynomials in Fq [x] whose degrees are
less than n and consider the vectors in Fnq determined by their classes in R as described
before Equality (1). Then, the following equality of Euclidean inner products of vectors in
Fnq holds:
h[f (x)g(x)], [h(x)]i = h[g(x)], [f (x)h(x)]i.

(2)

Proof. Let f (x) = f0 + · · · + fn−1 xn−1 . We have
h[f (x)g(x)], [h(x)]i =

n−1
X

fi h[xi g(x)], [h(x)]i,

i=0

and
h[g(x)], [f (x)h(x)]i =

n−1
X

fi h[g(x)], [xn−i h(x)]i.

i=0

In order to prove the proposition, it is sufficient to show
h[xi g(x)], [h(x)]i = h[g(x)], [xn−i h(x)]i.

(3)

Let g(x) = g0 + · · · + gn−1 xn−1 and h(x) = h0 + · · · + hn−1 xn−1 . Then
i

h[x g(x)], [h(x)]i =

n−1
X

gi+j mod n hj =

gj hj+n−i mod n , and

j=0

j=0

h[g(x)], [xn−i h(x)]i =

n−1
X

n−1
X

gj hj+n−i mod n ,

j=0

which shows Equality (3).



The following sections will explain how to get stabilizer quantum codes from suitable
QC codes Qq (f, g, h) and will give information about their parameters.

QUASI-CYCLIC CONSTRUCTIONS OF QUANTUM CODES

5

2. Quasi-cyclic construction of quantum codes with symplectic inner
product
Proposition 3. With the above notation, the QC code Q := Qq (f, g, h) has dimension
2n − deg(f (x)) − deg(g(x)), and its symplectic dual Q⊥s is quasi-cyclic and generated by
([g ⊥ (x)], [h(x)g ⊥ (x)]) and ([0], [f ⊥ (x)]).
Proof. The dimension can be deduced from the fact that {(f (x), h(x)f (x)), (0, g(x))} is
a Groebner basis for the preimage in (Fq [x])2 of the R-submodule Q = Qq (f, g, h) under
the map (Fq [x])2 → R2 (see [16, Theorem 2.1]). Alternatively, it is clear that a codeword
in Q can be expressed as ([a(x)f (x)], [a(x)h(x)f (x) + b(x)g(x)]), where deg(a(x)) ≤ n −
deg(f (x)) − 1 and deg(b(x)) ≤ n − deg(g(x)) − 1. From ([a(x)f (x)], [a(x)h(x)f (x) +
b(x)g(x)]), one can determine unique representatives (a(x), b(x)) with deg(a(x)) ≤ n −
deg(f (x)) − 1 and deg(b(x)) ≤ n − deg(g(x)) − 1, therefore the map
([a(x)f (x)], [a(x)h(x)f (x) + b(x)g(x)]) 7→ ([a(x)], [b(x)])
is an isomorphism of Fq linear spaces. Now the statement about dimension can be deduced
from the fact that the cyclic code generated by f (x) (respectively, g(x)) has dimension
n − deg(f (x)) (respectively, n − deg(g(x))).
With respect to duality, A vector generated by ([g⊥ (x)], [h(x)g ⊥ (x)]) and (0, [f ⊥ (x)])
has the form ([c(x)g ⊥ (x)], [c(x)h(x)g ⊥ (x) + d(x)f ⊥ (x)]), whose symplectic inner product
with ([a(x)f (x)], [a(x)h(x)f (x) + b(x)g(x)]) is, by Equality (2),
h[a(x)f (x)], [d(x)f ⊥ (x)]i + h[a(x)f (x)], [c(x)h(x)g ⊥ (x)]i
−h[a(x)h(x)f (x)], [c(x)g ⊥ (x)]i − h[b(x)g(x), c(x)g ⊥ (x)]i
= h[a(x)f (x)], [c(x)h(x)g ⊥ (x)]i − h[a(x)h(x)f (x), c(x)g ⊥ (x)]i
= h[a(x)h(x)f (x)], [c(x)g ⊥ (x)]i − h[a(x)h(x)f (x)], [c(x)g ⊥ (x)]i
= 0.
This concludes the proof after taking into account that the dimension of the space
generated by ([g⊥ (x)], [h(x)g ⊥ (x)]) and ([0], [f ⊥ (x)]) is 2n − deg(g⊥ (x)) − deg(f ⊥ (x)). 
Proposition 4. Consider the QC code Q := Qq (f, g, h) where we assume that h(x) satisfies that gcd(h(x) − β, xn − 1) = 1 for all non-zero β ∈ Fq . Then, a lower bound on the
symplectic weight of Q is the following value
dq (f, g, h) =

 

min d([g(x)]), d [(xn − 1)/gcd(xn − 1, h(x))] , d lcm f (x), g(x)/gcd(g(x), h(x))
,

. 
d([f (x)]) + d([gcd(h(x)f (x), g(x))]) + (q − 1)d([gcd(f (x), g(x)))] q .

Proof. Consider the symplectic weight

ws = ws ([a(x)f (x)], [a(x)h(x)f (x) + b(x)g(x)]).
If [a(x)] = 0 then ws ≥ d(g(x)).
We are going to use the following relation among symplectic and Hamming weights of
vectors {~u, ~v } ∈ F2n
q which was proved in [18, Lemma 2.4].
X
(4)
qws (~u, ~v ) = wH (~u) + wH (~v ) +
wH (α~u + ~v ).
06=α∈Fq

6

CARLOS GALINDO, FERNANDO HERNANDO AND RYUTAROH MATSUMOTO

Suppose that [b(x)] = 0, [a(x)] 6= 0 and [a(x)h(x)f (x)] 6= 0. Since h(x) − β is a unit
modulo xn − 1, [a(x)(h(x) − β)f (x)] 6= 0 for nonzero β. Then, for q = 2, it holds

.
ws =
wH ([a(x)f (x)]) + wH ([a(x)h(x)f (x)]) + wH ([a(x)(h(x) + 1)f (x)]) 2

.
≥
d([f (x)]) + d([h(x)f (x)]) + d([f (x)]) 2

.
≥
d([f (x)]) + d([gcd(h(x)f (x), g(x))]) + d([gcd(f (x), g(x))]) 2.
For q > 2, we have

ws =
wH ([a(x)f (x)]) + wH ([a(x)h(x)f (x)])
.
X
+
wH ([a(x)(h(x) + β)f (x)]) q
06=β∈Fq

≥



.
d([f (x)]) + d([gcd(h(x)f (x), g(x))]) + (q − 1)d([gcd(f (x), g(x))]) q.

Suppose now that [b(x)] = 0, [a(x)] 6= 0 and [a(x)h(x)f (x)] = 0. Then ws equals
wH ([a(x)f (x)]) and [a(x)f (x)] belongs to the cyclic code generated by [(xn − 1)/gcd(xn −
1, h(x))]. Thus ws ≥ d([(xn − 1)/gcd(xn − 1, h(x))]).
Finally and until the end of the proof, we assume [a(x)] 6= 0 and [b(x)] 6= 0. Then, we
have
(5) qws = wH ([a(x)f (x)]) + wH ([a(x)h(x)f (x) + b(x)g(x)])
X
wH ([a(x)(h(x) + β)f (x) + b(x)g(x)]).
+
06=β∈Fq

If some summand of the summation in (5) is zero, then [a(x)(h(x) + β)f (x)] = −[b(x)g(x)]
for some β ∈ Fq , which means that lcm(f (x), g(x))|a(x)f (x) as h(x) + β is a unit. So

ws ≥ wH ([a(x)f (x)]) ≥ d lcm(f (x), g(x)) .

In case the second summand in (5) is zero, we get

ws = wH ([a(x)f (x)])
and [a(x)f (x)] belongs to the cyclic code generated by [g(x)/gcd(g(x), h(x))]. So


ws ≥ d lcm f (x), g(x)/gcd(g(x), h(x))
.

Otherwise (all summands in (5) are nonzero),

.
ws ≥ d([f (x)]) + d([gcd(h(x)f (x), g(x))]) + (q − 1)d([gcd(f (x), g(x))]) q,

which concludes the proof.



Theorem 5. With the above notation, assume that the polynomial h(x) satisfies that
gcd(h(x) − β, xn − 1) = 1 for all non-zero β ∈ Fq . Assume also that it holds either (i)
f (x)|g ⊥ (x), g(x)|f ⊥ (x) and h(x)|h(x), or (ii) f (x)|g(x)|g ⊥ (x)|f ⊥ (x).
Then, the QC code Q := Qq (f, g, h) is symplectic self-orthogonal and allows us to
construct a stabilizer quantum code with parameters [[n, n − deg(f (x)) − deg(g(x)), ≥
dq (f, g, h)]]q .

QUASI-CYCLIC CONSTRUCTIONS OF QUANTUM CODES

7

Proof. The fact that Q is self-orthogonal follows trivially from Proposition 3 in Case (i).
In Case (ii), we have f ⊥ (x) = α1 (x)g⊥ (x), g ⊥ (x) = α2 (x)g(x) and g(x) = α3 (x)f (x),
where αi (x) ∈ Fq [x] for i ≤ i ≤ 3. Now


a(x)g⊥ (x), a(x)h̄(x)g⊥ (x) + b(x)f ⊥ (x)


= a(x)α2 (x)α3 (x)f (x), a(x)α2 (x)α3 (x)f (x) + q(x)g(x) ,

where q(x) = a(x)α2 (x)(h̄(x) − 1) + b(x)α1 (x)α2 (x), which again by Proposition 3, proves
the self-orthogonality in this case. Now Proposition 4 and Subsection 1.2 conclude the
proof.

To finish this section, we will provide some polynomials h(x) which are suitable for the
previous mentioned purposes.
For each set {i, j} of positive integers, consider the following trace polynomials in Fq [x]
i

2i

trji/i (x) = x + xp + xp + · · · + xp

(j−1)i

.

Proposition 6. Assume, as above, that the splitting field of xn − 1 ∈ Fq [x] is Fpmr
and consider a positive integer s < p which divides m and is coprime with r. Then the
polynomial in Fq [x]
h(x) = (p − s)trmr/s (x) + trmr/1 (x)
satisfies that h(x) + β is coprime with xn − 1 for all β ∈ Fq \ {0}.
Proof. In this proof, for the sake of simplicity, we will use the same expression for the
involved polynomials and the maps which they define. We are going to prove that the
equation h(x) + β = 0 has no solution in Fqm , which is equivalent to h(a) + β 6= 0 for all
a ∈ Fqm and β ∈ Fq \ {0}.
Indeed, observe that trji/i can be regarded as a map Fpji → Fpi . In addition, it holds
the equality trmr/1 = trs/1 ◦ trmr/s , where ◦ means maps composition. When trmr/s (a) =
b ∈ Fp , we have trmr/1 (a) = sb and h(a) = pb = 0. Otherwise we have trmr/s (a) = b′ ∈
Fps \ Fp , which cannot be equal to −trmr/1 (a) − β ∈ Fq , because our conditions imply
that (Fps \ Fp ) ∩ Fq = ∅.

Polynomials h(x) in Proposition 6 need not to be of degree less than n but this condition
can be obtained by considering the remainder h′ (x) of h(x) by division on xn − 1. The
fact that h′ (x) satisfies the conclusion of Proposition 6 can be easily proved from Bézout’s
identity.
Finally we explain when the polynomials h(x) = x + 1 or h(x) = xp − x are suitable for
our purposes.
Lemma 7. With the above notation, it holds that gcd(xn − 1, x + 1 + β) = 1 for all
β ∈ Fq \ {0} if and only if gcd(q − 1, n) = 1.
Proof. Assume that gcd(xn − 1, x + 1 + β) = x + 1 + β = x − α, α ∈ Fq , which means that
xn − 1 contains a q − 1 root of unity and so αq−1 = αn = 1. This equality holds if and
only if gcd(q − 1, n) 6= 1, which concludes the proof.

Proposition 8. The polynomial h(x) = x+1 ∈ F2 [x] (h(x) = xp −x ∈ Fp [x], respectively)
satisfies the condition gcd(h(x) − β, xn − 1) = 1 for all non-zero β ∈ Fq , being q = 2
(respectively, q = p and p does not divide m = logp (n + 1)).

8

CARLOS GALINDO, FERNANDO HERNANDO AND RYUTAROH MATSUMOTO

Proof. Lemma 7 proves the case q = 2. When q = p is a prime number which does not
divide m = logp (n + 1), we use the fact that xp − x + β is irreducible over Fpm if and
only if trFpm /Fp (β) 6= 0 [17, Corollary 3.79]. Then xp − x + β is irreducible over Fpm and
therefore xp − x + β is coprime with xn − 1 for n = pm − 1.

3. Quasi-cyclic construction of stabilizer quantum codes with the
Euclidean inner product
Let Qq (f, g, h) be the QC code over Fq of length 2n generated by ([f (x)], [h(x)f (x)])
and (0, [g(x)]) as introduced in Subsection 1. We are going to study the stabilizer quantum
codes given by self-orthogonal codes with respect to Euclidean inner product of the form
Qq (f, g, h). This way of obtaining quantum codes is usually known as the CSS construction
[5, 23]. For a start, we explain which code is the Euclidean dual of Qq (f, g, h).
Proposition 9. The Euclidean dual code of the QC code Qq (f, g, h) over Fq is a QC code
generated by the pairs ([−h(x)g⊥ (x)], [g ⊥ (x)]) and ([f ⊥ (x)], 0).
Proof. A codeword in Qq (f, g, h) can be written as ([a1 (x)f (x)], [a1 (x)h(x)f (x)+a2 (x)g(x)]).
Similarily, a codeword in the code generated by ([−h(x)g⊥ (x)], [g ⊥ (x)]) and ([f ⊥ (x)], 0)
can be written as ([−b1 (x)h(x)g ⊥ (x) + b2 (x)f ⊥ (x)], [b1 (x)g ⊥ (x)]). The Euclidean inner
product of the above two codewords is, by Proposition 2,
−h[a1 (x)f (x)], b1 (x)h(x)g ⊥ (x)i + h[a1 (x)f (x)], [b2 (x)f ⊥ (x)]i
|
{z
}
=0

+h[a1 (x)h(x)f (x)], [b1 (x)g ⊥ (x)]i + h[a2 (x)g(x)], [b1 (x)g ⊥ (x)]i
{z
}
|
=0

= −h[a1 (x)f (x)], b1 (x)h(x)g ⊥ (x)i + h[a1 (x)h(x)f (x)], [b1 (x)g⊥ (x)]i
= −h[a1 (x)f (x)], b1 (x)h(x)g ⊥ (x)i + h[a1 (x)f (x)], [b1 (x)h(x)g⊥ (x)]i = 0.
We have shown that the Euclidean dual code of Qq (f, g, h) contains the QC code generated by ([−h(x)g ⊥ (x)], [g⊥ (x)]) and ([f ⊥ (x)], 0). As is Proposition 3, the dimension of
Qq (f, g, h) is 2n−deg f (x)−deg g(x), and that of the latter is 2n−deg f ⊥ (x)−deg g ⊥ (x) =
deg f (x) + deg g(x), which completes the proof.

Now, we give conditions for self-orthogonality.
Proposition 10. A sufficient condition for Qq (f, g, h) to contain its Euclidean dual is
f (x)|g(x)|g ⊥ (x)|f ⊥ (x).
Proof. It follows from the following two equalities:
  h(x)g⊥ (x) 

⊥
⊥
([f (x)], [h(x)f (x)])
[h(x)g (x)], [g (x)] −
f (x)
i
 h

= 0, 1 − h(x)h(x) g⊥ (x)


(1 − h(x)h(x))g ⊥ (x)
=
(0, [g(x)]) .
g(x)

QUASI-CYCLIC CONSTRUCTIONS OF QUANTUM CODES



[f ⊥ (x)], 0

=



9




f ⊥ (x)
[h(x)f ⊥ (x)]
([f (x)], [h(x)f (x)]) −
(0, [g(x)]) .
f (x)
[g(x)]


With respect to distance, we can state the following result.
Proposition 11. The following value
deq (f, g, h) =

 

min d([g(x)]), d [(xn − 1)/ gcd(xn − 1, h(x))] , d lcm f (x), g(x)/ gcd(g(x), h(x))
,

d([f (x)]) + d([gcd(h(x)f (x), g(x))])
is a lower bound for the minimum distance of the QC code Qq (f, g, h).

Proof. A codeword in Qq (f, g, h) can be written as [a(x)f (x)], [a(x)h(x)f (x)+ b(x)g(x)] .
If [b(x)] = 0 and [a(x)h(x)f (x)] 6= 0, then its Hamming weight is at least d(f (x)) +
d(h(x)f (x)).
If [b(x)] = 0 and [a(x)h(x)f (x)] = 0, then then a(x)f (x) belongs to the ideal in Fq [x]
generated by (xn −1)/gcd(xn −1, h(x)). So wH ([a(x)h(x)]) ≥ d((xn −1)/gcd(xn −1, h(x))).
If [a(x)] = 0 then the Hamming weight is larger than or equal to d(g(x)).
Finally and until the end of proof, we assume [a(x)] 6= 0 and [b(x)] 6= 0. If [a(x)h(x)f (x)+
b(x)g(x)] = 0 then [a(x)f (x)] belongs to the cyclic code generated by [g(x)/gcd(g(x), h(x))].
Indeed, set m(x) = gcd(g(x), h(x)) and, as a consequence, g(x) = m(x)g ′ (x), h(x) =
m(x)h′ (x) and gcd(g ′ (x), h′ (x)) = 1. Then [a(x)h(x)f (x) + b(x)g(x)] = 0 implies
a(x)h(x)f (x) ∈ (g(x))
because g(x)|xn − 1. Thus a(x)m(x)h′ (x)f (x) = p(x)m(x)g ′ (x) for some polynomial p(x)
which proves that a(x)f (x) belongs to the ideal generated by g ′ (x). So
wH ([a(x)f (x)]) ≥ d (lcm(f (x), g(x)/gcd(g(x), h(x)))) .
Otherwise ([a(x)h(x)f (x) + b(x)g(x)] 6= 0) and then
wH (([a(x)f (x)], [a(x)h(x)f (x) + b(x)g(x)]))
≥ d (f (x)) + d(gcd(h(x)f (x), g(x))) ,
which concludes the proof.



Theorem 12. With the above notation, assume that the polynomials f (x) and g(x) satisfy that f (x)|g(x)|g ⊥ (x)|f ⊥ (x), then the QC code Qq (f, g, h) is self-orthogonal for the
Euclidean inner product and, as a consequence, it provides a stabilizer quantum code with
parameters
[[2n, 2n − 2 deg(f (x)) − 2 deg(g(x)), ≥ deq (f, g, h)]]q .
Proof. It follows from Propositions 9, 10 and 11, and Subsection 1.2.



10

CARLOS GALINDO, FERNANDO HERNANDO AND RYUTAROH MATSUMOTO

4. Quasi-cyclic construction of quantum codes with the Hermitian inner
product
In this section the coefficient field for our QC codes and polynomials will be Fq2 . This
fact will allow us to consider Hermitian inner product instead of Euclidean inner product.
x, ~y ih can be regarded
Recall that for two vectors ~x, ~y ∈ F2n
q 2 , the Hermitian inner product h~
q
q
as the Euclidean product h~x , ~y i, where ~x denotes component-wise qth power of the vector
~x.
Denote by Qq2 (f, g, h) the QC code in F2n
q 2 generated by ([f (x)], [h(x)f (x)]) and (0, [g(x)]).
Attached to a polynomial r(x) = a0 + a1 x + · · · + am xm of degree m < n, we define
r [q] (x) = aq0 + aq1 x + · · · + aqm xm . If ~x is represented by [f (x)] then ~xq is represented by
[f [q] (x)].
Proposition 13. The Hermitian dual code of the QC code over Fq2 Qq2 (f, g, h) is a QC
⊥

⊥

⊥

code generated by the pairs ([−h[q] (x)g [q] (x)], [g [q] (x)]) and ([f [q] (x)], 0).
Proof. The dimension of the Hermitian dual code of Qq2 (f, g, h) is
⊥

⊥

deg(f (x)) + deg(g(x)) = 2n − deg f [q] (x) − deg g [q] (x).
Therefore, it suffices to check the following chain of equalities:
D
h
i
E
⊥
⊥
([f (x)], [h(x)f (x)]) , −h[q] (x)g [q] (x) , [g [q] (x)]
h
D
h
iE D
h ⊥ iE
[q] ⊥
[q]
= − [f (x)], h (x)g
(x) + [h(x)f (x)], g[q] (x)
h ⊥ iE h
D
h ⊥ iE D
[q]
(x) + [h(x)f (x)], g [q] (x)
= − [h(x)f (x)], g
h

= 0.


The following result can be proved with a similar reasoning as in Proposition 10.
Proposition 14. A sufficient condition for Qq2 (f, g, h) to contain its Hermitian dual is
⊥

⊥

f (x)|g(x)|g [q] (x)|f [q] (x).
As a consequence of the previous results, we obtain the following one involving stabilizer
quantum codes.
Theorem 15. With the above notation, assume that the above polynomials, with coef⊥
⊥
ficients in Fq2 , f (x) and g(x) satisfy that f (x)|g(x)|g [q] (x)|f [q] (x), then the QC code
Qq2 (f, g, h) is self-orthogonal for the Hermitian inner product and, as a consequence, it
provides an stabilizer quantum code with parameters
[[2n, 2n − 2 deg(f (x)) − 2 deg(g(x)), ≥ deq2 (f, g, h)]]q .
Proof. It follows from what we said in Subsection 1.2 with respect to Hermitian duality
and the fact that deq2 (f, g, h) is a lower bound for the minimum distance of the QC code
Qq2 (f, g, h).


QUASI-CYCLIC CONSTRUCTIONS OF QUANTUM CODES

11

5. Examples
We devote this section to provide some examples of good stabilizer quantum codes
coming from our constructions.
The two first examples use symplectic product as explained in Section 2.
Example 1. Set n = 151, q = 2 and the polynomial x151 − 1 ∈ F2 [x]. The splitting field
of x151 − 1 is F215 and set ζ a primitive element. Taking cyclotomic cosets modulo n = 151
with respect to q = 2, one can get minimal polynomials of roots of x151 − 1 which divide
that polynomial.
Consider the cyclotomic coset
{2, 4, 8, 16, 32, 64, 128, 105, 59, 118, 85, 19, 38, 76, 1},
and the attached polynomial f (x) = (x − ζ 2 )(x − ζ 4 ) · · · (x − ζ) which belongs to F2 [x]
and divides x151 − 1. Analogously, let g(x) ∈ F2 [x] be the polynomial defined by the next
two cyclotomic cosets:

[2, 4, 8, 16, 32, 64, 128, 105, 59, 118, 85, 19, 38, 76, 1], and
[10, 20, 40, 80, 9, 18, 36, 72, 144, 137, 123, 95, 39, 78, 5] .

If now h(x) = x+ 1, using the QC code Q2 (f, g, h) and Theorem 5 we are able to construct
a stabilizer quantum code with parameters [[151, 106, 8]]2 .
To testify the goodness of this code, we note that [7] only gives a quantum code
with parameters [[151, 106, 6]]2 . In addition, according to [11], a code with parameters
[151, 128, 8]2 is the best known binary linear code with length 151 and minimum distance
8. In the unlikely case it were self-orthogonal for the Euclidean inner product, by using
the CSS construction, we would get a [[151, 105, 8]]2 code, with one unit less of dimension
than our code.
Example 2. In this example we use again Theorem 5 for providing a stabilizer quantum
code with good parameters.
Set n = 73 and q = 23 . The splitting field of x73 −1 is F29 . As in Example 1, considering
a primitive element of this field, we consider the polynomial f (x) (respectively, g(x)) in
F8 [x] defined by the cyclotomic coset
{8, 64, 1, 16, 55, 2, 24, 46, 3}
(respectively,
{8, 64, 1, 16, 55, 2, 24, 46, 3, 56, 10, 7}.)
Taking h(x) = x + 1, from Q2 (f, g, h) we obtain a stabilizer quantum code with parameters
[[73, 52, 7]]8 . A code with parameters [73, 63, 7]8 is the best known binary linear code with
length 73 and minimum distance 7 [11]. In the unlikely case it were self-orthogonal for
the Euclidean inner product, by using the CSS construction, we would get a [[73, 53, 7]]8
code, which has only one unit more of dimension than ours.
Example 3. Now we are going to give a couple of binary quantum codes obtained from
the procedure described in Section 3. Set n = 146 and consider the following polynomials
in F2 [x]: f (x) = 1, h(x) = x5 + x4 + x2 + x + 1 and gi (x) = h(x)fi (x), 1 ≤ i ≤ 3, where
f1 (x) = x9 + x7 + x4 + x3 + 1,
f2 (x) = x18 + x16 + x12 + x10 + x9 + x6 + x4 + x3 + x2 + x + 1 and

12

CARLOS GALINDO, FERNANDO HERNANDO AND RYUTAROH MATSUMOTO

f3 (x) = x27 + x26 + x25 + x24 + x21 + x20 + x19 + x18 + x17 + x16
+ x15 + x14 + x13 + x12 + x10 + x9 + x8 + x6 + x4 + x3 + x2 + x + 1.
The polynomials f1 (x), f2 (x) and f3 (x) are determined, respectively, by cyclotomic cosets
I1 , I2 and I3 , with respect to 2 modulo n = 73, such that I1 ⊂ I2 ⊂ I3 . They provide
linear codes with parameters [73, 64, 3]2 , [73, 55, 5]2 and [73, 46, 9]2 .
Consider the QC codes Qi := Q2 (f, gi , h), 1 ≤ i ≤ 3. By construction of the polynomials
gi (x) and by Proposition 10, it holds that
⊥
⊥
Q⊥
1 ⊆ Q2 ⊆ Q3 ⊆ Q3 ⊆ Q2 ⊆ Q1 .

Therefore, using the CSS procedure, we get binary stabilizer quantum codes C1 , C2 and
C3 with parameters [[146, 128, 3]]2 , [[146, 110, 5]]2 and [[146, 74, 8]]2 . Now, the Steane’s
enlargement of the codes C1 and C2 [25] gives rise to a binary stabilizer quantum code with
parameters [[146, 119, 5]]2 which exceeds the Gilbert-Varshamov bounds [8, 9, 20]. Steane’s
enlargement for C2 and C3 produces another stabilizer quantum code with parameters
[[146, 92, 8]]2 .
Example 4. Our last example is obtained by applying Theorem 15 where Hermitian inner
product is used. Write n = 80, q = 3 and consider the following polynomials in F9 [x],
which involve a primitive element ζ of F9 , f (x) = x + ζ 5 , h(x) = x2 + ζ 7 x + ζ and
g(x) = x9 + 2x8 + ζ 2 x6 + 2x5 + ζ 5 x4 + ζx3 + ζ 3 x2 + ζ 2 .
These polynomials satisfy the requirements of Theorem 15 and, as a consequence we get
a stabilizer quantum code with parameters [[160, 140, 5]]3 .
Notice that this code exceeds the Gilbert-Varshamov bounds [8, 9, 20]. In addition,
according to [11], a linear code with parameters [160, 149, 5]3 is the best known linear
ternary code with length n = 160 and minimum distance d = 5. In the unlikely case,
it were self-orthogonal, the CSS procedure would give a quantum code with parameters
[[160, 138, 5]]3 , which is worse than ours. We conclude by observing that we cannot reproduce this last procedure for self-orthogonality with respect to Hermitian duality because
examples of length 160 over F9 are not provided in [11].
References
[1] A. Ashikhmin and E. Knill. Nonbinary quantum stabilizer codes. IEEE Trans. Inform. Theory,
47(7):3065–3072, Nov. 2001.
[2] A. Ashikhmin, S. Litsyn and M. A. Tsfasman. Asymptotically good quantum codes. Phys. Rev. A,
63(3):032311, Mar. 2001.
[3] A. R. Calderbank, E. M. Rains, P. W. Shor and N. J. A. Sloane. Quantum error correction and
orthogonal geometry. Phys. Rev. Lett., 78(3):405–408, Jan. 1997.
[4] A. R. Calderbank, E. M. Rains, P. W. Shor and N. J. A. Sloane. Quantum error correction via codes
over GF(4). IEEE Trans. Inform. Theory, 44(4):1369–1387, July 1998.
[5] A. R. Calderbank and P. W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A,
54(2):1098–1105, Aug. 1996.
[6] D. Castelvecchi. Quantum computers ready to leap out of the lab in 2017. Nature, 541(7635):9–10,
Jan. 2017.
[7] Y. Edel Some good quantum twisted codes. Available at https://www.mathi.uni-heidelberg.de/ yves/.
[8] A. Ekert and C. Macchiavello. Quantum Error Correction for Communication. Phys. Rev. Lett.
77:2585-2588, Sept. 1996.
[9] K. Feng and Z. Ma. A finite Gilbert-Varshamov bound for pure stabilizer quantum codes. IEEE Trans.
Inf. Theory 50:3323-3325, Dec. 2004.
[10] D. Gottesman. Class of quantum error-correcting codes saturating the quantum Hamming bound.
Phys. Rev. A, 54(3):1862–1868, Sept. 1996.
[11] M. Grassl. Codetables. available at http://www.codetables.de/.
[12] M. Hagiwara and H. Imai. Quantum quasi-cyclic ldpc codes. In Proc. 2007 IEEE ISIT, pages 806–810,
Nice, France, June 2007.

QUASI-CYCLIC CONSTRUCTIONS OF QUANTUM CODES

13

[13] M. Hagiwara, K. Kasai, H. Imai and K. Sakaniwa. Spacially-coupled quasi-cyclic quantum ldpc codes.
In Proc. 2011 IEEE ISIT, pages 638–642, Nice, France, June 2007.
[14] T. Kasami. A Gilbert-Varshamov bound for quasi-cyclic codes of rate 1/2. IEEE Trans. Inform.
Theory, 20:679, Sept. 1974.
[15] A. Ketkar, A. Klappenecker, S. Kumar, P. K. Sarvepalli. Nonbinary stabilizer codes over finite fields,
IEEE Trans. Inform. Theory 52: 4892-4914, Nov 2006.
[16] K. Lally and P. Fitzpatrick. Algebraic structure of quasicyclic codes. Discrete Appl. Math., 11:157–175,
July 2001.
[17] R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, 2nd edition, 2008.
[18] S. Ling, J. Luo and C. Xing. Generalization of Steane’s enlargement construction of quantum codes
and applications. IEEE Trans. Inform. Theory, 56(8):4080–4084, Aug. 2010.
[19] S. Ling and P. Solé. Good self-dual quasi-cyclic codes exist. IEEE Trans. Inform. Theory, 49(4):1052–
1053, Apr. 2003.
[20] R. Matsumoto and T. Uyematsu. Constructing quantum error-correcting codes for pm -state systems
from classical error-correcting codes. IEICE Trans. Fundamentals, E83-A(10):1878–1883, Oct. 2000.
[21] J. Qian, W. Ma and X. Wang. Quantum error-correcting codes from quasi-cyclic codes. Int. J. Quantum Inf., 6(6):1263–1269, Dec. 2008.
[22] P. W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52(4):2493–
2496, Oct. 1995.
[23] A. M. Steane. Simple quantum error correcting codes Phys. Rew. Letters , 77(1954):793–797, Dec.
1996.
[24] A. M. Steane. Multiple particle interference and quantum error correction. Proc. Roy. Soc. London
Ser. A, 452:2551–2577, Nov. 1996.
[25] A. M. Steane. Enlargement of Calderbank-Shor-Steane quantum codes. IEEE Trans. Inform. Theory
45:2492-2495, Dec. 1999.
Current address: Carlos Galindo and Fernando Hernando: Instituto Universitario de Matemáticas y
Aplicaciones de Castellón and Departamento de Matemáticas, Universitat Jaume I, Campus de Riu Sec.
12071 Castelló (Spain), Ryutaroh Matsumoto: Department of Information and Communication Engineering, Nagoya University, Nagoya, 464-8603 Japan.
E-mail address: galindo@uji.es; carrillf@uji.es; ryutaroh.matsumoto@nagoya-u.jp

