INSTITUTE OF PHYSICS PUBLISHING

JOURNAL OF PHYSICS A: MATHEMATICAL AND GENERAL

J. Phys. A: Math. Gen. 36 (2003) 8113–8127

PII: S0305-4470(03)61762-2

Conversion of a general quantum stabilizer code to an
entanglement distillation protocol*
Ryutaroh Matsumoto
Department of Communications and Integrated Systems, Tokyo Institute of Technology, Tokyo
152-8552, Japan
E-mail: ryutaroh@rmatsumoto.org

Received 4 April 2003
Published 8 July 2003
Online at stacks.iop.org/JPhysA/36/8113
Abstract
We show how to convert a quantum stabilizer code to a one- or two-way
entanglement distillation protocol. The proposed conversion method is a
generalization of those of Shor–Preskill and Nielsen–Chuang. The recurrence
protocol and the quantum privacy amplification protocol are equivalent to theprotocols converted from [[2, 1]] stabilizer codes. We also give an example of a
two-way protocol converted from a stabilizer better than the recurrence protocol
and the quantum privacy amplification protocol. The distillable entanglementby the class of one-way protocols converted from stabilizer codes for a certainclass of states is equal to or greater than the achievable rate of stabilizer
codes over the channel corresponding to the distilled state, and they can distill
asymptotically more entanglement from a very noisy Werner state than thehashing protocol.
PACS numbers: 03.67.Pp, 03.67.Mn, 03.67.Hk, 89.70.+c

1. Introduction
In many applications of quantum mechanics to communication, the sender and the receiver
have to share a maximally entangled quantum state of two particles. When there is a noiselessquantum communication channel, the sender can send one of two particles in a maximallyentangled state to the receiver and sharing of it is easily accomplished. However, the quantum
communication channel is usually noisy, that is, the quantum state of the received particle
changes probabilistically from the original state of a particle.
Entanglement distillation protocols [2] and quantum error-correcting codes [16, 18] are
the schemes for sharing a maximally entangled state over a noisy communication channel.
* A one page abstract of this paper appeared in the Proceedings of 2003 IEEE International Symposium on Information
Theory.
0305-4470/03/298113+15$30.00 © 2003 IOP Publishing Ltd Printed in the UK

8113

8114

R Matsumoto

A distillation protocol is said to be two-way (resp. one-way) if it involves two-way (resp.
one-way) classical communication. Two-way protocols have larger distillation ability than
one-way protocols. However, few two-way protocols have been proposed so far, namely therecurrence protocol [2] and the quantum privacy amplification protocol (QPA protocol) [6].
There may be many two-way protocols better than existing ones, and the discovery of better
protocols has been awaited.
Immediately after the proposal of those schemes, Bennett et al discovered that one canconstruct a one-way entanglement distillation protocol from a quantum code [3, section V.C],
which requires 2n additional qubits where n is the number of noisy entangled states to be
distilled. Nielsen and Chuang [12, exercise 12.34] observed a construction method of a oneway protocol without extra qubits from a real binary quantum stabilizer code as a generalizationof the idea in [17].
By a conversion method from a quantum code to a distillation protocol, we can solve
problems of distillation protocols from results in quantum codes. For example, we canconstruct a good distillation protocol from a good quantum code. Thus such a conversion
method deserves further investigation.
It is not known how one can convert a quantum error-correcting code to a two-way
entanglement distillation protocol. We shall propose a conversion method from an arbitrary
quantum stabilizer code to both one- and two-way entanglement distillation protocols as a
generalization of Shor and Preskill [17], Nielsen and Chuang [12]. Benefits of the proposed
conversion methods are• We can construct infinitely many two-way protocols. One can easily construct a two-way
protocol better than the recurrence protocol and the QPA protocol from a simple stabilizer
code (see section 4.2).
• It is known that one-way protocols and quantum error-correcting codes without classicalcommunication have the same ability of sharing maximally entangle states over a noisy
quantum channel [3]. The proposed protocols might be used for further clarification of
the relation between distillation protocols and quantum error-correcting codes.
This paper is organized as follows: in section 2, basic notation is introduced. In section 3,
we present a construction of entanglement distillation protocols from quantum stabilizer codes.
In section 4, we give examples of converted protocols equivalent to the recurrence protocol and
the QPA protocol, and an example better than them. In section 5, we evaluate the distillable
entanglement by the class of one-way protocols converted from stabilizer codes, and showthat the converted protocols can distill asymptotically more entanglement from a noisy Wernerstate than the hashing protocol [3]. In section 6, we derive a lower bound on fidelity with ageneral initial state of protocols.

2. Notation
In this section, we fix notation and the problem formulation. Let HA and HB be
p-dimensional complex linear spaces with orthonormal bases {|0A , . . . , |(p − 1)A } and{|0B , . . . , |(p − 1)B }, respectively, where p is a prime number. We shall restrict ourselves
to p-ary stabilizer codes because an m-ary stabilizer code can be constructed as a tensor
product of pi -ary stabilizer codes [14, p 1831, remarks], where pi are prime divisors of m, andextension of the proposed conversion method to the m-ary case is straightforward. We defineConversion of a general quantum stabilizer code to an entanglement distillation protocol

8115

the maximally entangled states in HA ⊗ HB by
1 |β(a, b) = I ⊗ X Z √|iA iB 
p i=0
p−1

a

b

