text:
# Thermal concurrence mixing in a 1D Ising model

## I Introduction

Entanglement, the rather counterintuitive non-local correlations exhibited by quantum systems, has recently become one of the most valuable resources in quantum information processing bennett00 . Over the past few years it has developed into a quantifiable physical resource vedral97 ; bennett96 ; wootters98  in an analogous manner to energy. Thus, the amount of entanglement present naturally in complex physical systems (systems with many interacting components) now becomes a relevant question to ask. Condensed matter physicists have long investigated correlations between parts of composite systems. Entanglement is the “quantum” or “nonlocal” part of these correlations. As such, it can behave very differently from the total correlations. For example, while correlations are averaged on mixing states, entanglement generally decreases. The topic of variation of entanglement in condensed matter systems with respect to the variation of external parameters such as temperature, field components etc., is a relatively unexplored and potentially rich area of study. In this context, as a simple initial model, Arnesen, Bose and Vedral have studied the variation of entanglement with temperature and magnetic field in a 1D isotropic finite Heisenberg chain arnesen00 . Prior to that, Nielsen had investigated the entanglement between two qubits interacting via the Heisenberg interaction at a nonzero temperature nielsen98  and O’Connor and Wootters have investigated the entanglement in the ground state of an antiferromagnetic isotropic Heisenberg ring wootters00 . In Ref. arnesen00 , the entanglement at a nonzero temperature, being that of a thermal state, was called thermal entanglement. Subsequently, Wang has studied the quantum Heisenberg XY-model wang01  and the two-qubit anisotropic XXZ-model wang01b  in a similar context.

In this paper, we are going to study the thermal entanglement in the 1D Ising model in an external magnetic field sachdev . Ising-like interactions form the basic coupling in many proposals for experimental systems that can be used to perform quantum computation, see for example, cory96 ; kane98 ; mooij99 ; briegel00 . The 1D Ising model describes a set of linearly arranged spins (qubits), each interacting with its nearest neighbors by a coupling which is proportional to $`\sigma _z\sigma _z`$. This coupling can be diagonalized in a basis of disentangled states. Naïvely one might think that this implies a complete absence of entanglement in the Ising model. However, an external magnetic field with a component, however small, along a direction perpendicular to the $`z`$ axis is sufficient to make the eigenstates entangled.

We start in section II by considering analytically the case of two qubits interacting via the Ising interaction in a magnetic field orthogonal to the $`z`$ direction. In section III, we formulate a theorem for the concurrence mixing due to occupation of both the ground and the excited states. Next, in section IV, we consider numerically the variation of entanglement with the orientation of magnetic field. Before concluding, in section V we show that the kinds of behavior found for two qubits also hold for many qubits.

## II Two qubits with Ising interaction

The Hamiltonian for an isotropic quantum Ising model with nearest neighbor couplings in an external magnetic field can in the most general form be expressed as

$$\widehat{H}=J\underset{<i,j>}{}\widehat{\sigma }_z^i\widehat{\sigma }_z^j+\stackrel{}{B}\underset{k}{}\stackrel{}{\widehat{\sigma }^k},$$
(1)
where the indices $`i`$, $`j`$ and $`k`$ label the $`N`$ spins. Here we will consider systems in one spatial dimension with periodic boundary conditions so the $`N`$th spin also couples to the first spin. Thus we have a qubit “ring”. First we will consider the case of $`N=2`$. Our Hamiltonian can then be written as

$$\widehat{H}=2J\widehat{\sigma }_z\widehat{\sigma }_z+\stackrel{}{B}(\stackrel{}{\widehat{\sigma }}\widehat{I}+\widehat{I}\stackrel{}{\widehat{\sigma }}).$$
(2)
The usual form of the Ising model has a magnetic field only along the $`z`$ axis. This case has no entanglement at all, since the Hamiltonian is diagonal in the standard disentangled basis $`\{|00,|01,|10,|11\}`$, where $`|0`$ stands for spin up and $`|1`$ stands for spin down. However, in this paper we will consider the cases when the magnetic field is not parallel to the $`z`$ axis.

### II.1 Orthogonal fields

Let us first study the special case when the magnetic field is perpendicular to the $`z`$ axis, say $`\stackrel{}{B}=B\stackrel{}{x}`$. Our system is now described by the following Hamiltonian:

$$\widehat{H}=2J\widehat{\sigma }_z\widehat{\sigma }_z+B(\widehat{\sigma }_x\widehat{I}+\widehat{I}\widehat{\sigma }_x).$$
(3)
We are going to investigate the entanglement in this two-qubit Ising ring. In this paper, we will use the squared concurrence wootters98 ; wootters00a , called the tangle $`\tau `$, as a measure of entanglement. To calculate this, first we need to define the product matrix $`R`$ of the density matrix, $`\rho `$, and its spin-flipped matrix, $`\stackrel{~}{\rho }=(\widehat{\sigma }_y\widehat{\sigma }_y)\rho ^{}(\widehat{\sigma }_y\widehat{\sigma }_y)`$. Hence, we have

$$R\rho \stackrel{~}{\rho }=\rho (\widehat{\sigma }_y\widehat{\sigma }_y)\rho ^{}(\widehat{\sigma }_y\widehat{\sigma }_y).$$
(4)
Now concurrence is defined by

$$C=max\{\lambda _1\lambda _2\lambda _3\lambda _4,0\},$$
(5)
where the $`\lambda _i`$ are the square roots of the eigenvalues of $`R`$, in decreasing order. In this method the standard basis, $`\{|00,|01,|10,|11\}`$, must be used. As usual for entanglement measures, the tangle ranges from $`0`$ (no entanglement) to $`1`$, when the two qubits are maximally entangled.

For finite temperatures we need the density matrix, $`\rho `$, for a system which is at thermal equilibrium. This is given by $`\rho =e^{\widehat{H}/T}/Z`$, where $`Z=tr(e^{\widehat{H}/T})`$ is the partition function (using units where the Boltzmann constant, $`k_B=1`$). We then solve the time independent Schrödinger equation for our qubits. The energy levels of our Hamiltonian (3) are, in rising order, $`2\sqrt{J^2+B^2},2J,2J,2\sqrt{J^2+B^2}`$, as in Fig. 1.

For zero temperature only the lowest energy level is populated. The tangle of this pure state can easily be calculated from the density matrix, for $`B>0`$,

$$\tau =\frac{J^2}{J^2+B^2}=\frac{1}{1+\left(\frac{B}{J}\right)^2}.$$
(6)
In Fig. 2, a contour plot of the tangle $`\tau `$, as a function of magnetic field amplitude, $`B`$, and the temperature, $`T`$ is shown.

From Eq. (6), it is clear that the entanglement is highest for nearly vanishing magnetic fields and decreases with increasing field amplitude. However, Eq. (6) is not valid for strictly $`B=0`$, in which limit it seems to predict maximal entanglement. At precisely $`B=0`$, in fact, no entanglement is present (the eigenstates are same as those of the usual Ising Hamiltonian without any magnetic field). Hence there is a quantum phase transition sachdev  at the point B=0 when the entanglement jumps from zero to maximal even for an infinitesimal increase of $`B`$. As we will see later this point is only one point on a transition line for $`B`$-fields along the $`z`$ axis.

Let us now turn our attention to the more realistic case of non-zero temperatures. For a general pure state only one of the eigenvalues of Eq. (4) is non-zero and therefore equal to the tangle. This statement is proved in *lemma 1* in the next section. For low temperature and magnetic field, i.e. $`B,TJ`$, it is a good approximation to assume that only the two lowest energy levels are populated. This becomes clear when we look at Fig. 1 in the regime $`BJ`$. The lowest two levels are much closer to each other compared with their separation from the third lowest energy level (i.e. the second excited state). Thus when the temperature is low, only the lowest two levels appear in the state of the system. We will find (*theorem 1*, next section) that, in our case, the combination of the two lowest states also combines their concurrences in the following weighted subtraction:

$$C=\mathrm{max}\{|w_0C_0w_1C_1|,0\},$$
(7)
where the index $`0`$ refers to the ground state, while $`1`$ refers to the excited state and $`w_0`$ and $`w_1`$ are the weights of the ground and excited states respectively. The weights can be any weights from the statistics, for example Maxwell-Boltzmann statistics or Fermi-Dirac statistics. We call this concurrence mixing. In our case, the first excited state is the Bell state, $`|\mathrm{\Psi }^{}=(|01|10)/\sqrt{2}`$, which has $`\tau =1`$, and Eq. (7) reduces to

$$C=|w_0\frac{J}{\sqrt{J^2+B^2}}w_1|.$$
(8)
In general, the first term in the above equation is larger than the second, and in this case the concurrence decreases with temperature as $`w_0`$ decreases and $`w_1`$ increases (cf Fig. 2). In Fig. 2 we also see that, for a given temperature, the entanglement can be increased by adjusting the magnetic field and is generally largest for some intermediate value of the magnetic field. This effect can be understood by noting that $`w_0`$ increases with increasing $`B`$ as the energy separation between the levels increase, but $`J/\sqrt{J^2+B^2}`$ decreases. As a result the combined function reaches a peak as we vary $`B`$ and decreases subsequently, inducing analogous behavior for the concurrence.

## III Concurrence mixing

