text:
# Untitled Document

to appear in the AMS Contemporary Mathematics volume: 5 April 2000 Quantum Computation and Quantum Information Science quant-ph/0004092

QUANTUM GAMES AND

QUANTUM ALGORITHMS

David A. Meyer

Project in Geometry and Physics

Department of Mathematics

University of California/San Diego

La Jolla, CA 92093-0112

dmeyer@chonji.ucsd.edu

and Institute for Physical Sciences

Los Alamos, NM

ABSTRACT

A quantum algorithm for an oracle problem can be understood as a quantum strategy for a player in a two-player zero-sum game in which the other player is constrained to play classically. I formalize this correspondence and give examples of games (and hence oracle problems) for which the quantum player can do better than would be possible classically. The most remarkable example is the Bernstein-Vazirani quantum search algorithm which I show creates no entanglement at any timestep.

1999 Physics and Astronomy Classification Scheme: 03.67.Lx, 02.50.Le.

2000 American Mathematical Society Subject Classification: 81P68, 68Q15, 91A05.

Key Words: quantum strategy, quantum algorithm, query complexity, entanglement.

Expanded version of an invited talk presented at the Special Session on Quantum Computation and Information at the Joint Mathematics Meetings, Washington, DC, 19–22 January 2000.

1. Introduction

Despite the exuberance of people working on quantum computation—and more generally, quantum information theory—we discuss remarkably few quantum algorithms. These include, and are largely limited to, the Deutsch-Jozsa , Simon , Shor  and Grover  algorithms. Of course, quantum versions of many other information processing tasks have also been studied: cryptography , error correction , communication channels , distributed computation , etc. When I was invited to speak about quantum computing at Microsoft Research in January 1998, I decided to try to add game theory to this list.

My motivations were twofold: First, as I explained in that talk, von Neumann was not only the driving force behind the development of modern digital computers —a subject of great interest to Microsoft—but also one of the founders of quantum mechanics , and thus someone whose ideas are central to quantum computing. But he had another great interest—shared with Microsoft—economics! Von Neumann essentially invented game theory ; his book with Morgenstern, Theory of Games and Economic Behavior  raises (and in some cases, answers) many of the questions which preoccupy game theorists and economists today. Second, I hoped that something like the argument that identifies which two-person zero-sum games have optimal mixed, rather than pure, classical strategies might provide some insight into which problems are solvable more efficiently by quantum rather than classical algorithms. This hope was probably somewhat naïve, but it brings us to the first question I’ll address in this talk: What do quantum games have to do with quantum algorithms?

The quantum game I described originally , PQ PENNY FLIP, is perhaps too simple to make the connection with quantum algorithms completely clear. In fact, it is so simple, involving only one qubit, that several people have pointed out that it could be simulated classically . I have argued elsewhere that this misses the point slightly, that the issue is not whether there exists a classical simulation, but how the complexity of that simulation would scale if the size of the game were to increase . To illustrate this point explicitly, in this talk I’ll tell a story which involves a game which has instances of arbitrarily large size. My discussion of this game naturally includes a description of Grover’s algorithm , which not only helps to answer the first question, but raises a second and third.

The second is: Are there sophisticated quantum search algorithms? More explicitly, are there ‘databases’ which can be ‘searched’ with better than the square root speedup that Grover’s algorithm provides over the best possible classical algorithm?  Since Bennett, Bernstein, Brassard & Vazirani , Boyer, Brassard, Høyer and Tapp , and Zalka  have shown that Grover’s algorithm is optimal, I will explain the natural changes in the problem which make this question interesting.

Recently Lloyd has argued that Grover’s algorithm can be implemented without entanglement . At first glance this may appear surprising: many people have stated that the power of quantum computing derives from entanglement . This belief underlies the criticism that NMR experiments do not realize quantum computation because the state of the system at each timestep is separable , i.e., a convex combination of unentangled pure states . Similarly, van Enk observed that the one qubit PQ PENNY FLIP game not only can be simulated classically, but involves no entanglement , which would suggest by the same ‘reasoning’ that such a quantum game would be unrelated to quantum algorithms. In fact, the quantum game in the story to come provides an answer to the third question I’ll address: Can quantum-over-classical improvements be achieved without entanglement?

2. PQ games

I’ll begin by reviewing briefly the one qubit game PQ PENNY FLIP . In our first episode, the starship Enterprise is facing some imminent catastrophe when the superpowerful being Q appears on the bridge and offers to rescue the ship if Captain Picard

Captain Picard and Q are characters in the popular American television (and movie) series Star Trek: The Next Generation whose initials and abilities are ideal for this illustration. See . can beat him at a simple game: Q produces a penny and asks Picard to place it in a small box, head up. Then Q, followed by Picard, followed by Q, reaches into the box, without looking at the penny, and either flips it over or leaves it as it is. After Q’s second turn they open the box and Q wins if the penny is head up. Q wins every time they play, using the following quantum strategy:

$$\begin{array}{cc}\hfill |0& \underset{\text{ }H\text{ }}{\overset{\mathrm{Q}}{}}\frac{1}{\sqrt{2}}(|0+|1)\hfill \\ & \underset{\sigma _x\mathrm{or}I_2}{\overset{\mathrm{Picard}}{}}\frac{1}{\sqrt{2}}(|0+|1)\hfill \\ & \underset{\text{ }H\text{ }}{\overset{\mathrm{Q}}{}}|0\hfill \end{array}$$

Here $`|`$ is Dirac notation  for an element of Hilbert space, 0 denotes ‘head’ and 1 denotes ‘tail’, $`H=\frac{1}{\sqrt{2}}\left(\genfrac{}{}{0pt}{}{1}{1}\genfrac{}{}{0pt}{}{1}{1}\right)`$ is the Hadamard transformation, and $`\sigma _x=\left(\genfrac{}{}{0pt}{}{0}{1}\genfrac{}{}{0pt}{}{1}{0}\right)`$ implements Picard’s possible action of flipping the penny over. Q’s quantum strategy of putting the penny into the equal superposition of ‘head’ and ‘tail’ on his first turn means that whether Picard flips the penny over or not, it remains in an equal superposition which Q can rotate back to ‘head’ by applying $`H`$ again since $`H=H^1`$. So when they open the box, Q always wins.

Notice that if Q were restricted to playing classically, i.e., to implementing only $`\sigma _x`$ or $`I_2`$ on his turns, an optimal strategy for both players would be to flip the penny over or not with equal probability on each turn. In this case Q would win only half the time, so he does substantially better by playing quantum mechanically.

The structure of PQ PENNY FLIP motivates the following definition which formalizes one meaning for quantum game.

Eisert, Wilkens & Lewenstein have proposed a different formalism for quantum games and have applied it to find a (unique) Pareto optimal equilibrium for the Prisoners’ Dilemma when the players are allowed to select moves from the same specific subset of unitary transformations . Benjamin & Hayden recently showed that this is not a solution when the players are allowed to make arbitrary unitary moves ; in fact, in this case there is no equilibrium, just as in PQ PENNY FLIP . Nevertheless, that formalism still seems likely to be interesting, although more closely related to quantum communication protocols  than to quantum algorithms.

Definitions. A PQ game consists of

(i) a Hilbert space $``$—the possible states of the game—with $`N=\mathrm{dim}`$,

(ii) an initial state $`\psi _0`$,

(iii) subsets $`Q_iU(N)`$, $`i\{1,\mathrm{},k+1\}`$—the elements of $`Q_i`$ are the moves Q chooses among on turn $`i`$,

(iv) subsets $`P_iS_N`$, $`i\{1,\mathrm{},k\}`$, where $`S_N`$ is the permutation group on $`N`$ elements—the elements of $`P_i`$ are the moves Picard chooses among on turn $`i`$, and

(v) a projection operator $`\mathrm{\Pi }`$ on $``$—the subspace $`W_\mathrm{Q}`$ fixed by $`\mathrm{\Pi }`$ consists of the winning states for Q.

Since only Picard and Q play, these are two-player games; they are zero-sum since when Q wins, Picard loses, and vice versa.

A pure quantum strategy for Q is a sequence $`u_iQ_i`$. A pure (classical) strategy for Picard is a sequence $`s_iP_i`$, while a mixed (classical) strategy for Picard is a sequence of probability distributions $`f_i:P_i[0,1]`$. If both Q and Picard play pure strategies, the corresponding evolution of the PQ game is described by

$$\psi _f=u_{k+1}s_ku_k\mathrm{}u_2s_1u_1\psi _0.$$

After Q’s last move the state of the game is measured with $`\mathrm{\Pi }`$. According to the rules of quantum mechanics , the players observe the eigenvalue 1 with probability $`\mathrm{Tr}(\psi ^{}\mathrm{\Pi }\psi )`$; this is the probability that the state is projected into $`W_\mathrm{Q}`$ and Q wins. More generally, if Picard plays a mixed strategy, the corresponding evolution of the PQ game is described by

$$\rho _f^{}=u_{k+1}^{}\left(\underset{s_kP_k}{}f_k^{}(s_k^{})s_k^{}u_k^{}\mathrm{}u_2^{}\left(\underset{s_1P_1}{}f_1^{}(s_1^{})s_1^{}u_1^{}\rho _0^{}u_1^{}s_1^{}\right)u_2^{}\mathrm{}u_k^{}s_k^{}\right)u_{k+1}^{},$$

where $`\rho _0^{}=\psi _0^{}\psi _0^{}`$. Again, after Q’s last move $`\rho _f`$ is measured with $`\mathrm{\Pi }`$; the probability that $`\rho _f`$ is projected into $`W_\mathrm{Q}^{}W_\mathrm{Q}^{}`$) and Q wins is $`\mathrm{Tr}(\mathrm{\Pi }\rho _f)`$.

