text:
# Entanglement purification of unknown quantum states

## I Introduction

Entanglement is a quantum-mechanical resource that can be used for a number of tasks, including quantum teleportation, quantum cryptography, and quantum dense coding. Since real quantum channels are noisy, it is very difficult to create perfect entanglement directly between two distant parties. There is thus a need to purify (or distill) partial entanglement. Suppose two parties share $`N`$ pairs of qubits such that each pair is in the same entangled, but mixed state $`\rho `$, the total state $`\rho ^{(N)}`$ of all $`N`$ pairs thus being the $`N`$-fold tensor product $`\rho ^{(N)}=\rho ^N\rho \mathrm{}\rho `$. There exist protocols , using only local operations and classical communication, which allow the two parties to transform $`M<N`$ of the pairs into maximally entangled states, for instance singlet states. In the limit $`N\mathrm{}`$, the fidelity of the singlets approaches 1 and the fraction $`M/N`$ a fixed limit, called the asymptotic yield.

In this paper, we consider the more general case in which the initial state $`\rho ^{(N)}`$ is not a tensor-product state. This corresponds to the realistic situation that the state $`\rho `$ of each individual pair is not perfectly known, for instance because one of the particles has been sent through a channel with only partially known characteristics. In Secs. III and IV, we apply the entanglement purification methods known as one-way hashing  and recurrence  to partially known, including completely unknown, quantum states. It turns out that the generalization of the recurrence method is straightforward, whereas the hashing method as it is described in Ref.  depends on the initial state being of tensor-product form and therefore requires a more careful analysis. Unlike Briegel et al. , who have studied entanglement purification with imperfect quantum operations, we assume that all operations are error-free. A paper related to ours is Ref.  by Eisert et al., who study how distillable entanglement decreases when information about a quantum state is lost.

Before we turn to the actual entanglement purification protocols, we discuss, in Sec. II, the problem of what density operator $`\rho ^{(N)}`$ to assign to $`N`$ pairs of qubits if only partial information is available. This is an unsolved problem, and we do not attempt to give a general solution. We show, however, that under the additional assumption of exchangeability the state $`\rho ^{(N)}`$ must have a certain simple form, which is amenable to entanglement purification. Our discussion also provides a resolution of the apparent paradox found by Horodecki et al. , who give an example where applying the Jaynes principle of maximum entropy  leads to a state with more distillable entanglement than seems to be warranted by the available information. We conclude in Sec. V.

## II State assignment based on partial information

Let us consider the example given by Horodecki et al. . The authors consider a system composed of a single pair of qubits and define an operator

$$B=\frac{1}{2}(\sigma _x\sigma _x+\sigma _z\sigma _z)=(𝚽_+𝚿_{}),$$
(1)
where $`𝚿_\pm =|\mathrm{\Psi }_\pm \mathrm{\Psi }_\pm |`$, $`𝚽_\pm =|\mathrm{\Phi }_\pm \mathrm{\Phi }_\pm |`$ are projectors onto the Bell states,

$`|\mathrm{\Phi }_\pm `$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}(|00\pm |11),`$ (2)
$`|\mathrm{\Psi }_\pm `$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}(|01\pm |10).`$ (3)
Our definition of $`B`$ differs from that of Ref.  by a constant factor to simplify the expressions. If all that is known about the system state is the expectation value $`B=1/2`$, then Jaynes’s principle of maximum entropy stipulates that one should assign the state of maximum von Neumann entropy compatible with the constraint $`B=1/2`$, which in this case is

$$\rho _J=\frac{9}{16}𝚽_++\frac{1}{16}𝚿_{}+\frac{3}{16}(𝚿_++𝚽_{}).$$
(4)
This state has distillable entanglement. Horodecki et al.  point out that the state

$$\rho _H=\frac{1}{2}𝚽_++\frac{1}{4}(𝚿_++𝚽_{}).$$
(5)
also satisfies the constraint $`B=1/2`$, but is separable and hence unentangled. They conclude that the entanglement in the maximum entropy state $`\rho _J`$ is “fake,” because it violates the condition that an inference scheme “should not give us an inseparable estimated state if only theoretically there exists a separable state consistent with the measured data.” As an alternative to the Jaynes principle, they propose first to minimize the entanglement and then to find the state of maximum entropy among those states that have minimal entanglement. For the constraint $`B=1/2`$, this alternative scheme results in the state $`\rho _H`$ given above.

A simple defense of the Jaynes principle would be the following (see also Refs. ). The alternative procedure proposed by Horodecki et al. assumes additional information about the two qubits, namely that entanglement is a priori unlikely. This would be reasonable, e.g., in a situation where the parties know that the state has been prepared by an adversary whose objective is to let them have as little entanglement as possible. But then more is known about the state than just the given expectation value, and hence the assumptions behind the Jaynes procedure are not fulfilled.

If there is no specific additional information, however, the maximum entropy state assignment $`\rho _J`$ is preferable to the minimum entanglement assignment $`\rho _H`$. Indeed, if a projective measurement in the Bell basis is performed, assigning $`\rho _H`$ corresponds to assigning zero probability to the measurement outcome $`𝚿_{}`$, an outcome that is not ruled out by the constraint $`B=1/2`$. In this sense, the minimum entanglement assignment is inconsistent with the prior information. By contrast, no inconsistency of this kind can arise from the maximum entropy assignment in the absence of prior information beyond the given expectation value. Since no measurement of a single system can tell if that system is entangled or not, the prediction of “fake entanglement” for $`\rho _J`$ can cause no difficulty. In particular, there is no way to turn a single $`\rho _J`$ state into a maximally entangled state even probabilistically .

We now turn to the case in which the parties share not just one, but $`N`$ qubit pairs. We denote by $`\rho ^{(N)}`$ the total state of the $`N`$ pairs and assume that the $`N`$ pairs are known to satisfy the constraints $`B_k\mathrm{Tr}(\rho _kB)=1/2`$ for $`k=1,\mathrm{},N`$, where $`\rho _k`$ is the reduced density operator of the $`k`$-th pair. In this case, the state assignment $`\rho ^{(N)}=\rho _J^N`$ is not supported by the prior information, even though this is the state of maximum entropy compatible with the given expectation values. For large $`N`$, this state assignment corresponds to the definite prediction that a nonzero number of perfect singlets can be distilled, which is certainly not implied by the given expectation values. The alternative state assignment $`\rho ^{(N)}=\rho _H^N`$ would, however, be equally unsupported by the prior information. It corresponds to the definite prediction that no singlets can be distilled from the $`N`$ pairs, which is the minimum number of distillable singlets compatible with the a priori knowledge. Although this is a very cautious prediction, it is also not implied by the given expectation values.

The fact that a naïve application of the principle of maximum entropy to many copies of a system fails is essentially of classical origin and is not unique to problems involving entanglement. Jaynes  has given a thorough discussion of this problem, which can be explained by a simple example. Consider a possibly loaded die. All that is known about the die is the mean value $`n_nnp(n)=3.5`$, where $`p(n)`$ is the probability of the outcome $`n`$, $`n=1,\mathrm{},6`$. The probability distribution of maximum entropy compatible with the given mean-value constraint is $`p(n)=1/6`$ for $`n=1,\mathrm{},6`$. Now consider throwing the die $`N`$ times. A naïve application of the maximum entropy principle would predict that the $`N`$ dice throws were independent and identically distributed (i.i.d.) according to the single-trial distribution $`p(n)`$. This would lead to the prediction that the fraction of throws showing any particular outcome would approximate 1/6 with arbitrary precision as $`N`$ tended to infinity. This prediction, however, is not implied by the prior knowledge, which is compatible with many possible outcome sequences, including sequences in which only the events $`n=1`$ and $`n=6`$ ever occur—quite possible, if the die is loaded. Moreover, with an i.i.d. distribution, the results of earlier throws imply nothing about the probability of later outcomes. Even the most gullible gambler might become suspicious if 1 and 6 were the only outcomes after thousands of throws.

In Ref. , Jaynes discusses how to choose the multi-trial distribution in the classical case. The starting point of his discussion is the assumption that the probability distribution of the $`N`$ dice throws is exchangeable. The same assumption is the starting point for our quantum analysis. If exchangeability is assumed, the task of assigning a state of $`N`$ qubit pairs compatible with the constraints given above is much simplified. A state $`\rho ^{(N)}`$ of $`N`$ copies of a system is exchangeable if it is a member of an exchangeable sequence $`\rho ^{(k)}`$, $`k=1,2,\mathrm{}`$ . An exchangeable sequence is defined by

* $`\rho ^{(k)}=\mathrm{Tr}_{k+1}\rho ^{(k+1)}`$ for all $`k`$, where $`\mathrm{Tr}_{k+1}`$ denotes the partial trace over the $`(k+1)`$th system, and

* each $`\rho ^{(k)}`$ is invariant under permutations of the $`k`$ systems on which it is defined.

This definition is the quantum generalization of de Finetti’s  definition of exchangeable sequences of classical random variables.

A state $`\rho ^{(N)}`$ is exchangeable if and only if it can be written in the form

$$\rho ^{(N)}=𝑑\rho p(\rho )\rho ^N,$$
(6)
where $`d\rho `$ is a measure on density operator space, and $`p(\rho )`$ is a normalized generating function, $`𝑑\rho p(\rho )=1`$. This is a consequence of the quantum de Finetti theorem, the quantum version of the fundamental representation theorem due to de Finetti . The quantum theorem was first proved by Hudson and Moody  after pioneering work by Størmer ; for an elementary proof see Ref. .