where a, b ∈ {0, . . . , p − 1}, and matrices X and Z are defined by
X|i = |i + 1 mod pZ|i = ωi |iwith a complex primitive pth root ω of 1. The matrices X, Z and their commutation relation
were first applied to quantum mechanics by Weyl [20, section 4.15]. Suppose that Charlie
prepares n pairs of particles in the state |β(0, 0), sends the particles corresponding to HA
to Alice, and sends the other particles corresponding to HB to Bob. The quantum channels
between Alice and Charlie and between
Bob andand Alice and Charlieare noisy in general,Bob share a mixed state ρ ∈ S HA⊗n ⊗ HB⊗n , where S HA⊗n ⊗ HB⊗n is the set of density
operators on HA⊗n ⊗ HB⊗n . The state ρ can be an arbitrary density operator. The goal of anentanglement distillation protocol is to extract as many pairs of particles with state close to|β(0, 0) as possible from n pairs of particles in the state ρ.
3. Protocol
In this section, we shall describe how to make an entanglement distillation
 ⊗k protocol
 from
⊗k
H
from
S
⊗
H
a quantum
stabilizer
code.
In
the
protocol,weextract
a
state
τ
∈
A
B


ρ ∈ S HA⊗n ⊗ HB⊗n .
The proposed protocol will be constructed from the nonbinary generalization [11, 14] ofquantum stabilizer codes [4, 5, 8]. We assume that the reader is familiar with the formalismof the nonbinary stabilizer code. Let us introduce the notation of stabilizer codes. Let
E = {ωi Xa1 Z b1 ⊗ · · · ⊗ Xan Z bn : a1 , b1 , . . . , an , bn , i are integers}, and S a commutative
subgroup of E. The subgroup S is called a stabilizer.
Let Zp = {0, . . . , p − 1} with addition and multiplication taken modulo p. For a vectora = (a1 , b1 , . . . , an , bn ) ∈ Z2n
p , letXZ(a ) = Xa1 Z b1 ⊗ · · · ⊗ Xan Z bn .

Suppose that {XZ(g1 ), . . . , XZ(gn−k ) (and possibly some power of ωI ) } is a generating set of
the group S, where g1 , . . . , gn−k are linearly independent of Zp .
Let H be a complex linear space with the orthonormal basis {|0, . . . , |p − 1}, andhereafter we shall identify H with HA and HB by linear maps |i → |iA  and |i → |iB . Let
Q be a stabilizer code defined by S, that is, a joint eigenspace of S in H ⊗n . There are many
joint eigenspaces of S and we can distinguish an eigenspace by its eigenvalue of XZ(gi ) fori = 1, . . . , n − k. Hereafter, we fix a joint eigenspace Q of S and suppose that Q belongs tothe eigenvalue λi of XZ(gi ) for i = 1, . . . , n − k.
Suppose that we sent |ϕ ∈ Q, and received XZ(e)|ϕ. We can tell which eigenspace of
S contains the state XZ(e)|ϕ by measuring an observable whose eigenspaces are the sameas those of XZ(gi ). Then the measurement outcome always indicates that the measured stateXZ(e)|ϕ belongs to the eigenspace λi ωgi ,e , where gi , e is the symplectic inner productdefined bygi , e =nbi ci − ai di

i=1

for gi = (a1 , b1 , . . . , an , bn ) and e = (c1 , d1 , . . . , cn , dn ).

(1)

8116

R Matsumoto