In this section, we are going to formulate and prove a useful concurrence mixing theorem. We begin with a lemma which illustrates the method used in the theorem. The results of *lemma 1* appear in Ref. wootters98 .
Lemma 1: *Let $`\rho `$ be a pure density matrix. Then the product matrix $`R=\rho \stackrel{~}{\rho }`$, where $`\stackrel{~}{\rho }=(\widehat{\sigma }_y\widehat{\sigma }_y)\rho ^{}(\widehat{\sigma }_y\widehat{\sigma }_y)`$, has only one non-zero eigenvalue, and its value is the concurrence squared, i.e. the tangle. For a general pure state, $`|\alpha =a|00+b|01+c|10+d|11`$ the concurrence is $`C=2|adbc|`$ or, written as a Schmidt decomposition, $`C=2|c_0c_1|`$, where $`c_i`$ are the two Schmidt coefficients.*
Proof: Consider a general pure density matrix $`\rho =|\alpha \alpha |`$. By writing out the product matrix

$$\rho \stackrel{~}{\rho }=|\alpha \alpha |\widehat{\sigma }_y\widehat{\sigma }_y|\alpha \alpha |\widehat{\sigma }_y\widehat{\sigma }_y,$$
(9)
we see directly that $`|u_0=|\alpha `$ is an eigenstate with eigenvalue $`|\alpha |\widehat{\sigma }_y\widehat{\sigma }_y|\alpha |^2`$. It is always possible to find three more vectors $`|\alpha _k^{},k=1,2,3`$ all of them linearly independent of each other and orthogonal to $`|\alpha `$. Thus the remaining three eigenvectors can be written as $`|u_k=\widehat{\sigma }_y\widehat{\sigma }_y|\alpha _k^{},k=1,2,3`$, all with eigenvalue zero. From Eq. (5) we now get the concurrence to be $`C=|\alpha |\widehat{\sigma }_y\widehat{\sigma }_y|\alpha |=2|adbc|`$. Thus, for a pure state, concurrence can be defined as the absolute expectation value of the operator $`\widehat{\sigma }_y\widehat{\sigma }_y`$. By tracing out one qubit and solving for the eigenvalues, which are equal to the square of the Schmidt coefficients, $`c_i`$, of the remaining density matrix, we find that the concurrence also can be written as $`C=2|c_0c_1|`$.
Theorem 1: *Consider two pure states of the same system $`|\alpha _m`$ and $`|\alpha _n`$. If the spin-flip overlap is zero, i.e.*

$$\alpha _m|\widehat{\sigma }_y\widehat{\sigma }_y|\alpha _n=0,$$
(10)
*then the concurrence of the mixture of the two pure states, with weights $`w_i`$, can be expressed as*

$$C_{mixed}=|w_mC_mw_nC_n|.$$
(11)
Proof: Let $`\rho _i=|\alpha _i\alpha _i|`$, $`i=m,n`$, be our two pure states. From our lemma, we have

$`\rho _i\stackrel{~}{\rho _i}|u_{i0}`$ $`=C_i^2|u_{i0}`$ (12)
$`\rho _i\stackrel{~}{\rho _i}|u_{ik}`$ $`=0,k=1,2,3`$ (13)
where $`|u_{i0}=|\alpha _i`$ and $`|u_{ik}=\widehat{\sigma }_y\widehat{\sigma }_y|\alpha _{ik}^{}`$. Let us write our mixed state, $`\rho `$, as a weighted average of the pure density matrices, $`\rho =w_m\rho _m+w_n\rho _n`$. Since $`\stackrel{~}{\rho }`$ is only a linear transformation of $`\rho `$, we also have $`\stackrel{~}{\rho }=w_m\stackrel{~}{\rho _m}+w_n\stackrel{~}{\rho _n}`$. Using these assumptions, we can write down the product matrix

$$\rho \stackrel{~}{\rho }=w_m^2\rho _m\stackrel{~}{\rho _m}+w_mw_n(\rho _m\stackrel{~}{\rho _n}+\rho _n\stackrel{~}{\rho _m})+w_n^2\rho _n\stackrel{~}{\rho _n}.$$
(14)
Our condition (10) makes the cross terms drop out, since

$$\rho _i\stackrel{~}{\rho _j}=|\alpha _i\alpha _i|\widehat{\sigma }_y\widehat{\sigma }_y|\alpha _j\alpha _j|\widehat{\sigma }_y\widehat{\sigma }_y=0.$$
(15)
Furthermore, condition (10) together with Eq. (12) gives the following relation

$`\rho _i\stackrel{~}{\rho _i}|u_{j0}`$ $`=|\alpha _i\alpha _i|\widehat{\sigma }_y\widehat{\sigma }_y|\alpha _i\alpha _i|\widehat{\sigma }_y\widehat{\sigma }_y|\alpha _j`$ (16)
$`=\delta _{ij}C_j^2|u_{j0}.`$
The Eqs. (14)-(16) give two of the four eigenequations of the product matrix

$$\rho \stackrel{~}{\rho }|v_i=(\delta _{im}w_m^2C_m^2+\delta _{in}w_n^2C_n^2)|v_i,$$
(17)
where $`|v_i=|u_{i0}=|\alpha _i`$. Since these two eigenvectors only span two dimensions in the four-dimensional space, we can always find another two vectors $`|\alpha _k^{},k=2,3`$ which are linear independent of each other and orthogonal to the two eigenstates. Thus the last two eigenvectors are $`|v_k=\widehat{\sigma }_y\widehat{\sigma }_y|\alpha _k^{},k=2,3`$, both with zero eigenvalue. Eq. (5) now gives our mixed concurrence formula.
*Theorem 1* applies to any system with a mixture of two pure states satisfying condition (10). It can easily be extended to apply to the mixing of more pure states. The requirement is then that condition (10) must hold for all pairs of pure states.

In our case, it would have been interesting if, when including all four levels, the concurrence could be calculated as

$$C=\underset{k}{\mathrm{max}}\{2w_kC_k\underset{i}{}w_iC_i,0\}.$$
(18)
In fact, for a three-level approximation (involving the first three levels), this formula is correct, however the exact four-level concurrence is not in agreement with Eq. (18), because condition (10) does not hold for mixing the ground state with the third excited state.

## IV Arbitrary fields

In section II we treated a case of a magnetic field orthogonal to the Ising direction. We are now going to generalize this to arbitrary magnetic fields. The new Hamiltonian can be written

$`\widehat{H}=`$ $`2J\widehat{\sigma }_z\widehat{\sigma }_z`$ (19)
$`+B\mathrm{sin}\theta (\widehat{\sigma }_x\widehat{I}+\widehat{I}\widehat{\sigma }_x)`$
$`+B\mathrm{cos}\theta (\widehat{\sigma }_z\widehat{I}+\widehat{I}\widehat{\sigma }_z),`$
where $`\theta `$ is the angle between the magnetic field and the Ising direction. It is sufficient to consider variation of $`B`$ in a plane containing the Ising direction, because in 3 spatial dimensions the Hamiltonian possesses rotational symmetry about the $`z`$ axis.

The expression for the tangle is analytically solvable. However, because of a difficult cubic equation in the diagonalization, the expressions are complicated, so we present the results in graphical form. At zero temperature, Fig. 3 shows our solution when the tangle is plotted as a function of $`B_x=B\mathrm{sin}\theta `$ and $`B_z=B\mathrm{cos}\theta `$, and Fig. 4 shows the solution when the tangle is plotted as a function of the amplitude $`B`$ and angle $`\theta `$.

We notice that the region around $`B_x=0`$ for all $`|B_z|<2J`$ has the highest possible entanglement. At exactly at $`B_x=0`$ there should not be any entanglement, the white region of Fig. 3 indicates a quantum phase transition at $`B_x=0`$ (the sharpness of the transition being illustrated by the fact that the zero entanglement line at $`B_x=0`$ is so thin that it is invisible). For small angles, $`\theta `$, there are two energy levels close to the energy $`2J`$ with corresponding states close to the Bell states $`|\mathrm{\Psi }^\pm =(|01\pm |10)/\sqrt{(}2)`$. Thus we get a maximally entangled qubit pair in the limit. However, at $`\stackrel{}{B}=B_z\stackrel{}{z}`$, with $`|B_z|<2J`$, the states are degenerate with no entanglement as a result. In the case $`B_z>2J`$ ($`B_z<2J`$) the ground state is always the non-entangled state $`|11`$ ($`|00`$). Also notice that $`\theta =\pi /2`$ corresponds to our earlier orthogonal case, thus the tangle follows Eq. (6). Even when $`|B_x|`$ is increased to the point where it starts to dominate, the spins will simply align along $`B_x`$ and give a disentangled state. Thus the entanglement falls off with increasing strength of the magnetic field in either direction.

Let us now look at the case of finite temperature (thermal entanglement). The first excited state is $`|\mathrm{\Psi }^{}`$ which lies at the energy $`2J`$. This state is totally independent of magnetic field, thus the tangle corresponding to this state forms a constant plane at $`1`$. Fortunately, condition (10) in our theorem is also satisfied, which makes Eq. (7) valid. In Figs. 5 and 6 a numerical solution is shown at a low temperature. Note how fast the tangle drops to zero for a low $`|B_x|`$-component. This does not contradict the concurrence mixing formula, as the weights $`w_i`$ also depend on the magnetic field through the energy. The fast drop in the tangle is due to the degeneracy at $`B_x=0`$. The smallness of the energy difference at low values of $`|B_x|`$ makes the two levels almost equally populated even for small temperatures. The line of zero entanglement at $`B_x=0`$ for $`T=0`$ has broadened into a region of almost zero entanglement in the finite temperature case (compare Figs. 3, 5).

It is also interesting to see that there exists an angle $`\theta =\theta ^{}(B,T)`$, where the entanglement is maximum for a given temperature and amplitude