How, in general, do we pick $`p(\rho )d\rho `$? To our knowledge, there is no universal rule for this task, although there exist a number of proposals for unbiased measures $`d\rho `$ on density operator space . These can be interpreted as proposals for state assignments for $`N`$ systems under the sole assumption of exchangeability, i.e., using a generating function $`p(\rho )=1`$.

If, in addition to exchangeability, there is a mean-value constraint $`O=o`$, the naïve Jaynes maximum entropy state assignment leads to a generating function of the form $`p(\rho )=\delta (\rho \rho _J)`$, where $`\rho _J`$ is the single-system state of maximum entropy, subject to the constraint; this generating function is unacceptable for the reasons given above. A good choice of $`p(\rho )d\rho `$ should be nonzero for all $`\rho `$ that are compatible with the prior information—we should never arbitrarily rule out any possibility. Similarly, $`p(\rho )d\rho `$ ought to vanish for any $`\rho `$ which is actually ruled out by the prior information. We therefore would expect a multi-system generalization of Jaynes’s maximum entropy procedure to have the form

$$p_{\mathrm{MAXENT}}(\rho )d\rho =𝒩\delta [o\mathrm{Tr}(O\rho )]f(\rho )d\rho ,$$
(7)
where $`𝒩`$ is a normalization constant and $`f(\rho )d\rho `$ is strictly positive. The exact form of the function $`f(\rho )`$ and of the measure $`d\rho `$ is the subject of ongoing research. In the spirit of the single-system Jaynes principle, $`p(\rho )d\rho `$ should favor states $`\rho `$ with higher von Neumann entropy $`S(\rho )`$ and should give the usual $`\rho _J`$ when $`N=1`$ .

Given an initial state assignment of the form (6), additional information can be obtained, e.g., by making measurements on individual subsystems. Suppose a measurement outcome $`k`$ is represented by a positive single-system operator $`F_k`$, with $`_kF_k=1`$; i.e., the $`F_k`$ form a positive-operator valued measure (POVM) . Given that the subsystem is in state $`\rho `$, the probability of getting outcome $`k`$ is $`p(k|\rho )=\mathrm{Tr}[F_k\rho ]`$. If the total state is given by Eq. (6), the probability of outcome $`k`$ in a measurement on a single subsystem is then

$$p_k=𝑑\rho p(\rho )p(k|\rho ).$$
(8)
After the measurement we must update the state of the remaining $`N1`$ systems by Bayes’s rule,

$$\rho ^{(N1)}=𝑑\rho p(\rho |k)\rho ^{(N1)},$$
(9)
where

$$p(\rho |k)=\frac{p(\rho )p(k|\rho )}{p_k}.$$
(10)
By doing different measurements on several subsystems, we acquire more and more data; if these measurements are chosen well, the resulting posterior $`p_{\mathrm{post}}(\rho )`$ becomes more and more peaked and has less and less dependence on the choice of prior $`p(\rho )`$. This procedure is a straightforward Bayesian version of quantum state tomography .

The condition of exchangeability in combination with the quantum de Finetti theorem provides only a partial solution of the problem of state assignment in the presence of partial information, but we show in the next two sections that exchangeability alone is sufficient to guarantee that the entanglement purification procedures known as one-way hashing and recurrence can be carried out. The probability of distilling a positive yield of maximally entangled states depends on the exact form of $`p(\rho )d\rho `$ in Eq. (6).

## III Entanglement purification by one-way hashing

In this section, we first present a version of the one-way hashing algorithm that proceeds by Bayesian updating of the probabilities for products of Bell states and that can in principle be applied to general exchangeable states. We then briefly sketch the argument given in Ref.  that for a product state $`\rho ^N`$, where $`\rho `$ is Bell-diagonal with von Neumann entropy $`S`$, the asymptotic yield of pure singlets is given by $`N(1S)`$. We show how to modify this argument so that it can be applied to general exchangeable states. Finally we give a simplified Bayesian hashing algorithm for exchangeable states and discuss its asymptotic yield. Our analysis is restricted to pairs of qubits, but the method generalizes straightforwardly to arbitrary Hilbert space dimensions.

We restrict attention to Bell-diagonal states, i.e., mixtures of the Bell states,

$$\rho _\stackrel{}{w}=w_1𝚿_{}+w_2𝚿_++w_3𝚽_{}+w_4𝚽_+,$$
(11)
where we denote the weights by $`\stackrel{}{w}=\{w_1,w_2,w_3,w_4\}`$, $`w_1+w_2+w_3+w_4=1`$, $`w_j0`$ for $`j=1,\mathrm{},4`$. Most existing entanglement purification procedures begin by making this assumption. If it does not hold, it is possible to put any state in this form by “twirling,” that is, by randomly rotating both spins of an entangled pair. The final yield of maximally entangled states cannot be diminished by omitting this step, however, so it is better to think of twirling as a conceptual, rather than a physical procedure. After twirling, the initial, exchangeable state (6) of our $`N`$ pairs of qubits becomes

$$\rho ^{(N)}=𝑑\stackrel{}{w}p(\stackrel{}{w})\rho _\stackrel{}{w}^N,$$
(12)
where

$$𝑑\stackrel{}{w}p(\stackrel{}{w})=1.$$
(13)
We now define the set of labeled states

$`\rho _{00}=𝚿_{},`$ $`\rho _{01}=𝚿_+,`$ (14)
$`\rho _{10}=𝚽_{},`$ $`\rho _{11}=𝚽_+.`$ (15)
The first bit in the label tells us whether the pair is in a $`\mathrm{\Psi }`$ or a $`\mathrm{\Phi }`$ state; the second bit tells us whether it is in a $`+`$ or $``$ state. If we are restricted to local measurements and classical communication on a single pair, the best we can do is to determine one of these two bits, but not both, and the pair will be left in an unentangled state. Bennett et al. have shown, however, that if we can manipulate the qubits collectively, much more interesting measurements are possible .

The first step is to rewrite the state (12) as a probability distribution over strings of bits, with each qubit pair associated with two bits in the string. For this, we define the product distribution

$$p(i_1i_2\mathrm{}i_{2N}|\stackrel{}{w})=w_{i_1i_2}w_{i_3i_4}\mathrm{}w_{i_{2N1}i_{2N}},$$
(16)
where $`w_{00}w_1`$, $`w_{01}w_2`$, $`w_{10}w_3`$, and $`w_{11}w_4`$. Using this notation,

$$\rho ^{(N)}=\underset{i_1,i_2,\mathrm{},i_{2N}}{}p(i_1i_2\mathrm{}i_{2N})\rho _{i_1i_2}\mathrm{}\rho _{i_{2N1}i_{2N}},$$
(17)
where

$$p(i_1i_2\mathrm{}i_{2N})=𝑑\stackrel{}{w}p(\stackrel{}{w})p(i_1i_2\mathrm{}i_{2N}|\stackrel{}{w}).$$
(18)
We now select a random subset of the bits $`i_1\mathrm{}i_{2N}`$ and list all the qubit pairs which have at least one associated bit in the subset. From this list we choose one qubit pair to be the target. For each of the other qubit pairs in the list, Alice and Bob both perform one of a set of three unitary transformations on their half of the pair, followed by a bilateral controlled-NOT onto the target pair. This sequence of operations is equivalent to replacing one of the bits of the target pair with the parity of a subset of all the bits. The choice of unitary transformation corresponds to including the first, second, or both of the bits from a particular pair in the parity calculation. Then a measurement is performed on the target pair. (The details of this procedure are given in .) By carrying out such a procedure, one bit of joint information is acquired about all the pairs, at the expense of sacrificing one entangled pair (that is, two bits). The unmeasured pairs in general undergo an invertible transformation among the Bell states, but they do not become entangled with each other, and this transformation can, if one chooses, be undone, leaving the sequence of bits for the unmeasured pairs unaltered. Bennett et al. have shown that such a procedure can be equivalent to finding the parity of any subset of the $`2N`$ bits. This parity bit then allows one to update the probability distribution for the remaining $`2(N1)`$-bit string.

Let us examine this in a little more detail. Let $`\stackrel{}{ı}i_1i_2\mathrm{}i_{2N}`$ denote a sequence of bits. We can select a subset of these bits by giving another sequence $`\stackrel{}{x}`$, which includes a 1 for each bit to be included in the subset and a 0 for the rest. The parity of the subset is then

$$\pi _\stackrel{}{x}(\stackrel{}{ı})\stackrel{}{x}\stackrel{}{ı}\left(\underset{m=1}{\overset{2N}{}}x_mi_m\right)mod2.$$
(19)
For a given $`\stackrel{}{ı}`$ the probability of getting a value $`\pi _\stackrel{}{x}`$ for the parity is either 0 or 1, so the probability of getting $`\pi _\stackrel{}{x}`$ as a measurement result is

$$p(\pi _\stackrel{}{x})=\underset{\stackrel{}{ı}}{}p(\pi _\stackrel{}{x}|\stackrel{}{ı})p(\stackrel{}{ı})=\underset{\stackrel{}{ı}}{}\delta _{\pi _\stackrel{}{x},\stackrel{}{x}\stackrel{}{ı}}p(\stackrel{}{ı}).$$
(20)
For simplicity let us assume that the target pair is the last, so the last two bits are sacrificed; the new state for the $`N1`$ remaining pairs is

