Distributed quantum information processing with minimal local resources
Distributed quantum information processing with minimal local resources
Earl T. Campbell∗
Department of Materials, Oxford University, Oxford, UK
(Dated: Feb, 2006)
We present a protocol for growing graph states, the resource for one-way quantum computing, when the
available entanglement mechanism is highly imperfect. The distillation protocol is frugal in its use of ancilla
qubits, requiring only a single ancilla qubit when the noise is dominated by one Pauli error, and two for a general
noise model. The protocol works with such scarce local resources by never post-selecting on the measurement
outcomes of purification rounds. We find that such a strategy causes fidelity to follow a biased random walk,
and that a target fidelity is likely to be reached more rapidly than for a comparable post-selecting protocol. An
analysis is presented of how imperfect local operations limit the attainable fidelity. For example, a single Pauli
error rate of 20% can be distilled down to ∼ 10 times the imperfection in local operations.
PACS numbers: 03.67.Mn, 03.67.Lx, 03.67.Pp
The paradigm of distributed quantum computing (QC) in-
volves a number of simple, optically active structures, each
capable of representing at least one qubit. Relevant exam-
ples include trapped atoms [1, 2, 3], and elementary nanos-
tructures such as NV centres within diamond [4, 5, 6]. En-
tanglement between structures is to be accomplished through
an optical channel, for example by measuring photons af-
ter a beam splitter has erased their ‘which path’ information
[1, 7, 8, 9, 10, 11, 12], as in figure (1a). Remarkably, recent
experimental results [3] demonstrated such an optical channel
between ions in separate traps. However, results to-date show
that the ‘raw’ entanglement generated in this way is liable to
have significant noise, well above fault tolerance thresholds
[13, 14]. Thus it is important to ask, can we exploit the mod-
est complexity within each local structure in order to distill
the entanglement to a higher fidelity?
Originally entanglement distillation was intended for se-
cure quantum communication [15, 16, 17, 18], but the same
protocols naturally carry over to distributed QC [19, 20]. First
a noisy entanglement operation produces many noisy Bell
pairs between two locations, which these protocols then con-
vert into fewer high-fidelity Bell pairs. At each local site there
must be a certain number of qubits available, one logical qubit
that is directly involved in the computation, and some num-
ber of ancilla qubits. Computation is performed by distilling a
high-fidelity Bell pair between two ancilla qubits, and then us-
ing it to implement a gate between two logical qubits. In addi-
tion to allowing purification, ancilla qubits protect the logical
qubits against damage from probabilistic gates [1, 4, 19, 20].
Since these protocols emphasize implementing a good fidelity
gate, we refer to them as gate-based protocols. For significant
purification of noise from a depolarizing source, these propos-
als require 3 or 4 ancillary qubits [19, 20]; whereas for phase
noise, the number of ancillas can be reduced by one [20].
Another family of distillation protocols emerged after the
one-way model of quantum computing showed that all the en-
tanglement necessary for computation is present in a class of
states called graph, or cluster, states [21, 22, 23, 24]. The dis-
∗Electronic address: earl.campbell@materials.ox.ac.uk
FIG. 1: An outline of a suitable architecture for a distributed quantum
computer. (a) The numbers label local sites, each housing a matter
system within a optical cavity. The optical cavities emit photons into
an input port of a multiplexer, which can route any input port to any
output port. Beam-splitters erase which-path information, so that
entanglement is generated conditional on the detector signatures. (a:
inset) for our primary protocol, each matter system is assumed to
have enough level structure to provide two good qubits, a ancilla
and a logical qubit. (b) two example level structures that would be
suitable for the ancilla qubit. The L-level has only one logical state
that optically couples to an excited state. The Λ-level structure has
both levels coupling to a common excited state, however the two
transitions are distinguishable by either frequency or polarization.
tillation of graph states is akin to error correction, as it con-
sists in repeated measurement of the stabilizers that describe
the graph state. In virtue of this feature, we refer to these as
stabilizer-based protocols. The first such protocol uses noisy
copies of a graph state and post-selects upon detection of a
single error [25, 26, 27]. Further proposals cast aside the need
for post-selection at the cost of a stricter error threshold [28],
above which, distillation is possible. These proposals use a
combination of noisy copies of the graph state and highly pu-
rified GHZ states. Because of the size of the entangled states
in the ancilla space, iterating these distillation protocols may
take longer than for gate-based protocols. A significant tem-
poral overhead will occur when the entangling operation has
a high failure rate. Building large entangled states in the an-
http://arxiv.org/abs/0704.1464v3
mailto:earl.campbell@materials.ox.ac.uk
cilla space also restricts the class of employable entangling
operations, excluding entangling protocols that only produce
Bell pairs [1, 9]. Of course, provided we have enough local
qubits to provide ancillas for our ancillas, these disadvantages
are easily nullified. However, many systems which are poten-
tially well suited for distributed QC may be very limited in the
number of qubits they can embody.
By blending ideas from the gate-based and stabilizer proto-
cols, this paper proposes an entanglement distillation protocol
which performs rapidly whilst requiring fewer ancillas than
previous protocols. The bulk of this paper shows that one an-
cilla is sufficient to distil errors from dephasing noise. We
then extend the protocol to cover depolarizing noise; as with
other schemes this requires an additional ancilla, which we
use to reduce the depolarizing noise to a dephasing noise. Like
gate-based protocols, we build up a graph state edge-by-edge,
with ancillas never building entangled states larger than Bell
pairs. However, as with stabilizer-based protocols, our pro-
posal repeatedly makes stabilizer measurements directly onto
the qubits constituting the graph state. Ancillas must typically
be optically active, such as in an L or Λ level configuration
(see Fig. 1b). Qubits are laBelled Ax and Lx for ancilla and
logical qubit, respectively, at local site x.
First our analysis will focus on the case when the noisy
entanglement channel is dominated by one type of Pauli error,
which may be very severe. Without loss of generality, we
describe the channel as being affected by phase noise, such
that two ancillas A1 and A2, can be put in the mixed state:
ρA1,A2 = (1− ε)|Ψ+〉〈Ψ+|+ εZA|Ψ+〉〈Ψ+|ZA, (1)
where ZA is the Pauli phase-flip operator acting on either A1
or A2, and |Ψ+〉 = |0〉A1|1〉A2 + |1〉A1|0〉A2. If the dominant
noise is a different Pauli error, or different Bell pairs are pro-
duced, then local rotations can always bring the state into the
form of equation 1. Furthermore, only a single Z error is pos-
sible as this Bell state is invariant under the bilateral ZA1ZA2
rotation. Scenarios where such a noise model may arise in-
clude parity based entangling operations [9, 10] that possess a
degree of robustness against bit-flip errors.
After producing noisy entanglement between two ancillas,
the entanglement is pumped down to the logical qubits, result-
ing in a quantum operation on the logical qubits. The target
(perfect) entangling operation we aim to eventually achieve is
either of the parity projections:
P− = 2(|01〉〈01|+ |10〉〈10|), (2)
P+ = 2(|00〉〈00|+ |11〉〈11|),
which act on the logical qubits L1 and L2, and have an ad-
ditional normalization factor of 2 that simplifies later expres-
sions. The only assumption we make about the initial state
of the logical qubits is that they are part of a graph state (in
the constructive definition), such that they have equal magni-
tude in both parity subspaces, 〈G |P+|G 〉 = 〈G |P−|G 〉; where
|G 〉 denotes the graph state of all the logical qubits. Both P−
and P+ allow arbitary graph growth, and which projection we
eventually obtain is unimportant as P±|G 〉 differ only by lo-
cal rotations [30]. We will see that entanglement distillation
results from repetition of an entanglement transfer procedure.
FIG. 2: The sequence of operations required to pump entanglement
down to two logical qubits L1 and L2, shown in the graph state no-
tation. (a) Ancillas are prepared in the (|0〉+ |1〉)/
2 state, and the
logical qubits are part of some larger graph state |G 〉; (b) An entan-
gling operation is performed between the ancillas, with the possibil-
ity of Z noise; (c) A H ·X is applied to ancilla A1; (d) At both local
sites control-Z operations are performed between ancilla and logical
qubit; (e) Ancilla A1 is measured in the Y basis; (f ) Ancilla A2 is
measured in the X-basis. The possibility of a Z error is tracked by
using ZE , where E = 1 tracks an error, and E = 0 tracks the er-
rorless state. The measurement outcome is represented by M , where
M = +1 for a |0〉 measurement and M = −1 otherwise. The dotted
line between the logical qubits represents a projection operator P±
between the logical qubits, where the sign is equal to M(−1)E .
Each round of our protocol is an entanglement pumping
procedure, described graphically in Fig. (2). Every round of
purification begins with performing a noisy entangling opera-
tion between two ancillas, A1 and A2. This operation may be
probabilistic provided that success is heralded, in which case
it is repeated until successful. Next, a series of local opera-
tions must be performed. First, apply a bit-flip then Hadamard
to one ancilla, say A1, and then two control–Z operations be-
tween each ancilla and its logical qubit. The resulting state is
a graph state, with the possibility of a Z error on A2. Then,
measure A1 in the Y -basis (correcting for any by-product),
giving the state described by Fig. 2e. Finally, A2 is measured
in the X-basis. When no error was present, this measurement
performs a parity check on the logical qubits, L1 and L2; that
is, we measure the observable ZL1ZL2. On the first round of
pumping, the odd and even parity outcomes will occur with
50/50 probability. Accounting for the possibility of a Z error
causes a noisy parity measurement, or quantum operation:
P∆ (|G 〉〈G |) =
α∆P+|G 〉〈G |P+ + α
−∆P−|G 〉〈G |P−
α∆ + α−∆
where α = (ε−1 − 1)
2 , and ∆ = M1 is +1 for a |0〉 mea-
surement outcome, and −1 for |1〉.
If we repeat the entanglement pumping procedure n
times, then we will get a series of measurements results
M1,M2,. . .Mn. Concatenating the mapping, for each mea-
surement result, we get back an operation of the same form
but with ∆ =
Mi. The core of our proposal is that
we continue to purify the qubits until |∆| reaches some value
FIG. 3: The evolution of ∆ against T , the number of rounds of entan-
glement pumping. The state evolves as a biased random walk in ∆.
The weighting of probabilities at a some point ∆ is such that there
is a probability P|∆| for increasing the magnitude of ∆, where P|∆|
is defined in equation 4. The red dashed lines represent the halting
lines for ∆, and in this example ∆H = 3. Note that, the paths to the
halting line, occur at T = ∆H + 2n, for non-negative integer n.
∆H at which point we halt the procedure. ∆H is chosen such
that it corresponds to a target fidelity FT , where the fidelity is
simply F (∆) = (1 + α−2|∆|)−1.
In contrast to previous gate-based protocols, our protocol is
not post-selective (NPS). Analogous post-selecting protocols
(PS) using an equivalent entangling pumping procedure to
eliminate phase errors have already been proposed [20]. The
essential difference for PS is that it resets upon any measure-
ment outcome, Mx, that differs from the first measurement
outcome, M1; a reset consists in measuring out the qubits be-
ing distilled, bringing them back to ∆ = 0. Benefits of NPS
are two-fold: (i) since purification is never restarted it is safe
to operate directly on the logical qubits, hence we eliminate
the need for an additional ancilla that exists in PS protocols;
(ii) the probability of success within T rounds is never less
than for PS, indeed, we shall show that NPS significantly out-
performs PS in this regard. A point in favour of PS is that, if
can freely use multiple ancillas, then PS may achieve a higher
asymptotic limit of fidelity (due to the effect of errors in local
operations). However, we shall see that NPS can still attain
fidelities within fault tolerance thresholds.
Returning to our consideration of the evolution of ∆ in our
protocol, it is clear that at each purification step, T , ∆ can
either increase or decrease by 1. Hence, the evolution bears
similarities to a random walk, illustrated by Fig.3. It differs
from a random walk in two regards: (i) it halts when it reaches
∆ = ±|∆H |; (ii) the probabilities are the biased when ∆ 6= 0.
The bias increases the chance of walking in the direction of
larger |∆|, which occurs with probability:
(1− ε)αD + εα−D
αD + α−D
, (4)
where D = |∆|. On the face of it, it seems that the probability
of walking to a state ∆ in T steps is dependent upon which
FIG. 4: A comparison of the rapidity of our proposal versus a post-
selection protocol, with a target fidelity FT = 1 − 10−4. The three
plots represent different values for the error rate ε, and hence require
a different value of ∆H ; shown in key. On each plot we show the
probability of success against the number of rounds T , for both the
protocol NPS (blue) and PS (orange). The yield for NPS and PS
(Ynps and Yps) is given on each plot. Notice that for NPS, the prob-
ability of success increases in steps. This is explained by figure 3,
which shows that successful paths are separated by 2 time steps.
path is taken. However, the probability of a kink in the path —
D increasing and subsequently decreasing — is independent
of D, and is k = PD(1 − PD+1) = ε(1 − ε). Hence, each
path occurs with probability:
Ppath(D,T ) =
). (5)
The total probability of walking to (D,T ) is the product of
Ppath(D,T ) with the number of paths to that position.
We have calculated the total probability of success, after T
rounds, by summing over all the different ways of reaching
the halting line. For comparison, we performed the analogous
calculation for an otherwise equivalent PS protocol. Figure
4 shows PS and NPS protocols for a target fidelity of FT =
1 − 10−4, with each plot being for a different error rate ε.
Note that, for higher error rate or higher target fidelity, the
width of the random walk is wider (larger∆H ). In this regime,
the superiority of NPS increases, as more entanglement can
be lost upon post-selection. Conversely, when ∆H = 2 the
protocols are effectively identical, as stepping back will take
the walk to the origin. A protocol’s yield is the expected ratio
of distilled Bell pairs to used noisy Bell pairs. Since each time
step uses a Bell pair, the yield of a protocol is 1/〈T 〉, with
some values given in Fig. 4. Since NPS is a faster protocol
than PS, it also has a superior yield.
For this idealized error model we can asymptotically ap-
proach unit fidelity. However, it is important to consider how
other errors limit the maximum attainable fidelity. For sim-
plicity, we take an aggressive error model where if a single
error occurs once, then the overall entangling gate has fidelity
zero. We use η to denote the probability per time step that an
error occurs, where these errors can result from either faulty
FIG. 5: A logarithmic plot of the expected infidelity, 1 − E(F ),
when additional error sources affect our distillation protocol. The
plot is a function of ε, the probability of a phase error occurring in
the long-range entangling operation. Each curve is a different value
of η, the probability per distillation round that some other error oc-
curs. The blue cross marks an example discussed in the text, where
the dephased Bell pairs are obtained by prior distillation on raw de-
polarized Bell pairs.
local operations or noise in the entanglement channel that is
orthogonal to the distilled dominant noise. Furthermore, we
approximate the chance of an error after T rounds by its up-
per bound, ηT . Once we reach ∆H the fidelity will depend
on the number of time steps taken. Therefore, we calculate
the expectation of the fidelity, E(F ). Figure 5 shows how the
expected infidelity, 1 − E(F ), varies with ε and η. Since the
optimal choice of ∆H changes with ε this produces inverted
humps along the curves, which are more pronounced for small
ε. On all curves the behaviour is roughly the same; we can
characterize the performance by noting that when the domi-
nant error rate is 0.2 (i.e. 20%), and the probability of other
error sources is η, then the protocol brings all error probabili-
ties to order 10η. Given that relevant fault tolerance strategies
can handle noise of order 1% [13, 14], the single-ancilla dis-
tillation may suffice when η is of order 0.1%.
If the orthogonal errors are too large, then an additional an-
cilla is required. Using the two ancillas, bit-errors are first
distilled away by a post-selective protocol, such as in [20].
Orthogonal errors are at their most extreme when the noise
is depolarizing, producing Werner states of fidelity F0. As
an example, we consider the distillation of Werner states of
F0 = 0.85; a rigorous analysis is provided in appendix A.
Five rounds of distillation reduces the orthogonal errors to
∼ 10−5, after which the phase noise has accumulated to
ε = 0.22; we have not gained fidelity, but we have mapped
all noise into phase noise. These dephased Bell pairs are
used in our primary distillation protocol, and are distilled to
E(F ) ∼ 10−4. This result is marked on Fig. 5 , where η is
taken to equal the remaining non-phase errors. As a final re-
mark, note that if we create GHZ states among ancillas (rather
than Bell-pairs) then our strategy can be combined with the
band-aid protocol of [28], increasing tolerance of imperfect
local operations.
In conclusion, using fewer ancillas than previous pro-
posals, an otherwise intolerably-large error is rapidly re-
duced below error-correction thresholds [13, 14]. For de-
phasing/depolarizing noise models, the protocol needs only
one/two ancillas, respectively. The author thanks Simon Ben-
jamin, Joseph Fitzsimons, Pieter Kok, and Dan Browne for
useful discussions. This research is part of the QIP IRC
(GR/S82176/01).
[1] L. M. Duan et al., Quantum Information and Computation 4,
165 (2004).
[2] D. K. L. Oi, S. J. Devitt, and L. C. L. Hollenberg, Physical
Review A 74, 052313 (2006).
[3] D. L. Moerhing et al., Nature 449, 68 (2007).
[4] S. C. Benjamin et al., New Journal of Physics 8, 141 (2006).
[5] J. Wrachtrup, S. Y. Kilin, and A. P. Nizovtsev, Optics and Spec-
troscopy 91, 429 (2001).
[6] T. Gaebel et al., Nature Physics 2, 408 (2006).
[7] C. Cabrillo et al., Phys. Rev. A 59, 1025 (1999).
[8] S. Bose et al., Phys. Rev. Lett 83, 5158 (1999).
[9] L. M. Duan and H. J. Kimble, Physical Review Letters 90,
253601 (2003).
[10] S. D. Barrett and P. Kok, Phys. Rev. A 71, 060310(R) (2005).
[11] S. C. Benjamin, Phys. Rev. A 72, 056302 (2005).
[12] Y. L. Lim, A. Beige, and L. C. Kwek, Phys. Rev. Lett 95,
030505 (2005).
[13] R. Raussendorf, J. Harrington, and K. Goyal, New. Jour. Phys,
9, 199, (2007).
[14] C. M. Dawson, H. L. Haselgrove, and M. A. Nielsen, Physical
Review Letters 96, 020501 (2006).
[15] C. H. Bennett et al., Phys. Rev. A 54 (1996).
[16] C. H. Bennett et al., Phys. Rev. Lett 76 (1996).
[17] W. Dür et al., Phys. Rev. A 59, 169 (1999).
[18] M. Murao et al., Phys. Rev. A 57, R4075 (1998).
[19] W. Dür and H. J. Briegel, Phys. Rev. Lett. 90, 067901 (2003).
[20] L. Jiang et al., (2007), quant-ph/0703029.
[21] R. Raussendorf, D. E. Browne, and H. J. Briegel, Phys. Rev. A
68, 022312 (2003).
[22] R. Raussendorf and H. J. Briegel, Phys. Rev. Lett. 86, 5188
(2001).
[23] M. Hein et al., (2005), quant-ph/0602096.
[24] M. Hein, J. Eisert, and H. J. Briegel, Phys. Rev. A 69, 062311
(2004).
[25] W. Dür, H. Aschauer, and H. J. Briegel, Phys. Rev. Lett. 91,
107903 (2003).
[26] H. Aschauer, W. Dür, and H. J. Briegel, Physical Review A 71,
012319 (2005).
[27] C. Kruszynska et al., Physical Review A 74, 052316 (2006).
[28] K. Goyal, A. McCauley, and R. Raussendorf, Physical Review
A 74, 032318 (2006).
[29] D. E. Browne and T. Rudolph, Phys. Rev. Lett 95, 010501
(2005).
[30] P+|G 〉 = XL1(
j∈N(L1) Zj)P−|G 〉, where N(L1) is the set
of neighbours of L1.
APPENDIX A: CONVERTING WERNER STATES INTO
DEPHASED BELL STATES.
In the main article we propose a protocol that uses a sin-
gle extra ancilla to distil a graph state in an edge-by-edge
fashion, provided an entanglement channel that generates de-
phased Bell states. However, if the entanglement channel suf-
fers depolarizing noise then this generates a rank-4 Bell diag-
onal mixed state, known as a Werner state. Here we show that
with an additional ancilla a well-known post-selective proto-
col can be used to convert these Werner states into dephased
Bell states. As an example, we calculate the accumulated
phase noise when the entanglement channel produces Werner
states with a fidelity of F0 = 0.85, and non-phase errors must
be reduced to order 10−5.
Given an entanglement channel that generates Werner states
of the form:
ρ = F0|Φ
+〉〈Φ+|+
1− F0
Z|Φ+〉〈Φ+|Z (A1)
+X |Φ+〉〈Φ+|X + Y |Φ+〉〈Φ+|Y
where |Φ+〉 = |00〉 + |11〉. The X and Y noise can be dis-
tilled by performing repeated noisy measurements of the ZZ
observable. This is implemented by first performing bilateral
control-phase rotations, with both controls from one EPR pair,
and both targets on another EPR pair. The control qubits are
measured in the X-basis, and we post-select on the even parity
measurement outcome. After n successful rounds the target
qubits are in some Bell diagonal state:
ρn = an|Φ
+〉〈Φ+|+ bnX |Φ
+〉〈Φ+|X (A2)
+cnZ|Φ
+〉〈Φ+|X + dnY |Φ
+〉〈Φ+|Y
After another successful round of distillation, the state is
transformed such that:
ρn+1 ∝ F0P+ρnP+ +
1− F0
P−ρnP− (A3)
+ZP+ρnP+Z + ZP−ρnP−Z
Where each term comes from considering a different Bell state
contribution to the mixed state of the control qubits. Contribu-
tions with Z or Y noise generate projections into the opposite
parity space, as these errors anti-commute with one of the X-
basis measurements. Contributions with X or Y noise will
result in a phase error on a target qubit. These errors propa-
gate down to the target qubits because X and Y rotations do
not commute with control phase gates, rather these rotations
change the gate’s control from the |1〉 state to |0〉. Before nor-
malization, the density matrix coefficients obey the recursive
relations:
an+1 = F0an +
1− F0
cn (A4)
cn+1 =
an + Fcn, (A5)
bn+1 = dn+1 =
1− F0
(bn + dn) (A6)
Fixing the n = 1 coefficients to those of our undistilled
Werner state, we can derive:
an + cn =
1 + 2F0
bn = dn =
(1− F0)
Hence, after n rounds of post-selective distillation, the re-
maining X and Y noise has a magnitude:
NXY (F0, n) =
bn + dn
an + bn + cn + dn
1 + 2F0
2− 2F0
)n)−1
To give a numerical example, consider a source of Werner
states of fidelity 0.85, and we wish to reduce NXY to order
10−5. It is easy to calculate that five rounds of distillation is
sufficient since NXY (0.85, 5) = 1.69 · 10
Finally, we need to calculate how the undistilled phase
noise has changed through these five rounds of distillation.
From the recursive relations, an unnormalized form of cn can
be derived:
1 + 2F
4F − 1
(A10)
After normalization, we have the remaining phase noise:
NZ(F0, n) =
an + bn + cn + dn
, (A11)
NZ(0.85, 5) = 0.22 (A12)
It is an interesting feature of distillation that although this state
has a lower fidelity than the Werner state, it is a more useful
resource for the subsequent level of distillation. Hence, fi-
delity alone is a poor indicator of the distillable entanglement
of a mixed state.
