text:
# Quantum cryptographic three party protocols

## I Introduction

In a multi party protocol a set $`P`$ of players wants to correctly compute a function $`f(a_1,\mathrm{},a_n)`$ which depends on secret inputs of $`n`$ players. Some players might collude to cheat in the protocol as to obtain information about secret inputs of the other players or to modify the result of the computation. Possible collusions of cheaters are modelled by adversary structures

###### Definition 1

An adversary structure is a monotone set $`𝒜2^P`$, i. e., for subsets $`S^{}S`$ of $`P`$ the property $`S𝒜`$ implies $`S^{}𝒜`$.

The main properties of a multi party protocol are:

1. A multi party protocol is said to be $`𝒜`$-secure if no single collusion from $`𝒜`$ is able to obtain information about the secret inputs of other participants which cannot be derived from the result and the inputs of the colluding players.
2. A multi party protocol is $`𝒜`$-partially correct if no possible collusion can let the protocol terminate with a wrong result.
3. A multi party protocol is called $`𝒜`$-fair if no collusion from $`𝒜`$ can reconstruct the result of the multi party computation earlier then all honest participants together. No collusion should be able to run off with the result.

We will be more strict here and demand robustness even against disruptors.

1. A multi party protocol is $`𝒜`$-correct whenever no single collusion from $`𝒜`$ can abort the protocol, modify its result, or take actions such that some player gets to know a secret value.

A protocol is called $`𝒜`$-robust if it has all of the above properties. Note that we will allow only one collusion to cheat, but we think of every single player as being curious, i. e., even if he is not in the collusion actually cheating he will eavesdrop all information he can obtain without being detected cheating

With oblivious transfer all multi party protocols can be realized with perfect security if all players are cooperating . But a collusion of players can abort the calculation, see next section.

Classically one can avoid this problem only by introducing a new cryptographic primitive which is more powerful than oblivious transfer .

This paper analyzes three party quantum protocols and how they can cope with the problem of disruption. We prove that there are situations where a quantum channel is strictly more powerful than oblivious transfer. Together with the results of  we can conclude that the cryptographic power of a quantum channel is uncomparable to the power of oblivious transfer.

## II Impossibility of classical three party protocols

To clearly show the advantage of quantum protocols we restate the following impossibility result of .

###### Lemma 2

Let $`P`$ be a set of players for which each pair of players is connected by a (private) oblivious transfer channel and each player has access to an authenticated broadcast channel. Then $`𝒜`$-robust multi party computations are possible for all functions if and only if no two sets of $`𝒜`$ cover $`P\{P_i\}`$ for a player $`P_iP`$ or $`|P|=2`$.

The basic idea to prove this impossibility result of  is to have two possible collusions $`A_1,A_2`$ covering $`P\{P_i\}`$ (for a player $`P_i`$) where either all players from $`A_1`$ or all players from $`A_2`$ refuse to cooperate with the players of the other possible collusion. Then the single player $`P_i`$ has to assist all other players. In  it is proven that one cannot avoid that the player $`P_i`$ learns a secret.

Especially three party protocols cannot necessarily be realized robustly if every player is possibly cheating.

## III Three party protocols

If all players in a three party protocol cooperate we can use the protocols of  to implement $`𝒜`$-robust quantum multi party protocols. Hence we focus on the situation where three players (Alice, Bob, and Helen) want to perform three party protocols and Alice and Bob are in conflict. One of the two is refusing to cooperate with the other and it is unclear for Helen who is cheating.

As a first step we will introduce a bit commitment protocol for Alice and Bob. The idea is that Alice sends her quantum states via Helen and Bob does not know which quantum data is coming from Helen and which data is just forwarded by Helen. Hence Bob cannot complain without reason or he risks to be detected cheating by Helen. Forwarding information as if it were ones own without being able to eavesdrop is impossible classically. One further advantage of the protocol below is that Alice can forward all information via Helen and Bob cannot know whose information it is: An anonymous quantum channel. This way Bob cannot distinguish between commitments of Alice and “pretended” commitments of Helen. Later we want to follow this idea with larger protocols containing this bit commitment protocol as a subprotocol. Then we let Alice forward all her information via Helen.

Commit($`b`$)

FOR $`i\{1,\mathrm{},l\}`$ DO

1. Alice gives a random string $`r`$ of qubits encoded in random bases $`s`$ $`\{+,\times \}`$ to Helen.
2. Helen sends a substring to Bob interleaved with quantum states of her own. Helen tells Alice which quantum states are hers without revealing information about which substring she forwarded.
3. Bob announces to have received all quantum states. With a probability of $`1/2`$ he publishes all his measurement results.
4. Alice opens to Helen the bases she used. Now Alice is bound to the parity bit of $`r`$.

OD

1. Alice is now bound to the Xor of all quantum states (which were not measured and published by Bob) Alice announces (via Helen if needed) if this parity bit is equal to the bit $`b`$ she originally wanted to commit to.

Unveil

1. Alice opens (via Helen if necessary) all choices she made.
2. Helen and Bob check consistency.

###### Lemma 3

For $`𝒜=\{\{Alice\},\{Bob\},\{Helen\}\}`$ the above protocol realizes an $`𝒜`$-robust bit commitment for Alice which binds her to Bob and to Helen even if Alice and Bob are in conflict.

###### Proof III.1.

We say the protocol has failed if many of the quantum states measured and published by Bob do not match what Alice sent or what Helen sent. If there are only very few cases with discrepancies the protocol is considered a success.

If the protocol does not fail then the protocol is concealing to Helen. Helen has sent some substrings to Bob and as she could not know which substrings would be measured and published by Bob there are some substrings which she forwarded, but which were not tested. Hence Helen cannot measure the overall parity bit $`b`$ even after getting to know the bases. Helen cannot measure before getting to know the bases as she will be detected cheating whenever Bob measures and publishes a quantum state she disturbed.

If the protocol did not fail it is concealing to Bob unless Helen and Bob collude. This is clear as Bob does not have the complete quantum state, and can hence not measure the parity bit.

If the protocol did not fail it is binding for Alice unless she colludes with Helen, which is impossible according to our assumption.

If the protocol failed there are two cases to be considered. First, Bob published a lot of measurement results which do not match what Alice sent, but Helen was not complaining about Bob, then it is clear for Alice that Helen and Bob collude somehow, but as this is not possible according to our assumption this will not happen. The second case is that Helen complains about Bob, then Bob is identified as a cheater as every player complains about Bob.

As Alice is by the above protocol bound to Bob and Helen we have bit commitment from Alice to Bob and from Alice to Helen and from Bob to Alice and from Bob to Helen. As the quantum channel between Alice and Helen and between Bob and Helen is working we even have oblivious transfer from Helen to Alice and from Helen to Bob by forcing honest measurements with bit commitment .

###### Corollary III.2.

The above sketched oblivious transfer protocol between Alice and Helen and between Bob and Helen is $`𝒜`$-robust and becomes $`\stackrel{~}{𝒜}`$-robust after it terminated for $`𝒜=\{\{Alice\},\{Bob\},\{Helen\}\}`$ and $`\stackrel{~}{𝒜}=\{\{Alice,Bob\},\{Helen\}\}`$.

###### Proof III.3.

The bit commitment used for forcing measurments need only be shortly binding. It need only be binding until the honest measurement is performed unreversibly. Hence the collusion $`\{Alice,Bob\}`$, which would be able to violate the binding condition but not the concealing condition of the above bit commitment, cannot cheat after the measurement is performed.

Next we have to define some notions which are important for multi party protocols. Details can be looked up in .

###### Definition III.4.

A bit commitment with Xor (BCX) to a bit $`b`$ is a commitment to bits $`b_{1L}`$, $`b_{2L},\mathrm{},`$ $`b_{mL},`$ $`b_{1R},\mathrm{},`$ $`b_{mR}`$ such that for each $`i`$ $`b_{iL}b_{iR}=b`$.

The following result about zero knowledge proofs on BCX can be found in  and in references therein.

###### Theorem III.4.

Bit commitments with Xor allow zero knowledge proofs of linear relations among several bits a player has committed to using BCX. Especially (in)equality of bits or a bit string being contained in a linear code.

Furthermore BCXs can be copied, as proofs may destroy a BCX.

In a multi party scenario it is necessary that a player should be committed to all other players. In our three party case this is given by our bit commitment protocol which binds one player (Alice or Bob) to the other two. For Helen the following global bit commitment with Xor can be implemented by Corollary III.2 and the techniques used in  as she is not in conflict with anyone.

###### Definition III.5.

A global bit commitment with Xor (GBCX) is a BCX commitment from a player $`\mathrm{Alice}P`$ to all other players such that all players are convinced that Alice did commit to the same bit in all the different BCX.

###### Corollary III.6.

Zero knowledge proofs of linear relations among several GBCX are possible. Furthermore GBCX can be copied by copying the individual BCX.

On these commitments operates the committed oblivious transfer protocol, defined in  which forms the basis of our multi party protocols.

###### Definition III.7.

Given two players Alice and Bob where Alice is committed to bits $`b_0,b_1`$ and Bob is committed to a bit $`a`$. Then a committed oblivious transfer protocol (COT) is a protocol where Alice inputs her knowledge about her two commitments and Bob will input his knowledge about his commitment and the result will be that Bob is committed to $`b_a`$.

In a global committed oblivious transfer protocol all players are convinced of the validity of the commitments, i.e., that indeed Bob is committed to $`b_a`$ after the protocol.

As Helen is not actively cheating by assumption and Alice or Bob cannot complain about Helen without being expelled from the protocol we can realize GCOT from Helen to Alice and from Helen to Bob by following the protocol of . To realize GCOT from Alice to Bob is more difficult. We will do this in two steps. First we realize a subprotocol which we call subGCOT and second we will observe that all other steps can be realized easily once one round of subGCOT was successfull.

To realize subGCOT between Alice and Bob we carry out the first 7 steps of the GCOT protocol of  in a way that Bob cannot decide if the data comes from Alice or from Helen if he then complains without reason he risks to get in conflict with Helen, which would prove him cheating.