$$\rho ^{(N1)}=\underset{\stackrel{}{ı}^{}}{}p(\stackrel{}{ı}^{}|\pi _\stackrel{}{x})\rho _{i_1i_2}\rho _{i_3i_4}\mathrm{}\rho _{i_{2N3}i_{2N2}},$$
(21)
where $`\stackrel{}{ı}^{}i_1i_2\mathrm{}i_{2N2}`$ and

$$p(\stackrel{}{ı}^{}|\pi _\stackrel{}{x})=\underset{i_{2N1},i_{2N}}{}p(\stackrel{}{ı}|\pi _\stackrel{}{x})=\underset{i_{2N1},i_{2N}}{}\frac{p(\stackrel{}{ı})p(\pi _\stackrel{}{x}|\stackrel{}{ı})}{p(\pi _\stackrel{}{x})}.$$
(22)
Note that while the initial probability distribution $`p(\stackrel{}{ı})`$ is symmetric under interchanges of the pairs, this symmetry is lost after measurement.

The purification scheme follows simply from this. One chooses subsets of the bit string at random and measures their parity, sacrificing one pair with each measurement, but updating the probability distribution for the remaining strings. This procedure is repeated until one is left with only a single string, say $`\stackrel{}{ı}_0`$, with probability $`1\delta `$ for some small $`\delta `$. Written more formally, the posterior probability $`p_{\mathrm{post}}`$ at the end of the procedure, conditioned on all measurement results, has the property $`p_{\mathrm{post}}(\stackrel{}{ı}_0)=1\delta `$ for some sequence $`\stackrel{}{ı}_0`$. One then knows with high probability the maximally entangled state of each remaining pair, which can then be transformed into a standard state (such as $`𝚿_{}`$) by local operations. The yield of this procedure is the number of entangled pairs left at the end.

It is clear that there are states for which the yield is zero. The obvious example is a state $`\rho ^N`$ where $`\rho `$ is unentangled. For states of the form $`\rho _\stackrel{}{w}^N`$, Bennett et al. have shown that asymptotically the method gives a yield of $`N(1S_\stackrel{}{w})`$ maximally entangled pairs with fidelity approaching 1, where

$$S_\stackrel{}{w}=\underset{j=1}{\overset{4}{}}w_j\mathrm{log}w_j=\mathrm{Tr}(\rho _\stackrel{}{w}\mathrm{log}\rho _\stackrel{}{w})$$
(23)
is the entropy of $`\rho _\stackrel{}{w}`$. The argument makes use of the theorem of typical sequences  (which is closely related to Shannon’s noiseless coding theorem ), according to which, for any $`ϵ>0`$ and $`\delta >0`$ and sufficiently large $`N`$, there exists a subset $`\mathrm{TYP}(N)`$ of the set of all sequences $`\stackrel{}{ı}`$ with the following properties:

$$p(\mathrm{TYP}(N))\underset{\stackrel{}{ı}\mathrm{TYP}(N)}{}p(\stackrel{}{ı}|\stackrel{}{w})1ϵ,$$
(24)
i.e., the total probability of the set $`\mathrm{TYP}(N)`$ is arbitrarily close to 1; and

$$|\mathrm{TYP}(N)|2^{N(S_\stackrel{}{w}+\delta )},$$
(25)
i.e., the number of sequences in $`\mathrm{TYP}(N)`$ is not much larger than $`2^{NS_\stackrel{}{w}}`$. The set $`\mathrm{TYP}(N)`$ is called the set of typical sequences. Since the parity measurement in each hashing round rules out half the typical sequences on average and since essentially all the probability is concentrated on the typical sequences, it can be expected that after sacrificing approximately $`NS_\stackrel{}{w}`$ pairs, essentially all the probability is concentrated on a single typical sequence. Clearly this leads to a positive yield only if $`S_\stackrel{}{w}<1`$.

The theorem of typical sequences does not hold in general for sequences corresponding to exchangeable states of the form (12). To apply the hashing method in this case, we rely on a generalization of the theorem of typical sequences due to Cziszár and Körner  (this theorem has recently been used by Jozsa et al.  to derive a universal quantum information compressing scheme). Applied to our setting, the theorem is that, given a fixed entropy $`S_0`$, then for any $`ϵ>0`$ and $`\delta >0`$ and sufficiently large $`N`$, there exists a subset $`\mathrm{CK}(N)`$ of the set of all sequences $`\stackrel{}{ı}`$ with the following properties:

$$\underset{\stackrel{}{ı}\mathrm{CK}(N)}{}p(\stackrel{}{ı}|\stackrel{}{w})1ϵ$$
(26)
for all $`\stackrel{}{w}`$ such that $`S_\stackrel{}{w}<S_0`$, which means that the set $`\mathrm{CK}(N)`$ is typical for all probability distributions with entropy less than $`S_0`$; and

$$|\mathrm{CK}(N)|2^{N(S_0+\delta )},$$
(27)
i.e., the number of sequences in $`\mathrm{CK}(N)`$ is not much larger than $`2^{NS_0}`$. In the following, when we write “typical sequences,” we mean sequences in $`\mathrm{CK}(N)`$, whereas by “atypical sequences” we mean sequences in $`\overline{\mathrm{CK}}(N)`$, the complement of $`\mathrm{CK}(N)`$.

Now assume that we want to perform the hashing protocol on a state of $`N`$ pairs of the form (12) with the property

$$_{S_\stackrel{}{w}>S_0}𝑑\stackrel{}{w}p(\stackrel{}{w})=\eta 1$$
(28)
for some entropy $`S_0<1`$; i.e., there is only a small a priori probability that the entropy of the unknown state exceeds the given value $`S_0`$. (The case of states that do not have this property will be discussed at the end of this section.) Furthermore, assume that $`N`$ is large enough that there exists a Cziszár-Körner set $`\mathrm{CK}(N)`$ with constants $`ϵ,\delta 1`$ in Eqs. (26) and (27). It then follows that

$`p(\mathrm{CK}(N))`$ $``$ $`{\displaystyle \underset{\stackrel{}{ı}\mathrm{CK}(N)}{}}p(\stackrel{}{ı})`$ (29)
$`=`$ $`{\displaystyle \underset{\stackrel{}{ı}\mathrm{CK}(N)}{}}{\displaystyle 𝑑\stackrel{}{w}p(\stackrel{}{w})p(\stackrel{}{ı}|\stackrel{}{w})}`$ (30)
$``$ $`{\displaystyle \underset{\stackrel{}{ı}\mathrm{CK}(N)}{}}{\displaystyle _{S_\stackrel{}{w}<S_0}}𝑑\stackrel{}{w}p(\stackrel{}{w})p(\stackrel{}{ı}|\stackrel{}{w})`$ (31)
$`=`$ $`{\displaystyle _{S_\stackrel{}{w}<S_0}}𝑑\stackrel{}{w}p(\stackrel{}{w}){\displaystyle \underset{\stackrel{}{ı}\mathrm{CK}(N)}{}}p(\stackrel{}{ı}|\stackrel{}{w})`$ (32)
$``$ $`{\displaystyle _{S_\stackrel{}{w}<S_0}}𝑑\stackrel{}{w}p(\stackrel{}{w})(1ϵ)`$ (33)
$`=`$ $`(1\eta )(1ϵ)`$ (34)
$``$ $`1\eta ϵ,`$ (35)
where Eqs. (13), (26), and (28) have been used.

We use this inequality, in combination with Eq. (27), to derive the asymptotic yield of the hashing algorithm applied to exchangeable states. We restrict our analysis to a simplified protocol, in which we choose a number $`r`$, somewhat larger than $`N(S_0+\delta )`$, such that

$$\zeta 2^{N(S_0+\delta )r}1.$$
(36)
We begin with input strings $`\stackrel{}{ı}`$ that have probability $`p(\stackrel{}{ı})`$. Let $`h`$ denote a sequence of $`r`$ parity checks on random subsets, and let $`\stackrel{}{o}=o_1,\mathrm{},o_r`$ denote the $`r`$-bit string of parity checks, or outcomes. Note that we denote all strings of bits as vectors, even though they are not all of the same length. The probability distribution $`p(h)`$ on parity-check sequences is weighted uniformly on all sequences. For a given input string $`\stackrel{}{ı}`$ and a given parity-check sequence $`h`$, the outcome $`\stackrel{}{o}`$ is determined; we denote this deterministic outcome by $`\stackrel{}{o}_{h,\stackrel{}{ı}}`$. We can express this deterministic outcome in terms of a probability for outcome string $`\stackrel{}{o}`$, given parity-check sequence $`h`$ and input string $`\stackrel{}{ı}`$:

