text:
# Galaxy Formation and Evolution: Recent Progress

## 1 Introduction

These are exciting times to be working on any aspect of studies of galaxies at high redshift whether observational or theoretical. Most would agree that the current period represents something of a golden era in the subject. Figure 1 shows the increasing extent to which articles concerned with galaxy evolution dominate the published literature over the past 25 years (gauged xenophobically I’m afraid by keyword statistics only in two North American journals).

To try and understand the cause for this prominence in the subject, the dates associated with the commissioning of some major observational facilities have been marked. The progress appears to have been driven largely by new kinds of optical and near-infrared data: faint counts and searches for primaeval galaxies in the late 1970’s and early 1980’s (\[Peterson et al 1979, Tyson & Jarvis 1979, Kron 1980, Koo 1985\]), faint galaxy redshift surveys made possible by multi-object spectrographs in the late 1980’s and early 1990’s (\[Lilly et al 1995, Ellis et al 1996, Cowie et al 1996, Cohen et al 2000\]), the launch of Hubble Space Telescope (HST) and its revelation of resolved galaxy images to significant redshifts (\[Griffiths et al 1994, Glazebrook et al 1995, Brinchmann et al 1998\]), the remarkable Hubble Deep Field image (\[Williams et al 1996\]) and the plethora of papers that followed (\[Livio, Fall & Madau 1998\]) and the arrival of the Keck telescopes bringing a new wave of faint Lyman-break galaxy spectroscopy at unprecedented redshifts (\[Steidel et al 1996, Steidel et al 1999\])††††††$`\mathrm{}`$A correlation was also made with three key international conferences (\[Larson & Tinsley 1978, Frenk et al 1988, Livio, Fall & Madau 1998\]) but I was horrified to see that these appeared to have had a negative effect on the community’s output! I assume this arose from a much-needed period of post-conference reflection!.

One often hears claims that a subject undergoing spectacular progress is one that is nearing completion (c.f. \[Horgan 1997\]). After all, the rise in Figure 1 clearly cannot continue indefinitely and fairly soon, it could be argued, we will then have solved all of the essential problems in the subject. As if anticipating this, a theoretical colleague gave a recent colloquium at my institute entitled Galaxy Formation: End of the Road !

Consider the evidence. Observationally we may soon, via photometric redshifts, have determined the redshift distribution, luminosity evolution and spatial clustering of sources to unprecedented limits. If one accepts photometric redshifts are reliable, the rate of progress in the traditional pursuit of $`N(m,color,z)`$ is limited solely by the field of view of the telescope and the exposure times adopted. Panchromatic data matching that obtained with optical and near-infrared telescopes from SIRTF, FIRST, and ALMA will also enable us unravel the cosmic star formation history $`\rho _{SFR}(z)`$ to unprecedented precision (\[Madau et al 1996, Blain et al 1999\]). It has already been claimed that the above data, e.g. $`N(m,color,z)`$ and $`\rho _{SFR}(z)`$, can be understood in terms of hierarchical models of structure formation where galaxies assemble through the cooling of baryonic gas into merging cold dark matter halos (CDM, \[Kauffmann et al 1994, Baugh et al 1998, Cole et al 2000a\]).

The word ‘concordance’ was recently coined astrophysically in an article reconciling different estimates of the cosmological parameters (\[Ostriker & Steinhardt 1996\]). Such concordance in our understanding of galaxy evolution is a natural consequence of semi-analytical theories whose sole purpose is to explain the ‘big picture’ as realised with the extant galaxy data. In this series of lectures I want to show that we have our work cut out for some considerable time! Exciting progress is definitely being made, but observers must rise to the challenge of testing the fundamentals of contemporary theories such as CDM and theorists must get ready to interpret qualitatively new kinds of data that we can expect in the next decade.

Figure 1:The remarkably rapid growth in galaxy evolution studies: the fraction of the ApJ and AJ literature containing the key word ‘galaxy evolution’ over the past 25 years. The inset shows the marked decline in the use of galaxies as probes of the cosmological parameters during 1970-1980 (after Brinchmann, Ph.D. thesis 1998).

These lectures are intended for interested graduate students or postdocs entering the field. There is an obvious observational flavor although I have tried to keep in perspective an ultimate goal of comparing results with recent CDM predictions. The bias is largely to optical and near-infrared applications; there is insufficient space to do justice to the rapidly-developing contributions being made at sub-millimetre, radio and X-ray wavelengths which other contributors at this winter school will cover in detail.

## 2 Galaxy Formation and Cosmology

Traditionally faint galaxies were studied in order to constrain the cosmological world model (\[Sandage 1961\]); their evolution was considered just one more tedious correction (the so-called evolutionary correction) in the path to the Holy Grail of the deceleration parameter $`q_o`$ ($`\mathrm{\Omega }_M`$/2 in $`\mathrm{\Lambda }`$=0 Friedmann models). The most useful galaxies in this respect were giant ellipticals in rich clusters. Tinsley (1976) demonstrated how sensitive the derived $`q_0`$ was to the assumed main sequence brightening with look-back time in these populations.

The traditional view for the formation history of an elliptical followed Eggen, Lynden-Bell & Sandage (1962). Monolithic collapse and rapid star formation leads to a subsequent track known as ‘passive evolution’ (i.e. without further star formation). Tinsley showed that main sequence brightening in such a stellar population is largely governed by the rate at which stars evolve off the main sequence, i.e. the slope $`x(1)`$ of the initial mass function at the typical turnoff mass 0.4–1$`M_{}`$. Whence:

$$E(z,t)=dM_v/dlnt1.3\mathrm{\hspace{0.33em}0.3}x$$
(2.1)
and, in terms of its bias on $`q_o`$:

$$\mathrm{\Delta }q_o=1.4(H_ot_o)^1dM_v/dlnt=1.8\mathrm{\hspace{0.33em}0.42}x$$
(2.2)
Tinsley argued that one would have to know the evolutionary correction to remarkable precision get a secure value of $`q_o`$. In fact, noting that the difference in apparent magnitude for a standard candle at $`z`$=1 between an empty and Einstein-de Sitter Universe is only $``$0.5 mag, the relative importance of cosmology and evolution can be readily gauged.

Despite the above, it is always a mystery to me why several of our most eminent astronomers (\[Kristian et al 1978, Gunn & Oke 1975\]) continued to pursue the Hubble diagram as a cosmological probe using first-ranked cluster galaxies, in some cases for several years after the challenge of resolving the evolutionary correction became known. Tammann (1985) estimated about 400 nights nights of Palomar 200-inch time was consumed by the two competing groups whose resulting values of $`q_o`$ fundamentally disagreed. Recently Aragón-Salamanca (1998) showed, in a elegant summary of the situation, how the modern $`K`$-band Hubble diagram is most likely complicated further by the fact that first-ranked cluster galaxies are still assembling their stars over the redshift interval 0$`<z<`$1, offsetting the main sequence brightening (Figure 2).

In the late 1970’s therefore, the motivation for studying faint galaxies became one of understanding their history rather than using them as tracers of the cosmic expansion (see inset panel in Figure 1). This is not to say that uncertainties in the cosmological model do not affect the conclusions drawn. The connection between cosmology and source evolutions remains strong in three respects:

Figure 2:A recent appraisal of the prospects of securing cosmological constraints from the Hubble diagram of brightest cluster galaxies (\[Aragón-Salamanca et al 1998\]). Luminosity evolution is parameterised as $`L=L(0)(1+z)^\gamma `$. For $`q_o`$=0, the top panel shows residuals and best fit trend applying $`k`$-correction and luminosity distance effects only; no luminosity evolution is seen. The middle and bottom panels show the residuals when evolution is modeled for single burst populations formed at $`z_F`$=2 and 5, respectively. High $`z`$ galaxies are less luminous than expected, presumably because they are still accreting material. Quantitatively, the effect amounts to a factor of 2-4 less stellar mass depending on the assumed $`q_o`$ (c.f. \[van Dokkum et al 1999\]).

1. We use our knowledge of stellar evolution to predict the past appearance of stellar populations in galaxies observed at high redshift. However, stellar evolution is baselined in physical time (the conventional unit is the Gyr: 109yr), whereas we observe distant sources in redshift units. The mapping of time and redshift depends on the world model. Broadly speaking there is less time for the necessary changes to occur in a high $`\mathrm{\Omega }_M`$ universe and consequently evolutionary trends are much stronger in such models.
2. Many evolutionary tests depend on the numbers of sources, the most familiar being the number-magnitude count which is remarkably sensitive to small changes in source luminosity. However, the relativistic volume element $`dV(z)`$ depends sensitively on curvature being much larger in open and accelerating Universes than in the Einstein-de Sitter case.
3. Predictions for the mass assembly history of a galaxy in hierarchical models depend also on the cosmological model in a fairly complex manner since these models jointly satisfy constraints concerned with the normalisation of the mass power spectrum via the present abundance of clusters (e.g. \[Baugh et al 1998\]). Figure 3 illustrates one aspect of this dependence (\[Kauffmann & Charlot 1998\]); structure grows more rapidly in a dense Universe so the decline with redshift in the abundance of massive spheroidal galaxies, which are thought in this picture to forms via mergers of smaller systems, is much more marked in high density models than in open or accelerating Universes.