Finally, an equilibrium is a pair of strategies, one for Picard and one for Q, such that neither player can improve his probability of winning by changing his strategy while the other does not.

As I’ll show in the next section, the structure of a PQ game specializes to the structure of the known quantum algorithms. In general, unlike the simple case of PQ PENNY FLIP, $`W_\mathrm{Q}=W_\mathrm{Q}(\{s_i\})`$ or $`W_\mathrm{Q}=W_\mathrm{Q}(\{f_i\})`$, i.e., the conditions for Q’s win can depend on Picard’s strategy. Each of the three example games I consider here suffices to prove that there are games with mixed/quantum equilibria at which Q does better than he would at any mixed/mixed equilibrium; equivalently, there are some quantum algorithms which outperform classical ones.

3. Guessing a number

In our second episode, Q returns to the Enterprise and challenges Captain Picard again. He boasts that if Picard picks any number between 0 and $`N1`$, inclusive, he can guess it. Now, Picard is no slouch; he has been studying up on quantum algorithms since the last episode. In particular, he has studied Grover’s algorithm  and realizes that for $`N=2^n`$, Q can determine the number he picks with high probability by playing the following strategy:

$$\begin{array}{ccc}\hfill |0\mathrm{}0,0& \underset{\text{ }H^nH\sigma _x\text{ }}{\overset{\mathrm{Q}}{}}\frac{1}{\sqrt{N}}\underset{x=0}{\overset{N1}{}}|x\frac{1}{\sqrt{2}}(|0|1)\hfill & (u_1)\hfill \\ & \underset{\text{ }s\left(f_a\right)\text{ }}{\overset{\mathrm{Picard}}{}}\frac{1}{\sqrt{N}}\underset{x=0}{\overset{N1}{}}(1)^{\delta _{xa}}|x\frac{1}{\sqrt{2}}(|0|1)\hfill & (s_1)\hfill \\ & \underset{H^nI_2s(f_0)H^nI_2}{\overset{\mathrm{Q}}{}}\mathrm{},\hfill & (u_2)\hfill \end{array}$$

where $`a[0,N1]`$ is Picard’s chosen number, and the moves $`s_1`$ and $`u_2`$ are repeated a total of $`k=\frac{\pi }{4}\sqrt{N}`$ times, i.e., $`s_k=\mathrm{}=s_1`$ and $`u_{k+1}=\mathrm{}=u_2`$. For $`f:\text{}_2^n\text{}_2`$, $`s(f)`$ is the permutation (and hence unitary transformation) defined by

$$s(f)|x,b=|x,bf(x),$$

where $``$ denotes addition mod 2. This transformation is often referred to as ‘$`f`$-controlled-NOT’. Each of Picard’s moves $`s_i`$ can be thought of as the response of an oracle which computes $`f_a(x):=\delta _{xa}`$ to respond to the quantum query defined by the state after $`u_i`$. After $`O(\sqrt{N})`$ such queries, a measurement by $`\mathrm{\Pi }=|aa|I_2`$ returns a win for Q with probability bounded above $`\frac{1}{2}`$, i.e., Grover’s quantum algorithm determines $`a`$ with high probability. (Here $`a|:=|a^{}`$ and the tensor product is implicit in $`|aa|`$ .)

Notice that if Q were to play classically, he could query Picard about a specific number at each turn, but on the average it would take $`N/2`$ turns to guess $`a`$. A classical equilibrium is for Picard to choose $`a`$ uniformly at random, and for Q to choose a permutation of $`N`$ uniformly at random and guess numbers in the corresponding order. Even when Picard plays such a mixed strategy, Q’s quantum strategy is optimal; together they define a mixed/quantum equilibrium.

Knowing all this, Picard responds that he will be happy to play, but that Q should only get 1 guess, not $`\frac{\pi }{4}\sqrt{N}`$. Q protests that this is hardly fair, but he will play, as long as Picard tells him how close his guess is to the chosen number. Picard agrees, and they play. Q wins. They play again. Q wins again. Picard doesn’t understand what’s going on. The problem is that in his studies of quantum algorithms, he overlooked an insufficiently appreciated quantum algorithm, the slightly improved  Bernstein-Vazirani algorithm : Guess $`x`$ and answer $`a`$ are vectors in $`\text{}_2^n`$, so $`xa`$ depends on the cosine of the angle between the vectors. Thus it seems reasonable to define “how close a guess is to the answer” to be the oracle response $`g_a(x):=xa`$. Then Q plays as follows:

$$\begin{array}{ccc}\hfill |0\mathrm{}0,0& \underset{H^nH\sigma _x}{\overset{\mathrm{Q}}{}}\frac{1}{\sqrt{N}}\underset{x=0}{\overset{N1}{}}|x\frac{1}{\sqrt{2}}(|0|1)\hfill & (u_1)\hfill \\ & \underset{\text{ }s\left(g_a\right)\text{ }}{\overset{\mathrm{Picard}}{}}\frac{1}{\sqrt{N}}\underset{x=0}{\overset{N1}{}}(1)^{xa}|x\frac{1}{\sqrt{2}}(|0|1)\hfill & (s_1)\hfill \\ & \underset{\text{ }H^nI_2\text{ }}{\overset{\mathrm{Q}}{}}|a\frac{1}{\sqrt{2}}(|0|1)\hfill & (u_2)\hfill \end{array}$$

For $`\mathrm{\Pi }=|aa|I_2`$ again, Q wins with probability 1, having queried Picard only once!

Just as before, Picard makes the game hardest for Q classically if he chooses $`a`$ uniformly at random. Classically Q requires $`n`$ queries to determine $`a`$ with probability 1. The classical to quantum improvement in number of queries is thus $`n`$ to 1, in some sense greater than the Grover improvement from $`O(N)`$ to $`O(\sqrt{N})`$.

4. Entanglement

Most remarkably, Bernstein & Vazirani’s ‘sophisticated’ quantum search algorithm achieves this improvement without creating any entanglement at any timestep! Recall the following definition.

Definition. A pure state—a vector in $``$—is entangled if it does not factor relative to a given tensor product decomposition of the Hilbert space .

In the two algorithms considered in the previous sections, the Hilbert space decomposes into a tensor product of qubits , i.e., $`\text{}^2`$s. To see that the slightly improved  Bernstein-Vazirani algorithm  creates no entanglement relative to this decomposition, note that $`\psi _0`$ has no entanglement, and hence $`u_1\psi _0`$ has none since $`u_1`$ is the tensor product of operations on individual qubits. Also, $`\psi _f`$ is not entangled since $`|a`$ is just the tensor product of qubits in states $`|0`$ or $`|1`$. But $`\psi _f`$ is obtained from the intermediate state $`s_1u_1\psi _0`$ by the action of $`u_2`$ which, like $`u_1`$, is the tensor product of operations on individual qubits. So $`s_1u_1\psi _0`$ also is not entangled.

In contrast, for Grover’s algorithm, every state after $`u_1\psi _0`$ is entangled for $`n>1`$. By a natural measure the entanglement oscillates with period $`\frac{\pi }{4}\sqrt{N}`$, i.e., after $`\frac{\pi }{4}\sqrt{N}`$ queries the state is close to $`|a\frac{1}{\sqrt{2}}(|0|1)`$ and its entanglement is fairly small, while after only $`\frac{\pi }{8}\sqrt{N}`$ queries the entanglement is fairly large . So what could be the suggestion of Lloyd, to which I alluded in the Introduction, that Grover’s algorithm can be implemented without entanglement ? He simply observes that since the first $`n`$ qubits are never entangled with the last qubit, if they are implemented by a single tensor factor of dimension $`N`$, there is no entanglement. This is true, of course, by definition, and has been observed earlier in the general quantum computing setting by Jozsa and Ekert . The cost incurred for realizing such a scheme physically, as Lloyd acknowledges, increases exponentially with $`n`$ and must be paid with increasing energy, mass, or precision.

5. Conclusion

So what do quantum games have to do with quantum algorithms? The two versions of GUESS A NUMBER illustrate the relation for oracle problems. In these cases, quantum algorithms specialize the PQ game definition to require that $`s_1=\mathrm{}=s_k`$, i.e., the oracle always responds the same way once a function has been chosen. Furthermore, the winning states for Q, $`W_\mathrm{Q}`$, depend on Picard’s strategy $`\{s_i\}`$, i.e., on $`a`$. The Deutsch-Jozsa , Simon  and Shor  algorithms can also be described this way.

Are there ‘sophisticated’ quantum algorithms? Yes. The oracle which responds in the Bernstein-Vazirani scenario with $`xa`$ mod 2 is a ‘sophisticated database’ by comparison with Grover’s ‘naïve database’ which only responds that a guess is correct or incorrect. The former is closely related to the vector space model for information retrieval in which there is a vector space with basis vectors corresponding to the occurrence of key words: database elements define vectors in this space and are ranking according to their inner product with the vector representing a query . Furthermore, relatively speaking, it improves more over the classical optimum than does Grover’s algorithm.

And finally, is entanglement required for quantum-over-classical improvements? No. I’ve shown that, remarkably, the slightly improved version of the Bernstein-Vazirani algorithm does not create entanglement at any timestep, but still solves this oracle problem with fewer queries than is possible classically. Relative to the oracle, this quantum algorithm has no entanglement, unlike Grover’s, which does—at least within the standard model of quantum computing. It illustrates both ‘sophisticated quantum search’ without entanglement and sophisticated “quantum search without entanglement” .

Acknowledgements

I thank Mike Freedman, Manny Knill, Raymond Laflamme, John Smolin and Nolan Wallach for useful discussions. This work has been partially supported by Microsoft Research and by ARO grant DAAG55-98-1-0376.

