Enumerating all bilocal Clifford distillation protocols throughsymmetry reduction

arXiv:2103.03669v5 [quant-ph] 17 May 2022

S. Jansen1,2 , K. Goodenough3 , S. de Bone3,4 , D. Gijswijt1 , and D. Elkouss3,5
1

Delft Institute of Applied Mathematics, Delft University of Technology, The Netherlands.

2

Korteweg-de Vries Institute for Mathematics, University of Amsterdam, The Netherlands

3

QuTech, Delft University of Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands

4

QuSoft, CWI, Science Park 123, 1098 XG Amsterdam, The Netherlands

5

Networked Quantum Devices Unit, Okinawa Institute of Science and Technology Graduate University, Okinawa, Japan

Entanglement distillation is an essentialbuilding block in quantum communication
protocols. Here, we study the class ofnear-term implementable distillation protocols that use bilocal Clifford operations
followed by a single round of communication. We introduce tools to enumerate
and optimise over all protocols for up
to n = 5 (not necessarily equal) Belldiagonal states using a commodity desktop
computer. Furthermore, by exploiting thesymmetries of the input states, we findall protocols for up to n = 8 copies ofa Werner state. For the latter case, we
present circuits that achieve the highest
fidelity with perfect operations and no
decoherence. These circuits have modest
depth and number of two-qubit gates. Our
results are based on a correspondence
between distillation protocols and double
cosets of the symplectic group, and improve on previously known protocols.

1 Introduction
Entanglement is an essential resource for a host ofquantum communication tasks, including but notlimited to secret-key generation [1], conference
key agreement [2, 3], clock synchronisation [4],and distributed quantum computation [5, 6, 7].
Due to experimental limitations, entanglement
is in practice always noisy, i.e. it has a nonunit fidelity with a target perfectly entangledstate. A lower fidelity can lead to a lower rate
at which one can perform certain tasks, or evenyield their implementation impossible. Entanglement distillation is a set of procedures that

increase the fidelity of the present entanglementby transforming multiple copies of a lower fidelity
entangled state into (usually) a smaller numberof copies with higher fidelity [8, 9, 10] (see [11]for a review).
Entanglement distillation has been studied indifferent settings. One such setting corresponds
to the highly idealised scenario where one is given
an asymptotic number of copies of a single state,
and one can perform arbitrary local operations
and classical communication (LOCC) [12, 13, 14].
Such protocols can in principle require an unbounded number of rounds of classical communication between Alice and Bob, rendering them infeasible in practice. A well-known explicit asymptotic protocol is the hashing protocol [8]. This
protocol allows for the distillation to maximallyentangled states at a finite rate, given that thegiven input state has a high enough input fidelity.
Other scenarios include purification with the helpof entanglement [15, 16, 17, 18], on a single copy
only, known as filtering [19, 20], with environment
assistance [21], of higher-dimensional states [22,23] or with different classes of operations than
LOCC [24, 25]. On the experimental side, entanglement distillation has been realised using
photonic setups [26, 27, 28, 29, 30, 31] (where
the distilled state is not stored in a memory
afterwards), ions [32] (where the distillation was
performed within a single node) and NV-centres
in diamond [33] (where the distilled states wereheralded and stored in memories for further use).
Our goal is to find good distillation protocols
with modest requirements. In particular, protocols where Alice and Bob use a small numberof entangled states [34, 35], and require only asingle round of communication after performing

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

1

their local operations [34]. The above class of
distillation protocols were first considered in [34],where they were called measure and exchange
protocols. The semidefinite programming bounds
found by Rozpedek et al. [34] allow to bound the
optimal performance of measure and exchange
protocols. Moreover, in some particular cases theexisting protocols meet the bounds allowing to establish their optimality. Regarding the design ofprotocols, a heuristic procedure called the seesaw
method allows to improve existing protocols [34].
More recently, Krastanov et al. investigated agenetic optimisation method for a subset of these
protocols [36] and evaluated them including noisy
operations.
Here, complementary to previous work, we finda systematic procedure to obtain good measureand exchange protocols.
To this end, we narrow down our investigationfrom general measure and exchange protocols toa practically relevant subset of protocols andstates. We consider the distillation of Belldiagonal states, where we use arbitrary noiselessbilocal Clifford circuits and measure out all but
one of the qubit pairs. The measurement results
are communicated between Alice and Bob, andthe protocol is deemed successful if all pairs
had correlated outcomes. We call this class ofprotocols bilocal Clifford protocols for short. This
class of protocols includes a number of relevant
protocols considered before in the literature [8,10, 37, 38, 39, 40, 41, 42, 36].
The restriction to bilocal Clifford protocols
and Bell-diagonal states allows us to reduce thefinding of all bilocal Clifford protocols to enumerating all (double) cosets Dn \ Sp(2n, F2 )/Kn .
Here, Sp(2n, F2 ) is the symplectic group over thefield with two elements F2 , Kn is the (possibly
trivial) subgroup that preserves the input statesand Dn is the distillation subgroup, which isthe set of operations that leave both the successprobability and fidelity invariant. One of ourcontributions in this work is to characterise thissubgroup in terms of its generators and its order.
We consider two cases for the input states general input states (i.e. trivial symmetry group)and the n-fold tensor product of Werner states.
For general input states, we find all protocols
for up to n = 5 entangled pairs. For an nfold tensor product of Werner states, we describe
an algorithm that finds a complete set of double

coset representatives. This allows us to optimiseover all bilocal Clifford protocols when distilling
an n-fold tensor product of a Werner state for n
up to 8 pairs.
We find that for n = 2, 3 copies of a Wernerstate, the highest fidelity out of all bilocal Clifford
protocols is achieved by protocols studied before
in the literature. For n = 4 to 8, we find increased
fidelities over previously considered distillation
schemes. Furthermore, we find explicit circuits
achieving the highest fidelity out of all bilocal
Clifford protocols, see Appendix E. These circuits
have comparable depth and number of two-qubit
gates as previously studied protocols, highlighting also the practical feasibility of our findings.
This paper is structured as follows. In Section
2 we describe the preliminaries and notationneeded throughout the paper. Section 3 explains bilocal Clifford distillation protocols andhow the optimisation over such protocols can berephrased as an optimisation over elements fromthe symplectic group Sp(2n, F2 ). In Section 4
we characterise the distillation subgroup Dn . In
Section 5 we prove a further reduction of oursearch space when the state to be distilled isan n-fold tensor product of a Werner state. In
Section 6 we present our optimisation results. We
end with conclusions and discussions in Section 7.

2 Preliminaries
We begin by setting some relevant notation. The
field with two elements is denoted by F2 . We use
the notation Ui to denote a single-qubit operation
on qubit i. The single-qubit operations that we
use are the Pauli gates (I, X, Y and Z), theHadamard gate (H) and the phase gate (S).
Moreover, we denote by CNOTij a controlledNOT operation with control qubit i and target
qubit j, by CZij a controlled-Z operation between
qubits i and j and by SWAPij the operation thatswaps qubits i and j.

2.1 Pauli group and Clifford group
The Pauli matrices are defined as
"

#

"

#

1 0
I=
,
0 1

0 1
X=
,
1 0

"

"

#

0 −i
Y =
,
i 0

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

#

(1)

1 0
Z=
.
0 −1
2

The Pauli group with phases on n qubits P nconsists of all 2n × 2n matrices of the form λP1 ⊗· · · ⊗ Pn with λ ∈ {±1, ±i} and Pi ∈ {I, X, Y, Z}
for all i ∈ {1, . . . , n}, together with standard
matrix multiplication. Of particular interest to
us is the Pauli group without any phase factors,
Pn ∼= P n /hiI ⊗n i. Here hiI ⊗n i is the subgroup
generated by iI ⊗n . We will call this the Pauligroup for short. An element of the group Pn isreferred to as a Pauli string (of length n). The
order of Pn equals |Pn | = 4n .
An important class of gates in quantum information theory are the so-called Clifford gates [43].
Circuits composed of Clifford gates are efficiently
classically simulable, yet can be used to create
complex quantum states, which are used for example in stabiliser error correction. The Cliffordgates on n qubits form a group Cn , and eachC ∈ Cn induces an automorphism f : P n →P n on P n by conjugating each element with C,
i.e. f (P ) = CP C † . The Clifford group Cn isgenerated by Hadamard- (Hi ) and phase (Si )gates on each qubit (1 ≤ i ≤ n) and CNOT gates
between every pair (i, j) of qubits. In matrix
representation, these gates are given by
"

#

1 1 1
H=√
,
2 1 −11
0
CNOT = 
0
0

"

#

1 0
S=
,
0 i
0
1
0
0

0
0
0
1

(2)



0
0

.
1
0

(3)

2.2 Binary representation of the Pauli groupand the Clifford group
The elements of the Pauli group and the Cliffordgroup can be described in terms of binary vectors
and matrices, respectively. To see this, we first
introduce the following notation for the Paulimatrices.
τ00 = I,

τ10 = X,

τ11 = iY,

τ01 = Z. (4)We extend this notation to tensor products ofPauli matrices as follows.
τv := τv1 vn+1 ⊗ · · · ⊗ τvn v2n ,v ∈ F2n2 ,paper, so an element λτv , λ ∈ {±1, ±i}, of P n canbe represented by the binary vector v ∈ F2n
2 . Themultiplication of the elements of P n corresponds
then to the addition of the binary vectors.
For any C ∈ Cn , the conjugation map fcorresponds to a linear map on the set of binary
vectors (and thus on P n ). The map f is an automorphism, and thus preserves the commutation
relations of the elements of P n . To see what this
implies for the linear transformation in the binary
picture, let v, w ∈ F2n
2 . ThenTτv τw = (−1)v Ωw τw τv ,
"

#

0 In
where Ω =. A proof of this formula can
In 0
be found in Appendix A.
Let M denote the linear transformation corresponding to conjugation by C. It follows fromequation (6) thatT

τM v τM w = (−1)(M v) ΩM w τM w τM v .

(7)