Figure 3:The abundance of massive ($`>`$10$`{}_{}{}^{11}M_{}^{}`$) systems as a function of redshift in two hierarchical models (\[Kauffmann & Charlot 1998\]) showing the strong decline in a high density ($`\tau `$CDM) model c.f. that in a low density accelerating model ($`\mathrm{\Lambda }`$CDM).

Fortunately, we are making excellent progress in constraining the cosmological parameters from independent methods, the most prominent of which include the angular fluctuation spectrum in the microwave background (\[de Bernardis et al 2000, Balbi et al 2000\]), the Hubble diagram of distant Type Ia supernovae (\[Garnavich et al 1998, Perlmutter et al 1999\]), the abundance of rich clusters at various epochs (\[Bahcall & Fan 1998\]) and the redshift-space distortion in large redshift surveys such as 2dF (\[Peacock et al 2000\]).

Given it matters, how then should we respond to the widely-accepted concordance in the determination of $`H_o,\mathrm{\Omega }_M,\mathrm{\Lambda }`$ from various probes (Ostriker & Steinhardt 1996, Bahcall 1999)? The claimed convergence on the value of Hubble’s constant (\[Mould et al 2000\]) is not so important for the discussion below since most evolutionary tests are primarily concerned with relative comparisons at various look-back times where $`H_o`$ cancels. The most bewildering aspect of the concordance picture is the resurrection of a non-zero $`\mathrm{\Lambda }`$, the evidence for which comes primarily from the Hubble diagram for Type Ia supernovae.

As a member of the Supernova Cosmology Project (\[Perlmutter et al 1999\]) I obviously take the supernova results seriously! However, this does not prevent me from being surprised as to the implications of a non-zero $`\mathrm{\Lambda }`$. The most astonishing fact is how readily the community has apparently accepted the resurrection of $`\mathrm{\Lambda }`$ \- a term for which there is no satisfactory physical explanation (c.f \[Wang et al 2000\]). To one poorly-understand component of the cosmic energy density (non-baryonic dark matter), we seem to have added another (vacuum energy). It seems a remarkable coincidence that all three significant constituents ($`\mathrm{\Omega }_B,\mathrm{\Omega }_{DM},\mathrm{\Omega }_\mathrm{\Lambda }`$) are comparable in magnitude to within a factor of 10, and hardly a step forward that only one is physically understood!

The lesson I think we should draw from the cosmic concordance is similar to the comment I made in $`\mathrm{\S }`$1 when we discussed some theorists’ triumphant reconciliation of their theories with faint galaxy data (a point we will debate in detail in $`\mathrm{\S }`$3). In both cases, the hypothesis certainly reproduces a wide range of observations but note it takes, as input, parameters for which there is not yet a clear physical model. One should not, therefore, regard a concordant picture as anything other than one of many possible working hypotheses. In the case of the cosmological models, we need to invest effort into understanding the physical nature of dark matter and vacuum energy. In the case of galaxy evolution our goal should be to test the basic ingredients of hierarchical galaxy formation.

## 3 Star Formation Histories

One of the most active areas of relevance to understanding the rate at which galaxies assemble is concerned with determining the cosmic star formation history. The idea is simple enough. A systematic survey is conducted according to some property that is sensitive to the on-going rate of star formation. The volume-average luminosity density is converted into its equivalent star formation rate averaged per unit co-moving volume and the procedure repeated as a function of redshift to give the cosmic star formation history $`\rho _{}(z)`$. In this section we will explore the uncertainties and also the significance of this considerable area of current activity in terms of the constraints they provide on theories of galaxy formation.

The joint distribution of luminosity $`L`$ and redshift $`z`$, $`N(L,z)`$, for a flux-limited sample permits the construction of the luminosity function $`\mathrm{\Phi }(L)`$ according to procedures which are reviewed by Efstathiou, Ellis & Peterson (1988) and compared by Ellis (1997) . The luminosity function is often characterised according to the form defined by Schechter (1976), viz:

$$\mathrm{\Phi }(L)dL/L^{}=\mathrm{\Phi }^{}(L/L^{})^\alpha exp(L/L^{})dL/L^{}$$
(3.3)
in which case the integrated number of galaxies per unit volume $`N`$ and the luminosity density $`\rho _L`$ then becomes:

$$N=\mathrm{\Phi }(L)𝑑L=\mathrm{\Phi }^{}\mathrm{\Gamma }(\alpha +1)$$
(3.4)
and

$$\rho _L=\mathrm{\Phi }(L)L𝑑L=\mathrm{\Phi }^{}L^{}\mathrm{\Gamma }(\alpha +2)$$
(3.5)
and the source counts in the non-relativistic case, applicable to local catalogs, is:

$$N(<m)d^{\mathrm{\hspace{0.17em}3}}(m)𝑑L\mathrm{\Phi }(L)(L/L^{})^{\frac{3}{2}}\mathrm{\Phi }^{}L^{\frac{3}{2}}\mathrm{\Gamma }(\alpha +\frac{5}{2})$$
(3.6)
Frequently-used measures of star formation in galaxies over a range of redshift include rest-frame ultraviolet and blue broad-band luminosities (\[Lilly et al 1995, Steidel et al 1996, Sullivan et al 2000\]), nebular emission lines such as H$`\alpha `$ (Gallego et al 1995, Tresse & Maddox 1998, Glazebrook et al 1999), thermal far-infrared emission from dust clouds (\[Rowan-Robinson et al 1997, Blain et al 1999\]) and, most recently, radio continuum emission (\[Mobasher et al 1999\]).

Since only a limited range of the luminosity function centered on $`L^{}`$ is reliably probed in flux-limited samples, a key issue is how well the integrated luminosity density $`\rho _L`$ can be determined from such surveys. In the Schechter formalism, equations \[3.4\] and \[3.5\] show that whilst $`N`$ would diverge for $`\alpha <`$–1, the luminosity density is convergent unless $`\alpha <`$–2.

Figure 4:The luminosity function for galaxies selected at 2000 Å from the recent survey of Sullivan et al (2000). The histogram and associated numbers indicate the absolute magnitude distribution observed which is corrected by volume and $`k`$-correction effects to give the data points. The dotted curve illustrates the considerable effect of extinction as gauged by Balmer decrements determined individually for those galaxies with emission lines. Such uncertainties translate in factors of two uncertainty in the local UV luminosity density.

Figure 4 shows the local rest-frame ultraviolet (2000 Å ) luminosity function from Sullivan et al (2000) whose faint end slope $`\alpha `$=–1.6 is markedly steeper than that found for samples selected in the near-infrared (\[Mobasher et al 1993, Gardner et al 1997, Cole et al 2000b\]) (where $`\alpha `$-1). This contrast in the luminosity distribution of young and old stellar populations is an important result which emphasizes the relatively weak connection between stellar mass and light and implies there may be significant uncertainties in the estimation of integrated luminosity densities for star-forming populations.

Kennicutt (1998) carefully reviewed the relationships between the various observational diagnostics listed above and the star formation rate. Clearly a major uncertainty in any transformation based on the ultraviolet/optical continuum or nebular emission line measures is the likely presence of absorbing dust (Figure 4). Other uncertainties include the form of the initial stellar mass function and the nature of the star formation history itself.

Figure 5:Star formation rates derived from UV (2000 Å ) continua versus those derived from H$`\alpha `$ fluxes from the local survey of Sullivan et al (2000, open squares) and the $`z`$1 samples of Glazebrook et al (1999, large stars). For the Sullivan et al sample, extinction corrections were derived from individual Balmer decrements assuming Case B recombination and applied to the $`H\alpha `$ fluxes in the upper panel and both estimates in the lower panel.

Some of these uncertainties are quite imponderable and the only way to estimate their effect in typical populations is to undertake a comparison of the various diagnostics for the same sample. Sullivan et al (2000) compared UV and H$`\alpha `$-based estimators for their local balloon-based UV-selected sample and Glazebrook et al (1999) undertook a similar comparison for a restricted incomplete sample of high redshift galaxies (drawn from a $`I`$-selected sample). Bell & Kennicutt (2000) independently examined some of Sullivan et al’s conclusions based on a smaller local sample with satellite UV fluxes. The comparison analysed by Sullivan et al is shown in Figure 5. Although an overall linear relation is observed the scatter is quite considerable, greater than accountable from observational errors. The uncertainties would appear to be alarming in view of the fairly modest trends claimed in $`\rho _{SFR}(z)`$ (see below).

In addition to the scatter arising from extinction (accounted for via individual Balmer emission line decrements), Sullivan et al suggest that some fraction of their UV-selected population must be suffering star formation which is erratic in its time history. In such a situation, different diagnostics will be sensitive to bursts of activity for different periods, corresponding to the time over which the contributing stars remain on the main sequence. $`H\alpha `$ flux arises from recombination photons linked to those emitted below the Lyman limit from main sequence stars with lifetimes $``$106 years. The UV and blue continua persist for much longer periods ($`10^810^9`$ years).