$$p(\stackrel{}{o}|h,\stackrel{}{ı})=\delta _{\stackrel{}{o},\stackrel{}{o}_{h,\stackrel{}{ı}}}.$$
(37)
Since for each parity-check bit obtained, two bits of the input string are discarded, two strings with the same parity check, which differ only on those two bits, become the same after that step. After $`r`$ steps of a parity-check sequence $`h`$, there will be only $`Nr`$ entangled pairs, corresponding to a string of $`2(Nr)`$ bits. If one starts with a string $`\stackrel{}{ı}`$, one will be left with a shorter substring $`\stackrel{}{ı}_h(\stackrel{}{ı})`$. Different initial strings $`\stackrel{}{ı}`$ that generate the same outcome $`\stackrel{}{o}`$ and lead to the same final substring $`\stackrel{}{ı}_h(\stackrel{}{ı})`$ are equivalent for practical purposes. Let us denote the set of all input strings $`\stackrel{}{ı}`$ which lead to outcome $`\stackrel{}{o}`$ and to output substring $`\stackrel{}{ı}_h`$ by $`I_h(\stackrel{}{o},\stackrel{}{ı}_h)\{\stackrel{}{ı}|\stackrel{}{o}_{h,\stackrel{}{ı}}=\stackrel{}{o},\stackrel{}{ı}_h(\stackrel{}{ı})=\stackrel{}{ı}_h\}`$.

For parity-check sequence $`h`$, we are interested in outcomes $`\stackrel{}{o}`$ such that all typical input strings $`\stackrel{}{ı}`$ that lead to $`\stackrel{}{o}`$ produce the same output string $`\stackrel{}{ı}_h(\stackrel{}{ı})`$. For outcomes where this is the case, the procedure picks out a unique output string from among all those that could be produced by a typical input string. In this case, we say that we accept the outcome $`\stackrel{}{o}`$ and the corresponding unique output string, which we denote by $`\stackrel{}{ı}_{h,\stackrel{}{o}}`$. In this way we divide the outcomes for a parity-check sequence $`h`$ into two sets, the set of accepted outcomes, $`A_h`$, and its complement. For an outcome that we accept and for a typical input string, we can write the conditional probability (37) as

$`p(\stackrel{}{o}|h,\stackrel{}{ı},\stackrel{}{ı}\mathrm{CK}(N))`$ $`=`$ $`\{\begin{array}{cc}1,\hfill & \text{if }\stackrel{}{ı}I_h(\stackrel{}{o},\stackrel{}{ı}_{h,\stackrel{}{o}})\hfill \\ 0,\hfill & \text{if }\stackrel{}{ı}I_h(\stackrel{}{o},\stackrel{}{ı}_{h,\stackrel{}{o}})\hfill \end{array}`$ (38)
$`=`$ $`\delta _{\stackrel{}{o},\stackrel{}{o}_{h,\stackrel{}{ı}}}\delta _{\stackrel{}{ı}_h(\stackrel{}{ı}),\stackrel{}{ı}_{h,\stackrel{}{o}}}\text{for }\stackrel{}{o}A_h\text{.}`$ (39)
Though the additional Kronecker delta in this expression is redundant, it reminds one that any typical input string $`\stackrel{}{ı}`$ that leads to an accepted outcome $`\stackrel{}{o}`$ produces output string $`\stackrel{}{ı}_{h,\stackrel{}{o}}`$. Notice that this is not true for atypical input strings: an atypical input string can have outcome $`\stackrel{}{o}`$ and produce outcome string $`\stackrel{}{ı}_{h,\stackrel{}{o}}`$ or a different output string.

The probability that the outcome is accepted, given input string $`\stackrel{}{ı}`$ and parity-check sequence $`h`$, is

$`p(\mathrm{accept}|h,\stackrel{}{ı})`$ $`=`$ $`{\displaystyle \underset{\stackrel{}{o}A_h}{}}p(\stackrel{}{o}|h,\stackrel{}{ı})`$ (40)
$`=`$ $`{\displaystyle \underset{\stackrel{}{o}A_h}{}}\delta _{\stackrel{}{o},\stackrel{}{o}_{h,\stackrel{}{ı}}}`$ (41)
$`=`$ $`\{\begin{array}{cc}1,\hfill & \text{if }\stackrel{}{ı}\text{ leads to an accepted outcome,}\hfill \\ 0,\hfill & \text{if }\stackrel{}{ı}\text{ does not lead to an accepted outcome.}\hfill \end{array}`$ (42)
Notice that this conditional acceptance probability can be nonzero for atypical input strings. The complementary probability, that the outcome is not accepted, given $`\stackrel{}{ı}`$ and $`h`$, is given by

$`p(\overline{\mathrm{accept}}|h,\stackrel{}{ı})`$ $`=`$ $`{\displaystyle \underset{\stackrel{}{o}A_h}{}}p(\stackrel{}{o}|h,\stackrel{}{ı})`$ (43)
$`=`$ $`{\displaystyle \underset{\stackrel{}{o}A_h}{}}\delta _{\stackrel{}{o},\stackrel{}{o}_{h,\stackrel{}{ı}}}`$ (44)
$`=`$ $`\{\begin{array}{cc}0,\hfill & \text{if }\stackrel{}{ı}\text{ leads to an accepted outcome,}\hfill \\ 1,\hfill & \text{if }\stackrel{}{ı}\text{ does not lead to an accepted outcome.}\hfill \end{array}`$ (45)
If the input string is a typical string, the conditional acceptance probability can also be written as

$$p(\mathrm{accept}|h,\stackrel{}{ı},\stackrel{}{ı}\mathrm{CK}(N))=\underset{\stackrel{}{o}A_h}{}\delta _{\stackrel{}{o},\stackrel{}{o}_{h,\stackrel{}{ı}}}\delta _{\stackrel{}{ı}_h(\stackrel{}{ı}),\stackrel{}{ı}_{h,\stackrel{}{o}}}$$
(46)
\[see Eq. (39)\].

What we are interested in for the present is the probability to have an outcome that is accepted, given a typical input string, but averaged over all parity-check sequences:

$`p(\mathrm{accept}|\stackrel{}{ı},\stackrel{}{ı}\mathrm{CK}(N))`$ $`=`$ $`{\displaystyle \underset{h}{}}p(\mathrm{accept}|h,\stackrel{}{ı},\stackrel{}{ı}\mathrm{CK}(N))p(h)`$ (47)
$`=`$ $`{\displaystyle \underset{h}{}}p(h){\displaystyle \underset{\stackrel{}{o}A_h}{}}\delta _{\stackrel{}{o},\stackrel{}{o}_{h,\stackrel{}{ı}}}\delta _{\stackrel{}{ı}_h(\stackrel{}{ı}),\stackrel{}{ı}_{h,\stackrel{}{o}}}.`$ (48)
The complementary probability,

$`p(\overline{\mathrm{accept}}|\stackrel{}{ı},\stackrel{}{ı}\mathrm{CK}(N))`$ $`=`$ $`{\displaystyle \underset{h}{}}p(\overline{\mathrm{accept}}|h,\stackrel{}{ı},\stackrel{}{ı}\mathrm{CK}(N))p(h)`$ (49)
$`=`$ $`{\displaystyle \underset{h}{}}p(h){\displaystyle \underset{\stackrel{}{o}A_h}{}}\delta _{\stackrel{}{o},\stackrel{}{o}_{h,\stackrel{}{ı}}},`$ (50)
is the average probability not to have an outcome that is accepted, given the typical input string $`\stackrel{}{ı}`$. This probability is the probability that for a random parity-check sequence, the typical input string $`\stackrel{}{ı}`$ leads to an outcome that does not pick out a unique output string $`\stackrel{}{ı}_{h,\stackrel{}{o}}`$, i.e., does not lead to the only possible output string that could have been produced by a typical input string. We can bound this probability in the following way. The number of typical sequences satisfies $`|\mathrm{CK}(N)|2^{N(S_0+\delta )}`$. For parity subsets chosen randomly, the probability that two typical input strings, $`\stackrel{}{ı}`$ and $`\stackrel{}{ȷ}`$, agree on all $`r`$ parity checks—i.e., have the same outcome—is $`2^r`$; thus the probability that $`\stackrel{}{ı}`$ and $`\stackrel{}{ȷ}`$ agree on all $`r`$ parity checks and produce different output strings, $`\stackrel{}{ı}_h(\stackrel{}{ı})`$ and $`\stackrel{}{ı}_h(\stackrel{}{ȷ})`$, is $`2^r`$. Hence the probability of not producing a unique output, given a typical input $`\stackrel{}{ı}`$, is bounded by

$$p(\overline{\mathrm{accept}}|\stackrel{}{ı},\stackrel{}{ı}\mathrm{CK}(N))2^r\times 2^{N(S_0+\delta )}=\zeta .$$
(51)
This implies that the conditional acceptance probability (48) satisfies

$$p(\mathrm{accept}|\stackrel{}{ı},\stackrel{}{ı}\mathrm{CK}(N))1\zeta .$$
(52)
Bayes’s rule tells us that the posterior probability for output string $`\stackrel{}{ı}_h`$, given $`h`$ and $`\stackrel{}{o}`$, is

$`p(\stackrel{}{ı}_h|h,\stackrel{}{o})`$ $`=`$ $`{\displaystyle \underset{\stackrel{}{ı}I_h(\stackrel{}{o},\stackrel{}{ı}_h)}{}}p(\stackrel{}{ı}|h,\stackrel{}{o})`$ (53)
$`=`$ $`{\displaystyle \underset{\stackrel{}{ı}I_h(\stackrel{}{o},\stackrel{}{ı}_h)}{}}{\displaystyle \frac{p(\stackrel{}{o}|h,\stackrel{}{ı})p(h)p(\stackrel{}{ı})}{p(\stackrel{}{o}|h)p(h)}}`$ (54)
$`=`$ $`{\displaystyle \underset{\stackrel{}{ı}I_h(\stackrel{}{o},\stackrel{}{ı}_h)}{}}{\displaystyle \frac{p(\stackrel{}{o}|h,\stackrel{}{ı})p(\stackrel{}{ı})}{p(\stackrel{}{o}|h)}},`$ (55)
where

