text:
# Role of Coulomb correlation on magnetic and transport properties of doped manganites: La0.5Sr0.5MnO3 and LaSr2Mn2O7

## 1 Introduction

The half-doped manganites, La0.5Sr0.5MnO3 and LaSr2Mn2O7, belong to the Ruddlesden-Popper family , (R,A)n+1MnnO3n+1, which has been attracting intensive interest due to itinerant doped carriers that give rise to a variety of interesting physical phenomena, notably colossal magnetoresistance. One of the most striking properties of the double layered manganites, La2-2xSr1+2xMn2O7, is the extremely large magnetoresistance which is much larger than that for prototypical perovskite systems: it was found in 40 % doped La2-2xSr1+2xMn2O7 that the resistivity ratio reaches $``$ 20,000 % at 7 T above Tc , whereas for La0.6Sr0.4MnO3 $`\rho (0)/\rho (H)`$ 200 % at 15 T . The main difference between 3D perovskite and 2D layered compounds arises from the change of dimensionality (n) of the crystal structure connected with the number of MnO6 layers along the $`c`$ direction (n=$`\mathrm{}`$ for pseudocubic perovskite systems and n=2 for double layered manganites), which in turn has a strong influence on their magnetic and transport properties . Measurements and comparison of characteristic features (e.g., the strong anisotropy of electrical (magneto-) transport and magnetostriction, and the 2D character of magnetism caused by reduction of the exchange coupling between the Mn ions along the $`c`$ direction in the double-layered manganites) suggested that both the anisotropic transfer interaction and the two dimensional spin correlation have a strong influence on the CMR properties in layered manganites .

The pseudocubic perovskites, La1-xSrxMnO3, have an insulating paramagnetic phase at high temperature and a metallic ferromagnetic phase at low temperature over a wide range of hole doping . The strong coupling between the magnetic ordering and the electrical conductivity demonstrates the strong relationship between the electrical resistivity and the spin alignment which has been explaind by the double-exchange mechanism arising from the mixed valence of Mn3+/Mn4+. In comparison to these pseudocubic perovskites, the double layered structures (La2-2xSr1+2xMn2O7) with their two-dimensional networks of MnO6 octahedra have a reduced exchange coupling between the Mn ions along the c direction. Indeed, in the double-layered case consisting of two perovskite blocks separated by an intervening insulating layer of (La,Sr)O ions along the c axis, the balance between antiferromagnetism and ferromagnetism is very sensitive to $`e_g`$ band filling . Bilayer La2-2xSr1+2xMn2O7 demonstrates ferromagnetism in a doping range $`x<0.39`$, a canted antiferromagnetic structure for a hole concentration $`0.39<x<0.48`$, and layered antiferromagnetic states for $`x>0.48`$ .

An important issue in the theory of CMR oxides is the role of Coulomb correlation since an accurate treatment of correlation may affect significantly the balance between ferromagnetic and antiferromagnetic interactions and hence the magnetic ground state. According to our previous investigations , where we demonstrated that the on-site Coulomb correlation of Mn d electrons significantly modifies the electronic structure, magnetic ordering, interlayered exchange interactions and promotes strong electronic transport anisotropy in 50 % doped LaSr2Mn2O7, the experimentally observed magnetic ordering is reproduced within LSDA+U calculations only for U$``$7 eV. This is in contrast with the CMR perovskite 3D manganites (LaMnO3, (La,Sr)MnO3 systems) where LSDA theory correctly predicts the magnetic ground state .

Considering two 50 % doped manganites, the double layered LaSr2Mn2O7 and pseudocubic perovskite La0.5Sr0.5MnO3, we outline here the main similarities and differences in their characteristic properties: (i) Both manganites formally consist of Mn3.5+ ions surrounded by oxygen octahedra, and so in a high spin configuration the majority $`t_{2g}`$ states are filled and the electrically active orbitals are $`d_{x^2y^2}`$ and $`d_{3z^2r^2}`$. (ii) The dynamical Jahn-Teller (JT) effect is absent for both systems, $`\mathrm{\Delta }_{JT}=D(MnO_{apical})/D(MnO_{planar})`$, where $`D(MnO)`$ is manganese oxygen distance, equals to 1.004 and 1.001 for La0.5Sr0.5MnO3 and LaSr2Mn2O7, respectively – although it should be noted here that due to an intervening layer of (La.Sr)O ions along the $`c`$ axis in the latter manganite, its MnO6 octahedra are slightly distorted in terms of different distances between Mn and apical oxygens. Hence, in contrast to the 3D perovskite manganites which have two types of oxygen atoms (one apical and one planar), there are three oxygen types in the double layered manganites – two apical and one planar. (iii) The resistivity of La0.5Sr0.5MnO3 is of the order of 10$`{}_{}{}^{3}\mathrm{\Omega }cm`$ with a flat temperature dependence , whereas for LaSr2Mn2O7 the $`ab`$-plane resistivity is 100–10$`{}_{}{}^{1}\mathrm{\Omega }cm`$  and the resistivity perpendicular to the layer is $``$102 times larger; in addition, according to previous theoretical works  both are half-metals. (iv) They have different magnetic orderings: La0.5Sr0.5MnO3 is a ferromagnet (FM), while LaSr2Mn2O7 is an A-type antiferromagnet (AFM) (magnetic moments lie in the $`ab`$ plane and couple ferromagnetically within the single MnO2 layer, but show AFM order between layers). (v) As mentioned above, the different influence of the on-site Coulomb correlation on the magnetic ordering in these manganites has been established in the previous calculations.

In this paper, on the basis of comprehensive analyses of the crystal structures, electronic structures and magnetic configurations of the double layered LaSr2Mn2O7 and pseudocubic perovskite La0.5Sr0.5MnO3 compounds, we establish the mechanisms governing the band formation in these manganites and the different role of the on-site Coulomb correlation in its relation with the electronic, magnetic and transport properties. For both compounds, we consider the total energy differences between FM and AFM spin configurations for the Coulomb correlation parameter, U, equal to 0 and 7 eV; then, for the ground states of these manganites, we compare the exchange interaction parameters and the most important band characteristics (such as the population of Mn-d states near the Fermi level, Mn-d sub-band widths and the p-d hybridization) and give a possible reason why the LSDA scheme (U=0) fails to predict the magnetic ground state as well as the electrical transport properties for the double layered manganite, in contrast to its success for the case of the pseudocubic perovskite manganite.

## 2 Methodology

The LSDA and LSDA+U calculations were performed in the frame-work of the linear-muffin-tin-orbital method in the atomic sphere approximation (LMTO-ASA) . We used the von Barth-Hedin-Janak form  for the exchange-correlation potential. The crystal parameters were taken from Ref. . From the constrained LSDA supercell calculations , we obtained values of the Coulomb and exchange parameters to be U=7.1 eV and J=0.79 eV for La0.5Sr0.5MnO3 and U=7.2 eV and J=0.78 eV for LaSr2Mn2O7. These values are typical for the transition-metal oxides .

## 3 Results and Discussion

### 3.1 Electronic structure, transport anisotropy and magnetism

As a first step, we performed the band structure calculations of the FM (all atoms in every layer and between layers are ordered ferromagnetically) and the A-type AFM (ferromagnetic layers stacked antiferromagnetically) phases of both La0.5Sr0.5MnO3 and LaSr2Mn2O7 by the standard LSDA method. FM spin alignment is found to be more preferable from total energy calculations for both manganites (Table 1). The projected densities of states (DOS) for these FM cases look very similar (Fig. 1): For the majority-spin channel, Mn 3d states of both compounds form the bands between 2.2 eV below EF and 2.5 eV above EF. As seen from the figure, the $`e_g`$ ($`x^2y^2`$ and $`3z^2r^2`$) bands are partially filled, cross EF, and are rather broad compared to the $`t_{2g}`$ ($`xy`$ and degenerate $`xz`$, $`yz`$) bands which are about 1.2 eV wide and lie 1 eV below EF. The exchange interaction splits the Mn 3d states such that the $`t_{2g}`$ and $`e_g`$ minority-spin bands are located 2.6 eV higher in energy than the majority-spin states. We obtained a band gap in the minority-spin $`d`$ bands of around 2.5 eV for both La0.5Sr0.5MnO3 and LaSr2Mn2O7 – in keeping with the fact that doped perovskite manganites are found to be half-metallic . The analogs in the main band characteristics near EF in the calculated electronic spectra of the double layered and doped perovskite manganites allow us to suggest that the insulating character of minority-spin electrons for the double-layered manganite may also render the conduction band a half-metallic one (i.e., 100 % spin polarization for the conduction electrons). Note that $`E_F`$ in our spin-polarized band structure calculations of the double-layered manganite was found to lie at the bottom of the $`t_{2g}`$ minority spin conduction band (which is in agreement with the full-potential LMTO calculations for LaSr2Mn2O7 ), and so the LSDA electronic band structure just misses to being half-metallic.