Depending upon how widespread star formation histories of this kind may be, two forms of error may arise in estimating cosmic star formation histories. Firstly, the star formation rate derived for an individual galaxy will be a past time average, smoothing over any erratic behavior, rather than a true instantaneous value. More importantly however, particularly at high redshift, galaxies may be preferentially selected only if their star formation history is erratic, for example in $`H\alpha `$ surveys where some threshold of detectability may seriously restrict the samples.

Figure 6 shows a recent estimate of the cosmic star formation history drawn from various surveys (\[Blain 2000\]). There appears to be a marked increase in activity over 0$`<z<`$1 with a possible decline beyond $`z>`$2. Although, inevitably perhaps, attention has focused on the case for the high redshift decline, even the strong rise to $`z`$1 remains controversial. Originally proposed independently by Lilly et al (1995) and Fall et al (1996), revised estimates for the local luminosity density (\[Sullivan et al 2000\]) and independent surveys (\[Cowie et al 1999\]) have challenged the rapidity of this rise. Part of the problem is that no single survey permits a self-consistent measurement of $`\rho _{SFR}`$ over more than a very limited range in $`z`$. Most likely, therefore, much of the scatter in Figure 6 is simply a manefestation of the kinds of uncertainties discussed above in the context of Sullivan et al’s survey.

Beyond z$``$2, the available star formation rates have been derived almost exclusively from UV continua in Lyman break galaxies selected by their ‘dropout’ signatures in various photometric bands (\[Madau et al 1996, Steidel et al 1996, Steidel et al 1999\]) and from currently scant datasets of sub-mm sources interpreted assuming thermal emission from dust heated by young stars (\[Blain et al 1999, Barger et al 1999b\]). There has been much discussion on the possible disparity between the estimates derived from these two diagnostics (which other lecturers will address). Two points can be made: firstly, the measured UV luminosity densities will clearly underestimate the true values given likely extinctions. Secondly, the sample of sub-mm sources with reliable redshifts remains quite inadequate for luminosity density estimates in the sense described above. Most of the constraints arise from modelling their likely properties in a manner consistent with their source counts and the integrated far-infrared background.

Have we become over-obsessed with determining the cosmic star formation history? Observers are eager to place their survey points alongside others on the overall curve and different groups defend their methods against those whose data points disagree. We should consider carefully what role this cosmic star formation history plays in understanding how galaxies form?

Figure 6:The history of recent star formation from the recent compilation of Blain (2000). Data points are taken from a variety of sources referenced in that article. Thick solid and dashed lines represent trends expected from simple luminosity evolution and hierarchical models, respectively. It is clear there is considerable observational scatter at all redshifts, not just beyond $`z`$1 as often assumed.

Clearly, the prime conclusion we can draw from Figure 6 is that the stars which make the galaxies we see today formed continuously over a very wide redshift range. This may seem such an obvious deduction that it hardly merits stating but it is important to stress the absence of any obvious detectable ‘epoch of star formation’ as was once imagined (\[Eggen, Lynden-Bell & Sandage 1962, Frenk et al 1988\]). Hierarchical modelers were quick to point out (e.g. \[Baugh et al 1998\]) that they predicted extended star formation histories as early as 1990 (\[White & Frenk 1991\]). It is certainly true that a continuous assembly of galaxies is a major feature of these models and thus one supported by the data.

However, what about the quantitative form of Figure 6 which remains so difficult to pin down: does the shape of the curve really matter? Firstly, we should recognise that the luminosity density integrates over much detailed astrophysics that may be important. A particular $`\rho _{SFR}`$ at a given redshift could be consistent either with a population of established massive sources undergoing modest continous star formation or a steep luminosity function where most of the activity is in newly-formed dwarf galaxies. In terms of structure formation theories, these are very different physical situations yet that distinction is lost in Figure 6.

Secondly, theoretically, the cosmic star formation history is not particularly closely related to how galaxies assemble. It is more sensitive to the rate at which gas cools into the assembling dark matter halos, a process of considerable interest but which involves a myriad of uncertain astrophysical processes (Figure 7) which are fairly detached from the underlying physical basis of say the hierarchical picture. In support of this, we should note that Baugh et al (1999) were able, within the same $`\mathrm{\Lambda }`$-dominated CDM model, to ‘refine’ their earlier prediction to match new high redshift datapoints revealing a much less marked decline beyond z$``$2.

Figure 7:An illustration of the complex physical processes governing the star formation rate of a young galaxy (courtesy of Carlos Frenk). Star formation is governed by the rate at which baryonic gas cools and falls into dark matter halos and this is inhibited by heating, e.g. from supernovae. The precise form of the cosmic star formation history gives us more insight into the interplay between these processes, integrated over all star-forming galaxies, than in distinguishing between various forms of structure formation (e.g. hierarchical vs. monolithic).

## 4 Morphological Data from HST

As we discussed in $`\mathrm{\S }`$1, one of the most exciting new datasets that arrived in the mid-1990’s was the first set of resolved images of galaxies at significant look-back times from HST. Much of the early work was conducted in rich clusters (\[Couch et al 1994, Dressler et al 1994, Couch et al 1998, Dressler et al 1998\]) where the well-known ‘Butcher-Oemler’ effect (\[Butcher & Oemler 1978\]) - a surprisingly recent increase in the fraction of blue cluster members - was found to be due to a dramatic shift in the morphology-density relation (Figure 8). As recently as $`z`$0.3-0.4 (3-4 Gyr ago), cluster S0s were noticeably fewer in proportion, their place apparently taken by spirals, many of which showed signs of recent disturbances, such a distorted arms and tidal tails.

The physical origin of this transformation from spirals to S0s remains unclear and is currently being explored by detailed spectroscopy of representative cluster members (\[Barger et al 1996, Abraham et al 1996b, Poggianti et al 1999\]). A key diagnostic here is the interplay between the changing morphologies, the presence of nebular emission lines (such as \[O II\] 3727 Å – H$`\alpha `$ is generally redshifted out of the accessible range) and Balmer absorption lines (such as H$`\delta `$ 4101 Å ). The latter lines are prominent in main sequence A stars which linger for $``$1 Gyr after any enhanced starburst activity.

Barger et al (1996) proposed a simple cycle where an unsuspecting galaxy undergoes some perturbation, perhaps due to a merger or its first encounter with the intracluster gas, subsequently becomes morphologically-distorted and spectrally-active before subsiding to a regular spheroidal with a decaying Balmer absorption line. Whereas such a cycle can explain the proportion of unusual objects, it has difficulty matching their luminosities. A galaxy should be rendered more luminous during a burst and thus blue examples cannot easily be the precursors of the equally-luminous red post-burst cases. A controversy has since arisen over the fractions of objects seen in the various spectrally-active classes (\[Balogh et al 1999\]) suggesting much work is needed in this area, both in quantifying cluster-cluster variations and also radial variations in the responsible processes.

Although the cluster work discussed above represents something of a digression in our overall theme, the realisation that galaxies can so easily be transformed morphologically has profound implications for our understanding of galaxy formation. Much of the early work explaining the Hubble sequence (\[Tinsley 1977\]) assumed galaxies evolve as isolated systems, however the abundance of morphologically-peculiar and interacting galaxies in early HST images (\[Griffiths et al 1994\]) has been used to emphasize the important role that galaxy mergers must play in shaping the present Hubble sequence (\[Toomre & Toomre 1972, Barnes & Hernquist 1992\]). Merger-induced transformations of this kind are a natural consequence of hierarchical models (\[Baugh, Cole & Frenk 1996\]). Early disk systems are prone to merge during epochs when the cosmic density is high and the peculiar velocity field is cold, forming bulge-dominated and spheroidal systems which may then later accrete disks.

The possibility that galaxies transform from one class to another is a hard hypothesis to verify observationally since, as we have seen, traditionally observers have searched for redshift-dependent trends with subsets of the population chosen via an observed property (color, morphology, spectral characteristics) which could be transient. Moreover, experience ought to teach us that the outcome of tests of galaxy formation rarely come down simply to either Theory A or Theory B; usually it is some complicated mixture or the question was naive in the first place! Fortunately, the late formation of massive regular galaxies in the hierarchical picture (Figure 9) seems a particularly robust prediction and one in stark contrast to the classical ‘monolithic collapse’ picture (\[Tinsley 1977, Sandage 1983\]). The distinction is greatest for ellipticals presumed to form at high redshift with minimum dissipation (their central density reflecting that of the epoch of formation). Studying the evolutionary history of massive ellipticals is thus an obvious place to start.

Figure 9:The important role of late merging in a typical CDM semi-analytical model (Baugh et al 1996). The panels show the redshift-dependent growth for the stellar mass (left) and that of all baryonic material (right), as indicated by the thickness of the black area at a given epoch, for two present-day massive galaxies. The top system grows gradually and is thought to represent a present-day spiral. The bottom system suffers a late equal-mass merger thought to produce a present-day elliptical. Note the remarkably late assembly; most of stellar mass in both cases assembles in the interval 0$`<z<`$1.