subGCOT

1. Alice randomly picks $`c_0,c_1`$ from a previously agreed on code $`𝒞`$ (for requirements on $`𝒞`$ see ) and commits to all bits of the codewords, and proves that the codewords fulfil the linear relations of $`𝒞`$ (for the zero knowledge technique used confer ).
2. Bob randomly picks $`I_0,I_1\{1,\mathrm{},M\}`$, with $`|I_0|=|I_1|=\sigma m`$ ($`\sigma `$ is a parameter of the code $`𝒞`$), $`I_1I_0=\mathrm{}`$ and sets $`b^i\overline{b}`$ for $`iI_0`$ and $`b^ib`$ for $`iI_0`$.
3. Alice runs $`\mathrm{OT}(c_0^i,c_1^i)(b^i)`$ with Bob (by  and the above bit commitment which binds Bob to Helen and Alice) who gets $`w^i`$ for $`i\{1,\mathrm{},m\}`$. Bob tells $`I=I_0I_1`$ to Alice who opens $`c_0^i,c_1^i`$ for each $`iI`$.
4. Bob checks that $`w^i=c_{\overline{b}}^i`$ for $`iI_0`$ and $`w^i=c_b^i`$ for $`iI_1`$, sets $`w^ic_b^i`$, for $`iI_0`$ and corrects $`w`$ using the code $`𝒞`$’s decoding algorithm, commits to $`w^i`$ for $`i\{1,\mathrm{},m\}`$, and proves that $`w^1\mathrm{}w^m𝒞`$.
5. All players together randomly pick a subset $`I_2\{1,\mathrm{},m\}`$ with $`|I_2|=\sigma m`$, $`I_2I=\mathrm{}`$ and opens $`c_0^i`$ and $`c_1^i`$ for $`iI_2`$.
6. Bob proves that $`w^i=c_b^i`$ for $`iI_2`$.

Alice and Helen play subGCOT with Bob in a way that Alice plays via Helen using the above bit commitment protocol and the forcing measurement technique of  such that Bob cannot distinguish between commitments/quantum states of Alice and pretended commitments/quantum states of Helen, then Bob cannot destinguish between the subGCOT protocols he plays with Alice and those which are pretended by Helen. Two cases can occur:

1. After $`l`$ trials a subGCOT protocol was successful from Alice to Bob and neither player complains. This subGCOT protocol can be used to perform GCOT from Alice to Bob, as all other steps of GCOT are not critical.
2. After $`l`$ trials no subGCOT protocol between Alice and Bob was successfull. Then, as Helen and Bob do not collude and Bob cannot distinguish between Alices and Helens data, it is clear that Alice is cheating if Bob only complained about her data and it is clear that Bob is cheating if he complained about Helen as well as Alice.

Once Alice and Bob were able to run one round of subGCOT they can complete this protocol to a GCOT protocol by the steps:

1. Alice randomly picks and announces a privacy amplification function $`h:\{0,1\}^m\{0,1\}`$ such that $`a_0=h(c_0)`$ and $`a_1=h(c_1)`$ and proves $`a_0=h(c_0^1,\mathrm{},c_0^m)`$ and $`a_1=h(c_1^1,\mathrm{},c_1^m)`$.
2. Bob sets $`ah(w)`$, commits to $`a`$ and proves $`a=h(w^1\mathrm{},w^m)`$.

Alice and Bob give their proofs (following the procedure of ) in the above steps to Helen. Hence the proofs must be correct as no one can risk to get into conflict with Helen, also convincing Helen is enough as she is not colluding with Alice or with Bob.

For the corectness of the GCOT protocol we refer to the proof in . We conclude:

###### Lemma III.8.

Even if Alice and Bob are in conflict there exists an $`𝒜`$-robust protocol for GCOT between Alice and Helen, Bob and Helen and Alice and Bob. This protocol becomes $`\stackrel{~}{𝒜}`$-robust after it terminated for $`𝒜=\{\{Alice\},\{Bob\},\{Helen\}\}`$ and $`\stackrel{~}{𝒜}=\{\{Alice,Bob\},\{Helen\}\}`$.

###### Proof III.9.

By Corollary III.2 we can have oblivious transfer from Helen to Alice and from Helen to Bob. As Helen cannot be in conflict with Alice or Bob (or a cheater can be identified) we can realize GCOT from Helen to any other player by the protocols of  with the security of the oblivious transfer channel of CorollaryIII.2.

The above protocol for GCOT between Alice and Bob is still concealing for Helen even if Alice and Bob collude, but the resulting commitments need not be binding any more. This is no problem as we allow Alice and Bob to collude only after the termination of the protocol (See comment after Theorem III.9).

From a bit commitment which can bind one player to the two other players we can realize GBCX and together with a GCOT protocol working in at least one direction between every two players we can obtain all three party protocols, see  (and  for creating a distributed bit commitment, which is needed in , in the presence of conflicts). Hence we can conclude:

###### Theorem III.9.

For three players Alice, Bob, and Helen all functions can be realized by quantum multi party protocols if two players are honest. The protocol becomes $`\{\{Alice\},\{Bob\},\{Helen\}\}\{A\}`$-secure after its execution if there is a player outside of $`A`$ nobody complained about.

Note that the bit commitment used during the protocol is not necessarily binding after Alice and Bob collude. If one wants to implement a long binding bit commitment one has to implement it as a multi party computation.

## IV A completeness Theorem for Quantum Multi Party Protocols

In the paper  quantum multi party protocols were proposed which use secret sharing to force measurements to implement oblivious transfer. Then these protocols follow  to implement multi party computations with oblivious transfer.

There was an impossibility result in  that quantum multi party protocols for all functions become impossible if two possible collusions cover the set $`P`$ of players. But due to the use of oblivious transfer this had to be weakened to the condition of Lemma 2. The impossibility result of  did not seem to be sharp. Now we can prove that the result is indeed sharp as we can implement multi party protocols even in the case not covered by :

###### Theorem IV.0.

$`𝒜`$-robust quantum multi party protocols for all functions are possible if and only if no two collusions of $`𝒜`$ cover the set $`P`$ of players.

These protocols become $`\stackrel{~}{𝒜}`$-robust after termination for an adversary structure $`\stackrel{~}{𝒜}`$ which may contain one and only one complement of a set of $`𝒜`$.

###### Proof IV.1.

If one looks at  one can see that the above theorem is proven there for all cases but one. The case left open is that two collusions $`A_1`$, $`A_2`$, covering $`P\{P_i\}`$ for a player $`P_i`$, are in conflict such that no player from $`A_1`$ can use the oblivious transfer to any player of $`A_2`$ (and vice versa).

In this case we can proceed analogously to our three party protocols. All commitments are made via $`P_i`$ (Helen) and equality of commitments is proven to Helen. This way we obtain GBCX in a way that whenever a player complains a cheater can be identified.

The GCOT protocol can be realized analogously to the above three party protocol. A player Alice $`A_1`$ runs subGCOT via Helen with a player Bob $`A_2`$ such that Bob cannot distinguish data from Helen and data from Alice. Again Bob cannot complain without either being detected cheating or proving that Alice cheats. On top of subGCOT GCOT can easily be realized. With GBCX and GCOT we can realize all multi party protocols  if one keeps in mind that distributed bit commitments can be realized without problems even when conflicts are present .

The set $`A𝒜`$, for which $`A^c`$ may be contained in $`\stackrel{~}{𝒜}`$, can in the above case be chosen to be any set containing Helen.

The set $`\stackrel{~}{𝒜}`$ can even contain more than one complement of a set of $`𝒜`$ provided Helen is not in the additional collusion. The protocol seems to be more secure than a quantum protocol where no complains were present. This is true, due to the fact that Helen becomes a trustable third party in the way that we know she is not colluding with anyone. This shows that conflicts appearing during the protocol can yield additional information which can be exploited to increase the security.

One of the ideas of this paper, namely to anonymize oblivious transfer, can also be applied to classical protocols. With the primitive of anonymous oblivious transfer all multi party protocols become possible with perfect security, and whenever a player tries to abort the protocol this player is identified or the protocol terminates correctly .


format: text

text:
# Model Calculations for Copper Clusters on Gold Electrodes

## 1 Introduction

During the last two decades, the scanning tunneling microscope (STM) has become a versatile tool for the investigation of conducting surfaces. It has not only been used for obtaining images with atomic resolution, but also for the modification of the surface structure. In particular, experimental procedures have been developed for the deposition of small metal clusters on surfaces. In this respect electrochemical interfaces are particularly suited for a controlled modification of surfaces, since two potential differences can be varied independently: the bias between the electrode and the STM tip, and the electrode potential with respect to a reference electrode. Thus, Kolb et al.  have been been able to deposit small copper clusters on the surface of Au(111) electrodes by first depositing copper on the STM tip and subsequently bringing the tip in contact with the surface. This deposition can be controlled with great precision, and has given rise to speculations about possible applications in nanotechnology. Recently, these copper clusters have attracted further attention because they appear to be stable at electrode potentials at which bulk copper dissolves, an effect which has been attributed to quantum confinement .

Since these copper clusters on Au(111) have become to be considered as a prototype for electrochemical surface modifications, we have performed model calculations for clusters of various sizes and shapes within the embedded atom method. An important characteristic of the Cu/Au(111) system is the fact that before the formation of the cluster, which is performed at potentials slightly above the deposition potential for bulk copper, the electrode is already covered with an epitaxial monolayer of copper atoms. Obviously, this must be taken into account if the calculations are to be meaningful.

## 2 Calculation method

Since we are dealing with metallic systems comprising a large number of atoms, we require a calculation method that allows the treatment of large systems, but without missing the important many-body properties of metallic binding. In this respect, the embedded-atom method (EAM) as proposed by Daw and Baskes  appears as the natural choice. This model for the interaction between metallic atoms in condensed phases gives a much better description of the metallic bond than pair potentials which do not take into account many-particle effects.

Within the embedded-atom method the total energy $`E_{tot}`$ of an arrangement of $`N`$ metal particles is calculated as the sum of individual particles energies $`E_i`$:

$$E_{\mathrm{tot}}=\underset{i=1}{\overset{N}{}}E_i\text{where}E_i=F_i(\rho _{h,i})+\frac{1}{2}\underset{ji}{}V_{ij}(r_{ij})$$
(1)
$`F_i`$ is the embedding function and represents the energy necessary to embed atom $`i`$ into the electronic density $`\rho _{h,i}`$. The latter quantity is calculated at the position of atom $`i`$ as the superposition of the individual atomic electronic densities $`\rho _i(r_{ij})`$ of the other particles in the arrangement:

$$\rho _{h,i}=\underset{ji}{}\rho _i(r_{ij})$$
(2)
The attractive contribution to the energy is given by the embedding function $`F_i`$, which contains the many-body effects. The repulsive interaction between ion cores is represented as a radial pair potential $`V_{ij}(r_{ij})`$, which takes the form of a pseudocoulombic repulsive energy:

$$V_{ij}=\frac{Z_i(r_{ij})Z_j(r_{ij})}{r_{ij}}$$
(3)
where $`Z_i(r_{ij})`$ may be considered as an effective charge which depends upon the nature of particle $`i`$.

We have employed two different versions of EAM potentials. On one hand, we have used the original parameterization of Foiles et al  (denoted FDB), which is based on experimental data of pure metals and of several alloys, so as to reproduce such parameters as equilibrium lattice constants, sublimation energies, bulk moduli, elastic constants, vacancy formation energies, and heats of solution. On the other hand, we have used a potential specifically devised by Barrera et al.(denoted BTI) to describe the structure and energetics of Cu-Au alloys.

## 3 Results and discussion

### 3.1 Energetics of copper islands

The clusters generated by electrochemical STM techniques come in various forms and sizes. In this section we focus on flat islands that are only a few monolayers thick. In order to explore the energetics of such clusters we have performed static calculations within the embedded-atom scheme, and assumed a commensurate structure.

Both the energy of adsorption per atom in the bulk of the cluster and edge effects are of interest. In order to separate the two, we have adapted the drop model  that is often used for the calculation of surface energies to the two-dimensional situation.

In order to calculate properties for a Cu island adsorbed on a surface, we use a two-dimensional version of the drop model. Thus, we split the energy of a two-dimensional cluster into a bulk and a surface contribution; for a circular cluster we may write:

$$E=4\pi R^2e_s+2\pi Re_l$$
(4)
where $`R`$ is the radius of the cluster, $`e_s`$ the energy per unit surface of the cluster, and $`e_l`$ the energy per unit boundary length. Rearrangement gives:

$$\frac{E}{\pi R}=e_s+\frac{2}{R}e_l$$
(5)
so that the two contributions $`e_s`$ and $`e_l`$ can be determined by a plot of the total system energy $`E`$ vs. $`1/R`$. However, such a plot gave a fair scattering of data particularly for small clusters, where the deviations from the spherical shape are noticeable. We have therefore modified eq. (4) a little and written:

$$E=u_sn_s+u_ln_l$$
(6)
where $`u_s`$ and $`u_l`$ denote the energy per bulk atom and per boundary atom, respectively, and $`n_s`$ and $`n_l`$ denote the numbers of bulk and of boundary atom. Rearrangement now leads to:

$$\frac{E}{n_t}=u_s+\left(u_lu_s\right)\frac{n_l}{n_t}$$
(7)
where $`n_t=n_s+n_l`$ is the total number of atoms in the cluster.

A typical plot of $`E/n_t`$ vs. $`n_l/n_t`$ is shown in Fig. 1. The fit to a straight line is excellent, so that both the bulk adsorption energy $`u_s`$ and the quantity $`\mathrm{\Delta }u_{\mathrm{step}}=\left(u_lu_s\right)`$, which is the energy required to form a step atom from a bulk atom, can be determined with good accuracy. A few results are shown if Fig. 2; they have been obtained both with the BTI and with the FDB potentials, which here give quite similar results.

The adsorption energy $`u_s`$ per bulk atom is highest for the cluster that is one monolayer high, where all the copper atoms are bonded directly to the gold surface. For clusters that are two or three layers high, the adsorption energies are the same within the accuracy of the calculation. In contrast, the energy for step formation is lowest for the monolayer, indicating that the Cu-Cu bond is weakened by the stronger Cu-Au bond. The energy per atom required to form a double step is particularly large, so that clusters of pyramidal shape are favored. These results bear witness to the fact that in metallic bonding the bond energies are not additive.

Because of the circular geometry assumed for the Cu island, calculations for step formation of figures 2a-2c correspond to an average over different orientations on the surface. Calculations can also be performed for different directions on the surface, as shown in figure 2d. As expected, the step formation energy is lower for the formation of more compact steps, so these should predominate.

The step-formation energy is difficult to measure, but estimates can be obtained from the growth and the stability of copper clusters. Xia et al.  estimate the step energy to be of the order of 0.4 to 0.5 eV, which is quite in line with our calculations.

### 3.2 Atom dynamics simulations

In order to explore structures that are not necessarily commensurate with the Au(111) substrate, we performed molecular-dynamics simulations within the embedded-atom scheme. At first, we tested the two different potentials employed in this work and performed calculations for a Cu monolayer adsorbed on Au(111). The system consisted of a slab of Au atoms eight layers thick, four of them mobile, covered with a Cu layer. Each of these layers consisted of 196 atoms; cyclic boundary conditions were imposed parallel to the surface. For the the interactions between the particles a cut-off radius of 7 Å was employed. The time step was set at 0.2 fs, and the simulations ran over 4 ns.

Although the energetic predictions of the two parameterizations employed here are very similar, as shown in the previous section, they result in rather different structures for the adsorbed Cu monolayer. In the case of the FDB potentials the monolayer is compressed, leading to holes and domains with an incommensurate structure (see Fig. 3a). In contrast, the BTI potentials, which are based on data for Cu-Au alloys, predict a commensurate $`(1\times 1)`$ structure, which correspond to the experimental observation in the electrochemical system (see fig. 3b). It is worth mentioning that although both structures show strong differences while observed in direct space, the Fourier transforms of the corresponding averaged atomic densities lead to a hexagonal pattern with the same lattice parameter, with considerably more diffuse spots in the case of the FDB potentials. Because of its better agreement with the experimental finding, we shall use only the BTI potentials in the following simulations. However, the tendency of the copper atoms to form compressed structures is real – it is caused by the shorter lattice constant of bulk copper – and will also be found in the simulations with the BTI potentials reported below.

To investigate the properties of copper clusters adsorbed on a Au(111) surface we have performed atom dynamics simulations with Cu clusters containing between 55 and 125 atoms with different starting configurations such as a cylindrical or an inverted pyramidal structure; typical runs lasted between 4 ns and 10 ns. Since a full statistical analysis requires a higher number of runs than we have undertaken so far, we shall only give here some representative results which show the main features of the investigated system.

Figure 4 shows the atomic arrangement for a Cu cluster that is 7-layers high. The pyramidal structure is favored by the step energies (see previous section) and was obtained with various starting configurations. Is is instructive to consider the time-averaged atomic density as a function of the distance perpendicular to the surface (Fig. 4b). The decreasing height of the peaks and their decreasing area reflect the pyramidal structure of the cluster. Note that the peaks become broader with increasing distance, since the atoms in the top layers are more mobile. An analysis of the distance between lattice planes yields values in the range of 2.00 to 2.02 Å for the Cu planes closer to the surface. In bulk copper the distance between lattice planes in the (111) direction is 2.09 Å, so the clusters are somewhat contracted. This is understandable in terms of bond order arguments: The lower coordination of the atoms at the boundary of the layer yields a stronger binding between the layers, with a concomitant lowering of the interlattice distance.

The presence of a cluster induces a rearrangement of the copper monolayer underneath. In fact, several atoms initially belonging to the cluster are incorporated into the monolayer during the simulations, making it more compact after equilibration. This effect is illustrated in fig. 5, where a cluster is shown along with the structure of the Cu monolayer in contact with the Au(111) surface. The presence of the cluster strongly distorts the monolayer and creates dislocations.

The compression of the monolayer can be quantitatively expressed through the average distance to the nearest neighbors. Figure 5c shows a corresponding contour plot for the copper atoms in the monolayer. The data were obtained by averaging the distance of each particle to its nearest neighbors, and by further averaging over 1000 time steps. It is evident that the presence of the cluster produces a dramatic decrease of the nearest-neighbor distance in the monolayer; the minimal values are around 2.67 Å, which is somewhat larger than the value for bulk copper (2.55 Å), but much smaller than the distance between Au atoms on the Au(111) surface (2.88 Å). Figure 5c also reveals the shape of the basis of the cluster, which resembles that of a truncated equilateral triangle. This can be understood as follows: According to the static calculations of the previous sections, steps should preferentially occur in the more compact $`<110>`$ directions. Two kinds of facets arise in these directions, which depending on their structure are usually denoted as {111} and {100} faces, respectively . These facets originate the growth of faces of pyramids that resemble the (111) and (100) fcc faces respectively, which are known to have different surface energies. Since the embedded atom method predicts, in qualitative agreement with experiment, a lower surface energy for the (111) surface, this is the facet that is expected to predominate, and the pyramids should exhibit hexagonal bases, where the sides corresponding to the {111} facets should be considerably larger than those of the {100} facets.

The clusters generated by these simulations are stable within the time that can reasonably be covered in a simulation. They are not stable in an absolute sense since it would generally be favorable to spread them out into a monolayer. However, real copper clusters, if they are chemically pure, should also be in a metastable state, since the average binding energy in a cluster is always less than that of the bulk material. Electrochemical experiments with such clusters are usually performed in sulphate solutions; in the region near the equilibrium potential for the Cu/Cu2+ system copper is covered by a layer of adsorbed sulphate ions, which may increase their stability.

## 4 Conclusions