By equation (6), we know that τv and τw
commute iff v T Ωw = 0 and anti-commute iffv T Ωw = 1. In order to preserve the commutation
relations, it must then hold that v T M T ΩM w =Tv T Ωw for all v, w ∈ F2n
2 , so M ΩM = Ω.
The matrices M that satisfy this condition thus
preserve the so-called symplectic inner productω(v, w) ≡ v T Ωw between any two v, w ∈ F2n
2 .
These matrices form a group known as the symplectic group over F2 , denoted by Sp(2n, F2 ). The
order of the symplectic group over F2 is wellknown [44] to be equal to2| Sp(2n, F2 )| = 2nnY(4j − 1).

(8)

j=1

The symplectic complement of a subspace V2nof F2n2 is defined as the set of elements of F2
that have zero symplectic inner product with allelements from V ,V ⊥ = {v ∈ F2n
2 | ω(v, w) = 0 ∀w ∈ V } .

(9)The symplectic complement satisfies the following property,(5)

As mentioned in Section 2.1, the global phasefactors are not important in the context of this

(6)

V⊥

⊥

=V .

(10)

Calculations involving a symplectic matrix
M can often be simplified by writing it as a

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

3

1)
Nn

i=1 ρi

2)

Φ

+ ⊗n

CT

A

C†

B

CT

A

C†

B

NP

3)

Φ+

A

⊗n

C NP

C†

4)

B
A

⊗n
Φ+

NP̃

B

Figure 1: Schematic description of how bilocal Clifford
circuits map n-qubit bipartite systems to n-qubit
bipartite systems. From 1) to 2), we rewrite the state⊗n

as ⊗ni=1 ρi = (I ⊗ N ) |Φ+ i, whereP†
N (·) = P ∈Pn pP P (·) P . In 3), we use the fact⊗n⊗nthat AT ⊗ I |Φ+ i = I ⊗ A |Φ+ i
for any 2n × 2n
matrix A [46]. For 4), we use the fact the Cliffords act
on the group of Pauli strings Pn .
#

"

A B
, with A, B, C, D ∈block matrix M =C D
Mn×n (F2 ). From the condition M T ΩM = Ω itfollows that the blocks satisfy
B T D + DT B = 0,
AT C + C T A = 0,

(11)

AT D + C T B = I n .
Moreover, the inverse of M is given by
"

M

−1

#

DT B T=.
C T AT(12)

Let φ : Cn → Sp(2n, F2 ) be the function thatmaps every Clifford gate to the corresponding
symplectic matrix. This map is a surjective
group homomorphism [45]. The symplectic group
Sp(2n, F2 ) is thus generated by the images of agenerating set of the Clifford group Cn under φ.

3 Bilocal Clifford protocols
This section covers the structure of the distillation protocols that are considered in this paper.

We consider a system consisting of two parties,
Alice and Bob, that share n entangled two-qubit
states. We focus on states that are diagonalin the Bell basis. Bell-diagonal states naturally
arise with realistic noise models such as dephasing
and depolarizing. Moreover, any bipartite state
can be twirled into a Bell-diagonal state while
preserving the fidelity [9]. We note that the
protocols found in our paper are also relevant tostates that are not necessarily Bell diagonal —the performance of a protocol on a Bell-diagonal
and a not necessarily Bell-diagonal state will becomparable as long as the two states in question
are close in trace distance.
Bell-diagonal states can be written asρ = pI Φ+ED+ pY Ψ−Φ+ + pX Ψ+Ψ− + pZ Φ−

ED

Ψ+

Φ− .

(13)

The indices of the probabilities arise from thefollowing correspondence between the Bell states
and the Pauli matrices.
EE1
Φ+ = √ (|00i + |11i) = (I ⊗ I) Φ+ ,2EE1
Ψ+ = √ (|01i + |10i) = (I ⊗ X) Φ+ ,2
E1
Ψ− = √ (|01i − |10i) = (I ⊗ −iY ) Φ+ ,2
E1
Φ− = √ (|00i − |11i) = (I ⊗ Z) Φ+ .
2
(14)Equation (14) gives rise to a bijective mappingfrom the Bell states Φ+ , Ψ+ , |Ψ− i and |Φ− ito the Pauli matrices I, X, Y and Z, respectively.
We denote a tensor product of n Bell-diagonalstates by a tensor product of Pauli matrices, e.g.
Φ+ ⊗ Ψ+ ⊗ |Ψ− i ⊗ |Φ− i is denoted by I ⊗ X ⊗Y ⊗ Z.
We generalise the notation of equation (13) anddenote by pP the probability that the system
is in the state described by P ∈ Pn . In thesubscript we will not explicitly denote the tensor
product, e.g. pXY denotes the probability thatthe system is described by X ⊗ Y . The initialstate of the protocol consisting of n entangled
two-qubit states can thus be fully described by
the set of probabilities Q = {pP1 P2 ...Pn : Pi ∈{I, X, Y, Z}}. We refer to such a system as ann-qubit bipartite system. When working in thebinary representation, we write pv instead of pP ,Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

4where v is a binary vector and pv = pP if v is thebinary representation of P . It will be clear fromthe context which convention is used.

|Φ− i state, which correspond to the I and Z Paulimatrix, respectively. The success probability ofthe protocol is thus equal to

3.1 Bilocal Clifford circuits
The first step of the protocol is the performanceof bilocal Clifford operations. That is, if Aliceapplies a Clifford operation C̃ ∈ Cn to her qubits,
then Bob applies C̃ ∗ , the entry-wise complex
conjugate of C̃, to his qubits (see Fig. 1). This
leads to a permutation of the set Q. In particular,
each element pP of Q is mapped [46] to pC̃ T P C̃ ∗ , orequivalently, pCP C † , where we defined C = C̃ T ∈Cn . We denote the probabilities that describe thepermuted state by p̃P1 P2 ...Pn .
We note here that the most general permutation on Q by local unitaries consists of applying
bilocal Cliffords followed by a Pauli string applied to either Alice or Bob’s side [45]. These
Pauli strings can be used to reorder locally thecoefficients of the states.
Since (bilocal) Clifford operations form agroup, the Clifford group has a group action
on Q. The (normal) subgroup of the Cliffordgroup that fixes Q point-wise does not change
any of the statistics, and is thus not of interest to us. This subgroup consists of all Paulistrings, and quotienting out the Cliffords by thissubgroup leads to the symplectic group (over F2 ),Sp(2n, F2 ) [45, 47]. We can thus describe a bilocal
Clifford operation by an element M ∈ Sp(2n, F2 ).
To simplify notation, we sometimes slightly abuse
the notation and denote by C ∈ Sp(2n, F2 ) the
symplectic matrix corresponding to conjugation
by C ∈ Cn , but it should be kept in mind thatalways the symplectic matrix M is meant.

3.2 Measurements and postselection for bilocal Clifford protocols
In the second step, Alice and Bob perform measurements in the computational basis on n − 1 of
their qubits. Alice and Bob report their results
to each other using classical communication. If
the outcomes are equal, they keep the state thatwas not measured. In this case, the protocol iscalled successful. If the outcomes are not equal,
they discard all states, and the protocol is not
successful. The probability that a protocol issuccessful is equal to the probability that allmeasured states are either in the Φ+ or in theXp̃P1 Q2 ...Qn ,P1 ∈{I,X,Y,Z},
Qj ∈{I,Z}

psuc =(15)

where we used the convention that the first twoqubit state is not measured. Moreover, thefidelity between the remaining state and the Φ+state is equal toP

Fout =

Qj ∈{I,Z} p̃I1 Q2 ...Qn

psuc

.

(16)

To simplify notation in the rest of this paper,
we introduce the following two definitions.
Definition 3.1. The base of an n-qubit bipartite
quantum system is given byno

B = v ∈ F2n
2 | vi = 0 ∀i ∈ {1, ..., n + 1} .

Note that the base vectors correspond to thePauli strings I1 ⊗ Q2 ⊗ ... ⊗ Qn ∈ Pn with Qj ∈{I, Z} for all j ∈ {2, ..., n}.
Definition 3.2. The pillars of an n-qubit bipartite quantum system are given byno

P = v ∈ F2n
2 | vi = 0 ∀i ∈ {2, ..., n} .

The elements of the pillars correspond to thePauli strings P1 ⊗ Q2 ⊗ ... ⊗ Qn ∈ Pn with P1 ∈{I, X, Y, Z} and Qj ∈ {I, Z} for all j ∈ {2, ..., n}.
The naming of the base and pillars is made clear
when the probabilities pP are ordered in an ndimensional hypercube, where each dimension
corresponds to a qubit pair, see Fig. 2.
Using these definitions, equation (15) can be
rewritten as
X
psuc =
p̃v ,
(17)
v∈P

and equation (16) asPp̃v
PF = v∈B .
v∈P p̃v(18)

The fidelity as defined above corresponds to the
I coefficient of the output state, and does not
suffice to describe the output state completely.

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

5Figure 2: Probabilities that describe the state of a 2-pair system (left) and a 3-pair system (right). The light grey
rectangles/cylinders highlight the probabilities that correspond to the pillars. The darker circles highlight theprobabilities that correspond to the base. For the 3-pair system we have labelled here only the coefficients that areon the front, right and top face.

To describe the output state, we require theX, Y and Z coefficients as well. Similarly toequation (18), these coefficients Fi are describedin terms of the probabilities byPv∈B+vi p̃v.
Fi = Pv∈P p̃v(19)

Here, vi is v1 = e1 , v2 = e1 + en+1 , v3 = en+1 ,corresponding to the X, Y and Z coefficients,
respectively and we have used the standard basis
vectors {ei : i ∈ {1, ..., 2n}} of F2n
2 .
The fidelity, success probability and the three
Fi coefficients are referred to as the distillation
statistics. Importantly, we are not interested in
permutations of the three Fi coefficients, since
they can be permuted arbitrarily by local operations after the measurement step.
In the binary picture, the distillation statistics
can be calculated using the inverse of the symplectic matrix, which can be efficiently calculatedusing (12). Let M be the symplectic matrix
corresponding to a permutation P 7→ CP C † ,C ∈ Cn . We wish to determine which binary
vectors are mapped to the vectors corresponding
to the base and the pillars by M . Since M
permutes the binary vectors, this is equivalent todetermining where the base and pillar vectors are
mapped to by M −1 .
Finally, there is a direct analogy between our
optimisation over bilocal Clifford protocols, andquantum error detection schemes of the formshown in Fig. 3. Such schemes will detect as