$$\mathrm{max}\tau (\stackrel{}{B},T)=\tau (\theta ^{}(B,T)).$$
(20)
This feature can be explained heuristically if we assume that with $`B_x`$ and $`B_z`$ fixed, the entanglement should change continuously with temperature. We know that increasing the temperature widens the low entanglement zone around $`B_x=0`$ and the entanglement has to fall off for large $`|B_x|`$. So it is expected that at some intermediate value of $`|B_x|`$ (and hence $`\theta `$) the maximal entanglement will be reached. As we increase the temperature further, the near-zero entanglement zone centered around $`B_x=0`$ widens even more and pushes the entanglement maxima away to higher and higher values of $`|B_x|`$. The highest value of the tangle tends more and more towards orthogonal fields (c.f. Figs. 5, 6). The preferred angle traverses from $`\theta =0`$ at zero temperature (Fig. 4) to $`\theta =\pi /2`$ at $`TJ`$ (Fig. 6). In the classical limit, i.e. at very high temperatures all entanglement fades away as expected, because the state is completely mixed.

We can use the two-level approximation to get an estimate of the angle creating maximal entanglement. Let us first estimate the ground state energy, $`ϵ`$. Since we know that the lowest two energy levels are very close and the first excited state is $`2J`$, we can use the approximation $`2J+ϵ4J`$ while solving for eigenvalues of the Hamiltonian (19). The ground state energy is then

$$ϵ=2J\frac{4B_x^2}{4J^2B_z^2}J.$$
(21)
For the above approximation to hold, we must operate in a region not too close to the poles at $`B_z=\pm 2J`$. This gives the following energy difference between the two lowest levels

$$\mathrm{\Delta }ϵ=2Jϵ\frac{4B_x^2}{4J^2B_z^2}J.$$
(22)
The two terms of the ground state energy (21) can be considered as the first two terms in a Taylor expansion. This suggests that we instead write

$$ϵ=2J\sqrt{1+\frac{\mathrm{\Delta }ϵ}{J}}=2J\sqrt{1+\frac{4B_x^2}{4J^2B_z^2}}.$$
(23)
Let us, from here onwards, measure all energies in units of $`J`$, i.e. let $`J=1`$. For a magnetic field only in the $`x`$ direction, the concurrence of the ground state is $`C_0=\tau ^{1/2}=2J/ϵ`$, where $`\tau `$ is given by Eq. (6). For non-zero $`B_z`$ this formula remains an excellent approximation (as we have verified numerically). Substituting Eq. (23) for $`ϵ`$ gives

$$C_0=\frac{1}{\sqrt{1+\mathrm{\Delta }ϵ}}.$$
(24)
Recall that the first excited state is $`|\mathrm{\Psi }^{}`$ with concurrence $`C_1=1`$. From the concurrence mixing theorem (11) we get an approximation of the thermal concurrence. If $`w_i`$ are weights following Maxwell-Boltzmann statistics, then the maximum entanglement is reached when the following condition holds:

$$T(1+e^{\mathrm{\Delta }ϵ/T})=2(1+\mathrm{\Delta }ϵ+\sqrt{1+\mathrm{\Delta }ϵ}).$$
(25)
In the region we are interested in, where temperature is not bigger than $`20\%`$ of the coupling constant, $`J`$, the temperature is also much smaller than $`\mathrm{\Delta }ϵ`$, and Eq. (25) can be further simplified to

$$\mathrm{\Delta }ϵ=T\mathrm{ln}\frac{4}{T}.$$
(26)
Remember that the ground state energy is still a function of the magnetic field. In order to fix the temperature, $`\mathrm{\Delta }ϵ`$ has to be fixed, i.e. maximum entanglement is reached in the cross section between the energy surface and the constant energy plane that follows from Eq. (26). From Eq. (22) it is clear that this is described by an ellipse in a $`B_xB_z`$-plane. Using the field amplitude $`B`$ as a parameter, the angle we defined in Eq. (20) is given by

$$\mathrm{sin}\theta ^{}=\pm \sqrt{\frac{\mathrm{\Delta }ϵ}{4\mathrm{\Delta }ϵ}\frac{4B^2}{B^2}},$$
(27)
assuming that the parameter $`|B|>\sqrt{ϵ}`$.

Another way to parameterize the optimum line is to let $`B_z`$ be the parameter and solve for $`B_x`$,

$$B_x=\pm \sqrt{\mathrm{\Delta }ϵ\left(1\frac{B_z^2}{4}\right)},$$
(28)
with $`|B_z|<2`$. Again keep in mind that Eqs. (27) and (28) follow from the assumption that $`\mathrm{\Delta }ϵ0`$, and therefore the ellipse is not closed around the poles at $`B_z=\pm 2`$ (*cf* Figs. 5, 7).

## V Qubit rings

As the expressions for the thermal tangle of the general two-qubit case are already quite complicated, we can not expect to find any easily manageable analytic expressions in the many-qubit case. Instead, we have performed numerical simulations, which gives the entanglement between neighboring qubits as shown in Fig. 7.

The behavior for even $`N`$ rings is quite similar to that of the two qubit case. To understand why there is an extra low entanglement zone around $`B_z=0`$ in the case of odd $`N`$ rings, one has to go back the basic cause for entanglement arising in the Ising chain. It results from the competition between the term $`\widehat{\sigma }_z\widehat{\sigma }_z+B_z\widehat{\sigma }_z`$ trying to impose spin order in the $`z`$ direction and $`B_x\widehat{\sigma }_x`$ trying to impose spin order in the $`x`$ direction. In the odd qubit case, it is impossible for all neighboring spins to be oriented oppositely, so the ordering power of $`\widehat{\sigma }_z\widehat{\sigma }_z`$ is significantly reduced. In such circumstances, it is mainly the competition between $`B_z\widehat{\sigma }_z`$ and $`B_x\widehat{\sigma }_x`$ (albeit aided by the small $`\widehat{\sigma }_z\widehat{\sigma }_z`$ interaction) which determines the entanglement. Thus the high entanglement values near $`B_z=0`$ present for the two qubit (and all other even $`N`$) cases disappear for odd $`N`$. Note also that the entanglement in the odd $`N`$ case is somewhat larger in magnitude compared with the even $`N`$ case. This is a result of the fact that the two terms $`\widehat{\sigma }_z\widehat{\sigma }_z`$ and $`B_z\widehat{\sigma }_z`$ compete for the type of $`z`$ ordering (parallel or anti-parallel neighboring spins). In even $`N`$ case, this competition is much stronger and this tends to lower the entanglement by reducing the net effect of $`z`$ ordering terms with respect to $`x`$ ordering terms. As the number $`N`$ of qubits in the chain is increased, the difference between even and odd $`N`$ chains should disappear (because for large $`N`$, adding or removing an extra qubit from the chain should not make a significant difference). This effect is clearly seen in Fig. 7 where the difference in appearance between the plots for $`N=3`$ and $`N=4`$ is much greater than that between $`N=5`$ and $`N=6`$.

Entanglement can also be calculated between non-neighboring qubits with the results shown in Fig. 8 for next-nearest neighbors. Again we observe that the even $`N`$ case has lower entanglement on average than the odd $`N`$ case. Also in the odd qubit case, the entanglement between next-nearest neighbors is somewhat complementary to that between nearest neighbors (this can be seen for example by placing the plots for $`N=5`$ in the two cases on top of each other). Thus the amount of entanglement between pairs of nearest neighbors and pairs of next-nearest neighbors can be controlled by varying the field direction.

## VI Conclusions

In this paper we have investigated the natural thermal entanglement arising in an Ising ring with a magnetic field in an arbitrary direction. We have investigated two qubit analytically and three through seven qubits numerically. One of the most interesting results is the fact that for a given temperature, the (nearest neighbor, pairwise) entanglement in the ring can be maximized by rotating the magnetic field (at fixed magnitude) to an optimal direction. This can be regarded as magnetically induced entanglement. The pairwise entanglement between next-nearest neighbors can be maximized by rotating the field to a different direction. We have also proved a theorem of mixing of concurrences which is applicable to any system in which the pure states in the mixture have no spin-flip overlap.

So far we have have only considered pairwise entanglement. In future work we will estimate the entanglement between three or more qubits in the ring and also focus on investigating ways to detect the natural entanglement in Ising models, and on investigation of the entanglement in the large variety of available condensed matter models of interacting systems.

###### Acknowledgements.

This work was funded by the UK Engineering and Physical Sciences Research Council and the European Union Project EQUIP (contract IST-1999-11053).


format: text

text:
# Separation of spin and charge in paired spin-singlet quantum Hall states

(February 5, 2001)

## Abstract

We propose a series of paired spin-singlet quantum Hall states, which exhibit a separation of spin and charge degrees of freedom. The fundamental excitations over these states, which have filling fraction $`\nu =\frac{2}{2m+1}`$ with $`m`$ an odd integer, are spinons (spin-$`\frac{1}{2}`$ and charge zero) or fractional holons (charge $`\pm \frac{1}{2m+1}`$ and spin zero). The braid statistics of these excitations are non-abelian. The mechanism for the separation of spin and charge in these states is topological: spin and charge excitations are liberated by binding to a vortex in a $`p`$-wave pairing condensate. We briefly discuss related, abelian spin-singlet states and possible transitions.

Strongly correlated electrons in low dimensional systems are known to exhibit physical phenomena that are surprising and, at first sight, counterintuitive. Among these is the remarkable phenomenon of quantum number fractionalization: elementary excitations in strongly interacting many-electron systems can have quantum numbers (for spin and charge) that are fractions of those of the electron. This fractionalization can take the form of a separation of spin and charge, or of a fractionalization of the electric charge of the electron.