The embedded-atom method, which we have employed, is particularly suited to treat large ensembles of metal atoms; both static and dynamic calculations can be performed with relative ease . Since the interaction parameters have been fitted to experimental data, we expect the method to give qualitatively correct results and to provide good estimates for binding and step-formation energies. We think that our results for copper on Au(111) are encouraging, and that the method can be applied to similar systems and give valuable information about the properties of metal clusters on metal electrodes.

Our calculations do not explain the extra stability of copper clusters observed by Kolb et al. . However, our method is not suited to investigate quantum confinement, which these authors believe to be the cause of this effect. On the other hand, metal dissolution is a comparatively slow process: it involves the solvation of the dissolved ion, and thus requires $`10^{12}10^{11}`$ s. On this timescale, the copper clusters can freely exchange electrons with the underlying substrate. The very fact that these clusters can be imaged with the STM shows that such an exchange occurs without a major hindrance. Therefore the explanation for this stability has to be sought elsewhere. Preliminary energetic considerations with the present calculation method, indicate that the admixture of gold to copper clusters may improve their stability. This will be the subject of further investigations.

### Acknowledgment

Financial support by the DAAD, the Deutsche Forschungsgemeinschaft, and by Fundación Antorchas is gratefully acknowledged. E.P.M.L. and M.G. D.P. thank CONICET, CONICOR, Secyt UNC and Program BID 802/OC-AR PICT No 06-04505 for financial support.

## Figures

* Binding energy per atom for a Cu island adsorbed on a clean Au(111) surface as a function of the fraction of atoms that belong to the border of the island.
* Energy per surface atom $`u_s`$ and energy required to generate an atom at a step from an atom on the surface of the island $`\mathrm{\Delta }u_{\mathrm{step}}`$ for several systems. FDB denotes the results obtained with the potentials of Foiles et al.  and BTI indicates the corresponding results with the potentials of Barrera et al.. An island with circular shape was assumed in all cases. (a) Cu island on Au(111). (b) Cu island on a pseudomorphic layer of Cu adsorbed on Au(111). (c) Two-atom high Cu island on a pseudomorphic layer of Cu adsorbed on Au(111). (d) Step formation energy for different directions on the surface. The calculations were performed with the BTI potentials.
* Final structures obtained after 4 ns in an atom-dynamics simulation for a Cu monolayer adsorbed on Au(111). (a) Potentials of Foiles et al. (FDB) ; (b) potentials of Barrera et al. (BTI) .
* Atomic arrangement (a), and Cu atom density (b) as a function of the distance perpendicular to the surface for a 7-layers high Cu cluster formed on a Au(111) surface.
* Compression of the Cu monolayer induced by the presence of a cluster. (a) Atomic arrangement of the cluster. (b) Structure of the Cu layer in contact with the Au(111) surface. (c) Contour plot of the distance between nearest neighbors in the Cu monolayer. The contour lines start at a distance of 2.65 Å, are separated by 0.05 Å, and end at 2.95 Å. The geometric arrangement is shown for comparison.


text:
# Lattice gauge theory: A retrospective

## 1 Introduction

I am honored to have this opportunity to give the final talk at this wonderful meeting. I was originally asked to talk about “Lattice gauge theory: past, present, and future.” Well, I really don’t know much about the future, and if I did, I would be out trying to develop the ideas. As for the present, well you have for the last few days been hearing all about it, and there is too much for me to usefully review anyway. Thus the majority of this talk will refer back to the early days. I will try to recall the conditions that drove us to this peculiar approach to regularizing quantum field theory.

## 2 Particle physics in the late 60’s

I begin by summarizing the situation in particle physics in the late 60’s, when I was a graduate student. Quantum-electrodynamics had already been immensely successful, but the basic theory was in some sense “done.” While hard calculations remained, and indeed still remain, there was no major conceptual advance remaining.

These were the years when the “eightfold way” for describing multiplets of particles had recently gained widespread acceptance. The idea of “quarks” was around, but with considerable caution about assigning them any physical reality; maybe they were nothing but a useful mathematical construct. A few insightful theorists were working on the weak interactions, and the basic electroweak unification was beginning to emerge. The SLAC experiments were observing substantial inelastic electron-proton scattering at large angles, and this was interpreted as evidence for substructure, with the term “parton” coming into play. While occasionally there were speculations relating quarks and partons, people tended to be rather cautious about pushing this too hard.

A crucial feature at the time was that the extension of quantum electrodynamics to a meson-nucleon field theory was failing miserably. The analog of the electromagnetic coupling had a value about 15, in comparison with the 1/137 of QED. This meant that higher order corrections to perturbative processes were substantially larger than the initial calculations. There was no known small parameter in which to expand.

In frustration over this situation, much of the particle theory community set aside traditional quantum field theoretical methods and explored the possibility that particle interactions might be completely determined by fundamental postulates such as analyticity and unitarity. This “S-matrix” approach raised the deep question of just “what is elementary.” A delta meson might be regarded as a combination of a proton and a pion, but it would be just as correct to regard the proton as a bound state of a pion with a delta. Furthermore, the particles were all bound together by exchanging themselves. These “dual” views of the basic objects of the theory persist today in string theory.

## 3 The early 70’s

As we entered the 1970’s, partons were increasingly identified with quarks. This shift was pushed by two dramatic theoretical accomplishments. First was the proof of renormalizability for non-Abelian gauge theories , giving confidence that these elegant mathematical structures  might have something to do with reality. Second was the discovery of asymptotic freedom, the fact that interactions in non-Abelian theories become weaker at short distances . Indeed, this was quickly connected with the pointlike structures hinted at in the SLAC experiments. Out of these ideas evolved QCD, the theory of quark confining dynamics.

The viability of this picture depended upon the concept of “confinement.” While there was strong evidence for quark substructure, no free quarks were ever observed. This was particularly puzzling given the nearly free nature of their apparent interactions inside the nucleon. This returns us to the question of just “what is elementary.” Are the physical particles we see in the laboratory the fundamental objects or are they these postulated quarks and gluons?

Struggling with this paradox led to the now standard flux tube picture of confinement. The gluonic fields are analogues of photons except that they carry “charge” with respect to eachother. Massless charged particles are rather singular objects, leading to a conjectured instability that removes zero mass gluons from the spectrum, but does not violate Gauss’s law. A Coulombic $`1/r^2`$ field is a solution of the equations of a massless field, but, without massless particles, such a spreading of the gluonic flux is not allowed. The field lines from a quark cannot end, nor can they spread in the inverse square law manner. Instead, as in Fig. 1, the flux lines cluster together, forming a tube of flux emanating from the quark and ultimately ending on an antiquark. This tube is a real physical object, and grows in length as the quark and antiquark are pulled apart. The resulting force is constant at long distance, and can be determined from the slope of the famous “Regge trajectories.” In physical units, it has a strength of about 14 tons.

The reason a quark cannot be isolated is similar to the reason that a piece of string cannot have just one end. Of course one can’t have a piece of string with three ends either, but this is the reason for the underlying $`SU(3)`$ group theory. The confinement phenomenon cannot be seen in perturbation theory; when the coupling is turned off, the spectrum becomes free quarks and gluons, dramatically different than the pions and protons of the interacting theory.

## 4 The mid 70’s revolution

We then entered a particularly exciting time for particle physics, with a series of dramatic events revolutionizing the field. First was the discovery of the $`J/\psi `$ particle . The interpretation of this object and its partners as bound states of heavy quarks provided the hydrogen atom of QCD. The idea of quarks became inescapable; field theory was reborn. The $`SU(3)`$ non-Abelian gauge theory of the strong interactions combined with the electroweak theory became the durable “standard model.”

This same period also witnessed several remarkable realizations on a more theoretical front. Non-linear behaviors in various classical field theories were shown to have deep consequences for their quantum counterparts. Classical “lumps” represented a new way to get particles out of a quantum field theory . Much of the progress here was in two dimensions, where techniques such as “bosonization” showed equivalences between theories of drastically different appearance. A boson in one approach might appear as a bound state of fermions in another, but in terms of the respective Lagrangian approaches, they were equally fundamental. Again, we were faced with the question “what is elementary?” Of course modern string theory is discovering multitudes of “dualities” that continue to raise this same question.

The discovery of such phenomena had deep implications: field theory can have much more structure than seen from a Feynman diagram analysis alone. But this in turn had crucial consequences for practical calculations. Field theory is notorious for divergences requiring regularization. The bare mass and charge entering the theory are infinite quantites. They are not the physical observables, which must be defined in terms of physical processes. To carry out calculations, a “regulator” is required to tame the divergences, and when physical quantities are related to each other, any regulator dependence should drop out.

The need for controlling infinities had, of course, been known since the early days of QED. But all regulators in common use were based on Feynman diagrams; the theorist would calculate diagrams until one diverged, and that diagram was then cut off. Numerous schemes were devised for this purpose, ranging from the Pauli-Villars approach to forest formulae to dimensional regularization. But with the increasing realization that non-perturbative phenomena were crucial, it was becoming clear that we needed a “non-perturbative” regulator, independent of diagrams.

## 5 The lattice

The necessary tool appeared through Wilson’s lattice theory. Wilson presented this as an example of a model with confinement. The strong coupling expansion had a finite radius of convergence, allowing a rigorous demonstration of confinement, albeit in an unphysical limit. The resulting spectrum had exactly the desired properties; only gauge singlet bound states of quarks and gluons could move.

This was not the first time that the basic structure of lattice gauge theory had been written down. A few years earlier, Wegner  presented a $`Z_2`$ lattice gauge model as an example of a system posessing a phase transistion but not exhibiting any local order parameter. In his thesis, Jan Smit  described using a lattice regulator to formulate gauge theories outside of perturbation theory. The time was clearly ripe for the development of such a regulator. Very quickly after Wilson’s suggestion, Balian, Drouffe, and Itzykson  explored an amazingly wide variety of aspects of these models.

To reiterate, the primary role of the lattice is to provide a non-perturbative cutoff. Space is not really meant to be a crystal, the lattice is a mathematical trick. It provides a minimum wavelength through the lattice spacing $`a`$, i.e. a maximum momentum of $`\pi /a`$. Path summations become well defined ordinary integrals. By avoiding the convergence difficulties of perturbation theory, the lattice provides a rigorous route to the definition of quantum field theory.