An oft-quoted result in support of old ellipticals is the remarkable homogeneity of their optical colors (\[Sandage & Visvanathan 1978, Bower et al 1992\]). The idea is simple: the intrinsic population scatter in a color sensitive to recent star formation, such as $`UB`$, places a constraint either on how synchronous the previous star formation history must have been across the population or, if galaxies form independently, the mean age of their stellar populations. By combining cluster data at low redshift (\[Bower et al 1992\]) with HST-selected samples at intermediate redshift (\[Ellis et al 1998\]), the bulk of the cluster elliptical population was deduced to have formed its stars before z$``$2, in apparent conflict with hierarchical models. Similar conclusions have been drawn from evolution of the mass/light ratio deduced from the fundamental plane (\[Ziegler & Bender 1997, van Dokkum et al 1998\]).

Unfortunately, one cannot generalize from the results found in distant clusters. In hierarchical models, clusters represent early peaks in the density fluctuations and thus evolution is likely accelerated in these environments (\[Kauffmann 1995\]) plus, of course, there may be processes peculiar to these environments involving the intracluster gas. It is also important to distinguish between the history of mass assembly and that of the stars. Recent evidence for widespread merging of ellipticals in clusters (\[van Dokkum et al 1999\]) lends support to the idea that the stars in dense regions were formed at high redshift, in lower mass systems which later merged.

For these reasons, attention has recently switched to tracking the evolution of field ellipticals. The term field elliptical is something of a misnomer here since a high fraction of ellipticals actually reside in clusters. What is really meant in this case is that we prefer to select ellipticals systematically in flux-limited samples rather than concentrate on those found in the cores of dense clusters‡‡‡‡‡‡$`\mathrm{}`$A major concern in all the work relating to the evolution of galaxies in clusters is precisely how the clusters were located..

The study of evolution in field ellipticals is currently very active and I cannot possibly do justice, in the space available, to the many complex issues being discussed. Instead let me summarise what I think are the most interesting results.

* Searches for a population of faint intrinsically red objects, representing the expected $`z>`$1 precursors of passively-evolving ellipticals which formed their stars at high redshift have been conducted both with and without HST morphological data (\[Zepf 1997, Barger et al 1999a, Menanteau et al 1999, Daddi et al 2000, McCarthy et al 2000\]). However, only recently have substantial areas of sky been mapped. This is because such searches are most sensitive to high $`z`$ sources when conducted using optical-near infrared colors and access to large infrared arrays is a recent technical development. Both Daddi et al (2000) and McCarthy et al (2000) (Figure 10) claim strong angular clustering in their faint red populations and there is limited evidence that the abundance is consistent with a constant comoving number density, in contrast to the hierarchical predictions. However, without confirmatory spectroscopy neither the redshift range nor the nature of these red sources is yet clear. Even if it later emerges, as was claimed on far less convincing data (\[Zepf 1997, Barger et al 1999a, Menanteau et al 1999\]), that there is a shortage of intrinsically red objects beyond $`z`$1, only a modest amount of residual star formation is needed to substantially bluen a well-established old galaxy (\[Jimenez et al 1999\]). Even when redshift data is secured, color alone may be an unreliable way to track a specific population.

Figure 10:Evidence for a clustered population of red objects in a 1000 arcmin2 area of the ongoing Las Campanas Infrared Survey (\[McCarthy et al 2000\]). The angular correlation function for objects with $`IH>`$3.5 (top set of data points) is substantially above that for all $`H`$-selected galaxies (bottom set) and consistent with a high fraction of the red objects being clustered ellipticals with $`\overline{z}`$1.0-1.5.
* At brighter magnitudes, systematic redshift surveys with associated HST data give constraints on the luminosity function and colors of morphologically-selected ellipticals (\[Brinchmann et al 1998, Schade et al 1999, Menanteau et al 1999, Im et al 2000\]). Unfortunately, because of the disparity in field of view betweeen WFPC-2 and the ground-based multislit spectrographs, the samples remain small and hence the conclusions are subject to significant field-to-field clustering uncertainties. However, no substantial decline in the volume density of ellipticals is yet observed to $`z`$1, although there is some dispute as to the fraction which may deviate in color from the passive track (\[Im et al 2000\] c.f. \[Menanteau et al 1999\]). Current spectroscopic surveys may not be quite deep enough to critically test the expected evolution in the hierarchical models, particularly if $`\mathrm{\Lambda }`$0.
* A completely independent method of determining whether field ellipticals form continously as expected in hierarchical models is possible in the Hubble Deep Fields (Menanteau et al 2000). Here, the imaging signal/noise is sufficient to permit an examination of the internal colors of ellipticals with $`I<`$24, a subset of which have redshifts. Menanteau et al (2000) find about 25% of the HDF ellipticals show blue cores and other color inhomogeneities suggestive of recent star formation, perhaps as a result of the merger with a gas-rich low mass galaxy. Keck spectroscopy (\[Ellis et al 2001\]) supports this suggestion: galaxies with blue cores generally show emission and absorption line features indicative of star formation (Figure 11). The amount of blue light seen in the affected ellipticals can be used to quantify the amount of recent star formation and the associated spectrum can be used to estimate the timescale of activity through diagnostic features of main sequence stars. Only modest accretion rates of $``$10% by mass over $``$1 Gyr are implied, albeit for a significant fraction of the population. This continued growth, whilst modest c.f. expectations of hierarchical models, is noticeably less prominent in rich clusters (\[Menanteau et al 2000\]).

Figure 11:Color inhomogeneities in HDF field ellipticals suggest continued star formation is occurring, possibly as a result of hierarchical assembly. Each row displays the $`I`$ band HST image, a $`VI`$ color image and the Keck LRIS spectrum. The top set refers to a $`z`$=0.92 elliptical with a blue core; its spectrum shows features indicative of active star formation (\[O II\] emission and deep Balmer absorption lines). The bottom set refers to a quiescent example at $`z`$=0.966 whose spectrum is consistent with an old stellar population. The amount of blue light can be combined with the depth of the spectral features to statistically estimate the amount and timescale of recent star formation.

What evolution is found in the properties of other kinds of galaxy? Brinchmann et al (1998) secured HST images for a sizeable and statistically-complete subset of CFRS and LDSS redshift survey galaxies and found the abundance of spirals to $`I`$=22 - a flux limit which samples 0.3$`<z<`$0.8 - is comparable to that expected on the basis of their local abundance if their disks were somewhat brighter and bluer in the past as evidenced from surface photometry (\[Lilly et al 1999\]). In practice, however, the detectability of spiral disks is affected by a number of possible selection effects (\[Simard et al 1999, Bouwens & Silk 2000\]) and it may be some time before a self-consistent picture emerges.

A less controversial result from Brinchmann et al (1998) claimed in earlier analyses without redshift data (\[Glazebrook et al 1995, Driver et al 1995\]) is the remarkably high abundance of morphologically-peculiar galaxies in faint HST data. Brinchmann et al quantified this in terms of the luminosity density arguing that a substantial fraction of the claimed decline in the blue luminosity density since $`z`$1 (c.f. Figure 6) arises from the demise of this population (Figure 12).

Figure 12:The morphological dependence of the blue luminosity density from that subset of the CFRS/LDSS redshift survey imaged with HST (Brinchmann et al 1998). The marked decline in the luminosity density of galaxies with peculiar morphology over 0$`<z<`$1 is the primary cause for steep slope in the blue faint galaxy counts.

Given our earlier concerns with over-interpreting the cosmic star formation history, should we be cautious in drawing conclusions from Figure 12? Although Brinchmann et al’s redshift sample is small, the basic result is consistent with the HST morphological number counts where much larger samples are involved. Whereas early skeptics argued that morphologically-peculiar galaxies represent regular systems viewed at unfamiliar ultraviolet wavelengths, recent NICMOS imaging (see Dickinson’s lectures) suggests such ‘morphological bandshifting’ is only of minor consequence. In quantitative detail, as before, uncertain corrections must be made for the effects of the flux limited sample and of course extinction is a major uncertainty. However, it seems inescapable that the bulk of the decline in blue light (the so-called faint blue galaxy problem, \[Ellis 1997\]) arises from the demise of a population of late-type and morphologically-peculiar systems. A key question therefore is what happened to this population? We will address this problem in the next section.

## 5 Constraining the Masses of Distant Galaxies

A recurring issue arises from the discussions in the earlier sections. Whilst observers are, with some restrictions, able to measure distant galaxy properties such as rest-frame colors, luminosities and star formation rates, these may be poor indications of the underlying stellar and total masses predicted most straightforwardly by contemporary models of structure formation. Either we put our faith in the forward modelling of the readily-available observables (i.e. we invest a lot of effort in understanding the complexities of feedback, Figure 7), or we consider how to measure galactic masses.