The crucial role of Coulomb correlation in the stability of the experimentally observed magnetic ground state of LaSr2Mn2O7 was established in Ref. . We investigated the electronic structure similarities of LaSr2Mn2O7 and La0.5Sr0.5MnO3 for both FM and A-type AFM spin alignments in the frame-work of the LSDA+U method with the calculated U value of 7 eV. According to the total energy differences in Table 1, the ground state of the perovskite manganite remains ferromagnetic, while the observed A-type AFM ordering in double layered manganite is found to be energetically more favorable with U=7 eV. (A possible reason for the LSDA failure for the case of the double layered manganite in contrast to the perovskite will be discussed later). A comparison of the projected DOS’s for the LSDA+U ground states of La0.5Sr0.5MnO3 (solid line) and LaSr2Mn2O7 (dashed line) is shown in Fig. 2. Only majority spin $`e_g`$ states contribute to the DOS at EF. We find the magnetic moment of the primitive unit cell to be equal to 7.00 $`\mu _B`$. Thus, LSDA+U calculations result in a truly half-metallic state for the double layered manganite, and so electron conduction is possible only within the majority spin sublattice.

One of the main differences between the doped pseudocubic perovskite and double layered manganites which is clearly seen from Fig. 2, is the different behavior of the electrically active states when on-site Coulomb correlation is taken into account. The DOSs for the LaSr2Mn2O7 $`e_g`$ states demonstrate (Fig. 2) the significant difference between $`3z^2r^2`$ and $`x^2y^2`$ orbitals in the electron population near $`E_F`$, while for La0.5Sr0.5MnO3 the band widths and the position of the band centers of these two $`e_g`$ orbitals as well as their contributions to the DOS at $`E_F`$ are very close (Fig. 2).

In Table 1 we presented the ratio between the $`x^2y^2`$ and $`3z^2r^2`$ contributions to the DOS at EF (denoted as N$`_{x^2y^2}`$/N$`_{3z^2r^2}`$) calculated in both the LSDA and LSDA+U approaches. The ratio demonstrates the presence of anisotropy in the population of the two $`e_g`$ states at EF; and since the situation does not change qualitativly in the 0.3 eV energy window just above EF (Fig. 2), we draw the following conclusions in the picture of charge transport: For La0.5Sr0.5MnO3, we have 3D conduction; the use of U=7 eV does not result in a large splitting of the $`e_g`$ states and the number of electrons that contribute to electrical transport remain almost insensitive to the influence of U. This is contrary to that in LaSr2Mn2O7 where for U=7 eV the electron conduction (hopping) along the $`c`$ axis (N$`_{3z^2r^2}`$) becomes very small and thus, on-site correlation treated within LSDA+U promotes 2D type (in-plane) electronic behavior in the double layered system — as observed experimentally. Thus, the comparison of the LSDA and LSDA+U band structures for both manganites leads us to the following conclusion: the exchange splitting with almost unoccupied minority spin Mn-3d states and the ligand field splitting of the $`t_{2g}`$ and $`e_g`$ states are the main factors governing band formation in both La0.5Sr0.5MnO3 and LaSr2Mn2O7. However, futher splitting of the $`e_g`$ states with increase of U is an essential feature of the layered manganites, but is absent in La0.5Sr0.5MnO3.

The total energy differences for the two manganites for U=0 and 7 eV shown in Table 1 (where the total energy of the FM spin ordering for each U value is taken to be zero) demonstrate that for the double layered compound the on-site Mn-d electron Coulomb correlations modify the magnetic ordering from FM to A-type AFM – as experimentally observed, while the FM ground state of the pseudocubic perovskite remains energetically more preferred as U is increased. To determine the character of the exchange coupling in these manganites, we calculated the effective exchange interaction parameters (for computational details see ). In Table 1, the values of the d-d effective exchange parameters, $`J_{dd}`$, between nearest Mn neighbours which belong to the different layers of one bilayer are shown for both U values. As seen from the Table, they follow the magnetic ordering behavior (obtained by the total energy differences between FM and AFM configurations) for both compounds. (For more details of the change of the exchange interaction parameters and the FM-AFM total energy differences in LaSr2Mn2O7 with the increase of U, see Ref. .)

We interpreted the calculated exchange coupling within the superexchange (SEX) and double exchange (DEX) models by calculating the $`e_g`$-sub-band widths of the manganite ground states. As can be seen from Table 1, where we present the ratio of the $`x^2y^2`$ and $`3z^2r^2`$ band widths (denoted as W$`_{x^2y^2}`$/W$`_{3z^2r^2}`$), for La0.5Sr0.5MnO3 the $`e_g`$-band widths stay exactly equal with increase of U, and provide positive DEX interactions. We note here, that the increase of the ferromagnetic contributions to the exchange interaction energy (c.f., Table 1) may be due to the increase of the $`e_g`$-band widths from 3.4 eV for U=0 to 3.8 eV for U=7 eV and the stronger O-p hybridization in the Mn-d states – as will be illustrated below. In LaSr2Mn2O7, a sharp increase of the W$`_{x^2y^2}`$/W$`_{3z^2r^2}`$ ratio coming from the narrowing of the $`3z^2r^2`$ band width (Table 1 and Fig. 2) results in the strong splitting of these two $`e_g`$-sub-bands and so promotes the negative (AFM) contribution to the exchange interaction. Thus, Coulomb correlations have a very different influence on pseudocubic and double layered manganites: for the first we obtain an increase of the DEX contributions, while for LaSr2Mn2O7, U supresseses the DEX contributions to the interlayer exchange interaction energy and produces the change in magnetic ordering from FM to AFM.

### 3.2 Significance of p-d hybridization

The degree of O-p hybridization with Mn-d states plays an important role in the band structure and on the exchange mechanism . We compared below the p-d hybridization of La0.5Sr0.5MnO3 and LaSr2Mn2O7 for U=0 and 7 eV by calculating the O-p contributions to the DOS at the energy windows of corresponding Mn-d states. And the comparison gives interesting differences between double layered and perovskite manganites, supporting the results on magnetic and transport properties we have already discussed above.

According to the qualitative picture of the simple DEX model, an electrically active electron has a finite hopping probability (t) between ferromagnetically ordered Mn ions, but this hopping vanishes in the case of antiferromagnetic spin alignment due to strong Hund coupling (t$`<<`$J). The character of the occupied $`e_g`$ orbitals, which affects transport and magnetic properties, has been established above, but it is also important to investigate the role of oxygen hybridization in the $`e_g`$ and $`t_{2g}`$ orbitals as well .

At first, we shall consider a significance of oxygen p-hybridization in the electrically active $`e_g`$ orbitals. For both manganite compounds, two $`e_g`$ ($`3z^2r^2`$ and $`x^2y^2`$) and $`p_x`$, $`p_y`$, $`p_z`$ oxygen states contribute to the DOS at $`E_F`$. In Table 1, we present the percentage of these contributions for unit cells consisting of two Mn atoms for both compounds. As expected, only $`p_z`$ orbitals of apical oxygens ($`p_x`$, $`p_y`$ of planar oxygens) hybridize with “out-of-plane” $`3z^2r^2`$ (“in-plane” $`x^2y^2`$) d-orbitals. Comparing the lowest spin configurations within LSDA and LSDA+U (as obtained by total energy differences), we draw the following conclusions: for ferromagnetic La0.5Sr0.5MnO3, we have significant contributions to the DOS at EF from both apical and planar oxygens, and the on-site Coulomb correlation resulting in a redistribution of the conduction electrons between $`e_g`$ and p-states, do not change the 3D character of the hopping matrix (Table 1). The influence of U on the population picture at EF in LaSr2Mn2O7 is very different. Established above sharp decrease of the N$`_{3z^2r^2}`$ for U=7 eV occurs together with vanishing apical oxygen contributions at EF (Table 1) resulting in suppression by U the $`c`$ axis transport. This leads to the superexchange antiferromagnetic coupling along the $`c`$ axis – as was obtained by calculating the interlayer exchange interaction parameters (Table 1). In contrast, a sharp increase of the $`p_x`$ ($`p_y`$) hybridization in the $`x^2y^2`$ orbital (due to the charge redistribution) provides strong DEX ferromagnetic interactions in the $`ab`$-plane.

Investigation of the oxygen contributions to the DOS at EF allowed us to draw conclusions on the transport and exchange properties in La0.5Sr0.5MnO3 and LaSr2Mn2O7. Overlapping of Mn-$`t_{2g}`$ and O-p orbitals in these manganites is an essential factor governing their band formation. In order to compare the p- and d-band overlaps for the perovskite and double layered compounds, we should, first of all, compare Mn-O distances for these systems. The distances between Mn and apical and planar oxygens in La0.5Sr0.5MnO3 are 1.941 and 1.934 Å, respectively; for the double layred manganite they are $``$0.01 Å smaller than for the perovskite compound: 1.917 (1.940) Å for Mn and apical oxygens and 1.927 Å for Mn and planar oxygen distances. Such a negligible difference in Mn-O distances serves to stress our results below.