References

 D. Deutsch & R. Jozsa, “Rapid solution of problems by quantum computation”, Proc. Roy. Soc. Lond. A 439 (1992) 553–558.

 D. R. Simon, “On the power of quantum computation”, in S. Goldwasser, ed., Proceedings of the 35th Symposium on Foundations of Computer Science, Santa Fe, NM, 20–22 November 1994 (Los Alamitos, CA: IEEE Computer Society Press 1994) 116–123.

 P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring”, in S. Goldwasser, ed., Proceedings of the 35th Symposium on Foundations of Computer Science, Santa Fe, NM, 20–22 November 1994 (Los Alamitos, CA: IEEE Computer Society Press 1994) 124–134.

 L. K. Grover, “A fast quantum mechanical algorithm for database search”, in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, 22–24 May 1996 (New York: ACM 1996) 212–219.

 S. Wiesner, “Conjugate coding”, SIGACT News 15 (1983) 78–88; C. H. Bennett & G. Brassard, “Quantum cryptography: Public-key distribution and coin tossing”, in Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, December 1984 (New York: IEEE 1984) 175–179; A. Ekert, “Quantum cryptography based on Bell’s theorem”, Phys. Rev. Lett. 67 (1991) 661–663.

 P. W. Shor, “Scheme for reducing decoherence in quantum computer memory”, Phys. Rev. A 52 (1995) R2493–R2496; A. M. Steane, “Error correcting codes in quantum theory”, Phys. Rev. Lett. 77 (1996) 793–797.

 A. S. Kholevo, “Bounds for the quantity of information transmitted by a quantum communication channel”, Problemy Peredachi Informatsii 9 (1973) 3–11; transl. in Problems Inf. Transmiss. 9 (1973) 177–183; C. H. Bennett, D. P. DiVincenzo, J. Smolin & W. K. Wootters, “Mixed state entanglement and quantum error correction”, Phys. Rev. A 54 (1996) 3824–3851; B. Schumacher, M. Westmoreland & W. K. Wootters, “Limitation on the amount of accessible information in a quantum channel”, Phys. Rev. Lett. 76 (1997) 3452–3455.

 R. Cleve & H. Buhrman, “Substituting quantum entanglement for communication”, Phys. Rev. A 56 (1997) 1201–1204; H. Buhrman, W. van Dam, P. Høyer & A. Tapp, “Multiparty quantum communication complexity”, Phys. Rev. A 60 (1999) 2737–2741.

 J. von Neumann, in A. H. Taub, ed., Collected Works, Vol. 5, Design of Computers, Theory of Automata and Numerical Analysis (New York: Pergamon Press 1961–1963).

 J. von Neumann, Mathematische Grundlagen der Quantenmechanik (Berlin: Springer-Verlag 1932); transl. by R. T. Beyer as Mathematical Foundations of Quantum Mechanics (Princeton: Princeton University Press 1955).

 J. von Neumann, “Zur theorie der gesellschaftsspiele”, Math. Ann. 100 (1928) 295–320.

 J. von Neumann & O. Morgenstern, Theory of Games and Economic Behavior, third edition (Princeton: Princeton University Press 1953).

 D. A. Meyer, “Quantum strategies”, Phys. Rev. Lett. 82 (1999) 1052–1055.

 See, e.g., S. J. van Enk, “Quantum and classical game strategies”, Phys. Rev. Lett. 84 (2000) 789.

 D. A. Meyer, “Why quantum strategies are quantum mechanical”, published as“Meyer replies”, Phys. Rev. Lett. 84 (2000) 790.

 C. H. Bennett, E. Bernstein, G. Brassard & U. Vazirani, “Strengths and weaknesses of quantum computing”, SIAM J. Comput. 26 (1997) 1510–1523.

 M. Boyer, G. Brassard, P. Høyer & A. Tapp, “Tight bounds on quantum searching”, Fortsch. Phys. 46 (1998) 493–506.

 C. Zalka, “Grover’s quantum searching algorithm is optimal”, Phys. Rev. A 60 (1999) 2746–2751.

 S. Lloyd, “Quantum search without entanglement”, Phys. Rev. A 61 (1999) 010301.

 R. Jozsa, “Entanglement and quantum computation”, in S. A. Huggett, L. J. Mason, K. P. Tod, S. T. Tsou & N. M. J. Woodhouse, eds., The Geometric Universe: Science, Geometry, and the Work of Roger Penrose (Oxford: Oxford University Press 1998) 369–379; A. Ekert & R. Jozsa, “Quantum algorithms: entanglement-enhanced information processing”, Phil. Trans. Roy. Soc. Lond. A 356 (1998) 1769–1782.

 A. M. Steane, “A quantum computer needs only one universe”, quant-ph/0003084.

 S. L. Braunstein, C. M. Caves, R. Jozsa, N. Linden, S. Popescu & R. Schack, “Separability of very noisy mixed states and implications for NMR quantum computing”, Phys. Rev. Lett. 83 (1999) 1054–1057; R. Schack & C. M. Caves, “Classical model for bulk-ensemble NMR quantum computation”, Phys. Rev. A 60 (1999) 4354–4362; For a response to this criticism, see R. Laflamme, “Review of ‘Separability of very noisy mixed states and implications for NMR quantum computing’ ”, Quick Reviews in Quantum Computation and Information, http://quickreviews.org/qc/.

 R. F. Werner, “Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model”, Phys. Rev. A 40 (1989) 4277–4281.

 L. M. Krauss, The Physics of Star Trek, with a forword by Stephen Hawking (New York: HarperCollins 1995).

 P. A. M. Dirac, The Principles of Quantum Mechanics, fourth edition (Oxford: Oxford University Press 1958).

 J. Eisert, M. Wilkens & M. Lewenstein, “Quantum games and quantum strategies”, Phys. Rev. Lett. 83 (1999) 3077–3080.

 S. C. Benjamin & P. M. Hayden, “Comment on ‘Quantum games and quantum strategies’ ”, quant-ph/0003036.

 A. M. Steane & W. van Dam, “Physicists triumph at guess my number”, Phys. Today 53(2) (February 2000) 35–39.

 R. Cleve, A. Ekert, C. Macchiavello & M. Mosca, “Quantum algorithms revisited”, Proc. Roy. Soc. Lond. A 454 (1998) 339–354.

 E. Bernstein & U. Vazirani, “Quantum complexity theory”, in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, San Diego, CA, 16–18 May 1993 (New York: ACM 1993) 11–20; This algorithm was rediscovered independently in B. M. Terhal & J. A. Smolin, “Single quantum querying of a database”, Phys. Rev. A 58 (1998) 1822–1826.

 E. Schrödinger, “Die gegenwärtige Situation in der Quantenmechanik”, Naturwissenschaften 23 (1935) 807–812; 823–828; 844–849.

 B. Schumacher, “Quantum coding (information theory)”, Phys. Rev. A 51 (1995) 2738–2747.

 D. A. Meyer & N. R. Wallach, “Invariants for multiple qubits I: the case of 3 qubits”, in preparation.

 G. Salton & M. McGill, Introduction to Modern Information Retrieval (New York: McGraw-Hill 1983); M. W. Berry, Z. Drmač & E. R. Jessup, “Matrices, vector spaces, and information retrieval”, SIAM Rev. 41 (1999) 335–362.

 D. A. Meyer, “Sophisticated quantum search without entanglement”, UCSD preprint (2000).


format: text

text:
# The Shrödinger operator on graphs and topology

We shall define a Schrödinger operator for a one-dimensional simplicial complex (a graph)111We began the discussion of this problem together with A. P. Veselov $`\mathrm{\Gamma }`$ without ends (that is, at least two and only finitely many edges meet at any vertex), which acts on functions of vertices $`T`$ or edges $`R`$:

$$(L\psi )_T=\underset{T^{}}{}b_{T:T^{}}\psi _T^{}$$
$`(\mathrm{V})`$
for $`L_0=^{}`$, $`b_{T:T^{}}=1`$, $`b_{T:T^{}}=m_T`$,

$$(L\psi )_R=\underset{R^{}}{}d_{R:R^{}}\psi _R^{}$$
$`(\mathrm{E})`$
for $`L_0=^{}`$, $`d_{R:R^{}}=1`$, $`d_{R:R}=2`$.

Here the coefficients are real, symmetric, and non-zero only for nearest neighbours

$$T^{}T=R,RR^{}=T.$$

The coefficients $`b_{T:T}=W_T`$ and $`d_{R:R}=W_R`$ are called the potential, $`m_T`$ is the number of edges at a vertex, and $``$ is the boundary operator.

Definition 1. The Wronskian of a pair of solutions of $`L\psi _i=\lambda \psi _i`$, $`i=1,2`$, is the skew-symmetric bilinear expression

$$W_𝐑=b_{T:T^{}}(\psi _{1T}\psi _{2T^{}}\psi _{2T}\psi _{1T^{}}),T^{}T,$$
$`(\mathrm{V})`$
$$W_𝐑=\underset{R^{}R=T}{}d_{R:R^{}}(\psi _{1R}\psi _{2R^{}}\psi _{2R}\psi _{1R^{}}),R^{}R.$$
$`(\mathrm{E})`$
Here $`𝐑=(TT^{})`$ is an oriented edge, $`W_{TT^{}}=W_{T^{}T}`$.

Theorem 1. The Wronskian of a pair of solutions is well defined as a 1-chain on $`\mathrm{\Gamma }`$, whose boundary is equal to zero: $`W=0`$.

The proof follows in both cases by considering the quantity $`(L\psi _1)\psi _2(L\psi _2)\psi _1`$.