The approach, however, had a marvelous side effect. By discreetly making the system discrete, it becomes sufficiently well defined to be placed on a computer. This was fairly straightforward, and came at the same time that computers were rapidly growing in power. Indeed, numerical simulations and computer capabilities have continued to grow together, making these efforts the mainstay of lattice gauge theory.

## 6 What is a gauge theory?

The Wilson theory very naturally extends the concept of a gauge theory to the lattice. To expand on this I digress into a few of the “definitions” of a gauge theory. Indeed, there are many, and the lattice approach is closely tied to most.

At the simplest level, a gauge theory is nothing but a generalization of electromagnetism to include an internal symmetry, i.e. the gauge fields are given an “isospin-like” quantum number. Both on the lattice and in the continuum the internal symmetry of the strong gauge field is $`SU(3)`$. Through this extension the gluons acquire charges with respect to each other. Infrared difficulties with massless charged particles lie at the root of the confinement phenomenon.

A common interpretation of a gauge theory is as a dynamics with an exact local symmetry. The action should be invariant under a gauge transformation, such as the familiar

$$Ag^{}Ag+ieg^{}g$$

This definition is appealing in that it directly extends to gravity, where the basic equations are invariant under local coordinate changes. This symmetry also immediately applies exactly to the plaquette form of the Wilson lattice gauge action. The only difference between electromagnetism and the strong interactions is that the fundamental variables are generalized from a simple $`U(1)`$ for photons to the internal $`SU(3)`$ symmetry group with eight gluons.

Another point of view considers a gauge theory directly as a theory of phases. The interaction of an electron with the electromagnetic field appears through its wave function acquiring a phase

$$\psi \mathrm{exp}(ie_x^yA^\mu 𝑑x_\mu )\psi $$

where the gauge field is integrated along the path traversed by the particle. In the rest frame of the particle, this is simply the statement that the oscillation frequency, or energy, is increased by the vector potential, i.e. $`EE+eA_0`$. A particularly nice thing about this interpretation is that it easily generalizes to non-Abelian theories; one just replaces the word “phase” with “matrix” taken from the appropriate group. For the strong interations this is the group $`SU(3)`$, where the 3 comes from the requirement of 3 quarks making a proton.

Wilson’s formulation directly implements a theory of phases on the lattice. The basic variables are phases associated with the links of a lattice. One such variable is associated with every link connecting a nearest neighbor pair. For the strong interactions they are elements of $`SU(3)`$. The bond variables are directed, reversing the order of two neighbors gives the inverse matrix.

For completeness let me mention one elegant definition of a gauge theory that does not translate particularly well onto the lattice. This concept was pushed some time ago by Weinberg , and looks for interactions in quantum field theory where one is forced to involve fields that do not transform simply under Lorentz transformations. Instead, when one does such a transformation, one must allow for the possibility of a gauge change. This point of view also applies to gravity, where the local formulation requires introducing Christoffel symbols, the analogue of the gauge potentials. That these ideas do not formulate well on the lattice is a consequence of the strong breaking of Lorentz invariance by the lattice regulator.

## 7 Parameters

The way the link matrices are combined to form the Wilson action is well known to this audience, so I won’t pursue it here. I do, however, want to reiterate one of the most remarkable aspects of this theory, the paucity of adjustable parameters. To begin with, the lattice spacing itself is not an observable. We are using the lattice to define the theory, and thus for physics we are interested in the continuum limit $`a0`$. Then there is the coupling constant, which is also not a physical parameter due to the phenomenon of asymptotic freedom. The lattice works directly with a bare coupling, and in the continuum limit this should vanish

$$e_0^20$$

In the process, the coupling is replaced by an overall scale for this vanishing. Coleman and Weinberg  gave this phenomenon the marvelous name “dimensional transmutation.” Of course an overall scale is not really something we should expect to calculate from first principles. Its value would depend on the units chosen, be they furlongs or light-fortnights.

Next consider the quark masses. Indeed, measured in units of the asymptotic freedom scale, these are the only free parameters in the strong interactions. Their origin remains one of the outstanding mysteries of particle physics. The massless limit gives a rather remarkable theory, one with no undetermined dimensionless parameters. This limit is not terribly far from reality; chiral symmetry breaking should give massless pions, and experimentally the pion is considerably lighter than the next non-strange hadron, the rho. A theory of two massless quarks is a fair approximation to the strong interactions at intermediate energies. In this limit all dimensionless ratios should be calculable from first principles, including quantities such as the rho to nucleon mass ratio.

The strong coupling at any physical scale is not an input parameter, but should be determined. Such a calculation has gotten lattice gauge theory into the famous particle data group tables; see Fig.3. With appropriate definition the current result is

$$\alpha _s(M_Z)=0.115\pm 0.003$$

where the input is details of the charmonium spectrum.

## 8 Numerical simulation

Of course, as this audience is intimately familiar, large scale numerical simulations have come to dominate the field. They are based on attempts to evaluate the path integral

$$Z=𝑑Ue^{\beta S}$$

A direct evaluation of such an integral has pitfalls. At first sight, the basic size of the calculation is overwhelming. Considering a $`10^4`$ lattice, small by today standards, there are 40,000 links. For each is an $`SU(3)`$ matrix, parametrized by 8 numbers. Thus we have a $`10^4\times 4\times 8=320,000`$ dimensional integral. One might try to replace this with a discrete sum over values of the integrand. If we make the extreme approximation of using only two points per dimension, this gives a sum with

$$2^{320,000}=3.8\times 10^{96,329}$$

terms! Of course, computers are getting pretty fast, but one should remember that the age of universe is only $`10^{27}`$ nanoseconds.

These huge numbers suggest a statistical treatment. Indeed, the integral in Eq. 8 is formally just a partition function. Consider a more familiar statistical system, such as a glass of Kingfisher. There are a huge number of ways of arranging the atoms of carbon, hydrogen, oxygen, etc. that still leaves us with a glass of Kingfisher. We don’t need to know all those arrangements, we only need a dozen or so “typical” glasses to know all the important properties.

This is the basis of the Monte Carlo approach. The analogy with a partition function and the role of $`\frac{1}{\beta }`$ as a temperature enables the use of standard techniques to obtain “typical” equilibrium configurations, where the probability of any given configuration is given by the Boltzmann weight

$$P(C)e^{\beta S(C)}$$

For this we use a Markov process, making changes in the current configuration

$$CC^{}\mathrm{}$$

biased by the desired weight.

The idea is easily demonstrated with the example of $`Z_2`$ lattice gauge theory . For this toy model the links are allowed to take only two values, either plus or minus unity. One sets up a loop over the lattice variables. When looking at a particular link, calculate the probability for it to have value $`1`$

$$P(1)=\frac{e^{\beta S(1)}}{e^{\beta S(1)}+e^{\beta S(1)}}$$

Then pull out a roulette wheel and select either 1 or $`1`$ biased by this weight. Lattice gauge Monte-Carlo programs are by nature quite simple. They are basically a set of nested loops surrounding a random change of the fundamental variables. Fig. 4 shows the results of my first simulation of this model.

## 9 Selected accomplishments

Of course this entire meeting is about the accomplishments of the technique. The results have been fantastic, giving first principles calculations of interacting quantum field theory. I will just mention two examples. The early result that bolstered the lattice into mainstream particle physics was the convincing demonstration of the confinement phenomenon. The force between two quark sources indeed remains constant at large distances. A summary of this result is shown in Fig. 5, taken from Ref. .

Another accomplishment for which the lattice excels over all other methods has been the study the deconfinement of quarks and gluons into a plasma at a temperature of about 170–190 Mev. Indeed, the lattice is a unique quantitative tool capable of making precise predictions for this temperature. The method is based on the fact that the Euclidean path integral in a finite temporal box directly gives the physical finite temperature partition function, where the size of the box is proportional to the inverse temperature. This transition represents a loss of confining flux tubes in a background plasma. Fig. 6 shows a recent calculation of this transition .

## 10 Quarks

While the gauge sector of lattice gauge theory is in good shape, from the earliest days fermionic fields have caused annoying difficulties. Actually there are several apparently unrelated fermion problems. The first is an algorithmic one. The quark operators are not ordinary numbers, but anticommuting operators in a Grassmann space. As such the exponentiated action itself is not a number but rather an operator. This makes comparison with random numbers problematic.

Over the years various clever tricks for dealing with this problem have been developed; we have seen numerous large scale Monte Carlo simulations involving dynamical fermions. The algorithms used are all essentially based on an initial analytic integration of the quarks to give a determinant. This, however, is the determinant of a rather large matrix, the size being the number of lattice sites times the number of fermion field components, with the latter including spinor, flavor, and color factors. In my opinion, the algorithms working directly with these large matrices remain quite awkward. I often wonder if there is some more direct way to treat fermions without the initial analytic integration.

The algorithmic problem becomes considerably more serious when a chemical potential generating a background baryon density is present. In this case the required determinant is not positive; it cannot be incorporated as a weight in a Monte Carlo procedure. This is particularly frustrating in the light of striking predictions of superconducting phases at large chemical potential . This is perhaps the most serious unsolved problem in lattice gauge theory.

The other fermion problems concern chiral issues. There are a variety of reasons that such symmetries are important in physics. First is the light nature of the pion, which is traditionally related to the spontaneous breaking of a chiral symmetry expected to become exact as the quark masses go to zero. Second, the standard model itself is chiral, with the weak bosons coupling to chiral currents. Third, the idea of chiral symmetry is frequently used in the development of unified models as a tool to prevent the generation of large masses and thus avoid fine tuning.

Despite its importance, chiral symmetry and the lattice have never fit particularly well together. I regard this as evidence that the lattice is trying to tell us something deep. Indeed, the lattice fully regulates the theory, and thus all the famous anomalies must be incorporated explicitly. It is well known that the standard model is anomalous if either the quarks or leptons are left out, and this feature must appear in any valid formulation.