In Fig. 3, we present the calculated angular electron density distribution in the energy window of corresponding majority spin $`t_{2g}`$ states for both manganites. As seen from the figure, the hybridization between Mn-d $`t_{2g}`$ and O-p states for La0.5Sr0.5MnO3 exists for both U=0 and 7 eV, becoming stronger as U is increased (Fig. 3(a) and 3(b)). The same result was obtained for undoped LaMnO3 , in which, however, strong Jahn-Teller distortions of MnO6 octahedra lead to more than two times larger oxygen contributions to $`t_{2g}`$ Mn states than that for La0.5Sr0.5MnO3. In contrast to these perovskites, and despite the almost equal Mn-O distances in the doped manganites, LSDA band structure calculations for LaSr2Mn2O7 gave O-p contributions to the DOS at the energy windows corresponding to $`t_{2g}`$ states that are almost negligible (Fig. 3(c)). The p-d hybridization for the double layered manganite is correctly described only treated in LSDA+U (Fig. 3(d)): it becomes very strong between Mn and planar oxygens and one of the apical atoms, O1 (which lies between Mn-layers of one MnO6 bilayer unit), while it is supressed for apical O2 atoms which belong to the (La,Sr) insulating layer as well. Thus, we believe that the absence p-d hybridization as an important ingredient in the band formation picture results in the failure of the LSDA scheme in predicting observed magnetic and transport properties of the double layered manganite.

The lowered dimensionality of the magnetic interactions in the double layered system, which was established under the influence of the on-site Coulomb correlation, is also seen from a comparison of two LSDA+U cases for La0.5Sr0.5MnO3 and LaSr2Mn2O7 (Fig. 3(b) and 3(d)): in the 3D-compound, we have equal contributions to the DOS from all p-states ($`p_x`$, $`p_y`$ and $`p_z`$) of planar oxygens, while for the double layered manganite only $`p_x`$($`p_y`$) states of the planar oxygens give significant contributions to the DOS at the energy window corresponding to Mn-d $`t_{2g}`$ states. In addition, the absence of the hybridization between Mn-d states and apical O2-p states (this oxygen lies at the boundary of the perovskite-type bilayer) makes the whole hybridization picture obtained for the double layered LaSr2Mn2O7 for U=7 eV (Fig. 3(d)) to be in a very good agreement with the structural peculiarity of this compound - namely the existance of two perovskite-type layers separated by a rock-salt-type layer (La,Sr)2O2.

## 4 Summary

In summary, the calculated electronic band structure, exchange interaction parameters, transport properties and p-d hybridization of the double layered LaSr2Mn2O7 are significantly modified under on-site Coulomb correlation U, resulting in the observed magnetic ground state and transport anisotropy. The comparison with the band characteristics of the 3D perovskite La0.5Sr0.5MnO3 sets these similar doped manganites apart by means of different role of the Coulomb correlation on magnetism and transport properties.

Work at Northwestern University supported by the U.S. Department of Energy (grant No. DE-F602-88ER45372) and at Institute of Metal Physics supported by RFFI (grant No. 01-02-17063).


format: text

text:
# Age Estimates for Globular Clusters in NGC 1399

## 1 Introduction

The metal-rich and metal-poor Globular Clusters (GCs) in our Galaxy, are thought to be both very old, i.e. $``$13 Gyrs (e.g. Carretta et al. 2000) and enhanced in $`\alpha `$ elements, i.e. \[$`\alpha `$/Fe\] $``$ +0.3 (Carney 1996). However the amount, and even the existence of a relative age difference between these two subpopulations is a matter of current debate.

Giant ellipticals also reveal two subpopulations of GCs (e.g. Larsen et al. 2001), with mean metallicities similar to those seen in spirals (Forbes, Brodie & Larsen 2001). Very little is currently known about the ages and abundance ratios of such GCs. The spectroscopic (Kissler-Patig et al. 1998; Cohen et al. 1998; Beasley et al. 2000) and recent photometric (Puzia et al. 1999; Kundu et al. 1999) studies suggest that both subpopulations are very old but the red (metal-rich) GCs could be up to as much as 5 Gyrs younger than the blue (metal-poor) ones. Abundance ratios for GCs in the giant ellipticals studied to date are consistent with Galactic GCs but individual errors are large. In the case of the merger remnant NGC 7252, Maraston et al. (2001) found GCs that had both young ($``$ 1 Gyr) ages and solar abundance ratios. Accurate measurements of individual GC ages and abundance ratios in elliptical galaxies will provide key constraints on the possible GC formation mechanisms (Ashman & Zepf 1992; Forbes, Brodie & Grillmair 1997).

In our previous spectroscopic study of NGC 1399 we obtained spectra of 18 GCs with the LRIS spectrograph on the Keck telescope (Kissler-Patig et al. 1998). These spectra indicated that the two subpopulations were old and coeval within the errors (i.e. $`\pm `$ 0.5 Å in H$`\beta `$ Lick line index). Such errors were too large to clearly distinguish a relative age difference between the two subpopulations but they were generally consistent with old ages similar to those found in the Milky Way GC system. We also identified two metal-rich GCs with potentially super-solar abundance ratios.

Here we present higher S/N spectra (i.e. errors on H$`\beta `$ are about $`\pm `$ 0.25 Å ) for 10 GCs. These data are perhaps the highest quality spectra published for GCs beyond the Local Group and are comparable to the best spectra in the literature for M31 (Huchra et al. 1996) and Milky Way GCs (Trager et al. 2000). Errors in spectral line indices have a huge impact on our ability to estimate GC ages. For our previous dataset these errors translated into a relative age uncertainty of about $`\pm `$ 10 Gyrs for a 15 Gyr old GC. The data presented here have a corresponding error of $`\pm `$ 5 Gyrs. This allows us to better estimate the relative age of individual GCs and in particular identify GCs with young inferred ages in a giant elliptical galaxy for the first time. Here we confirm that the metal-poor GCs have \[Fe/H\] $``$ –1.5 and are very old. We also identify two metal-rich GCs with super-solar abundance ratios (i.e. \[$`\alpha `$/Fe\] $`>`$ 0) – such ratios are generally unexpected in late epoch mergers of spiral disks (Goudfrooij et al. 2001).

## 2 Observations and Data Reduction

Candidate GCs were selected from the list of Grillmair (1992) and observed on 1997 Sept. 30th and Oct. 1st using the LRIS spectrograph (Oke et al. 1995) on the Keck I telescope. The observational setup was the same as used by Kissler-Patig et al. (1998) except integrations were longer at 13,200 sec. The 600 l/mm grating gave a resolution of 5.6Å .

Data reduction was carried out using the REDUX software package developed by A. Phillips. Using a series of scripts this package subtracts the bias, flatfields the data, removes the $`x`$ and $`y`$distortions, and produces optimal sky subtracted 1-D spectra. Comparison lamp spectra of Hg, Ar, Ne and Kr were used for wavelength calibration. Spectra from the different nights were combined. Flux calibration was provided by the flux standard BD284211 observed on the first night. To correct the GCs onto the Lick/IDS system, we convolved our spectra with a wavelength-dependent Gaussian kernel and then applied small offsets obtained from observations of several Lick standard stars (see Beasley et al. in prep.).

Lick indices (Trager et al. 2000) were measured from our flux-calibrated spectra. Due to the variable nature of the wavelength ranges in multi-slit spectra, the same set of indices were not measured for all spectra. Uncertainties in the indices were derived from the photon noise in the unfluxed spectra. We have obtained spectra with S/N = 30–45 Å-1, giving errors in the H$`\beta `$ index of 0.34–0.22 Å.

Of the 17 usable spectra we confirm that 11 are bona fide GCs. We found objects #43 and #164 (IDs from Grillmair 1992) to be Galactic stars. Background galaxies (and their redshifts) are #40 (z$``$0.11), #163 (z$``$0.07), #167 (z$``$0.14) and #169 (z$``$0.13). Our sample of GCs have an average galactocentric distance of 20 kpc and cover the observed range of C–T1 colors for the GC system (Ostrov, Geisler & Forte 1993). Velocities have been measured from the spectra via cross-correlation with high S/N spectra of two M31 GCs (158-213; $`v_{\mathrm{helio}}`$ = –180 km/s and 225-280; $`v_{\mathrm{helio}}`$ = –164 km/s). The 11 GCs have a mean velocity of 1551 $`\pm `$ 74 km/s and velocity dispersion of 246 $`\pm `$ 57 km/s. NGC 1399 itself has a velocity of 1447 $`\pm `$ 12 km/s. One GC, #41 with velocity 1619$`\pm `$68 km/s, has been excluded from our line-strength analysis due to suspect sky-subtraction.

## 3 Ages and Abundances

To investigate the properties of our GC sample, we primarily use the stellar population models of Maraston & Thomas (2000) which predict line-strength indices using the Lick/IDS-based fitting functions of Worthey (1994). It is important to check that we have adequately corrected the data onto the Lick system. To this end, we have compared index-index plots of our data with the models, and generally find good agreement. The strongest (and best measured) features in the GC spectra, which we use in this study, are the primarily metallicity-sensitive Mg2, Mg $`b`$ and $``$Fe$``$ indices (the mean of the Fe5270 and Fe5335), and the more age-sensitive H$`\beta `$ and H$`\gamma _\mathrm{A}`$ (the broader of the two H$`\gamma `$ indices defined by Worthey & Ottaviani 1997). Our line index measurements for the 10 GCs in NGC 1399 are listed in Table 1. We also include T1 magnitudes (similar to Johnson R) and C–T1 colors from Geisler, Forte & Dirsch (in prep.).

