text:
# An introduction to quantum game theory

## I Introduction

Game theory is the study of decision making of competing agents in some conflict situation. It was developed in the 1930’s in the context of economic theory and was first formalized by von Neumann and Morgenstern in The Theory of Games and Economic Behavior neumann44 . Subsequently much work was done on game theory and it is now a mature discipline used in areas such as the social sciences, biology and engineering.

With the recent interest in quantum computing and quantum information theory, there has been an effort to recast classical game theory using quantum probability amplitudes, and hence study the effect of quantum superposition, interference and entanglement on the agents’ optimal strategies. Apart from unsolved problems in quantum information theory god , quantum game theory may be useful in studying quantum communication since that can be considered as a game where the objective is to maximize effective communication. Inspired by quantum game theory, within the new branch of mathematical economics, econophysics, workers have attempted to model markets and auctions, assuming traders can use quantum protocols piotr01a ; piotr01b . Here, a quantum strategy, representing a superposition of trading decisions, can give an advantage over classical strategies piotr02 . This, of course, must be distinguished from attempts to use the mathematical machinery of quantum field theory to solve classical financial market problems ilinski ; baaquie01 .

There has been recent work linking quantum games to the production of algorithms for quantum computers lee02  that may lead to new ways of approaching such algorithms. There is also speculation that nature may be playing quantum games at the molecular level eisert99 . In support of this, recent work on protein molecules, including the protein folding problem, is now turning to a full quantum mechanical description at the molecular level gogonea99 .

The seminal work on quantum game theory by Meyer meyer99  studied a simple coin tossing game and showed how a player utilizing quantum superposition could win with certainty against a classical player. A general protocol for two player–two strategy quantum games with entanglement was developed by Eisert et al eisert99  using the well known prisoners’ dilemma as an example and this was extended to multiplayer games by Benjamin and Hayden benjamin00b .

Since then more work has been done on quantum prisoners’ dilemma benjamin00a ; eisert00 ; du01a ; du01b ; du01c ; du02 ; iqbal01a ; iqbal02  and a number of other games have been converted to the quantum realm including the battle of the sexes iqbal01a ; marinatto00 ; du00a ; iqbal01 , the Monty Hall problem li01 ; flitney02a ; dariano02 , rock-scissors-paper iqbal01b , and others du00b ; benjamin00b ; kay01 ; iqbal01c ; iqbal02a ; iqbal02b ; iqbal02c ; johnson01 ; guinea02 .

In section two we introduce some terminology and basic ideas of game theory. Section three will introduce the idea of quantum game theory and give the general protocol for the construction of such games, along with a review of the existing work in this field. Finally, in section four we discuss some questions and suggestions.

## II Game Theory

### II.1 Basic ideas and terminology

Game theory attempts to mathematically model a situation where agents interact. The agents in the game are called players, their possible actions moves, and a prescription that specifies the particular move to be made in all possible game situations a strategy. That is, a strategy represents a plan of action that contains all the contingencies that can possibly arise within the rules of the game. In response to some particular game situation, a pure strategy consists of always playing a given move, while a strategy that utilizes a randomizing device to select between different moves is known as a mixed strategy. The utility to a player of a game outcome is a numerical measure of the desirability of that outcome for the player. A payoff matrix gives numerical values to the players’ utility for all the game outcomes. It is assumed that the players will seek to maximize their utility within the given rules of the game. Games in which the choices of the players are known as soon as they are made are called games of perfect information. These are the main ones that are of interest to us here.

A dominant strategy is one that does at least as well as any competing strategy against any possible moves by the other player(s). The Nash equilibrium (NE) is the most important of the possible equilibria in game theory. It is the combination of strategies from which no player can improve his/her payoff by a unilateral change of strategy. A Pareto optimal outcome is one from which no player can obtain a higher utility without reducing the utility of another. Strategy $`A`$ is evolutionary stable against $`B`$ if, for all sufficiently small, positive $`ϵ`$, $`A`$ performs better than $`B`$ against the mixed strategy $`(1ϵ)A+ϵB`$. An evolutionary stable strategy (ESS) msmith73  is one that is evolutionary stable against all other strategies. The set of all strategies that are ESS is a subset of the NE of the game. A two player zero-sum game is one where the interests of the players are diametrically opposed. That is, the sum of the payoffs for any game result is zero. In such a game a saddle point is an entry in the payoff matrix for (say) the row player that is both the minimum of its row and the maximum of its column.

### II.2 An example: the prisoners’ dilemma

A two player game where each player has two possible moves is known as a $`2\times 2`$ game, with obvious generalizations to larger strategic spaces or number of players. As an example, consider one such game that has deservedly received much attention: the prisoners’ dilemma. Here the players’ moves are known as cooperation ($`C`$) or defection ($`D`$). The payoff matrix is such that there is a conflict between the NE and the Pareto optimal outcome. The payoff matrix can be written as

$$\begin{array}{ccc}& \text{Bob}:C& \text{Bob}:D\\ & & \\ \text{Alice}:C& (3,3)& (0,5)\\ \text{Alice}:D& (5,0)& (1,1)\end{array}$$
(1)
where the numbers in parentheses represent the row (Alice) and column (Bob) player’s payoffs, respectively. The game is symmetric and there is a dominant strategy, that of always defecting, since it gives a better payoff if the other player cooperates (five instead of three) or if the other player defects (one instead of zero). Where both players have a dominant strategy this combination is the NE.

The NE outcome $`\{D,D\}`$ is not such a good one for the players, however, since if they had both cooperated they would have both received a payoff of three, the Pareto optimal result. In the absence of communication or negotiation we have a dilemma, some form of which is responsible for much of the misery and conflict through out the world.

## III Quantum Game Theory

### III.1 Introductory ideas: penny flip

A two state system, such as a coin, is one of the simplest gaming devices. If we have a player that can utilize quantum moves we can demonstrate how the expanded space of possible strategies can be turned to advantage. Meyer, in his seminal work on quantum game theory meyer99 , considered the simple game “penny flip” that consists of the following: Alice prepares a coin in the heads state, Bob, without knowing the state of the coin, can choose to either flip the coin or leave its state unaltered, and Alice, without knowing Bob’s action, can do likewise. Finally, Bob has a second turn at the coin. The coin is now examined and Bob wins if it shows heads. A classical coin clearly gives both players an equal probability of success unless they utilize knowledge of the other’s psychological bias, and such knowledge is beyond analysis by standard game theory 111 The biases of opposing players can be modeled with game theory but additional formalism is required rubinstein98 ..