These issues are currently a topic with lots of activity . Several schemes for making chiral symmetry more manifest have been developed, with my current favorite being the domain-wall formulation, where, as sketched in Fig. 7 our four dimensional world is an interface in an underlying five dimensional theory.

## 11 My Pet Problems

As I said at the beginning, I do not know what areas will dominate lattice gauge theory in the future. Thus let me conclude by mentioning some problems that particularly interest me. These are all directly connected with the problems of quarks discussed in the previous section.

The first is the chiral symmetry problem, alluded to above. Here the recent developments have put parity conserving theories, such as the strong interactions, into quite good shape. The various schemes, including domain-wall fermions, the overlap formula, and variants on the Ginsparg-Wilson relation, all quite elegantly give the desired chiral properties. Chiral gauge theories themselves, such as the weak interactions, are not yet completely resolved, but the above techniques appear to be tantilizingly close to giving a well defined lattice regularization. It is still unclear whether the lattice regularization can simultaneously be fully finite, gauge invariant, and local. I expect these issues to be a major topic of continuing research and look forward to the final resolution.

Chiral symmetry should be expected to have a considerably broader impact on particle physics in the future. The problems encountered are closely related to similar issues with supersymmetry, another area that does not naturally fit on the lattice. This also ties in with the explosive activity in string theory and a possible regularization of gravity.

The other area in particular need of advancement lies in dynamical fermion methods. As I said earlier, I regard all existing algorithms as frustratingly awkward. This, plus the fact that sign problem with a background density remains completely unsolved, suggests that new ideas are needed. It has long bothered me that we treat fermions and bosons so differently in numerical simulations. Indeed, why is it that we have to treat them separately?


text:
# Theory of the Quantum Speed Up

## I Premise

The quantum algorithms are sometimes faster than their classical counterparts. We show that this quantum speed-up results from a succession of entanglement and disentanglement, the former due to dynamical quantum-parallel computation, the latter to the extra-dynamical projection of quantum measurement. Thus the quantum speed-up implies irreversibility.

Some standard notions concerning problem solving must be modified to understand the speed-up. Standard problem solving has three stages:

* State the problem. This defines the problem solution, usually implicitly. E.g. consider the problem of finding two primes $`x,y`$ (unknown) such that $`xy=c`$ (known). This equation implicitly defines the values of $`x`$ and $`y`$ which satisfy it. An implicit definition does not represent the process required to compute the solution.
* Program the computation. Change the implicit definition into an explicit, finite step-by-step logical procedure for constructing the solution. This procedure is specified by the solution algorithm.
* Run the program. The execution is dynamical in character. By dynamics we mean, here and in the following, deterministic dynamics***Classical nondeterministic computation, at the current fundamental level, will be seen as pseudorandom deterministic computation..

The standard assumption is that the solution of a problem must be computed by a dynamical development. Step (ii) changes a definition which does not represent a dynamical process, into one which represents it.

Quantum computation does not fit this scheme, as we will see in the next Section.

## II The speed-up in Shor’s algorithm

Consider Shor’s algorithm . The problem is to efficiently find the period $`r`$ of a hard-to-reverse function $`f(x)`$ from $`\{0,1\}^n`$ to $`\{0,1\}^n`$. Fig. 1 gives the algorithm block diagram.

Fig. 1

$`H`$ is the Hadamard and $`F`$ the digital Fourier transform, $`M`$ denotes measurement of a register content. We need to consider only two steps of the algorithm (see Castagnoli et al., ).

* The process of computing $`f(x)`$ for all possible $`x`$, in quantum superposition, puts two n-qubit registers $`X`$ and $`F`$ into the state Quantum theory can be formulated praxically or ontically. The former (for example, Finkelstein ) is closest to Heisenberg’s. It deals with operators dispensing with states. The ontic formulation makes quantum theory seem less time-symmetrical than it really is. In the present theory, it makes the speed-up seem to happen all at once at the end of computation. We use the ontic formulation here, misleading as it is, because it is more familiar to most physicists.

$`|\psi ,t_2_{XF}={\displaystyle \frac{1}{\sqrt{N}}}{\displaystyle \underset{x}{}}|x_X|f\left(x\right)_F,`$

$`x`$runs over $`0,1,\mathrm{},N1,`$ with $`N=2^n.`$

* Let $`\left[F\right]`$ be the content of register $`F`$, an observable. Measuring $`\left[F\right]`$ in $`|\psi ,t_2_{XF}`$ This intermediate measurement can be skipped, but we will show that this makes no difference. and finding the result $`\overline{f}`$ yields the state

$`|\psi ,t_3_{XF}=k\left(|\overline{x}_X+|\overline{x}+r_X+|\overline{x}+2r_X+\mathrm{}\right)|\overline{f}_F;`$

$`k`$ is for normalization, $`f(\overline{x})=f(\overline{x}+r)=\mathrm{}=\overline{f}.`$

The transition from $`|\psi ,t_2_{XF}`$ to $`|\psi ,t_3_{XF}`$ obeys the quantum principle:

* measuring an observable is extra-dynamically represented by projection on the eigenspace of one eigenvalue;
* this eigenvalue is selected at random according to the square of the probability amplitudes.

If $`Q`$ and $`Q^{^{}}`$ are the projection operators on the state just before and after the measurement $`M`$, and $`P`$ is the projection operator for the observed value of the function, then classically $`Q^{^{}}=Q`$, while quantally $`Q^{^{}}=PQP`$ (up to normalization), depending on both $`P`$ and $`Q`$.

Thus, selecting $`\overline{f}`$ projects into the post-measurement state all and only those tensor products of $`|\psi ,t_2_{XF}`$ ending with $`|\overline{f}_F`$. Point (A) of the quantum principle, by selecting one eigenvalue, imposes a logical constraint on the output of computation. Because of this constraint, quantum measurement filters, out of an exponentially larger superposition, all and only those values of $`x`$ whose function is that eigenvalue.

Therefore quantum measurement performs extra-dynamically a computation crucial for finding $`r`$, which is “readily” extracted out of $`|\psi ,t_3_{XF}`$. Measurement time is linear in the number of qubits of register $`F`$, and is independent of the entanglement between $`X`$ and $`F`$, which holds problem complexity. Disentanglement comes for free, as a by-product of quantum measurement.

Filtration, together with function evaluation, is essential to speed-up. This can be better seen by comparing step by step quantum and classical computation times§§§Classical time is that required to derive the symbolic description of a quantum state (e.g. $`|\psi ,t_2_{XF}`$ , or $`|\psi ,t_3_{XF}`$, with all $`x`$, $`f\left(x\right)`$, $`\overline{x}`$, $`r`$, etc. replaced by the proper numerical values) from the previous one by classical computation. Note that the resulting classical algorithm is reasonably efficient in itself, with times on the order of problem size.: (I) function evaluation: poly$`\left(n\right)`$ vs exp$`\left(n\right);`$ (II) filtration: linear$`\left(n\right)`$ vs exp$`\left(n\right)`$; (III) extracting $`r`$ out of $`|\psi ,t_3_{XF}`$: linear$`\left(n\right)`$ vs linear$`\left(n\right).`$ Speed-up is due to steps (I) and (II).

The extra-dynamical character of quantum computation is clarified by showing that Shor’s algorithm does not fit standard, dynamical, problem solving. Quantum dynamics is deterministic: any state in time dynamically determines a unique successor. While function evaluation is dynamical in character, the filtration performed by quantum measurement is not.

Classically the state after measurement $`M`$ is the same as the state before $`M`$. In quantum fact the state after measurement is influenced by both the state before measurement and the measurement itself, by the quantum principle: $`|\psi ,t_3_{XF}=k|\overline{f}_F\overline{f}|_F|\psi ,t_2_{XF}.`$ $`|\psi ,t_2_{XF}`$ is the prior state; the left-multiplication by $`|\overline{f}_F\overline{f}|_F`$ represents the final constraint selecting all tensor products ending with $`|\overline{f}_F`$. The determination of $`|\psi ,t_3_{XF}`$ is jointly influenced by an initial condition and a final condition. It is richer than dynamical determination, insofar as it yields the speed-up. We needed a computational context to realize this.

Extra-dynamical computation means much more than nondeterministic computation. For example, point (A) of the quantum principle does not involve randomness and yields Shor’s quantum speed-up in $`70\%`$ of the cases, when a single run of the algorithm is sufficient to identify $`r`$ In $`30\%`$ of the cases, more than one run is needed. Randomness assures that we do not always obtain the same result..

Determination with joint influence is extra-dynamical, it cannot be represented by a dynamical propagation of an input into an output. Of course we could go through step (ii), and replace joint influence with a dynamical process that leads to a “filtered” state like $`|\psi ,t_3_{XF}`$. But this would introduce programming and computation, increasing computation time exponentially in problem size. Joint influence bypasses step (ii) as well as speeding-up the computation. It yields a direct physical determination of the object of an implicit definitionSince the implicit definition is the problem, we see that, in Shor’s algorithm, computation can be identified with problem solving: points (i), (ii), and (iii) of Section I are both altered and unified..

This can also be seen as follows. $`|\psi ,t_3_{XF}`$ (selected with joint influence) contains the solutions $`x`$ of the implicit algebraic equation $`f(x)=\overline{f}`$, although the reverse of $`f`$ has not been computed. Thus, $`f(x)=\overline{f}`$ implicitly defines the solutions $`x`$ while quantum measurement selects them without going through programming and dynamical computation. The extra-dynamical character of this selection is clear. It takes essentially no time.

It can be seen that the same theory of the speed-up holds for Simon’s algorithm , as modified in .

Until now we have assumed the intermediate measurement of $`\left[F\right]`$. However, as is well known, this measurement can be skipped without affecting the result of measuring $`\left[X\right]`$ at time $`t_4`$ (fig. 1). It was introduced by Ekert and Jozsa  to clarify the way Shor’s algorithm operates; it can also clarify the speed-up. In fact skipping it is mathematically equivalent to performing it: the filtration performed by the extra-dynamical projection of quantum measurement is induced by measuring only $`\left[X\right]`$ at the end.