|φi
n

|0i
..
.

≈ |φi
C

NP

C†

|0i
Figure 3: Equivalence between bilocal Clifford protocols
and a subset of error detection schemes. This circuit
detects as errors the set of Pauli strings that do not end
up in the pillars after applying the Clifford circuit C.

errors the set of Pauli strings that do not end up
in the pillars after applying the Clifford circuit
C. We will not pursue this further in this paper,
however.

4 Preservation of distillation statistics
The distillation statistics from equations (17),(18) and (19) are the relevant parameters forquantifying an entanglement distillation protocol.
Furthermore, there exist non-identical bilocal
Clifford circuits which result in the same distillation statistics. To find all bilocal Clifford
protocols, it is thus sufficient to find a representative bilocal Clifford protocol for each uniquecollection of distillation statistics. In this section
we characterise these representatives for general
input states.

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

6

First, we specify the set of bilocal Clifford
operations that preserve the distillation statistics.
We denote this set by Dn . Now observe that
Dn is a subgroup of Sp(2n, F2 ). Moreover, let
M ∈ Sp(2n, F2 ) and consider the corresponding
distillation protocol. We can freely add or remove
elements from Dn at the end of this protocol,
without changing the distillation statistics. Thatis, all elements in the right coset Dn M = {DM :D ∈ Dn } yield the same distillation statistics.
Instead of optimising over all possible Clifford
circuits it thus suffices to optimise over the rightcosets of Dn in Sp(2n, F2 ).

4.1 Characterising the subgroup that preserves
distillation statistics using base and pillars
In this section we explain the relation between
the base and the pillars, which were introduced
in definitions 3.1 and 3.2, respectively, and thedistillation subgroup Dn .
From equations (17), (18) and (19) it canbe observed that for a general initial state, theoperations that preserve the distillation statistics
are precisely those operations that leave simultaneously both the base and pillars invariant, andpermute the three affine subspaces B + e1 , B +en+1 and B +e1 +en+1 . In the following lemma it
is first proven that invariance of the base implies
invariance of the pillars, and vice versa.
Lemma 4.1. Let Q be an n-qubit bipartite
quantum system with base B ⊆ F2n
2 and pillars
2n2n2nP ⊆ F2 . Let π : F2 → F2 , π(v) = M v, withM ∈ Sp(2n, F2 ). Then π[B] = B ⇐⇒ π[P] =P.
Proof. We first prove π[B] = B =⇒ π[P] =P. For this, we first show that the pillars
form the symplectic complement of the base,i.e. B ⊥ = P (see equation (9)). Recall from
Definition 3.1 that v ∈ B if and only if vi = 0
for i = 1, ..., n + 1. Note that B is a subspaceof F2n2 . The symplectic inner product between v
Tand w ∈ F2n
2 , is equal to ω(v, w) = v Ωw. Thisis equal to zero for all v ∈ B if and only if wi = 0
for all i ∈ {2, ..., n}, so iff w ∈ P.
Let v ∈ B and w ∈ P. Then ω(v, w) =0, and since M ∈ Sp(2n, F2n2 ), we have thatω (π(v), π(w)) = 0 as well. Since by assumption
π(v) ∈ B, it follows that π(w) ∈ P. Finally,
since π is an automorphism, we know that it isbijective and thus π[P] = P.

For the other direction, we use the fact thatP ⊥ = B, see equation (10). Then, the above
argument can be repeated with B and P interchanged to conclude that π[B] = B ⇐⇒π[P] = P.
We will now show that not only does preservation of the base imply preservation of the fidelity
and success probability, but that it also implies
that the other coefficients of the output state arepreserved, up to a permutation.
2n
Lemma 4.2. Let π : F2n
2 → F2 , π(v) = M v,
with M ∈ Sp(2n, F2 ) such that π[B] = B. Thenthe coefficients F1 , F2 , F3 are permuted amongst
each other after applying π. In other words, thethree coefficients of the output state are stabilised
as a set after application of M .

Proof. We have the following decomposition of
the linear space P into four cosets of the subspace B:
P = B∪(B + e1 )∪(B + e1 + en+1 )∪(B + en+1 ) .
Since π [B] = B, it follows from Lemma 4.1
that π [P] = P. So π permutes the three cosets
vi + B, vi = e1 , e1 + en+1 , en+1 .
It follows by equation (19) that π permutes thecoefficients F1 , F2 , and F3 .
From Lemma 4.1 and 4.2 we conclude that theoperations that preserve the distillation statistics
for arbitrary input states are precisely the operations that leave the base invariant. We use thisobservation to characterise the subgroup Dn that
preserves the distillation statistics. In the trivial
case that n = 1, we have D1 = Sp(2, F2 ). In
this case, the only base element is the identity
I, which is always mapped to itself under an
automorphism. For all n > 1, however, Dn
is a proper subgroup of Sp(2n, F2 ). Consider
for instance the Hadamard gate on the second
qubit, which is an element of Sp(2n, F2 ). Thisgate induces the swap of X2 and Z2 and hereby
changes the base.

4.2 Generators of the subgroup that preserves
distillation statistics
The goal of this section is to characterise thedistillation subgroup Dn . In particular, we findthe distillation subgroup in terms of a generating
set Tn .

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

7

of Dn in Sp(2n, F2 ) limits the search space of
protocols, in this section a formula for the orderof Dn is presented and proved. As mentioned
earlier, in the trivial case that n = 1 we have
Tn = {H1 , S1 , . . . , Sn } ∪ {CNOTij | 1 ≤ j < i ≤ n} D = Sp(2, F ), and thus |D | = | Sp(2, F )| = 6.
1212
∪ {CNOTij | 2 ≤ i < j ≤ n} .
(20)
For n ≥ 2 the order of Dn is given in Theorem 4.4.

Lemma 4.3. The distillation subgroup is generated by the set Tn , i.e. Dn = hTn i, where

Proof. By inspection, each element of Tn preserves the base, so by Lemmas 4.1 and 4.2 wehave that hT" n i ⊆ #Dn . For the other inclusion,
A B
let M =∈ Dn . We show that we
C D
can reduce such an arbitrary M to the identity matrix by left-multiplication by elements in
hTn i. An overview of the basic matrix operations
corresponding to multiplication by elements ofSp(2n, F2n2 ) is given in Appendix B.
First, note that if M ∈ Dn , then by definition
M [B] ⊆ B and M [P] ⊆ P. In the binary
picture this implies that
Bij = 0 if (i, j) 6= (1, 1),

D12 = · · · = D1n = 0.

Since M has full rank, we cannot have B11 =
D11 = 0. Hence, by multiplying M from the left
by I, H1 or H1 S1 , we may assume that B11 = 0(such that B = 0) and D11 = 1.
That M has full rank implies that the last ncolumns of M are linearly independent. By using
CNOT gates from {CNOTij | 1 ≤ j < i ≤ n} ⊆Tn and {CNOTij | 2 ≤ i < j ≤ n} ⊆ Tn , the Dsubmatrix can be reduced to the identity matrix.
Since D = I and B = 0, it follows from (11)that A = I and C is symmetric. For 1 ≤ j <i denote Sij := (Sj CNOTij )2 ∈ hTn i. Leftmultiplication by Sij corresponds to adding row ito row n + j and adding rows i and j to row n + i.
Note that this preserves the fact that A = D = I
and B = 0.
For j = 1, . . . , n − 1 (in this order), we canmultiply M from the left by elements from {Sj }∪{Sij | i > j} ⊆ hTn i to ensure that Cji = 0
for all 1 ≤ j ≤ i ≤ n. This implies that C isstrictly lower triangular. But if C is strictly lower
triangular and symmetric, C = 0. This implies
that M = I.

4.3 Order of the subgroup that preserves distillation statistics
As noted before, for general input states it issufficient to only consider the right cosets of Dn
in Sp(2n, F2 ). To see how much looking at cosets

Theorem 4.4. For an n-to-1 distillation protocol, with n > 1, the order of Dn is given by2|Dn | = 6 · 2n −1

n−1
Y(2j − 1).

j=1

Proof. First note that D ∈ Dn is fully determinedby how it maps each of the standard basis vectors{ei : i ∈ {1, ..., 2n}} of F2n
2 . We count how manytransformations of the standard basis vectors are
possible.
Let us start by looking at e2n . This is a baseelement, thus it must again be transformed to abase element, because D preserves the distillation
statistics. There are 2n−1 base elements, but
the identity element, the zero vector, is always
mapped to itself by D. Thus there are 2n−1 − 1
possibilities for the transformation of e2n . That
all transformations are indeed possible, is provedby giving a construction. Suppose that e2n is
mapped to a base element v ≡ De2n ∈ B.
We show that v can be transformed to e2n
through left-multiplication by elements of Dn , see
Appendix B. The transformation from e2n to v
can then be obtained by taking the product of
the inverses of these generators in reverse order.
Note that v1 , ..., vn+1 = 0. The vector v can betransformed to e2n by taking the following steps.
1. If v2n = 0, apply a CNOTni ∈ Dn gate withi chosen such that vn+i = 1. Note that
there always is a i such that this is possible,
because otherwise v is the zero vector, whichcorresponds to the identity element I ⊗n .
2. For all i ∈ {2, ..., n} with vn+i = 1, apply a
CNOTin ∈ Dn gate.
Steps 1 and 2 are visually summarised below.
0
0
0
 0 
 0 
 0 






 0 





 1  0  2  0 
v= →−  →−   = e2n
 0 
 0 
 0 






 · 
 · 
 0 
·
1
1


Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.











8