To quantize this game, we replace the coin by a two state quantum system such as a spin one-half particle. Now Bob is given the power to make quantum moves while Alice is restricted to classical ones. Can Bob profit from his increased strategic space? Let $`|0`$ represent the “heads” state and $`|1`$ the “tails” state. Alice initially prepares the system in the $`|0`$ state. Bob can proceed by first applying the Hadamard operator,

$$\widehat{H}=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right),$$
(2)
putting the system into the equal superposition of the two states: $`1/\sqrt{2}(|0+|1)`$. Now Alice can leave the “coin” alone or interchange the states $`|0`$ and $`|1`$, but if we suppose this is done without causing the system to decohere either action will leave the system unaltered, a fact that can be exploited by Bob. In his second move he applies the Hadamard operator again resulting in the pure state $`|0`$ thus winning the game. Bob utilized a superposition of states and the increased latitude allowed him by the possibility of quantum operators to make Alice’s strategy irrelevant, giving him a certainty of winning.

We shall see later that quantum enhancement often exploits entangled states, but in this case it is just the increased possibilities available to the quantum player that proved decisive. Du et al has also considered quantum strategies in a simplified card game that do not rely on entanglement du00b .

### III.2 A general prescription

Where a player has a choice of two moves they can be encoded by a single bit. To translate this into the quantum realm we replace the bit by a quantum bit or qubit that can be in a linear superposition of the two states. The basis states $`|0`$ and $`|1`$ correspond to the classical moves. The players’ qubits are initially prepared in some state to be specified later. We suppose that the players have a set of instruments that can manipulate their qubit to apply their strategy without causing decoherence of the quantum state. That is, a pure quantum strategy is a unitary operator acting on the player’s qubit. Unitary operations on the pair of qubits can be carried out either before the players’ moves, for example to entangle the qubits, or afterwards, for example, to disentangle them or to chose an appropriate basis for measurement. Finally, a measurement in the computational basis $`\{|0,|1\}`$ is made on the resulting state and the payoffs are determined in accordance with the payoff matrix. Knowing the final state prior to the measurement, the expectation values of the payoffs can be calculated. The identity operator $`\widehat{I}`$ corresponds to retaining the initial choice while

$$\widehat{F}i\widehat{\sigma }_x=\left(\begin{array}{cc}0& i\\ i& 0\end{array}\right)$$
(3)
corresponds to a bit flip. The resulting quantum game should contain the classical one as a subset.

We can extend the list of possible quantum actions to include any physically realizable action on a player’s qubit that is permitted by quantum mechanics. Some of the actions that have been considered include projective measurement and entanglement with ancillary bits or qubits.

A quantum game of the above form is easily realized as a quantum algorithm. Physical simulation of such an algorithm has already been performed for a quantum prisoners’ dilemma in a two qubit nuclear magnetic resonance computer du01a .

### III.3 Quantum $`2\times 2`$ games

In traditional $`2\times 2`$ games where each player has just a single move, creating a superposition by utilizing a quantum strategy will give the same results as a mixed classical strategy. In order to see non-classical results Eisert et al eisert99  produced entanglement between the players’ moves. Keeping in mind that the classical game is to be a subset of the quantum one, Eisert created the protocol in Fig. 1 for a quantum game between two players, Alice and Bob.

The final state can be computed by

$$|\psi _f=\widehat{J}^{}(\widehat{A}\widehat{B})\widehat{J}|\psi _i,$$
(4)
where $`|\psi _i=|00`$ represents the initial state of the qubits and $`|\psi _f`$ the final states, $`\widehat{J}`$ is an operator that entangles the players’ qubits, and $`\widehat{A}`$ and $`\widehat{B}`$ represent Alice’s and Bob’s move, respectively. A disentangling gate $`\widehat{J^{}}`$ is applied prior to taking a measurement on the final state and the payoff is subsequently computed from the classical payoff matrix. Since we require the classical game to be a subset of the quantum one, of necessity $`\widehat{J}`$ commutes with the direct product of any pair of classical moves. In the quantum game it is only the expectation value of the players’ payoffs that is important. For Alice (Bob) we can write

$$\$=P_{00}|\psi _f|00|^2+P_{01}|\psi _f|01|^2+P_{10}|\psi _f|10|^2+P_{11}|\psi _f|11|^2$$
(5)
where $`P_{ij}`$ is the payoff for Alice (Bob) associated with the game outcome $`ij,i,j\{0,1\}`$. If both players apply classical strategies the quantum game provides nothing new. However, if the players adopt quantum strategies the entanglement provides the opportunity for the players’ moves to interact in ways with no classical analogue.

A maximally entangling operator $`\widehat{J}`$, for an $`N\times 2`$ game, may be written, without loss of generality benjamin00b , as

$$\widehat{J}=\frac{1}{\sqrt{2}}(\widehat{I}^N+i\widehat{\sigma }_x^N).$$
(6)
An equivalent form of the entangling operator that permits the degree of entanglement to be controlled by a parameter $`\gamma [0,\pi /2]`$ is

$$\widehat{J}=\mathrm{exp}\left(i\frac{\gamma }{2}\widehat{\sigma }_x^N\right),$$
(7)
with maximal entanglement corresponding to $`\gamma =\pi /2`$.

The full range of pure quantum strategies are any $`\widehat{U}`$ SU(2). We may write

$$\widehat{U}(\theta ,\alpha ,\beta )=\left(\begin{array}{cc}e^{i\alpha }\mathrm{cos}(\theta /2)& ie^{i\beta }\mathrm{sin}(\theta /2)\\ ie^{i\beta }\mathrm{sin}(\theta /2)& e^{i\alpha }\mathrm{cos}(\theta /2)\end{array}\right),$$
(8)
where $`\theta [0,\pi ]`$ and $`\alpha ,\beta [\pi ,\pi ]`$. The strategies $`\stackrel{~}{U}(\theta )\widehat{U}(\theta ,0,0)`$ are equivalent to classical mixtures between the identity and bit flip operations. When Alice plays $`\stackrel{~}{U}(\theta _A)`$ and Bob plays $`\stackrel{~}{U}(\theta _B)`$ the payoffs are separable functions of $`\theta _A`$ and $`\theta _B`$ and we have nothing more than could be obtained from the classical game by employing mixed strategies.