In $`D=1`$ spatial dimension, the separation of spin and charge is well understood. It is seen in explicit solutions of specific integrable model systems (Hubbard and supersymmetric $`t`$-$`J`$ models). The general framework of the Luttinger Liquid has made it clear that in 1+1 dimensions the separation of spin and charge is a generic feature, which does not require any fine tuning of the interactions among the electrons.

In spatial dimensions $`D=2`$ or higher, spin and charge tend to confine and a separation of the two is only possible under very special conditions. It has been proposed that the key feature underlying the anomalous behavior of the cuprate high-$`T_c`$ materials is precisely a separation of spin and charge And , and concrete scenarios, based on $`𝐙_2`$ or $`U(1)`$ gauge theories, have been put forward spch .

In this paper, we focus on the quantum Hall (qH) regime, which is relevant for $`2D`$ electrons in strong magnetic fields, and for rotating Bose-Einstein condensates WG . In particular, we discuss the separation of spin and charge in the qH regime. Specifically, we propose a series of paired spin-singlet qH states, of filling fraction $`\nu =\frac{2}{2m+1}`$, which are generalizations of the Moore-Read or pfaffian states for spin polarized electrons. The fundamental excitations over these states are spinons (with spin $`\frac{1}{2}`$ and zero charge) and holons (with zero spin and fractional charge $`\pm \frac{1}{2m+1}`$, in units of the charge of the electron). The braid statistics of these excitations are non-abelian, and thereby the paired spin-singlet states fall in the category of ‘non-abelian qH states’.

It is important to stress that the more conventional ‘abelian’ spin-singlet qH states (such as the Halperin states with label $`(m+1,m+1,m)`$, see below) do not exhibit a separation of spin and charge. The excitations over such states are conveniently analyzed in terms of a ‘spin-charge decomposition’ MR ; BF ; MiR  but this is subject to certain gluing conditions (expressing locality of the excitation w.r.t. the electrons), which exclude single spinons or holons from the (bulk) physical spectrum. The essential feature that liberates spin and charge in the paired states proposed here is the presence of the pairing condensate: by binding to a vortex in the pairing condensate, the spin and charge excitations become local with respect to the electrons in the ground state, and they can propagate independently.

It is illustrative to compare the separation of spin and charge in the paired spin-singlet states with the fractionalization of charge in paired, so-called $`q`$-pfaffian, spin polarized states. For the $`q`$-pfaffian states, Laughlin’s gauge argument gives that the adiabatic insertion of a single flux quantum will produce an excitation of charge $`\frac{1}{q}`$. However, as in the case of BCS superconductors, the presence of the pairing condensate leads to a reduction of the elementary flux quantum by a factor of $`2`$, and thereby the unit-flux Laughlin quasi-particles are separated into two constituents each carrying a charge $`\frac{1}{2q}`$. In a similar way, conventional quasiparticles (carrying spin and charge) over a paired spin-singlet state are separated into spinons and holons.

Before we present the paired spin-singlet states, we briefly recall some facts about spin-singlet states and paired states in the qH regime. Despite the presence of strong magnetic fields in the qH regime, there is experimental motivation to study states that are not (fully) spin polarized (see e.g. Eis ). In many qH systems, the energy scale for the Zeeman splitting is relatively low, and it can be further suppressed by the application of hydrostatic pressure. Using this technique, combined with a tilted field technique, spin transitions in the qH regime can be studied Kang . The simplest qH states that are singlets w.r.t. the $`SU(2)`$ spin symmetry are the Halperin states Halp

$`\stackrel{~}{\mathrm{\Psi }}_{\mathrm{SS}}^{(m+1,m+1,m)}(z_1^{},\mathrm{},z_N^{};z_1^{},\mathrm{},z_N^{})=`$
$`\mathrm{\Pi }_{i<j}(z_i^{}z_j^{})^{m+1}\mathrm{\Pi }_{i<j}(z_i^{}z_j^{})^{m+1}\mathrm{\Pi }_{i,j}(z_i^{}z_j^{})^m,`$
where $`z_i^{}`$ and $`z_i^{}`$ are the coordinates of the spin up and spin down electrons, respectively, and $`m`$ is an even integer. The state Eq. (Separation of spin and charge in paired spin-singlet quantum Hall states) has filling fraction $`\nu =2/(2m+1)`$. Here and below we display reduced qH wave functions $`\stackrel{~}{\mathrm{\Psi }}(x)`$, which are related to the actual wave functions $`\mathrm{\Psi }(x)`$ via $`\mathrm{\Psi }(x)=\stackrel{~}{\mathrm{\Psi }}(x)\mathrm{exp}(_i\frac{|x_i|^2}{4l^2})`$ with $`x_i=z_i^{},z_i^{}`$ and $`l=\sqrt{\frac{\mathrm{}c}{eB}}`$ the magnetic length. Hierarchies of more general (abelian) spin-singlet states were studied in Rez ; WDJ ; LF ; MiR .

In a 1991 paper, Moore and Read introduced the notion of a paired qH state and discussed the so-called $`q`$-pfaffian states at filling $`\nu =\frac{1}{q}`$ (with $`q`$ even) MR . It is believed that this state (with $`q=2`$) is at the origin of the observed qH plateau at filling fraction $`\nu =\frac{5}{2}`$ (see Read  for a recent review). The wave function for the $`q`$-pfaffian is given by

$$\stackrel{~}{\mathrm{\Psi }}_{\mathrm{pf}}^{(q)}(z_1,\mathrm{},z_N)=\mathrm{Pf}\left(\frac{1}{z_iz_j}\right)\underset{i<j}{}(z_iz_j)^q,$$
(2)
where the pfaffian factor for an antisymmetric matrix $`M_{ij}`$ is defined as $`\mathrm{Pf}(M_{ij})=𝒜_{i\mathrm{even}}M_{i1,i}`$, with $`𝒜`$ denoting anti-symmetrization. In ARRS , the pfaffian states were generalized to a series of non-abelian spin-singlet (NASS) states, at filling $`\nu =\frac{4}{4M+3}`$ with $`M`$ an odd integer. These states exhibit a pairing of like spins. The excitations over these NASS states have non-abelian statistics, but there is no separation of spin and charge.

In the paired spin-singlet states that we propose here, the pairing takes place in the charge sector, irrespective of the spin of the electrons. This leads to a wave function

$`\stackrel{~}{\mathrm{\Psi }}_{\mathrm{paired}}^{(m)}(z_1^{},\mathrm{},z_N^{};z_1^{},\mathrm{},z_N^{})=`$ (3)
$`\mathrm{Pf}\left({\displaystyle \frac{1}{x_ix_j}}\right)\stackrel{~}{\mathrm{\Psi }}_{\mathrm{SS}}^{(m+1,m+1,m)}(z_i^{};z_j^{}),`$
where $`x_l=z_i^{},z_j^{}`$, $`m`$ is now an odd integer and the filling fraction is $`\nu =\frac{2}{2m+1}`$. There exists a hamiltonian for which this state is the unique ground state Rezpri . One way to study the excitations over this state is by using this hamiltonian. Here we will proceed by analyzing the state Eq. (3) and its excitations using an associated conformal field theory (CFT).

Following the CFT-qH correspondence outlined in MR , one quickly finds that the CFT associated to the (bosonic) paired spin-singlet state at $`m=0`$ is the (chiral) CFT based on the affine Kac-Moody algebra $`SO(5)_1`$. For this algebra, the eight currents associated to the roots of $`SO(5)`$ can be written in terms of spin and charge bosons $`\phi _{s,c}`$ and a Majorana fermion $`\psi `$. \[The assignment of spin and charge quantum numbers to the weights and roots of $`SO(5)`$ is indicated in fig. 1.\] For general $`m`$, the ‘condensate’ operators $`\mathrm{\Psi }`$ and $`\mathrm{\Delta }`$ are obtained from these currents by the substitution $`\phi _c\sqrt{2m+1}\phi _c`$,

$`\mathrm{\Psi }^\alpha =\psi e^{i\sqrt{\frac{2m+1}{2}}\phi _c\pm \frac{i}{\sqrt{2}}\phi _s},\overline{\mathrm{\Psi }}^\alpha =\psi e^{i\sqrt{\frac{2m+1}{2}}\phi _c\pm \frac{i}{\sqrt{2}}\phi _s}`$
$`\mathrm{\Delta }_c=e^{i\sqrt{4m+2}\phi _c},\overline{\mathrm{\Delta }}_c=e^{i\sqrt{4m+2}\phi _c},\mathrm{\Delta }_s^A=e^{\pm i\sqrt{2}\phi _s},`$
(4)
with $`\alpha =,`$ referring to the spin eigenvalue $`s_z=\pm \frac{1}{2}`$ and $`A=,`$. The quantum numbers $`q`$ (charge) and $`s_z`$ are measured by the operators $`Q=i\sqrt{\frac{2}{2m+1}}\frac{dz}{2\pi i}\phi _c`$ and $`S_z=\frac{i}{\sqrt{2}}\frac{dz}{2\pi i}\phi _s`$. The wave function Eq. (3) is obtained as a correlator of $`N`$ spin-up electrons $`\mathrm{\Psi }^{}`$ and $`N`$ spin-down electrons $`\mathrm{\Psi }^{}`$, together with a neutralizing background charge. The CFT description makes it easy to identify the fundamental (quasi-particle) excitations. For $`m=0`$ they are the operators that generate the spinor (4-dimensional) representation of the $`SO(5)_1`$ current algebra. For general $`m`$ these become