$$p(\stackrel{}{o}|h)=\underset{\stackrel{}{ı}}{}p(\stackrel{}{o}|h,\stackrel{}{ı})p(\stackrel{}{ı})$$
(56)
is the probability for outcome string $`\stackrel{}{o}`$, given parity-check sequence $`h`$.

Given a parity-check sequence $`h`$ and an accepted outcome $`\stackrel{}{o}A_h`$ for that sequence, we judge the “success” of the accepted output string $`\stackrel{}{ı}_{h,\stackrel{}{o}}`$ by the posterior probability, i.e,

$$p(\mathrm{success}|h,\stackrel{}{o})=p(\stackrel{}{ı}_{h,\stackrel{}{o}}|h,\stackrel{}{o})=\underset{\stackrel{}{ı}I_h(\stackrel{}{o},\stackrel{}{ı}_{h,\stackrel{}{o}})}{}p(\stackrel{}{ı}|h,\stackrel{}{o})\text{for }\stackrel{}{o}A_h\text{.}$$
(57)
The total probability of success, $`p(\mathrm{success})`$, is obtained by averaging over all parity-check sequences $`h`$ and over all accepted outcomes $`\stackrel{}{o}A_h`$. This probability can be manipulated in the following ways:

$`p(\mathrm{success})`$ $`=`$ $`{\displaystyle \underset{h}{}}{\displaystyle \underset{\stackrel{}{o}A_h}{}}p(\mathrm{success}|h,\stackrel{}{o})p(\stackrel{}{o}|h)p(h)`$ (58)
$`=`$ $`{\displaystyle \underset{h}{}}{\displaystyle \underset{\stackrel{}{o}A_h}{}}{\displaystyle \underset{\stackrel{}{ı}I_h(\stackrel{}{o},\stackrel{}{ı}_{h,\stackrel{}{o}})}{}}p(\stackrel{}{ı}|h,\stackrel{}{o})p(\stackrel{}{o}|h)p(h)`$ (59)
$`=`$ $`{\displaystyle \underset{h}{}}{\displaystyle \underset{\stackrel{}{o}A_h}{}}{\displaystyle \underset{\stackrel{}{ı}I_h(\stackrel{}{o},\stackrel{}{ı}_{h,\stackrel{}{o}})}{}}p(\stackrel{}{o}|h,\stackrel{}{ı})p(h)p(\stackrel{}{ı})`$ (60)
$``$ $`{\displaystyle \underset{h}{}}{\displaystyle \underset{\stackrel{}{o}A_h}{}}{\displaystyle \underset{\genfrac{}{}{0pt}{}{\stackrel{}{ı}I_h(\stackrel{}{o},\stackrel{}{ı}_{h,\stackrel{}{o}})}{\stackrel{}{ı}\mathrm{CK}\left(N\right)}}{}}p(\stackrel{}{o}|h,\stackrel{}{ı})p(h)p(\stackrel{}{ı})`$ (61)
$`=`$ $`{\displaystyle \underset{h}{}}{\displaystyle \underset{\stackrel{}{o}A_h}{}}{\displaystyle \underset{\stackrel{}{ı}\mathrm{CK}(N)}{}}\delta _{\stackrel{}{o},\stackrel{}{o}_{h,\stackrel{}{ı}}}\delta _{\stackrel{}{ı}_h(\stackrel{}{ı}),\stackrel{}{ı}_{h,\stackrel{}{o}}}p(h)p(\stackrel{}{ı}).`$ (62)
The inequality here follows from restricting the sum over input strings to typical strings and reflects the fact that an atypical string might lead to an accepted outcome and to the accepted output string $`\stackrel{}{ı}_{h,\stackrel{}{o}}`$, thereby contributing to the success probability. The final equality comes from using Eq. (39) for $`p(\stackrel{}{o}|h,\stackrel{}{ı})`$. Using Eqs. (35), (48), and (52), we can now bound the probability of success:

$`p(\mathrm{success})`$ $``$ $`{\displaystyle \underset{\stackrel{}{ı}\mathrm{CK}(N)}{}}p(\stackrel{}{ı}){\displaystyle \underset{h}{}}p(h){\displaystyle \underset{\stackrel{}{o}A_h}{}}\delta _{\stackrel{}{o},\stackrel{}{o}_{h,\stackrel{}{ı}}}\delta _{\stackrel{}{ı}_h(\stackrel{}{ı}),\stackrel{}{ı}_{h,\stackrel{}{o}}}`$ (63)
$`=`$ $`{\displaystyle \underset{\stackrel{}{ı}\mathrm{CK}(N)}{}}p(\stackrel{}{ı})p(\mathrm{accept}|\stackrel{}{ı},\stackrel{}{ı}\mathrm{CK}(N))`$ (64)
$``$ $`(1\zeta ){\displaystyle \underset{\stackrel{}{ı}\mathrm{CK}(N)}{}}p(\stackrel{}{ı})`$ (65)
$`=`$ $`(1\zeta )p(\mathrm{CK}(N))`$ (66)
$``$ $`(1\zeta )(1\eta ϵ)`$ (67)
$``$ $`1\zeta \eta ϵ.`$ (68)
This is the desired result. Assuming we can choose arbitrary positive constants $`ϵ`$ and $`\eta `$ and have sufficiently large $`N`$, the probability (68) can be made arbitrarily close to 1.

Except for certain singular distributions $`p(\stackrel{}{w})`$, given an exchangeable state of the form (12), it is always possible to make $`\eta `$ in Eq. (28) arbitrarily small by choosing the entropy $`S_0`$ sufficiently large ($`0S_0<2`$); if $`S_01`$, however, then the number of hashing rounds $`rN`$, which means there is no yield since $`Nr0`$. To decrease the value of $`S_0`$ and thereby make the yield positive or increase an already positive yield, one can perform quantum state tomography on some of the pairs to obtain more data about the state, generally producing a narrower posterior distribution $`p^{}(\stackrel{}{w})`$ (see Sec. II). The width of the posterior distribution depends on the number of pairs sacrificed for the tomographic measurements, but not on the total number of pairs $`N`$. The number of pairs needed for tomography can therefore be neglected in the asymptotic limit of large $`N`$.

Asymptotically, the prior probability of obtaining a posterior $`p^{}(\stackrel{}{w})`$ concentrated at $`\stackrel{}{w}=\stackrel{}{w}_0`$ with an entropy $`S_{\stackrel{}{w}_0}<S_0`$ is given by the expression

$$p(S<S_0)_{S_\stackrel{}{w}<S_0}𝑑\stackrel{}{w}p(\stackrel{}{w}),$$
(69)
where $`p(\stackrel{}{w})`$ is the prior distribution (12) defining the initial state. Putting everything together we see that, for $`S_0<1`$, $`p(S<S_0)`$ is the probability of obtaining an asymptotic yield of $`N(1S_0)`$ using a combination of quantum state tomography and one-way hashing.

If most of the prior distribution $`p(\stackrel{}{w})`$ is concentrated on states with an entropy exceeding 1 bit, i.e., if $`p(S<1)`$ is small, then it will normally be a better strategy to precede the hashing procedure by a few iterations of the recurrence method. This is the content of the next section.

## IV Entanglement purification by recurrence

If the generating function $`p(\stackrel{}{w})`$ has no significant support on weights $`\stackrel{}{w}`$ with $`S_\stackrel{}{w}<1`$, then hashing cannot be used for entanglement purification, at least initially. It might still be possible, however, to distill some entanglement by using the more robust (but far more wasteful) technique of recurrence .

In the recurrence algorithm, an initial set of $`2N`$ entangled qubit pairs is grouped into $`N`$ sets of 2 pairs each. In each set, one pair is designated the target pair, and the other the control pair. Alice and Bob thus have $`N`$ target qubits and $`N`$ control qubits each. Alice now rotates all her qubits by $`\pi /2`$ about the $`x`$ axis, while Bob rotates all his qubits by $`\pi /2`$ about the $`x`$ axis. Each of them then performs a controlled-NOT operation from each control qubit onto the corresponding target qubit and measures his or her target qubit in the $`z`$ basis ($`|0`$ and $`|1`$). The target qubits are then discarded. If Alice and Bob both get the same result for a given target pair (i.e., both 0 or both 1), the procedure has succeeded, and the control pair can be shown to have increased entanglement. If their results differ, the procedure has failed, and the control qubits must also be discarded.

If the state of both target and control pairs is of form (11), the probability of success is

$$p_s=p_s(\stackrel{}{w})=(w_1+w_4)^2+(w_2+w_3)^2,$$
(70)
and the new state of the control pair after the measurement has weights

$`w_1^{}`$ $`=`$ $`2w_2w_3/p_s,`$ (71)
$`w_2^{}`$ $`=`$ $`(w_2^2+w_3^2)/p_s,`$ (72)
$`w_3^{}`$ $`=`$ $`2w_1w_4/p_s,`$ (73)
$`w_4^{}`$ $`=`$ $`(w_1^2+w_4^2)/p_s.`$ (74)
If initially $`w_4>1/2`$, then this procedure converges towards $`w_4=1`$. The convergence is slow, however, and since more than half of all the pairs is discarded each time, the yield is generally low.