In quantum prisoners’ dilemma a player with access to quantum strategies can always do at least as well as a classical player. If cooperation is associated with the $`|0`$ state and defection with the $`|1`$ state, then the strategy “always cooperate” is $`\widehat{C}\stackrel{~}{U}(0)=\widehat{I}`$ and the strategy “always defect” is $`\widehat{D}\stackrel{~}{U}(\pi )=\widehat{F}`$. Against a classical Alice playing $`\stackrel{~}{U}(\theta )`$, a quantum Bob can play Eisert’s “miracle” move 222There are some notational differences to Eisert et al’s original paper eisert99  in the form of $`\widehat{D}`$ that necessitates a corresponding change in $`\widehat{J}`$. This allows an easier generalization of the entanglement operator to multiplayer games. The only effect on the results is a possible rotation of $`|\psi _f`$ in the complex plane that is not physically observable.

$$\widehat{M}=\widehat{U}(\frac{\pi }{2},\frac{\pi }{2},0)=\frac{i}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$$
(9)
that yields a payoff of $`\$_B=3+2\mathrm{sin}\theta `$ for Bob while leaving Alice with only $`\$_A=1/2(1\mathrm{sin}\theta )`$. In this case the dilemma is removed in favor of the quantum player. In the partially entangled case, there is a critical value of the entanglement parameter $`\gamma =\mathrm{arcsin}(1/\sqrt{5})`$, below which the quantum player should revert to the classical dominant strategy $`\widehat{D}`$ to ensure a maximal payoff eisert99 . At the critical level of entanglement there is effectively a phase change between the quantum and classical domains of the game du01c ; du02 .

In a space of restricted quantum strategies, corresponding to setting $`\beta =0`$ in Eq. (8), Eisert demonstrated that there was a new NE that yielded a payoff of three to both players, the same as mutual cooperation. This NE has the property of being Pareto optimal. Unfortunately there is no a priori justification to restricting the space of quantum operators to those of with $`\beta =0`$.

With the full set of three parameter quantum strategies every strategy has a counter strategy that yields the opponent the maximum payoff of five, while the player is left with the minimum of zero benjamin00a . This result arises since for any $`\widehat{A}=\widehat{U}(\theta ,\alpha ,\beta )`$ there exists $`\widehat{B}=\widehat{U}(\theta ,\alpha ,\frac{\pi }{2}\beta )`$ such that

$$(\widehat{A}\widehat{I})\frac{1}{\sqrt{2}}(|00+i|11)=(\widehat{I}\widehat{B})\frac{1}{\sqrt{2}}(|00+i|11).$$
(10)
That is, on the maximally entangled state any unitary operation that Alice carries out on her qubit is equivalent to a unitary operation that Bob carries out on his. So for any strategy $`\widehat{U}(\theta ,\alpha ,\beta )`$ chosen by Alice, Bob has the counter $`\widehat{D}\widehat{U}(\theta ,\alpha ,\frac{\pi }{2}\beta )`$, essentially “undoing” Alice’s move and then defecting. Hence there is no equilibrium amongst pure quantum strategies.

We still have a (non-unique) NE amongst mixed quantum strategies eisert00 . A mixed quantum strategy is the combination of two or more pure quantum strategies using classical probabilities. This is in contrast to a superposition of pure quantum strategies which simply results in a different pure quantum strategy. The idea is that Alice’s strategy consists of choosing the pair of moves

$$\widehat{A}_1=\widehat{C}=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),\widehat{A}_2=\left(\begin{array}{cc}i& 0\\ 0& i\end{array}\right)$$
(11)
with equal probability, while Bob counters with the corresponding pair of optimal answers

$$\widehat{B}_1=\widehat{D}=\left(\begin{array}{cc}0& i\\ i& 0\end{array}\right),\widehat{B}_2=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$$
(12)
with equal probability. The combinations of strategies $`\{A_i,B_j\}`$ provide Bob with the maximum payoff of five and Alice with the minimum of zero when $`i=j`$, while the payoffs are reversed when $`ij`$. The expectation value of the payoffs for each player is then the average of $`P_{CD}`$ and $`P_{DC}`$, or 2.5. There is a continuous set of NE of this type, where Alice and Bob each play a pair of moves with equal probability, namely

$`\widehat{A}_1=\widehat{U}(\theta ,\alpha ,\beta )`$ , $`\widehat{A}_2=\widehat{U}(\theta ,{\displaystyle \frac{\pi }{2}}+\alpha ,{\displaystyle \frac{\pi }{2}}+\beta ),`$ (13)
$`\widehat{B}_1=\widehat{U}(\pi \theta ,{\displaystyle \frac{\pi }{2}}+\beta ,\alpha )`$ , $`\widehat{B}_2=\widehat{U}(\pi \theta ,\pi +\beta ,{\displaystyle \frac{\pi }{2}}+\alpha ).`$
If other values of the payoffs were chosen in Eq. (1), while still retaining the conditions for a classical prisoners’ dilemma333A prisoners’ dilemma is characterized by the payoffs for the row player being in the order $`P_{DC}>P_{CC}>P_{DD}>P_{CD}`$., the average quantum NE payoff may be below (as is the case here) or above that of mutual cooperation benjamin00a . In the latter case the conflict between the NE and the Pareto optimal outcome has disappeared, while in the former we have at least an improvement over the classical NE result of mutual defection.

In Ref. du01a  a quantum prisoners’ dilemma with Eisert et al’s scheme was achieved on a two qubit nuclear magnetic resonance computer, with various degrees of entanglement, from a separable (i.e., classical) game to a maximally entangled quantum game. Good agreement between theory and experiment was obtained.

The prescription provided by Eisert et al is a general one that can be applied to any $`2\times 2`$ game, with the generalization to $`2\times n`$ games being to use SU($`n`$) operators to represent the players’ actions.

This method of quantization is not unique. Another way of achieving similar results is simply to dispense with the entanglement operators and simply hypothesize various initial states, an approach first used by Marinatto and Weber marinatto00  and since used by other authors flitney02a ; iqbal01b . The essential difference to Eisert’s scheme is the absence of a disentangling operator. Different games are obtained by assuming different initial states. The classical game (with quantum operators representing mixed classical strategies) is obtained by selecting $`|\psi =|00`$, while an initial state that is maximally entangled gives rise to the maximum quantum effects. In references marinatto00 ; iqbal01b  the authors restrict the available strategies to probabilistic mixtures of the identity and bit flip operators forcing the players to play a mixed classical strategy. The absence of the $`\widehat{J}^{}`$ gate still leads to different results than playing the game entirely classically.

Iqbal has considered ESS in quantum versions of both the prisoners’ dilemma and the battle of the sexes iqbal01a  and concluded that entanglement can be made to produce or eliminate ESSs while retaining the same set of NE. A classical ESS can easily be invaded by a mutant strategy that employs quantum means and that can exploit entanglement. Without the entanglement, the quantum mutants have no advantage. In these models the replicator dynamic takes a “quantum” form iqbal01 .