$$\varphi _c=\sigma e^{\frac{i}{\sqrt{4m+2}}\phi _c},\overline{\varphi }_c=\sigma e^{\frac{i}{\sqrt{4m+2}}\phi _c},\varphi _s^\alpha =\sigma e^{\pm \frac{i}{\sqrt{2}}\phi _s},$$
(5)
where $`\sigma (z)`$ is the so-called spin field associated to the Majorana (Ising) fermion $`\psi (z)`$. Higher excitations, such as those constituting the vector representation, can be generated by bringing together two or more of the fundamental excitations. The expressions Eq. (5) show that the fundamental excitations can be characterized as spinons $`\varphi _s^\alpha `$ (spin-$`\frac{1}{2}`$ but no charge) and holons $`\varphi _c`$, $`\overline{\varphi }_c`$ (of charge $`\pm \frac{1}{2m+1}`$ and zero spin).

To illustrate the separation of spin and charge, we present explicit wave functions for excited states. We first consider an abelian excitation, with spin down ($`s_z=\frac{1}{2}`$) and charge $`\frac{1}{2m+1}`$, at location $`w`$. Its wave function takes the familiar form

$$\underset{i}{}(z_i^{}w)\stackrel{~}{\mathrm{\Psi }}_{\mathrm{paired}}^{(m)}.$$
(6)
The important observation is now that, starting from this wave function, one can separate the locations of the spin and charge parts of this excitation, creating a spinon at position $`w_s`$ and a holon at $`w_c`$. In the corresponding wave function, the pfaffian factor in Eq. (3) is replaced by (compare with MR )

$$\mathrm{Pf}\left(\frac{\mathrm{\Phi }(x_i,x_j;w_c,w_s)}{x_ix_j}\right)\underset{i}{}(x_iw_c)^{1/2}\frac{_i(z_i^{}w_s)^{1/2}}{_j(z_j^{}w_s)^{1/2}},$$
(7)
where

$$\mathrm{\Phi }(x_i,x_j;w_c,w_s)=\left(\frac{x_iw_c}{x_jw_c}\frac{x_jw_s}{x_iw_s}\right)^{1/2}+ij.$$
(8)
That (7) in fact defines a well-behaved electronic wave function can be seen by noting that it is identical to

$$\frac{1}{_j(z_j^{}w_s)}\mathrm{Pf}\left(\frac{(x_iw_c)(x_jw_s)+ij}{x_ix_j}\right).$$
(9)
In the limit where $`w_s,w_cw`$, spin and charge recombine and the wave function reduces to Eq. (6). Note that the factor $`_j(z_j^{}w_s)^1`$ should be regularized and projected onto the lowest Landau level in the same way as the wave functions for quasi particles over the Laughlin states Laugh .

The charge of the holon excitation equals $`\frac{1}{2}\mathrm{\Phi }_0\sigma _H`$ (with $`\mathrm{\Phi }_0=\frac{h}{e}`$ the flux quantum), showing that the creation of a single holon involves the insertion of a half-quantum of magnetic flux, which is the canonical flux quantum in the presence of a pairing condensate. This flux insertion is accompanied by a vortex in the pairing condensate, and this brings in the factor $`\sigma (z)`$ in the expressions Eq. (5). The role of the vortices in this discussion is similar to the role of visons in the Senthil-Fisher theory SF .

An important feature that is implied by the presence of spin-fields $`\sigma (z)`$ in the expressions Eq. (5) for the spinons and holons, is that the braid statistics of these excitations will be non-abelian. This feature is analogous to the non-abelian statistics of the charge $`\frac{1}{2q}`$ excitations over the (spin-polarized) $`q`$-pfaffian state, and we refer to the literature for a discussion MR ; RR ; NW .

It is well-known that the $`q`$-pfaffian spin-polarized state is closely related to two abelian states at filling $`\nu =\frac{1}{q}`$: the two-layer $`(q+1,q+1,q1)`$ state and a strong pairing state which is a Laughlin state of strongly paired electrons. Possible transitions among these three states have been discussed in the literature (see e.g. NW ; RG ; Wen ). In the spin-singlet situation, we may similarly identify two series of abelian spin-singlet states at $`\nu =\frac{2}{2m+1}`$ that allow for a transition into the pfaffian spin-singlet state Eq. (3): a two-layer state associated to $`SO(6)`$ and a strong pairing state. The wave function for the two-layer state reads

$`\stackrel{~}{\mathrm{\Psi }}_{2\mathrm{layer}}^{(m)}(\{z_i^t,z_i^t,z_i^b,z_i^b\})=`$ (10)
$`\mathrm{\Pi }_{i<j}(z_i^tz_j^t)^{m+2}\mathrm{\Pi }_{i<j}(z_i^tz_j^t)^{m+2}`$
$`\mathrm{\Pi }_{i<j}(z_i^bz_j^b)^{m+2}\mathrm{\Pi }_{i<j}(z_i^bz_j^b)^{m+2}`$
$`\mathrm{\Pi }_{i,j}(z_i^tz_j^t)^{m+1}\mathrm{\Pi }_{i,j}(z_i^bz_j^b)^{m+1}\mathrm{\Pi }_{i,j}(z_i^tz_j^b)^m`$
$`\mathrm{\Pi }_{i,j}(z_i^tz_j^b)^m\mathrm{\Pi }_{i,j}(z_i^tz_j^b)^{m1}\mathrm{\Pi }_{i,j}(z_i^tz_j^b)^{m1}`$
where the indices $`t,b`$ refer to the top and bottom layers. This wave function arises as a correlator of two-layer spinful electron operators which, in the case $`m=0`$, generate an $`SO(6)_1`$ affine Kac-Moody algebra.

The strong pairing state is an abelian state of strongly bound pairs with quantum numbers $`(q=2,s_z=0)`$ and $`(q=0,s_z=1)`$, which are the operators $`\mathrm{\Delta }_c`$ and $`\mathrm{\Delta }_s^{}`$ in fig. 1. Spin and charge are decoupled from the start, and (putting $`m=0`$) we can associate to this state the symmetry $`SO(4)SU(2)_s\times SU(2)_c`$.

There are various ways to understand and describe possible transitions among the three types of paired spin-singlet states at $`\nu =\frac{2}{2m+1}`$. Such transitions are expected when electrons in the two-layer state are subjected to increasing interlayer interactions. A useful framework is that of $`K`$-matrices describing the topological order of the various states Wen1 . \[For this discussion, we refer to the states via their associated $`SO(6)`$, $`SO(5)`$ or $`SO(4)`$ symmetries.\] For the $`SO(6)`$ states, the naive $`K`$-matrix for the four electron operators $`(,t)`$, $`(,t)`$, $`(,b)`$, $`(,b)`$ is singular. After a reduction to three independent condensate operators we find the following ‘qH data’

$`𝐊_e=\left(\begin{array}{ccc}m+2& m& 2m+1\\ m& m+2& 2m+1\\ 2m+1& 2m+1& 4m+2\end{array}\right)`$ (14)
$`𝐪_e=(1,1,2),𝐬_e=(,,0),𝐥_e=(t,b,),`$
where $`𝐪_e`$, $`𝐬_e`$ and $`𝐥_e`$ specify the charge, spin and layer index for an appropriate basis of ‘electron’ operators, which build the qH condensate. By applying a duality transformation ($`𝐊_\varphi =𝐊_e^1`$, $`𝐪_\varphi =𝐊_\varphi 𝐪_e`$, etc.) one obtains the topological data for a basis of quasi-hole excitations Wen1 ; ABGS .

Starting from this characterization of the topological order in the $`SO(6)`$ state, the topological order of the $`SO(5)`$ and $`SO(4)`$ states can be obtained in a systematic manner ABGS ; Wen . For the $`SO(5)`$ state, the resulting description employs a so-called pseudo-particle whose role it is to account for the degeneracies that are associated to the non-abelian braid statistics. Choosing $`\mathrm{\Psi }^{}`$, $`\mathrm{\Delta }_s^{}`$ and $`\mathrm{\Delta }_c`$ as the fundamental condensate operators, we find

$`𝐊_e=\left(\begin{array}{ccc}m+2& 1& 2m+1\\ 1& 2& 0\\ 2m+1& 0& 4m+2\end{array}\right),\begin{array}{c}𝐪_e=(1,0,2)\hfill \\ 𝐬_e=(,,0)\hfill \end{array}`$ (20)
$`𝐊_\varphi =\left(\begin{array}{ccc}1& \frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{3}{4}& \frac{1}{4}\\ \frac{1}{2}& \frac{1}{4}& \frac{2m+3}{8m+4}\end{array}\right),\begin{array}{c}𝐪_\varphi =(0,0,\frac{1}{2m+1})\hfill \\ 𝐬_\varphi =(0,,0)\hfill \end{array}`$ (26)
It is the first particle in the $`\varphi `$-sector that is interpreted as a pseudo-particle, the other two have quantum numbers corresponding to $`\varphi _s^{}`$ and $`\overline{\varphi }_c`$. The matrix $`𝐊_\varphi `$ is of a general form first proposed in GSBCR ; for the interpretation of $`K`$-matrices for non-abelian qH states we refer to ABGS . We remark that the ground state degeneracy on the torus is not simply given by $`|\mathrm{det}𝐊_e|`$, as is the case for abelian qH states; the actual value here is $`3(2m+1)`$.