Suppose that instead of a product state we have an exchangeable state of the form (12). We can carry out the procedure exactly as before, grouping the pairs into sets of two, with a target and control bit. If there are initially $`2N`$ pairs in the state

$$\rho ^{(2N)}=𝑑\stackrel{}{w}p(\stackrel{}{w})\rho _\stackrel{}{w}^{2N},$$
(75)
then after performing the measurements, Alice and Bob will get the same result $`N_s`$ times and different results $`NN_s`$ times, leaving them with a new state of the form (75) for $`N_s`$ pairs. For large $`N`$, the posterior distribution $`p(\stackrel{}{w}|N_s)`$ will generally be sharply peaked about those $`\stackrel{}{w}`$ which give a value of $`p_s`$ close to $`N_s/N`$. Unlike hashing, the recurrence algorithm produces a posterior state $`\rho ^{(N_s)}`$ which is exchangeable. We now turn to how we find this state in light of the measurement results.

Compared with the hashing algorithm, where precisely one bit of information is obtained in each round of the procedure, in the recurrence method much more information is obtained, namely the value of $`N_s`$. We can therefore deduce the posterior distribution

$$p(\stackrel{}{w}|N_s)=\frac{p(N_s|\stackrel{}{w})p(\stackrel{}{w})}{p(N_s)},$$
(76)
where

$$p(N_s|\stackrel{}{w})=\left(\genfrac{}{}{0pt}{}{N}{N_s}\right)[p_s(\stackrel{}{w})]^{N_s}[1p_s(\stackrel{}{w})]^{NN_s},$$
(77)
and

$$p(N_s)=𝑑\stackrel{}{w}p(N_s|\stackrel{}{w})p(\stackrel{}{w}).$$
(78)
Because the remaining states have been transformed according to (74), we must also change to the new variables $`\stackrel{}{w}^{}`$. So the new state is

$$\stackrel{~}{\rho }^{(N_s)}=𝑑\stackrel{}{w}^{}p^{}(\stackrel{}{w}^{})\rho (\stackrel{}{w}^{}),$$
(79)
where

$$p^{}(\stackrel{}{w}^{})d\stackrel{}{w}^{}=p(\stackrel{}{w}|N_s)d\stackrel{}{w}.$$
(80)
While this Bayesian procedure is very simple compared to the hashing method, it is still a bit too complicated for simple illustration. There is, however, an even simpler variant of this technique that is easy to analyze. Suppose that, instead of the general Bell-diagonal state (11), we have an initial Werner state

$$\rho (F)=F𝚽_++\frac{1F}{3}(𝚽_{}+𝚿_++𝚿_{}).$$
(81)
We can carry out the recurrence procedure exactly as above, with the probability of success

$$p_s(F)=(8F^24F+5)/9;$$
(82)
here $`F`$ denotes the fidelity of the state with $`𝚽_+`$, with $`F>1/2`$ necessary for distillability. The recurrence procedure does not in general lead to a new state of form (81), but by twirling the state can be put in this form, at the cost of some increase in entropy. The new state has a fidelity

$$F^{}=\frac{10F^22F+1}{8F^24F+5}.$$
(83)
Suppose that we have $`2N`$ entangled pairs, with partial information sufficient to determine that they are all in a state of the form (81), but not to determine the exact fidelity $`F`$. The joint state of the pairs is then

$$\rho ^{(2N)}=𝑑Fp(F)\rho (F)^{2N}.$$
(84)
We then group the pairs into sets of two and carry out the recurrence procedure on each set, with $`N_s`$ successful results. We can then deduce a revised generating function

$$p(F|N_s)=\frac{p(N_s|F)p(F)}{p(N_s)},$$
(85)
where

$$p(N_s|F)=\left(\genfrac{}{}{0pt}{}{N}{N_s}\right)[p_s(F)]^{N_s}[1p_s(F)]^{NN_s},$$
(86)
and

$$p(N_s)=𝑑Fp(N_s|F)p(F).$$
(87)
The new density operator for the $`N_s`$ remaining pairs is

$$\rho ^{(N_s)}=𝑑F^{}p^{}(F^{})\rho (F^{})^{N_s},$$
(88)
where the the posterior distribution is expressed in terms of the new variable $`F^{}`$ given by (83). Working this out explicitly, we get

$$p^{}(F^{})=\left(8F(F^{})2+\frac{3(34F^{})}{\sqrt{6F^{}4F_{}^{}{}_{}{}^{2}1}}\right)\frac{p[F(F^{})|N_s]}{108F^{}},$$
(89)
where $`F(F^{})`$ is the inverse of (83):

$$F(F^{})=\frac{(12F^{})+3\sqrt{6F^{}4F_{}^{}{}_{}{}^{2}1}}{108F^{}}.$$
(90)
We can see how much information is gained by a single round of the recurrence method using this simplified version as an example. If the initial generating function is a uniform distribution, $`p(F)=4/3`$ for $`1/4<F<1`$, then for large $`N`$ the posterior distribution is highly peaked after one round. We see this in Figure 1, where the prior and posterior distributions are shown for different values of $`N`$ and a typical choice of $`N_s`$. Note that states with $`1/4<F<1/2`$ move towards $`F=1/4`$ under the procedure, producing a peak about the completely mixed state; for high $`N`$ and the value of $`N_s`$ used in our example, this peak is suppressed by the Bayesian updating. States with $`F>1/2`$ move towards $`F=1`$. The procedure has fixed points at $`F=1/4`$, $`F=1/2`$, and $`F=1`$.

It should be noted that because of its extremely small yield, the recurrence method should never be used if hashing is possible. An initial state that cannot be distilled by the hashing method, however, might, after one or more rounds of the recurrence method, satisfy the criterion (28) for some value of $`S_0<1`$. If that is so, then a combination of tomography and hashing should be used thereafter, as described in the last section.

Similarly, if $`p(\rho )`$ has some support on distillable and some on undistillable states, a few rounds of the recurrence method generally produces convergence on either a distillable or undistillable state, without ambiguity. Under certain circumstances, however, it might be beneficial to supplement this with tomographic measurements on a number of pairs as well. For example, the updating procedure (74) treats the coefficients $`w_1,w_4`$ and $`w_2,w_3`$ symmetrically. An initially symmetric state thus has this symmetry preserved, and the distribution $`p(\stackrel{}{w})`$ might become double-peaked. In this case, measuring a small number of pairs would suffice to eliminate one of the two peaks.

## V Conclusion

We have given a Bayesian account of the entanglement purification procedures of one-way hashing and recurrence. The Bayesian formulation allows us to provide a straightforward discussion of the conditions under which maximally entangled states can be distilled from unknown or partially known quantum states. For one-way hashing, we have given the a priori probabilities for the possible asymptotic yields of maximally entangled pairs. Our results can be used to decide which combination of quantum state tomography, recurrence, and hashing to use to obtain the highest expected yield, both asymptotically and in the case of a fixed number of initially given pairs. Although our discussion is entirely in terms of pairs of qubits, the method is general and can be applied to any generalization of hashing or recurrence in Hilbert spaces of higher dimension.

## Acknowledgments

We would like to thank Howard Barnum, Oliver Cohen, Chris Fuchs, and Bob Griffiths for helpful conversations. T.A.B. was supported in part by NSF Grant No. PHY-9900755 and DOE Grant No. DE-FG02-90ER40542, R.S. was supported by the UK Engineering and Physical Sciences Research Council, and C.M.C. was supported in part by ONR Grant No. N00014-00-1-0578. Some of this work was done at the July 2000 workshop on “Quantum Information Processing” at the Benasque Center for Science in Benasque, Spain.


format: text

text:
# Pseudogap Induced Antiferromagnetic Spin Correlation in High-Temperature Superconductors

## I Introduction

The high-temperature superconductors exhibit various anomalous metallic properties in their normal phases. A gap-like behavior, first discovered by the NMR relaxation rate measurement as one of these properties has attracted a lot of current interest. It is characteristic to the underdoped cuprates and observed as a broad peak in the $`1/T_1T`$-$`T`$ curve at a slightly higher temperature than the superconducting transition point $`T_\mathrm{c}`$. The possible relation of the pseudogap phenomena with the origin of the superconductivity underlies the reason of such interest. The behavior has now been detected in the temperature dependence of various other physical quantities; the neutron scattering intensity, the magnetic susceptibility, the resistivity, the Hall coefficient and the angle-resolved photo-emission spectrum (ARPES).

A lot of theories have been proposed to explain the phenomena. Since they were observed only for compounds with double CuO2 layers like YBa2Cu4O8 for the first time, the interlayer coupling was supposed to play the predominant role on the gap formation. However, after the discovery of the phenomena on the mono-layer oxide HgBa2CuO4 by the NMR measurement, most theories are based on the model with a single CuO2 plane, such as the square-lattice $`t`$-$`J`$ model which has been extensively studied theoretically in the description of the cuprate superconductivity. Based on the concept of the spin-charge separation, Tanamoto et al.  showed that the $`t`$-$`J`$ model exhibits a gap-like behavior in its spin excitation spectrum as the result of the spinon condensation by applying the mean field approximation to the resonating valence bond basis. Onoda et al. also derived the occurrence of the gap-like behavior in the temperature dependence of the resistivity within the same model using the slave-boson mean field approximation. These results, however, crucially depend on the nature of the approximation, the validity of which is not so well established.