### III.4 Larger strategic spaces

Since this initial work, the field of quantum games has been extended to multiplayer games and games with more than two pure classical strategies. As situations become more complicated there is more flexibility in the method of quantization.

Additional players are easily accommodated in the quantum game protocol of Fig. (1) by adding additional qubits to the initial state and additional player operators, as shown in Fig. (2). The entanglement operator of Eq. (6) creates a maximal entanglement between all the players’ qubits.

Benjamin and Hayden benjamin00b  have examined three and four player quantum games. These are strategically richer than the two player ones. For example, it is possible to construct a prisoners’ dilemma-like three handed game that has a NE in pure quantum strategies that is either better or worse than the classical one.

A game where entanglement can be exploited particularly effectively is the minority game. The players must select either zero or one. If they select the least popular choice they are rewarded. No reward is given if the numbers are balanced. Classically, the players can do no better than making a random selection and the situation is not improved in the three player quantum version. In the four player classical game half the time there is no minority, so each player wins on average only one time in eight. However, entanglement in the quantum version allows us to avoid this outcome and provides a NE which rewards each player with probability one quarter, twice the classical average benjamin00b .

Games with more than two classical pure strategies can be modeled in ways similar to the strategically smaller games by replacing the qubits representing the players’ decisions by, in general, an $`n`$-state quantum system (or qunit) for the $`n`$-choice case. The space of pure quantum strategies is expanded from SU(2) to SU($`n`$).

The game of rock-scissors-paper, where the players have three choices, has been examined by Iqbal and Toor iqbal01b . However, to make the game amenable to analysis, the authors do not allow the players the full range of unitary operations, but rather restrict the strategies to mixtures of $`\widehat{I}`$ and two operators that involve the interchange of a pair of states. Entanglement still provides for an enrichment over the classical game.

There are three quantum versions of the game show situation known as the Monty Hall problem li01 ; flitney02a ; dariano02  in which players have a three way choice. In the work by the present authors flitney02a  the game is modeled using suitable unitary operators, with the participants having access to the full set of SU(3) operations. In the quantum version either player can exploit the entanglement to their advantage if the other person employs only classical means but if the full set of SU(3) operators are available to both players we again have a situation where every strategy has a counter strategy. It is still possible to find a (non-unique) NE amongst mixed quantum strategies.

Li et al li01  permit one of the players to use an ancillary entangled particle and to take measurements on this as part of their strategy. Against a classical opponent, this turns what was a biased game into a fair one.

The final version dariano02  adopts a different protocol for constructing a quantum game. The author’s dispense with the idea of unitary operators acting on qutrits and instead have the participants directly selecting vectors in a three dimensional Hilbert space. In this variant a classical player can always be defeated by a quantum one.

Some of the mathematical methods of physics have attracted the attention of economists and a new branch of economic mathematics has appeared, econophysics. Recently, Polish theorists Piotrowski and Sładkowski have proposed a quantum-like approach to economics with its roots in quantum game theory piotr01a . Classical game theory is already extensively used by economists. In the new quantum market games, transactions are described in terms of projective operations acting on Hilbert spaces of strategies of traders. A quantum strategy represents a superposition of trading actions and can achieve outcomes not realizable by classical means piotr02 . Furthermore, quantum mechanics has features that can be used to model aspects of market behavior. For example, traders observe the actions of other players and adjust their actions accordingly, so there is non-commutativity of bidding piotr01b , maximal capital flow at a given price corresponds to entanglement between buyers and sellers piotr01a , and so on. There is speculation that markets cleared with quantum algorithms will have increased efficiency piotr01b  and avoiding dramatic market reversals.

### III.5 Quantum Parrondo’s games

Parrondo’s paradox, or Parrondo’s games arise when we have two games that are losing when played in isolation, but when played in combination form an overall winning game harmer99a ; mcclintock99 . This necessarily involves some form of coupling between the games, for example, through the player’s capital harmer99b  or via history dependent rules parrondo00 .

There has been recent attempts to create quantum versions of Parrondo’s games. In references ng01 ; flitney02b  the history dependent game of Parrondo et al parrondo00  has been translated directly into the quantum sphere by replacing the tossing of classical coins by SU(2) operations on qubits. There is coupling through the history dependent rules with additional effects arising from interference when a suitable superposition of states is chosen as the initial state. Meyer and Blumer meyer01  uses a quantum lattice gas automaton to construct a Parrondo game involving a single particle in an unbiased random walk between lattice sites. Ratcheting in one direction is achieved by multiplication by a position dependent phase factor and the resulting quantum interference. Lee and Johnson lee02  have examine the relationship between efficient quantum algorithms and Parrondo’s games. Here a random mixture of two algorithms produces a superior result than either one alone.

## IV Discussion and open questions

We have considered the basic protocol for simple quantum games and given examples of the various possibilities that have been discussed in the literature. In general the quantum representation of a classical game is not unique but all contain the classical game as a subset. The full set of quantum operations can be represented by trace-preserving, completely-positive maps. The possibilities where those operations are not directly unitary, such as the use of ancillas and the performance of measurements, remain little explored.

Quantization of a game can lead to either the appearance or disappearance of Nash equilibria. In general the much enhanced strategic space available to the players makes the quantum game more “efficient” than its classical counter part. For example, the gap between the Pareto optimal outcome and the NE in the prisoners’ dilemma is reduced or eliminated, and the average payoff in a multi-player minority game is increased, when players are permitted to use (mixed) quantum strategies. There are no equilibria in the space of pure quantum strategies in an entangled, fair, $`2\times 2`$ quantum game, a result that is easily extended to $`2\times n`$ games, but general results for multiplayer games or repeated games remain to be discovered.

Ng and Abbott ng01  have posed the as yet unanswered question: can coupling in a quantum Parrondo’s game be achieved through quantum entanglement alone? We have already mentioned how the selection of different initial superpositions can lead to different quantum games marinatto00 ; iqbal01b ; flitney02a . Is it possible to construct a quantum game where, by choosing a suitable superposition for the initial state, the resulting games can be individually losing but the superposition of the results produces a positive payoff? The coupling in this case would be through quantum interference, arranged to minimize the amplitudes of the losing final states and maximize those of the winning states.

The effect of a noisy input to a quantum game has been examined by Johnson johnson01 . In this example a suitable level of noise enhances the payoff. Decoherence can be simulated in a quantum game by applying a controlled not gate to the desired qubit, with the control bit being a random classical bit benjamin00b . The effect of noise and decoherence on a quantum game is another area that invites further examination.