Given the transformation of e2n by D, we
now wish to determine the number of possible
transformations for en . We know that leftmultiplication by D preserves the symplectic
inner product. Hence, since ω(en , e2n ) = 1, it
must hold that ω(Den , De2n ) = 1. Observethat for every non-zero element u ∈ F2n
2 , exactly
for half of the elements of F2nthesymplectic2
inner product with u is equal to one1 . Thusn
|F2n |
there are 22 = 42 = 22n−1 possibilities for thetransformation of en .
We show that each of those transformations
can indeed be achieved. Suppose that D has
mapped en to a vector w ≡ Den ∈ F2n
2 . Becauseω(Den , De2n ) = 1 and De2n is a base vector,
we know that there is at least one i ∈ {2, . . . , n}such that wi = 1. Since we can always apply
a CNOTin ∈ Dn gate, which does not affectthe vector e2n , we can assume without lossof generality that wn = 1. Now w can betransformed to en without affecting e2n by taking
the following steps.
3. For all i with wi = 1 apply a CNOTni ∈ Dngate.
4. For all i 6= n with wn+i = 1, apply a
CZin ∈ Dn gate. This operation results inthe addition of row i to row 2n and the
addition of row n to row n + i. Note that
this operation leaves the base invariant, so
indeed CZin ∈ Dn .

The elements of Dn that leave en and e2n
invariant form a subgroup that is isomorphic toDn−1 , with the number of cosets in Dn equal to22n−1 (2n−1 − 1). Thus
|Dn | = 22n−1 (2n−1 − 1)|Dn−1 |.
By induction on n it follows that
|Dn | = |D1 |

j=2

=6·2

2

= 6 · 2n −1









1
Let u ∈ F2n
2 , such that uk = 1. Then the vectors
u0 ∈ F2nsatisfying ω(u, u0 ) = 1 can be constructed by2choosing u0j ∈ {0, 1} randomly for j ∈ {1, . . . , 2n}\{n+k}and then choosing u0n+k ∈ {0, 1} such that ω(u, u0 ) = 1.

(2j−1 − 1)n−1Y(2j − 1).

The following corollary is a direct consequenceof Theorem 4.4.
Corollary 4.5. The index of Dn in Sp(2n, F2 )is given bynY
1(2j + 1).
[Sp(2n, F2 ) : Dn ] = (2n − 1)3
j=12