Ideally we seek methods for determining the total mass (baryonic plus the dark matter halo) but this seems out of reach for the moment except for local systems with tracers of the larger halo in which galaxies are thought to reside. Useful tracers here include the dynamical properties of attendant dwarf galaxies (\[Zaritsky et al 1998\]) and globular clusters (\[Huchra et al 1998\]). A promising route in the future might be galaxy-galaxy gravitational lensing (\[Blandford & Narayan 1992\]). Here a foreground population is restricted in its selection, perhaps according to morphology or redshift, and the statistical image distortions in a background population analysed. Early results were based on HST data, for cluster spheroidals (\[Natarajan et al 1999\]) and various field populations (\[Griffiths et al 1996\]), however with extensive panoramic data from the Sloan Digital Sky Survey, convincing signals can be seen with ground-based photometry (\[Fischer et al 2000\]). Again, photometric redshifts will be helpful in refining the sample selection and in determining the precise redshift distribution essential for accurate measures on an absolute scale.

Unfortunately, promising though the technique appears, the restrictions of galaxy-galaxy lensing are numerous. It only gives mass estimates for statistical samples: the signal is too weak to be detected in individual cases, unless a strong lensing feature is seen (\[Hogg et al 1996\]). Moreover, the redshift range and physical scale on which the mass is determined is defined entirely by geometrical factors and, ultimately, one may never be able to apply the method to galaxies beyond $`z`$1.

Extensive dynamical data is becoming available for restricted classes of high redshift galaxy, via linewidth measures (\[Koo et al 1995\]), resolved rotation curves (\[Vogt et al 1997\]) for sources with detectable \[O II\] 3727 Å emission, and via internal stellar velocity dispersions for absorption line galaxies such as spheroidals. Under certain assumptions, these give mass estimates and have enabled the construction of the fundamental plane for distant spheroidals (\[Treu et al 2000\]) and the Tully-Fisher relation for high redshift disk galaxies (\[Vogt et al 1997\]). The greatest progress in the former has been in constructing the fundamental plane in rich clusters (\[van Dokkum et al 1998\]) where slow evolution in the inferred mass/light ratio for cluster ellipticals is consistent with a high redshift of formation (see $`\mathrm{\S }`$5). For the emission line studies it is not straightforward to convert data obtained over a limited spatial extent into reliable masses even for regular well-ordered systems. For compact and irregular sources, the required emission lines may come from unrepresentative components yielding poor mass estimates (\[Lehnert & Heckman 1996\]).

The prospects improve significantly if we drop the requirement to measure the total mass and are willing to consider only the stellar mass. In this case, the near-infrared luminosity is of particular importance. Broadhurst et al (1992) and Kauffmann & Charlot (1998) have demonstrated that the $`K`$ (2$`\mu `$m) luminosity is a good measure of its underlying stellar mass regardless of how that mass assembled itself (Figure 13). This remarkable fact arises because $`K`$-band light in all stellar populations (whether induced in bursts or continuous periods of activity) arises from long-lived giants whose collective output mirrors the amount of past activity, smoothing over its production timetable.

Figure 13:The $`K`$-band luminosity is a good measure of the underlying stellar mass irrespective the past star formation history (Kauffmann & Charlot 1998). The curves show the observed $`K`$ magnitude as a function of the redshift at which such an object is selected for a system containing 10$`{}_{}{}^{11}M_{}^{}`$ produced according to a variety of star formation histories. Even across extreme cases (single burst at $`z=\mathrm{}`$, solid line, to a constant star formation rate to the epoch of observation, short-dash), the $`K`$-band output remains the same to within a factor of $``$2. The lower panel shows, how different the observed optical-infrared color would be in these cases.

A deep K-band redshift survey thus probes the very existence of massive systems at early times. A slightly incomplete survey to $`K`$=20 (\[Cowie et al 1996\]) and a complete photometric survey to $`K`$=21 (\[Fontana et al 1999\]) indicates an apparently shortfall of luminous $`K`$ objects beyond $`z`$1-1.5 c.f. pure luminosity evolution models. Unfortunately, small sample sizes, field-to-field clustering, spectroscopic incompleteness and untested photometric redshift techniques beyond z$``$1 each weaken this potentially important conclusion. An important goal in the immediate future must be to reconcile these claims with the apparently abundant (and hence conflicting) population of optical-infrared red objects to $`K`$19-20 (\[Daddi et al 2000, McCarthy et al 2000\]).

The precision of the technique introduced by Kauffmann & Charlot (1998) can be improved if the optical-infrared color is available as an extra parameter (\[Ellis et al 2000\]). In this way a first-order correction can be made for the past star formation history and hence the effect of the spread in the lower panel of Figure 13 can be used to improve the mass estimate. Importantly, such a technique for determine accurate stellar masses can then be applied to all galaxies, regular or peculiar, irrespective of their dynamical state and over a range in redshift (providing the data is sufficiently precise). The technique can be considered as a modification of that frequently utilised in estimating photometric redshifts. The observed optical-infrared SED for an object of known redshift is used to optimally fit the stellar mass rather than the redshift in the framework of an evolutionary synthesis code. Stellar masses can be derived to within a random uncertainty of 30-50% by this technique although at present there is no reliable way to verify the results except by comparison with independent dynamical measures (Figure 14).

Figure 15:Evolution of the stellar mass density $`\rho _{stars}(z,T)`$ from the analysis of Brinchmann & Ellis (2000). A remarkable decline with time in stellar mass density is seen for the morphologically-peculiar class which argues against a truncation of their star formation activity as the primary cause for their demise. Brinchmann & Ellis argue that this population must be transforming, possibly via mergers, into the regular classes. A simple model which implements a likely redshift-dependent merger rate (\[LeFevre et al 2000\]) with elliptical products can broadly reproduce the trends observed (shaded area of the plot).

## 6 Origin of the Hubble Sequence

The availability of stellar masses for all types enables the construction of a powerful evolutionary plot, analogous to Figure 6, involving the stellar mass density, $`\rho _{stars}(z,T)`$, as a function of morphology $`T`$. Whilst the stellar mass density can grow by continued star formation, unlike the UV luminosity density, $`\rho _{UV}`$, it is difficult to imagine how it can decline. As we saw earlier $`\rho _{UV}`$ can decline significantly in only 1-2 Gyr because of an abrupt truncation of activity. However, such a change would have very little effect on the infrared output as illustrated in Figure 13.

Brinchmann and Ellis (2000) secured $`K`$ luminosities and optical-IR SEDS for over 300 galaxies in the CFRS/LDSS and Hawaii survey fields and derive $`\rho _{stars}(z,T)`$ (Figure 15). Estimating the integrated stellar mass density is prone to all of the difficulties reviewed earlier for the luminosity density and there is the added complication that the redshift surveys in question are optically-selected and thus must miss some (red) fraction of a true $`K`$-limited sample. Accordingly, the mass densities derived are lower limits to the true values.

Remarkably, $`\rho _{stars}(z,T)`$ is a declining function for the intriguing population of morphologically-peculiar galaxies. Whereas the declining UV luminosity density could imply a fading population, such an explanation cannot be consistent with Figure 15 which argues, instead, that the objects are genuinely disappearing into other systems. The most logical explanation for their declining contribution to the stellar mass density is that morphologically-peculiar objects are being transformed, e.g. by mergers, into regular objects.

Figure 16:An increase in the merger fraction as a function of redshift from the HST analysis of LeFevre et al (2000). Galaxies of known redshift were examined for satellites brighter than a fixed rest-frame luminosity within a projected radius of 20$`h^1`$ kpc and corrections made for unrelated line-of-sight contamination. This redshift-dependent merger rate was adopted by Brinchmann & Ellis (2000) in Figure 15.

Merging has been an attractive means for governing the evolution of galaxies for many years (\[Toomre & Toomre 1972, Rocca-Volmerange & Guiderdoni 1989, Broadhurst et al 1992\]) and of course is fundamental to the hierarchical formation picture. However it has been extremely difficult to determine the observed rate at intermediate redshift. The fundamental problem is that we observe galaxies at various look-back times via discrete ‘snapshots’ without ever being able to prove two associated systems are destined to merge on a particular timescale. Using the CFRS/LDSS HST dataset referred to earlier, LeFevre et al (2000) undertook a quantitative survey of the fraction of luminous galaxies with satellites brighter than a fixed absolute magnitude within a 20$`h^1`$ kpc metric radius and, after allowance for projection effects, determined the merger fraction increases with redshift as $`(1+z)^{3.4\pm 0.5}`$ \- a result consistent with earlier ground-based efforts. Sadly, it is not straightforward to convert the proportion of galaxies with associated sources into a physical merger rate or, as ideally required, a mass assembly rate without some indication of the dynamical timescale for each merger and the mass of each satellite. Moreover, there are several annoying biases that affect even the derived merger fraction.

Brinchmann & Ellis (2000) attempted to reconcile the decline of the morphologically-peculiar population, the redshift dependence of the LeFevre et al merger fraction and associated evidence for continued formation of ellipticals (\[Menanteau et al 2000\]) into a simple self-consistent picture. They transferred the dominant population of morphologically-irregular galaxies, via the $`z`$-dependent merger rate, into a growth in the regular galaxies (shaded area of Figure 15). This is clearly a simplistic view, but nonetheless, gives a crude empirical rate at which regular galaxies are assembling. If correct, how does this agree with mass assembly histories predicted, say in $`\mathrm{\Lambda }`$CDM?