## Acknowledgment

This work was supported by GTECH Corporation Australia with the assistance of the SA Lotteries Commission (Australia).


format: text

text:
# Violence in the Hearts of Galaxies - Aberration or Adolescence?

## 1 Introduction

Over the last 50 years, astronomers have been intrigued by enormously energetic objects called Active Galactic Nuclei (AGN), a violent phenomenon occurring in the nuclei, or central regions, of some galaxies with intensities and durations which cannot easily be explained by stars, thus providing some of the first circumstantial evidence for theoretically-predicted supermassive black holes. Despite their intriguing properties they were largely viewed as interesting but unimportant freaks in the broader study of galaxy formation and evolution, leading astronomers studying the properties of galaxies to exclude the small fraction of galaxies with active centres as irritating aberrations. Here I describe the discovery of AGN and the variety of classifications that followed; I describe some features of unifying models of the central engine that attempt to explain the varied properties of different AGN classes that give rise to the classification. The search for supermassive black holes in AGN and non-active galaxies is discussed along with the developing realisation that all galaxies with significant bulge components might harbour dormant supermassive black holes as remnants of a past adolescent period of quasar activity and therefore posses the potential to be re-triggered into activity under the right conditions, making nuclear activity an integral part of galaxy formation and evolution.

## 2 The Early Studies of Active Galactic Nuclei

The discovery of AGN began with the development of radio astronomy after World War II when hundreds of sources of radio waves on the sky were detected and catalogued (e.g. Third Cambridge Catalogue (3C) - Edge et al. 1959 and its revision (3CR) - Bennett 1961), but the nature of these strong radio emitters was unknown. Astronomers at Palomar attempted to optically identify some of the catalogued radio sources; Baum & Minkowski (1960) discovered optical emission from a faint galaxy at the position of the radio source 3C295 and, on studying the galaxy’s spectrum, or cosmic bar-code, measured its redshift and inferred a distance of 5000 million light years, making it the most distance object known at that time. Distances can be inferred from Hubble’s law whereby the more distant an object, the faster it appears to be receding from us, due to the expansion of the Universe. Chemical elements present in these objects emit or absorb radiation at known characteristic frequencies and when observed in a receding object, the observed frequency is reduced or redshifted due to the Doppler effect; the same physical process that causes a receding ambulance siren to be lowered in pitch after it passes the observer.

Attempts to find visible galaxies associated with other strong radio sources such as 3C48, 3C196 and 3C286 failed and only a faint blue, star-like object at the position of each radio source was found - thus leading to their name ‘quasi-stellar radio sources’, or ‘quasars’ for short. The spectrum of these quasars resembled nothing that had previously been seen for stars in our Galaxy and these blue points remained a mystery until Maarten Schmidt (1963) concentrated on 3C273, for which an accurate radio position was known (Hazard, Mackey & Shimmins 1963). The optical spectrum of the blue source associated with the radio emitter seemed unidentifiable until Schmidt realised that the spectrum could be clearly identified with spectral lines emitted from hydrogen, oxygen and magnesium atoms if a redshift corresponding to 16% of the speed of light was applied. The same technique was applied successfully to 3C48 (Greenstein & Matthews 1963) and demonstrated that these objects are not members of our own galaxy but lie at vast distances and are super-luminous. Indeed, the radiation emitted from a quasar (L $`>`$1013 L, where the Sun’s luminosity is L = 3.8 $`\times `$ 1026 Watt) is bright enough to outshine all the stars in its host galaxy. Such energies cannot be produced by stars alone and it was quickly realised that the release of gravitational potential energy from material falling towards, or being accreted by, a supermassive black hole at the galaxy centre, $``$100 times more energy efficient than nuclear fusion, was the only effective way to power such prodigious outputs (Lynden-Bell 1969).

A black hole is a region of space inside which the pull of gravity is so strong that nothing can escape, not even light. Two main kinds of black holes are thought to exist in the Universe. Stellar-mass black holes arise from the the collapsed innards of a massive star after its violent death when it blows off its outer layers in a spectacular supernova explosion; these black holes have mass slightly greater than the Sun but are compressed into a region only a few kilometres across. In contrast, supermassive black holes, which lurk at the centres of galaxies, are 10 million to 1000 million times more massive than the Sun and contained in a region about the size of the Solar System. The emission of radiation from a supermassive black hole appears at first to be contradictory; however, the energy generating processes take place outside the black hole’s point-of-no-return, or event horizon. The mechanism involved is the conversion of gravitational potential energy into heat and light by frictional forces within a disk of accreting material, which forms from infalling matter that still possesses some orbital energy, or angular momentum, and so cannot fall directly into the black hole.

Radiation from AGN is detected across the electromagnetic spectrum and today, nuclear activity in galaxies has been detected over a wide range of luminosities, from the most distant and energetic quasars, to the weaker AGN seen in nearby galaxies, such as Seyferts (Seyfert 1943), and even the nucleus of our own Milky Way.

## 3 AGN Orientation - Looking at it from All Angles

After the initial discovery of radio-loud AGN, the advent of radio interferometry soon led to detailed images of these strong radio emitters (e.g., Bridle & Perley 1984; Bridle et al. 1994) which revealed remarkable long thin jets of plasma emanating from a central compact nucleus and feeding extended lobes, often at considerable distances from the AGN, millions of light years in the most extreme cases. The radio emission is synchrotron radiation produced by electrons spiraling around magnetic fields in the ejected plasma; figure 1 shows a radio image of the classic radio galaxy Cygnus A in which the nucleus, jets and lobes are visible. These dramatic jets and clouds of radio-emitting plasma were interpreted as exhaust material from the powerful central engine (Scheuer 1974; Blandford & Rees 1974).

### 3.1 Too fast to believe - the remarkable jets in radio-loud AGN

The sharpest radio images, made repeatedly over many years using networks of radio telescopes spanning the globe, resulted in ‘movies’ of the motion of material in the jets. The blobs of plasma in these jets were apparently being ejected at many times the speed of light, c, appearing to violate fundamental laws of physics. It was quickly realised that such superluminal motion, was an optical illusion caused by the plasma moving at relativistic speeds, i.e. $`>`$ 0.7c, and being ejected towards us at an angle close to our line of sight (e.g., Blandford & Rees 1978). Relativistic motion appears to be present for jet matter over hundreds of thousands of light years and the detailed physical driving mechanisms remain an area of active study. The relativistic motion of jet matter has an enormous impact on the appearance of these objects and is possibly the single-most important contributor to the variety of observed morphological types.