If $`\left[F\right]`$ measurement is skipped, the state of registers $`X`$ and $`F`$ at time $`t_4`$ is entangled. This establishes an equivalence between measuring $`\left[X\right]`$ or $`\left[F\right]`$. From a mathematical standpoint, the outcome of measuring $`\left[F\right]`$ at time $`t_4`$ can be backdated in time along the reversible process, provided that the overall state undergoes the inverse of the usual forward-time evolution. This is equivalent to having measured $`\left[F\right]`$ at time $`t_2`$.

We should counter the objection that register $`F`$ can be annihilated immediately after function evaluation. This would leave register $`X`$ in a mixture that is the partial trace over $`F`$ of the density matrix of the two registers:

$`|\psi ,t_2_X^{^{}}={\displaystyle \frac{1}{\sqrt{N}}}{\displaystyle \underset{h}{}}e^{i\delta _h}\left(|x_h_X+|x_h+r_X+|x_h+2r_X+\mathrm{}\right)|f_h_F,`$

where the range of $`h`$ is such that $`f_h`$ ranges over all the values assumed by $`f\left(x\right)`$, $`f\left(x_h\right)=f\left(x_h+r\right)=\mathrm{}=f_h`$, and $`\delta _h`$ are random phases independent of each other\**\**\**We are using the random phase representation. Let us exemplify it for a two-state system. The mixture $`\rho =\mathrm{sin}^2\phi |00\left|+\mathrm{cos}^2\phi \right|11|`$ becomes $`|\psi =\mathrm{sin}\phi |0+e^{i\delta }\mathrm{cos}\phi |1`$, where $`\delta `$ is a random phase with uniform distribution in $`[0,2\pi ]`$; $`\rho `$ is the average over $`\delta `$ of $`|\psi \psi |`$.. For the current purposes, annihilating $`F`$ is like having performed the intermediate $`\left[F\right]`$ measurement.

## III The speed-up in quantum oracle computing

Quantum oracle computing can be seen as a competition between two players. One produces the problem, the other is challenged to produce the solution. We shall call the former player Sphinx, the latter Oedipus.

Let us consider Grover’s algorithm . The game is as follows. The Sphinx hides an object in drawer number $`k`$, among $`n`$ drawers. Oedipus must find where it is, in the most efficient way. The chest of drawers is actually a quantum computer that, set in the mode $`k`$ and given a drawer number $`x`$ as the input, yields the output $`f_k\left(x\right)=\delta _{k,x}`$($`\delta _{k,x}=1`$ if $`k=x`$ and $`\delta _{k,x}=0`$ if $`kx`$). Fig. 2a gives the usual Grover’s algorithm for $`n=4`$.

Fig. 2a,b

The Sphinx sets the mode $`k`$ at random and passes the computer on to Oedipus. Oedipus must find $`k`$ in the most efficient way by testing the computer input-output behaviour.

Without entering into detail, we note that the computer has two registers $`X`$ and $`F`$. Oedipus prepares them in the initial state $`\frac{1}{\sqrt{2}}|00_X\left(|0_F|1_F\right),`$ the same for all $`k`$, and invokes the algorithm presented in fig. 2a. The state $`\psi `$ before final measurement depends on the Sphinx’ choice $`k`$:

$`k=00`$ $``$ $`\psi ={\displaystyle \frac{1}{\sqrt{2}}}|00_X\left(|0_F|1_F\right),`$
$`k=01`$ $``$ $`\psi ={\displaystyle \frac{1}{\sqrt{2}}}|01_X\left(|0_F|1_F\right),`$
$`k=10`$ $``$ $`\psi ={\displaystyle \frac{1}{\sqrt{2}}}|10_X\left(|0_F|1_F\right),`$
$`k=11`$ $``$ $`\psi ={\displaystyle \frac{1}{\sqrt{2}}}|11_X\left(|0_F|1_F\right).`$
Measuring $`\left[X\right]`$ yields Oedipus answer. This is reached in $`O\left(\sqrt{n}\right)`$ time, versus $`O\left(n\right)`$ with classical computation. But it is reached in a dynamical way, without any interplay between quantum parallel computation and the extra-dynamical projection of quantum measurement.

As we have seen, this interplay is associated with an isomorphism between the problem that implicitly defines its solution and the solution determination. This obviously requires that the problem is physically represented in a complete way. Here it is not: the above possible choices of the Sphinx and the related implications are not physically represented.

This is easily altered by introducing an ancillary two-qubit register $`K`$ which contains the computer mode $`k`$. Given the input $`k`$ and $`x`$, the output of computation is now $`F(k,x)=f_k\left(x\right)`$ (fig. 2b). The preparation becomes

$`{\displaystyle \frac{1}{2\sqrt{2}}}\left(|00_K+e^{i\delta _1}|01_K+e^{i\delta _2}|10_K+e^{i\delta _3}|11_K\right)|00_X\left(|0_F|1_F\right),`$

where $`\delta _1`$, $`\delta _2`$ and $`\delta _3`$ are independent random phases. To Oedipus, the Sphinx’ random choice is indistinguishable from a mixture where $`k`$ is a random variable with uniform distribution over $`00`$, $`01`$, $`10`$, $`11`$. Fig. 2b includes the physical representation of the problem; we can go directly to the final state before measurement:

$`\left(|00_K|00_X+e^{i\delta _1}|01_K|01_X+e^{i\delta _2}|10_K|10_X+e^{i\delta _3}|11_K|11_X\right)\left(|0_F|1_F\right),`$

$`\delta _1`$, $`\delta _2`$ and $`\delta _3`$ are independent random phases. Measuring $`\left[K\right]`$ gives the Sphinx’ choice, measuring $`\left[X\right]`$ gives Oedipus answer, or vice-versa. Now that the game has been physically represented, we find again that there is the above “interplay”.

In this game context, joint influence becomes the joint determination of the drawer number on the part of the two players, imposed by the quantum principle.

Why does extra-dynamical joint influence produce a speed-up? We suggest the following argument. The quantum game – yielding joint determination of the drawer number as a special quantum feature – should be as efficient as a classical game where there were joint determination of the drawer number on the part of the two players.

This cannot mean that Oedipus dictates the Sphinx’ choice, or the Sphinx suggests to Oedipus the right answer: this would be unilateral determination. Joint determination is symmetrical. The classical game must be defined as follows, with reference to the square-shaped chest of drawers herebelow††††††If the number of drawers is $`O\left(n\right)`$, the number of rows or colums is $`O\left(\sqrt{n}\right)`$.

|  | $`0`$ | $`1`$ |
| --- | --- | --- |
| $`0`$ | $`00`$ | $`01`$ |
| $`1`$ | $`10`$ | $`11`$ |

The Sphinx chooses the row number, say 1. Oedipus chooses the column number, say 0. Clearly, the drawer number 10 has been jointly determined by the Sphinx and Oedipus. Now the cost of Oedipus search is $`O(\sqrt{n})`$ rather than $`O(n)`$, since he must search only the row. This is in agreement with theory.

A similar analysis applies to Deutsch’s algorithm  as modified in .

## IV Conclusions

We have shown that quantum computation speed-up depends essentially on the extra-dynamical, irreversible projection of quantum measurement. To be sure, the entropy increase associated with speed-up is proportional only to the size of the output register, not the computation.

Extra-dynamical computation is more efficient than dynamical computation, as it yields the speed-up. It is a high level quantum feature, as it comes from a special interplay between a plurality of lower level ones (entanglement, disentanglement …).

Earlier, attention was paid only to reversible quantum computation. The seminal well known works of Bennett, Fredkin and Toffoli, Benioff, and Feynmann demonstrated that computation can be reversible both in the classical and quantum framework. With Deutsch and others, quantum computation becomes quantum problem-solving, yields a speed-up and, we point out, ceases to be reversible. The current quantum algorithms ingeniously exploit extra-dynamical computation.

It is natural to ask whether other extra-dynamical projections than the one inherent in quantum measurement can be useful. Two come to mind at once: a statistics symmetry can be seen as an extra-dynamical projection on the “symmetric” subspace; and annealing is a projection on the ground state resulting from gradual cooling by a succession of extra-dynamical interventions. Exploiting these forms of projection might result in further speed-ups, and further reductions in the programming process.

This work developed through many discussions with Artur Ekert.


text:
# EUV and X-ray observations of Abell 2199: a three-phase intracluster medium with a massive warm component

11institutetext: Department of Physics, University of Alabama, Huntsville, AL 35899, U.S.A. 22institutetext: Osservatorio Astrofisico di Catania, Via S. Sofia 78, I-95125 Catania, Italy 33institutetext: Mullard Space Science Laboratory, UCL, Holmbury St. Mary, Dorking, Surrey, RH5 6NT, U.K. (Received / Accepted )

## Abstract

Various independent ways of constraining key cosmological parameters yielded a consensus range of values which indicates that at the present epoch the bulk of the universe’s baryons is in the form of a warm ($``$ 106 K) gas - a temperature regime which renders them difficult to detect. The discovery of EUV and soft X-ray excess emission from clusters of galaxies was originally interpreted as the first direct evidence for the large scale presence of such a warm component. We present results from an EUVE Deep Survey (DS) observation of the rich cluster Abell 2199 in the Lex/B (69 - 190 eV) filter passband. The soft excess radial trend (SERT), shown by a plot against cluster radius $`r`$ of the percentage EUV emission $`\eta `$ observed above the level expected from the hot intracluster medium (ICM), behaves as a simple function of $`r`$ which decreases monotonically towards $`r=0`$; it smoothly turns negative at $`r`$ 6 arcmin, inwards of this radius the EUV is absorbed by cold matter with a line-of-sight column density of $``$ 2.7 $`\times `$ 1019 cm-2. The centre of absorption is offset from that of the emission by $``$ 1 arcmin, and the area involved is much larger than that of the cooling flow. These facts together provide strong evidence for a centrally concentrated but cluster-wide distribution of clumps of cold gas which co-exist with warm gas of similar spatial properties. Further, the simultaneous modeling of EUV and X-ray data requires a warm component even within the region of absorption. The phenomenon demonstrates a three phase ICM, with the warm phase estimated to be $``$ 5-10 times more massive than the hot.