In Fig. 1 we plot the magnesium and iron indices of the GCs, and for the central line-strength of NGC 1399 itself (taken from Kuntschner 2000). At low metallicities, the GCs follow the models reasonably well. However, at higher metallicities, the NGC 1399 GCs deviate significantly from the grids. The metal-rich GCs seemingly show an enhancement of magnesium with respect to iron, $`and`$ an enhancement of Mg $`b`$ with respect to Mg2.

This behavior is also exhibited by NGC 1399 itself, which lies to the right of the population models. The fact that these magnesium lines do not vary in the same fashion does not indicate that we are unable to measure these indices. Rather, these indices (i.e. the bandpasses) have different contributions from elements other than magnesium (e.g. Tripicco & Bell 1995; Trager et al. 2000). Since the models of Maraston & Thomas (2000) use scaled-solar isochrones, we conclude that this offset arises because the metal-rich GCs in our sample have non-solar abundance ratios, i.e. \[Mg/Fe\] $`>`$ 0. This result is consistent with high-resolution spectroscopy of bright giants in Galactic GCs, which typically exhibit \[$`\alpha `$/Fe\] $``$ \+ 0.3 (Carney 1996). Due to the small difference between solar and $`\alpha `$-enhanced isochrones at low metallicities (e.g. Salaris & Weiss 1998) it is possibile that the metal-poor GCs also possess super-solar abundance ratios.

The stellar population models can be used to disentangle age and metallicity, albeit in a model dependent way, and derive relative ages and metallicities for the NGC 1399 GCs. In particular we use the hydrogen Balmer lines which are strongly age sensitive combined with magnesium and iron which are largely metal sensitive.

In Fig. 2 we show our GC data compared to the stellar population models of Maraston & Thomas (2000) extended to younger ages (Maraston 2001, private comm.). To complement Mg2, our most robust measure of metallicity, we use \[MgFe\] (\[Mg $`b`$ $`\times `$ $``$Fe$``$\]0.5), which minimizes the effects of the overabundance seen in Mg $`b`$, whilst increasing measurement accuracy (Gonzalez 1993). We have chosen to derive ages and metallicities for the GCs using the Maraston grids, since these are calibrated on Galactic GCs. In Table 1, we list the derived ages and metallicities of the GCs, obtained from the mean of the values predicted in the upper two panels of Fig. 2. Uncertainties are obtained by perturbing the line-strengths by their errors and re-deriving their ages and metallicities. We emphasize that these uncertainties represent the random measurement errors, and do not include possible systematic errors in the models themselves.