The fast motion of jet material also causes extreme apparent brightening, or Doppler boosting, of the radiation and greatly amplifies any flickering, or variability, in the light levels. Today, the wide range of observed radio structures, brightnesses and levels of variability can be understood in terms of the angle at which we view the high-speed plasma jet. Radio galaxies like Cygnus A are orientated perpendicular to our line of sight, lying in the plane of the sky, appear rather symmetrical, and as expected, show no variability or superluminal motion. At the other extreme are bright, compact and highly variable BL Lac objects, which are being observed head-on. Figure 2 shows a sketch of this model in which a jet of plasma is ejected from either side of the central engine at relativistic speeds; object classification depends on the angle of the jet to our line of sight. Objects viewed at intermediate angles are seen as either extended, ‘lobe-dominated’ quasars or relatively compact, ‘core-dominated’ quasars (see also Urry & Padovani 1995).

### 3.2 Obscuring-Doughnuts in Radio-Quiet AGN

Radio-quiet quasars and Seyferts are known to be $``$10 times more common, but 100 to 1000 times weaker at radio wavelengths and significantly less extended than their radio-loud cousins (Goldschmidt et al. 1999), but orientation still has important effects, this time on the optical properties. Optical spectroscopy provides a powerful diagnostic tool for the physical conditions in astronomical objects; as described earlier chemical elements have a characteristic spectral signature and physical conditions within a gas can be inferred from distortions of this chemical bar-code. In particular, broadening of the spectral lines indicates a spread in gas-cloud velocities, whilst the relative brightnesses of spectral lines indicate the intensity of ultraviolet radiation incident upon the gas.

Measurements of the optical spectra of Seyfert nuclei show spectral lines from gas ionised (i.e. gas in which atoms have been stripped of one or more electrons) by strong ultraviolet radiation that is too intense to be produced by a collection of stars and is instead thought to originate from the accretion disk. All Seyfert nuclei contain a region of ionised gas, the Narrow Line Region (NLR), extending over several hundred light years where the spectral line-widths correspond to gas velocties of a few hundred km s-1 and densities are moderate (electrons per unit volume $`n_e`$$``$103$``$106 cm-3). Closer in, within $``$0.1 light year of the black hole, is the Broad-Line Region (BLR), a much denser region of gas ($`n_e`$$``$109 cm-3) that shows gas velocities up to 10,000 km s-1. Seyferts were originally classified into two types; type-1 Seyferts that show evidence for both a BLR and an NLR, and type-2 Seyferts that show only an NLR (Khachikian & Weedman 1971, 1974).

The mystery of the missing BLRs in type-2 Seyferts was solved elegantly in 1985 when Antonucci & Miller discovered a hidden BLR in the scattered light spectrum of the archetypal Seyfert 2 galaxy NGC 1068, which closely resembled that of a Seyfert type 1. This discovery led to the idea that the BLR exists in all Seyferts and is located inside a doughnut, or torus, of molecular gas and dust; our viewing angle with respect to the torus then explains the observed differences between the unobscured, broad-line Seyfert 1s, viewed pole-on, and the obscured, narrow-line Seyfert 2s, viewed edge-on. Hidden Seyfert 1 nuclei can then be seen in reflected light as light photons are scattered into the line of sight by particles above and below the torus acting like a “dentist’s mirror” (Antonucci & Miller, 1985; Tran 1995; Antonucci 1993; Wills 1999). The lower panel of Figure 2 shows a sketch of a Seyfert nucleus with the different types of AGN observed as angle between line of sight and torus axis increases. Figure 3 shows an image of the molecular torus in NGC 4151, surrounding the mini, quasar-like radio jet emanating from the centre of the galaxy, as predicted by the unification scheme.

Radio quiet quasars also have broad and narrow lines and are considered to be the high luminosity equivalents of Seyfert type 1 galaxies. A population of narrow-line quasars, high luminosity equivalents to obscured Seyfert 2s, are predicted by the unification scheme but, until now, have remained elusive. New optical and infrared sky surveys are beginning to reveal a previously undetected population of red AGN (Cutri et al. 2001) with quasar type 2 spectra (Djorgovski et al. 1999) and weak radio emission (Ulvestad et al. 2000). A significant population of highly obscured but intrinsically luminous AGN would alter measures of AGN evolution, the ionisation state of the Universe and might contribute substantially to the diffuse infrared and X-ray backgrounds.

### 3.3 Further unification?

The presence of gas emitting broad and narrow optical lines in radio-loud AGN and the discorvery of mini radio jets in Seyferts (e.g. Wilson & Ulvestad 1982) led to further consistency between the two unification schemes. Nevertheless, the complete unification of radio-loud and radio-quiet objects remains problematic, particularly in explaining the vast range in radio power and jet extents, and might ultimately involve the combination of black hole properties, such as accretion rate, black hole mass and spin, and orientation (Wilson & Colbert, 1995; Boroson 2002).

## 4 Searching for Supermassive Black Holes

Although incontrovertible observational proof of the existence of supermassive black holes (SMBHs) has yet not been found, evidence is mounting to suggest the presence of massive dark objects, or large mass concentrations at the centres of galaxies. Black holes, by definition, cannot be ‘seen’ and instead one must look for the consequences of their presence. The presence of SMBHs has been inferred indirectly from the energetics of accretion required to power luminous AGN and explain rapid flux variability and, more directly, from kinematic studies of the influence of the black hole’s gravitational pull on stars and gas orbiting close to it in the central regions of both active and non-active galaxies. Theoretical models rule out alternatives to a supermassive black holes such as collections of brown or white dwarf stars, neutron stars or stellar-mass black holes which would merge and shine or evaporate too quickly (Maoz 1995, 1998; Genzel et al. 1997, 2000).

### 4.1 Quasar lifetimes and the black hole legacy

Soon after the discovery of quasars it became clear that they were most common when the Universe was relatively young with the peak of the quasar epoch at redshift z$``$2.5 or a look-back time of 65% of the age of the Universe (See Figure 4); today bright quasars are rare and weaker Seyferts dominate instead. The number of dead quasars or relic, dormant black holes left today can estimated by applying some simple arguments to the quasar observations. Soltan (1982) integrated the observed light emitted by quasars, and, assuming the power source for quasar light is accretion of material by a supermassive black hole with a mass-to-energy conversion efficiency of 10% and that the black hole grows during the active phase, predicted the total mass in relic black holes today. Knowing the number of galaxies per unit volume of space (e.g. Loveday et al. 1992), if one assumes that all galaxies went through a quasar phase at some time in their lives, then each galaxy should, on average, contain a $``$108 M black hole as a legacy of this violent, but short-lived period ($``$107 to $``$108 years). Alternatively, if only a small fraction of galaxies went through a quasar phase, the active phase would have lasted lasted longer ($`>`$109 years) and the remnant SMBHs would be relatively rare, but unacceptably massive ($`>`$109 M) (e.g. Cavaliere et al., 1983; Cavaliere & Szalay 1986, Cavaliere & Padovani 1988).