A further reduction leads to the following qH data for the strong pairing $`SO(4)`$ state (the data for the $`\varphi `$ sector is obtained by the duality mentioned above)

$$𝐊_e=\left(\begin{array}{cc}2& 0\\ 0& 4m+2\end{array}\right),𝐪_e=(0,2),𝐬_e=(,0).$$
(27)
This same set of qH data can be obtained by starting from the $`SO(6)`$ data Eq. (LABEL:eq:so6qHdata) and condensing quasiparticle-quasihole pairs, following ref. Wen .

The simplest filling fraction where the paired spin-singlet states that we propose are possible is $`\nu =\frac{2}{3}`$. At that same filling fraction, there exists an abelian spin-singlet state, described by composite fermions with anti-parallel flux attachment WDJ . To distinguish the different states, one may consider the exponents for various tunneling processes. For the paired spin-singlet state the scaling dimensions for electrons, holons and spinons are $`g_{\mathrm{el}}=m+2`$, $`g_{\mathrm{hol}}=\frac{2m+5}{16m+8}`$, and $`g_{\mathrm{sp}}=\frac{5}{8}`$, respectively. Thus, for tunneling through the bulk, the holon is the most relevant particle (for $`m1`$), while the $`IV`$ for tunneling electrons from a Fermi-liquid into the edge is $`IV^{g_e}=V^{m+2}`$. According to LF2 , the scaling dimensions for the composite fermion spin-singlet state at $`\nu =\frac{2}{3}`$ are $`g_{\mathrm{el}}=2`$, $`g_{\mathrm{qp}}=\frac{2}{3}`$. They give rise to a quadratic $`IV`$ for electron tunneling, in contrast to the cubic $`IV`$ for the paired state. Another way to distinguish the two states is via the spin-Hall conductance, which has opposite sign as compared to the ordinary Hall conductance for the abelian state. For the paired spin-singlet state both conductances have the same sign.

There are two ways in which the paired state Eq. (3) can be relevant in a double-layer geometry. First, as already mentioned, there is the possibility of a transition from a double-layer state for spin-full electrons, Eq. (LABEL:eq:so6), into a single-layer paired state. A second possibility is a realization of the paired state as a double-layer state for spin-polarized electrons, with the layer index playing the role of the spin-index.

As is the case for the pfaffian and the NASS states, these states can be generalized to states which show clustering instead of pairing. Starting from an $`SO(5)_k`$ symmetry structure, one derives states that allow clusters of up to $`2k`$ particles of equal spin, with filling fractions given by $`\nu =\frac{2k}{2km+1}`$.

This research is supported in part by the Foundation FOM of the Netherlands and by the Netherlands Organization for Scientific Research (NWO). A.W.W.L. acknowledges the Institute for Theoretical Physics at the University of Amsterdam for hospitality. His research is supported by NSF under Grant DMR-00-75064.


text:
# Quantum fingerprinting

## 1 Introduction

Fingerprinting can be a useful mechanism for determining if two strings are the same: each string is associated with a much shorter fingerprint and comparisons between strings are made in terms of their fingerprints alone. This can lead to savings in the communication and storage of information.

The notion of fingerprinting arises naturally in the setting of communication complexity (see \[KN97\]). The particular model of communication complexity that we consider in this paper is called the simultaneous message passing model, which was introduced by Yao \[Yao79\] in his original paper on communication complexity. In this model, two parties—Alice and Bob—receive inputs $`x`$ and $`y`$, respectively, and are not permitted to communicate with one another directly. Rather they each send a message to a third party, called the referee, who determines the output of the protocol based solely on the messages sent by Alice and Bob. The collective goal of the three parties is to cause the protocol to output the correct value of some function $`f(x,y)`$ while minimizing the amount of information that Alice and Bob send to the referee.

For the equality problem, the function is simply