We consider a graph $`\mathrm{\Gamma }`$ having $`k`$ ‘tails’ $`(z_1,\mathrm{},z_k)`$, $`k1`$: the tails $`z_j`$ are half-lines with edges $`R_{jn}`$, $`n1`$, and vertices $`T_{j,n1}`$, $`R_{jn}=T_{jn}T_{j,n1}`$. Suppose that the Schrödinger operator is ‘finitary’, that is, for $`n>n_0`$ and all $`j`$ we have $`L=L_0+2`$ in both cases.

The equation $`L\psi =\lambda \psi `$ has solutions in $`z_j`$ as $`n\mathrm{}`$ of the form $`\psi _{jn}^\pm =a_\pm ^n`$, $`a_\pm =\frac{1}{2}(\lambda \pm \sqrt{\lambda ^24})`$. A basis of real solutions for $`\lambda `$ is:

$$C_{jn}=(a_{}\psi _{jn}^++a_+\psi _{jn}^{})(a_++a_{})^1,S_{jn}=(\psi _{jn}^+\psi _{jn}^{})(a_+a_{})^1.$$

These solutions are defined only on the tails. We introduce a ‘phase space’ $`^{2k}`$ with basis $`(C_1,S_1,\mathrm{},C_k,S_k)`$ and a skew-scalar product

$$C_i,C_j=S_i,S_j=0,C_i,S_j=\delta _{ij}.$$

The operator $`L`$ determines the subspace $`\mathrm{\Lambda }_\lambda ^{\mathrm{}}^{2k}`$ of vectors $`\psi _{\mathrm{}}\mathrm{\Lambda }_\lambda ^{\mathrm{}}`$, which can be extended to the whole graph $`\mathrm{\Gamma }`$ as the solution

$$L\psi =\lambda \psi ,\psi =\psi _0=(\psi _1\mathrm{},\mathrm{},\psi _k\mathrm{}),\psi _j\mathrm{}=\alpha _jC_j+\beta _jS_j$$

in the tail $`z_j`$ for $`n>n_0`$.

Theorem 2. 222In 1971 I. M. Gelfand told the author about an interesting idea on the relation between self-adjoint extensions of symmetric operators and Lagrangian planes. This was Gel’fand’s reaction to the author’s paper , built round the relation between Hamiltonian formalism and differential topology. The subspace $`\mathrm{\Lambda }_\lambda ^{\mathrm{}}`$ is Lagrangian, that is, the scalar product on it is equal to zero.

The proof follows from Theorem 1. In fact, for any pair of solutions $`\psi _1`$, $`\psi _2`$ on $`\mathrm{\Gamma }`$ we have $`W=_{j=1}^k\kappa _jz_j+\text{ (finite)}`$, where the $`z_j`$ are the tails. Only the differences $`z_iz_j`$ can be extended to cycles on $`\mathrm{\Gamma }`$ modulo $`\mathrm{}`$. Therefore we have $`W=_{l2}^k\mu _l(z_1z_l)+\text{ (a finite cycle)}=_{j=1}^k\kappa _jz_j+\text{ (a finite chain)}`$. Hence the theorem follows:

$$\underset{j=1}{\overset{k}{}}\kappa _j=0=\psi _1\mathrm{},\psi _2\mathrm{}.$$

We represent the graph $`\mathrm{\Gamma }`$ in the form $`\mathrm{\Gamma }=\mathrm{\Gamma }^{}K_1\mathrm{}K_s`$, where the $`K_l`$ are trees growing from the vertices (‘nests’) $`T_l\mathrm{\Gamma }^{}`$, with $`\mathrm{\Gamma }^{}`$ a finite graph without ends (‘the base’), $`sk`$.

Theorem 3. The dimension of the spaces of solutions of $`L\psi =\lambda \psi `$ on $`\mathrm{\Gamma }`$ is always at least $`k`$. It is strictly greater than $`k`$ if and only if the Schrödinger operator $`L^{}`$, restricted to the base $`\mathrm{\Gamma }^{}`$ has a ‘singular’ eigenvalue $`\lambda _p^{}`$, where $`\psi _P^{}(t_l)=0`$ at all nests $`l=1,\mathrm{},s`$. In this case and anly in this case the operator that associates the vector $`\psi _{\mathrm{}}\mathrm{\Lambda }_\lambda ^{\mathrm{}}`$ with the solution of $`L\psi =\lambda \psi `$ has a non-trivial kernel.

The spectrum of the operator $`L`$ in the Hilbert space $`_2^\epsilon (\mathrm{\Gamma })=H_\epsilon `$, $`\epsilon =0,1`$ (vertices and edges) can be divided into a continuous part $`|\lambda |2`$ (scattering zone) and a discrete spectrum in the zones $`\lambda <2`$, $`\lambda >2`$. Points of the discrete spectrum inside the zone $`|\lambda |2`$ are possible only if localized on $`\mathrm{\Gamma }^{}`$, where $`\lambda =\lambda ^{}`$ is a singular eigenvalue. The algebraic properties of the scattering zone (unitarity) are entirely determined by Theorem 2. For $`|\lambda |>2`$ we have $`a_+a_{}=1`$, $`a_\pm `$. We consider a Lagrangian plane $`\mathrm{\Lambda }_\lambda ^{}^{2k}`$ with basis $`\mathrm{\Psi }_j^{}`$, $`j=1,\mathrm{},k`$, decreasing at infinity.

Proposition 1. A point $`\lambda `$, is a point of the discrete spectrum for $`L`$ in $`H_\epsilon `$ $`(\epsilon =0,1)`$ if $`\mathrm{\Lambda }_\lambda ^{\mathrm{}}\mathrm{\Lambda }_\lambda ^{}`$ is non-empty or $`\lambda =\lambda _p^{}`$ is a singular eigenvalue on the base $`\mathrm{\Gamma }^{}`$ The Morse indices of eigenvalues for $`\lambda [2,\mathrm{}]`$ and $`\lambda [\mathrm{},2]`$ are well-defined and equal to the algebraic numbers of the normal discrete eigenvalues. There is necessarily a discrete spectrum if: $`\mathrm{max}_T\left(b_{T:T^{}}^2+W_T^2\right)>4`$, $`\mathrm{max}_R\left(d_{R:R^{}}^2+W_R^2\right)>4`$, or $`\mathrm{max}_q|\lambda _q^{}|>4`$ for the spectrum of base $`\mathrm{\Gamma }^{}`$.


text:
# Determining the reality of X-ray filaments

## 1 Introduction

With the advent of high-resolution X-ray telescopes it is now routine to see structure in X-ray images. Assessing the level at which one should believe this structure presents more of a challenge in X-ray observations than in optical or radio images of comparable resolution, because X-ray data are very often photon-noise limited. The problem is made worse by the common (and necessary) practice of smoothing the data with a Gaussian. This is carried out in order to make the images conform to our expectations of what the ‘true’ sky image with infinite exposure time would look like; but it is important to remember that in general it does not in fact take away the photon-limited nature of the underlying data.

A number of smoothed X-ray images of extragalactic objects appear, on published contour maps, to show quite clear ‘filamentary’ connections between X-ray sources in the field. (The term ‘filament’ does not have a single definition in the literature; I shall use it to mean any extended, apparently linear connection between two sources.) In this paper I discuss the techniques necessary to determine whether such filamentary connections are real, and apply them to some sample observations of galaxies and quasars, previously analysed by other authors (Arp 1996, Dahlem et al. 1996, Arp 1997), which I have taken from the ROSAT archives.

## 2 Significance and contouring

The first problem in assessing the reality of features in smoothed X-ray maps is that of the significance levels to be chosen when contouring. If the mean background count density is $`\mu `$ counts per unit area and the convolving Gaussian has the form111To avoid confusion, I use $`\mathrm{\Sigma }`$ throughout the paper to denote the width of a convolving Gaussian, and $`\sigma `$ to refer to the conventional significance levels. $`f(r)\mathrm{exp}(r^2/2\mathrm{\Sigma }^2)`$, then, as pointed out in Appendix A of Hardcastle et al. (1998), the background noise is not normally distributed unless $`\mu \mathrm{\Sigma }^21`$, a condition which does not typically apply in the sort of datasets being considered here. It is therefore incorrect, for example, to take the r.m.s. dispersion of the background noise after smoothing, multiply by three, add the mean and call the resulting contour level ‘$`3\sigma `$’ as though it were the corresponding confidence level for normally-distributed noise. In general it is not. Contours for noise which is not normally distributed should ideally have the same properties as those for normally distributed noise, so that the contour referred to as the ‘$`3\sigma `$’ contour, for example, should exclude all but 0.135% of the background. But in the case where $`\mu \mathrm{\Sigma }^21`$, there is no analytic solution to the question ‘what is the contour level corresponding to the $`n\sigma `$ level for normally distributed noise, for some $`n`$?’. Instead, Hardcastle et al. (1998) outline a Monte Carlo procedure for determining the correct significance level. In this procedure, fields of simulated Poisson noise are convolved with a Gaussian and the ‘$`n\sigma `$’ level is derived directly from the distribution of the resulting noise. (Results of this process for some sample values of $`\mu `$ and $`\mathrm{\Sigma }`$ are plotted in Fig. 1.) If, on the other hand, $`\mu \mathrm{\Sigma }^21`$, then the noise will be approximately normally distributed and a simple analysis, described in Hardcastle et al. (1998), shows that the $`3\sigma `$ contour should be at $`\mu +3\sqrt{\mu /4\pi \mathrm{\Sigma }^2}`$ counts per unit area.

It is common for authors not to state the method by which the ‘$`3\sigma `$’ (or other) levels in published contour plots of smoothed X-ray images were derived; in some cases, even the size of the convolving Gaussian and/or the binning scheme is not given. This practice makes it very difficult to assess the reality of features in such plots, and it is recommended that in all cases where the noise is not, or might not be, normally distributed authors should explain what they mean by ‘$`3\sigma `$’. In what follows, wherever I refer to a $`2\sigma `$ or $`3\sigma `$ level calculated by me, it will imply that I have derived it from simulated Poisson noise as described above.