More complex models including quasar evolution (e.g. Tremaine 1996; Faber et al. 1997) and the effects of galaxy growth (e.g. Haehnelt & Rees 1993) favour short-lived periods of activity in many generations of quasars, or a mixture of continuous and recurrent activity (Small & Blandford 1992; Cen 2000; Choi, Yang & Yi 2001). The complex physics of accretion and black hole growth, however, remain an area of active study (e.g. Blandford & Begelman 1999; Fabian 1999). Nevertheless, the range of black hole mass of interest is thought to be M $``$106 to 109.5M, with the lower mass holes being ubiquitous (Kormendy & Gebhardt 2001).

### 4.2 Irresistible black holes - dynamics of gas and stars

Although the prodigious energy outputs from powerful quasars offer strong circumstantial evidence that supermassive black holes exist, most notably in driving the ejection and acceleration of long, powerful jets of plasma close to the speed of light (Rees et al. 1982), it has not, until recently, been possible to make more direct kinematic measurements of the black hole’s gravitational influence. The mass of a central object, the circular velocity of an orbiting star and the radius of the orbit are related by Newton’s Laws of motion and gravity. Precise measurements of the velocities of stars and gas close to the centre of a galaxy are then used to determine the mass of the central object.

The strongest dynamical evidence for black holes comes from studies of centre of our own Galaxy and a nearby Seyfert, NGC 4258; a decade of painstaking observations of a cluster of stars orbiting around the mildly active centre of the Milky Way, within a radius of 0.07 light years of the central radio source Sgr A\*, suggest a central mass of M=(2.6$`\pm `$0.2)$`\times `$106 M (Eckart & Genzel 1997; Genzel 1997, 2000; Ghez 2000). Discovery of strong radio spectral lines, or megamasers, emitted from water molecules in a rapidly rotating nuclear gas disc at the centre of NGC 4258 implies a centre mass M=(4$`\pm `$0.1)$`\times `$107 M concentrated in a region smaller than 0.7 light years (Miyoshi et al. 1995), again small enough to rule out anything other than a black hole (Maoz 1995, 1998). Precision measurements of black hole masses in other galaxies using a variety of techniques, although challenging and still model dependent, have become increasingly common (e.g. Maggorian et al. 1998; Bower et al. 1998; Gebhardt et al. 2000) and now more than 60 active and non-active galaxies have black hole estimates.

## 5 Black Hole Demographics - the Host Galaxy Connection

In general, galaxies consist of two main visible components - a central ellipsoidal bulge and a flat disc structure commonly containing spiral arms - together making a structure resembling two fried eggs back-to-back. Elliptical galaxies have no discs and are dominated by their bulges, maintaining their shapes by the random motions of their stars; spiral galaxies, like our own Galaxy and nearby Andromeda have prominent discs and are supported mainly by rotation, with rotation speeds between 200 km s-1 and 300 km s-1. Some spiral galaxies contain a bar-like structure that crosses the nucleus; the spiral arms then begin at the ends of the bar and wind outwards. If the bar is narrow and straight it is classed as a ‘strong’ bar and if oval-shaped (essentially an elongated bulge) it is ‘weak’. Dynamical simulations have revealed that in the region of the bar, stars do not travel on circular orbits as they do in the disk, but instead follow more elongated elliptical, or ‘non-circular’ paths.

With the great progress made recently in measuring the mass of central supermassive black holes in a significant number of active and non-active galaxies, correlations with their host galaxy properties are now possible. Maggorian et al. (1998) confirmed the correlation between the brightness of a galaxy bulge (and hence stellar mass) and the mass of its central black hole (e.g. Kormendy & Richstone 1995) establishing a best fit to the linear relation of M=0.006Mbulge, despite a large scatter. A much tighter correlation was subsequently discovered between the velocity dispersion ($`\sigma `$) of stars in the host galaxy bulge and the central black hole mass (e.g. Gebhardt et al 2000; Ferrarese & Merrit 2000). The velocity dispersion is a measure of the range of random speeds present in star motions and is potentially a more reliable galaxy mass indicator than total starlight; the greater the spread in speeds, the more massive the galaxy bulge. The tightness of the correlation points to a connection between the formation mechanism of the galaxy bulge and central black hole although the physics involved are not yet known. The M$``$$`\sigma `$ relation for a mixture of nearby active and non-active galaxies (Figure 5), measured using a variety of techniques, shows the relationship between bulge and black hole is very similar for both, although investigations continue to establish the precise form of the correlation and whether it is universal for active and non-active galaxies. If universal, this relationship would provide exciting confirmation that non-active galaxies contain dormant versions of the same kind of black holes that power AGN.

No correlation exists between galaxy disc properties and black hole mass, and disc galaxies without bulges do not appear to contain supermassive black holes (e.g. Gebhardt et al. 2001), suggesting discs form later and are not involved in the process that intimately links the black hole and bulge.

## 6 AGN and their Environment

### 6.1 The violent early Universe

The relationships between black holes and their host galaxies are increasingly compelling but unanswered questions remain concerning the relationship between star formation, galaxy formation, quasar activity and black hole creation in the early Universe. Observations of faint galaxies in the Hubble Deep Field suggested a peak in star formation history that matches that of the quasar epoch (e.g. Madau et al. 1996) implying a close link between star formation and quasar activity. More recent measurements, however, suggest that the star formation activity may be constant for redshifts greater than 1 with the onset of substantial star formation occurring at even earlier epochs, at redshifts beyond 4.5 (Steidel et al. 1999). An increasing number of new quasars are also being found at redshifts greater than 4 (Fan et al. 2001; Schneider et al. 2002) providing constraints for cosmological models of galaxy formation and continuing the debate on the relationship between quasar activity, star formation and the creation of the first black holes (e.g. Haiman & Loeb 2001).