$$f(x,y)=\{\begin{array}{cc}1\hfill & \text{if }x=y\hfill \\ 0\hfill & \text{if }xy\text{.}\hfill \end{array}$$

The problem can of course be trivially solved if Alice sends $`x`$ and Bob sends $`y`$ to the referee, who can then simply compute $`f(x,y)`$. However, the cost of this protocol is high; if $`x`$ and $`y`$ are $`n`$-bit strings, then a total of $`2n`$ bits are communicated. If Alice and Bob instead send fingerprints of $`x`$ and $`y`$, which may each be considerably shorter than $`x`$ and $`y`$, the cost can be reduced significantly. The question we are interested in is how much the size of the fingerprints can be reduced.

If Alice and Bob share a random $`O(\mathrm{log}n)`$-bit key then the fingerprints need only be of constant length if we allow a small probability of error; a brief sketch of this follows. A binary error-correcting code is used, which can be represented as a function $`E:\{0,1\}^n\{0,1\}^m`$, where $`E(x)`$ is the codeword associated with $`x\{0,1\}^n`$. There exist error-correcting codes (Justesen codes, for instance) with $`m=cn`$ such that the Hamming distance between any two distinct codewords $`E(x)`$ and $`E(y)`$ (with $`xy`$) is at least $`(1\delta )m`$, where $`c`$ and $`\delta `$ are constants. For the particular case of Justesen codes, we may choose any $`c>2`$ and we will have $`\delta <9/10+1/(15c)`$ (assuming $`n`$ is sufficiently large). For further information on Justesen codes, see Justesen \[Jus72\] and MacWilliams and Sloane \[MS77, Chapter 10\]. Now, for $`x\{0,1\}^n`$ and $`i\{1,2,\mathrm{},m\}`$, let $`E_i(x)`$ denote the $`i^{\text{th}}`$ bit of $`E(x)`$. The shared key is a random $`i\{1,2,\mathrm{},m\}`$ (which consists of $`\mathrm{log}(m)\mathrm{log}(n)+O(1)`$ bits). Alice and Bob respectively send the bits $`E_i(x)`$ and $`E_i(y)`$ to the referee, who then outputs 1 if and only if $`E_i(x)=E_i(y)`$. If $`x=y`$ then $`E_i(x)=E_i(y)`$, so then the outcome is correct. If $`xy`$ then the probability that $`E_i(x)=E_i(y)`$ is at most $`\delta `$, so the outcome is correct with probability $`1\delta `$. The error probability can be reduced from $`\delta `$ to any $`\epsilon >0`$ by having Alice and Bob send $`O(\mathrm{log}(1/\epsilon ))`$ independent random bits of the codewords $`E(x)`$ and $`E(y)`$ to the referee. In this case, the length of each fingerprint is $`O(\mathrm{log}(1/\epsilon ))`$ bits.

One disadvantage of the above scheme is that it requires overhead in creating and maintaining a shared key. Moreover, once the key is distributed, it must be stored securely until the inputs are obtained. This is because an adversary who knows the value of the key can easily choose inputs $`x`$ and $`y`$ such that $`xy`$ but for which the output of the protocol always indicates that $`x=y`$.

Yao \[Yao79, Section 4.D\] posed as an open problem the question of what happens in this model if Alice and Bob do not have a shared key. Ambainis \[Amb96\] proved that fingerprints of $`O(\sqrt{n})`$ bits suffice if we allow a small error probability (see also \[KNR95, NS96, BK97\]). Note that in this setting Alice and Bob still have access to random bits, but their random bits may not be correlated. Subsequently, Newman and Szegedy \[NS96\] proved a matching lower bound of $`\mathrm{\Omega }(\sqrt{n})`$. Their result was generalized by Babai and Kimmel \[BK97\] to the result that the randomized and deterministic complexity can be at most quadratically far apart for any function in this model. Babai and Kimmel attribute a simplified proof of this fact to Bourgain and Wigderson.

We shall consider the problem where there is no shared key (or entanglement) between Alice and Bob, but the fingerprints can consist of quantum information. In Section 2, we show that $`O(\mathrm{log}n)`$-qubit fingerprints are sufficient to solve the equality problem in this setting—an exponential improvement over the $`\sqrt{n}`$-bound for the comparable classical case. Our method is to set the $`2^n`$ fingerprints to quantum states whose pairwise inner-products are bounded below 1 in absolute value and to use a test that identifies identical fingerprints and distinguishes distinct fingerprints with good probability. (It is possible to take the fingerprints to be nearly pairwise orthogonal, although the bound on the absolute value of the inner product between pairs of states is not directly related to the error probability of the fingerprinting method.) This gives a simultaneous message passing protocol for equality in the obvious way: Alice and Bob send the fingerprints of their respective inputs to the referee, who then executes the test to check if the fingerprints are equal or distinct. In Section 2, we also show that the fingerprints must consist of at least $`\mathrm{\Omega }(\mathrm{log}n)`$ qubits if the error probability is bounded below 1.

In Sections 3 and 4, we consider possible improvements to the efficiency of the fingerprinting methods of Section 2. In Section 3, we investigate the number of qubits required to contain $`2^n`$ fingerprints with pairwise inner product bounded in absolute value by any $`\delta <1`$. In Section 4, we consider the efficiency of tests that distinguish between $`k`$ copies of pairs of indentical states and $`k`$ copies of pairs of states whose inner product is bounded in absolute value by any $`\delta <1`$.

Finally, in Section 5 we consider a variation of fingerprinting with a shared quantum key, consisting of $`O(\mathrm{log}n)`$ shared Bell states (EPR-pairs). We observe that results in \[BCT99\] imply that errorless (i.e., exact) fingerprinting is possible with $`O(\mathrm{log}n)`$-bit classical fingerprints in a particular context where achieving the same performance with only a classical shared key requires fingerprints of length $`\mathrm{\Omega }(n)`$.

We assume the reader is familiar with the basic notions of quantum computation and quantum information—for further information we refer the reader to the book by Nielsen and Chuang \[NC00\].

## 2 Quantum fingerprinting without shared keys

In this section, we show how to solve the equality problem in the simultaneous message passing model with logarithmic-length quantum fingerprints in a context where no shared key is available. The solution is quite simple and the fingerprints are exponentially shorter than in the comparable classical setting, where $`\mathrm{\Theta }(\sqrt{n})`$ bit fingerprints are necessary and sufficient (see the references in the introduction). The method that we present is based on classical error-correcting codes, though in a different manner than discussed in Section 1 since no shared key is available.

Assume that for fixed $`c>1`$ and $`\delta <1`$ we have an error correcting code $`E:\{0,1\}^n\{0,1\}^m`$ for each $`n`$, where $`m=cn`$ and such that the distance between distinct codewords $`E(x)`$ and $`E(y)`$ is at least $`(1\delta )m`$. As mentioned in Section 1, a reasonable first choice of such codes are Justesen codes, which give $`\delta <9/10+1/(15c)`$ for any chosen $`c>2`$. Now, for any choice of $`n`$, we define the $`(\mathrm{log}(m)+1)`$-qubit state $`|h_x`$ as

$$|h_x=\frac{1}{\sqrt{m}}\underset{i=1}{\overset{m}{}}|i|E_i(x)$$
(1)
for each $`x\{0,1\}^n`$. Since two distinct codewords can be equal in at most $`\delta m`$ positions, for any $`xy`$ we have $`h_x|h_y\delta m/m=\delta `$. Thus we have $`2^n`$ different $`(\mathrm{log}(n)+O(1))`$-qubit states, and each pair of them has inner product at most $`\delta `$.

The simultaneous message passing protocol for the equality problem works as follows. When given $`n`$-bit inputs $`x`$ and $`y`$, respectively, Alice and Bob send fingerprints $`|h_x`$ and $`|h_y`$ to the referee. Then the referee must distinguish between the case where the two states received—call them $`|\varphi `$ and $`|\psi `$—are identical or have inner product at most $`\delta `$. This is accomplished with one-sided error probability by the procedure that measures and outputs the first qubit of the state

$$(HI)(\text{c-SWAP})(HI)|0|\varphi |\psi .$$

Here $`H`$ is the Hadamard transform, which maps $`|b\frac{1}{\sqrt{2}}(|0+(1)^b|1)`$, SWAP is the operation $`|\varphi |\psi |\psi |\varphi `$ and c-SWAP is the controlled-SWAP (controlled by the first qubit). The circuit for this procedure is illustrated in Figure 1.

By tracing through the execution of this circuit, one can determine that the final state before the measurement is

$$\frac{1}{2}|0(|\varphi |\psi +|\psi |\varphi )+\frac{1}{2}|1(|\varphi |\psi |\psi |\varphi ).$$

Measuring the first qubit of this state produces outcome 1 with probability $`\frac{1}{2}\frac{1}{2}|\varphi |\psi |^2`$. This probability is 0 if $`x=y`$ and is at least $`\frac{1}{2}(1\delta ^2)>0`$ if $`xy`$. Thus, the test determines which case holds with one-sided error $`\frac{1}{2}(1+\delta ^2)`$.

The error probability of the test can be reduced to any $`\epsilon >0`$ by setting the fingerprint of $`x\{0,1\}^n`$ to $`|h_x^k`$ for a suitable $`kO(\mathrm{log}(1/\epsilon ))`$. From such fingerprints, the referee can independently perform the test in Figure 1 $`k`$ times, resulting in an error probability below $`\epsilon `$. In this case, the length of each fingerprint is $`O((\mathrm{log}n)(\mathrm{log}(1/\epsilon ))`$.

It is worth considering what goes wrong if one tries to simulate the above quantum protocol using classical mixtures in place of quantum superpositions. In such a protocol, Alice and Bob send $`(i,E_i(x))`$ and $`(j,E_j(y))`$ respectively to the referee for independent random uniformly distributed $`i,j\{1,2,\mathrm{},m\}`$. If it should happen that $`i=j`$ then the referee can make a statistical inference about whether or not $`x=y`$. But $`i=j`$ occurs with probability only $`O(1/n)`$—and the ability of the referee to make an inference when $`ij`$ seems difficult. For many error-correcting codes, no inference whatsoever about $`x=y`$ is possible when $`ij`$ and the lower bound in \[NS96\] implies that no error-correcting code enables inferences to be made when $`ij`$ with error probability bounded below 1. The distinguishing test in Figure 1 can be viewed as a quantum operation which has no analogous classical probabilistic counterpart.

Our quantum protocol for equality in the simultaneous message model uses $`O(\mathrm{log}n)`$-qubit fingerprints for any constant error probability. Is it possible to use fewer qubits? In fact, without a shared key, $`\mathrm{\Omega }(\mathrm{log}n)`$-qubit fingerprints are necessary. This is because any $`k`$-qubit quantum state can be specified within exponential precision with $`O(k2^k)`$ classical bits. Therefore the existence of a $`k`$-qubit quantum protocol implies the existence of an $`O(k2^k)`$-bit (deterministic) classical protocol. From this we can infer that $`k\mathrm{\Omega }(\mathrm{log}n)`$.

## 3 Sets of pairwise-distinguishable states in low-dimensional spaces

In Section 2, we employed a particular classical error-correcting code to construct a set of $`2^n`$ quantum states with pairwise inner products below $`\delta `$ in absolute value. Here, we consider the question of how few qubits are sufficient for this to be accomplished for an arbitrarily small $`\delta >0`$. We show that $`\mathrm{log}n+O(\mathrm{log}(1/\delta ))`$ qubits are sufficient. While this gives somewhat better bounds than the Justesen codes discussed in Section 2, unfortunately we only have a nonconstructive proof of this fact. The proof follows.

Suppose $`d\frac{4n}{\delta ^2\mathrm{log}e}`$. Then we claim there are $`2^n`$ unit vectors in $`^d`$ with pairwise inner product at most $`\delta `$ in absolute value. Consider two random vectors in $`v,w`$ in $`\{+1,1\}^d/\sqrt{d}`$. Suppose $`v`$ and $`w`$ agree in $`d^{}`$ coordinates and disagree in $`dd^{}`$ coordinates, then their inner product is $`v|w=(2d^{}d)/d`$. Using a Chernoff bound \[AS92, Corollary A.2\] we have

$$\mathrm{Pr}[|v|w|>\delta ]=\mathrm{Pr}[|2d^{}d|>\delta d]2e^{\delta ^2d/2}.$$

Now pick a set $`S`$ of $`2^n`$ random vectors from $`\{+1,1\}^d/\sqrt{d}`$. The probability that there are distinct $`v,wS`$ with large inner product is upper bounded by

$`\mathrm{Pr}[\text{ distinct }v,wS\text{ with }|v|w|>\delta ]`$ $``$ $`{\displaystyle \underset{\text{distinct }v,wS}{}}\mathrm{Pr}[|v|w|>\delta ]`$
$`<`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{2^n}{2}}\right)2e^{\delta ^2d/2}<2^{2n\delta ^2d\mathrm{log}e/2}.`$
If $`d4n/\delta ^2\mathrm{log}e`$ then this probability is $`<1`$, which implies the existence of a set $`S`$ of $`2^n`$ vectors having the right properties.

By associating $`\{0,1\}^n`$ with the $`2^n`$ vectors above, we obtain fingerprints of $`\mathrm{log}(4n/\delta ^2\mathrm{log}e)\mathrm{log}n+O(\mathrm{log}(1/\delta ))`$ qubits for any $`\delta >0`$.

Up to constant factors, the nonconstructive method above is optimal in the following sense. Let $`\delta 2^n`$. Then an assignment of $`b`$-qubit states to all $`n`$-bit strings such that the absolute value of the inner product between any two fingerprints is at most $`\delta `$, requires $`b\mathrm{\Omega }(\mathrm{log}(n/\delta ))`$ qubits. In order to demonstrate this, we will prove and then combine two lower bounds on $`b`$.

Firstly, the states can be used as fingerprints to solve the equality problem of communication complexity with bounded-error probability in one round of communication (Alice sends the fingerprint of her input $`x`$ to Bob, who compares it with the fingerprint of his $`y`$). Therefore the known lower bound for equality implies $`bc\mathrm{log}n`$ for some $`c>0`$.

Secondly, pick a set of $`a=1/\delta `$ different fingerprints. These are complex unit vectors $`v_1,\mathrm{},v_a`$ of dimension $`2^b`$, whose pairwise inner products are at most $`\delta `$ in absolute value. Let $`A`$ be the $`a\times 2^b`$ matrix having the conjugated vectors $`v_i`$ as rows and let $`B`$ be the $`2^b\times a`$ matrix having the $`v_i`$ as columns. Consider the $`a\times a`$ matrix $`C=AB`$. Its $`i,j`$ entry is $`C_{ij}=v_i|v_j`$, so the diagonal entries of $`C`$ are 1, the off-diagonal entries are at most $`\delta `$ in absolute value. This means that $`C`$ is strictly diagonally dominant: $`C_{ii}=1>(a1)\delta _{ji}|C_{ij}|`$ for all $`i`$. It is known that such a matrix has full rank \[HJ85, Theorem 6.1.10.a\]. This implies that the $`a`$ vectors $`v_1,\mathrm{},v_a`$ are linearly independent and hence must have dimension at least $`a`$. Thus $`1/\delta =a2^b`$, hence $`b\mathrm{log}(1/\delta )`$.

Since both lower bounds on $`b`$ hold simultaneously, we have

$$b\mathrm{max}\{c\mathrm{log}n,\mathrm{log}(1/\delta )\}\frac{c\mathrm{log}n+\mathrm{log}(1/\delta )}{2}\mathrm{\Omega }(\mathrm{log}(n/\delta )).$$

It should be noted that having small inner product $`\delta `$ is desirable but not all-important. For instance, there is a trade-off between $`\delta `$ and the number of copies of each state sent by Alice and Bob in the simultaneous message passing protocol for equality from the previous section in terms of the total number of qubits communicated and the resulting error bound.

## 4 The state distinguishing problem

Motivated by the fingerprinting scheme of Section 2, we define the state distinguishing problem as follows. The input consists of $`k`$ copies of each of two quantum states $`|\varphi `$ and $`|\psi `$ with a promise that the two states are either identical or have inner product bounded in absolute value by some given $`\delta <1`$. The goal is to distinguish between the two cases with as high probability as possible.

One method for solving this problem is to use the method in Section 2, independently performing the test in Figure 1 $`k`$ times, resulting in an error probability of 0 in the identical case and $`(\frac{1+\delta ^2}{2})^k`$ otherwise. We will describe an improved method, whose error probability is approximately $`\sqrt{\pi k}(\frac{1+\delta }{2})^{2k}`$ (which is almost a quadratic reduction when $`\delta `$ is small). We also show that this is nearly optimal by proving a lower bound of $`\frac{1}{4}(\frac{1+\delta }{2})^{2k}`$ on the error probability.

The improved method for the state distinguishing problem uses registers $`R_1,\mathrm{},R_{2k}`$, which initially contain $`|\varphi ,\mathrm{},|\varphi ,|\psi ,\mathrm{},|\psi `$ ($`k`$ copies of each). It also uses a register $`P`$ whose classical states include encodings of all the permutations in $`S_{2k}`$. Let $`0`$ denote the identity permutation and let $`P`$ be initialized to $`0`$. Let $`F`$ be any transformation satisfying

$$F:|0\frac{1}{\sqrt{(2k)!}}\underset{\sigma S_{2k}}{}|\sigma .$$

Such a transformation can easily be computed in polynomial time.

The distinguishing procedure operates as follows:

1. Apply $`F`$ to register $`P`$.
2. Apply a conditional permutation on the contents of registers $`R_1,\mathrm{},R_{2k}`$, conditioned on the permutation specified in $`P`$.
3. Apply $`F^{}`$ to $`P`$ and measure the final state. If $`P`$ contains $`0`$ then answer equal, otherwise answer not equal.

The state after is Step 2 is

$$\frac{1}{\sqrt{(2k)!}}\underset{\sigma S_{2k}}{}|\sigma \sigma (|\varphi \mathrm{}|\varphi |\psi \mathrm{}|\psi )$$

(where $`\sigma (|\varphi \mathrm{}|\varphi |\psi \mathrm{}|\psi )`$ means we permute the contents of the $`2k`$ registers according to $`\sigma `$).

Case 1: $`|\varphi =|\psi `$. In this case the permutation of the registers does absolutely nothing, so the procedure answers equal with certainty.

Case 2: Assume $`|\varphi |\psi |<\delta `$. The probability of answering equal is the squared norm of the vector obtained by applying the projection $`|00|I`$ to the final state, which is

$`p_{eq}`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{(2k)!}}}{\displaystyle \underset{\sigma S_{2k}}{}}0|F^{}|\sigma \sigma (|\varphi \mathrm{}|\varphi |\psi \mathrm{}|\psi )^2`$
$`=`$ $`{\displaystyle \frac{1}{(2k)!}}{\displaystyle \underset{\sigma S_{2k}}{}}\sigma (|\varphi \mathrm{}|\varphi |\psi \mathrm{}|\psi )^2.`$
Since $`|\eta ^2=\eta |\eta `$ for any $`|\eta `$ we may simplify this probability as follows:

$`p_{eq}`$ $`=`$ $`{\displaystyle \frac{1}{((2k)!)^2}}{\displaystyle \underset{\sigma ,\tau S_{2k}}{}}\sigma (\varphi |\mathrm{}\varphi |\psi |\mathrm{}\psi |)\tau (|\varphi \mathrm{}|\varphi |\psi \mathrm{}|\psi )`$
$`=`$ $`{\displaystyle \frac{1}{((2k)!)^2}}{\displaystyle \underset{\sigma ,\tau S_{2k}}{}}\varphi |\mathrm{}\varphi |\psi |\mathrm{}\psi |\sigma ^1\tau (|\varphi \mathrm{}|\varphi |\psi \mathrm{}|\psi )`$
$`=`$ $`{\displaystyle \frac{1}{(2k)!}}{\displaystyle \underset{\sigma S_{2k}}{}}\varphi |\mathrm{}\varphi |\psi |\mathrm{}\psi |\sigma (|\varphi \mathrm{}|\varphi |\psi \mathrm{}|\psi )`$
$`=`$ $`{\displaystyle \frac{(k!)^2}{(2k)!}}{\displaystyle \underset{j=0}{\overset{k}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j}}\right)^2\delta ^{2j}`$
$``$ $`{\displaystyle \frac{(k!)^2}{(2k)!}}\left(1+\delta \right)^{2k}.`$
The sum of binomial coefficients arises by grouping the permutations $`\sigma `$ according to the number of registers $`j`$ in the set $`\{R_1,\mathrm{},R_k\}`$ that $`\sigma `$ causes to contain $`|\psi `$. We therefore have $`p_{eq}\sqrt{\pi k}(\frac{1+\delta }{2})^{2k}`$.

We now show that the error probability cannot be less than $`\frac{1}{4}(\frac{1+\delta }{2})^{2k}`$ for the state distinguishing problem.<sup>1</sup><sup>1</sup>1Note that this lower bound concerns a problem that is slightly more general than the problem of distinguishing fingerprints, because the fingerprints used in Section 2 are not arbitrary but come from a known set of only $`2^n`$ states. Consider an optimal state distinguisher that acts on $`k`$ copies of $`|\varphi `$ and $`k`$ copies of $`|\psi `$ where either $`|\varphi =|\psi `$ or $`|\varphi |\psi |\delta `$. Let $`|\varphi _1=|\psi _1=|0`$, and let $`|\varphi _2=\mathrm{cos}(\frac{\theta }{2})|0+\mathrm{sin}(\frac{\theta }{2})|1`$ and $`|\psi _2=\mathrm{cos}(\frac{\theta }{2})|0\mathrm{sin}(\frac{\theta }{2})|1`$, where $`\theta =\mathrm{cos}^1(\delta )`$. Clearly, $`|\varphi _1=|\psi _1`$ and $`\varphi _2|\psi _2=\delta `$. A state distinguisher must distinguish between the state $`|a=|\varphi _1^k|\psi _1^k`$ and the state $`|b=|\varphi _2^k|\psi _2^k`$. We now consider the probability with which a state distinguisher can distinguish between these states. Since $`\varphi _1|\varphi _2=\psi _1|\psi _2=\mathrm{cos}(\frac{\theta }{2})`$, it follows that $`a|b=\mathrm{cos}^{2k}(\frac{\theta }{2})=(\frac{1+\mathrm{cos}\theta }{2})^k=(\frac{1+\delta }{2})^k`$. Now, it is known that the optimal procedure distinguishing between two states with inner product $`\mathrm{cos}\alpha `$ has error probability $`\frac{1\mathrm{sin}\alpha }{2}\frac{1}{4}\mathrm{cos}^2\alpha `$. (This follows from an early result of Helstrom \[Hel67\], which was later strengthened by Fuchs \[Fuc95, Section 3.2\]. A clean and self-contained derivation of this result may also be found in \[Pre00\].) Therefore, the state distinguisher must have error probability at least $`\frac{1}{4}(\frac{1+\delta }{2})^{2k}`$.

## 5 Errorless fingerprinting using a shared quantum key

Finally, we consider briefly the case of fingerprinting where Alice and Bob have a shared quantum key, consisting of $`O(\mathrm{log}n)`$ Bell states, but are required to output classical strings as fingerprints. Is there any sense in which a quantum key can result in improved performance over the case of a classical key? We observe that results in \[BCT99\] imply an improvement in the particular setting where the fingerprinting scheme must be exact (i.e., the error probability is 0) and where there is a restriction on the inputs that either $`x=y`$ or the Hamming distance between $`x`$ and $`y`$ is $`n/2`$ (and $`n`$ is divisible by 4).

Under this restriction, any classical scheme with a shared key would still require fingerprints of length $`\mathrm{\Omega }(n)`$. On the other hand, there is a scheme with a shared quantum key of $`O(\mathrm{log}n)`$ Bell states that requires fingerprints of length only $`O(\mathrm{log}n)`$ bits. See \[BCT99\] for details (the results are partly based on results in \[BCW98, FR87\]). It should be noted that if the exactness condition is relaxed to one where the error probability must be $`O(1/n^c)`$ (for a constant $`c`$) then there exists also a classical scheme with classical keys and fingerprints of length $`O(\mathrm{log}n)`$.

### Acknowledgments

We thank John Preskill for references to the literature about optimally distinguishing between quantum states, and Andris Ambainis for information about the origins of the classical $`O(\sqrt{n})`$-bit fingerprinting scheme. Some of this research took place while R.C. was at the CWI and while H.B. and R.C. were at Caltech, and the hospitality of these institutions is gratefully acknowledged.