## 3 The effect of the PSF

However, even when the $`3\sigma `$ level is correctly defined, such that a contour at this level would exclude all but 0.135% of the Gaussian-smoothed background noise, it is unfortunately not necessarily the case that we can say that all ‘structure’ around a bright source enclosed by such a contour is detected at a corresponding significance level. The radially averaged point-spread function (PSF) of X-ray instruments often has a very broad tail, so that there are expected to be significant count densities at large distances from the centroid; the shape of the PSF can be energy-dependent, so that these off-centre counts are likely to have a peculiar spectrum compared to either the point source itself or the background. When two point sources are placed close to each other, the natural consequence of this feature of the PSF is that we get an enhancement of the count rate which is at its greatest directly between them. Smoothing the data with a Gaussian may well bring this feature up above the noise, giving the appearance of a filament connecting the sources.

So to assess the reality of filaments observed at a given contour level in smoothed images we must ask what is the probability of seeing such filaments under the null hypothesis, which is that the two sources are in fact not connected by any real feature on the X-ray sky. In general this too must be done by Monte Carlo simulation. I have written code which generates a Poisson-distributed noise background and two or more simulated sources, convolved with a suitable PSF, which match those seen on the sky. The simulated data are then smoothed with a Gaussian, and then either automatically or by eye it is possible to see whether a ‘filament’ at a given contour level joins them (in practice, the code does this using a simple recursive flood-fill algorithm). By repeating this procedure many times, we can directly estimate the probability that an observed filament would be seen under the null hypothesis, and so characterise its statistical significance. Only connections which have a very small chance of being seen under the null hypothesis can be described as statistically significant. An example of the kinds of apparent filaments that can result from low choices of contour levels even under the null hypothesis is given in Fig. 2.

## 4 Data and simulations

Using the techniques discussed above, it is possible to re-examine objects discussed in the literature. The ROSAT data listed in Table 1 were obtained from the public archive. Data were analysed using the IRAF Post-Reduction Offline Software (PROS).

The radially averaged ROSAT PSPC PSF is well known (e.g. Hasinger et al. 1995) and so, using a suitably integrated version of an analytical approximation to the PSF, it is simple to simulate PSPC observations. One complication is that the PSF is both energy-dependent and dependent on the off-axis angle of the source. Dealing with the energy dependence of the PSF is not hard, but would involve generating an energy-weighted PSF for each source. For simplicity, I choose to use the PSF at a single energy, in most cases 1 keV (the energy at which ROSAT is most sensitive); this is a conservative choice, in the sense that the PSF is narrowest at approximately this energy. The off-axis angle dependence of the width of the PSF is incorporated, though not the distortions which appear at far-off-axis angles; no source considered here is significantly affected by them. The actual PSF observed in a given observation is also affected by the ROSAT aspect reconstruction problems, which can introduce various kinds of elongation, but since it is very hard to determine the extent to which this affects a given observation, I have not included it in the simulations.

The ROSAT HRI PRF is more strongly affected by the aspect reconstruction problems, but, for simplicity, in the two cases where it is used in this paper I have just used the standard parametrization of David et al. (1997).

### 4.1 Mrk 474

Mrk 474 is a $`z=0.041`$ Seyfert galaxy adjacent to a $`z=1.94`$ quasar (Arp 1996). The Seyfert is a very strong X-ray source, while the point X-ray source identified by Arp with the quasar, located 170 arcsec to the NW, is only weakly detected in the PSPC observations.

Arp (1996) analysed the 0.5-2.0 keV PSPC data, and saw a filament connecting the Seyfert and quasar. It is not clear what binning scheme and smoothing Gaussian was used to produce his figures 1 and 2, but I obtain very similar results by binning by a factor 7 (so that each pixel is 3.5 arcsec) and smoothing with a Gaussian of $`\mathrm{\Sigma }=4`$ pixels (14 arcsec). The results are insensitive to the exact values of binning and smoothing used. The mean number of background counts in the image per 3.5-arcsec pixel, close to the central source and after excluding all visible background sources is 0.0135, which, using the techniques described in section 2, corresponds to $`2`$\- and $`3\sigma `$ levels in the smoothed dataset of 0.032 and 0.044 counts pixel-1 respectively. The image is contoured with these levels in Fig. 3. Comparing this figure with Arp’s figures 1 and 2, it can be seen that my $`2\sigma `$ level is more or less equivalent to his $`4\sigma `$ level, while my $`3\sigma `$ level is close to his $`5\sigma `$ level. As shown in Fig. 3, the connecting ‘filament’ is not represented except at the $`2\sigma `$ level when the confidence limits are calculated correctly. Moreover, when I simulated this situation (using 30 net counts for the quasar, as measured by Arp (1996), and 6700 net counts for the Seyfert galaxy), I found that we expect to see a connection between the two sources at the $`2\sigma `$ level 65% of the time, and even at the $`3\sigma `$ level 30% of the time, if the two sources are in fact just adjacent point sources, because of the increased count density close to Mrk 474. The detection of the filament in this source is thus certainly not statistically significant.

### 4.2 NGC 4651/3C 275.1

The nearby (Virgo cluster) galaxy NGC 4651 is adjacent to the radio-loud quasar 3C 275.1 ($`z=0.557`$). In this case the quasar is a reasonably strong X-ray source, while the galaxy shows some weaker extended emission. Hardcastle & Worrall (1999) found the PSPC emission from the quasar to be consistent with that of a point source, although the HRI observations of the source suggest some extension on small scales, consistent with emission from a cluster (Hardcastle & Worrall 1999, Crawford et al. 1999). NGC 4651 has an optical jet or tail; Arp (1996) views this as evidence for ejection, while Wehrle, Keel & Jones (1997) suggest that the optical colours are evidence for a tidal origin.

Binning and smoothing the 0.1-2.0 keV energy band with the same parameters as I used for Mrk 474, and with a measured mean background count level of 0.0534 counts pixel-1, the elongation of NGC 4651 in the direction of 3C 275.1 is clearly visible. The $`3\sigma `$ contour after smoothing is at about 0.110 counts pixel-1, and the elongation is seen at this level \[corresponding to a level somewhere between the $`4`$ and $`8\sigma `$ contours in figure 7 of Arp (1996)\]. Taking the quasar as containing about 200 counts in the 0.1-2.0 keV energy band, and the galaxy as containing 120, I used simulations to determine whether, if the galaxy were really a point source, the effect of the quasar’s proximity could cause the observed extension; as expected from the images and from the comparative weakness of the quasar, the probability of obtaining such a strong result by chance is negligible. We can safely conclude that the extension of NGC 4651 is likely to be real. However, there is no evidence for a compact jet-like structure in NGC 4651 in the HRI image.

### 4.3 NGC 3067/3C 232

The radio-loud quasar 3C 232 ($`z=0.534`$) is adjacent to the starburst galaxy NGC 3067. In this case, too, the effect of contamination by the quasar’s PSF is small and the elongation seen by Arp (1996) in the 0.7–2.0 keV X-ray emission of NGC 3067 appears real; simulation shows that this degree of extension in the smoothed image is too great to be produced by chance, particularly as it is not directed towards the quasar (which is what we would expect for an artefact of the sort discussed in section 3).

Arp (1996) also reports filaments in smoothed 0.1-2.0 keV images connecting 3C 232 to stellar objects to the north and northeast. Arp binned the data here in 5-arcsec pixels and smoothed with a small Gaussian of $`\mathrm{\Sigma }=3`$ pixels. The background noise level per 5-arcsec pixel in this energy band is 0.068 counts; the corresponding $`3\sigma `$ level is 0.15 counts pixel-1, whereas Arp’s lowest contour appears to have been at 0.11 counts pixel-1, somewhat below the $`2\sigma `$ level. Simulation shows that we would not expect a filament even at this level connecting 3C 232 with the northern stellar object by chance under the null hypothesis, which suggests that there is some real emission in between 3C 232 and the northern stellar object, but the data provide no significant evidence for such a filament rather than, for example, an intervening point source.

### 4.4 NGC 4319/Mrk 205

Arp (1996) observed the X-ray bright $`z=0.07`$ Seyfert galaxy Mrk 205 with the ROSAT HRI. The Seyfert lies 44 arcsec south of the galaxy NGC 4319, which was not detected in the HRI observations; but a number of other sources are detected in the field, including the early-type galaxy NGC 4291, 6.4 arcmin away to the NE, which is extended in the X-ray. Three of the brightest of these sources, at off-axis distances from 8 to 15 arcmin, are identified with intermediate-to-high redshift quasars. In addition to Arp’s data, a deeper exposure centred on NGC 4291 exists in the archive; this shows similar detections. Having adaptively smoothed his dataset (this process involves smoothing the pixels containing small numbers of photons with larger Gaussians than those containing larger numbers, and then summing the results) Arp obtained the ‘startling’ result that many — indeed, almost all — of the point sources were joined to the central source, Mrk 205, by ‘filaments’ of X-ray emission.

I began to investigate this field by analysing the data in a similar way to the other sources. Adopting Arp’s binning scheme of 8-arcsec pixels, the mean number of background counts per pixel $`\mu `$ is then about 1.08. I smoothed the whole image with a Gaussian of 16 pixel FWHM, or $`\mathrm{\Sigma }=6.80`$ pixels; the corresponding $`3\sigma `$ level is 1.21 counts pixel-1. (This result was derived from numerical simulation, but since $`\mathrm{\Sigma }^2\mu 1`$ in this case, the background noise is close to being normally distributed, and the analytic approximation described in section 2 in fact applies and gives the same answer.) At this level, or even at the corresponding $`2\sigma `$ level, no filaments connected any of the sources. Only at the $`1\sigma `$ contour level did the filamentary structure seen in Arp’s figure 10 begin to become apparent.