Figure 17:Predicted evolution in stellar mass functions for disk and spheroidal populations in a $`\mathrm{\Lambda }`$CDM hierarchical model (Frenk, priv. comm). The curves define mass functions as a function of redshift ($`z`$=0,0.5,1,2, from right to left). Modest growth over 0$`<z<`$2 is expected for disk galaxies but significant growth is predicted for massive spheroidals.

Figure 17 shows a recent prediction of the assembly history of spheroids and disks (Frenk, private communication). Although there are some discrepancies between this and its equivalent prediction from Kauffmann & Charlot (1998, Figure 3), the trends are clear. The strongest evolutionary signal is expected in terms of a recent assembly of massive spheroids; the equivalent growth rate in stellar disks is more modest. To the extent it is currently possible to test this picture, the qualitative trend is supported by the data. Field ellipticals are certainly still assembling (\[Menanteau et al 2000\]) but perhaps more slowly than expected according to Figure 17; unfortunately deeper samples with redshifts are needed for a precise statement. Brinchmann (in prep.) has examined the stellar mass growth rate in disks using the infrared-based method over 0$`<z<`$1 and finds only modest changes. This is very much a developing area and one that would benefit from significantly enlarged HST datasets chosen to overlap the growing faint redshift survey databases.

Figure 18:Face-on barred spirals of known redshift in the Hubble Deep Field. Abraham et al (1999) claim that all such systems should easily be recognised to z$``$1 in HDF-quality data whereas, beyond z$``$0.6, there appears to be a marginal paucity of such systems compared to their non-barred counterparts. If supported by further data, this could indicate an epoch corresponding to the ‘dynamical maturing’ of stellar disks.

The HST data, particularly that in the Hubble Deep Fields (HDF), is an astonishingly rich resource which is still not completely exploited. As an indication of what might be possible with future instrumentation, I will close with some remarks on the important role that bulges and bars may play in the history of the Hubble sequence.

50% of local spirals have bars which are thought to originate through dynamical instabilities in well-established differentially-rotating stellar disks. If we could determine the epoch at which bars begin appearing, conceivably this would shed some light on how recently mature spirals came to be. Via careful simulations based on local examples, Abraham et al (1999) showed that face-on barred galaxies should be recognisable to $`z`$1 in the HDF exposures. In fact, many are seen (Figure 18) but tantalisingly the barred fraction of face-on spirals appears to drop beyond a redshift z$``$0.6. The effect is marginal but illustrative of a powerful future use of morphological imaging with the Advanced Camera for Surveys.

The story with bulges is also unclear, although potentially equally exciting. Traditionally, bulges were thought to represent miniature ellipticals which formed monolithically at high redshift (\[Eggen, Lynden-Bell & Sandage 1962\]). Detailed studies of local examples, including the Galactic bulge, have shown a considerable diversity in properties, both in integrated color and even in their photometric structure (\[Wyse 1999\]). There is some evidence of a bimodality in the population; prominent bulges in early type spirals share surface brightness characteristics of ellipticals, whereas those in late-type spirals are closer to exponential disks. This might indicate two formation mechanisms, one primordial (as in the traditional picture), the other related perhaps to the merging assembly history or via disk instabilities through what is termed ‘secular’ evolution.

Taking advantage of the HDF images, including those from NICMOS, Ellis et al (2000) have examined the color distribution for a large sample of spirals bulges of known redshift and compared these colors with their integrated equivalent for the HDF ellipticals. If bulges are miniature ellipticals formed at high redshift, one would expect similar trends. Interestingly, in the hierarchical picture, one expects bulges to be older and presumably redder than ellipticals (since the latter predominantly form from merged disk systems which most likely contain bulges as early merger remnants). Ellis et al (2000) find intermediate redshift bulges are the reddest part of a typical spiral but, surprisingly, they are often bluer than their elliptical counterparts and far less homogeneous as a population. Contamination from disk light is an obvious concern though simulations suggest only modest bias arises to redshifts where these trends become prominent. What could be responsible for this puzzling behavior? Evolutionary synthesis modelling suggest only a modest amount of star formation corresponding to continued infall of $``$5% by mass would be needed to explain the bluing.

## 7 Conclusions

In summary, despite the frantic increase in publication rate in this field, there is an enormous amount of work still to be done, both observationally, in exploiting the connection between resolved images from HST and ground-based spectroscopy, and theoretically, in predicting more accurately the expected evolutionary histories of resolved components. In my opinion the subject suffers too much from a satisfaction with simply replicating, according to a particular theory, a range of observations. This is particularly dangerous when the observables are luminosities, colors and star formation rates since the theoretical parameters involved are numerous. The challenge will be to overcome the obvious limitations we presently face in determining galactic masses for complete samples of galaxies viewed at various look-back times, as well as integrating the growing body of data being obtained in the far infrared and sub-mm spectral regions.

###### Acknowledgements.

I thank my students, past and present, and collaborators at Cambridge, Caltech and elsewhere for allowing me to present the results of unpublished work undertaken with them. I also thank Marc Balcells, Ismael Perez-Fournon and Francisco Sanchez for inviting me to Tenerife to give these lectures and for their remarkable patience in waiting for this written version.


format: text

text:
# Encoded Universality in Physical Implementations of a Quantum Computer

## I Introduction

Our generous universe comes equipped with the ability to compute. In physics, determination of the *allowable* manipulations of a physical system is of central importance. Computer science, on the other hand, has arisen in order to *quantify* what resources are needed in order to perform a certain algorithmic function. For computer science to be applicable to the real world, this quantification should be limited by what physics has determined to be allowable manipulations. Thus we arrive at the realization that because information is physical, computer science should be built on primitives which respect the laws of physics.

An important property of classical information which carries over to the quantum world is the fungible nature of information. A resource is fungible if interchanging it with another resource does not destroy the value of the resource. Whether we represent a classical bit by the presence or absence of a chad on a punch-card or in the average orientation of a million electron spins, the intrinsic value of the information (the value of the bit) is untouched: it does not depend upon the medium in which it is represented. The fungible nature of information has been key to the exponential growth of the computer revolution: it does not matter that the information is being confined to ever smaller components on silicon chips. So, too, for quantum information: the plethora of experimentally proposed systems from which a quantum computer could be built is made possible by the fungibility of quantum information.

Another example of the fungible nature of quantum information is the idea that one can *encode* quantum information. The theory of quantum error correcting codes, for instance, makes use of this to allow computation in the presence of noise. In this paper we argue that we can harness the fungible nature of quantum information in another important aspect, namely in universality constructions. In particular, we propose that instead of taking a physical system and adding external Hamiltonians and interactions to it so that a certain universal set of gates may be performed, one examines instead the intrinsic system interactions for their potential universality. The key to this approach is the recognition that the ability to encode quantum information allows for certain interactions to be universal over an encoded Hilbert subspace, even though they are not universal over the entire Hilbert space. Our task is then to search for the encodings providing such universality, given the intrinsic system interactions. Such encoded universality is common in quantum error correction but appears to have not been recognized in the discussions concerning the physical construction of a quantum computer.

## II Universality

The action of gates $`𝐆`$ on a circuit corresponds to unitary evolution of the system, with the gates given by the evolution operators derived from the system Hamiltonian $`𝐇`$: $`𝐆(t)=𝚃\left\{\mathrm{exp}[i^t𝐇(\tau )𝑑\tau ]\right\}`$. Here $`𝚃`$ denotes the time ordering operation. A finite set $`𝒢`$ of gates is defined to be *universal* if: i) each $`𝐔_i𝒢`$ acts on a constant number of qubits only, and ii) any quantum circuit (performing any desired unitary operation) can be simulated to arbitrary accuracy efficiently by a circuit with gates in $`𝒢`$.

Somewhat surprisingly, most discussions of universality in quantum computing are cast in the language of gates, rather than Hamiltonians. As physicists we find, however, that in order to understand encoded universality, it is often more useful to think about a gate in terms of the generating Hamiltonian instead of the resulting gate. Given the notion of a universal set of gates, various physical implementations of such a quantum computer have been proposed. Naturally, in order to qualify as a valid quantum computer, each physical implementation must be shown to possess a universal set of gates arising from controllable interactions of the given physical system. To date, with some exceptions, all physical proposals for a quantum computer have implemented a set of universal gates via a route in which: (i) the basic qubit is identified in the physical system, (ii) single-qubit unitary gates are shown to be possible on these qubits, and (iii) some two-qubit gate acting between qubits is shown to be possible. The latter is usually a CNOT or a controlled phase. For a few systems this standard model does provide a natural path towards building a quantum computer, but for other implementations severe device engineering must be performed in order to force the system to achieve this universal set of gates.

For instance, in many solid state implementations a fast intrinsic interaction is the exchange interaction (Heisenberg coupling)