Proof. Recall that | Sp(2n, F2 )| = 2n1). As a result,[Sp(2n, F2 ) : Dn ] =Qnjj=1 (4 −| Sp(2n, F2 )|
|Dn |
2

Qn

j
j=1 (4 − 1)Qj
6 · 2n2 −1 n−1
j=1 (2 − 1)Qnjjj=1 (2 − 1)(2 + 1)=
Qn−1 j3 j=1 (2 − 1)
n
Y
1 n
j

=



Thus indeed, given the transformation of e2n ,there are 22n−1 possible transformations of en .
Combining this with the number of transformations of e2n , we find that there are 22n−1 (2n−1 −1)
possible transformations for en and e2n together.

n(2j−1) Y

j=1

·
0
0
0
 · 
 0 
 0 
 0 








 1 







 3  1  4  1  5  1 
w= →−  →−  →−   = en
 · 
 · 
 0 
 0 








 · 
 · 
 0 
 0 
·
·
·
0


j=2

j=2

Steps 3 to 5 are visually summarised below.
22j−1 (2j−1 − 1)Pn

5. If w2n = 1, apply the gate Sn ∈ Dn on qubit
n.



n
Y

2n

(2 + 1).
= (2 − 1)3
j=1

For comparison, we list the values of| Sp(2n, F2 )| and [Sp(2n, F2 ) : Dn ] in Table 1 forn = 2, 3, 4, 5.

4.4 Finding a transversal
In this section, we briefly describe a way to finda transversal for the cosets of Dn in Sp(2n, F2 ).
A transversal is a set that contains exactly
one element for each of the cosets. Once thisAccepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

9

2

3

4

5

| Sp(2n, F2 )|

720

145152047377612800

24815256521932800[Sp(2n, F2 ) : Dn ]

15

315

11475

782595

Table 1: Values of | Sp(2n, F2 )| and [Sp(2n, F2 ) : Dn ] for n = 2, 3, 4, 5.

transversal is found, it can be applied to anarbitrary n-qubit input state to calculate all possible distillation statistics that can be achieved
using bilocal Clifford circuits. From this set of
distillation statistics, the optimal protocol basedon any optimality criterion can be selected.
In order to find a transversal, random elementsfrom the symplectic group Sp(2n, F2 ) are sampled. A sampled element is added to the setof representatives if the corresponding coset is
not yet represented in this set. Recall that twoelements belong to the same coset if they resultin the same distillation statistics (for a general
input state). This is the case if and only if
the same Pauli strings are mapped to the base.
More formally, consider an n-qubit pairs bipartite
system with base B in the binary picture. Let
M1 , M2 ∈ Sp(2n, F2 ). Let V denote the set ofbinary vectors that are mapped to the base by M1
and let W denote the set of binary vectors thatare mapped to the base by M2 . Then M1 and M2
belong to the same coset if and only if V = W .
Because M1 and M2 permute the binary Pauli
vectors, this is equivalent to M1−1 [B] = M2−1 [B].
The sampling is continued until the set ofrepresentatives has size [Sp(2n, F2 ) : Dn ]. Notethat finding a transversal in the way described inthis section is equivalent to the coupon collector’s
problem. Hence, it has expected running timeO([Sp(2n, F2 ) : Dn ] log[Sp(2n, F2 ) : Dn ]).

distinct distillation protocols correspond to the
double cosets Dn \ Sp(n, F2 )/Kn , similar to ourargument before for right cosets for general input
states. In this section, we describe how one
can rewrite an arbitrary symplectic matrix M toanother symplectic matrix M 0 of a specific form,
which is in the same double coset as M . Sucha representative M 0 of the double coset has asmaller number of free parameters, reducing thesearch space significantly.
Recall that an overview of the basic matrix operations corresponding to elements of Sp(2n, F2n
2 )is given in Appendix B.
Lemma 5.1. Let M ∈ Sp(2n, F2 ). There exists
M 0 in the double coset Dn M Kn that is of the form

"

M0 =

Here we describe our reduction of the search spacewhen the input state is an n-fold tensor productof Werner states. A Werner state has coefficientsinpI = Fin , pX = pY = pZ = 1−F
3 , and its n-foldtensor product is highly symmetric — it is left
invariant under any element of Kn , where
Kn = h {SWAPij }1≤i<j≤n ∪ {Hi }ni=1 ∪ {Si }ni=1 i.
We leverage this symmetry by noting that the

0


A B

,
A
=

 a
0 AT


0



 b

B=

bT





,
In−1 
,E +baT (n−1)×(n−1)

where a, b ∈ F2n−1 and E ∈ F2
symmetric with zeroes on the diagonal.

is

Proof. Let M 0 ∈ Dn M Kn be such that
Mij0 = δij

5 Reduction for n-fold tensor productsof Werner states

1#for (i, j) ∈ [n] × {2, . . . , k}(21)

with 1 ≤ k ≤ n as large as possible. Note thatfor k = 1 the condition is trivially fulfilled.
Claim: k = n.
Proof of claim. Suppose that k < n. Then0
Mk+1,k+1= 0, otherwise we can use row operations on M 0 (left-multiplication by matrices
0
CNOTk+1,i ∈ Dn ) to obtain Mi,k+1= δi,k+1 for
all i ∈ [n] while keeping (21), contradicting the
maximality of k.
0
Note that the above condition Mk+1,k+1=
0 needs to hold after applying operations to
M 0 that preserve the form in equation (21).

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

10

Thus, by permuting rows in {k + 1, . . . , n} (leftmultiplication by matrices SWAPij ∈ Dn ) or
permuting columns in {1, k + 1, . . . , n} (rightmultiplication by matrices SWAPij ∈ Kn ) we
deduce that Mij0 = 0 for (i, j) ∈ {k + 1, . . . , n} ×
{1, k + 1, . . . , n}. Since we can swap column iand n + i by multiplying from the right with
Hi ∈ Kn , we also have Mij0 = 0 for (i, j) ∈{k + 1, . . . , n} × {n + 1, n + k + 1, . . . , 2n}. Tosummarise, we have
Mij0 = 0 for i ∈ {k + 1, . . . , n}
and j ∈ [2n] \ {n + 2, . . . , n + k}
Mij0 = δij

for i ∈ {2, . . . , k} and j ∈ {2, . . . , k}.

Since rows k +1, . . . , n must have zero symplectic
inner product with rows 2, . . . , k, it follows thatrows k + 1, . . . , n must in fact be equal to zero.
Since M 0 has full rank, this implies that k = n. 
0 =0Consider the first row of M 0 . We have M1,j
00
for j = 2, . . . , n. If M1,1
= M1,n+1= 0, thenthe fact that this row has zero symplectic innerproduct with rows 2, . . . , n implies that the firstrow is equal to zero, which is not possible as M 0
has full rank. So by multiplying from the right byI, H1 , or S1 H1 which are in Kn , we may assume
0 = 1 and M 0that M1,1= 0.
 A 1,n+10B
Writing M = C D , we see that A and B
have the following form:


1



 a

A=







,
In−1 

B=

0

0



 b

dT

triangular matrix. Since the first n columnsof M 0 must have pairwise zero symplectic
inner product, this implies that in fact C = 0.
Since AT D + C T B = In , it follows thatD = (AT )−1 = AT , where we have used that A
is self-inverse.
Note that for any permutation π ∈ Sn−1 , we
can replace a, b, E by π(a), π(b), π(E) (permuting
both rows and columns) by multiplying M 0 simultaneously from the left and the right by elements
SWAPij , since SWAPij is an element of Dn andKn for 2 ≤ i < j 6= n. Also, we can replace (a, b)
by (b, a) or (a, a + b) by multiplication from theleft and right by elements from {S1 , H1 }. Hence,
to cover all cases, it suffices to enumerate over the
triples (a, b, E) where a ≤ b ≤ a + b and E runs
over the adjacency matrices of graphs on n − 1
nodes (up to isomorphism).

6 Optimisation results
In the previous sections we have outlined our
methods for finding all possible bilocal Clifford
protocols, which were described in Section 3. In
the following we report our findings, first for up ton = 5 general Bell-diagonal input states, second
for up to n = 8 identical Werner states.





.
E0 

Since row 1 has zero symplectic inner productwith rows 2, . . . , n, it follows that d = b. Notethat for 1 ≤ i < j ≤ n − 1 the symplectic
inner product of rows i + 1 and j + 1 is equal
0 + a b + E0 .
to ai bj + Eji
Since this inner
j i
ij
product is zero, the matrix E := E 0 + baT issymmetric. By multiplying from the right by
Hi Si Hi ∈ Kn (i = 2, . . . , n) if necessary, we may
set the diagonal elements of E 0 such that the
diagonal elements of E are zero.
Recall from Lemma 4.3 that Sij:=(Sj CNOTij )2 ∈ Dn for 1 ≤ j < i. Recall
furthermore that left-multiplication of M 0 by
Sij amounts to adding row i to row n + j
and adding rows i and j to row n + i. By
left-multiplication by elements Sij ∈ Dn andSi ∈ Dn we may (without changing the first nrows of M 0 ) assume that C is a strictly upper

6.1 Achieved distillation statistics for general
input states
In Fig. 4 we show the achievable (psuc , Fout ) pairs
for n = 2, 3, 4, 5 copies of a state with coefficients
pI = 0.7, pX = 0.15, pY = 0.10, pZ = 0.05.
We also plot the envelope, indicating the best
performing schemes. Moreover, our results forn = 5 clearly show that picking an arbitrary coset
does not give a good protocol in general.
Furthermore, we consider the n = 2 scenario
where the two input states are equal, i.e. bothhave equal values for the pI , pX , pY , pZ parameters. By comparing all analytic expressions of
the output fidelity as a function of pI , pX , pY , pZ ,we find that the DEJMPS protocol achieves thehighest fidelity out of all bilocal Clifford protocols(see [48] for the details).
While we do not explore this direction, theresults can also be applied to less symmetriccases, i.e. when the n pairs are not the same. Thissituation is, for example, relevant when states

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

11

Fout
n=2
n=3
n=4
n=5

0.9
0.85
0.8
0.75
0.7
0.2

0.3

0.4

0.5

0.6

0.7

0.8

psuc

Figure 4: Achievable (psuc , Fout ) pairs for n = 2 to 5
copies of a state with coefficients pI = 0.7, pX = 0.15,
pY = 0.10, pZ = 0.05. The highest achievable pairs
are indicated by a solid line for each number of copies.
Not included in the plot are those distillation protocols
with fidelity smaller than F = 0.68.

arrive at different times, and thus experience
different amounts of decoherence.

6.2 Achieved distillation statistics for n-foldWerner states
Here we show our results for the case of an n-foldtensor product of a Werner state. First, we list
the number of cases to check (i.e. the number of
triples (a, b, E), see Section 5) and the number ofdistinct distillation protocols for this scenario in
Table 2.
The number of cases and distinct protocols still
rapidly grow with n, but our reduction allowed
to consider all possible distillation protocols forn = 8 in about a day of computer run-time. Thisshould be compared with a naive optimisation
over all elements of the symplectic group —for n = 8 the ratio between the order of thesymplectic group and the number of cases tocheck is approximately 2 · 1034 . For n = 9
and higher however, our current method becomes
infeasible, requiring too many cases to consider.
One could imagine improving on Lemma V.1 asto reduce the gap between the number of cases
to check and the number of distinct distillation
protocols. This could potentially only allow foran enumeration up to n ≈ 11. This can bemade more quantitative by considering that alower bound on the number !
of double cosets is2 )|given by |Sp(2n,F|Dn ||Kn | = O

n2

2 2
6n n!

, since the size ofa double coset can be at most |Dn | · |Kn |. We
note here that we are approximating the numberof distinct distillation statistics by the number ofdouble cosets. With such a lower bound, it isclear that a full enumeration becomes infeasible
for n ' 11, even in the best-case scenario.
We note here that the large number of distinct
protocols only means that a full enumeration of
the distillation protocols becomes infeasible forlarger n. In particular, it does not necessarily preclude an optimisation of the distillation
protocols for a given metric, such as the output
fidelity. In this paper, however, we only consider
an optimisation by first fully enumerating all
distinct protocols.
In order to gauge the advantage of the optimal
protocols that we find for Werner states, we
compare them with the class of protocols wecall concatenated DEJMPS protocols. These arebilocal Clifford protocols that are built frommultiple iterations of the DEJMPS protocol [10],see Appendix C for more information. The
concatenated DEJMPS protocols form a natural generalisation of the (nested) entanglement
pumping protocols [11].
We first investigate the increase in fidelity
Fout − Fin conditioned on the success of the
distillation protocol. We plot the increase in
fidelity as a function of the input fidelity Fin for
n = 2, 3, . . . , 8 in Fig. 5. The dotted lines correspond to the concatenated DEJMPS protocols,
the solid lines correspond to the protocols that
achieve the highest output fidelity found with
our optimisation. For completeness, we show
the success probabilities and fidelities for the
optimised protocols for n = 2, 3, . . . , 8 in Tables 5,6, 7 and 8 in Appendix E.
Let us now discuss Fig. 5. First we observethat for n = 2, 3, the optimal protocols correspond to the original DEJMPS [10] and doubleselection [37] protocols. However, for n > 3,
we find distillation protocols that outperform theconcatenated DEJMPS protocols.
We find that the optimal protocol for n = 4
achieves the same fidelity as the concatenated
DEJMPS protocol for n = 5, and can be executed with a circuit of the same depth as theconcatenated DEJMPS protocol. This protocol
achieves the same distillation statistics as the
protocol found with different means in the recent
work from [49].

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

12

2

3

4

5

6

7

8

Cases

2

10

60

561

6358

1115402917980

Distinct protocols

2

5

13

34

108

379

1736

Table 2: Number of cases to check and number of distinct distillation protocols for n identical Werner states.

Fout − Fin

1-Fout

0.2

n=4
n=5
n=6
n=7
n=8

10−2

n=2
n=3
n=4
n=5
n=6
n=7
n=8

0.25

10−3

0.15
0.1

10−4

0.05
0

0.5

0.6

0.7

0.8

0.9

1

Fin 10−5

Figure 5: Comparison between the increase in fidelity
Fout − Fin with our optimisation (solid) andconcatenated DEJMPS protocol (dotted), for n = 2 to
8 identical Werner states with fidelity Fin . Note how
the n = 5 concatenated DEJMPS protocol overlaps
with an optimised n = 4 protocol.

For n = 5 there is a large gap between
the optimised protocols and the concatenated
DEJMPS protocol. We make this now morequantitative by expanding the Fout for high input
fidelity Fin ≈ 1. For n = 5, the concatenated
DEJMPS protocol has quadratic scaling in theinfidelity,

1−



2
(1 − F )2 + O (1 − F )3 ,3(22)

while the optimised protocol has a cubic scaling
in the infidelity
1−



10
(1 − F )3 + O (1 − F )4 .
9(23)This is particularly surprising, since previous
protocols with five or less pairs [36] have a scalingthat is at most quadratic in the infidelity. We list
the scaling of the found protocols in Table. 9.
Next, we investigate the behavior of the protocols for high fidelities Fin ≈ 1. In Fig. 6 weplot the infidelity 1 − Fout as a function of the
input fidelity Fin . We observe that it is possible

0.9

0.92

0.94

0.96

0.98

1

Fin

Figure 6: Comparison between the achieved infidelities
1 − Fout with our optimisation (solid) andconcatenated DEJMPS protocol (dotted), for n = 4 to
8 identical Werner states with fidelity Fin .

to reach fidelities of around 0.999 using six copiesof Werner states with fidelity Fin = 0.9. We do
not plot the results for n = 2, 3 since we find no
improvements with respect to previous protocols.
We have seen that the optimised distillation
protocols are capable of achieving a higher fidelity than the concatenated DEJMPS protocols.
However, the optimised distillation protocols also
have a lower success probability. This motivates
us to investigate three metrics, each of which
combines the success probability and the qualityof the resultant state. As the first metric, we
use the distillable entanglement rate which we approximate by combining the distillation protocol
together with a hashing protocol [8]. That is,given n entangled pairs, we first perform an n-to1 distillation protocol and then use the output
as input for the hashing protocol. The rate
r at which this procedure produces maximallyentangled state is given byr=(1 − H(p)) · psuc
,
n

(24)

where H(p) is the entropy in bits of the probability distribution p = (pI , pX , pY , pZ ) correspond-

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

13

ing to the output state. This metric has been usedpreviously and is sometimes called the hashingyield [36].
We compare the achieved rate of all founddistillation protocols and the concatenated DEJMPS protocols in Fig. 7. We show both achieved
rates and the ratio between them. We find thatfor n > 3 and fidelities . 0.76 the optimalbilocal Clifford protocols achieve up to rates
three times greater than concatenated DEJMPS
protocols. Conversely, for high fidelities it suffices
to use concatenated DEJMPS protocols if one isinterested in maximising the asymptotic rate.

Rate
Optimised
Conc. DEJMPS

10-1
10-2
10-3
10-4

Fin

For the second metric, we consider the morepractical application of achieving a certain
threshold fidelity Ftar using (at most) one roundof distillation. While there exist a number ofapplications that require a minimum fidelity, we
consider here device-independent quantum key
distribution. If one assumes only depolarising noise, a bound on the minimum fidelity isgiven [50] by Ftar = 0.930025 to perform deviceindependent quantum key distribution. In what
follows, we will assume that it is necessary toachieve Ftar , and that the other coefficients of theoutput state are equal.

Ratio

In Fig. 8 we show the average rate at which
entanglement can be distilled to Ftar using asingle round of distillation. We find a similar
behaviour as in Fig. 7, where for higher fidelities(≈ 0.78) it suffices to perform concatenated
DEJMPS protocols, while for lower fidelities the
optimised protocols achieve a larger rate.

Figure 7: Comparison between the achieved rates after
distilling and then hashing with our optimisation (solid)
and the concatenated DEJMPS (dotted) protocol. For
both cases, we take the envelope of all protocols on
n = 2 to 8 identical Werner states with fidelity Fin .
Top) achieved rates with our optimisation andconcatenated DEJMPS protocols. Bottom) Ratio
between the rate with our optimisation andconcatenated DEJMPS protocols.