However, Arp’s use of adaptive smoothing is intended to improve the visibility of low-surface-brightness features. The characteristics of Poisson noise smoothed in this way are even less clear than for the single-Gaussian case, but the question may still be answered by Monte Carlo simulation as discussed in section 2. Arp’s description of his binning scheme is somewhat ambiguous, but I obtained a reasonable match to the image in his figure 10 by smoothing the 8-arcsec pixels containing one count with a Gaussian of $`\mathrm{\Sigma }`$ (not FWHM) of 16 pixels, pixels with two counts with a Gaussian of $`\mathrm{\Sigma }=16/\sqrt{2}`$ pixels, and so on ($`\mathrm{\Sigma }=16\times 2^{(n1)/2}`$ pixels, where $`n`$ is the number of counts) up to pixels with more than 12 counts, which were not smoothed.

I then simulated the effects of smoothing Poisson-distributed noise with $`\mu =1.08`$ counts pixel-1 with this adaptive filter. The resulting $`3\sigma `$-equivalent level (1.29 counts pixel-1) is, as expected, higher for this smoothing method than for the case where the whole field is smoothed with the largest Gaussian (on the analytic approximation, this would be 1.13 counts pixel-1), both because the ‘average’ smoothing Gaussian is smaller and because the method accentuates the difference between bright and faint noise pixels. As shown in Fig. 4, when contoured at this level my adaptively smoothed image shows no significant filaments; a much lower level of contouring is required to show up the structures in Arp’s figure 10. In fact, it appears from the caption from Arp’s figure 11a that his ‘$`3\sigma `$’ level is 1.08 counts pixel-1, which is similar to the expected number of counts per pixel (unchanged, of course, as a result of smoothing). It is therefore not at all surprising that contouring at this level shows connections between adjacent sources; since the median for these data is close to the mean, this contour level corresponds to contouring about half the area of the map (preferentially the central regions, because of the effects of vignetting on the external component of the X-ray background). Simulating adaptive smoothing of the HRI field of view, neglecting vignetting, I find that we expect to see a connection at this level between the central source and the northernmost point source (identified with a $`z=0.464`$ quasar) approximately 25% of the time under the null hypothesis; the filaments in Arp (1996) are therefore not statistically significant. They are similarly undetected on the deeper HRI image centred on NGC 4291 (where the $`3\sigma `$ level of the adaptively smoothed image is lower as a fraction of $`\mu `$ because of the higher number of background counts per pixel).

### 4.5 NGC 3628

The starburst galaxy NGC 3628 was observed by Dahlem et al. (1996) and shows a striking filamentary structure, extending south from the galactic nucleus to a point source 2.7 arcmin away, in images in the 0.75 keV band (0.44–1.21 keV) and 1.5 keV band (0.73–2.04 keV); this point source itself appears connected to another point source a short distance to the SE, which Flesch & Arp (1999) identify with a $`z=2.15`$ quasar.

The contour levels selected by Dahlem et al. correspond quite well to the $`3\sigma `$ levels derived from simulation; after master veto rate filtering to match theirs and binning in 15-arcsec pixels I find a background count rate away from NGC 3628 in the 0.75-keV band of 0.23 counts pixel-1, corresponding to a $`3\sigma `$ level of 0.73 counts pixel-1, which is actually below their adopted $`2.5\sigma `$ level. The filament is thus apparent in contours at better than the $`3\sigma `$ level. Simulation (using a PSF appropriate for an energy of 0.75 keV) shows that the connection between the two adjacent point sources is not significant, but that a connection at the observed level between NGC 3628 and the source to the S is not expected to occur by chance. However, this does not take account of the extended X-ray halo found by Dahlem et al. (1996) around NGC 3628 (and clearly visible as excess emission in their figure 2). If we model this crudely as an extra uniform contribution to the background — taking the average in a region between NGC 3628 and the southern source, the background is pushed up to $`0.59\pm 0.04`$ counts pixel-1 — then the connection between NGC 3628 and the point source can occur by chance in a few per cent of cases, so the feature is only marginally significant. Again, the filamentary emission is not seen in the HRI image, which supports the notion that we are seeing a region of extended emission rather than a true X-ray jet; but it will clearly be of great interest to obtain more sensitive images of this field. At the time of writing, a scheduled short Chandra observation has not yet been processed.

### 4.6 NGC 4151

Arp (1997) suggests that a filament connects this well-studied Seyfert galaxy to a $`z=0.615`$ BL Lac object 5 arcmin to the N in a ROSAT HRI image. Arp binned the HRI data into 10-arcsec (20-pixel) square bins; the off-source background is then 1.21 counts pixel-1. It is not clear what Arp means when he says that he smoothed the data with a ‘$`5\sigma `$ Gaussian’; a $`\mathrm{\Sigma }=5`$ arcsec Gaussian is very small given this binning scheme while a $`\mathrm{\Sigma }=5`$ pixel Gaussian is very large, causing the two sources to overlap. I obtain images quite similar to those of Arp (1997) if I smooth with a $`\mathrm{\Sigma }=3`$ pixel Gaussian (Fig. 5). The $`3\sigma `$ level derived from simulation is then 1.53 counts pixel-1 (since $`\mu \mathrm{\Sigma }^210`$, the analytic approximation of section 2 gives a very similar answer). As Fig. 5 shows, the sources are not connected at the $`3\sigma `$ level with this choice of smoothing. A connection between the sources does appear at a much lower significance level, 1.35 counts pixel-1, which is about $`1.5\sigma `$. Simulation shows that a connection at this level can occur by chance 20% of the time under the null hypothesis (some examples of the connections seen in simulations are shown in Fig. 2, where the lowest contour is at 1.35 counts pixel-1). The connection seen in Fig. 5 is therefore not significant.

## 5 Conclusions

Using Monte Carlo techniques to find the distribution of pixel values in smoothed noise fields and to assess the reality of connections between adjacent sources, I have found that the filamentary X-ray connections between low- and high-redshift Seyfert galaxies and quasars reported by Arp (1996) are not statistically significant. I have confirmed that the X-ray extension of two low-redshift galaxies located near high-redshift radio-loud quasars, reported in the same paper, is significant. The filament extending south from NGC 3628, discussed by Dahlem et al. (1996), was shown to be marginally significant. The connection between NGC 4151 and a BL Lac object reported by Arp (1997) is also apparently not statistically significant.

These results suggest that it is necessary to be cautious in the interpretation of smoothed X-ray images, and I urge authors to apply the techniques I have described to any situation where the detection or non-detection of faint extended X-ray emission has important scientific implications.

###### Acknowledgements.

I am grateful to Eric Flesch for kindly arranging for me to be sent the copy of ‘Seeing Red’ (Arp 1998) which provoked my interest in this topic, and to two referees for their helpful suggestions.


text:
# Directed flow of antiprotons in Au+Au collisions at AGS

## 1 Introduction

The production of antiprotons at AGS energies (10-15A GeV) is near threshold in nucleon-nucleon collisions. Via collective effects, $`\overline{p}`$ production can be enhanced in nucleus-nucleus collisions as compared to p+p collisions . The observed yield of antiprotons is a result of both production and subsequent annihilation. The high antiquark densities in the quark-gluon plasma (QGP) state might lead to antibaryon abundances greatly exceeding the values in a chemically equilibrated hadron gas . However, due to conservation of entropy, those abundances may be considerably diluted to a level very close to chemical equilibrium . On the other hand, antibaryons have a large annihilation cross section, which may be modified in the baryon rich colliding systems . Measurements of $`\overline{p}`$ at the AGS may also contain a large feed-down contribution from the decay of antilambdas, $`\overline{\mathrm{\Lambda }}\overline{p}+\pi ^+`$, as well as from other antihyperons ($`\overline{Y}`$). Microscopic calculations have given some indication of how the annihilation process might change in the dense environment of a heavy-ion collision. It has been shown that the amount of annihilation in the nuclear medium depends strongly on the formation time of the hadrons . In view of all this, it came as a surprise that both in Si+Au and Au+Au collisions the measured $`\overline{p}/p`$ ratio is well described by computing the yields from a fireball in complete thermal and chemical equilibrium . Since the conditions for thermal equilibrium are equal to those for hydrodynamic evolution of the fireball, it is of great interest to determine experimentally the flow features for antiprotons.

The hydrodynamic evolution of the fireball leads to characteristic flow patterns such as radial expansion  and azimuthal anisotropies, first discovered in ultra-relativistic nuclear collisions by ref. . Since then, the study of anisotropies in the azimuthal distribution of particles, also called anisotropic (directed, elliptic, etc.) transverse flow, plays an important role in high energy nuclear collisions . Detailed measurements (for surveys see refs. ) have revealed that in a non-central high energy heavy-ion collision, nucleons in the backward hemisphere are preferentially emitted in the direction of the impact parameter vector pointing from the target to the projectile. Antiprotons co-moving with those nucleons have a greater probability of annihilation and rescattering, and this could result in an anticorrelation with the nucleon directed flow - the so-called anti-flow of antiprotons in nuclear collisions predicted by Jahns et al. . Measurements of the directed flow of antiprotons are important for understanding the role of annihilation in dense nuclear matter. They could also provide insight into the mechanism of anti-quark production in heavy-ion collisions. A surprising result reported in refs. , is the possible anomalous enhancement of the $`\overline{\mathrm{\Lambda }}/\overline{p}`$ ratio even beyond values expected for complete chemical equilibration . One possible explanation could be that $`\overline{\mathrm{\Lambda }}`$ baryons have a lower annihilation cross section than $`\overline{p}`$. A straightforward way to test this hypothesis would be the measurement of $`\overline{p}`$ and $`\overline{\mathrm{\Lambda }}`$ (anti-)flow .