Miyake and Narikiyo, on the other hand, suggested that the pseudogap rather originates from the enhancement of the antiferromagnetic spin fluctuation paying attention on the nesting effect based on the phenomenological itinerant-localized duality theory. In our previous study, we also proposed a simple explanation based on the well-known property of the Heisenberg magnets. We were successful in demonstrating the presence of the gap-like behavior in the temperature dependence of the NMR relaxation rate by numerically diagonalizing the finite cluster $`t`$-$`J`$ model for sufficiently large $`J`$. Our result shows it is interpreted as a crossover from the paramagnetic to the magnetically well correlated state induced by the rapid development of the antiferromagnetic spin correlation.

Lately lots of interest have been paid on the role of the superconducting fluctuations. For instance, Koikegami and Yamada, based on the $`d`$-$`p`$ model, indicated that superconducting fluctuations will survive at higher temperature than the transition temperature $`T_\mathrm{c}`$ based on the fluctuation exchange approximation. This means that the gap-like behavior is regarded as a precursor of the gap formation of the strong coupling superconductivity as was predicted by the self-consistent $`t`$-matrix approximation by Yanase and Yamada. With the use of the $`t`$-matrix approximation Kobayashi et al showed that the gap-like behavior is induced by the appearance of the superconducting fluctuations while the antiferromagnetic spin fluctuation is suppressed on the contrary. Onoda and Imada claim that the competition between the superconducting fluctuations and antiferromagnetic spin fluctuations is necessary for deriving the gap behavior.

In spite of lots of theoretical proposals, the final answer is still far from being established. Most theories, however, seem to have an agreement on the important role of aniferromagnetic spin correlation on the pseudogap formation. In the present paper, in order to confirm the validity of our mechanism we extend our numerical investigation and derive the temperature dependence of various physical properties, including $`1/T_1T`$, in a wider parameter region that covers realistic situations for high-$`T_\mathrm{c}`$ cuprates. The effect of the next-nearest neighbor hole hopping with a coupling $`t^{}`$ is also studied. The effect of the antiferromagnetic spin correlation on the pseudogap formation is then clarified without resorting to any approximation. If we take into account the lack of reliable approximation scheme in treating the strongly correlated systems, the numerical analysis of the model has its own significance in order to check the validity of various explanations.

## II Mechanism of Pseudogap

According to our proposal, the local spin excitations are suppressed around a characteristic temperature, of the the same magnitude of the antiferromagnetic coupling $`J`$, associated with the growth of the short-range antiferromagnetic correlation as we decrease the temperature. As a result various magnetic quantities will show their particular $`T`$-dependence in reflecting the reduced local excitations. In fact the high temperature series expansion for the square-lattice antiferromagnetic Heisenberg model shows a broad peak in the temperature dependence of the NMR relaxation rate $`1/T_1T`$ around $`TJ`$. Since the hole motion acts to destroy the short-range antiferromagnetic order, the hole doping will reduce the crossover temperature in agreement with the observed hole doping dependence of the pseudogap temperature. Thus the pseudogap behavior is simply realized as the manifestation of the growth of the short-range antiferromagnetic correlation. The above picture has been supported by our numerical exact diagonalization study on the two-dimensional $`t`$-$`J`$ model with 10 lattice sites. We found that for a small hole concentration ($`\delta =0.1`$) the $`T`$ dependence of $`1/T_1T`$ does show a broad peak around the temperature where the nearest neighbor antiferromagnetic spin correlation shows rapid growing, for a sufficiently large antiferromagnetic coupling ($`J/t=0.6`$). In the next section we perform the same calculation to investigate how our previous results are modified by using realistic parameters for the cuprate superconductors and also to examine the presence of possible gap-like behaviors for various magnetic properties.

## III Numerical Analysis of $`t`$-$`J`$ model

Let us first consider the standard square-lattice $`t`$-$`J`$ model Hamiltonian defined by

$`H`$ $`=t{\displaystyle \underset{<𝐢,𝐣>,\sigma }{}}(c_{𝐣,\sigma }^{}c_{𝐢,\sigma }+c_{𝐢,\sigma }^{}c_{𝐣,\sigma })`$ (1)
$`+J{\displaystyle \underset{<𝐢,𝐣>}{}}(𝐒_𝐢𝐒_𝐣\frac{1}{4}n_𝐢n_𝐣),`$ (2)
where $`t`$ is the nearest neighbor electron hopping integral and $`J`$ is the antiferromagnetic Heisenberg exchange constant between spins on adjacent lattice sites. Throughout the paper, all the energies are measured in units of $`t`$. With the use of the calculated eigenvalues and eigenvectors, we evaluated the temperature dependence of the imaginary part of the dynamical spin susceptibility of conduction electrons $`\mathrm{Im}\chi (q,\omega )`$ and the static spin correlation function $`S_𝐢^zS_𝐣^z`$. In actual numerical estimations of $`\mathrm{Im}\chi (q,\omega )`$ the $`\delta `$-function is approximated by the Lorentzian distribution with some small width. Since we need all the eigenvalues and eigenvectors, the cluster size of the model was limited by the available disk space of the computer. We show in the following the results for the $`\sqrt{10}\times \sqrt{10}`$ cluster under the periodic boundary condition.

### A NMR relaxation rate

In order to obtain the temperature dependence of the NMR relaxation rate, we evaluate $`1/T_1T`$ by the following formula:

$$\frac{1}{T_1T}=\underset{\omega 0}{lim}\frac{1}{\omega }\underset{q}{}\mathrm{Im}\chi (q,\omega ).$$
(3)
The effect of the $`q`$-dependence of the hyperfine form factor is neglected, for simplicity. To clarify the role of antiferromagnetic spin correlation, we have also evaluated the $`T`$ dependence of the $`Q(\pi ,\pi )`$ component of the spin correlation function,

$$S(Q)=\frac{1}{N}\underset{𝐢,𝐣}{}(1)^{(𝐣𝐢)(\widehat{x}+\widehat{y})}S_𝐢^zS_𝐣^z.$$
(4)
In our previous study the following nearest-neighbor spin correlation function was used instead for the purpose,

$$C_1=\frac{1}{N}\underset{𝐢}{}\frac{1}{4}\underset{\rho =\pm \widehat{x},\pm \widehat{y}}{}S_𝐢^zS_{𝐢+\rho }^z.$$
(5)
We are using $`S(Q)`$ here to emphasize the continuity that there exists the antiferromagnetic order in the limit of no doping. Note that the terms, magnetically singlet and antiferromagnetic, are used in nearly the same meaning. We are only concerned with the short range magnetic correlation of the system of finite clusters. According to the above definitions there is no reason to make definite distinction between $`S(Q)`$ and $`C_1`$. Actually both of $`S(Q)`$ and $`C_1`$ show almost no essential difference in their temperature dependence.

We show in Fig.1 results of $`T`$ dependence of (a) $`1/T_1T`$ and (b) $`S(Q)`$ for the undoped case ($`\delta =0`$) for $`J`$=0.6, 0.5, and 0.4. Only for $`J`$=0.4, the temperature dependence of $`S(Q)`$ has already been reported by Tohyama et al. For cuprate superconductors the value $`J=0.4`$ is estimated experimentally. All the calculated $`T`$ dependence of $`1/T_1T`$ exhibits a broad peak around $`TJ`$ where $`S(Q)`$ shows the significant increase. The above behavior of $`1/T_1T`$ for $`\delta =0`$ is, for instance, consistent with the high temperature series expansion for the Heisenberg model. The quantum Monte Carlo simulation study by Sandvik and Scalapino, however, showed no peak behavior in the $`1/T_1T`$-$`T`$ curve. No peak is also observed by the NMR measurement for the undoped La2CuO4. The reason is the temperature in these studies is not so high enough to cover the crossover region of the order of $`J`$.

The same results are shown in Figs.2(a) and 2(b) for the one-hole case ($`\delta =0.1`$). Peaks in the $`T`$ dependence of $`1/T_1T`$ for $`J`$=0.5 and 0.6 are shifted to lower temperature where the rapid growth of $`S(Q)`$ is observed, in agreement with our mechanism. Although no peak appears for the case $`J`$=0.4, a slight hump still exists around the same temperature. Such a behavior will be detected as a deviation from the Curie-Weiss like temperature dependence of $`1/T_1T`$, rather than a peak as was actually observed for La2-xSrxCuO4. The same calculation for the hole-doped 4$`\times `$4 $`t`$-$`J`$ cluster does not show any gap-like anomalies. This is probably because the temperature range didn’t cover the region where the pseudogap is expected to appear. The present results indicate that the gap-like behavior appears at much higher temperature than the calculated lowest excitation gap $`\mathrm{\Delta }`$ of the cluster. For example, the broad peak appears around $`T0.4`$, while the estimated $`\mathrm{\Delta }`$ is 0.146, for $`J=0.6`$ and $`\delta `$=0.1. Therefore it excludes the possibility that the pseudogap is caused by the discreteness of energy levels of finite systems. The same results for the two-hole system ($`\delta =0.2`$) are shown in Figs.3(a) and 3(b). Although no gap-like behavior is observed, they are also consistent with our view because of the absence of any significant enhancement of the antiferromagnetic spin correlation.

### B Neutron scattering intensity