###### Key Words.:

Galaxies: intergalactic medium, cooling flows  offprints: R. Lieu

Abell 2199 is a well-studied X-ray bright cluster of galaxies (e.g. Siddiqui et al. 1998). In a recent study (Lieu et al. 1999a; LBM99) we presented a first observation of the cluster with the Extreme Ultraviolet Explorer (EUVE; Bowyer & Malina 1991); the cluster showed clear evidence of excess emission in the DS Lex/B filter ($``$ 65-190 eV passband) above the thermal contribution from the hot intra-cluster medium (ICM). The A2199 sky area was re-observed by EUVE for $``$ 57 ksec in February 1999 (see Lieu et al. 1999b; L99). The program featured an in situ background measurement by pointing at small offset from the cluster, which asserted the correctness of the original method of determining (and subtracting) the background from an asymptotically flat region of the radial profile. Complementary data in the X-ray (0.2 - 2.0 keV) passband, as gathered by a ROSAT PSPC observation which took place in July 1990, with an exposure of 8.5 ksec, were extracted from the public archive 111See the High Energy Astrophysics Archive available at http://heasarc.gsfc.nasa.gov/docs/rosat/archive.html. Same PSPC observation (RP number 150083) as in L99 and LBM99 was consulted for the present work.. For correct comparison between the EUV and X-ray emissions, the Galactic HI column density was measured at NH = (8.3 $`\pm `$ 1.0) $`\times `$ 1019 cm-2 by a dedicated observation at Green Bank (Kaastra et al. 1999), and was found to be spatially smooth. The EUV and X-ray data were simultaneously modeled with a thin plasma emission code (Mewe et al. 1985; Mewe et al. 1986) and appropriate line-of-sight Galactic absorption (Morrison & McCammon 1983) for the above value of NH. At a given radius the hot ICM was assumed to be isothermal, with the abundance fixed at 0.3 solar apart from the cooling flow region where the parameter became part of the data fitting in order to account for any possible abundance gradient within this region (a different way of handling the abundance does not sensitively affect the results presented in this work).

The forementioned model, when applied to the PSPC spectra at all radii, generally leads to acceptable fits. At low energies the EUV measurements gave crucial new information. The overall effect is a soft excess as reported previously. A plot of the SERT indicates, however, that the percentage EUV excess at a given radius is less at the centre. In fact, the trend takes the form of a negative central excess (i.e. absorption, see Fig. 1), which steadily rises with radius until the 6 arcmin point, beyond that the fractional excess turns positive and continues to increase until the limiting radius of EUV detection ($``$ 20 arcmin, Lieu et al. 1999b). In the present paper we interpret the results physically, and demonstrate that such a trend, together with the spectral data, provide compelling reasons for a three phase model of the ICM, with the warm intermediate phase as origin for the soft excess.

We first address the outer parts of the cluster, where the data present formidable difficulties to the non-thermal interpretation of the soft excess which postulates a large population of intracluster relativistic electrons undergoing inverse-Compton (IC) interaction with the cosmic microwave background (CMB, see Ensslin & Biermann 1999, Sarazin & Lieu 1998). Fig. 2 shows a composite plot of the EUV and X-ray data for the 12 - 15 arcmin annulus. The prominent EUV excess, unaccompanied by any similar effect in soft X-rays, implies that the bulk of the relativistic electrons have energies below 200 MeV, a cut-off which is most obviously understood as due to aging (i.e. synchrotron and inverse-Compton losses): the electrons are at least 3 $`\times `$ 109 years old. However, in order to account for the large EUV excess the highly evolved electron spectrum at the present epoch must still include sufficient particles ahead of the cut-off. This means that for the region of concern, at injection (when the power-law differential number index is assumed to be 2.5, in accordance with our Galactic cosmic ray index) the relativistic electron pressure would have exceeded that of the hot ICM by a factor of $``$ 4, leading to a major confinement problem for the hot gas. The inclusion of cosmic ray protons exaggerates the difficulty, as protons carry 10 - 100 times more pressure than electrons. Thus the only other viable alternative, viz. the originally proposed thermal (warm) gas scenario (Lieu et al. 1996), must now be considered seriously. This is especially so in the light of the recent constraints on cosmological parameters, which point to the existence of a warm and massive baryonic component (Cen & Ostriker 1999, Maloney & Bland-Hawthorn 1999).

Turning to the core of the cluster, one sees in Fig. 1 that the EUV is absorbed. For more details, in Fig. 3 is shown an image of the brightness of the EUV excess. The data suggest an intermixed model (Jacobsen & Kahn 1986) of the ICM: the lack of soft excess at small radii is due entirely to the larger amount of cold absorbing matter collected in this region. Our inference of the state of the ICM is reinforced by the behavior of the SERT: the trend depicted in Fig. 1 follows a simple parametric profile which applies equally satisfactorily to the absorption and soft excess regions, with no change of behavior at the transition radius of $``$ 6 arcmin. In fact, there is no particular significance in this radius (it is much larger than the cooling flow radius of $``$ 2 arcmin; Siddiqui et al. 1998). The observation is naturally interpreted as the combined effect of clumped emission regions containing a warm component, absorbed by clouds of cold gas (neutral H at T $`10^4`$ K) in between them (statistical quality of the data can not well constrain the size of the clouds. However, if pressure equipartition with the hot gas is assumed, the HI mass estimates derived in the following convert to an approximate cloud radius of 1-10 kpc). Both the warm and the cold gas distributions are cluster-wide and centrally condensed, but with increasing radius the lines-of-sight are more transparent to EUV photons created at locations along them. For comparable intrinsic emission profiles of the soft excess and the hot ICM, the result is an outwardly rising SERT.

The argument for an intermixed ICM also rests upon direct evidence for the presence of soft excess even in the absorbed regions. We show in Fig. 4 a core spectrum, where it can be seen that by the time intrinsic absorption accounts for the EUV decrement, an excess is seen in soft X-rays (which are less absorbed). This clearly indicates a complex ICM where the various gas phases co-exist. The apparent negative soft excess within the absorption radius is simply due to an abundance of cold clouds masking EUV emissions from the warm and hot components.

The thermal origin of the EUV is compelling for another reason: the widespread absorption reported here implies the existence of a cold phase in the midst of the well known hot phase, and then the question naturally arises concerning why a warm phase is absent, and is not the cause of the soft excess. At the very least, mixing layers on the surface of the cold clouds would suffice to produce the intermediate phase (Fabian 1997).

The mass budgets of the three ICM components in consideration are estimated as follows. The intrinsic HI column density as inferred from the central EUV absorption converts to a density of cold clouds of $``$ 5 $`\times `$ 1010 M Mpc-3. This gives a mass ratio of 1:2000 between the cold and hot gas along the line-of-sight. Any estimate of the mass of warm gas at the centre is likely to be inaccurate, since the soft emission is significantly absorbed. We therefore considered the 12 - 15 arcmin region where this complication is not as severe as in the centre. The extreme softness of the emission (Fig. 2) limits the gas temperature to kT $`<`$ 100 eV (or T $`<`$ 106 K), with a correspondingly large mass estimate of 1.25 $`\pm _{0.9}^{0.4}\times `$ 1014 M 222Errors are estimated from the statistical uncertainties in the determination of the warm gas emission measure, as obtained by spectral modelling with XSPEC 10.0., under the assumption of 100 % filling factor of the warm gas in the spherical shell of concern; this is $``$ 43 $`\pm _{29}^{13}`$ times more massive than the hot ICM in this region, as obtained from the hot gas density of Siddiqui et al. (1998). The 1-$`\sigma `$ lower limit ratio implies $``$ 3 times more missing baryons than expected (Cen & Ostriker 1999), although it must be emphasized that both the mass and bolometric luminosity can be substantially reduced if the gas turns out to be warmer. This can be realized by adopting alternative emission models for the warm phase, especially those which involve an underionized gas, since the EUV emission efficiency is then enhanced, and the gas can be warmer than the above temperature constraint. Plasma in such an ionization state is easily produced by mixing layers or shock heating.

References

Balucinska-Church M., McCammon, D. 1992, ApJ 400, 699.
Bowyer S., Malina R.F. 1991, in EUV Astronomy,
eds. R.F. Malina, S. Bowyer (new York:Pergamon), 397.
Cen R., Ostriker J.P. 1999, ApJ 514, 1-6.
Maloney P.R., Bland-Hawthorn J. 1999, ApJ 522, L81-84.
Ensslin T.A., Biermann, P.L. 1998, A&A 330, 90–98.
Fabian A.C. 1997, Science 275, 48–49.
Jakobsen P., Kahn, S.M. 1986, ApJ 309, 682 .
Kaastra J.S. 1992 in An X-Ray Spectral Code for Optically Thin Plasmas
(Internal SRON-Leiden Report, updated version 2.0).
Kaastra J.S., Lieu R., Mittaz, J.P.D. et al. 1999, ApJ 519, L119.
Lieu R., Mittaz J.P.D., Bowyer S. et al. 1996, Science, 274,1335–1338.
Lieu R., Bonamente M., Mittaz 1999a, ApJ 517, L91.
Lieu R., Bonamente M., Mittaz et al. 1999b, ApJ 527, L77.
Mewe R., Gronenschild E.H.B.M., van den Oord G.H.J. 1985, A&A 62, 197 .
Mewe R., Lemen J.R., van den Oord G.H.J. 1986, A&A 65, 511.
Morrison R., McCammon, D. 1983, ApJ 270, 119.
Sarazin C.L., Lieu R. 1998, ApJ 494, L177.
Siddiqui H., Stewart G.C., Johnston, R.M. 1998, A&A, 334, 71.
Snowden S.L., McCammon D., Burrows D.N., Mendenhall, J.A. 1994,
ApJ 424, 714.