The life cycle of an AGN involves a mechanism to trigger the infall of gas to create an accretion disc and continued fuelling, or replenishment, of this brightly-shining accretion disc. A number of models have suggested that at intermediate to high redshifts it may be moderately easy to trigger and fuel AGN, where galaxies might be more gas rich, star formation is vigorous and collisions between galaxies are common (Haehnelt & Rees 1993). Kauffman & Haehnelt (2000) suggest a model in which galaxy and quasar evolution at early times was driven by mergers of gas-rich disc galaxies, which drove the formation and fuelling of black holes and created today’s elliptical galaxies, thereby tying together host galaxy and black hole properties. As the Universe ages, a decreasing galaxy merger rate and available gas supply and increasing accretion timescales produce the decline in bright quasars.

An alternative hypothesis, linking black hole and bulge growth with quasar activity, involves strong bars in early galaxies (Sellwood 1999); early disc galaxies developed strong bars which were highly efficient at removing angular momentum from disc gas and funnelling it towards the centre to feed and grow a black hole. This represents the bright quasar phase in which the black hole grows rapidly, but on reaching only a few percent of the mass of the host disc, the central mass concentration soon destroys the bar due to an increasing number of stars that follow random and chaotic paths, thereby choking off the fuel supply and quenching the quasar. In addition, the increase in random motion in the disc leads to the creation of a bulge. A disc might be re-built some time later if the galaxy receives a new supply of cold gas, perhaps from a ‘minor merger’ whereby a small gaseous galaxy or gas-cloud falls into the main disc and is consumed by the disc without causing significant disruption, and without significantly affecting the black hole mass. This scenario nicely accounts for the relationship between black hole masses and bulge properties and lack of correlation with disc properties.

An important unknown parameter in these models is the amount of cold gas in progenitor disc galaxies and how it evolves with time; it is expected that the Universe was more gas-rich in the past (Barger et al. 2001), but observations of neutral hydrogen (Hi) and molecular gas such as carbon monoxide (CO) with new generation facilities, such as Atacama Large Millimeter Array (ALMA), the Giant Metrewave Radio Telescope (GMRT), the Extended Very Large Array (EVLA) and the proposed Square Kilometre Array (SKA), will offer exciting opportunities to measure the gaseous properties of distant galaxies directly to further our understanding of galaxy formation and evolution and its relationship to quasar and star-formation activity.

### 6.2 Re-activating dormant black holes in nearby galaxies

While the most luminous AGN might coincide with violent dynamics in the gas-rich universe at the epoch of galaxy formation (Haehnelt & Rees 1993), nuclear activity in nearby galaxies is more problematic since major galaxy mergers, the collision of two equal-mass disc galaxies, are less common and galaxy discs are well established; reactivation of ubiquitous ‘old’ black holes is therefore likely to dominate. Host-galaxy gas represents a reservoir of potential fuel and, given the ubiquity of supermassive black holes, the degree of nuclear activity exhibited by a galaxy must be related to the nature of the fuelling rather than the presence of a black hole (e.g., Shlosman & Noguchi 1993; Sellwood & Moore 1999). Gravitational, or tidal forces exterted when two galaxies pass close to one another may play a role in this process, either directly, when gas from the companion, or outer regions of the host galaxy, is tidally removed and deposited onto the nucleus, or by causing disturbances to stars orbiting in the disc and leading to the growth of structures such as bars, in which stars travel on elliptical paths and drive inflows of galactic gas (e.g. Toomre & Toomre 1972; Simkin, Su & Schwarz 1980; Shlosman, Frank & Begelman 1989; Mundell et al. 1995; Athanassoula 1992; Mundell & Shone 1999).

Numerous optical and IR surveys of Seyfert hosts have been conducted but as yet show no conclusive links between nuclear activity and host galaxy environment. Neutral hydrogen (Hi) is an important tracer of galactic structure and dynamics and may be a better probe of environment than the stellar component. Hi is often the most spatially extended component of a galaxy’s disc so is easily disrupted by passing companions, making it a sensitive tracer of tidal disruption (e.g. Mundell et al., 1995). In addition, because gas can dissipate energy and momentum through shock waves (Mundell & Shone, 1999), whereas collisions between stars are rare, the observable consequences of perturbating the Hi in galactic bars are easily detectable. However, despite the diagnostic power of Hi, until recently few detailed studies of Hi in Seyferts have been performed (Brinks & Mundell 1996; Mundell 1999).

The strength of a galaxy collision, which depends on initial galaxy properties such as mass, concentration, distance and direction of closest approach, ranges from the most violent mergers between equal mass, gas-rich disc galaxies, to the weakest interaction in which a low mass companion, perhaps on a fly-by path, interacts with a massive primary. In this minor-merger case the primary disc is perturbed but not significantly disrupted or destroyed. Indeed, Seyfert nuclei are rare in strongly interacting systems, late-type spirals and elliptical galaxies (Keel et al. 1995; Bushouse 1996) and sometimes show surprisingly undisturbed galactic discs despite the presence of Hi tidal features (Mundell et al. 1995). Seyfert activity may therefore involve weaker interactions or minor mergers between a primary galaxy and a smaller companion or satellite galaxy, rather than violent major mergers (e.g. De Robertis, Yee & Hayhoe 1998). A key question is whether the gaseous properties of normal galaxies differ from those with Seyfert nuclei and a deep, systematic Hi imaging survey of a sample of Seyfert and normal galaxies is now required.

## 7 Unanswered Questions and Prospects for the Future

Studies of galaxies and AGN are being revolutionised by impressive new sky surveys, such as SLOAN and 2DF, which have already significantly increased the number of known galaxies and quasars in the Universe. In the next decade and beyond, prospects for understanding AGN and their role in galaxy formation and evolution are extremely promising given the number of planned new instruments spanning the electromagnetic spectrum.

$``$We do not yet know whether galaxies grow black holes or are seeded by them; NGST (Next Generation Space Telescope) will find the smallest black holes at the earliest times and allow us to relate them to the first galaxies and stars.

$``$ The amount of cold gas in galaxies through cosmic history is a key ingredient in star-formation, quasar activity and galaxy evolution models but is still unknown. The study of gas at high redshifts with ALMA, the GMRT and the EVLA will revolutionise our understanding its role in these important phenomena and provide powerful constraints for cosmological models.

$``$Current models of AGN physics - fuelling, accretion discs and the acceleration of powerful radio jets - remain speculative; detailed studies of X-ray emitting gas, e.g with the highly ambitious X-ray space interferometer MAXIM, might offer valuable new insight into the energetics and physical structure of this extreme region.

$``$Finally, the detection and detailed study of gravitational waves, using the space-based detector LISA, from massive black holes living in black-hole binary systems or in the very act of merging will prove the existence of SMBHs and perhaps provide insight into the origin of the difference between radio-loud and radio-quiet AGN.