Finally, we consider the metric of the success probability times the relative entropy ofentanglement [51, 52, 53]. The relative entropyof entanglement (REE) is an upper bound on
the distillable entanglement [53], and can becomputed exactly for Bell-diagonal states [51].
The success probability times the REE is aquantity that has been used to capture how well a
protocol concentrates the present entanglement,
and has even been used to show optimality ofsome distillation protocols, see [34]. We notethat we have found that the success probability
times the REE decreases as the number of input
states increases. We thus consider maximising
the above quantity for fixed values of n. To
this end, we plot the difference between the
success probability and the REE for all optimised
protocols and concatenated DEJMPS protocols

6
5
4
3
2
1

0.5

0.6

0.7

0.8

0.9

1.0

Fin

in Fig. 9 for n = 2, . . . , 8. We find for alln > 3 that the full optimisation over bilocal
Clifford protocols allows for a larger value of thesuccess probability times the REE, in particularfor higher fidelities. This should be contrasted
with the results from Figs. 7 and 8, where thefull optimisation only showed an improvement
over concatenated DEJMPS protocols for lower
fidelities.
Let us conclude with an investigation of circuitsthat achieve the highest fidelity for n = 4 to 8.
Interestingly, these protocols can be implemented
with low-depth circuits. We performed a searchover circuits of the form described in Appendix D,
to find circuits that achieve the highest fidelity.

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

14

Rate

100

∆(Rel. ent. · psuc )Optimised
Conc. DEJMPS

n=2
n=3
n=4
n=5
n=6
n=7
n=8

0.04
0.03

10-1

0.02
0.01

10-2

Fin

0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00

Figure 8: Average rate at which entanglement can be
distilled to a minimum fidelity of Ftar = 0.930025,
using both our optimisation (solid) and concatenated
DEJMPS (dotted) protocols.

We report these circuits in Appendix D. For n = 4
to 8, we find a total number of two-qubit gates of4, 7, 8, 11 and 13. Furthermore, the corresponding circuit depths are 3, 5, 6, 6 and 7, respectively.
For comparison, the circuit from [49] for n = 4
pairs has 4 two-qubit gates and depth 5. This
protocol can be converted to our optimal n =4 protocol by left-multiplication with elements
in Dn and right-multiplication with elements in
Kn . Therefore, both protocols achieve the same
distillation statistics. The protocol from [54] forn = 5 pairs, which achieves the same fidelity andsuccess probability as the concatenated DEJMPS
protocol, has 4 two-qubit gates and depth 4. We
note here that the fidelity and success probability
do not necessarily need to correspond to a uniquespecific distillation protocol. As an example,
for n = 8 there are four distinct protocols that
achieve the highest fidelity. These protocols havethe same fidelity and success probability, butdiffer in their Fi components.

7 Conclusions and discussions
Our goal in this paper was to find good distillation protocols requiring modest resources. For
this, we introduced the class of bilocal Clifford
protocols which generalises many existing protocols. The protocols in this class require only asingle round of communication between the end
parties and the implementation of Clifford gates.
Within this class, we leveraged group theoretic

0.00

0.5

0.6

0.7

0.8

0.9

1.0

Fin

Figure 9: Difference between the product of the successprobability and relative entropy of entanglement of theresultant state, optimised over all bilocal Clifford
protocols and all concatenated DEJMPS protocols.

tools to find all distillation protocols for up ton = 5 pairs for general Bell-diagonal states andup to n = 8 pairs for the n-fold tensor product ofa Werner state.
Some of the protocols that we found strongly
improve upon the fidelities and rates of previous
protocols. Moreover, we give explicit circuits forthe optimal protocols for the n-fold Werner state
case, with n = 2 to n = 8. These circuits havecomparable depth and number of two-qubit gatesas previous protocols, indicating the experimental
feasibility of the new protocols. If the improved
performance holds with noisy operations, then it
will translate in improved forecasts for the performance of near-term quantum networks [54, 55]
or distributed quantum computation [7]. Finally,
since we have enumerated all bilocal Clifford
protocols up to n = 5, it is possible to pick andchoose the protocol that maximises any figure of
merit for any particular set of input states. Our
software can be found at [48].
In this work we considered distilling one entangled pair out of n pairs. The results here could
be extended to n to m distillation protocols bygeneralising Lemma 5.1 and the characterisationof the distillation subgroup to the case of n tom distillation. Such distillation protocols would
allow for a more refined trade-off between the
fidelity and the success probability/rate. Anotherinteresting avenue would be to generalise thetools to higher dimensional entangled states.

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

15

Acknowledgements
This work was supported by the QIA project(funded by European Union’s Horizon 2020,
Grant Agreement No.
820445) and by the
Netherlands Organization for Scientific Research (NWO/OCW), as part of the Quantum Software Consortium program (Project No.
024.003.037/3368). The authors thank T. Coopmans for initial discussions, and F. Rozpędek
and S. Bäuml for valuable feedback on the
manuscript.

References[1] Charles H. Bennett and Gilles Brassard.
“Quantum cryptography: Public key distribution and coin tossing”. TheoreticalComputer Science 560, 7–11 (2014).
[2] Kai Chen and Hoi-Kwong Lo. “Conference key agreement and quantum sharingof classical secrets with noisy ghz states”.
In Proceedings. International Symposium on
Information Theory, 2005. ISIT 2005. Pages
1607–1611. IEEE (2005).
[3] Jérémy Ribeiro, Gláucia Murta, andStephanie Wehner.
“Fully deviceindependent conference key agreement”.
Physical Review A 97, 022307 (2018).
[4] Richard Jozsa,
Daniel S. Abrams,
Jonathan P. Dowling, and Colin P. Williams.
“Quantum clock synchronization based onshared prior entanglement”. Physical Review
Letters 85, 2010 (2000).
[5] Lov K. Grover. “Quantum telecomputation” (1997). arXiv:quant-ph/9704012.
[6] J. Ignacio Cirac, Artur Ekert, Susana F.
Huelga,andChiaraMacchiavello.
“Distributed quantum computation overnoisy channels”. Physical Review A 59,
4249 (1999).
[7] Naomi H. Nickerson, Ying Li, and Simon C.
Benjamin. “Topological quantum computing
with a very noisy network and local error
rates approaching one percent”. Naturecommunications 4, 1–5 (2013).
[8] Charles H. Bennett, Gilles Brassard, Sandu
Popescu, Benjamin Schumacher, John A.
Smolin, and William K. Wootters. “Purification of noisy entanglement and faithful

teleportation via noisy channels”. PhysicalReview Letters 76, 722 (1996).
[9] Charles H. Bennett, David P. Divincenzo,
John A. Smolin, and William K. Wootters.
“Mixed-state entanglement and quantum error correction”. Physical Review A 54,
3824–3851 (1996).
[10] David Deutsch, Artur Ekert, Richard Jozsa,
Chiara Macchiavello, Sandu Popescu, andAnna Sanpera. “Quantum privacy amplification and the security of quantum cryptography over noisy channels”. Physical Review
Letters 77, 2818–2821 (1996).
[11] Wolfgang Dür and Hans J. Briegel. “Entanglement purification and quantum error
correction”. Reports on Progress in Physics
70, 1381 (2007).
[12] Igor Devetak and Andreas Winter. “Distillation of secret key and entanglement fromquantum states”. Proceedings of the Royal
Society A: Mathematical, Physical and engineering sciences 461, 207–235 (2005).
[13] Francesco Buscemi and Nilanjana Datta.
“Distilling entanglement from arbitrary resources”. Journal of Mathematical Physics
51, 102201 (2010).
[14] Felix Leditzky, Nilanjana Datta, andGraeme Smith. “Useful states and entanglement distillation”. IEEE Transactions on
Information Theory 64, 4689–4708 (2017).
[15] Vlatko Vedral. “On bound entanglement
assisted distillation”. Physics Letters A 262,
121–124 (1999).
[16] Satoshi Ishizaka. “Bound entanglement provides convertibility of pure entangled states”.
Physical Review Letters 93, 190501 (2004).
[17] Ferran Riera-Sàbat, Pavel Sekatski, Alexander Pirker, and Wolfgang Dür. “Entanglement purification by counting and locating
errors with entangling measurements”. Physical Review A 104, 012419 (2021).
[18] Ferran Riera-Sàbat,Pavel Sekatski,
Alexander Pirker, and Wolfgang Dür.
“Entanglement-assisted
entanglement
purification”. Physical Review Letters 127,
040502 (2021).
[19] Nicolas Gisin. “Hidden quantum nonlocality
revealed by local filters”. Physics Letters A
210, 151–156 (1996).
[20] Frank Verstraete, Jeroen Dehaene, andBart De Moor. “Local filtering operations

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

16

on two qubits”. Physical Review A 64,
010101 (2001).
[21] Francesco Buscemi and Nilanjana Datta.
“General theory of environment-assisted entanglement distillation”. IEEE transactions
on information theory 59, 1940–1954 (2012).
[22] Miguel A. Martín-Delgado and MiguelNavascués. “Single-step distillation protocol
with generalized beam splitters”. PhysicalReview A 68, 012322 (2003).
[23] Hector Bombin and Miguel A. MartínDelgado. “Entanglement distillation protocols and number theory”. Physical Review A
72, 032313 (2005).
[24] Fernando G. S. L. Brandao and Nilanjana
Datta. “One-shot rates for entanglement
manipulation under non-entangling maps”.
IEEE Transactions on Information Theory
57, 1754–1760 (2011).
[25] Bartosz Regula, Kun Fang, Xin Wang, andMile Gu. “One-shot entanglement distillation beyond local operations and classicalcommunication”. New Journal of Physics 21,
103017 (2019).
[26] Paul G. Kwiat, Salvador Barraza-Lopez, Andre Stefanov, and Nicolas Gisin. “Experimental entanglement distillation and ‘hidden’ non-locality”.
Nature 409, 1014–
1017 (2001).
[27] Jian-Wei Pan, Sara Gasparoni, Rupert
Ursin, Gregor Weihs, and Anton Zeilinger.
“Experimental entanglement purification ofarbitrary unknown states”. Nature 423, 417–
422 (2003).
[28] Takashi Yamamoto,
Masato Koashi,Şahin Kaya Özdemir, and Nobuyuki Imoto.
“Experimental extraction of an entangled
photon pair from two identically decohered
pairs”. Nature 421, 343–346 (2003).
[29] Philip Walther, Kevin J. Resch, Časlav
Brukner, Aephraim M. Steinberg, Jian-Wei
Pan, and Anton Zeilinger. “Quantum nonlocality obtained from local states by entanglement purification”. Physical Review Letters
94, 040504 (2005).
[30] Luo-Kan Chen, Hai-Lin Yong, Ping Xu,
Xing-Can Yao, Tong Xiang, Zheng-Da Li,
Chang Liu, He Lu, Nai-Le Liu, Li Li,
et al. “Experimental nested purification fora linear optical quantum repeater”. Nature
Photonics 11, 695–699 (2017).