$$𝐄_{ij}=\stackrel{}{\sigma }^i\stackrel{}{\sigma }^j,$$
(1)
(here $`\stackrel{}{\sigma }^i`$ is the vector of Pauli spin matrices $`(\sigma _x,\sigma _y,\sigma _z)`$ on the $`i`$-th qubit). We call $`𝐄_{ij}`$ the exchange interaction because addition of a global phase and rescaling gives a Hamiltonian which exchanges the qubits $`(|x|y|y|x)`$. The gates which can be obtained by tuning the exchange interaction strength $`J`$ are the unitary gates $`𝐔_{ij}(t)=\mathrm{exp}(itJ𝐄_{ij})`$. Given $`n`$ qubits coupled via exchange interactions it can be shown that these gates alone cannot be used to implement an arbitrary quantum circuit on $`n`$ qubits. Thus designers of solid state quantum computers have had to supplement the exchange interaction by single-qubit rotations in order to make their set of interactions universal over all $`n`$ qubits. However, adding this single-qubit capability generally leads to considerable device complexity and to disadvantages such as slow single-qubit gate times and possible additional sources of decoherence resulting from addition of auxiliary, non-intrinsic interactions to the system.

It was recently realized that the exchange interaction by itself can be used to simulate a quantum circuit if a particular encoded space of three or more qubits is used to represent the quantum information. Thus while the exchange interaction on $`n`$ qubits cannot be used to implement an arbitrary quantum circuit on $`n`$ qubits, it can be used to simulate a quantum circuit on $`cn`$ qubits, where $`c`$ is a constant representing the encoding efficiency of such a code. The fact that the exchange interaction alone can be used to simulate a quantum circuit by using encoded quantum information allows one to avoid implementing the generally difficult single-qubit gates.

This example illustrates a new approach to universality very different from the conventional paradigm of using single qubit-gates supplemented by a two-qubit gate. The latter has consituted the primary guideline in recent years for deciding whether a physical system might be used as a quantum computer, without regard to the fact that this is just one of many possible paths to universality. Nevertheless, other approaches have also been proposed. Thus, it was shown that *almost any* two-qubit unitary gate along with the exchange gate acting between $`n`$ qubits is universal over all $`n`$ qubits. We propose here a radically different route to achieve universality, namely, that starting from the natural interactions given by the physics of the proposed qubit system (e.g., $`𝐄_{ij}`$), the underlying potential of that interaction for encoded universality be investigated. For a given physical system, the natural interactions of choice should be determined by various factors including their speed, the ease with which they can be implemented, and their robustness towards decoherence processes. The path we take, then, is to proceed from the intrinsic interactions to encoded universality, rather than to artificially modify or build the interactions to fit a standard model.

## III General Formalism

The general formalism will be illustrated here with the example of the exchange interaction. We omit most of the proofs and details, which can be found in Ref. 4.

Assume that we are given a set of interactions on some $`d`$-dimensional Hilbert space – Hermitian Hamiltonians $`h_i(t)𝐇_i`$ where $`h_i(t)`$ are controllable coupling constants – that we want to use for our universal quantum computer. Which unitary gates can be approximated by turning these interactions on and off (perhaps in parallel)? The answer to this is that every unitary gate in the Lie group corresponding to the Lie algebra *generated* by the Hamiltonians $`𝐇_i`$ can be approximated to arbitrary accuracy by a sequence of gates obtained through the temporal evolution of $`h_i(t)𝐇_i`$. This is true because of the following properties:

$`e^{i(\alpha 𝐀+\beta 𝐁)}=\underset{n\mathrm{}}{lim}(e^{i\alpha 𝐀/n}e^{i\beta 𝐁/n})^n`$ (2)
$`e^{[𝐀,𝐁]}=\underset{n\mathrm{}}{lim}(e^{i𝐀\sqrt{n}}e^{i𝐁/\sqrt{n}}e^{i𝐀/\sqrt{n}}e^{i𝐁\sqrt{n}})^n.`$ (3)
To approximate to a given accuracy, say $`\mathrm{exp}(i(\alpha 𝐀+\beta 𝐁))`$, by a sequence of gates with generators $`𝐀`$ and $`𝐁`$ one just truncates Eq. (2) for large enough $`n`$. Every element in the Lie algebra, that is the algebra formed via linear combination ($`\alpha 𝐀+\beta 𝐁`$) and via the Lie commutator ($`i[𝐀,𝐁]`$), can be approximated to given accuracy using these results. Thus all gates in the Lie group corresponding to this Lie algebra generated by the $`𝐇_i`$ can be approximated to arbitrary accuracy by using the controllable coupling constants $`h_i(t)`$. The inverse of this statement is also true.

Let $`𝒜`$ be the Lie algebra generated by the $`𝐇_i`$. The Lie group generated by the Lie algebra $`𝒜`$ is a subgroup of the $`d`$-dimensional unitary group $`U(d)`$ and thus is a compact Lie group. An important property of compact Lie groups is that they, along with the Lie algebra which generates the Lie group, are completely reducible. A representation of a Lie algebra is irreducible if the action of the representation on its vector space does not possess an invariant subspace. An algebra which is completely reducible can be written as a direct sum of irreducible representations (irreps):

$$𝒜\underset{J}{}\underset{\lambda =1}{\overset{n_J}{}}_J,$$
(4)
where $`_J`$ is the $`J`$th irrep which appears with degeneracy $`n_J`$ and is $`d_J`$-dimensional. For the operators $`𝐇_i`$ this implies that there is a basis for the Hilbert space on which $`𝐇_i`$ acts as

$$𝐇_i=\underset{J}{}𝐈_{n_J}(𝐋_J)_i$$
(5)
where $`(𝐋_J)_i`$ are elements of the $`J`$th irrep $`_J`$ and $`𝐈_d`$ is the $`d`$-dimensional identity operator. Clearly, understanding the irreps of the Lie algebra generated by the Hamiltonians $`𝐇_i`$ will allow us to understand the suitability of this Lie algebra for simulating a quantum circuit. In particular, Eq. (5) implies that with a *suitable encoding* the $`𝐇_i`$ can produce the action of a specific irrep $`_J`$. This action may or may not be useful for quantum computation, an issue we address below.

It is often helpful in understanding the universality of an interaction to find the *commutant* $`𝒜^{}=\{𝐗:[𝐗,𝐀]=0,𝐀𝒜\}`$ of the Lie algebra $`𝒜`$. It should be clear from Eq. (5) that every element $`𝐊𝒜^{}`$ is reducible to:

$$𝐊=\underset{J}{}_{n_J}𝐈_{d_J}$$
(6)
where $`_{n_J}`$ is an $`n_J`$-dimensional (complex) square matrix, and $`d_J`$ is the dimension of the $`J`$th irrep. This structure, dual to $`𝒜`$, offers a useful way for seeing how the encoding arises: $`𝒜^{}`$ splits into a sum of degenerate irreps. The degeneracy of a particular representation gives the dimension of the space over which the encoding is made.

We should point out a non-trivial aspect of the question of “universality given a set of interactions”, which makes our task more difficult. This is the tensor product nature of quantum computation. We recall that a set of interactions is universal if it can be used to efficiently simulate a quantum circuit. An important property of the quantum circuit model is that at its most basic level it possess a tensor product of single qubit systems. Hidden within this seemingly trivial fact is the notion of locality: we believe that physics is local and hence we require our model of computation based on physics to preserve this locality. For the purposes of building a universal quantum computer this implies that we must, at some point, introduce a suitable tensor product structure in order to *efficiently* simulate a quantum circuit. The above discussion of representation theory for Lie algebras has been solely in terms of some abstract $`d`$-dimensional Hilbert space. We now admit two tensor product structures: first, on our physical system, and second, on the encoded qubits from which encoded universality will be constructed. The first tensor product structure is simply that implied by our physical system and is forced on us by the locality of physics. For example, if we are using the spins of single electrons on a quantum dot, the tensor product is just the natural one of these spin-qubits. The nature of this tensor product structure is also manifest in the set of interactions which will be present in the real world, and is represented in the Hamiltonian as operators acting on separate degrees of freedom.

The second tensor product is required by the fact that we are going to simulate a quantum circuit. Given a set of interactions, we know that these can be used to produce the action of a given set of irreps $`_J`$. However, without a mapping from the subspace on which the irrep acts to the tensor product structure of a quantum circuit, this is not enough to quantify the suitability of the interactions for universality. The exact cutoff where this tensor product structure comes into play is somewhat arbitrary. We will take the position here that we are searching for *small encodings*. That is, we seek to minimize the number of physical qubits used to encode a logical qubit. This logical qubit will be formed by a block of nearest neighbor qubits with the defining property that single encoded-qubit operations are possible within each such block. Given a set of such encoded qubits we then form a tensor product between pairs of blocks. We refer to this process of forming a tensor product code as “conjoining”. These considerations are illustrated below.

## IV Example of Isotropic Exchange

As an example of our general discussion consider the Heisenberg model for spin-spin interactions. The most general form of this is given by a sum of fully anisotropic pair-wise spin-spin couplings

$$𝐇_{ij}=J_{ij}^X\sigma _x^i\sigma _x^j+J_{ij}^Y\sigma _y^i\sigma _y^j+J_{ij}^Z\sigma _z^i\sigma _z^j.$$
(7)
We consider in detail here the isotropic limit in which the exchange couplings between a given $`ij`$ pair are all equal, i.e., $`J_{ij}^X=J_{ij}^Y=J_{ij}^ZJ_{ij}`$, so that we are dealing then with the Heisenberg Hamiltonian