Antiproton production in heavy-ion induced reactions at the AGS has been studied experimentally by the E858/E878 , E814/E877 , E866 , E886 , E864 , E802 , and E917  collaborations. In the current paper we present the first results on the measurements of directed flow of antiprotons detected in the E877 spectrometer in Au+Au collisions at a beam momentum of 11.5A GeV/c. The results were obtained from the analysis of 46 millions of central Au+Au events recorded during the 1995 heavy-ion run.

## 2 E877 apparatus

Fig. 1 shows the E877 experimental setup which is also discussed in . The trajectory of each beam particle was measured by two silicon micro-strip beam vertex detectors (BVER), located at 2.8 m and 5.8 m upstream of the target. For the 1995 run, each detector was upgraded from single-sided silicon wafers with one-dimensional pitch of 50 $`\mu `$m to double-sided wafers with a 200 $`\mu `$m pitch in both the $`x`$ and $`y`$ directions . Using these detectors the coordinates and angle of beam particles at the target were determined with an accuracy of 300 $`\mu `$m in position and 60 $`\mu `$rad in angle.

The determination of the centrality of the collision and of the reaction plane orientation were done using the transverse energy distribution measured in the target calorimeter (TCAL), and participant calorimeter (PCAL). Both calorimeters had $`2\pi `$ azimuthal coverage and, combined, provided nearly complete polar angle coverage: TCAL and PCAL covered the pseudorapidity regions $`0.5<\eta <0.8`$ and $`0.8<\eta <4.2`$, respectively .

Charged particles emitted in the forward direction and passing through a collimator ($`134`$ mrad$`<\theta _{horizontal}<16`$ mrad, $`11`$ mrad$`<\theta _{vertical}<11`$ mrad) were analyzed by a high resolution magnetic spectrometer with a horizontal bend-plane. The spectrometer acceptance covered mostly the forward rapidity region. The momentum of each particle was measured using two drift chambers, DC2 and DC3, whose pattern recognition capability was aided by four multi-wire proportional chambers (MWPC). The average momentum resolution was $`\mathrm{\Delta }p/p`$ 3%, limited by multiple scattering. A time-of-flight hodoscope (TOFU) located directly behind the tracking chambers provided the time-of-flight information with an average resolution of 85 ps. Energy loss measurements in TOFU and in a Forward Scintillator (FSCI) array located approximately 30 m downstream of the target were used to determine the particle charge.

For the 1995 run, the spectrometer was upgraded with upstream tracking chambers. Two identical multi-wire proportional chambers with highly segmented chevron-shaped readout pads, VTXA and VTXB, were instrumented and placed at 2 m and 2.25 m downstream of the target, just in front of the spectrometer magnet. They provided a precise measurement (about $`300\mu `$m resolution) of the track coordinate in the bending plane of the spectrometer before deflection in the magnetic field. A description of the design, implementation and performance of the vertex detectors can be found in .

## 3 Antiproton identification

The particle identification was performed by combining measurements of momentum, velocity, and charge of the particle. To reduce the background in the identification of antiprotons, tracks were required to have a confirmation from both upstream VTX detectors. Tracks were also required to have complete information from the cathode pad readout in both drift chambers. Fig. 2 shows the distribution of particle mass squared, calculated from the measured momentum and velocity, for negative particles with momentum less than 4 GeV/c. A clear antiproton peak is seen, with good signal-to-background ratio. The contribution of the background increases with momentum (see lower panel of Fig. 2) and becomes dominant at $`p>4.5`$ GeV/c. A maximum momentum of 4 GeV/c was required for clean identification of antiprotons. The mass resolution is quantitatively understood in terms of the intrinsic detector resolution, multiple scattering and time-of-flight resolution. For a positive antiproton identification we selected, in a plot of momentum versus the measured mass, a region of $`\pm 2.0\sigma _{m^2}(p)`$ around the antiproton mass peak, where $`\sigma _{m^2}(p)`$ represents the resolution in the mass squared at a given particle momentum $`p`$. The dependence of the mass resolution on momentum was assumed to be equal to that of protons.

Fig. 3 shows the antiproton acceptance in the transverse momentum $`p_t`$ and rapidity $`y`$ coordinates. The E877 spectrometer mainly covers the low $`p_t`$ region ($`p_t<0.4`$ GeV/c) forward of $`y_{cm}=1.6`$ ($`1.6<y<2.2`$). The final data sample comprises about 750 antiprotons with about 400 in the $`1.8<y<2.2`$ rapidity region.

Since tracking only starts 2 m downstream of the target, the E877 spectrometer is not well suited for separation of primary antiprotons from those fed down from anti-hyperon decays. Because of the large mass asymmetry and small decay momentum in these decays, the antiproton track points back to the target. A previous extensive study  based on a Monte-Carlo simulation showed that antiprotons are reconstructed for 70% of the $`\overline{\mathrm{\Lambda }}`$ and for 100% of the $`\mathrm{\Sigma }^{}`$ decaying such that the $`\overline{p}`$ is emitted into the acceptance of the spectrometer and consistent with originating from the target.

## 4 Results and Discussion

### 4.1 Experimental data

The azimuthal anisotropy in particle production is studied by means of Fourier analysis of azimuthal distributions  with respect to the reaction plane. We study the rapidity, transverse momentum, and centrality dependence of the Fourier coefficients $`v_n^{}`$ (amplitude of $`n`$-th harmonic) in the decomposition:

$$E\frac{d^3N}{d^3p}=\frac{1}{2\pi }\frac{d^2N}{p_tdp_tdy}(1+2v_1^{}\mathrm{cos}\varphi +2v_2^{}\mathrm{cos}2\varphi +\mathrm{}),$$

where the azimuthal angle $`\varphi =\varphi _{lab}\psi _r`$ is taken with respect to the reaction plane orientation. Directed flow is quantified by the dipole Fourier coefficient $`v_1^{}`$.

Similarly to the analysis performed in , the reaction plane angle is determined from the measured transverse energy distribution in four non-overlapping pseudorapidity windows. The reaction plane resolution, i.e. the accuracy with which the reaction plane orientation is determined, is evaluated by studying the correlation between flow angles measured in different windows. Finally, the flow signals are corrected for the finite reaction plane resolution. Details of this procedure are described in . In the following, only coefficients $`v_1`$ corrected for the reaction plane resolution will be shown.

The experimental acceptance for $`\overline{p}`$ is close to mid-rapidity (Fig. 3), where the directed flow changes sign. To optimize a possible flow signal, we skip the region very close to mid-rapidity and present, in Fig. 4, the measured azimuthal distributions of antiprotons emitted at rapidity $`y>1.8`$, for two collision centralities. To determine $`v_1`$, the distributions were fitted with a distribution $`f(\varphi )=1+2v_1\mathrm{cos}\varphi `$. A pronounced minimum is observed at $`\varphi =0`$ for semicentral collisions ($`\sigma =1026\%\sigma _{geo}`$), indicating that the antiproton production is strongly anti-correlated with the flow of nucleons. For more central collisions (top 10% of $`\sigma _{geo}`$), the antiproton azimuthal distribution is, within errors, isotropic ($`v_10`$). No or very little proton flow has been observed for the most central Au+Au collisions .

In order to check the contribution of the background to the observed flow signal we evaluated the azimuthal distributions for the particles whose measured mass was outside the window for positive antiproton identification. For the background sample we selected, in a plot of momentum versus the measured mass, a region of $`\pm `$2-6 $`\sigma _{m^2}(p)`$ away from the $`\overline{p}`$ mass peak. On the low mass side we cut the region less than 3.5 $`\sigma _{m^2}(p)`$ away from the $`K^{}`$ peak. The azimuthal asymmetry for the background sample was found to be consistent with zero ($`v_1=0.023\pm 0.053`$ for 10-26% $`\sigma _{geo}`$ centrality window and $`v_1=0.021\pm 0.038`$ for 0-10% $`\sigma _{geo}`$ centrality window). We also checked the $`v_1(p_t)`$-dependence for the background sample and found no signal within the statistical errors for all $`p_t`$ bins. The data shown do not include the correction due to background subtraction. Assuming a typical signal-to-background ratio of 1.2 and that background has no asymmetry, the average $`v_1`$ for 10-26% $`\sigma _{geo}`$ centrality window increases to $`0.19\pm 0.07`$.

The measured transverse momentum dependence of $`v_1`$ is shown in Fig. 5. Large negative values of $`v_1`$ are observed for $`p_t>0.1`$ GeV/c. It should be noted that the absolute value of the proton flow signal at similar rapidities and transverse momenta is significantly smaller . The right hand panel shows a result consistent with zero flow for the more central bin.

### 4.2 RQMD predictions

The Relativistic Quantum Molecular Dynamics (RQMD) model  has been widely used in describing relativistic heavy-ion collisions. It combines classical propagation of all hadrons with string and resonance excitations in the primary collisions of nucleons from target and projectile. Overlapping color strings may fuse into so-called ropes . Subsequently, the fragmentation products from rope, string and resonance decays interact with each other and with the original nucleons, mostly via binary collisions. These interactions drive the system towards equilibration  and are responsible for the development of collective flow, even in the pre-equilibrium stage. If baryons are surrounded by other baryons they acquire effective masses. These effective masses are generated by introducing Lorentz-invariant Skyrme-type quasi-potentials into the mass-shell constraints for the momenta, which simulates the effect of a mean field . There are no potential-type interactions in the so-called cascade mode of RQMD.