[31] Sebastian Ecker, Philipp Sohr, Lukas Bulla,
Marcus Huber, Martin Bohmann, and Rupert Ursin. “Experimental single-copy entanglement distillation”. Physical Review
Letters 127, 040506 (2021).
[32] Rainer Reichle, Dietrich Leibfried, Emanuel
Knill, Joseph W. Britton, R. Bradford
Blakestad, John D. Jost, Christopher
Langer, Roee Ozeri, Signe Seidelin, andDavid J. Wineland. “Experimental purification of two-atom entanglement”. Nature
443, 838–841 (2006).
[33] Norbert Kalb, Andreas A. Reiserer, Peter C.
Humphreys, Jacob J. W. Bakermans, Sten J.
Kamerling, Naomi H. Nickerson, Simon C.
Benjamin, Daniel J. Twitchen, Matthew
Markham, and Ronald Hanson. “Entanglement distillation between solid-state quantum network nodes”. Science 356, 928–
932 (2017).
[34] Filip Rozpędek, Thomas Schiet, Le Phuc
Thinh, David Elkouss, Andrew C. Doherty,
and Stephanie Wehner. “Optimizing practical entanglement distillation”. PhysicalReview A 97, 062333 (2018).
[35] Kun Fang, Xin Wang, Marco Tomamichel,and Runyao Duan. “Non-asymptotic entanglement distillation”. IEEE Transactions on
Information Theory 65, 6454–6465 (2019).
[36] Stefan Krastanov, Victor V. Albert, andLiang Jiang. “Optimized entanglement purification”. Quantum 3, 123 (2019).
[37] Keisuke Fujii and Katsuji Yamamoto. “Entanglement purification with double selection”. Physical Review A 80, 042308 (2009).
[38] Hans J. Briegel, Wolfgang Dür, J. Ignacio
Cirac, and Peter Zoller. “Quantum repeaters:
the role of imperfect local operations inquantum communication”. Physical Review
Letters 81, 5932 (1998).
[39] Wolfgang Dür and Hans J. Briegel. “Entanglement purification for quantum computation”.
Physical Review Letters 90,
067901 (2003).
[40] Wolfgang Dür, Hans J. Briegel, J. Ignacio
Cirac, and Peter Zoller. “Quantum repeaters
based on entanglement purification”. Physical Review A 59, 169 (1999).
[41] Liangzhong Ruan, Wenhan Dai, and Moe Z.
Win.
“Adaptive recurrence quantum
entanglement distillation for two-kraus-

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

17

operator channels”. Physical Review A 97,
052332 (2018).
[42] Karl Gerd H. Vollbrecht and Frank Verstraete. “Interpolation of recurrence andhashing entanglement distillation protocols”.
Physical Review A 71, 062325 (2005).
[43] Daniel Gottesman. “Theory of fault-tolerant
quantum computation”. Physical Review A
57, 127 (1998).
[44] Emil Artin. “Geometric algebra”. Chapter 6,
pages 143–147. Interscience Publishers New
York. (1957). 1 edition.
[45] Jeroen Dehaene, Maarten Van den Nest,
Bart De Moor, and Frank Verstraete. “Local
permutations of products of Bell states andentanglement distillation”. Physical Review
A 67, 022310 (2003).
[46] Mark M. Wilde. “Quantum information theory”. Cambridge University Press. (2013).
arXiv:1106.1445.
[47] Jeroen Dehaene and Bart De Moor. “Clifford group, stabilizer states, and linear andquadratic operations over gf (2)”. PhysicalReview A 68, 042318 (2003).
[48] “Enumerating distillation protocols code”.
DOI: 10.4121/15082515. Accessed: 2021-0204.
[49] Xuanqiang Zhao, Benchi Zhao, Zihe Wang,
Zhixin Song, and Xin Wang. “Practical
distributed quantum information processing
with LOCCNet”. npj Quantum Information7, 159 (2021).
[50] Ernest Y.-Z. Tan, Pavel Sekatski, JeanDaniel Bancal, René Schwonnek, Renato
Renner, Nicolas Sangouard, and Charles
C.-W. Lim.
“Improved DIQKD protocols with finite-size analysis” (2020).
arXiv:2012.08714.
[51] Vlatko Vedral, Martin B. Plenio, Michael A.
Rippin, and Peter L. Knight. “Quantifying
entanglement”. Physical Review Letters 78,
2275 (1997).
[52] Vlatko Vedral and Martin B. Plenio. “Entanglement measures and purification procedures”. Physical Review A 57, 1619 (1998).
[53] Vlatko Vedral. “The role of relative entropy
in quantum information theory”. Reviews ofModern Physics 74, 197 (2002).
[54] Takaaki Matsuo, Clément Durand, and Rodney Van Meter.
“Quantum link bootstrapping using a RuleSet-based communi-

cation protocol”. Physical Review A 100,052320 (2019).
[55] Michelle Victora, Stefan Krastanov, Alexander Sanchez de la Cerda, Steven Willis, andPrineha Narang. “Purification and entanglement routing on quantum networks” (2020).
arXiv:2011.11644.
[56] Dmitri Maslov and Martin Roetteler.
“Shorter stabilizer circuits via bruhat
decomposition
andquantum
circuittransformations”. IEEE Transactions on
Information Theory 64, 4729–4738 (2018).
[57] Sergey Bravyi and Dmitri Maslov.
“Hadamard-free circuits expose the structureof the Clifford group”. IEEE Transactions on
Information Theory 67, 4546–4563 (2021).

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

18

A Background on binary picture
For completeness, we give here more background and derivations on the binary picture used in thiswork. Firstly, we give a derivation of equation (1). Suppose that we have two elements τv , τw ∈ P n ,with v, w ∈ F2n
2 . Thenτv τw = (τv1 vn+1 ⊗ · · · ⊗ τvn v2n )(τw1 wn+1 ⊗ · · · ⊗ τwn w2n )
=

n
O

(25)

τvk vn+k τwk wn+k .

k=1

For all k ∈ {1, . . . , n}, we haveτvk vn+k τwk wn+k = X vk Z vn+k X wk Z wn+k
= X vk (−1)vn+k wk X wk Z vn+k Z wn+k(26)

= (−1)vn+k wk X vk +wk Z vn+k +wn+k= (−1)vn+k wk τvk +wk ,vn+k +wn+k .
As a result,τv τw =nO(−1)vn+k wk τvk +wk ,vn+k +wn+k

(27)

k=1

= (−1)
We can rewritePnvw
k=1 n+k k

τv+w

Pn

k=1 vn+k wk in terms of the vectors v and w:
n
X

"

#

0 In
Ξ=
.
0 0

T

vn+k wk = w Ξv,

k=1

(28)

Hence, the product of τv and τw is given byTτv τw = (−1)w Ξv τv+w .

(29)

Combining equation (29) for τv τw and τv τw , we finally obtainwT Ξv+v T Ξw

τv τw = (−1)

v T ΞT w+v T Ξw

τw τv = (−1)

v T Ωw

τw τv = (−1)"τw τv ,#0 In
Ω = Ξ+Ξ =. (30)In 0
T

Let C ∈ Cn be a Clifford operation and f : P n → P n , f (P ) = CP C † be the corresponding
2n
automorphism. Let π : F2n
2 → F2 be the representation of f in the binary picture. Let v, w ∈T
T
F22n . Then we know that Cτv+w C † = (−1)w Ξv Cτv τw C † = (−1)w Ξv Cτv C † Cτw C † . In the binaryT
representation, the prefactor (−1)w Ξv does not make a difference. Thus, π(v + w) = π(v) + π(w), so
π is a linear map, and there exists a binary 2n × 2n matrix M such that π(v) = M v for all v ∈ F2n
2 .

B Basic row/column operations corresponding to symplectic matrices
In this section we give an overview of the basic row and column operations used in the proofs of Lemma
4.3, Theorem 4.4 and Lemma 5.1 and the corresponding elements of Sp(2n, F2 ). Let M ∈ Mat2n×k (F2 )be a binary (2n × k)-matrix with k ≥ 1. Multiplying M from the left by an element of Sp(2n, F2 )results in basic row operations on the rows of M . The basic row operations corresponding to left
multiplication by elements of Sp(2n, F2 ) are summarized in Table 3 [56].
Similarly, multiplying M ∈ Matk×2n (F2 ) from the right by an element of Sp(2n, F2 ) results in basic
column operations on the columns of M . These column operations are summarized in Table 4.
Note that we are particularly interested in the cases k = 2n (Lemma 4.3, Lemma 5.1) and k = 1(Theorem 4.4), although Table 3 and Table 4 hold true for any k ≥ 1.
Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

19

Element of Sp(2n, F2 )Row operation

Hi

Swapping rows i and n + i

SiAdding row i to row n + i

CNOTijAdding row i to row j and adding row n + j to row n + i

Sij = (Sj CNOTij )2

Adding row i to row n + j and adding rows i and j to row n + i

CZij

Adding row i to row n + j and adding row j to row n + i

SWAPijSwapping rows i and j and swapping rows n + i and n + j

Table 3: Basic row operations corresponding to left multiplication of M ∈ Mat2n×k (F2 ) by the elements ofSp(2n, F2 ) in the first column.

Element of Sp(2n, F2 )Column operation

Hi

Swapping columns i and n + i

SiAdding column n + i to column i

CNOTijAdding column j to column i and adding column n + i to column n + j

Sij = (Sj CNOTij )2

Adding columns n + i and n + j to column i and adding column n + i tocolumn j

CZijAdding column n + i to column j and adding column n + j to column i

SWAPijSwapping columns i and j and swapping columns n + i and n + j