In Fig. 3 we show integrated spectra of three GCs associated with NGC 1399. As described below, two of the GCs (#161, #159) exhibit Balmer and metal line-stengths consistent with very young ages (notice in particular the strong H$`\beta `$ and Mg features in the spectrum of #161). Cluster #49 represents our highest S/N spectrum (H$`\beta `$ error is $`\pm `$ 0.22 Å) and is an example of an old metal–poor GC.

The majority of the GCs are old (as found by Kissler-Patig et al. 1998) and are consistent with the 11 Gyr isochrone, within 2$`\sigma `$ of their individual measurement errors. This age is consistent with the luminosity weighted age for the central stellar population of NGC 1399, i.e. 10 $`\pm `$ 2 Gyr using the line index measurement of Kuntschner (2000). One metal-poor GC ( #149) falls $`below`$ the oldest model isochrones, possibly reflecting the uncertainties in modelling horizontal-branches in the models.

Interestingly, two of the GCs (#159 and #161) have very young inferred ages of $``$2 Gyrs. Such young ages are consistent in all four model grids of Fig. 2, including H$`\gamma _\mathrm{A}`$. Worthey (1994) models also indicate young ages. Significantly, the age estimates from H$`\beta `$–\[MgFe\] and H$`\beta `$$``$Fe$``$ are both consistent indicating that the non-solar \[$`\alpha `$/Fe\] ratios of the GCs are $`not`$ responsible. It is important however to recognise that the population models are somewhat uncertain at very young ages, because they use fitting-functions derived only from old stars.

Kissler-Patig et al. (1998) also identified two GCs (#83 and #102 from Grillmair 1992) with strong Balmer and metal lines, and potentially very young ages albeit with large errors. One possibility raised by these authors was that their enhanced Balmer lines were due to the presence of blue horizontal branches (BHBs).

de Freitas Pacheco & Barbuy (1995), Maraston & Thomas (2000) and Lee et al. (2000) have investigated the potential influence of a BHB on the H$`\beta `$ line index. According to Lee et al. a warm BHB can raise the H$`\beta `$ EW in metal-rich GCs by up to 0.75 Å, without significantly affecting the metallicity, if those GCs are $``$ 4 Gyrs older than Galactic ones. For metal-rich Galactic GCs, with estimated ages $``$ 13 Gyrs, the increase in H$`\beta `$ from a BHB is minimal. Thus assuming that GCs #159 and #161 are truely metal-rich with \[Fe/H\] $``$ 0, then they must be $``$ 4 Gyr older than typical Galactic GCs in order for BHBs to explain their H$`\beta `$ EW. If we accept current estimates for the oldest Galactic GCs to be 12.5 Gyrs, then 16.5 Gyr GCs would be incompatible with the current best estimates for the age of the Universe (Gnedin, Lahav & Rees 2001). We note that future far-UV photometry may help to distinguish between the presence of a BHB and a young age (Lee 2001, private comm.)

So although we can not conclusively choose between these two alternatives, both have interesting implications. If the BHB interpretation is correct, it would be the first detection of BHBs in metal-rich GCs of an elliptical galaxy since the initial discovery in two metal-rich Galactic GCs by Rich et al. (1997). It also implies that at least some GCs in NGC 1399 are systemically older than their Galactic counterparts by at least 4 Gyrs, and hence in conflict with the age of the Universe under certain cosmologies. The alternative is that these GCs, which are both metal-rich and have super-solar \[Mg/Fe\] abundance ratios, formed only $``$ 2 Gyrs ago. Whether these GCs formed in an accreted satellite or in situ is not clear, but to attain the enhanced abundance ratios would require that they formed very soon after the first type II SNe. According to Thomas, Greggio & Bender (1999), a recent merger would require an extremely flat IMF to reproduce the observed $`\alpha `$ enhancement. However late epoch mergers of spiral disks, like the Milky Way, would not be expected to form $`\alpha `$ enhanced metal-rich GCs (Goudfrooij et al. 2001).

## 4 Concluding Remarks

From high S/N spectra and the stellar population models of Maraston & Thomas (2000) we find that the majority of globular clusters in NGC 1399 are old, similar to the luminosity-weighted age of NGC 1399 itself. At least two clusters have super-solar abundance ratios, again like the host galaxy. A super-solar abundance ratio for metal-rich stellar populations is a natural outcome from a fast, clumpy collapse but may also be produced by mergers if star formation has a sufficiently flat IMF (Thomas, Greggio & Bender 1999). Two metal-rich GCs are reported with unusually high H$`\beta `$ line strengths. It remains unclear whether this is due to a young ($``$ 2 Gyr) age, or extremely old ($`>`$ 15 Gyr) age with a blue horizontal branch. However a conflict with current cosmological parameters is avoided if the young age is favoured.

## 5 Acknowledgments

We thank T. Bridges for the cluster photometry, A. Phillips for the use of his software, L. Schroder for help with initial data reduction, and C. Maraston for providing her model grids ahead of publication. We also thank S. Larsen, B. Gibson and C. Maraston for useful discussions. Part of this research was funded by NSF grant AST 9900732 and an ARC grant. MB thanks the Royal Society. The data presented herein were obtained at the W.M. Keck Observatory, which is operated jointly by the California Institute of Technology and the University of California.


text:
# Intercellular Communication Via Intracellular Calcium Oscillations

## Abstract

In this letter we present the results of a simple model for intercellular communication via calcium oscillations, motivated in part by a recent experimental study. The model describes two cells (a ”donor” and ”sensor”) whose intracellular dynamics involve a calcium-induced, calcium release process. The cells are coupled by assuming that the the input of the sensor cell is proportional to the output of the donor cell. As one varies the frequency of calcium oscillations of the donor cell, the sensor cell passes through a sequence of N:M phase locked regimes and exhibits a ”Devil’s staircase” behavior. Such a phase locked response has been seen experimentally in pulsatile stimulation of single cells. We also study a stochastic version of the coupled two cell model. We find that phase locking holds for realistic choices for the cell volume.

Oscillatory increases in the intracellular concentration of calcium control a variety of important, diverse biological functions, including muscle contraction, metabolism and gene expression . In the latter case, for example, calcium oscillations lead to the expression of genes that are essential for dendritic development and neuronal survival. A recent review of the versatility and universality of calcium signalling has been given by Berridge et al . Typically cells have a Ca2+ rest concentration of about 100 nM, but when activated rise to concentrations of roughly ten times this. Such increases can be produced by ligands (agonists) binding to receptors located on the plasma membrane, through a process involving the second messenger inositol-1,4,5-trisphosphate (IP3). These can be receptor-specific, as shown in a recent study of the relationship between the production of IP3 and the calcium response . An important characteristic of the spike-like Ca2+ oscillations is that they are frequency, rather than amplitude, encoded. That is, an increase in the agonist concentration increases the frequency of oscillation, but has little effect on its amplitude. Another significant characteristic is that calcium signals can be propagated between cells, providing an important means of cell communication. Such intercellular communication can take different forms, including diffusion of calcium or IP3 through gap junctions and paracrine signaling. Recently deterministic models have been developed for signalling through gap-junction diffusion, via a second messenger such as calcium or IP3 . Important stochastic effects have also been included  for gap-junction signalling, as well as for other aspects of calcium dynamics . In one type of paracrine signalling, a calcium spike in one cell causes the release of a secondary agonist, such as ATP, to the extracellular space, followed by stimulation of purinergic receptors on nearby cells . Recently a new paracrine mechanism for intercellular communication has been proposed , based on the fact that the calcium liberated as a consequence of intracellular calcium spiking is often extruded to the extracellular neighborhood of the cell. The recent experimental study showed if this space is limited such that the local extracellular calcium fluctuations are sufficiently large, calcium-sensing receptors (CaR)  on the surfaces of adjacent cells can be activated, producing secondary spikes in these cells. Thus calcium receptors may mediate a new form of intercellular communication in which cells are informed of the intracellular signaling of their neighbors via extracellular calcium fluctuations. However, the experimental results yield only qualitative information about the response of the sensor cell to the donor cell.
In this letter we present the results of a simple model for paracrine intercellular communication via calcium oscillations, motivated in part by this recent experimental study. As one still does not understand in detail the complex biochemistry involved in the CaR coupling, we limit ourselves to studying a simplified model that might capture the qualitative features of this new form of signaling. There are two aspects to describing the intercellular communication: the intracellular dynamics and the coupling between cells. A number of theoretical models have been developed to explain intracellular Ca oscillations . The basis for most of these is that after an agonist (hormone) binds to the extracellular side of a receptor bound to the membrane, the Gα subunit at the intracellular side of the receptor-coupled G-protein is activated. This activated G-protein then stimulates a phospholipase C (PLC) which helps form a second messenger IP3 and diacylglycerol. IP3 then binds to specific receptors in the membrane of an internal store of calcium (such as the endoplasmic reticulum). The binding helps open calcium channels, which leads to a large flux of calcium ions from the internal store into the cytosol, which then stimulates the release of additional calcium ions. Some details of this complex progress, however, remain unknown.
As there are many different models for the intracellular calcium oscillations, we choose the simplest to illustrate how the results of communication between cells might differ depending on the internal cell dynamics. This is the so-called minimal model, involving two dynamical variables, the cytosolic calcium and an internal store of calcium (such as the endoplasmic reticulum) respectively , in which an agonist induces calcium oscillations in a single cell. We couple two such cells, the donor cell and the sensor cell, by assuming that the stimulus of the target cell is proportional to the cytosolic calcium content of the first cell. Since some of the cytosolic Ca2+ produced in the donor cell is extruded into a small space near a CaR receptor, this seems to be a reasonable assumption. This avoids modeling the extracellular diffusion of Ca2+ as well as the complex receptor dynamics that is presumably involved in the calcium-sensing receptor mechanism proposed by Höfer et al. . However, our model is consistent with the spirit of the single cell minimal model in that it provides a minimal two cell coupling that yields interesting intercellular communication. We should also note that under in vivo conditions, hormones are not released steadily, but are released in a pulsatile fashion. Thus our results for the sensor cell responding to an input signal are in principle relevant to the physiologically interesting question of how the intracellular cytosolic calcium responds to a pulsatile application of agonists.

We consider a coupled cell version of the minimal model, coupling two cells through a term proportional to the calcium output of the first (donor) cell. This term will serve as an external stimulus for the second (sensor) cell. The donor cell dynamics is described by two differential equations for its cytosolic Ca2+ concentration, $`y_1`$ and its internal store of Ca2+, $`y_2`$:

$`{\displaystyle \frac{dy_1}{dt}}`$ $`=`$ $`V_0+\beta _1V_1V_2+V_3+k_fy_2ky_1`$ (1)
$`{\displaystyle \frac{dy_2}{dt}}`$ $`=`$ $`V_2V_3k_fy_2`$ (2)
where $`V_2=\frac{V_{m2}y_1^2}{(k_2^2+y_1^2)}`$ and $`V_3=\frac{V_{m3}y_1^4y_2^2}{(k_a^4+y_1^4)(k_r^2+y_2^2)}`$. This model has been studied extensively . It is known that for a given set of the parameter values Ca2+ oscillations will occur when the parameter $`\beta _1`$, which increases with the concentration of the external hormonal stimulus, lies in a range $`\beta _{min}<\beta _1<\beta _{max}`$. The minimum and maximum values depend mainly on the parameters $`V_0`$ and $`V_1`$.
The sensor cell is modeled using the same equations for its cytosolic and internal calcium concentrations $`y_1^{^{}}`$ and $`y_2^{^{}}`$ as given in Eqs(1,2). However, instead of a term $`\beta _2V_1^{}`$ representing a constant stimulus, we use the term $`\beta _2y_1V_1^{}`$, which provides the coupling between the cells. This assumes that the stimulus to the donor cell from the extruded calcium from the donor cell is proportional to the the latter’s cytosolic calcium concentration. In general, the structural parameters $`V_0`$, $`V_1`$, $`V_2`$, $`V_3`$, $`k_f`$, $`k`$ of the first cell and $`V_0^{}`$, $`V_1^{}`$, $`V_2^{}`$, $`V_3^{}`$, $`k_f^{}`$, $`k^{}`$ of the second cell can be different, but for the sake of simplicity we take them to be the same. We find in general that oscillations in the donor cell due to a constant hormonal input produce oscillations in the sensor cell. This is in qualitative agreement with the experimental observation , but the detailed predictions of our model require further experimental study.
We have calculated the N:M rhythms predicted for this coupled minimal model as a function of $`\beta _1`$ for fixed $`\beta _2`$, where N denotes the number of stimuli arising from the donor cell and M the number of responses of the sensor cell in a given time interval. For example, the frequency of response can be the same as the frequency of the stimulus, i.e. N:M is 1:1. However, in general the Ca2+ response in the sensor cell is blocked when the frequency of pulses of the donor cell is increased. In Fig. 1 we show a 3:2 response. This phenomenon of blocking is also seen in heart patients, where it is known as Wencekbach periodicity. As one varies $`\beta _1`$ the sensor cell passes through a sequence of N:M phase locked regimes (in response to the oscillatory stimuli from the donor cell) and exhibits a ”Devil’s staircase” behavior , as shown in Fig. 2. That is, between any two steps there is a countless number of staircases. This behavior has been found earlier in a study of a finite difference model of cardiac arrhythmias  as well as in a model of intracellular calcium oscillations  in which the hormonal stimulus was modeled by a sequence of square well pulses. However, this is the first prediction of such behavior in coupled, nonexcitable cells. We find, for example, that with $`k=6s^1`$, $`k^{}=6s^1`$, $`\beta _2=0.4`$ and all other parameters as in Table 1 the variation of $`\beta _1`$ from $`0.3`$ to $`0.415`$, i.e. increase in the concentration of the external stimulus which increases the frequency output of the first cell, leads to the ratio of the stimulus/response from 1:1 rhythm ($`\beta _1=0.3`$), through 5:4 ($`\beta _1=0.4`$), 4:3 ($`\beta _1=0.405`$), 3:2 ($`\beta _1=0.41`$), 5:3 ($`\beta _1=0.412`$) to the 2:1 rhythm ($`\beta _1`$=0.415). On the other hand, various rhythms also can be obtained by fixing, for example, $`\beta _1=0.3`$ and varying $`\beta _2`$ from 0.38 to 0.345 (all other parameters as described above). In this case we find the following sequence of the stimulus/response rhythms: 1:1 rhythm ($`\beta _2=0.38`$), 5:4 ($`\beta _2=0.37`$), 4:3 ($`\beta _2=0.365`$), 3:2 ($`\beta _2=0.36`$) and finally a 2:1 rhythm ($`\beta _2`$=0.345). Some examples of the Devil’s staircase are shown in Fig. 2 and Fig. 3. This response of the sensor cell is similar to experimental results of Sch$`\ddot{o}`$fl et al.  who applied square wave pulses to phenylephrine to liver cells every 30 seconds. They found stimulus/response rhythms such as 2:1, but with less regularity than shown here . A subsequent stochastic model based on a deterministic model of intracellular dynamics due to Chay et al  yielded results qualitatively similar to the experiment .
Deterministic models such as the one used above neglect potentially important stochastic effects such as fluctuations in the baseline values of Ca2+ and variations in the amplitudes and widths of the spikes. Since the number densities of the intracellular signaling molecules are typically low (of the order of $`110^2\mu m^3`$, stochastic effects could be important. To see whether such effects are significant here, we have also studied a stochastic version of our model, using a Monte Carlo method due to Gillespie . We have studied the stochastic model for different values of the cell volume $`\mathrm{\Omega }`$ (assumed to be the same for both cells). For very small $`\mathrm{\Omega }`$ fluctuations destroy the phase locking, while in the limit of large $`\mathrm{\Omega }`$ one recovers the deterministic limit. Both results are what one would expect. For intermediate values of $`\mathrm{\Omega }`$, however, such as $`\mathrm{\Omega }=2000`$, which is the approximate volume of hepatocyte cells, we find that phase locking persists, although with occasional lapses. Some typical results for this case are shown in Fig. 4. Thus we find a stochastic version of the Devil’s staircase for values of the cell volume that are realistic. We also found that cells can switch between frequencies in the stochastic model if we choose $`\beta _1`$ and $`\beta _2`$ such that the deterministic model would give a frequency locking of the cells on the edge of one of the steps of the Devil’s staircase.
In conclusion, we have shown that a coupled minimalist model can account for a variety of calcium oscillations that have been seen experimentally in hepatocytes stimulated with time-dependent pulses of hormone . This simple model can also describe intercellular communication between cells via calcium-sensing receptors, with results that are at least qualitatively consistent with a recent experimental study  We have found in addition that the deterministic version of the model yields a Devil’s staircase type of phase locking between the donor and sensor cell. We have also found that this phase locking is present in a stochastic version of this model, which is a novel feature of the study. The stochastic model is more realistic than the deterministic model and yields baseline fluctuations and variations in the amplitude of the spikes in Ca2+, as seen in experimental studies of calcium oscillations. Whether or not paracrine communication in real biological systems will exhibit a Devil’s staircase behavior is an open question, however, as there are many ways in which one should improve our model to make it more realistic. For example, we are currently extending this study to include the plasma membrane receptor dynamics , and oscillations in $`IP_3`$ that have been seen in some recent studies . Our preliminary results from a study of two cells whose internal dynamics is given by a model of Kummer et al  with coupling through receptor dynamics similar to that of Riccobene et al  show that bursting behavior, in addition to the type of behavior reported here, is also possible for this form of paracrine communication. The fundamental problem of paracrine cell communication would seem to be a rich field for further experimental and theoretical investigation.
Acknowledgment This work was supported by NSF grant DMR9813409.

Figure Captions

Fig.1 Calcium oscillations of two connected cells ($`\beta _1`$=0.3, $`\beta _2`$=0.36). Frequencies of cells are locked in a sequence of 3:2. Deterministic model.

Fig.2 Devil’s staircase, a ratio $`N/M`$ (where $`N`$ is the number of spikes of the donor cell and $`M`$ is the number of spikes of the sensor cell) as a function of $`\beta _1`$ at fixed $`\beta _2`$=0.3.

Fig.3 Devil’s staircase, a ratio $`N/M`$ as function of $`\beta _1`$ at fixed $`\beta _2`$=0.2.

Fig.4 Calcium oscillations of two connected cells ($`\beta _1`$=0.17, $`\beta _2`$=0.3). Frequencies of cells are locked in a sequence of 1:1 with occasional fluctuations. Stochastic model with $`\mathrm{\Omega }=2000`$.


text:
# 1 Introduction

## 1 Introduction

The idea of processing information stored in quantum states has spawned numerous cryptographic applications. A few examples include quantum key distribution , which allows remote parties to securely establish a shared list of random numbers; a fast quantum algorithm for factoring , which can be used to break certain classical cryptosystems; quantum secret sharing , by which a secret quantum state can be divided among several parties; quantum data hiding , which offers an information theoretically secure way of sharing a classical secret; quantum digital signatures , which can be used to authenticate documents; and secure quantum channels , which allow secure transmission of quantum states.

But there are also a number of negative results about the possible cryptographic applications of quantum information, such as the impossibility of an unconditionally secure quantum protocol for bit commitment . A related result is the impossibility of “secure two-party computation,” in which two parties collaborate to compute a function without revealing their inputs  (although in general, secure multi-party quantum computation is possible ). However, this does not rule out all forms of collaborative computation by two parties: for example, what if one of the parties wishes to assist the other, with no possibility of learning the input or output of the computation? We will show that this kind of two-party computation can be done securely.

More precisely, the problem we will consider is the following: imagine that Alice would like to perform a quantum computation in secret, but although she can do some basic quantum gates, she does not have a full-fledged quantum computer. Bob, who runs a company that sells time on its quantum supercomputer, would like to supply Alice with the resources she needs to perform her computation. But Alice does not trust Bob; she needs to be absolutely sure that he cannot learn anything about her computation, i.e., that the state Bob sees at any time is the same, independent of her actual quantum state. Can they carry out an unconditionally secure protocol by which Bob can assist Alice? In this paper, we describe protocols that answer this question in the affirmative.

To fully specify our question, we must decide exactly what resources are allowed. Three kinds of resources must be specified: operations available to Alice, operations available to Bob, and ways in which they can communicate. We will always allow Bob to do universal quantum computation and make arbitrary quantum measurements, and we will allow bidirectional quantum communication. There are many possible restrictions on Alice’s resources that might be of interest, but we will choose the most restrictive set under which Bob can help her do universal quantum computation. We will allow Alice to store quantum states and to route her qubits (i.e., perform the swap gate), but we will suppose that the only nontrivial gates she can perform are the Pauli gates,

$$X:=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right],Z:=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$
(1)
(with which she can perform their product $`XZ`$, etc.). This gate set fails to be universal in two important ways. First, Alice cannot perform any interactions between qubits. Second, the single-qubit gates she can perform are restricted to the discrete set $`\{I,X,Z,XZ\}`$ (up to an overall phaseaaaFor simplicity, we identify operators that differ by an overall phase, since such phases are irrelevant in all the situations we consider. Equivalently, we could multiply all operators by a phase so that they have unit determinant. ), which forms a group (the Pauli group) under multiplication. In addition to the restrictions on her gates, we will suppose that Alice can only prepare the $`|0`$ state, and she cannot perform measurements. Alice also must be able to generate random classical bits (say, by flipping unbiased coins) and to perform Pauli gates conditioned on the values of these classical bits.

Note that a related question has been considered in the classical setting. As we argue in Section 5, there is no reasonable restriction on Alice’s gate set under which she can carry out a classical protocol analogous to our quantum protocols. However, one can instead assume Alice has the ability to perform polynomial-time computation and ask whether she can securely receieve help from an arbitrarily powerful Bob. For certain particular problems this is the case , whereas for other problems (in particular, NP-hard ones), it is not . In contrast, our protocols make no computational assumptions, and will apply to any quantum circuit known to Alice, not just the computation of a particular function.

All of the protocols we present are applications of a quantum version of the Vernam cipher , also known as private key encryption or the one-time pad. The classical Vernam cipher works as follows: suppose Alice wishes to securely send a bit $`b`$ to Charlie. She and Charlie share another bit $`k`$, the key, that is randomly chosen to be either $`0`$ or $`1`$, each with probability $`\frac{1}{2}`$. Alice computes the message bit $`m=bk`$, where $``$ denotes addition modulo two, and sends it to Charlie. Since he knows $`k`$, he can compute $`b=mk`$. However, an eavesdropper (whom we shall call Eve) who does not know $`k`$ can learn nothing about $`b`$ since $`b`$ and $`m`$ have zero mutual information. To send multiple bits, Alice and Charlie can repeat this procedure, using a new random key bit for each message bit.

The private quantum channel is a quantum analogue of this protocol in which the key remains classical, but the channel is used to send quantum states . (Note that this differs from the quantum Vernam cipher, in which the key is also a quantum state .) In the private quantum channel, Alice and Charlie need to share two classical bits $`j`$ and $`k`$ for Alice to send her qubit. The circuit shown in Fig. 1 summarizes their protocol. Alice applies the unitary operator $`Z^kX^j`$ to her state $`|\psi `$ and sends the result to Charlie. In between, Eve may intercept the state, but since she doesn’t know $`j`$ or $`k`$, she sees the density matrix

$$\frac{1}{4}\underset{j,k=0}{\overset{1}{}}Z^kX^j|\psi \psi |X^jZ^k=\frac{I}{2}$$
(2)
independent of $`|\psi `$. From Eve’s perspective, Alice has applied the depolarizing channel, so Eve can learn nothing about the state. Although she can destroy the state or change it in some way, she cannot learn anything about it. Assuming she does nothing, Charlie will receive the state $`Z^kX^j|\psi `$. Since he knows the values of $`j`$ and $`k`$, he can apply the inverse operation $`X^jZ^k`$ to recover the original state. If Alice wants to send Charlie $`n`$ qubits, they can repeat the procedure independently for each qubit, using a total of $`2n`$ random classical bits as the key. From Eve’s perspective, the density matrix of all $`n`$ qubits is again maximally mixed, independent of Alice’s state, so the procedure is secure.

We will show how the idea of a private quantum channel can be adapted to allow Bob to help Alice perform a quantum computation. The main idea behind these circuits is that Alice can use a private quantum channel to securely send qubits to herself. Since Alice is both the sender and the receiver, there is no need for her to distribute a key. Alice sends her qubits by way of Bob, who plays the part of the eavesdropper. However, instead of trying to learn Alice’s state (which of course would be futile), he intentionally performs the gate Alice would like to be able to do. After he gives it back to Alice, she performs an appropriate decoding operation. Of course, this procedure is only useful if the decoding operation can be performed using only the restricted set of gates available to Alice, which is not necessarily the case for arbitrary gates.

We begin in Sec. 2 by showing how Bob can help Alice perform a measurement in the computational basis, and then show how he can help her complete her gate set to do universal quantum computation in Sec. 3. We give a unified description of $`k`$-round protocols for secure assisted gates in Sec. 4, and we discuss why they have no meaningful classical analogue in Sec. 5. In Sec. 6 we discuss the question of whether Alice can determine whether Bob is being honest. Finally, in Sec. 7 we conclude with a discussion and some open questions.

## 2 Secure assisted measurement

First, we describe how Bob can make a measurement for Alice. We begin by discussing a classical version of the protocol. Suppose Alice has a classical bit $`b`$, but although she can manipulate it, she cannot read its value. However, she can securely send her bit to Bob and ask him to read it for her. Alice chooses a key bit $`k`$ at random and computes $`bk`$. She then gives the result to Bob, who reads the result and tells it to her. To determine the value of her original bit $`b`$, she simply flips the result if $`k=1`$ and does nothing otherwise.

This classical procedure doesn’t seem very useful since reading the value of a classical bit is usually an easy thing to do. But quantum measurement is a difficult task, so we can imagine a scenario in which Alice can coherently manipulate her qubits, but she cannot measure them. In such a situation, there is a quantum version of the above measurement protocol that allows Bob to make a measurement of Alice’s state in the computational basis. Alice chooses two random bits $`j`$ and $`k`$ and applies the unitary operator $`Z^kX^j`$ to her state. She then gives the qubit to Bob. He can acquire no information from this state since from his point of view, by (2) the density matrix is maximally mixed, independent of Alice’s actual state. However, if he measures the qubit in the computational basis and reports the result to Alice, she can determine the result of the corresponding measurement on her original state. The $`Z`$ operator does not change the measurement result, and the $`X`$ operator flips it, so Alice should flip the result if $`j=1`$ and not flip it if $`j=0`$. A quantum circuit for this protocol is shown in Fig. 2.

## 3 Secure assisted gates

We now describe how Bob can help Alice perform universal quantum computation. We do this by showing that she can perform a universal set of gates. In particular, we present circuits by which she can securely perform the Hadamard gate,

$$H:=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& 1\end{array}\right];$$
(3)
the $`\pi /8`$ gate,

$$T:=\left[\begin{array}{cc}1& 0\\ 0& \sqrt{i}\end{array}\right];$$
(4)
and the controlled-not gate (a two-qubit interaction),

$$C:=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right].$$
(5)
This gate set is universal for quantum computation in the sense that any unitary transformation can be approximated arbitrarily closely by some sequence of these gates . Thus, the circuits for secure implementation of these gates can be used as subroutines to perform an arbitrary quantum computation.

The simplest of these constructions is the protocol for a secure Hadamard gate. Alice chooses two random classical bits $`j`$ and $`k`$. To randomize her state so that Bob can learn nothing from it, Alice applies $`Z^kX^j`$ to her qubit. She then passes it to Bob. By (2), Bob’s density matrix is maximally mixed, independent of Alice’s actual state. If Bob is honest, he performs a Hadamard gate and hands the qubit back to Alice. Now she must correct her qubit so it is as if only the Hadamard were applied. Because $`XHZ=ZHX=H`$, $`Z`$ can be undone by $`X`$ and $`X`$ can be undone by $`Z`$. Thus Alice can appropriately fix her state using only Pauli gates, regardless of the values of $`j`$ and $`k`$. The resulting circuit, shown in Fig. 3, is equivalent to a Hadamard gate if Bob is honest. If he is dishonest, he can destroy Alice’s qubit or give her the wrong result, but he can learn nothing from the state she gave him.

A similar procedure can be used to perform a controlled-not gate. Since this is a two qubit gate, Alice must choose four random classical bits $`j,k,l,m`$. She randomizes her state by applying $`Z^kX^j`$ to the first qubit and $`Z^mX^l`$ to the second. Then she gives the qubits to Bob, who is supposed to perform a controlled-not gate and return them to Alice. Note that by (2) applied to each of the two qubits, Bob’s density matrix is maximally mixed, independent of Alice’s state. Supposing that Bob performs the controlled-not gate as requested, Alice must correct the encoded qubits so that the overall interaction is a controlled-not. If $`j=1`$, then the target bit was inverted based on an inverted control bit, so she must apply $`X^j`$ to the target. She then fixes the target bit by applying $`X^lZ^m`$ and the control bit by applying $`X^jZ^k`$. However, if $`m=1`$, she has also performed a controlled-$`(1)`$ gate due to the anticommutation of $`X`$ and $`Z`$. This can be fixed by applying $`Z^m`$ to the control bit. The resulting circuit is shown in Fig. 3.

Although the $`\pi /8`$ gate is only a one-qubit gate, this operation is more complicated to implement: Alice and Bob must use a two-round protocol, as we prove in the next section. In total, Alice needs four random classical bits $`j,k,l,m`$. First, she randomizes her quantum state by applying $`Z^kX^j`$. She then gives it to Bob (whose density matrix, again by (2), is maximally mixed), and if he is honest, he applies a $`\pi /8`$ gate and gives it back to Alice. She can undo her randomization by applying $`X^jZ^k`$. The $`Z`$ operation commutes with $`T`$, so it does not create any problems. However, $`XTX=T^{}`$ (up to an overall phase), which differs from $`T`$ by $`S:=T^2`$, a gate that Alice cannot perform. But she can have Bob do it for her, again encoding the qubit using (2), and since $`S^2=Z`$, she will be able to undo the randomization herself. If she only asks Bob to help her perform $`S`$ when $`j=1`$, this tells him the value of $`j`$. But Alice can avoid revealing $`j`$ by always asking Bob to participate in the second round, but operating on a dummy qubit when $`j=0`$. The complete circuit is shown in Fig. 3. Assuming Bob is honest, this circuit is equivalent to the $`\pi /8`$ gate up to an irrelevant overall phase.

## 4 The Gottesman-Chuang hierarchy

In this section, we explain the existence of the gate constructions discussed in the previous section using a hierarchy of gates presented by Gottesman and Chuang . We show that the gates that can be realized using a $`k`$-round protocol are exactly those in the $`(k+1)`$th level of this hierarchy.

A single-round protocol for a secure assisted gate $`U`$ on $`n`$ qubits requires that

$$D_jUE_j=Uj,$$
(6)
where $`E_j,D_j`$ are Alice’s encoding and decoding operators. Let $`C_1`$ denote the Pauli group on $`n`$ qubits; that is, all operators that are tensor products of $`n`$ Pauli operators. Furthermore, let $`C_1^S`$ denote those operators that can be written as a product of Pauli group elements and permutations of the qubits (i.e., products of swap gates). Gates in $`C_1^S`$ are exactly the operations that Alice can perform without assistance, so $`E_j,D_jC_1^Sj`$. For simplicity, we will assume that Alice uses the encoding where $`E_j`$ runs over all elements of $`C_1`$, each with probability $`p_j=2^n`$. (More generally, Alice could choose to include swap gates in her encoding, but this would not affect our conclusions.) The decoding operations are specified by

$$D_j=UE_j^{}U^{}.$$
(7)
Thus the requirement $`D_jC_1^S`$ allows us to classify the possible $`U`$’s that can be realized in this way: $`U`$ must come from the set

$$C_2^S:=\{U:UC_1U^{}C_1^S\}.$$
(8)
It is not hard to show that in factbbbI thank Wim van Dam for a discussion of this point.

$$C_2^S=C_2:=\{U:UC_1U^{}C_1\}.$$
(9)
The set $`C_2`$ forms a well known group, the Clifford group . Any gates in this group, such as the Hadamard and cnot gates, can be realized with a one-round protocol.

If Alice and Bob are willing to use a two-round protocol, they can do more gates. By the preceding discussion, Bob must do a gate from $`C_2`$ in the second round. However, in the first round, he can do any gate from

$$C_3:=\{U:UC_1U^{}C_2\},$$
(10)
e.g., the $`\pi /8`$ gate (or the Toffoli or Fredkin gate). Different encoding/decoding pairs may require Bob to do different things in the second round, but if Alice uses the swap trick introduced in the secure $`\pi /8`$ gate construction, this need not provide him with any information. By induction, we see that in $`k`$ rounds, Alice and Bob can securely perform any gate in the set

$$C_k:=\{U:UC_1U^{}C_{k1}\}.$$
(11)
Note that gates in $`C_2`$ are not sufficient for universal computation. However, universal quantum computation can be done using $`C_3`$ gates.

At first glance, it may seem that the form of (6) is too restrictive. Why should Bob have to perform exactly the gate Alice wants? In other words, shouldn’t we consider protocols of the form

$$D_jVE_j=Uj,$$
(12)
where $`VU`$? The answer is no, because if such a scheme exists, we can easily turn it into a scheme where $`V=U`$: we have $`V=D_0^{}UE_0^{}`$, which can be substituted into (12) to give

$$U=D_jD_0^{}UE_0^{}E_j.$$
(13)
By using the modified encoding operations $`E_j^{}=E_0^{}E_j`$ and decoding operations $`D_j^{}=D_jD_0^{}`$, Alice can ask Bob to perform $`U`$ instead of $`V`$. Thus there is no loss of generality in the choice (6).

## 5 Secure assisted classical gates

It is interesting to contrast these protocols for secure assisted quantum gates with the corresponding problem for reversible classical computers. If Alice cannot do universal classical computation, is it possible for Bob to assist her in a secure way? The answer is no: secure assisted universality can only be achieved in a meaningful way in the quantum setting. This is essentially because the ability to do classical operations is assumed in the quantum case, so classically controlled quantum gates are no more difficult to implement than unconditional quantum gates; but a classically controlled classical gate can be a more powerful resource than the original classical gate. For example, the controlled-not gate is not universal for classical computation, but a controlled-controlled-not (more commonly known as a Toffoli gate) is universal.

To see why secure assisted classical universality is not possible, we introduce a classical analogue of the Gottesman-Chuang hierarchy. For $`n`$-bit gates, let $`\stackrel{~}{C}_1`$ denote gates that are tensor products of $`n`$ identity and not gates. Also, let

$$\stackrel{~}{C}_k:=\{P:P\stackrel{~}{C}_1P^1\stackrel{~}{C}_{k1}\}$$
(14)
denote the set of classical gates (permutations) that map $`\stackrel{~}{C}_1`$ gates into $`\stackrel{~}{C}_{k1}`$ gates under conjugation. Just as in the quantum case, gates in $`\stackrel{~}{C}_2`$ are not sufficient for universal computation, but there are gates from $`\stackrel{~}{C}_3`$ (e.g., the Toffoli and Fredkin gates) that are universal. Thus the natural restriction on Alice’s gate set is to allow her to do only $`\stackrel{~}{C}_2`$ gates. In particular, since she must use gates that are controlled based on the values of her random key bits, she will be interested in using controlled-$`\stackrel{~}{C}_1`$ gates, all of which are in $`\stackrel{~}{C}_2`$. However, with a single-round protocol, she can only use controlled-$`\stackrel{~}{C}_1`$ gates to build $`\stackrel{~}{C}_2`$ gates on her computational bits, which gives her no additional computational power. Since she cannot perform the controlled-swap (Fredkin) gate, she cannot securely perform a multi-round protocol. Thus there is no way for her to achieve secure assisted universality.

However, there are particular examples in which Alice and Bob can perform a computation securely even in the classical case. Some work along these lines was mentioned in Section 1, but a simple example that shows the advantage of having a particular problem in mind is the following. Suppose Alice would like to find a satisfying assignment for a Boolean formula containing $`n`$ variables. Alice generates $`n`$ random bits, one for each of the variables in the formula. If the bit corresponding to a particular variable is zero, she does nothing; if that bit is one, she inverts the variable wherever it appears in the formula. She then tells Bob the formula, and if he is honest, he gives her a satisfying assignment. To find a satisfying assignment for her original problem, she flips the bits corresponding to the variables that were inverted in the formula she gave to Bob. Although Bob can learn a lot about the structure of the problem, he cannot learn the particular satisfying assignment of her original problem.cccI thank Sam Gutmann for suggesting this example.

## 6 Keeping Bob honest

The primary weakness of these protocols is that although he can learn nothing about the states Alice gives him, Bob can easily prevent her from performing her computation. He could simply not return her qubits, or worse yet, he could ruin the computation by performing the wrong gate. This weakness is inherited from the private quantum channel, and there is no way to avoid it altogether. However, although she cannot force Bob to help her, there may be simple ways for Alice to detect whether Bob is cheating.

If Alice is asking Bob to help her solve a problem in the computational complexity class NP, there is a particularly simple way for her to check his honesty. Presumably, Alice is asking for Bob’s help because the problem can be solved much faster on a quantum computer than on a classical computer—for example, she might ask him to help her perform Shor’s algorithm to factor a number. But if Alice has access to a classical computer and the problem is in NP, she can easily check the solution to see if it is right. In the example of factoring, Alice simply multiplies the resulting factors to see if they give her input.

However, what if Alice cannot readily check the solution? Can she still efficiently detect whether Bob is cheating? Intuitively, it seems that Alice should be able to gain some confidence that Bob is behaving honestly by performing tests of his actions using a randomly chosen subset of her inputs. If these tests fully characterize Bob’s operations, they can be used to bound the probability that Bob is cheating. Indeed, such a procedure provides an efficient way to check whether Bob is cheating in the restricted scenario in which he must act as a memoryless black box, as can be shown using ideas along the lines of . However, in general, Bob could introduce errors adversarially rather than randomly, which presents a more difficult verification problem. We leave the general adversarial scenario as an open problem. A solution to this problem might also be relevant to fault-tolerant quantum computing, where the assumption that Bob acts as a memoryless black box corresponds to an assumption of independent errors, and the general adversarial scenario accommodates errors of the most general type (which are hopefully nevertheless small).

## 7 Discussion

We have shown that it is possible for a party who cannot do universal quantum computation (Alice) to have her computational power augmented by another party (Bob) without compromising the security of the computation. Furthermore, we have briefly discussed ways of detecting whether Bob is truly being helpful—a problem that deserves further study. The protocols we have described, and more general protocols for verifying the validity of Bob’s actions, might prove useful for assuring the security of certain quantum information processing tasks.

We have focused on preventing Bob from obtaining information about the states Alice gives him, and we have not considered the information he might obtain from the particular gates Alice asks him to perform. We can imagine that she might want to prevent him from learning something this way. For example, in the context of programmable gates, Vidal and Cirac considered a different scenario in which Bob can learn Alice’s input, but she does not want him to know the function she is trying to compute . In the context of the present paper, it is not particularly difficult to prevent Bob from learning the function. The protocol can simply consist of Bob performing a fixed sequence of gates, cycling through Hadamard, cnot, and $`\pi /8`$. If a particular gate is not needed, she can supply Bob with junk qubits. With this protocol, the number of gates is increased by at most a factor of three. Since Alice does not send any classical information to Bob to describe her circuit, and since we have already established that he can learn nothing from her quantum states, it follows that he cannot learn anything about which gates are being used. The only thing Bob can learn is the length of the protocol, i.e., the total number of gates Alice has him perform. Even this meager amount of information can be reduced (although not eliminated), since Alice is free to add additional unnecessary gate requests, so that Bob can only learn an upper bound on the number of gates in Alice’s circuit.

Note that there is an analogy between programmable gates and secure assisted gates: whereas programmable gates generalize identity teleportation to gate teleportation, secure assisted gates generalize an identity private quantum channel to a private quantum channel that performs a gate. Furthermore, the Gottesman-Chuang hierarchy plays a similar role in the construction of gate teleportation circuits  and in showing that two-qubit measurements are universal for quantum computation .

There are many possible variants of this problem depending on the resources Alice and Bob are allowed to use. For example, if Alice is only allowed to perform single-qubit measurements, Bob can supply her with a cluster state . Perhaps other resource limitations would lead to interesting forms of secure assisted quantum computation.

Finally, it might be useful to consider restricting the total amount of information transfer. We have assumed that Alice and Bob have an inexpensive quantum channel, so they can send quantum states back and forth as many times as they wish. But this may not be a realistic assumption. If Alice and Bob are connected only by a very slow or expensive channel—or perhaps only by a classical channel, with a small reserve of prior shared entanglement—can they still accomplish interesting computational tasks? In other words, can they perform secure remote quantum computation? We should not expect Bob to enable Alice to do secure universal computation on remote data, but she might nevertheless be able to perform certain tasks securely.

Acknowledgements

I thank Isaac Chuang, Wim van Dam, Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Aram Harrow, Debbie Leung, Hoi-Kwong Lo, Ben Recht, Adam Smith, and Ronald de Wolf for helpful discussions. This work was supported by the Fannie and John Hertz Foundation, by the Cambridge–MIT Institute, by the National Security Agency and Advanced Research and Development Activity under Army Research Office contract number DAAD19-01-1-0656, and by the Department of Energy under cooperative research agreement DE-FC02-94ER40818.

References