For antiprotons, RQMD combines a large enhancement of initial production via hadronic multi-step processes with strong absorption through the free $`\overline{p}`$ absorption cross section , which results in the absorption of a large fraction of the produced antiprotons ($``$ 90% of $`\overline{p}`$ are reabsorbed for minimum bias Au+Au collisions ). The newest version of the model (RQMD v2.3) uses the formation of a quasi-bound state (proton-antiproton molecule) to significantly reduce the possibility of antiproton annihilation. However, the presence of a mean color potential could possibly have a much more significant effect on the final antiproton distribution . A systematic study of the antibaryon production with various projectile-target combinations and at different energies would be useful for refining this approach and for understanding the annihilation process in relativistic heavy-ion collisions.

Predictions of the RQMD model run in cascade mode for the $`p_t`$-dependence of $`v_1`$ for antiprotons are compared to the data in Fig. 5. For the model, we only used antiprotons produced in the experimental acceptance window. The magnitude of the negative signal observed in the data for semicentral collisions is comparable, within the errors, to that predicted by the model although, systematically, the model values are somewhat smaller.

A current question of interest and debate is the relative importance of including nuclear mean field effects in intra-nuclear cascade models. At lower energies, experimental data and a detailed comparison with theoretical predictions have been discussed in . An attractive $`\overline{p}`$ potential of the order of 100 to 150 MeV at normal nuclear density is needed to reproduce the size and shape of the experimental spectra . It is expected that collective flow may be an important observable for evaluating the importance of mean field effects . It was shown, in particular that, in semicentral Au+Au collisions, protons exhibit a strong azimuthal anisotropy, with the amplitude of flow well reproduced by RQMD only if the effects of mean field are included . It should be noted, however that, even including the mean field, only the $`p_t`$-integrated signal is reproduced by the model, while the predicted $`p_t`$-dependence significantly differs from the data. In Fig. 6 we present the RQMD v2.3 calculations for proton and antiproton mean values of the transverse momentum projected onto the reaction plane, $`p_x`$, as a function of rapidity for Au+Au collisions at 11.5A GeV/c with impact parameters $`b<10`$ fm. Calculations are presented for a pure cascade and mean-field modes of RQMD. Since the calculations are very CPU intensive we have a limited antiproton statistics for the mean field calculations: about 500 $`\overline{p}`$’s compared to more than 8700 $`\overline{p}`$’s for the cascade mode. The flow of nucleons is enhanced due to additional repulsion in the mean field approach. For antiprotons, on the other hand, the effective mean field potential in nuclear matter is expected to be attractive. The antinucleons are pulled towards the nucleon source, therefore the anti-flow should be considerably weakened , as observed in Fig. 6. Such a weakening is also supported by the results of Spieles et al. , where it was shown that, when the influence of the real part of an antinucleon-nucleus optical potential on the $`\overline{p}`$ momentum spectra is included into the calculations, the antiproton annihilation is indeed suppressed in the heavy-ion environment, such that the sum of in-medium annihilation cross section and elastic cross section is closer to the free annihilation cross sections which are employed in the cascade mode of RQMD v2.3. On the other hand, the amplitude of the measured antiproton flow signal is rather well described by the pure cascade calculations (see Fig. 5). A similar observation has been recently made by comparing the measurements of $`K^+`$ directed flow with the cascade and mean field RQMD predictions , where it has been shown that the cascade calculations reproduce the data better than the mean field calculations. Further measurements and detailed calculations in the mean field mode are required and this question cannot be fully settled until antiproton yield and flow have been measured over a larger phase space.

## 5 Conclusion

We have observed, for the first time, a strong azimuthal anisotropy in antiproton production in semicentral Au+Au collisions which is anti-correlated with the nucleon emission. The observed large anti-flow for $`\overline{p}`$ indicates that a strong annihilation process is involved in the dense nuclear matter as predicted by previous theoretical studies. The presented data have confirmed the need for a thorough investigation, both experimentally and theoretically, of antibaryon production in nucleus-nucleus interactions. Whereas the measured antiproton yields/spectra can be described within a thermal model assuming a chemical/thermal equilibration and collective expansion of the system, antiprotons exhibit a directed flow which is even stronger than expected by the models incorporating mean-field effects. A complementary measurement of the directed flow of antihyperons such as $`\overline{\mathrm{\Lambda }}`$ in the future combined with our results would provide necessary information for the decoupling of the flow contribution of primary antiprotons and that of antihyperons. Furthermore, the comparison between the directed flow behavior of these two contributions could give crucial information for understanding the observed unexpected $`\overline{\mathrm{\Lambda }}/\overline{p}`$ ratios.

## Acknowledgments

We thank the AGS staff, W. McGahern and Dr. H. Brown for excellent support and acknowledge the help of R. Hutter in all technical matters. Financial support from the US DoE, the NSF, the Canadian NSERC, and CNPq Brazil is gratefully acknowledged.


text:
# The orbital evolution of planets in disks

## 1. The model

The evolution of protoplanets can only be studied simultaneously with that of the protostellar disk in which the planets are still embedded early in their lifetime. The disk is assumed to be flat and non-self gravitating, and is modelled by the planar two-dimensional ($`r\phi `$) Navier-Stokes equations. The mutual gravitational interaction of the planets and the star, and the gravitational torques of the disk acting on the planets and the central star are included. The time dependent hydrodynamic equations are integrated by using a finite difference scheme (Kley 1998, 1999). The computations cover the radial range from 1.2 to 20 AU. The initial surface density distribution is axisymmetric and follows $`\mathrm{\Sigma }r^{1/2}`$; to speed up the computations an annular gap is imposed (Kley 1999). The material orbits the star with Keplerian speed. The planets of one Jupiter mass are initially placed at typical distances of several AU from the star. The whole system (disk, star and planets) is then evolved for several thousand orbital periods.

## 2. Results of a single Planet

The presence of the planet perturbs the axisymmetric density by generating trailing spirals (Fig. 1). In the situation where the tidal torques are greater than the internal viscous torques in the disc, and the disc response becomes non linear, an annular gap, or surface density depression, will form at the radius of the planet. The radial width of the gap is determined by the equilibrium of gravitational (gap openeing) torques and viscous (gap closing) torques. For a one Jupiter mass planet and a typical disk viscosity of $`\alpha 10^3`$ the width of the gap is about two Roche-lobe sizes of the planet.

Although the density around the planet is greatly reduced in the gap region, material from upstream may enter the Roche-lobe and eventually be accreted onto the planet (Fig. 2). Typical values for the viscosity ($`\alpha 10^3`$) and mass of the disk ($`M_{disk}=0.01M_{}`$) yield a mass accretion rate onto the planet of $`4\times 10^5M_{Jup}/yr`$ (Kley 1999).

The rate increases with larger disk viscosity and decreases when the mass of the planet grows. For very low disk viscosity and larger planetary masses the mass accumulation eventually terminates, and the maximum mass the planet may reach is about 5 Jupiter masses ($`M_{Jup}`$), see also Bryden et al. (1999), and Nelson et al. (2000).

The material in the disk acts gravitationally on the planet and disturbs the orbit. The net torque onto the planet, obtained by summation over the different annuli, is negative which leads to an inward migration on typical timescales of $`10^5yrs`$ (Nelson et al. 2000).

## 3. Evolution of two planets

As it is believed that more eccentric orbits are caused by the interaction of several objects, we have performed a run with two embedded Jupiter-type planets. Initially they were located at $`1a_J`$ and $`2a_J`$ in opposition to each other, i.e. separated by $`\mathrm{\Delta }\phi =180^{}`$. The two planets were assumed to be on circular orbits initially.

Two planets create a much more complicated pattern of wave-like disturbances in the density distribution of the disk than just one planet does. In a calculation of one planet on a fixed circular orbit, the wave pattern induced in the disk is stationary in the co-rotating frame. As seen in Fig. 3, in case of two planets (the Roche-lobes are indicated) it changes strongly with time. As both planets accrete essentially all of the mass which enters their Roche-lobes, their masses grow in time. The material located initially radially between the planets is consumed by the planets within the first few hundred orbital periods.

Finally, for the inner planet, the only gas available is that which flows through the gap created by the outer planet. Hence the mass of the inner planet grows at a smaller rate than the outer one, see Fig. 4 (bottom). At the same time, the gravitational interaction of the two planets, the star and the disk lead to changes in the orbital elements of the objects. The change in the semi-major axis of each planet is given in Fig. 4 (top). During the evolution, the fluctuations of the radial distances to the star strongly increase, indicating a growth in eccentricity of the planet.

## 4. Conclusions

By initially considering one planet on a fixed circular orbit, it was shown that even though the planet opens up an annular gap in disk it is nevertheless able to accrete more mass from its surroundings. As more massive planets induce a wider and deeper gap the mass accumulation essentially terminates, which puts the upper limit to the mass of the planet mass at about 5 to 10 $`M_{Jup}`$, in good agreement with the observations.

By considering the evolution of a system consisting of two Jupiter-type planets, we show (Kley 2000) that by mutual gravitational interaction the inward motion of the inner planet may come to a halt. As the outer planet continues to move inward and approaches the inner, the gravitational interaction between the two planets increases. The resulting configuration may be unstable, and lead to systems similar to $`\upsilon `$ And.

If the protoplanetary nebula has dissipated before the planets come very close to each other, one is left with a system of massive planets at several AU distance, similar to our own Solar System.

## References

Bryden G., Chen X., Lin D.N.C, Nelson R.P., & Papaloizou J.C.B., 1999, ApJ, 514, 344

Kley W., 1998, A&A, 338, L37

Kley W., 1999, MNRAS, 303, 696

Kley W., 2000, MNRAS, in press, astro-ph/9910155

Nelson R.P., Papaloizou J.C.B., Masset F., & Kley W., 2000, MNRAS, in press, astro-ph/9909486