We define gi = (a1 , −b1 , . . . , an , −bn ). Since the complex conjugate of ω is ω−1 , wecan see that XZ(gi ) is a componentwise complex conjugated matrix of XZ(gi ). Let S  be a
subgroup of E generated by {XZ(g1 ), . . . , XZ(gn−k )}. Easy computation shows that S  is again
commutative. So we can consider joint eigenspaces of S  . There exists a joint eigenspace Q
of S  whose eigenvalue of XZ(gi ) is λ̄i (the complex conjugate of λi ).
With this notation, our protocol is executed as follows:(1) Alice measures an observable corresponding to XZ(gi ) for each i, and let λ̄i ω−ai be theeigenvalue of an eigenspace of S  containing the state after measurement. In what follows
we refer to (a1 , . . . , an−k ) ∈ Zn−k
as a measurement outcome.
p(2) Bob measures an observable corresponding to XZ(gi ) for each i, and let λi ωbi be theeigenvalue of an eigenspace of S containing the state after measurement. In what follows
as a measurement outcome.
we also refer to (b1 , . . . , bn−k ) ∈ Zn−kp(3) Alice sends (a1 , . . . , an−k ) to Bob.
(4) Bob performs the error correction process according to b1 − a1 , . . . , bn−k − an−k asdescribed below.
(5) Alice and Bob apply the inverse of encoding operators of the quantum stabilizer codes.
(6) Alice and Bob discard the last n − k particles.
(7) If the difference of the measurement outcomes (b1 − a1 , . . . , bn−k − an−k ) indicates thatthe fidelity between the remaining k particles and |β(0, 0)⊗k is low, Bob discards all of
his particles and he tells Alice the disposal of particles.
We shall introduce some notation. For a vector u ∈ Z2np letu))|β(0, 0)⊗n .
|β(u) = (I ⊗ XZ(Let Q(x ) [resp Q (x )] ⊂ H ⊗n
HA⊗n
HB⊗n be the quantum stabilizer code of S (resp.
xiS ) belonging to the eigenvalue λi ω (resp. λ̄i ω−xi ) of XZ(gi ) (resp. XZ(gi )) for a vectorx ) (resp. P  (x )) be the projection onto Q(x ) (resp.
x = (x1 , . . . , xn−k ) ∈ Zn−kp , and P (

x )).
Q (
Lemma 1. We have
 = {P  (x ) ⊗ I }|β(0)
x ) ⊗ P (x )}|β(0)
{P  ((2)

for any x ∈ Zn−kp .
Proof. Let {|0, . . . , |pn − 1} be an orthonormal basis of H ⊗n consisting of tensor productsof {|0, . . . , |p − 1} ⊂ H , and we have
p −1


n

p |β(0) =|i ⊗ |i.
ni=0

For x ∈ Zn−kx , 0, . . . , |x , pk − 1} be an orthonormal basis of Q(x ). For a statep , let {||ϕ = α0 |0 + · · · + αpn −1 |pn − 1 ∈ H ⊗nwe define|ϕ = ᾱ0 |0 + · · · + ᾱpn −1 |pn − 1
x , 0, . . . , |x , pn−k − 1}
where ᾱi is the complex conjugate of αi . With this notation, {|n−kx ). The set {|x , i : x ∈ Zp , i = 0, . . . , p k − 1} isis an orthonormal basis of Q (⊗nand there exists a unitary matrix on H ⊗n that transforms
an orthonormal basis of Hnkx , i : x ∈ Zn−k
Let Ū be
the basis {|0, . . . , |p − 1} to {|p , i = 0, . . . , p − 1}.

Conversion of a general quantum stabilizer code to an entanglement distillation protocol

8117

the componentwise complex conjugate of U, that is, Ū transforms {|0, . . . , |pn − 1} tokx , i : x ∈ Zn−k{|p , i = 0, . . . , p − 1}. We have Ū ⊗ U |β(0) = |β(0) [10]. Therefore


−1
 p
k

 =
pn |β(0)

|
x , i ⊗ |x , i.

i=0x ∈Zn−k
p

Since
pk −1



P (
x) =


|
x , i
x , i|

i=0

we have


 k

k
p −1
−1
 p


n
 =
p {P (x ) ⊗ I }|β(0)
|x , i 
x , i| ⊗ I |
x , i ⊗ |x , i
i=0

i=0x ∈Zn−k
p

p −1
k

=



|
x , i ⊗ |x , i

i=0

=




pn {P  (x ) ⊗ P (x )}|β(0).

(3)



u)}|β(0).
Suppose that we perform the protocol above to the state |β(u) = {I ⊗ XZ(n−kAfter we get a = (a1 , . . . , an−k ) ∈ Zp as a measurement outcome in step 1, the state is = {I ⊗ XZ(u)}|β(0)
u)}{P  (a ) ⊗ I }|β(0)
{P  (a ) ⊗ I }{I ⊗ XZ(
= {I ⊗ XZ(u)}{P  (a ) ⊗ P (a )}|β(0)
(by equation (2)).
 belongs to Q (a ) ⊗ Q(b), whereu)}{P  (a ) ⊗ P (a )}|β(0)