The measurement of the neutron scattering intensity of YBa2Cu3O6.6 by Sternlieb et al.  indicated the presence of the pseudogap behavior in the temperature dependence of the $`q`$-integrated dynamical susceptibility

$$\mathrm{Im}\chi (\omega )dq\mathrm{Im}\chi (q,\omega ).$$
(6)
We show, in Figs.4, 5 and 6, the temperature dependence of (a) $`\mathrm{Im}\chi (Q,\omega )`$ and (b) $`\mathrm{Im}\chi (\omega )`$ for a small $`\omega `$ (=0.01$`t`$) for $`\delta `$=0, 0.1 and 0.2. Figs.4(a), 5(a) and 6(a) show the monotonic increase of $`\mathrm{Im}\chi (Q,\omega )`$ for all the values of $`J`$ with decreasing $`T`$, independent of the doping $`\delta `$. On the other hand, $`q`$-integrated local susceptibility in Figs.4(b), 5(b) and 6(b) reveals a gap-like behavior around the same crossover temperature as that of $`1/T_1T`$ for $`\delta 0.1`$. These results are in good agreement with the above neutron scattering experiment. As for the former, the low-frequency limit of $`\mathrm{Im}\chi (Q,\omega )`$ is given by

$`\mathrm{Im}\chi (Q,\omega ){\displaystyle \frac{\chi (Q,0)}{\mathrm{\Gamma }_Q}}\chi ^2(Q,0),(\omega 0),`$

where $`\mathrm{\Gamma }_Q`$ is the Lorentzian distribution width of the frequency spectrum. The monotonic increase of $`\mathrm{Im}\chi (Q,\omega )`$ with decreasing the temperature is therefore consistent with the absence of the pseudogap behavior in the $`T`$-dependence of $`1/T_{2\mathrm{G}}`$, i.e. $`T_{2\mathrm{G}}^2\chi ^1(Q,0)`$, by the NMR measurement.

### C Magnetic susceptibility

The pseudogap behavior has also been observed in the temperature dependence of the static magnetic susceptibility $`\chi `$. The calculated results of $`\chi `$ for $`\delta `$=0, 0.1 and 0.2 are shown in Figs. 7, 8 and 9, respectively. In all the figures we can see the crossover behaviors around the same temperature as those of $`1/T_1T`$ and $`\mathrm{Im}\chi (\omega )`$ in the underdoped case ($`\delta 0.1`$), even for the realistic value $`J=0.4`$. As shown in Fig. 9, peaks appear at lower temperature for $`\delta =0.2`$. However they result from the different origin. If there are two holes in a finite cluster model, its ground state always becomes singlet and the total energy has some small excitation gap. Therefore the susceptibility shows a peak around the temperature corresponding to the lowest excitation gap of the system that comes from these finite size effects. The behavior has nothing to do with our mechanism. (The same calculation of $`\chi `$ for $`J=0.4`$ by Tohyama et al. yielded a peak even for $`\delta =0.3`$.)

To conclude, all the results presented above support our view that the pseudogap behavior observed for various magnetic properties are induced by the growth of the antiferromagnetic spin correlation.

## IV Next-Nearest Neighbor Hopping $`t^{}`$

In the previous section we showed that the antiferromagnetic spin correlation produces a gap-like behavior in the $`T`$-dependence of $`1/T_1T`$, $`\mathrm{Im}\chi (\omega )`$ and $`\chi `$ around a common crossover temperature. The characteristic temperature for $`\delta =0.1`$ is roughly estimated as $`J/2`$, as shown in Figs. 2(a), 5(b) and 8. It is, however, much higher than observed ones for real cuprates. This is partly because the effect of the hole hopping $`t`$ is overestimated compared with that of $`J`$ due to the finite size effect. As another possible reason, let us discuss below the effect of including the next-nearest neighbor hole hopping,

$`H^{}=t^{}{\displaystyle \underset{<𝐢,𝐣>^{},\sigma }{}}(c_{𝐣,\sigma }^{}c_{𝐢,\sigma }+c_{𝐢,\sigma }^{}c_{𝐣,\sigma }),`$ (7)
into the $`t`$-$`J`$ Hamiltonian (1), where $`_{<𝐢,𝐣>^{}}`$ means the summation over all the next-nearest sites. The term is originally introduced to explain the dynamics of the correlated motion of spin and hole-hopping degrees of freedom in some cuprates. The value $`t^{}0.3`$ is estimated to be suitable for Sr2CuO2Cl2 by the exact diagonalization study. To clarify the effect of $`t^{}`$ on the pseudogap formation, we show the $`T`$ dependence of $`1/T_1T`$ for various values of $`t^{}`$ in Figs. 10(a) for $`J=0.6`$ and 10(b) for $`J=0.4`$ ($`\delta =0.1`$). From Fig. 10(a) we can see that the peak temperatures are lowered by the effect. The narrowing of the peak width takes place at the same time. As the result the slight anomaly in Fig.2(a) for $`J=0.4`$, shifted to lower temperature, now becomes evident if we assume $`t^{}=0.3`$ as shown Fig.10(b). Therefore it is possible to predict the crossover temperature around a realistic temperature range $`J/4`$ by including the effect of the next-nearest neighbor hopping.

As we increases the value of $`t^{}`$, there appears, however, another difficulty. Because the peak temperature is lowered and becomes comparable with the order of the lowest excitation gap of the cluster, it is very difficult to distinguish the peak behavior from the one that comes from the discreteness of the energy levels of the system. Further calculations on larger size clusters will be necessary to clarify the situation and to obtain reliable conclusions.

## V Discussion

The results of the present study clearly showed the presence of gap-like behaviors in the temperature dependence of various magnetic properties around a single crossover temperature due to the development of antiferromagnetic spin correlation. Experimentally detailed gap-like behaviors differ slightly with each other depending on materials. In the case of La2-xSrxCuO4, for instance, the crossover temperature of $`\chi `$ ($`T_\chi ^{}`$) is slightly higher than that of $`1/T_1T`$ ($`T_{\mathrm{NMR}}^{}`$). The recent NMR Knight shift measurement for Bi2Sr2CaCu2O8+δ also indicates the presence of two different crossover temperatures. Stimulated by these discoveries, it is argued that the higher crossover temperature (the large pseudogap) will be associated with the growth of the antiferromagnetic spin correlation. On the other hand, the lower one (the small pseudogap) will be due to the singlet (or superconducting pair) formation, i.e. $`T_\chi ^{}`$ will be assigned to the former, while $`T_{\mathrm{NMR}}^{}`$ the latter. From our approach based on the finite cluster model, it will be difficult to predict the presence of double pseudogap phenomena.

Our model Hamiltonian employed here is quite simplified one. In order to deal with actual systems we have to include various additional interactions specific to each system. In the present paper we are particularly interested in properties that are common to all the cuprate superconductors. Therefore in order to compare with experiments, we have to be aware that the observed properties are intrinsic to all of them or not. It will also be important to confirm whether the presence of two crossover temperatures is common to all the cuprates systems.

As was pointed out in the Introduction, spin-gap phenomena is characteristic to the underdoped cuprates where the superconducting transition temperature $`T_\mathrm{c}`$ decreases proportional to the hole doping concentration. On the other hand the pseudogap temperature increases. Because of this opposite doping dependence, it seems to be difficult to associate the pseudo-gap phenomena with the superconducting pairing fluctuations. The antiferromagnetic correlation, therefore, plays the dominant role on reducing the low energy excitations of the system as far as the magnetic freedoms are concerned. Only around the critical temperature $`T_\mathrm{c}`$, they will be further modified by the presence of the superconducting transition. These effect are limited to the very low energy regions. The present mechanism is based on the well-known properties of low-dimensional Heisenberg magnets. The overall doping dependence of the crossover temperature is also in agreements with experiments. It decreases with increasing hole doping, whereas the transition temperature $`T_\mathrm{c}`$ increases towards the optimum condition. Because of these reasons we suppose that our mechanism is one of most probable candidates for the phenomena.

Because the model treated here is a single-hole system ($`\delta =0.1`$ for the 10 site cluster), its ground state is doublet. Even in this doublet case we can derive the gap-like behavior in the temperature dependence of $`1/T_1T`$. If the same calculation is done on a two-hole system of a larger cluster with the same doping $`\delta `$, a slightly different properties will be obtained because its ground state now becomes singlet. We expect that the gap-like behavior will then be more evident. The difference becomes less conspicuous, if we increase the size of clusters, for it results from the size effect. Though it is very difficult because of various limitations concerning the available resources of computer systems, it will be interesting to extend our present numerical diagonalization study to the two-hole system with larger cluster size to clarified the situation.

## VI Summary

We have shown that the pseudogap behaviors observed in the high-temperature superconductors originate from the growth of the antiferromagnetic spin correlation based on the exact diagonalization study on the finite cluster $`t`$-$`J`$ model in a realistic parameter region for the real cuprates. We also found that the pseudogap temperature is lowered by including the next-nearest neighbor hopping effect.

## Acknowledgment

We wish to thank Profs M. Sato, K Yamada, Y. Ohta and Y. Hasegawa for fruitful discussions. We also thank the Supercomputer Center, Institute for Solid State Physics, University of Tokyo for the facilities and the use of the Fujitsu VPP500. This research was supported in part by Grant-in-Aid for the Scientific Research Fund from the Ministry of Education, Science, Sports and Culture (11440103).

## References