$$𝐇_{\mathrm{Hei}}=\underset{ij}{}J_{ij}𝐄_{ij}$$
(8)
where we assume that the coupling parameters $`J_{ij}`$ can be turned on/off at will. To show how this intrinsic coupling can lead to encoded universality we analyze its action on three qubits.

The Lie algebra $`_E`$ generated by $`𝐄_{ij}`$ on three qubits allows us to implement the Hamiltonians in the set $`\{𝐄_{12},𝐄_{23},𝐄_{13},𝐓i([𝐄_{12},𝐄_{23}]\}`$. A better basis for the Lie algebra is given by the set of operators $`𝐇_0=𝐄_{12}+𝐄_{23}+𝐄_{13}`$, $`𝐇_1=\frac{1}{4\sqrt{3}}\left(𝐄_{13}𝐄_{23}\right)`$, $`𝐇_3=\frac{1}{12}\left(2𝐄_{12}+𝐄_{23}+𝐄_{13}\right)`$, $`𝐇_2=i[𝐇_3,𝐇_1]`$. We then find that

$$[𝐇_0,𝐇_\alpha ]=0$$
(9)
for all $`\alpha `$ and

$$[𝐇_\alpha ,𝐇_\beta ]=iϵ_{\alpha \beta \gamma }𝐇_\gamma $$
(10)
with $`\alpha ,\beta ,\gamma \{1,2,3\}`$. $`𝐇_0`$ is an abelian invariant subalgebra of this Lie algebra and thus factors out as a global phase. The set $`\{𝐇_1,𝐇_2,𝐇_3\}`$, on the other hand, act as the generators of $`su(2)`$. Thus the exchange interaction between three qubits can be used to implement a single encoded-qubit $`su(2)`$. More precisely, we find that the $`𝐇_\alpha `$ for $`\alpha \{1,2,3\}`$ generates the algebra

$$_E^{(3)}=\left(\underset{i=1}{\overset{4}{}}𝒮_1\right)\left(\underset{i=1}{\overset{2}{}}𝒮_2\right)$$
(11)
where $`𝒮_d`$ is the $`d`$-dimensional irrep of $`su(2)`$. Note the degeneracy of the corresponding irreps. Corresponding to this decomposition the $`𝐇_\alpha `$ act as

$$𝐇_\alpha =\mathrm{𝟎}_4\left(\frac{1}{2}\sigma _\alpha 𝐈_2\right)$$
(12)
for $`\alpha \{1,2,3\}`$ where $`\mathrm{𝟎}_4`$ is 4-dimensional zero operator (the $`1`$ dimensional irreps all act as $`0`$) and $`𝐈_2`$ is the two-dimensional identity operator. The action of the exchange is thus identical to that of an $`su(2)`$ operator on a single qubit when working over the encoded space defined by the above decomposition. If we encode our logical qubits as

$`|0_L`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}(|010|100)`$ (13)
$`|1_L`$ $`=`$ $`\sqrt{{\displaystyle \frac{2}{3}}}|001\sqrt{{\displaystyle \frac{1}{6}}}|010\sqrt{{\displaystyle \frac{1}{6}}}|100`$ (14)
then we find that the action of $`𝐇_\alpha `$ is $`\frac{1}{2}\sigma _\alpha `$. Due to the degeneracy of the irrep, other encodings are also possible. Note that these states are nothing but $`J=1/2`$ total angular momentum states of $`3`$ spin-$`1/2`$ particles with a given projection along a certain axis, and can thus be found using elementary addition of angular momentum.

Having shown that the action of the exchange interaction on three qubits can produce the effect of a single $`2`$-dimensional representation of $`su(2)`$, it is natural to induce a tensor product structure between blocks of three qubits in order to simulate a quantum circuit. We thus *choose* an encoding scheme in which a single qubit is identified with $`3`$ physical qubis. This is not the only choice of tensor product structure. In fact, any tensor product between sets of $`k3`$ qubits can be used to construct a universal gate set. We define the encoding efficiency of our code as the number of encoded bits of our simulated quantum computer ($`e=\mathrm{log}_2(d)`$ where $`d`$ is the dimension of the encoded information) divided by the total number of qubits on which the encoding exists: $`E=e/n=\mathrm{log}_2(d)/n`$. Thus, for a scheme using the exchange interaction between three qubits, where we have a $`d=2`$ dimensional encoding on $`k=3`$ qubits, we find that $`E=1/3`$. A peculiar property of the exchange interaction is that it has an asymptotic encoding efficiency of unity. In particular, if we take $`n`$ qubits and use the exchange interaction to compute on these qubits then the dimension of the encoded space on which we can compute scales in such a way that the encoding efficiency is at least $`E(n)=1\frac{3}{2}\frac{\mathrm{log}_2n}{n}`$.  As $`lim_n\mathrm{}E(n)=1`$ we loose almost nothing in terms of encoding efficiency when we use the exchange interaction. We note, however, that one must still introduce a tensor product structure at some level in order to achieve universal quantum computation.

Once one has introduced a tensor structure for the encoding, it is necessary to show that the natural couplings of the system can produce a non-trivial action between the tensor components of this encoded tensor product structure. In the above case, where we have shown that we can obtain full control over an encoded qubit, what we now need to show is that a non-trivial action between the encoded qubits can be enacted. This is nothing more than a map from the encoded universality to the fully universal set of physical gates consisting of single qubit gates supplemented by a non-trivial coupling between the qubits, i.e., to the standard model. This point of the universality proof is typically the most daunting, but really amounts to nothing more than understanding the Lie algebra generated by the interaction over two tensored encoded qubits. For the exchange interaction it can be shown that nearest neighbor exchange interactions can be used to produce such an action. In particular, we find that the effect of the exchange interaction on $`6`$ qubits becomes

$$_E^{(6)}=\left(\underset{i=1}{\overset{7}{}}𝒮_1\right)\left(\underset{i=1}{\overset{5}{}}𝒮_5\right)\left(\underset{i=1}{\overset{3}{}}𝒮_9\right)𝒮_5$$
(15)
When we conjoin the two three-qubit codes, we find that these codes lie entirely within the last two irreps of this decomposition. This in turn implies that non-trivial interactions between the encoded irreps are possible. In fact the original single encoded qubit $`su(2)`$ is also contained within this decomposition. The important point, however, is that on the tensor product between encoded qubits we can indeed couple these encoded qubits in such a way as to achieve a map to the unencoded, fully universal set of gates. Thus we have established that our encoding can efficiently (to within a factor of three in spatial resources) simulate the unencoded set of universal gates.

A similar analysis can be applied to the anisotropic Heisenberg model (XY model). There it turns out that the smallest encoding one can achieve is a logical qutrit (3-level system) into three physical qubits. For both the isotropic and anisotropic Heisenberg models these universality results are general, i.e., they can be shown to hold for arbitrary numbers of qubits, $`n`$. However, the approach of conjoining small blocks that encode qubits via a tensor product can be generally used to construct the required mapping of universality for arbitrary interactions, even when a general proof appears inaccessible.

## V Outlook

We have shown that the commonly assumed paradigm of universal quantum computation requiring a set of both single-qubit and two-qubit gates can be replaced by a more general notion of encoded universality. This approach allows universality of quantum computation to be achieved via encodings specific to the natural or convenient physical interactions in a system. In the example given here we have discussed an instance where encoded universality can be achieved using only a single underlying physical interaction, namely the exchange interaction. This result is of particular significance for solid state implementations of quantum computation. The approach of coupling blocks containing small numbers of physical qubits (each forming one encoded qubit) via tensor products appears to be applicable to any interaction.

The results for encoded universality that we have described here are primarily existential, and do not address the very practical concerns of the overhead in temporal and spatial resources which may result from encoding. The practical question is then: what is the trade-off in resources of time (gates) and space (qubits) resulting from the universality encoding for a given set of physical interactions? Finding a universality encoding generally immediately reveals the spatial overhead, i.e., the number of physical qubits required to perform the encoding, and may also provide information about the asymptotic overhead. Thus, for the exchange interaction, the maximum spatial overhead is a factor of three, and becomes arbitrarily small asymptotically. The overhead in temporal resources, i.e., how many physical gates are required to implement a given set of encoded universal gates, is somewhat more challenging to deal with. General issues of optimization of physical gates for circuits of encoded qubits have been addressed. It has recently been shown explicitly that the encoded universal operations deriving from the exchange interaction can be realised within $``$ 10 clock cycles. However there does not exist to our knowledge any general methodology to find the optimal gate sequence for a specific two-qubit (or two-qutrit) gate.

The finding of encoded universality for the Heisenberg Hamiltonians suggest that this approach will be very useful for consideration of solid state quantum computation. Establishment of results concerning the existence of encodings for general classes of Hamiltonians is therefore now of interest. The new paradigm of encoded universality clearly opens up significant new opportunities for exploring the architectural realization of quantum computation.

Acknowledgements:- This work was supported in full by the National Security Agency (NSA) and Advanced Research and Development Activity (ARDA) under Army Research Office (ARO) contracts DAAG55-98-1-0371 (KBW) and DAAG55-98-C-0041 (DPD).