Entanglement of Subspaces and Error Correcting Codes
Entanglement of Subspaces and Error Correcting Codes
Gilad Gour1, ∗ and Nolan R. Wallach2, †
1Institute for Quantum Information Science and Department of Mathematics and Statistics,
University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
2Department of Mathematics, University of California/San Diego, La Jolla, California 92093-0112
(Dated: November 4, 2018)
We introduce the notion of entanglement of subspaces as a measure that quantify the entanglement
of bipartite states in a randomly selected subspace. We discuss its properties and in particular we
show that for maximally entangled subspaces it is additive. Furthermore, we show that maximally
entangled subspaces can play an important role in the study of quantum error correction codes.
We discuss both degenerate and non-degenerate codes and show that the subspace spanned by
the logical codewords of a non-degenerate code is a k-totally (maximally) entangled subspace. As
for non-degenerate codes, we provide a mathematical definition in terms of subspaces and, as an
example, we analyze Shor’s nine qubits code in terms of 22 mutually orthogonal subspaces.
PACS numbers: 03.67.Mn, 03.67.Hk, 03.65.Ud
I. INTRODUCTION AND DEFINITIONS
Bipartite entanglement has been recognized as a cru-
cial resource for quantum information processing tasks
such as teleportation [1] and super dense coding [2]. As a
result, in the last years there has been an enormous effort
to understand and study the characterization, manipu-
lation and quantification of bipartite entanglement [3].
Yet, despite a great deal of progress that was achieved,
the theory on mixed bipartite entanglement is incom-
plete and a few central important questions such as the
additivity of the entanglement of formation [4] remained
open. Perhaps the richness and complexity of mixed bi-
partite entanglement can be found in the fact that a finite
set of measures of entanglement is insufficient to com-
pletely quantify it [5]. In this paper we shed some light
on mixed bipartite entanglement with the introduction
of a new kind of measure of entanglement which we call
entanglement of subspaces (EoS). We will see that EoS
can play an important role in the study of quantum error
correcting codes (QECC).
It has been shown recently [6, 7] that geometry of
high-dimensional vector spaces can be counterintuitive
especially when subspaces with very unique properties
are more common than one intuitively expects. That is,
roughly speaking, if a high dimensional subspace is se-
lected randomly it is quite likely to have strange proper-
ties. For example, in [7] it has been demonstrated that a
randomly chosen subspace of a bipartite quantum system
will likely contain nothing but nearly maximally entan-
gled states even if the dimension of the subspace is almost
of the same order as the dimension of the original sys-
tem. This kind of result has implications, in particular, to
super-dense coding [8] and for quantum communication
in general (see also [9] for other implications of randomly
∗Electronic address: gour@math.ucalgary.ca
†Electronic address: nwallach@ucsd.edu
selected subspaces). The quantification of the entangle-
ment of such subspaces is therefore very important and
we start with its definition.
Definition 1. Let HA and HB be finite dimensional
Hilbert spaces and let WAB be a subspace of HA ⊗HB.
The entanglement of WAB is defined as:
≡ min
ψAB∈WAB
: ‖ψAB‖ = 1
, (1)
where E
is the entropy of entanglement of ψAB.
Note that if the subspace WAB contains a product
state then E(WAB) = 0. On the other hand, if, for
example, WAB is orthogonal to a subspace spaned by
an unextendible product basis (UPB) [11, 12] then
E(WAB) > 0.
Claim: Let dA = dimHA and dB = dimHB. If
E(WAB) > 0 then
dimWAB ≤ (dA − 1)(dB − 1). (2)
This claim follows from [10] and also related to the fact
that the number of (bipartite) states in a UPB is at least
dA + dB − 1 [11]. Note that for two qubits (i.e. dA =
dB = 2) E(WAB) can be greater than zero only for one
dimensional subspaces.
We can use Eq. (1) to define another measure of en-
tanglement on bipartite mixed states.
Definition 2. Let ρ ∈ B
HA ⊗HB
be a bipartite
mixed state and let SABρ be the support subspace of ρ.
Then, the entanglement of the support of ρ is defined as
ESupport(ρ) ≡ E(SABρ ) .
It can be easily seen that this measure is not continuous
and therefore can not be considered as a proper measure
of entanglement. Nevertheless, this measure can serve as
a mathematical tool to find lower bounds for other mea-
sures of entanglement that are more difficult to calculate
http://arxiv.org/abs/0704.0251v2
mailto:gour@math.ucalgary.ca
mailto:nwallach@ucsd.edu
especially in higher dimensions. For example, the entan-
glement of the support of ρ provides a lower bound for
the entanglement of formation. It can be shown that in
lower dimensions the bound is generally not tight. For
example, for two qubits in a mixed state ρ, the entangle-
ment of the support ESupport(ρ) = 0 (see Eq. (2)). On
the other hand, in higher dimensions the bound can be
very tight [6, 7].
II. ENTANGLEMENT OF SUBSPACES
In this section we study some of the properties of EoS
with a focus on additivity properties. The EoS provides a
lower bound on the entanglement of formation and our in-
terest in its additivity properties is due to one of the most
important unresolved questions in quantum information,
namely the additivity conjecture for the entanglement
of formation. In particular, the additivity question of
EoS is identical to the additivity conjecture of quantum
channel output entropy [13] that has been shown to be
equivalent to the additivity conjecture of entanglement
of formation [4]. Thus, additivity properties of EoS can
shed some light on this topic.
A. Additivity properties of the entanglement of
subspaces
Here we consider the additivity properties of EoS. We
start by showing that if UAB and V A
′B′ are two sub-
spaces such that E(UAB) > 0 and/or E(V A′B′) > 0 then
E(UAB ⊗ V A′B′) > 0.
Consider W = Cn ⊗ Cm. Let ej, j = 1, ..., n be the
standard basis of Cn. We will also use the notation fj for
the standard basis of Cm. An element of a tensor product
of two vector spaces, A and B will be called a product if
it is of the form a⊗ b with a ∈ A and b ∈ B.
Proposition 1. Let u1, ..., ud, v1, ..., vd ∈ W be such that
if x =
i bivi is a product then x = 0. If z =
i ui ⊗ vi
is a product in (Cn ⊗ Cn)⊗ (Cm ⊗ Cm) then z = 0.
Proof. We write ui =
j=1 ej ⊗ uij and vj =
j=1 ej ⊗ vij . Assume that
iui⊗vi is a product
in (Cn⊗Cn)⊗(Cm⊗Cm). This means that there exists
z ∈ Cn⊗Cn and w ∈ Cm⊗Cm such that
i,k,l
(ek⊗el)⊗(uik⊗vil) = z⊗w.
If we write out z =
k,lzklek⊗el with zkl ∈ C then we
must have
uik⊗vil = zklw
for all k, l. We now write uik =
ikfm and w =
mfm⊗wm. The displayed formula now implies that
(k.l,m fixed)
umikvil = zklwm.
This implies that (with k and m fixed) we have
umikel⊗vil = (
zklel)⊗wm.
Hence
ikvi is a product. Our assumption implies
that it must be 0. Hence
i,k,m
umikek⊗fm⊗vi =
ui⊗vi.
As was to be proved.
Note that the proposition above states that if none of
the decompositions of a bipartite mixed state, ρ, contain
a product state, then also none of the decompositions
of ρ ⊗ σ (σ is a bipartite mixed state) contain a prod-
uct state. This property is related to the additivity con-
jecture [4] for the entanglement of formation (and other
measures) and one of the main questions that we will
consider here is wether the EoS is additive. That is, does
E(UAB ⊗ V A
′B′) = E(UAB) + E(V A
′B′) ?
Clearly, if the EoS were additive then the proposition
above would have been a trivial consequence of that.
However, we were not able to prove the additivity of
EoS (in general) although for some special cases it has
been tested numerically in [14] and no counter example
has been found. The proposition below provides a lower
bound.
Proposition 2. Let N = min{dimUAB, dimV A′B′}.
E(UAB) + E(V A
)− logN ≤ E
UAB ⊗ V A
. (3)
The equation above provides a lower bound whereas
the upper bound E
UAB ⊗ V A′B′
≤ E(UAB)+E(V A′B′)
follows directly from the definition of EoS. Thus, for N =
1 the EoS is additive. Note also that even if N is small
(e.g. N = 2), E(UAB) and E(V A′B′) can be arbitrarily
large (i.e. depending on dA and dB but not on N).
Proof. Let χ be a normalized vector in UAB⊗V A′B′ . We
can write χ in its Schmidt decomposition as follows:
i ⊗ vA
where
i pi = 1 (pi ≥ 0) and the uABi ’s (vA
i ’s) are
orthonormal. Now, from the strong subadditivity of the
von-Neumann entropy we have
S(ρA′) + S(ρB) ≤ S(ρAB) + S(ρAA′) ,
where ρA ≡ TrA′BB′χ ⊗ χ∗, ρB ≡ TrAA′B′χ ⊗ χ∗,
etc. Now, note that S(ρAA′) = E(χ) and S(ρAB) =
H({pi}) ≤ logN , where H({pi}) is the Shanon entropy.
Furthermore, note that
ρA′ =
piωi and ρB =
where
ωi ≡ TrB′vA
i ⊗ vA
and σi ≡ TrAuABi ⊗ uABi
Hence, since the von-Neumann entropy is concave we
S(ρA′) ≥
piS(ωi) =
piE(v
i ) ≥ E
and similarly S(ρB) ≥ E
. Combining all this we
≤ logN + E(χ) ,
for all χ ∈ UAB ⊗ V A′B′ . This complete the proof.
B. Maximally entangled subspaces
As we have seen above, if N = 1 then the EoS is clearly
additive. As we will see in the next subsection, it is also
additive for maximally entangled subspaces:
Definition 3. Let W be a subspace of HA ⊗ HB and
let dA = dimHA and dB = dimHB. W is said to be a
maximally entangled subspace in HA ⊗HB if
E(W ) = logm , (4)
where m ≡ min{dA, dB}.
The term maximally entangled subspace have been
used in [6, 7] for a subspace W with E(W ) slightly less
than logm. In this paper, we will call such subspaces
nearly maximally entangled to distinguish from (exactly)
maximally entangled subspaces as defined above.
In [15] it has been shown that the average entangle-
ment of a pure state φ ∈ HA ⊗ HB which is chosen
randomly according to the unitarily invariant measure
satisfies
〈E(φ)〉 ≥ log2 dA −
2 ln 2dB
where without loss of generality dA ≥ dB. Later on,
in [6, 7] this result has been extended to subspaces and
in particular it has been shown, somewhat surprisingly,
that a randomly chosen subspace of bipartite quantum
system will likely be a nearly maximally entangled sub-
space. Thus, as nearly maximally entangled subspaces
are quite common it is important to understand their
structure. As a first step in this direction, in the following
we study the structure of (exactly) maximally entangled
subspaces.
Let φ be a state in HA⊗HB. If e1, ..., em is an or-
thonormal basis of HB we may write
φi⊗ei .
We define a dB× dB Hermitian matrix B = [〈φi|φj〉] (i.e.
B is the reduced density matrix). Let λ1, ..., λdB be the
set of eigenvalues of B counting multiplicity. Then the
entanglement of φ is
E(φ) = −
λi log(λi) .
It is easy to show that E(φ) ≤ logm and equality is
attained if and only if B = 1
P with P a projection
matrix onto a d dimensional subspace of CdB . Clearly
this definition of entropy is independent of the choice of
basis and could also be given using an orthonormal basis
of HA and analyzing the corresponding dA coefficients
in HB. Under the condition of equality φ is maximally
entangled, and this in particular implies that if dA ≥ dB
〈φi|φj〉 =
δij .
Proposition 3. Assume that dA ≥ dB and set m = dB .
Let UAB be a maximally entangled subspace in HA⊗HB
of dimension d. If e1, ..., em is an orthonormal basis of
HB then there exist U1, ..., Um subspaces of HA such that
〈Ui|Uj〉 = 0 if i 6= j, dimUj = d > 0 for all j = 1, ...,m
and unitary operators Ti : C
d → Ui i = 1, ...,m such that
UAB = {
Tiw⊗ei|w ∈ Cd}.
Conversely, if U1, ..., Um are mutually orthogonal sub-
spaces of HA such that dimUj = d > 0 for all j = 1, ...,m
and we have unitary operators Ti : C
d → Ui i = 1, ...,m
such that
UAB = {
Tiw⊗ei|w ∈ Cd} ,
then UAB is maximally entangled.
Proof. Let ψ1, ..., ψd be an orthonomal basis of U
Then we can write
ψij⊗ei
with 〈ψij |ψkj〉 = 1mδik. The condition on U
AB is that
if a ∈ Cd is a unit vector then
ajψj is maximally
entangled in HA⊗HB. This implies that
ajψlj
ajψkj
δl,k .
Fix l 6= k and let p 6= q ≤ d be two integers. Let a =
(a1, ..., ad) with aj = 0 for j 6= p or j 6= q. Set ap =
b, aq = c and |b|2 + |c|2 = 1. Then we have
〈bψlp + cψlq|bψkp + cψkq〉 = 0.
On the other hand we have
〈bψlp + cψlq|bψkp + cψkq〉 = bc 〈ψlp|ψkq〉+ cb 〈ψlq|ψkp〉
Set z = bc. We look at two cases: first z = 1
(b = c =
) and second z = i√
(b = 1√
, c = i√
). Thus we have
〈ψlp|ψkq〉+ 〈ψlq|ψkp〉 = 0
for the first case and
〈ψlp|ψkq〉 − 〈ψlq|ψkp〉 = 0
for the second. Hence, 〈ψlp|ψkq〉 = 〈ψlq|ψkp〉 = 0. We set
Ul = Span{ψlp|p = 1, ..., d}. Then 〈Ul|Uk〉 = 0 if l 6= k.
We now consider what happens when l = k. We first
note that taking ap = 1 and all other entries equal to 0
we have 〈ψlp|ψlp〉 = 1m . Now using b, c as above for p 6= q
we have
〈ψlp|ψlp〉+ 〈ψlp|ψlq〉+ 〈ψlq|ψlp〉+ 〈ψkp|ψkp〉 =
〈ψlp|ψlp〉+ i 〈ψlp|ψlq〉 − i 〈ψlq|ψlp〉+ 〈ψkp|ψkp〉 =
Hence as above we find that 〈ψlp|ψlq〉 = 0 if p 6= q. Thus√
mψl1, ...,
mψld is an orthonormal basis of Ul. This
implies that the spaces U1, ..., Um have the desired prop-
erties. Let u1, ..., ud, be the standard orthonormal basis
of Cd and define Tiuj =
mψij . With this notation in
place UAB has the desired form. The converse is proved
by the obvious calculation.
Corollary 4. If UAB is a maximally entangled subspace
in HA⊗HB (dA ≥ dB), then
dimUAB ≤
Furthermore, there always exists a maximally entangled
subspace of dimension ⌊dA/dB⌋.
Proof. Assume that dimHA = dA ≥ dimHB = dB.
According to the first part of Proposition 4, if UAB is
a maximally entangled subspace of dimension d then
d × dB ≤ dA. On the other hand, if d ≤ ⌊dA/dB⌋ then
the second half of the statement implies that there is a
maximally entangled subspace of dimension d.
In the following we find necessary and sufficient con-
ditions for a subspace to be maximally entangled. In
section III we use this to show that maximally entan-
gled subspaces can play an important role in the study
of error correcting codes. As above we consider the space
HA⊗HB with dimHA = dA ≥ dimHB = dB and a max-
imally entangled subspace UAB ⊂ HA⊗HB. We will also
consider End(HB) to be a Hilbert space with inner prod-
uct 〈X |Y 〉 = Tr(X†Y ) for any two operators X and Y in
End(HB).
Proposition 5. Let UAB ⊂ HA⊗HB be a subspace and
dA ≥ dB. Then, UAB is maximally entangled if and only
if the map End(HB)⊗UAB → HA⊗HB given by X⊗u 7→√
dB(I ⊗X)u is an isometry onto its image.
Proof. Let d = dimUAB and let the notation be as in
Proposition 3. Thus, if UAB is maximally entangled and
if e1, ..., edB is an orthonormal basis of HB then an ele-
ment of UAB is of the form
T (w) =
Ti(w) ⊗ ei ,
with Ti a unitary operator from C
d onto a subspace Ui
of HA and Ui and Uj are orthogonal for all i 6= j. We
now calculate
〈(I⊗X)T (w)|(I⊗Y )T (z)〉 =
〈Ti(w)|Tj(z)〉 〈Xei|Y ej〉 .
Now, since 〈Ti(w)|Tj(z)〉 = δij〈w|z〉 (see Proposition 3)
we have:
〈(I ⊗X)T (w)|(I ⊗ Y )T (z)〉 =
δij〈w|z〉 〈Xei|Y ej〉
= 〈w|z〉Tr(X†Y ) .
That is, we proved that if UAB is maximally entangled
then the map is an isometry. For the converse we note
that we have an isometry of Cd onto UAB given by
T (w) =
Ti(w) ⊗ ei .
Now, if the map defined in the proposition is an isometry
〈(I ⊗X)T (w)|(I ⊗ Y )T (z)〉 = 〈w|z〉Tr(X†Y ) .
That is,
〈Ti(w)|Tj(z)〉 〈Xei|Y ej〉 = 〈w|z〉Tr(X†Y ) ,
for all X,Y ∈ End(HB). Hence, we must have
〈Ti(w)|Tj(z)〉 = δij〈w|z〉/ and from Proposition 3 the
subspace UAB is maximally entangled.
C. Additivity of maximally entangled subspaces
We now discuss the additivity properties of maximally
entangled subspaces.
Proposition 6. Let UAB ⊂ HA⊗HB and V A′B′ ⊂
HA′⊗HB′ be maximally entangled subspaces. Then,
UAB ⊗ V A
= logm+ logm′ , (5)
where m ≡ min{dA, dB} and m′ ≡ min{dA′ , dB′}.
Remark. From the above proposition it follows that
if dA ≥ dB and dA′ ≥ dB′ or dB ≥ dA and
dB′ ≥ dA′ then UAB⊗V A
′B′ is maximally entangled
in (HA⊗HA′)⊗(HB⊗HB′). However, if for example
dA > dB and dA′ < dB′ then U
AB⊗V A′B′ is NOT
maximally entangled in (HA⊗HA′)⊗(HB⊗HB′) because
mm′ < min{dAdA′ , dBdB′}.
Proof. There are basically two possibilities (up to inter-
changing factors): the first is dA ≥ dB and dA′ ≥ dB′ ,
and the second is dA ≥ dB and dA′ < dB′ .
In the first case we have as in the statement of
proposition 3 the subspaces Uj and the unitaries Tj :
d → Uj such that UAB = {
i Tiw⊗ei|w ∈ Cd}. We
also have the orthonormal basis fi of HB
, the sub-
spaces Vj and the unitaries Sj : C
d′ → Vj such that
′B′ = {
i Siw
′⊗fi|w′ ∈ Cd
′}. Thus, as a subspace of
(HA⊗HA′)⊗(HB⊗HB′), UAB⊗V A′B′ is spanned by the
elements
(Tiw⊗Sjw′)⊗(ei⊗fj).
Thus if we identify Cd⊗Cd′ with Cdd′ then the converse
assertion in proposition 3 implies that UAB⊗V A′B′ is a
maximally entangled space. This implies that
UAB⊗V A
= log dB + log dB′ = logm+ logm
We now consider the second case. For UAB we have ex-
actly as above UAB = {
i Tiw⊗ei|w ∈ Cd}. For V A
we denote by fj an orthonormal basis of HA
(not of
HB′ as above). Thus, according to proposition 3 we have
′B′ = {
i fi ⊗ Siw′|w′ ∈ Cd
′}. As a subspace of
(HA⊗HA′)⊗(HB⊗HB′), UAB⊗V A′B′ is spanned by the
elements
(Tiw⊗fj)⊗(ei⊗Sjw′).
We will assume first that d′ ≤ d. Let w′1, ..., w′d′ be
an orthonormal basis of Cd
. Thus, if φ is a state in
UAB⊗V A′B′ we can write it as
i,j,k
(Tiwk⊗fj)⊗(ei⊗Sjw′k) ,
where wk are some non-normalized vectors in C
d. Fur-
thermore,
〈φ|φ〉 = dBdA′
‖uk‖2 .
Hence, if φ is normalized then
‖uk‖2 =
dBdA′
Now, since Sjw
k is an orthonormal set of vectors for all
j and k (see proposition 3), the entanglement of φ as an
element of (HA⊗HA′)⊗(HB⊗HB′) is given by
dBdA′S(B)
where B = [〈wi|wj〉]1≤i,j≤d′ , and if λ1, ..., λd′ are the
eigenvalues of B then the von-Neumann entropy of B is
S(B) = −
λi logλi .
Now B is the most general d′ × d′ self adjoint, positive
semidefinate matrix with trace 1/dBdA′ . The minimum
of the entropy for such matrices is
log(dadB)
This proves the proposition for the case d′ ≤ d. If d < d′
then we can prove the proposition by using the same
argument, this time with wk an orthonormal basis of C
and with B′ =
w′i|w′j
1≤i,j≤d. This completes the
proof.
The above proposition also shows that the entangle-
ment of formation is additive for bipartite states with
maximally entangled support. If ρ is a mixed state in
HA⊗HB then the entanglement of formation is defined
in terms of the convex roof extension:
EF(ρ) = min
piE(φi)
where the minimum taken over all decompositions
piφi⊗φ∗i
with φi a pure bipartite state and pi > 0 and
pi = 1.
Corollary 7. Let ρ and σ be mixed states in B(HA⊗HB)
and B(HA′⊗HB′), respectively. If the support subspaces
Sρ and Sσ are maximally entangled then
EF(ρ⊗ σ) = EF(ρ) + EF(σ) .
The proof of this corollary follows directly from the
fact that for states with maximally entangled support
EF(ρ) = E(Sρ). Note that the class of mixed states with
maximally entangled support is extremely small (i.e. of
measure zero). In particular, it is a much smaller class
than the one found by Vidal, Dur and Cirac [16] .
III. ERROR CORRECTING CODES
A. Definitions
We consider error correcting codes that are used to en-
code l qubits in n ≥ l qubits in such a way that they can
correct errors on any subset of k or fewer qubits. These
codes, which we call (n, l, k) error correcting codes, can
be classified into two classes (for example see [17]): de-
generate and non-degenerate (or orthogonal) codes. We
start with a general definition of error correcting codes
that is equivalent to the definition given (for example)
in [17] , but here we define the codes in terms of sub-
spaces.
Definition 4. Let X ∈ End(⊗kC2) and 0 ≤ i0 < i1 <
... < ik−1 ≤ n − 1. The operator Xi0i1···ik−1 on ⊗nC2,
that represents the errors on the k qubits i1, ..., ik−1,
is defined by Xi0...ik−1v = σ(X ⊗ I)σ−1v, where (a)
σ ∈ Sn (acting on {0, 1, ..., n − 1} by permutations) is
defined such that σ(j) = ij , (b) σ can act on ⊗nC2 by
σ(v0 ⊗ v1 ⊗ · · · ⊗ vn−1) = vσ(0) ⊗ vσ(1) ⊗ · · · ⊗ vσ(n−1)
and (c) ⊗nC2 is viewed as (⊗kC2)⊗ (⊗n−kC2) (putting
together the k tensor factors that correspond to the k
qubits i1, ..., ik−1 and the rest n− k tensor factors). An
(n, l, k) error correcting code is defined from its following
ingredients:
I. An isometry T : ⊗lC2 → ⊗nC2.
II. Let V0 = T (⊗lC2). There are V1, ..., Vd mutually
orthogonal subspaces of ⊗nC2 that are also orthogonal
to V0.
III. For each Vj there is a unitary isomorphism, Uj, of
Vj onto V0 with U0 = I.
IV. Xi0i1···ik−1V0 ⊂ ⊕dj=0Vj .
V. Let Pj be the ortogonal projection of ⊗nC2 onto Vj
then if v ∈ V0 is a unit vector and Pj(Xi0i1···ik−1v) 6= 0
Pj(Xi0i1···ik−1v)
∥Pj(Xi0i1···ik−1v)
equals v up to a phase.
In the next subsection we study Shor’s (9, 1, 1) error
correcting code and show that it satisfies this definition.
However, before that, let us introduce the notion of k-
totally entangled subspaces which will play an important
role in our discussion of QECC.
Definition 5. Let H be the space of n qubits, ⊗nC2.
Corresponding to any choice of k qubits (tensor factors)
we can consider H = HA ⊗HB with HA = ⊗n−kC2 and
HB = ⊗kC2. For k ≤ n/2 we will say that a subspace,
V , of H is k-totally entangled if it is maximally entangled
relative to every decomposition of H as above.
It is interesting to note that all the subspaces spanned
by the logical codewords of the different non-degenerate
error correcting codes given in [18, 19, 20] are 2-totally
entangled subspaces. On the other hand, the subspaces
spanned by the logical codewords of degenerate codes,
like Shor’s 9 qubits code, are in general only partially
maximally entangled subspaces (i.e. maximally entan-
gled for some choices of k qubits but not for all choices).
In the following subsections we will see the reason for
that.
B. Analysis of Shor’s 9 qubits code
We start with the following notations. We set u± =
(|000〉 ± |111〉) so that the two logical codewords in
Shor’s 9 qubit code are v+ = u+ ⊗ u+ ⊗ u+ and v− =
u−⊗u−⊗u−. The subspace spanned by these codewords
is denoted by V0 = Cv+ ⊕ Cv−. We also denote u0± =
(|100〉 ± |011〉)/
2, u1± = (|010〉 ± |101〉)/
2 and u2± =
(|001〉 ± |110〉)/
Using these notations, we define 21 mutually orthogo-
nal 2 dimensional subspaces orthogonal to V0:
V1 = Cu− ⊗ u+ ⊗ u+ ⊕ Cu+ ⊗ u− ⊗ u−,
V2 = Cu+ ⊗ u− ⊗ u+ ⊕ Cu− ⊗ u+ ⊗ u−,
V3 = Cu+ ⊗ u+ ⊗ u− ⊕ Cu− ⊗ u− ⊗ u+,
V4+i = Cu
+⊗u+⊗u+⊕Cui−⊗u−⊗u−, for i = 0, 1, 2,
V7+i = Cu+⊗ui+⊗u+⊕Cu−⊗ui−⊗u−, for i = 0, 1, 2,
V10+i = Cu+⊗u+⊗ui+⊕Cu−⊗u−⊗ui−, for i = 0, 1, 2,
V13+i = Cu
−⊗u+⊗u+⊕Cui+⊗u−⊗u−, for i = 0, 1, 2,
V16+i = Cu+⊗ui−⊗u+⊕Cu−⊗ui+⊗u−, for i = 0, 1, 2,
V19+i = Cu+⊗u+⊗ui−⊕Cu−⊗u−⊗ui+, for i = 0, 1, 2.
If X ∈ End(C2) (linear maps of C2 to C2) then we
denote by Xi the linear map of ⊗9C2 to itself that is the
tensor product of the identity of C2 in every tensor factor
but the i-th and is X in the i-th factor thus
X0 = X ⊗ I ⊗ I ⊗ I ⊗ I ⊗ I ⊗ I ⊗ I ⊗ I,
X1 = I ⊗X ⊗ I ⊗ I ⊗ I ⊗ I ⊗ I ⊗ I ⊗ I
Then we have (here ⌊x⌋ = max{m|m ≤ x,m ∈ Z})
XiV0 ⊂ V0 ⊕ V⌊i/3⌋+1 ⊕ Vi+4 ⊕ Vi+13, 0 ≤ i ≤ 8.
We choose an observable R with
R|Vi = λiI, 0 ≤ i ≤ 21
R|W = µI,
where W is the orthogonal complement of ⊕21i=0Vi and
λi 6= λj for i 6= j and λi 6= µ for any i. We define a
unitary operator Uj : Vj → V0 as follows: we denote the
Pauli matrices by
, A2 =
, A3 =
and then define U0 = I, Ui = (A1)3i−1, for i = 1, 2, 3,
Ui = (A2)i−4, for 4 ≤ i ≤ 12 and Ui = (A3)i−13, for
13 ≤ i ≤ 21. This gives an one qubit error correcting
code since if v ∈ V0 is a state and if we have an error in
the i-th position then we will have
Xiv ∈ V0 ⊕ V⌊i/3⌋+1 ⊕ Vi+4 ⊕ Vi+13 .
Thus, if we measure the observable R on Xiv then the
measurement will yield one of λj with j = 0, ⌊i/3⌋+1, i+4
or i + 13 and Xiv will have collapsed up to a phase to
Ujv; hence applying Uj will fix the error.
Remark. Note that the subspace V0 is not 2-totally en-
tangled subspace. Nevertheless, V0 has very special
properties. In particular, if we group the 9 qubits as
(1, 2, 3) : (4, 5, 6) : (7, 8, 9), then for any choice of 2 qubits
that are not from the same group, the subspace V0 is
maximally entangled with respect to the decomposition
between the 2 qubits and the rest 7 qubits. If the 2 qubits
are chosen from the same group then the entanglement
of V0 with respect to this decomposition is 1ebit. Thus,
out of the 36 different decompositions, with respect to 27
of them E(V0) = 2ebits and with respect to the other 9
decompositions E(V0) = 1ebit.
C. Orthogonal codes
We now consider a somewhat more intuitive class of
codes known as non-degenerate codes which we also name
as orthogonal codes.
Definition 6. Let A0 = I, A1, A2, A3 the Pauli basis and
define A
j0j1···jk−1
i0i1···ik−1 to be
(Aj0 ⊗Aj1 ⊗ · · · ⊗Ajk−1)i0···ik−1 ,
where 0 ≤ jr ≤ 3 and 0 ≤ i0 < i1 < ... < ik−1 ≤
n − 1. Let Σ be the set of distinct operators of the
form A
j0j1···jk−1
i0i1···ik−1 . Then an orthogonal (n, l, k) code is
an (n, l, k) error correcting code such that if we label
Σ as the set of d + 1 operators S0 = I, S1, ..., Sd then
Vj = SjV0.
Note that Σ has
d+ 1 =
elements. Thus, a necessary condition that there exist
an (n, l, k) code is the quantum Hamming bound [17]:
≤ 2n−l.
Proposition 8. A 2l dimensional subspace V of ⊗nC2
is the V0 of an (n, l, k)-orthoganal error correcting code
if and only if V is 2k-totally entangled.
Proof. Let V be a 2k-totally entangled subspace in H =
⊗nC2, and let X : ⊗kC2 → ⊗kC2 be a linear map on
k qubits. As above, for any i0 < i1 < ... < ik−1 (1 ≤
il ≤ n) we denote by Xi0i1...ik−1 the operation X on H,
when acting on the k qubits i0, i1, ...., ik−1 (the rest of the
n − k qubits are left ”untouched”). Let also Z ≡ {X ∈
|TrX = 0} and for any i0 < ... < ik−1 let
Ui0...ik−1 ≡ {Xi0...ik−1V |X ∈ Z}. We define the subspace
W = V +
i0<...<ik−1
Ui0...ik−1 .
That is, W consists of all the possible states after an
error on k or less qubits has been occurred. Now, let
A0 = I, A1, A2, A3 be an orthonormal basis of End(C
with Ai invertible (e.g. the Pauli basis of 2×2 matrices).
As in Definition 6, we denote by A
j0...jk−1
i0...ik−1
the operator
Xi0...ik−1 that corresponds to X = Aj0 ⊗· · ·⊗Ajk−1 , and
the set of all such operators we denote by
Σ ≡ {Aj0...jk−1i0...ik−1 |1 ≤ il ≤ n, 0 ≤ jl ≤ 3} .
Now, let v1, ..., vd be an orthonormal basis of V and define
B ≡ {Svi
S ∈ Σ, 1 ≤ i ≤ d}.
We now argue that B is an orthonormal basis of W .
Clearly, the vectors in B span W . It is therefore enough
to show that the vectors in B are orthogonal. Let Svi
and S′vj be two vectors in B with S = A
j0...jk−1
i0...ik−1
S′ = A
...j′
...i′
. We denote byHB the Hilbert space of the
qubits i0, ..., ik−1 and i
0, ..., i
k−1, and by HA the Hilbert
space of the rest of the qubits. Note that HB consists
of at most 2k qubits. Now, since V is 2k-totally entan-
gled subspace, it is maximally entangled relative to the
decomposition H = HA ⊗HB. Thus, from Proposition 5
we clearly have
〈Svi|S′vj〉 = 〈vi|vj〉Tr
S̃†S̃′
= δijδSS′ ,
where S ≡ IA ⊗ S̃ and S′ ≡ IA ⊗ S̃′; that is, S̃ and S̃′
are the projections of S and S′ onto HB, respectively.
Hence, B is an orthonormal basis of W .
Since B is an orthonormal basis we can construct an
observable (i.e. Hermition operator) R such that for all
v ∈ V R(Sv) = λSSv with all of the λS distinct. We
also define R to be zero on the orthogonal complement
to W in H. Now, suppose that an element v has been
changed by a k-qubit transformation yielding Xi0...ik−1v.
We do a measurment of R and since the image is in W
the outcome is λS for some S. After the measurment, the
quantum state is Sv and so we recover v by applying S−1
(actually S if we used the Pauli basis). The converse fol-
lows from the same lines in the opposite direction. This
completes the proof.
Note that Corollary 4 together with the proposi-
tion above is consistent with the quantum Singleton
bound [22], n ≥ 4k + l, which also follows trivially from
the quantum Hamming bound for the case of orthogonal
codes that we considered in this subsection.
IV. SUMMERY AND CONCLUSIONS
We introduced the notion of entanglement of subspaces
as a measure that quantify the entanglement of bipartite
states in a randomly selected subspace. We discussed its
properties and suggested that it is additive. We were not
able to prove this conjecture (which is equivalent to the
additivity conjecture of the entanglement of formation)
although some numerical tests [14] supports that and for
maximally entangled subspaces we proved that it is ad-
ditive. We then extended the definition of maximally
entangled subspaces into k-totally entangled subspaces
and showed that the later can play an important role in
the study of quantum error correction codes.
We considered both degenerate and non-degenerate
codes and showed that the subspace spanned by the log-
ical codewords of a non-degenerate code is a k-totally
(maximally) entangled subspace. This observation, fol-
lowed by an analysis of the degenerate Shor’s nine qubits
code in terms of 22 mutually orthogonal subspaces, mo-
tivated us to define a general (possible degenerate) error
correcting code in terms of subspaces. We believe that
further investigation in this direction would lead to a
better understanding of degenerate quantum error cor-
recting codes.
Acknowledgments:— The authors would like to thank
Aram Harrow and David Meyer for fruitful discussions.
[1] C. H. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A.
Peres and W. K. Wootters, Phys. Rev. Lett. 70, 1895
(1993).
[2] C. H. Bennett and S.J. Wiesner, Phys. Rev. Lett. 69,
2881 (1992).
[3] M. B. Plenio, S. Virmani, Quant. Inf. Comp. 7, 1 (2007).
[4] P. W. Shor, Commun. Math. Phys. 246, 453 (2004).
[5] G. Gour, Phys. Rev. A 72, 022323 (2005).
[6] P. Hayden, quant-ph/0409157
[7] P. Hayden, D. W. Leung and A. Winter, Comm. Math.
Phys. 265, 95 (2006).
[8] A. Abeyesinghe, P. Hayden, G. Smith and Andreas Win-
ter, IEEE Trans. Inform. Theory 52, 3635 (2006).
[9] P. Shor, Lecture Notes 2002, http://www.msri.org/ pub-
lications/ln/msri/2002/quantumcrypto/shor/1/
[10] N. R. Wallach, ”An Unentangled Gleason’s theorem”,
Quantum computation and information (Washington,
DC, 2000), 291–298,Contemp. Math. 305(2002).
[11] C. H. Bennett, D. P. DiVincenzo, T. Mor, P. W. Shor, J.
A. Smolin and B. M. Terhal, Phys. Rev. Lett. 82, 5385
(1999).
[12] D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin and
B. M. Terhal, Comm. Math. Phys. 238, 379 (2003).
[13] A. Roy and G. Gour, in preparation.
[14] A. W. Harrow, private communication.
[15] D. N. Page, Phys. Rev. Lett. 71, 1291 (1993).
[16] G. Vidal, W. Dur and J. I. Cirac, Phys. Rev. Lett. 89,
027901 (2002).
[17] M. A. Nielsen and I. L. Chuang, ”Quantum Computa-
tion and Quantum Information” (Cambridge University
Press, 2000).
[18] A. M. Steane, Phys. Rev. Lett. 77, 793 (1996); Proc. R.
Soc. London A, 452, 2551 (1996).
[19] C. H. Bennett, D. P. DiVincenzo, J. A. Smolin and W. K.
Wootters, Phys. Rev. A 54, 3824 (1996).
[20] R. Laflamme, C. Miquel, J. P. Paz and W. H. Zurek,
Phys. Rev. Lett. 77, 198 (1996).
[21] P. Shor, Phys. Rev. A 52, 2493 (1995).
[22] E. Knill and R. Laflamme, Phys. Rev. A 55, 900 (1997).
http://arxiv.org/abs/quant-ph/0409157
http://www.msri.org/