Observe that the vector {I ⊗ XZ( , . . . , gn−k , u ).
b = a + (g1 , uThus the measurement outcome in step 2 must be b.

For simplicity of presentation, we assume that the state ρ ∈ S HA⊗n ⊗HB⊗n can be writtenas
α(u)|β(
u)β(
u)|
(4)
ρ=
u
 ∈Z2np

is a probability distribution. A general case will be treated inwhere α(u) : u ∈ Z2np
section 6.
as a
After performing step 1 in the proposed protocol to state (4) and getting a ∈ Zn−kpmeasurement outcome, the state is (a , a ){I ⊗ XZ(α(u){I ⊗ XZ(u)}P (a , a )ρ(0)Pu)∗ }u ∈Z2np = |β(0)β(0)|.
Suppose that we get b as awhere P (a , a ) = P  (a ) ⊗ P (a ) and ρ(0)measurement outcome in step 2, and denote (b1 − a1 , . . . , bn−k − an−k ) by s . The state belongs to Q (a ) ⊗ Q[a + (g1 , uu)}P (a , a )|β(0) , . . . , gn−k , u )]. Thus the state{I ⊗ XZ(after step 2 is

8118



R Matsumoto (a , a ){I ⊗ XZ(α(u)P (a , b){I⊗ XZ(
u)}P (a , a )ρ(0)Pu)∗ }P (a , b)u
 ∈Z2np= (a , a ){I ⊗ XZ(α(u)P (a , b){I⊗ XZ(
u)}P (a , a )ρ(0)Pu)∗ }P (a , b)u
 ∈D(s )= (a , a ){I ⊗ XZ(α(u){I ⊗ XZ(u)}P (a , a )ρ(0)Pu)}

u
 ∈D(s )where
i , u  = bi − ai , for each i .
D(s ) = u ∈ Z2np : g
Let C be the linear subspace of Z2n
1 , . . . , gn−k , and C ⊥ be the orthogonal
p spanned by gspace of C with respect to the symplectic inner product (1). For vectors u , v such thatu) and XZ(v ) have the same effect on states in Q(a ) for any a , and we canu − v ∈ C, XZ(u) and XZ(v ) if u
 − v ∈ C, which is equivalent to v ∈ u
 + C. Thus, among
identify errors XZ(u) corresponding to D(s ), the most likely error vector u is one having maximum
errors XZ(α(v )v ∈
u+C

in the set D(s ). Let e be the most likely error vector in D(s ). The set D(s ) is equal to:u ∈ C ⊥ }.
e + C ⊥ = {e + u
Bob applies XZ(e)−1 to his particles. This is step 4. After applying XZ(e)−1 to Bob’s
particles, the joint state of particles of Alice and Bob is (a , a ){I ⊗ XZ(α(u){I ⊗ XZ(u − e)}P (a , a )ρ(0)Pu − e)∗ }.
(5)u ∈e+C ⊥u − e) does not change a state in Q(a ) if u
 − e ∈ C. Therefore, the state (5) is
Recall that XZ(equal to (a , a )α(u)P (a , a )ρ(0)Pu ∈e+C+ (a , a )[I ⊗ XZ(α(u)[I ⊗ XZ(u − e)]P (a , a )ρ(0)Pu − e)∗ ].

(6)u ∈e+(C ⊥ \C)

We shall explain how to use an encoding operator in step 5 to extract |β(0, 0)⊗k fromthe above state. Let |a ∈ H ⊗n−k be an ancillary state. Consider an encoding operator Ue on
H ⊗n sending |i ⊗ |a ∈ H ⊗n to |a , i for i = 0, . . . , pk − 1, where {|a , 0, . . . , |a , pk − 1}is an orthonormal basis of Q(a ) defined above. Observe that Ue is an encoding operator for−1
Q (a ) sending |i ⊗ |a ∈ H ⊗n to |a , i for i = 0, . . . , p k − 1. Applying Ue ⊗ Ue−1 to state(5) yields
 −1 (a , a )[I ⊗ XZ(α(u) Ue ⊗ Ue−1 [I ⊗ XZ(u − e)]P (a , a )ρ(0)Pu − e)∗ ](Ue ⊗ Ue )u ∈e+C ⊥

=




 −1
 (a , a )(Ue ⊗ Ue )α(u) Ue ⊗ Ue−1 P (a , a )ρ(0)Pu ∈e+C+(by equation (6))


 −1

α(
u) Ue ⊗ Ue−1 [I ⊗ XZ(u − e)]P (a , a )ρ(0)u ∈e+(C ⊥ \C)×P (a , a )[I ⊗ XZ(u − e)∗ ](Ue ⊗ Ue )

Conversion of a general quantum stabilizer code to an entanglement distillation protocol

=






 −1
α(
u) Ue ⊗ Ue−1 u ∈e+C

×
+

 k
−1
p


i=0

 k
p −1
1 
pn  i=0a , i| ⊗ a , i|  (Ue ⊗ Ue )




8119



|a , i ⊗ |a , i(by equation (3))


 −1

α(
u) Ue ⊗ Ue−1 [I ⊗ XZ(u − e)]P (a , a )ρ(0)u ∈e+(C ⊥ \C)×P (a , a )[I ⊗ XZ(u − e)∗ ](Ue ⊗ Ue )1α(u){|β(0, 0)⊗k ⊗ |a⊗2 }{β(0, 0)|⊗k= npu ∈e+C⊗ a|⊗2 }
+(by definition of Ue )

 −1

α(
u) Ue ⊗ Ue−1 [I ⊗ XZ(u − e)]P (a , a )ρ(0)u ∈e+(C ⊥ \C)×P (a , a )[I ⊗ XZ(u − e)∗ ](Ue ⊗ Ue ).
(7)
Taking partial trace of the first term over the last n − k qubits yields |β(0, 0)⊗k , which is
step 6.
Let τ5 be the final state of step 5, that is, state (7), and τ6 be the state after step 6. In
step 7, Bob computes the fidelity between the state |β(0, 0)⊗k and τ6 by using knowledge ofs and {α(u) : u ∈ Z2np }. Tr[τ5 ] is not 1 because τ5 is a state after projection. We have (a , a )]Tr[τ6 ] = Tr[τ5 ] = Tr[P (a , a )ρ(0)P  (a ) ⊗ I |β(0)
= β(0)|P
=

1
pn−k





α(
u)

u
 ∈e+C ⊥α(u)(by equation (2))

u ∈e+C ⊥(by equation (3)).

α(
u)

u
 ∈e+C ⊥If the initial state is |β(u) such that u ∈ e +C, we can get (1/pn−k )|β(0, 0)⊗k β(0, 0)|⊗k
as τ6 . Therefore, we haveβ(0, 0)|⊗k τ6 |β(0, 0)⊗k 

1
pn−k



α(
u).

u
 ∈e+C

Thus Bob estimates that the fidelity between |β(0, 0)⊗k and the normalized state of τ6 is at
least

α(
u)
 u ∈e+C
.
(8)
α(
u)
u
 ∈e+C ⊥The value (8) varies according to s = (b1 − a1 , . . . , bn−k − an−k ). If obtained difference simplies low fidelity, Bob discards all the particles and tell Alice of the disposal.
Note that if we include step 7 then the whole protocol needs two-way classicalcommunication, but if we exclude step 7 then it needs only one-way classical communication.

8120

R Matsumoto

When Alice and Bib do not execute step 7, the average of fidelity (8) should be consideredinstead of respective values of equation (8) for each difference s of measurement outcomes.
The average of equation (8) is at least
 
α(
u)
(9)
u
 ∈e(s )+Cs ∈Zn−kpwhere e(s ) is the guessed-error vector for a given difference s of measurement outcomes. Thisaverage fidelity (9) will be studied in sections 4 and 6.
4. Examples
In this section, we show how one can construct the well-known recurrence protocol and the
QPA protocol from stabilizer codes, and give a two-way protocol constructed from a stabilizer
better than the recurrence protocol and the QPA protocol.
4.1. The recurrence protocol and the QPA protocol
The recurrence protocol without twirling [2, step (A2)] has the same effect on any density
operator on HA⊗2 ⊗ HB⊗2 as the proposed protocol with p = 2, n = 2, k = 1, the stabilizer S
generated by Z ⊗ Z, encoding operators Ue (+1) : (α0 |0 + α1 |1)|a → α0 |00 + α1 |11 forthe code belonging to eigenvalue +1 of Z ⊗ Z, Ue (−1) : (α0 |0 + α1 |1)|a → α0 |01 + α1 |10for the code belonging to eigenvalue −1 of Z ⊗ Z, and discarding particles in step 7 if
s = (1) ∈ Z12 . This can be seen by a tedious but straightforward computation.
The QPA protocol [6] has the same effect as the protocol converted from the stabilizer
S generated by XZ ⊗ XZ, encoding operators Ue (+1) : (α0 |0 + α1 |1)|a → α0 (|0 −i|1)(|0 + i|1) + α1 (|0 + i|1)(|0 − i|1) for the code belonging to eigenvalue +1 of
XZ ⊗ XZ, Ue (−1) : (α0 |0 + α1 |1)|a → α0 (|0 − i|1)(|0 − i|1) + α1 (|0 + i|1)(|0 + i|1)
for the code belonging to eigenvalue −1 of XZ ⊗ XZ, and discarding particles in step 7 if
s = (1) ∈ Z12 .
4.2. A better protocol
We shall compare the protocol constructed from the stabilizer generated by {X ⊗ X ⊗ X ⊗X, Z ⊗ Z ⊗ Z ⊗ Z} (p = 2) with the recurrence protocol and the QPA protocol in a similar
way to [3, figure 8]. We discard particles in the protocol unless the measurement outcomescompletely agree, i.e., s = (0, 0).
Encoding operators for the stabilizer codes belonging to the eigenvalue (−1)s1 of
X ⊗ X ⊗ X ⊗ X and (−1)s2 of Z ⊗ Z ⊗ Z ⊗ Z are described in table 1.
Suppose that we have many copies of noisy entangled state1−F(|β(0, 1)β(0, 1)| + |β(1, 0)β(1, 0)| + |β(1, 1)β(1, 1)|)F |β(0, 0)β(0, 0)| +3and we want to distill the Bell state |β(0, 0)β(0, 0)| as often as possible by using the hashingprotocol and a two-way protocol chosen from the recurrence protocol without twirling, theQPA protocol, and the protocol constructed from {X ⊗ X ⊗ X ⊗ X, Z ⊗ Z ⊗ Z ⊗ Z}. We use
the hashing protocol to distill the perfect Bell state |β(0, 0)β(0, 0)| after a suitable numberof iterations of a two-way protocol as described in [3, section III.B.1].
The number of perfect Bell states distillable by the three two-way protocols are comparedin figure 1. Observe that an example of the proposed protocol has larger distillable
entanglement for the range of F between 0.75 and 0.87.

Conversion of a general quantum stabilizer code to an entanglement distillation protocol

distillable entanglement

0.4
0.35
0.3

8121

Proposed
QPA protocol
recurrence protocol w/o twirling

0.25
0.2
0.15
0.1
0.05
0
0.7

0.75

0.8
fidelity F

0.85

0.9

Figure 1. Comparison of two-way protocols.
Table 1. Encoding maps.
Eigenvalues

Encoding map|00|a → √1 (|0000 + |1111)2(s1 , s2 ) = (0, 0)|01|a → √1 (|0011 + |1100)2|10|a → √1 (|0101 + |1010)
2|11|a → √1 (|0110 + |1001)
2|00|a → √1 (|0001 + |1110)2(s1 , s2 ) = (0, 1)|01|a → √1 (|0010 + |1101)2|10|a → √1 (|0100 + |1011)
2|11|a → √1 (|1000 + |0111)2(s1 , s2 ) = (1, 0)|00|a → √1 (|0000 + |1111)2|01|a → √1 (|0011 + |1100)2|10|a → √1 (|0101 + |1010)
2|11|a → √1 (|0110 + |1001)2(s1 , s2 ) = (1, 1)|00|a → √1 (|0001 + |1110)2|01|a → √1 (|0010 + |1101)2|10|a → √1 (|0100 + |1011)
2|11|a → √1 (|1000 + |0111)2

5. Distillable entanglement by the converted protocols
In this section, we evaluate the distillable entanglement by one-way protocols constructedfrom stabilizers. Distillable entanglement is the most important measure of the performanceof a class of protocols.
We mean by an [[n, k]] entanglement distillation protocol a protocol always leaving kpairs of particles out of given n pairs of particles. Let D be a class of [[n, k]] entanglement

8122

R Matsumoto

distillation protocol for n = 1, 2, . . . , and k = 1, . . . , n. Let ρn be a density operator on
H ⊗2n . The distillable entanglement by the protocol D for the sequence of states {ρn } is the
maximum of a real number R such that for any R < R and any > 0 there exists an [[n, k]](k  nR ) protocol in D such that the protocol extracts a state τ ∈ H ⊗2k from ρn such that the
fidelity between τ and a maximally entangled state in H ⊗k is at least 1 − . Roughly speaking,the distillable entanglement by D is the largest number of maximally entangled pairs in H ⊗2distillable from one pair of particles. Our definition imposes on protocols the restriction that a
protocol always produces the same number of pairs of particles. A general definition without
this restriction was given by Rains [15].
Let α(i, j ) : (i, j ) ∈ Z2p be a probability distribution, and consider the density operatorα(i, j )|β(i, j )β(i, j )|ρ=(i,j )∈Z2p

on HA ⊗ HB . We shall estimate the distillable entanglement by the proposed protocol for thesequence of states {ρn = ρ ⊗n : n = 1, . . .}, and show the distillable entanglement is at least
as large as the achievable rate of quantum stabilizer codes over the quantum channel on H
with an error Xi Z j occuring with probability α(i, j ).
The achievable rate by quantum stabilizer codes over is the maximum of a real number
R such that for any R < R and any > 0 there exists an [[n, k]] (k  nR ) stabilizer code Q
such that any state |ϕ ∈ Q can be transmitted over with fidelity at least 1 − .
Proposition 2. We assume that the decoding of a quantum stabilizer code is implemented asfollows: first measure an observable whose eigenspaces are the same as the stabilizer of thecode, determine the most likely error of the form Xi1 Z j1 ⊗ · · · ⊗ Xin Z jn , and apply the inverseof the guessed error to the codeword. Under this assumption, the distillable entanglement by
the proposed protocol without step 7 for {ρn = ρ ⊗n : n = 1, . . .} is at least as large as theachievable rate by quantum stabilizer codes over .
Proof. Let R be the achievable rate by quantum stabilizer codes over . Then for any R < R
and > 0 there exists an [[n, k]] (k  nR ) quantum stabilizer code Q with stabilizer S suchthat for any state |ϕ ∈ Q can be transmitted over with fidelity at least 1 − . Let S be
generated by {XZ(g1 ), . . . , XZ(gn−k ) (and possibly some power of ωI )}, and Q belongs to theeigenvalue λi of XZ(gi ). Suppose that the decoder guesses the error as XZ(e(s )) when themeasurement outcomes indicate that the received state belongs to eigenvalue λi ωsi of XZ(gi )u)for i = 1, . . . , n − k, where s = (s1 , . . . , sn−k ). Then the decoder can correct any error XZ(ifu
 ∈ e(s ) + C : s ∈ Zn−kp(10)1 , . . . , gn−k .
where C is a linear subspace of Z2np spanned by g
By lemma 3 (see the appendix), there exists a codeword |ϕ ∈ Q such that if |ϕ isu)|ϕ is received with u not in the set (10) then the fidelity between |ϕtransmitted and XZ(and the decoded state is at most 9/16, because the set (10) is equal to the set of correctableerrors by Q in lemma 3. Since |ϕ can be transmitted through with fidelity at least 1 − ,the probability of the correctable error (10) over ⊗n is at least 1 − 16 /9.
Suppose that we apply the proposed protocol to ρ ⊗n such that if the difference sof measurement outcomes is observed then XZ(e(s ))−1 is applied in step 4. Then the
average (9) of the fidelity is at least 1 − 16 /9, because the errors in the set (10) are also
correctable by the proposed protocol (see equation (6)). For given > 0 set = 9 /16 in
the above argument, and we can see that the distillable entanglement is at least as large as theachievable rate of quantum stabilizer codes over .
Conversion of a general quantum stabilizer code to an entanglement distillation protocol

8123

The best known lower bound on the achievable rate by quantum stabilizer codes overis given by Hamada [9], and his lower bound gives the true value for the depolarizing
channels. Let us compare the distillable entanglement by the converted protocols andthat by the hashing protocol [3] for the Werner state of fidelity F, which is given byα(1, 1) = F, α(0, 1) = α(1, 0) = α(0, 0) = (1 − F )/3 and p = 2. The Werner stateis converted to
1−F(|β(0, 1)β(0, 1)| + |β(1, 0)β(1, 0)| + |β(1, 1)β(1, 1)|)F |β(0, 0)β(0, 0)| +3(11)
by applying XZ on Bob’s particle. The distillable entanglement of state (11) by the hashingprotocol is estimated as
1 − H2 (F, (1 − F )/3, (1 − F )/3, (1 − F )/3)(12)

where Hb is the Shannon entropy with base b. The distillable entanglement of state (11) by
the converted protocols is strictly larger than equation (12) for certain range of F, because theachievable rate of the Shor–Smolin concatenated codes is strictly larger than equation (12)over the depolarizing channel of fidelity F [7] and they can be written as stabilizer codes [9].
Let us consider the case of p = 3, α(0, 0) = F , and α(i, j ) = (1 − F )/8 for(i, j ) = (0, 0). The distillable entanglement by the nonbinary generalization [19] of thehashing protocol is estimated as
1 − H3 ({α(i, j )}).

(13)

The achievable rate by the quantum stabilizer codes is strictly greater than equation (13)for 0.2552  F  0.2557 [9, section VI.C], and so is the distillable entanglement by theconverted protocols.
6. Fidelity calculation in the general caseIn the preceding argument we assumed that the initial state shared by Alice and Bob was in theform of equation (4). In this section, we remove this restriction. Let ρ be an arbitrary density
operator in HA⊗n ⊗ HB⊗n . We shall consider applying the proposed protocol without step 7
to ρ and calculate the fidelity between the distilled state and |β(0, 0)⊗k . Precisely speaking,we shall calculate the fidelity between |β(0, 0)⊗k ⊗ |a⊗2 and the state after step 5, which isequal to that between |β(0, 0)⊗k and the state after step 6.
The idea of the following argument is borrowed from section 7.4 of [13]. Since there
is no selection of particles in steps 1–6 by a measurement, the whole process of steps 1–6
can be written as a completely positive trace-preserving map on the density operators on
HA⊗n ⊗ HB⊗n .
is anx ) : x ∈ Z2n
Let |ψ ∈ HA⊗n ⊗ HB⊗n ⊗ Henv is a purification of ρ. Since |β(p⊗n⊗northonormal basis of HA ⊗ HB , we can write |ψ as

|ψ =
|β(
x ) ⊗ |env(
x )
(14)
x ∈Z2npwhere |env(x ) is a vector in Henv .
In step 4, the inverse error operator XZ(e)−1 is determined from the difference s ofmeasurement outcomes and knowledge of α(u) : u ∈ Z2np . When we deal with an arbitrary
but known density operator ρ, determine e from s so that the lower bound (16) below on fidelity

8124

R Matsumoto

becomes large. Once we fix a determination rule of e from s , we can define Good = {u ∈ Z2np :⊗k
the protocol can perfectly distill |β(0, 0) from |β(u)}. Equation (14) can be written as|β(x ) ⊗ |env(x ) +|β(x ) ⊗ |env(
x ).
(15)
x ∈Goodx ∈Z2np \Good

Almost the same argument as section 7.4 of [13] shows that the fidelity between |β(0, 0)⊗k
and the state after step 6 is at least

2


 


1−
|β(
x ) ⊗ |env(
x )
(16)
 .
x ∈Z2n \Goodp

Acknowledgments
The author would like to thank Professor Tomohiko Uyematsu and Mr Toshiyuki Morita for
helpful discussions. This research was supported by the Japan Society for the Promotion of
Science under contract no 14750278.
Appendix. Bad codeword lemma
We consider a quantum channel over which an error of the form XZ(e) occurs with theprobability α(e) for e ∈ Z2n
p , and we also consider the following decoding method: measure⊗n
whose
eigenspaces are the same as those of S, and apply an operator
the observableofH
determinedbythe measurement outcome and some deterministic criterion.
XZ(re ) re ∈ Z2np
With this decoding method, we can correct at most p2n−2k errors among all the p2n errors foran [[n, k]] quantum stabilizer code.
Lemma 3. Let Q be an [[n, k]] quantum stabilizer code. Suppose that we have a fixed
decoding method as described above. There exists a codeword |ϕ ∈ Q such that
|ϕ|XZ(re )XZ(e)|ϕ|  34
for all uncorrectable error XZ(e), where an error XZ(e) is said to be correctable if a received
state XZ(e)|ϕ is decoded to |ϕ for all |ϕ ∈ Q and uncorrectable otherwise.
Proof. Consider the following map
Ef :ωi Xa1 Z b1 ⊗ · · · ⊗ Xan Z bn

−→
Z2n
p
.
−→ (a1 , b1 , . . . , an , bn )⊥Let C = f (S) ⊂ Z2n
p . Since S is commutative, we have C ⊆ C . Let Cmax be a subspace ofZ2np such that⊥
Cmax = Cmax
C ⊆ Cmax ⊆ C ⊥ .

Such a space Cmax always exists by the Witt theorem (see section 20 of [1]). Since⊥, we have dim Cmax = n. The set f −1 (Cmax ) is a commutative subgroup of
Cmax = Cmax
E, so we can consider a quantum stabilizer code Qmin ⊂ Q defined by f −1 (Cmax ). We havedim Qmin = pn−dim Cmax = 1. Let |ψ1  ∈ Qmin be a normalized state vector. We shall construct
the desired codeword |ϕ in lemma 3 from |ψ1 .

Conversion of a general quantum stabilizer code to an entanglement distillation protocol

8125

By the property of stabilizer codes, if x + Cmax = y + Cmax thenψ1 |XZ(x )∗ XZ(y )|ψ1  = 0.

(17)

Let R ⊂ C ⊥ be a set of coset representatives of Cmax in C ⊥ , that is, R has the same
number of elements as C ⊥ /Cmax , and if x , y ∈ R and x = y then x + Cmax = y + Cmax . We
assume 0 ∈ R. Define
1 |ψ2  = XZ(x )|ψ1 
pk x ∈R
which is a normalized state vector in Q by equation (17).
We want to take |ϕ in lemma 3 as a multiple of |ψ1 + ψ2 , so let us compute1 
ψ1 |ψ2  = 
ψ1 |XZ(x )|ψ1 
pk x ∈R1
=  ψ1 |ψ1 pk

by equation (17) and 0 ∈ R.

By equation(17) we also have ψ2 |ψ2  = ψ1 |ψ1 . Therefore, ψ1 + ψ2 |ψ1 + ψ2  =
(2 + 2/ pk )ψ1 |ψ1 . Define |ϕ by1

 |ψ1 + ψ2 
2 + 2/ pk

which is a normalized state vector in Q. We shall show that |ϕ has the desired property.
Suppose that an error XZ(e ) occurred and we applied XZ(re ) as the recovery operator. If/ C ⊥ , thee = e − re ∈ C, then the error e is correctable, otherwise e is uncorrectable. If e ∈⊥decoded state is orthogonal to any transmitted state, so we may assume e ∈ C \ C hereafter.
For e ∈ Cmax \C,
pk ψ2 |XZ(e)|ψ2 =ψ1 |XZ(x )∗ XZ(e)XZ(y )|ψ1 
x ,
y ∈R

=



ψ1 |XZ(x )∗ XZ(e)XZ(y )|ψ1 (by equation (17))

x ,
y ∈R
y +Cmaxx +Cmax =e+==ψ1 |XZ(x )∗ XZ(e)XZ(x )|ψ1 x ∈Rωe,x  ψ1 |XZ(x )∗ XZ(x )XZ(e)|ψ1 x ∈R= ψ1 |XZ(e)|ψ1 ωe,x  .

x ∈RConsider the linear map Le from C ⊥ to Zp defined byLe (
x ) = e, x .
/ C implies that Le is not a zero
Then the kernel of Le contains Cmax because e ∈ Cmax , and e ∈linear map. Hence we can partition R into cosets of ker(Le ) in C ⊥ . Each coset of ker(Le )in C ⊥ contains exactly pk−1 elements of R, and each element in a coset has the same value

8126

R Matsumoto

under Le . Thereforeωe,x  =ωLe (x )
x ∈R

x ∈R

= pk−1

p−1


ωi

i=0

= 0.
Summarizing these results we havee ∈ C ⊥ \Cmax ⇒ ψ1 |XZ(e)|ψ1  = 0e ∈ Cmax \C ⇒ ψ2 |XZ(e)|ψ2  = 0(by equation (17))

and by equation (17) we have for e ∈ C ⊥1|ψ1 |XZ(e)|ψ2 | =  .
pkThus we have for e ∈ C ⊥ \ C|ψ1 + ψ2 |XZ(e)|ψ1 + ψ2 |
1
 (|ψ1 |XZ(e)|ψ1 | + |ψ2 |XZ(e)|ψ2 | + 2|ψ1 |XZ(e)|ψ2 |)


 


2 + 2/ pk √
1
=2/ pk
1 + 2/ pk
2 + 2/ pk
 3/4
which completes the proof of lemma 3.

References[1] Aschbacher M 2000 Finite Group Theory 2nd edn (Cambridge Studies in Advanced Mathematics vol 10)(Cambridge: Cambridge University Press)[2] Bennett C H, Brassard G, Popescu S, Schumacher B, Smolin J A and Wootters W K 1996 Purification of
noisy entanglement and faithful teleportation via noisy channels Phys. Rev. Lett. 76 722–5 (Preprint quantph/9511027)[3] Bennett C H, DiVincenzo D P, Smolin J A and Wootters W K 1996 Mixed-state entanglement and quantum
error correction Phys. Rev. A 54 3824–51 (Preprint quant-ph/9604024)[4] Calderbank A R, Rains E M, Shor P W and Sloane N J A 1997 Quantum error correction and orthogonal
geometry Phys. Rev. Lett. 78 405–8 (Preprint quant-ph/9605005)[5] Calderbank A R, Rains E M, Shor P W and Sloane N J A 1998 Quantum error correction via codes over GF(4)IEEE Trans. Inf. Theory 44 1369–87 (Preprint quant-ph/9608006)[6] Deutsch D, Ekert A, Jozsa R, Macchiavello C, Popescu S and Sanpera A 1996 Quantum privacy amplificationand the security of quantum cryptography over noisy channels Phys. Rev. Lett. 77 2818–21 (Preprint quantph/9604039)
Deutsch D, Ekert A, Jozsa R, Macchiavello C, Popescu S and Sanpera A 1998 Quantum privacy amplificationand the security of quantum cryptography over noisy channels Phys. Rev. Lett. 80 2022 (erratum)[7] DiVincenzo D P, Shor P W and Smolin J A 1998 Quantum-channel capacity of very noisy channels Phys. Rev.
A 57 830–39 (Preprint quant-ph/9706061)
DiVincenzo D P, Shor P W and Smolin J A 1999 Quantum-channel capacity of very noisy channels Phys. Rev.
A 59 1717 (erratum)[8] Gottesman D 1996 Class of quantum error-correcting codes saturating the quantum Hamming bound Phys. Rev.
A 54 1862–8 (Preprint quant-ph/9604038)[9] Hamada M 2002 Information rates achievable with algebraic codes on quantum discrete memoryless channels
version 1 Preprint quant-ph/0207113v1

Conversion of a general quantum stabilizer code to an entanglement distillation protocol

8127[10] Horodecki M and Horodecki P 1999 Reduction criterion of separability and limits for a class of distillation
protocols Phys. Rev. A 59 4206–16 (Preprint quant-ph/9708015)[11] Knill E 1996 Non-binary unitary error bases and quantum codes Preprint quant-ph/9608048[12] Nielsen M A and Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge: Cambridge
University Press)[13] Preskill J 1998 Lecture notes for physics 229: quantum information and computation; webpage http://www.
theory. caltech. edu/people/preskill/ph229[14] Rains E M 1999 Nonbinary quantum codes IEEE Trans. Inf. Theory 45 1827–32 (Preprint quant-ph/9703048)[15] Rains E M 1999 Rigorous treatment of distillable entanglement Phys. Rev. A 60 173–8 (Preprint quantph/9809078)[16] Shor P W 1995 Scheme for reducing decoherence in quantum computer memory Phys. Rev. A 52 2493–6[17] Shor P W and Preskill J 2000 Simple proof of security of the BB84 quantum key distribution protocol Phys.
Rev. Lett. 85 441–4 (Preprint quant-ph/0003004)[18] Steane A M 1996 Error correcting codes in quantum theory Phys. Rev. Lett. 77 793–7[19] Vollbrecht K G H and Wolf M M 2003 Efficient distillation beyond qubits Phys. Rev. A 67 012303 (Preprint
quant-ph/0208152)[20] Weyl H 1931 The Theory of Groups and Quantum Mechanics 2nd edn (London: Methuen)