Table 4: Basic column operations corresponding to right multiplication of M ∈ Matk×2n (F2 ) by the elements ofSp(2n, F2 ) in the first column.

C Concatenated DEJMPS protocols
Here we describe the distillation protocols which we compare our results with. These are all based on
the so-called DEJMPS protocol [10]. The DEJMPS protocol takes two pairs of Bell-diagonal states, andoutputs one state. It performs bilocal single-qubit rotations on both pairs, then a bilocal CNOT, andfinally a measurement on one of the pairs where a success is achieved only when correlated outcomesare observed. It is clear that the DEJMPS protocol is an example of a bilocal Clifford protocol. The
DEJMPS protocol can be generalised to a number of pairs n > 2 by applying the DEJMPS protocol
multiple times.
Since the DEJMPS protocol corresponds to 2-1 distillation, the possible ways of combining thedifferent pairs correspond to the number of binary trees on n unlabeled nodes for an n-fold tensor
product of input states. Furthermore, for each of the performed DEJMPS protocols (corresponding
to each parent of the binary tree), we consider all possible single-qubit rotations. The concatenated
DEJMPS protocols are then all protocols that arise in this fashion. Note that this class includes wellknown variants of DEJMPS such as (nested) entanglement pumping protocols [11, 40, 38] or double
selection [37].
Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

20

D Distillation circuits
In this section we are concerned with finding circuits that achieve the highest fidelity for n = 4 to 8
for an n-fold tensor product of a Werner state2 .
We first note that one could use techniques for general Clifford circuit decompositions to decompose
the symplectic matrices of the form in 5.1. However, we found that this would in general lead tocircuits with high depths. Instead, we first find that any distillation protocol has a circuit in a given
form. Then, we randomly generate circuits of that form, until we find circuits that achieve the highest
fidelity, and have small depth.

D.1 Reducing the circuit search space
We use the Bruhat decomposition from [57, 56], which allows to write any Clifford circuit C in the form
C = F W F 0 , with F and, F 0 elements of the so-called Borel subgroup3 and W a layer of Hadamard
gates followed by a permutation σ ∈ Sn . The Borel subgroup Bn is generated by Xi , Si for 1 ≤ i ≤ n
and CNOTij with 1 ≤ j < i ≤ n. For convenience, we denote such CNOT gates as CNOT↑ gates.
Now note that the Borel subgroup Bn is a subgroup of the distillation subgroup Dn . This implies that
the F part of any circuit in the form C = F W F 0 does not change the distillation statistics. Thus, any
distillation protocol has a corresponding circuit of the form W F 0 . Furthermore, since the distillation
subgroup Dn contains elements that arbitrarily permute qubits 2 to n, we can restrict to permutations
that are either the identity, or exchange qubit 1 with j. In practice, we have found that it is sufficient
to only consider W = H2 H3 . . . Hn .
By the results from [57], any element F 0 from Bn can be written as a layer of CNOT↑ gates, a layer
of CZ gates, a layer of phase gates and a layer of Pauli gates. Firstly, the Pauli gates are in the kernelof φ, and thus can be left out. Secondly, the layer of S gates can be moved to the beginning. To see
this, first note that phase gates commute with CZ gates. Then, since CNOTij Si = Si CNOTij and
Sj CNOTij = CNOTij CZij Si Sj , the layer of S gates can be moved to the beginning. Since Wernerstates are invariant under S, the layer of S gates can be removed without changing the distillation
statistics. In the above process of moving the S gates to the beginning, the layer that only had CNOT↑
gates will now have CZ gates as well. In the binary picture we have the following identities,
CNOTij CZkl = CZkl CNOTij ,(31)

CNOTij CZij = CZij CNOTij ,(32)

CNOTik CZij = CZij CNOTik ,(33)

CNOTik CZjk = CZij CZjk CNOTik ,(34)

where the i, j, k, l are assumed to be distinct, and can be verified using Tables 3 and 4. By using theabove identities, the CZ gates can be moved through to the original layer of CZ gates.
It is thus sufficient to consider only elements F 0 that consist of a layer of CNOT↑ gates and a layer
of CZ gates. Now, to find circuits we randomly generate circuits consisting of a layer of CNOT↑ gates,
a layer of CZ gates, and a Hadamard gate on all qubits except the first. We found several circuits that
achieved the largest fidelity, and choose the one with smallest depth. We report the found circuits in
Fig. 10.

2

We are not interested in the cases n = 2 and n = 3, since for those cases the concatenated DEJMPS protocols are
optimal.
3

We use a different convention from [57, 56], where the target index for the CNOT gates in the Borel subgroup islarger than the control index.

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

21

•
•
•
• •
•

H
•

•

Z

H

•

•

H

Z

•

H

Z

•

H

Z

•

H

Z

•

Z

H

•
• •

•

Z

•

(a) n = 4, #2-qubit gates = 4, depth= 3.

•(b) n = 5, #2-qubit gates = 7, depth
= 5.

•

•

•

• •
•
•

•

•

•

H

Z

H

Z

H

Z

H

Z

H

Z

(c) n = 6, #2-qubit gates = 8, depth
=6

•
•
•

•

•

•
•

•

H

Z

• •

H

Z

•

H

Z

•

H

Z

•

H

Z

H

Z

•
•

•
• •
•

•

•

H

Z

H

Z

H

Z

•

H

Z

•

H

Z

H

Z

H

Z

•

•

•

•
•
•

•
•

•
•

• •

•

•

(d) n = 7, #2-qubit gates = 11, depth = 6.
(e) n = 8, #2-qubit gates = 13, depth = 7.

Figure 10: Circuits that achieve the maximum fidelity for n. These circuits are applied by both Alice and Bob, after
which they measure the last n − 1 qubits, and communicate their outcomes to each other. When the outcomes for
all individual qubit pairs are correlated, the distillation protocol was deemed successful.

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

22

E Analytical expressions
We report here the analytical expressions of the fidelity and success probability that correspond to thefound optimal schemes. The input state is an n-fold tensor product of a Werner state with fidelity F .
For completeness, we report here as well the distillation statistics expressed in the infidelity  ≡ 1 − F ,and the scaling of the output fidelity as a function of the infidelity.

n

psuc

2

8 2
4
5
9F − 9F + 9

3

32 3
4 2
7
27 F − 9 F + 27

4

4 2
4
1
32 4
27 F − 9 F + 27 F + 9

5

80 3
10 2
5
2
80 4
27 F − 27 F + 9 F − 27 F + 27

6

128 6
320 5
256 4
16 3
40 2
14
1
243 F + 243 F − 243 F + 243 F + 243 F − 243 F + 27

72048 7
128 6
320 5
796 4
44
49 2
37
37
3
2187 F − 2187 F + 729 F − 2187 F − 2187 F + 729 F − 2187 F + 2187

86656 81024 71664 6641120 4
416 3
4
16
53
5
2
6561 F − 6561 F + 6561 F − 6561 F − 6561 F + 6561 F − 6561 F − 6561 F + 6561

Table 5: Success probability for the protocols with the highest output fidelity for n = 2 to 8.

npsuc · Fout

2

2
1
10 2
9 F − 9F + 9

3

1
2
28 3
27 F − 9 F + 27

4

8 3
2 2
1
8 4
9 F + 27 F − 9 F + 27

5

32 5
20 4
10 3
20 2
5
27 F − 27 F + 9 F − 27 F + 27 F

6

32 6
112 5
80 4
8
32 2
10
1
3
27 F − 243 F + 243 F + 243 F − 243 F + 243 F + 243

72368 7
592 6
196 5
44
199 3
20 2
2
8
4
2187 F − 2187 F + 729 F − 2187 F − 2187 F + 729 F − 2187 F + 2187

86784 8
51
32
832 5
560 4
8
52
8
13
7
6
3
2
6561 F − 6561 F − 6561 F + 6561 F − 6561 F − 6561 F + 6561 F − 6561 F + 6561

Table 6: Product of the success probability and the output fidelity for the protocols with the highest output fidelity
for n = 2 to 8.

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

23

n

psuc

2

1 − 43  + 98 2

3

1 − 2 + 43 2

4

8 3
1 − 2 + 43 2 − 27


5

28 2
256 3
400 4
256 5
1 − 143  + 3  − 27  + 81  − 243 

6

608 4
608 5
256 6
2
3
1 − 5 + 32
3  − 12 + 81  − 243  + 729 

7

944 3
928 4
544 5
1600 62048 72
1 − 7 + 190
9  − 27  + 27  − 27  + 243  − 2187 

8

244 2
1540 36280 4
16832 528768 69472 74096 81 − 233  + 9  − 27  + 81  − 243  + 729  − 729  + 2187 

Table 7: Success probability for the protocols with the highest output fidelity for n = 2 to 8, expressed in theinfidelity  ≡ 1 − F .

npsuc · Fout2

2
1 − 2 + 10
9 

3

4 3
2
1 − 3 + 10
3  − 3

4

44 3
8
2
1 − 3 + 10
3  − 27  + 27

5

284 3
440 4
272 5
2
1 − 5 + 92
9  − 27  + 81  − 243 

6

122 2
466 3
992 4
1112 5512 6
1 − 173  + 9  − 27  + 81  − 243  + 729 

7

320 3
2936 41816 55680 62560 72
1 − 7 + 190
9  − 9  + 81  − 81  + 729  − 2187 

8

544 3
2180 417000 527872 62912 73584 82
1 − 8 + 259
9  − 9  + 27  − 243  + 729  − 243  + 2187 

4

Table 8: Product of the success probability and the output fidelity for the protocols with the highest output fidelity
for n = 2 to 8, expressed in the infidelity  ≡ 1 − F .

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

24

n

Fout

2

1 − 32  − O 2

3

1 − 31  − O 2

4

1 − 23 2 − O 3

5

3
4
1 − 109  −O 6

1 − 89 3 − O 4

7

13 3
1 − 27
 − O 4

88 3
1 − 27
 − O 4








Table 9: Scaling of the output fidelity around  ≈ 0 for the protocols with the highest output fidelity for n = 2 to 8,
where  ≡ 1 − F .

Accepted in Quantum 2022-03-30, click title to verify. Published under CC-BY 4.0.

25