text:
# COMPARATIVE COMPUTATIONAL STRENGTH OF QUANTUM ORACLES

## 1. Motivation

An important class of quantum algorithms makes use of “quantum oracles”, a device due to which the quantum circuit solving the problem becomes a function of part of the input. For such algorithms the number of invocations of quantum oracles is crucial and defines the query complexity of the problem. The most basic quantum oracle is the standard oracle whose computational strength is investigated extensively (See ).

The important result of  is that one could represent the coefficients of elements of the computational basis with polynomials of input variables when queries of the standard oracle are considered. By an argument on the increase in the degree of those polynomials appearing as coefficients for successive queries of the standard oracle combined with another argument on the minimum degree of an approximating polynomial required to yield the desired function, one could calculate a lower bound on the necessary number of queries determining the query complexity. Unfortunately the applicability of this idea is limited to the standard oracle.

Rather than arguing on the coefficients of the computational basis  argues on the basis formed by the eigenvectors of the standard oracle queries to calculate such a lower bound.  makes use of an analytic argument based on the degrees considering the coefficients of elements of the computational basis as trigonometric polynomials to obtain a result comparing the standard oracle to the phase oracle.

The approach in this article uses trigonometric polynomials of *eigenvalues of an oracle query* to represent the coefficients of states obtained by the quantum circuit to generalize the applicability of the argument used to compare two oracles in . To be able to apply an adversary argument to compare a larger class of oracles we start with a generalized definition of a quantum oracle and propose a classification of quantum oracles based on the behavior of eigenvalues and eigenvectors of an oracle query. This classification will ultimately provide the required framework for the comparison of a pair of quantum oracles in a general setting.

Such a general approach towards quantum oracles is significant because it is closer to the circuit description model than the usual black-box model, any block used repetitively in some algorithm could be regarded as an oracle query. Many problems such as the graph isomorphism problem are likely to give way to an efficient solution in the presence of a particular quantum oracle. Thus a classification of relative strength of a large class of quantum oracles could provide useful insight especially when coupled with the knowledge of the class of functions at which a quantum oracle could be constructed by a polynomial network of unitary gates.

## 2. Quantum Oracles and Quantum Algorithms with Oracle Queries

### 2.1. Introduction and definitions

Let $`𝔹=\{0,1\}`$ and $`𝔽_n^m`$ be the class of functions of the form $`f:𝔹^n𝔹^m`$. The class of all such discrete valued functions defined over a discrete set is given by $`𝔽=_{n,m>0}𝔽_n^m`$. Let the set of all unitary transformations given by a matrix of size $`2^k\times 2^k`$ be $`𝔘_k`$ and $`𝔘=_k𝔘_k`$. It is assumed we are working on a quantum system of size $`M`$ which is sufficiently large for the quantum circuits to operate on.

In the quantum computation literature when an oracle query is mentioned, it is generally implicit that this is a query of the standard oracle associated to $`f𝔽_n^m`$ of the form as in Section 2.2.1. For quantum algorithms with standard oracle queries, lower bounds for the number of queries required to calculate typical functions are established. Calculating Or and Parity of $`f𝔽_n^1`$ has query complexities $`\mathrm{\Theta }(\sqrt{2^n})`$ and $`\mathrm{\Theta }(2^n)`$ respectively (See ). These results are often attributed to an intrinsic weakness of the quantum computation model involving queries (See  pp. 271). Our conviction is that the definition of the standard oracle is far too “classical” to bring out the full potential of a quantum system and thus mainly responsible for such unsavory results. It is likely that there are other oracles of algorithmic importance encoding the information in a less trivial fashion some of which can be constructed with a polynomial network at those functions the standard oracle could not. Therefore both in an attempt to be free from the limitations the standard oracle imposes and to generalize the idea of a quantum oracle we’ll take a different approach and suggest the following definitions.

###### Definition 2.1 (Quantum oracles).

A *quantum oracle* $`Q`$ is a collection of functions
$`\{Q(n,m):𝔽_n^m𝔘|n,m^+\}`$. The class of all quantum oracles is denoted by $`𝔔`$.

Thus an oracle $`Q`$ gives rise to a unique unitary linear transformation $`Q(n,m)(f)`$ when queried at $`f𝔽_n^m`$. The functions $`Q(n,m)`$ are called *the instances* of $`Q`$. With an abuse of notation $`Q(n,m)(f)`$ is denoted by $`Q_f`$. Therefore an oracle query corresponds to a function $`Q:𝔽𝔘`$. It is assumed that one can also *inverse query* an oracle $`Q`$ at $`f`$ to obtain the unitary linear transformation $`(Q_f)^1`$.

###### Definition 2.2 (Quantum algorithm with oracle queries).

Let $`F:𝔽_n^m\times 𝔹^k𝔹^l`$. Upon input $`f𝔽_n^m`$ and $`x𝔹^k`$, the quantum circuit $`𝐔`$ with oracle queries computing $`F`$ is started with the initial state $`|\psi |x`$, is composed of finitely many unitary linear transformations: $`U_i`$, independent of $`f`$ and $`x`$, and queries and inverse queries of $`Q^{(\mathrm{})}`$ at $`f`$, independent of $`x`$, and satisfies:

$$f𝔽_n^m\mathrm{and}x𝔹^k,\underset{z𝔹^{Mkl}}{}|x|z,F(f,x)|𝐔|\psi |x|^21ϵ$$

$$f𝔽_n^m\mathrm{and}x𝔹^k,\underset{w𝔹^{Mk}}{}|x|w|𝐔|\psi |x|^2=1$$

where $`ϵ`$ is a fixed number smaller than $`\frac{1}{2}`$. Such a quantum circuit $`𝐔`$ with queries implements a quantum algorithm with queries computing $`F`$.

Note that with this definition the actual input is encoded both in the function $`f`$ and the state $`|x`$.

###### Definition 2.3 (An oracle approximating another oracle at functions in $`𝔽_n^m`$).

Given two oracles $`Q^{(1)}`$, $`Q^{(2)}`$ to be queried at the same $`f𝔽_n^m`$, if there exists a quantum circuit $`𝐔`$ involving $`N`$ queries (and inverse queries) of $`Q^{(1)}`$ such that $`Q^{(2)}𝐔<ϵ`$ independently of $`f𝔽_n^m`$ then $`Q^{(1)}`$ is said to approximate $`Q^{(2)}`$ up to $`ϵ`$ with $`N`$ queries at functions in $`𝔽_n^m`$. If there exists such an $`N`$ for which $`ϵ`$ could be taken arbitrarily small, then $`Q^{(1)}`$ is said to simulate $`Q^{(2)}`$ with $`N`$ queries at functions in $`𝔽_n^m`$.

###### Definition 2.4 (Efficient approximation and simulation between oracles).

For arbitrary oracles, $`Q^{(1)}`$ is said to *efficiently approximate* $`Q^{(2)}`$ up to $`\delta `$ if it could approximate $`Q^{(2)}`$ up to $`\delta `$ with $`O(poly(n+m))`$ queries at functions in $`𝔽_n^m`$ for any choice of $`n`$ and $`m`$. Efficient simulation is defined analogously.

If $`Q^{(1)}`$ can approximate $`Q^{(2)}`$ efficiently but not the other way around this could imply existence of a function whose query complexity would be lower if queries of $`Q^{(1)}`$ could be employed. Moreover $`Q^{(1)}`$ would be at least as powerful as $`Q^{(2)}`$ for any purpose of computation.

### 2.2. Examples of quantum oracles

#### 2.2.1. The standard oracle

The standard oracle $`Q^{std}`$ is the oracle whose query at $`f𝔽_n^m`$ gives rise to $`Q_f^{std}𝔘_{n+m}`$ with the following action on the computational basis of a quantum system of $`n+m`$ qubits:

$$Q_f^{std}:|x|y|x|yf(x)$$
(2.1)
where $``$ denotes summation modulo $`2^m`$.

For $`0s2^m1`$ let

$$|\psi _s=\frac{1}{2^{m/2}}\underset{k=0}{\overset{2^m1}{}}e^{\frac{2\pi isk}{2^m}}|k$$
(2.2)
Then it is easy to verify for each $`0x2^n1`$ and $`0s2^m1`$

$`Q_f^{std}(|x|\psi _s)`$ $`=|x({\displaystyle \frac{1}{2^{m/2}}}{\displaystyle \underset{k=0}{\overset{2^m1}{}}}e^{\frac{2\pi isk}{2^m}}|kf(x))`$
$`=|x({\displaystyle \frac{1}{2^{m/2}}}{\displaystyle \underset{k=0}{\overset{2^m1}{}}}e^{\frac{2\pi is(kf(x))}{2^m}}|k)`$
$`=e^{\frac{2\pi isf(x)}{2^m}}|x|\psi _s`$ (2.3)
#### 2.2.2. The complex phase oracle

The complex phase oracle $`Q^{cp_d}`$ of degree $`d`$ is the oracle whose query at $`f𝔽_n^m`$ gives rise to $`Q_f^{cp_d}𝔘_n`$ with the following action on the computational basis of a quantum system of $`n`$ qubits:

$$Q_f^{cp_d}:|xe^{\frac{2\pi idf(x)}{2^m}}|x$$
(2.4)
Therefore the query $`Q_f^{cp_d}`$ encodes the information purely into the phase of the eigenvalue associated to each computational basis state.

#### 2.2.3. The minimal oracle

The minimal oracle $`Q^{min}`$ is the oracle whose query at $`f𝔽_n^m`$ yields the identity operator in $`𝔘_n`$ unless $`n=m`$ and $`f`$ is a permutation on the set $`𝔹^n`$. In that case a query of $`Q^{min}`$ at $`f`$ gives rise to $`Q_f^{min}𝔘_n`$ with the following action on the computational basis of a quantum system of $`n`$ qubits:

$$Q_f^{min}:|x|f(x)$$
(2.5)
The eigenvectors of such an oracle query depends on the orbits of the permutation $`f`$. Let the permutation $`f𝔽_n^n`$ have $`𝔬`$ orbits, $`r_{\mathrm{}}`$ be the length of the $`\mathrm{}`$-th orbit and $`x_{\mathrm{}}`$ be the smallest element of the $`\mathrm{}`$-th orbit. For all $`1\mathrm{}𝔬`$ and $`0s_{\mathrm{}}r_{\mathrm{}}1`$ the following vectors are easily observed to be the eigenvectors:

$$|\psi _{\mathrm{},s_{\mathrm{}}}=\frac{1}{\sqrt{r_{\mathrm{}}}}\underset{k=0}{\overset{r_{\mathrm{}}1}{}}e^{\frac{2\pi is_{\mathrm{}}k}{r_{\mathrm{}}}}|f^k(x_{\mathrm{}})\mathrm{associated}\mathrm{to}\mathrm{eigenvalue}e^{\frac{2\pi is_{\mathrm{}}}{r_{\mathrm{}}}}$$
(2.6)
The minimal oracle has immense algorithmic importance. As  noted, the minimal oracle could give an efficient solution to a restricted version of a graph isomorphism problem. Order finding algorithm of  could also be considered to employ minimal oracle queries.

It is a known result that although $`Q^{min}`$ could simulate $`Q^{std}`$ with two queries at permutations in $`𝔽_n^n`$, to simulate $`Q^{min}`$ via $`Q^{std}`$ at permutations in $`𝔽_n^n`$, $`O(\sqrt{2^n})`$ oracle queries are necessary (See ).

## 3. A Classification of Quantum Oracles

We shall present a classification of oracles based on the eigenvectors and eigenvalues of their queries.

Assume we are provided with an oracle $`Q`$. Each instance $`Q(n,m)`$ could be lifted so that

$$Q(n,m):𝔽_n^m𝔘_r$$
(3.1)
for some sufficiently large $`r`$ by redefining $`Q(n,m)(f)`$ to be $`(Q(n,m)(f)I)𝔘_r`$ whenever $`Q(n,m)(f)𝔘_s`$ and $`s<r`$ originally. Therefore each instance of the oracle $`Q`$ is assumed to be in this form where $`rn`$ is the smallest such integer to allow such a lift.

The instance $`Q(n,m):𝔽_n^m𝔘_r`$ with $`r=n+k`$ is called *nonentangled* if at any choice of $`f𝔽_n^m`$ there exists an orthonormal basis $`\{|\alpha _x,0x2^n1\}`$ for $`(^2)^n`$ such that $`Q(n,m)(f)`$ acts stably on the following subspaces:

$$W_x=|\alpha _x|0,|\alpha _x|1,\mathrm{},|\alpha _x|2^k1$$
(3.2)
In other words it is required there exist such subspaces $`W_x`$ possibly depending on the choice of $`f𝔽_n^m`$ and satisfying $`Q_f(W_x)=W_x`$.

Given such a nonentangled instance $`Q(n,m)`$, let the pair $`(x,i)`$ take values in $`\{0\mathrm{}2^n1\}\times \{0\mathrm{}2^k1\}`$. At any choice of $`f𝔽_n^m`$ let $`|\beta _{x,i}`$ be the vectors in $`(^2)^k`$ such that for each $`(x,i)`$

$$Q(n,m)(f)(|\alpha _x|\beta _{x,i})=e^{i\theta _{x,i}(f)}|\alpha _x|\beta _{x,i}$$
(3.3)
Then the state $`|\psi _{x,i}=|\alpha _x|\beta _{x,i}`$ is called the $`(x,i)`$-th eigenvector of $`Q_f`$.

The nonentangled instance $`Q(n,m)`$ is called *basic* if for each $`(x,i)`$ there exists a real-valued function $`g_{x,i}`$ independent of the choice of $`f𝔽_n^m`$ such that after a renumbering of eigenvectors if necessary, the phase of the $`(x,i)`$-th eigenvalue could be expressed entirely as a function of $`f(x)`$: $`\theta _{x,i}(f)=g_{x,i}(f(x))`$. This definition does not exclude the possibility of the eigenvectors of $`Q(n,m)(f)`$ being dependent on $`f`$. If the eigenvectors of a basic instance $`Q(n,m)`$ could further be chosen independently of $`f𝔽_n^m`$ such an instance is called *simple*.

An oracle is called to be of any of these particular types if all its instances are so up to a base change. All the previous examples of oracles are nonentangled. The standard oracle and the complex phase oracle are simple. For the minimal oracle, one may renumber the eigenvectors identifying the index $`(\mathrm{},s_{\mathrm{}})`$ with $`f^s_{\mathrm{}}(x_{\mathrm{}})`$ and observe it is not basic because the knowledge of $`f(x)`$ is not sufficient to determine the length of the orbit containing $`x`$ and any other renumbering would suffer from a similar problem.

Many quantum algorithms with queries involve estimating one phase $`\theta _{x,i}(f)`$ using which calculation of $`F(f,x)`$ could be performed efficiently on a classical computer.

## 4. On the Class of Nonentangled Oracles Efficiently Simulated by the Standard Oracle

###### Definition 4.1 (Locally basic oracles).

A nonentangled oracle $`Q`$ is called *locally basic*, if at any instance $`(n,m)`$ there exists a function $`G𝔽`$ and a quantum circuit $`𝐔`$ consisting of $`O(poly(n+m))`$ standard oracle queries satisfying $`𝐔:|\psi _{x,i}|0\mathrm{}0|\psi _{x,i}|G(f,x,i)`$ where $`|\psi _{x,i}`$ is the $`(x,i)`$-th eigenvector of a query of $`Q`$, such that each $`\theta _{x,i}(f)`$, the phase of its $`(x,i)`$-th eigenvalue, is entirely a function of $`G(f,x,i)`$.

Clearly any basic oracle is locally basic. Any locally basic oracle could be efficiently simulated by the standard oracle since there exists a quantum circuit involving polynomially many standard oracle queries mapping:

$$|\psi _{x,i}|0\mathrm{}0\underset{𝐔}{}|\psi _{x,i}|G(f,x,i)e^{i\theta _{x,i}(f)}|\psi _{x,i}|G(f,x,i)\underset{𝐔^1}{}e^{i\theta _{x,i}(f)}|\psi _{x,i}|0\mathrm{}0(x,i)$$
(4.1)
###### Example 4.2.

$`Q^{std}`$ could efficiently simulate $`Q^{min}`$ at permutations in $`𝔽_n^n`$ whose every orbit has $`O(poly(n))`$ length.

Consider the set of permutations in the classes of functions $`𝔽_n^n`$ whose every orbit has length at most $`p(n)`$, for some polynomial $`p(x)`$. At such permutations, the minimal oracle behaves like a locally basic oracle. Consider the following quantum circuit $`𝐕`$:

1. Apply $`Q^{std}`$ $`p(n)`$ times to obtain $`|x|0\mathrm{}0|x|f(x)|f^2(x)\mathrm{}|f^{p(n)}(x)|0\mathrm{}0`$.
2. By going through the list of elements calculate the length of the orbit (guaranteed to be smaller than $`p(n)`$ by assumption), $`r`$, and the number of iterations of $`f`$ necessary to reach $`x`$ starting from the smallest element in the orbit, $`s`$:
$`|x|f(x)|f^2(x)\mathrm{}|f^{p(n)}(x)|0\mathrm{}0|x|f(x)|f^2(x)\mathrm{}|f^{p(n)}(x)|r|s`$.
3. Apply the step $`(1)`$ in reverse to obtain $`|x|0\mathrm{}0|r|s`$.

A similar argument reveals the existence of the quantum circuit $`𝐖`$, involving polynomially many queries of the standard oracle mapping each $`|f^s_{\mathrm{}}(x_{\mathrm{}})|0\mathrm{}0`$ to $`|\psi _{\mathrm{},s_{\mathrm{}}}|0\mathrm{}0`$. Thus the following algorithm involves polynomially many queries of the standard oracle:

$`|\psi _{\mathrm{},s_{\mathrm{}}}|0\mathrm{}0\underset{𝐖^1}{}|f^s_{\mathrm{}}(x_{\mathrm{}})|0\mathrm{}0\underset{𝐕}{}|f^s_{\mathrm{}}(x_{\mathrm{}})|0\mathrm{}0|r_{\mathrm{}}|s_{\mathrm{}}\underset{𝐖}{}`$
$`|\psi _{\mathrm{},s_{\mathrm{}}}|0\mathrm{}0|r_{\mathrm{}}|s_{\mathrm{}}\underset{\text{swap}}{}|\psi _{\mathrm{},s_{\mathrm{}}}|r_{\mathrm{}}|s_{\mathrm{}}|0\mathrm{}0(\mathrm{},s_{\mathrm{}})`$
Because each eigenvalue of a minimal oracle query is entirely a function of $`r_{\mathrm{}}`$ and $`s_{\mathrm{}}`$, one can repeat the argument in (4.1) to obtain the result.

However due to  the standard oracle could not efficiently simulate the minimal oracle at all the permutations and thus could not be locally basic. This fact is reminiscent of  when the eigenvalues of the minimal oracle is considered.

Conversely one might wonder if an oracle $`Q`$ that is efficiently simulated by the standard oracle has to be locally basic. Example 5.1 comparing the standard oracle with a generic local phase oracle implies that a direct approach to this question, trying to construct an algorithm with polynomially many queries of $`Q`$ mapping $`|\psi _{x,i}|0\mathrm{}0|\psi _{x,i}|G(f,x,i)(x,i)`$, is bound to fail for a large class of encodings of $`G(f,x,i)`$ into the phase of the eigenvalues. Thus it is conceivable that locally basic oracles describe a strictly smaller class.

## 5. A Comparison of Nonentangled Quantum Oracles

We shall assume we are given nonentangled oracles $`Q^{(1)},Q^{(2)}`$ to compare in terms of efficient approximation and therefore consider an arbitrary instance $`(n,m)`$ of $`Q^{(1)}`$ and $`Q^{(2)}`$.

As earlier assume we are working on a quantum system of sufficiently large size $`M`$ with an ordering on qubits. Without loss of generality we also assume oracle queries are always acting on the first qubits in this order by modifying all constant unitary transformations used in oracle approximation to account for the base change. Therefore to decide the action of an oracle query at functions in $`𝔽_n^m`$ on this quantum system, we will assume the instance $`(n,m)`$ of both oracles are given in the following form after a lift as in Section 3:

$$Q^{(\mathrm{})}:𝔽_n^m𝔘_M\mathrm{}=1,2$$
(5.1)
In view of the earlier requirement in Section 3, $`M`$ not being minimal does not affect the properties satisfied but only changes the multiplicity of eigenvalues.

Our aim is to put a lower bound on the $`Q^{(1)}`$ queries required to approximate $`Q^{(2)}`$ up to $`\delta `$ at functions in $`𝔽_n^m`$ using a classical adversary argument and show that this lower bound grows faster than any polynomial in $`n+m`$. Based on this framework of trigonometric polynomials of the eigenvalues of a query one may also make use of a quantum adversary argument in the sense of  to compare nonentangled oracles.

To conclude more than $`N`$ queries of $`Q^{(1)}`$ is necessary to approximate $`Q^{(2)}`$ up to $`\delta `$ at functions in $`𝔽_n^m`$ it is sufficient to show the existence of $`f𝔽_n^m`$ and an eigenvector $`|\psi _{x,i}^{(2)}`$ of $`Q_f^{(2)}`$ for some $`(x,i)\{0\mathrm{}2^n1\}\times \{0\mathrm{}2^{Mn}1\}`$ such that

$$Q_f^{(2)}|\psi _{x,i}^{(2)}U_{(N+1)}(Q_f^{(1)})^{p_N}U_N(Q_f^{(1)})^{p_{N1}}\mathrm{}(Q_f^{(1)})^{p_1}U_1|\psi _{x,i}^{(2)}>\delta $$
(5.2)
for any choice of $`\{U_k𝔘_M|1kN+1\}`$ and $`\{p_k=\pm 1|1kN\}`$.

It is not necessary in general that an eigenvector satisfying (5.2) exists even if approximation with $`N`$ queries up to $`\delta `$ is impossible. However this is necessary for impossibility of simulation with $`N`$ queries, i.e. if for all eigenvectors of $`Q_f^{(2)}`$ the following equation is satisfied:

$$U_{(N+1)}(Q_f^{(1)})^{p_N}U_N(Q_f^{(1)})^{p_{N1}}\mathrm{}(Q_f^{(1)})^{p_1}U_1|\psi _{x,i}^{(2)}=Q_f^{(2)}|\psi _{x,i}^{(2)}$$
(5.3)
for a particular choice of $`\{U_k𝔘_M|1kN+1\}`$ and $`\{p_k=\pm 1|1kN\}`$ then by linearity the same would clearly hold for any possible initial state. Therefore one could immediately deduce that $`Q^{(2)}`$ could be simulated with at most $`N`$ queries of $`Q^{(1)}`$ at functions in $`𝔽_n^m`$.

###### Definition 5.1 (Trigonometric polynomial).

A function $`T:^D`$ of the form:

$$T(\varphi _1,\mathrm{},\varphi _D)=\underset{j=1}{\overset{K}{}}c_je^{i(n_{j,1}\varphi _1+\mathrm{}+n_{j,D}\varphi _D)}\mathrm{where}c_j,n_{j,k}\mathrm{and}K<\mathrm{}$$

is called an *$`D`$-variate trigonometric polynomial* with *degree*

$$\mathrm{𝐝𝐞𝐠}T(\varphi _1,\mathrm{},\varphi _D)=\underset{j}{\mathrm{max}}(|n_{j,1}|+\mathrm{}|n_{j,D}|)$$

The following lemma is a generalized yet simpler variant of the one in  but considered in the framework of eigenvectors and eigenvalues. The approach in  is based on degree of ordinary polynomials but its applicability is limited to the standard oracle.

###### Lemma 5.2.

Let $`Q(n,m)`$ be a nonentangled instance with $`\theta _{x,i}`$ corresponding to the phase of the $`(x,i)`$-th eigenvalue and $`|\psi `$ be the state of the quantum system represented with respect to a particular choice of orthonormal basis $`\{|\alpha _j|0j2^M1\}`$ as follows:

$$|\psi =\underset{j=0}{\overset{2^M1}{}}T_j(𝚯(f))|\alpha _j\mathrm{where}𝚯(f)=\{\theta _{x,i}(f)|0x2^n1,0i2^{Mn}1\}$$

where each $`T_j(\varphi _{0,0},\mathrm{},\varphi _{x,i},\mathrm{}\varphi _{2^n1,2^{Mn}1})`$ is a trigonometric polynomial. Let the degree $`\mathrm{𝐝𝐞𝐠}|\psi =\mathrm{max}_j(\mathrm{𝐝𝐞𝐠}T_j)`$. Then for any unitary operator $`U`$ independent of $`f`$, $`\mathrm{𝐝𝐞𝐠}(U|\psi )\mathrm{𝐝𝐞𝐠}|\psi `$ and $`\mathrm{𝐝𝐞𝐠}((Q_f)^{\pm 1}|\psi )(\mathrm{𝐝𝐞𝐠}|\psi )+1`$ for $`f𝔽_n^m`$.

###### Proof.

$`\mathrm{𝐝𝐞𝐠}(U|\psi )\mathrm{𝐝𝐞𝐠}|\psi `$: Clear considering how a unitary transformation acts on the coefficients and the definition of trigonometric polynomial. This also implies the definition of the degree does not depend on the choice of basis.

$`\mathrm{𝐝𝐞𝐠}((Q_f)^{\pm 1}|\psi )(\mathrm{𝐝𝐞𝐠}|\psi )+1`$: It is clear if $`\{|\alpha _j|1j2^M\}`$ are the eigenvectors of $`Q_f`$. Otherwise use the previous result. ∎

Note that each trigonometric polynomial corresponding to the coefficient of a basis element following the application of a number of unitary transformations some of which are oracle queries to a unit vector has to be smaller than or equal to $`1`$ in absolute value.

###### Lemma 5.3.

Given two nonentangled oracles $`Q^{(1)}`$, $`Q^{(2)}`$ with $`\{U_k𝔘_M|1kN+1\}`$ and $`\{p_k=\pm 1|1kN\}`$ then $`U_{\left(N+1\right)}\left(Q_f^{\left(1\right)}\right)^{p_N}U_N\left(Q_f^{\left(1\right)}\right)^{p_{N1}}\mathrm{}\left(Q_f^{\left(1\right)}\right)^{p_1}U_1`$  could approximate $`Q_f^{(2)}`$ at most up to $`\mathrm{max}_{x,i}\left(\left|e^{i\theta _{x,i}^{\left(2\right)}\left(f\right)}T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f\right)\right)\right|\right)`$  at a function $`f𝔽_n^m`$ where

* $`e^{i\theta _{x,i}^{(2)}(f)}`$ denotes the $`(x,i)`$-th eigenvalue of the oracle query $`Q_f^{(2)}`$ corresponding to the eigenvector $`|\psi _{x,i}^{(2)}`$, also a function of $`f`$.
* $`T_{x^{},i^{}}^{x,i}(𝚯^{(1)}(f))`$ denotes the trigonometric polynomial (of the phases of the eigenvalues of the oracle query $`Q_f^{(1)}`$) corresponding to the scalar projection of the vector
$`U_{\left(N+1\right)}\left(Q_f^{\left(1\right)}\right)^{p_N}U_N\left(Q_f^{\left(1\right)}\right)^{p_{N1}}\mathrm{}\left(Q_f^{\left(1\right)}\right)^{p_1}U_1|\psi _{x,i}^{\left(2\right)}`$  over $`|\psi _{x^{},i^{}}^{(2)}`$.

Moreover each $`T_{x^{},i^{}}^{x,i}(𝚯^{(1)}(f))`$ has degree at most $`N`$.

###### Proof.

As stated, given $`\{U_k𝔘_M|1kN+1\}`$ and $`\{p_k=\pm 1|1kN\}`$ let

$$U_{(N+1)}(Q_f^{(1)})^{p_N}U_N(Q_f^{(1)})^{p_{N1}}\mathrm{}(Q_f^{(1)})^{p_1}U_1|\psi _{x,i}^{(2)}=\underset{x^{}=0}{\overset{2^n1}{}}\underset{i^{}=0}{\overset{2^{Mn}1}{}}T_{x^{},i^{}}^{x,i}(𝚯^{(1)}(f))|\psi _{x^{},i^{}}^{(2)}$$
(5.4)
If vectors are represented with respect to the basis formed by the eigenvectors of the oracle query $`Q_f^{(2)}`$, observing only the difference in the coefficient of the eigenvector $`|\psi _{x,i}^{(2)}`$ gives

$$Q_f^{(2)}|\psi _{x,i}^{(2)}U_{(N+1)}(Q_f^{(1)})^{p_N}U_N(Q_f^{(1)})^{p_{N1}}\mathrm{}(Q_f^{(1)})^{p_1}U_1|\psi _{x,i}^{(2)}|e^{i\theta _{x,i}^{(2)}(f)}T_{x,i}^{x,i}(𝚯^{(1)}(f))|$$
(5.5)
As all eigenvectors $`|\psi _{x,i}^{(2)}`$ of $`Q_f^{(2)}`$ are considered, this yields the stated result at every $`f𝔽_n^m`$.

Furthermore as a consequence of Lemma 5.2 each of the trigonometric polynomials
$`T_{x^{},i^{}}^{x,i}(𝚯^{(1)}(f))`$ has degree at most $`N`$. ∎

Therefore demonstration of (5.2) reduces to finding a lower bound for $`\left|e^{i\theta _{x,i}^{\left(2\right)}\left(f\right)}T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f\right)\right)\right|`$  for some $`(x,i)`$ and $`f𝔽_n^m`$. Making use of this fact one could determine the impossibility of efficient approximation between two oracles in a much more general sense.

###### Theorem 5.4.

Given two nonentangled oracles $`Q^{(1)}`$, $`Q^{(2)}`$ with $`\{U_k𝔘_M|1kN+1\}`$ and $`\{p_k=\pm 1|1kN\}`$ then $`U_{\left(N+1\right)}\left(Q^{\left(1\right)}\right)^{p_N}U_N\left(Q^{\left(1\right)}\right)^{p_{N1}}\mathrm{}\left(Q^{\left(1\right)}\right)^{p_1}U_1`$  could approximate $`Q^{(2)}`$ at functions in $`𝔽_n^m`$ at most up to

$$\frac{1}{2}\left[\underset{f_1,f_2𝔽_n^m}{\mathrm{max}}\left\{\underset{x,i}{\mathrm{max}}\left(\left|\left|e^{i\theta _{x,i}^{\left(2\right)}\left(f_1\right)}T_{x,i}^{x,i}\left(𝚯^{\left(2\right)}\left(f_2\right)\right)\right|\left|T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_1\right)\right)T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_2\right)\right)\right|\right|\right)\right\}\right]$$

where

* $`e^{i\theta _{x,i}^{(2)}(f_{\dot{ȷ}})}`$ denotes the $`(x,i)`$-th eigenvalue of the oracle query $`Q_{f_{\dot{ȷ}}}^{(2)}`$.
* $`T_{x^{},i^{}}^{x,i}(𝚯^{(1)}(f_{\dot{ȷ}}))`$ denotes the trigonometric polynomial (of the phases of the eigenvalues of the oracle query $`Q_{f_{\dot{ȷ}}}^{(1)}`$) corresponding to the scalar projection of the vector
$`U_{\left(N+1\right)}\left(Q_{f_{\dot{ȷ}}}^{\left(1\right)}\right)^{p_N}U_N\left(Q_{f_{\dot{ȷ}}}^{\left(1\right)}\right)^{p_{N1}}\mathrm{}\left(Q_{f_{\dot{ȷ}}}^{\left(1\right)}\right)^{p_1}U_1|\psi _{x,i}^{\left(2\right)}`$  over $`|\psi _{x^{},i^{}}^{(2)}`$, the $`(x^{},i^{})`$-th eigenvector of $`Q_{f_1}^{(2)}`$, therefore has degree at most $`N`$.
* $`T_{x^{},i^{}}^{x,i}(𝚯^{(2)}(f_{\dot{ȷ}}))`$ denotes the trigonometric polynomial (of the phases of the eigenvalues of the oracle query $`Q_{f_{\dot{ȷ}}}^{(2)}`$) corresponding to the scalar projection of the vector $`Q_{f_{\dot{ȷ}}}^{(2)}|\psi _{x,i}^{(2)}`$ over $`|\psi _{x^{},i^{}}^{(2)}`$, the $`(x^{},i^{})`$-th eigenvector of $`Q_{f_1}^{(2)}`$, therefore has degree at most $`1`$.

Moreover if $`Q^{(2)}`$ is a simple oracle then $`T_{x,i}^{x,i}(𝚯^{(2)}(f_2))=e^{i\theta _{x,i}^{(2)}(f_2)}`$.

###### Proof.

Assume the contrary and consider $`f_1,f_2𝔽_n^m`$ and $`(x,i)`$ for which

$$2\delta =(||e^{i\theta _{x,i}^{(2)}(f_1)}T_{x,i}^{x,i}(𝚯^{(2)}(f_2))||T_{x,i}^{x,i}(𝚯^{(1)}(f_1))T_{x,i}^{x,i}(𝚯^{(1)}(f_2))||)$$
(5.6)
is maximized.

The Triangle Inequality gives:

$`|e^{i\theta _{x,i}^{(2)}(f_1)}T_{x,i}^{x,i}(𝚯^{(2)}(f_2))+T_{x,i}^{x,i}(𝚯^{(1)}(f_2))T_{x,i}^{x,i}(𝚯^{(1)}(f_1))|`$
$`||e^{i\theta _{x,i}^{(2)}(f_1)}T_{x,i}^{x,i}(𝚯^{(2)}(f_2))||T_{x,i}^{x,i}(𝚯^{(1)}(f_2))T_{x,i}^{x,i}(𝚯^{(1)}(f_1))||=2\delta `$ (5.7)
By original assumption $`\left|T_{x,i}^{x,i}\left(𝚯^{\left(2\right)}\left(f_2\right)\right)T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_2\right)\right)\right|\delta `$ , otherwise we get a contradiction due to the same argument in Lemma 5.3, because the error in approximation has to be at least as large as the difference in the coefficient of $`|\psi _{x,i}^{(2)}`$. Thus another application of the Triangle Inequality gives:

$`\left|e^{i\theta _{x,i}^{\left(2\right)}\left(f_1\right)}T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_1\right)\right)\right|=`$
$`\left|e^{i\theta _{x,i}^{\left(2\right)}\left(f_1\right)}T_{x,i}^{x,i}\left(𝚯^{\left(2\right)}\left(f_2\right)\right)+T_{x,i}^{x,i}\left(𝚯^{\left(2\right)}\left(f_2\right)\right)T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_2\right)\right)+T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_2\right)\right)T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_1\right)\right)\right|`$
$`\left|\left|e^{i\theta _{x,i}^{\left(2\right)}\left(f_1\right)}T_{x,i}^{x,i}\left(𝚯^{\left(2\right)}\left(f_2\right)\right)+T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_2\right)\right)T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_1\right)\right)\right|\left|T_{x,i}^{x,i}\left(𝚯^{\left(2\right)}\left(f_2\right)\right)T_{x,i}^{x,i}\left(𝚯^{\left(1\right)}\left(f_2\right)\right)\right|\right|`$
$`\left|2\delta \delta \right|=\delta `$ (5.8)
which gives rise to another contradiction due to Lemma 5.3. Therefore the error should be at least as large as $`\delta `$ at either $`f_1`$ or $`f_2`$ which implies the result. Moreover the degree of the trigonometric polynomials should be as stated due to Lemma 5.2.

By definition of the simple oracle, if $`Q^{(2)}`$ is a simple oracle then the eigenvectors of $`Q_f^{(2)}`$ will be independent of $`f`$. Therefore $`T_{x,i}^{x,i}(𝚯^{(2)}(f_2))=e^{i\theta _{x,i}^{(2)}(f_2)}`$. ∎

Thus the argument is based on the fact that the large amount of change in the eigenvalues of $`Q_f^{(2)}`$ as $`f𝔽_n^m`$ is altered could not be accommodated by the relatively small change in the trigonometric polynomial which is a function of the phases of the eigenvalues of $`Q_f^{(1)}`$ since the change in these eigenvalues is also small. This imposes a lower bound on the number of $`Q_f^{(1)}`$ oracle queries we should perform to approximate $`Q_f^{(2)}`$ at functions in $`𝔽_n^m`$.

The following lemma, also made use of by , is helpful considered in conjunction with the Theorem 5.4.

###### Lemma 5.5.

Let $`T(\theta )`$ be a trigonometric polynomial of a single variable $`\theta `$ satisfying $`|T(\theta )|1`$ for any value of $`\theta `$. If $`|T(\theta _1)T(\theta _2)|=\lambda `$ then $`\frac{\lambda }{|\theta _1\theta _2|}(\mathrm{𝐝𝐞𝐠}T(\theta ))`$.

###### Proof.

The Mean Value Theorem yields:

$$\lambda =|T(\theta _1)T(\theta _2)|=|T^{}(\theta ^{})||\theta _1\theta _2|\mathrm{for}\mathrm{some}\theta ^{}[\theta _1,\theta _2]\mathrm{assuming}\theta _1<\theta _2$$
(5.9)
Combining with Bernstein’s Inequality (See ) one obtains:

$$|T^{}(\theta ^{})|(\mathrm{𝐝𝐞𝐠}T(\theta ))\underset{\pi \theta \pi }{sup}|T(\theta )|\mathrm{𝐝𝐞𝐠}T(\theta )$$

### 5.1. Example: the comparison of standard oracle vs. a generic local phase oracle

Consider a generic local phase oracle $`Q^{(1)}`$ whose instance $`(n,m)`$ has the following action on the computational basis of a quantum system of $`n`$ qubits: $`|xe^{i_yc_{x,y}\left(g\left(\frac{f\left(y\right)}{2^m}\right)\right)}|x`$  where $`g`$ is a real valued differentiable function on $`[0,1]`$ with $`sup_{t[0,1]}|g^{}(t)|B`$, each $`c_{x,y}`$, $`\mathrm{max}_{x,y}|c_{x,y}|C`$ for some constant $`C`$ and $`c_{x,y}=0\mathrm{whenever}2^np(n)>|yx|>p(n)`$ for some polynomial $`p(x)`$ ($`g`$, $`C`$ and $`p`$ are independent of the instance $`(n,m)`$). Any such oracle is locally basic and thus is efficiently simulated by the standard oracle.

Set $`Q^{(2)}=Q^{std}`$ for consistency with the earlier notation. Assume $`Q^{(1)}`$ can approximate $`Q^{(2)}`$ up to $`\delta `$ with $`N`$ queries at functions in $`𝔽_n^m`$.

Let $`f_1,f_2𝔽_n^m`$ given by:

$$f_1(x)=\{\begin{array}{cc}2^{m1}\hfill & \text{if }x=0\hfill \\ 0\hfill & \text{if }x0\hfill \end{array}f_2(x)=\{\begin{array}{cc}2^{m1}+1\hfill & \text{if }x=0\hfill \\ 0\hfill & \text{if }x0\hfill \end{array}$$
(5.10)
Set the initial state of the quantum system of size $`M`$ to be

$$|0^n(\frac{1}{2^{m/2}}\underset{k=0}{\overset{2^m1}{}}e^{\frac{2\pi i2^{m1}k}{2^m}}|k)|0^{Mnm}=|0^n|\psi _{2^{m1}}|0^{Mnm}$$
(5.11)
with the same notation as in Section 2.2.1.

An application of the specific form of Theorem 5.4 for the simple oracle $`Q^{(2)}`$, considering the action of the query $`Q_f^{(2)}I`$ on this initial state together with the earlier eigenvalue calculation yields:

$`|e^{i\theta _{0,2^{m1}}^{(2)}(f_1)}e^{i\theta _{0,2^{m1}}^{(2)}(f_2)}|`$ $`=|e^{\frac{2\pi i2^{m1}2^{m1}}{2^m}}e^{\frac{2\pi i2^{m1}(2^{m1}+1)}{2^m}}|`$
$`=|e^{\pi i2^{m1}}e^{\pi i(2^{m1}+1)}|=|1e^{\pi i}|=2`$ (5.12)
Thus in view of Theorem 5.4 we obtain:

$`2\delta `$ $`|2|T_{0,2^{m1},0}^{0,2^{m1},0}(𝚯^{(1)}(f_1))T_{0,2^{m1},0}^{0,2^{m1},0}(𝚯^{(1)}(f_2))||`$ (5.13)
$`22\delta `$ $`|T_{0,2^{m1},0}^{0,2^{m1},0}(𝚯^{(1)}(f_1))T_{0,2^{m1},0}^{0,2^{m1},0}(𝚯^{(1)}(f_2))|`$ (5.14)
$`T_{0,2^{m1},0}^{0,2^{m1},0}\left(𝚯^{\left(1\right)}\left(f\right)\right)`$  is a trigonometric polynomial with degree at most $`N`$ in the sense of Definition 5.1. It could also be regarded as a trigonometric polynomial $`T(\theta )`$ of a single variable $`\theta =g\left(\frac{f\left(0\right)}{2^m}\right)`$  with degree at most $`C\times N`$ (considering a real number as the degree of this trigonometric polynomial in the obvious sense does not affect the applicability of Lemma 5.5). Hence an application of Lemma 5.5 on $`T(\theta )`$ by letting $`\theta _1=g\left(\frac{f_1\left(0\right)}{2^m}\right)`$ , $`\theta _2=g\left(\frac{f_2\left(0\right)}{2^m}\right)`$  combined with the Mean Value Theorem yields:

$$\frac{22\delta }{B\frac{1}{2^m}}=\frac{2^{m+1}(1\delta )}{B}\mathrm{𝐝𝐞𝐠}T(\theta )C\times N$$
(5.15)
Thus approximating $`Q^{std}`$ up to $`\delta `$ requires at least $`\frac{2^{m+1}\left(1\delta \right)}{B.C}`$  queries of $`Q^{(1)}`$ at functions in $`𝔽_n^m`$ and therefore could not be efficient for such a generic local phase oracle. This result is analogous to that of  but a generic local phase oracle acts distinctly from the phase oracle in .

The following elementary lemma is useful for combining results regarding efficient simulation and approximation.

###### Lemma 5.6.

For arbitrary oracles $`Q^{(1)}`$, $`Q^{(2)}`$ and $`Q^{(3)}`$, if $`Q^{(1)}`$ can efficiently simulate $`Q^{(2)}`$ and $`Q^{(2)}`$ can efficiently approximate $`Q^{(3)}`$ up to $`\delta `$ then $`Q^{(1)}`$ can efficiently approximate $`Q^{(3)}`$ up to $`\delta `$. In particular if $`Q^{(1)}`$ can efficiently simulate $`Q^{(2)}`$ and $`Q^{(2)}`$ can efficiently simulate $`Q^{(3)}`$ then $`Q^{(1)}`$ can efficiently simulate $`Q^{(3)}`$.

As a consequence to this lemma the obtained result coupled with that of  yields:

* $`Q^{cp_d}`$ cannot efficiently simulate $`Q^{min}`$ for any degree $`d`$.
* $`Q^{min}`$ can efficiently simulate $`Q^{cp_d}`$ for any $`d`$ at permutations.

Thus $`Q^{min}Q^{std}Q^{cp_d}`$<sup>1</sup><sup>1</sup>1at permutations. where “$``$” denotes efficient simulation in single direction.

## 6. Acknowledgements

The author wishes to thank Rocco Servedio, Dave Bayer, Henryk Woźniakowski and Joseph Traub for their support and fruitful discussions and Jeff Phan for new suggestions and his help in correcting many inconsistencies.


format: text

text:
# Genetic Paralog Analysis and Simulations

## 1 Introduction

It is widely accepted that evolution is driven by two random processes - mutations and recombinations and a directional process - selection. Recombination not only re-shuffles genes inside genomes or between genomes but it is also responsible for amplification or elimination of sequences. Duplication of complete coding sequences produces additional copies of genes called paralogs. Thus, paralogous genes are homologous sequences arisen through gene duplication and parallel evolution in one genome. Paralogs can also appear by duplication of large fragments of chromosomes or even by fusion of different genomes (allopolyploidization). Before the fusion, corresponding sequences in the two genomes which had a common ancestor in the past are called orthologs . Since it would be very difficult to reproduce their real history, when they appear in the genome of one organism they are recognized as paralogs. Paralogs are a source of simple redundancy of information, making the genome more stable and resistant to mutational effect by complementing the function of one copy when the other is damaged by mutation  or by reinforcing the function of the amplified gene. Most importantly, gene duplication generates a sequence with a defined function but released from the selection pressure. Redefinition of the duplicated gene function may ameliorate the biological potential of the individual. Taking under consideration all the profits brought by paralogs one can ask why the number of paralogs seems to be limited. First of all, a higher number of gene copies, frequently causing a higher level of products does not mean a more concerted expression of the gene function. The best example - the Down syndrome - is caused by redundant information. Second, limitation comes also from the cost of replication and translation of information, which leads to selection pressure on the genome size. The genome size is the result of compromise between the trends for accumulating information and keeping the costs of replication in the reasonable limit. Nevertheless, the level of redundancy in genetic information is high, for example in a uni-cellular eukaryote organism - Saccharomyces cerevisiae (baker’s yeast) - probably no more than 20 % of genes fulfill essential functions and stay in unique copies. The function of the rest of genes can be complemented, probably mostly by paralogous sequences , .

According to the definition, all the genes in the genome which have a common ancestor belong to one paralog family or group. However, the genome analysis does not give us direct information about the descent of sequences from the common ancestor because we can only conclude about the common progenitor on the basis of homology between compared currently ”living” sequences. The level of homology could additionally indicate the time when the two sequences have diverged. Approximately, the number of mutations which have occurred in the diverging sequences grows with time linearly, though it may depend on the topological character of the duplication itself (i.e. duplication with or without inversion). Furthermore, the fraction of positions in which the two sequences differ does not grow linearly because of multiple substitutions (substitutions which have occurred in the same position several times) and reversions whose probability grows in time. Thus, the level of homology is not an exact measure of divergence time (branching time). At large time distances the homology between two paralogs could be too low to recognise properly whether the observed homology is accidental or the compared sequences actually descend from one progenitor sequence. That is why a threshold of homology is assumed - if the homology level is below the threshold, the compared sequences are considered as independently evolved. Since the threshold is arbitrary, and differs in different analyses, it is important to find whether the size distribution of paralog families depends on the cutoff level of homology.

In all analyzed genomes the distribution of paralog families follows a specific rule. Some authors claim an exponential function , others a power law ruling the frequency of the occurrence of the folds or protein families , , . The latter authors assumed a limited number of the initial sequences evolving into the full genome of the contemporary organism. In our simulations we have assumed that the evolution of the contemporary genomes has started with all the genes indispensable for survival of the individuals and these initial genes were independent progenitors of all paralog families. The organisation of these genes in higher hierarchy (families or folds) was neglected. We have analysed how the size distribution of paralog families depends on the selection pressure, on genome size and on the arbitrarily accepted threshold of homology deciding about the grouping of the sequences into paralog families. The selection pressure is an objective force influencing the genome evolution while the paralog identification errors are connected with our ignorance, rather. In our simulations we used two different ways for measuring the distance between paralogs: the first one was somewhat absolute because it measured the real time of duplication and the second one corresponded to the homology analysis - the Hamming distance between two sequences (bit-strings) was measured.

## 2 Experimental Distributions

Analysis of the first completely sequenced genome demonstrated that distributions of sizes for paralog families indicate a high level of gene duplication . Initial comparison, of bacterial, archeal and eukaryotic genomes has shown that the number of sequences in protein families vs. corresponding family sizes displays power law distributions .

In contrast, Slonimski et al.  in an one page note, reported that for protein families of $`N=2`$ to $`56`$ members, the clusters of $`N+1`$ contain half the number of proteins observed in clusters of $`N`$, independently of the microbial genome size. Their methodology ,  used Smith-Waterman scores $`SW>22`$, the Z-significance values, and connective-clusters in which a given sequence had similarity of $`Z_{value}8`$ with one or more other sequences. The analysis have been performed on yeast and 4 microbial genomes.

Yanai et al.  have compared paralog distributions for 20 genomes, using BLAST and E-significance values ranging from $`E=10^{10}`$ to as large as $`E=10^3`$. They report linear fits on log-log scale for all genomes, with somewhat noisy behaviour for larger families. Qian et al.  have linked the power law distribution of gene families in genomes, with the distribution of structural motifs and protein folds, all three displaying identical slope on log-log plots. Their analyses involved again 20 microbial genomes, and also inter-genome comparisons within analogous functional and structural families.

Unger et al.  compared orthologous gene distributions in three large curated databases: COG, ProtoMap, and Predom (28031, 81286 and 278584 sequences respectively), and also performed partial analysis of a human genome. They again observed a power law behaviour relating the number of sequences in structural and functional families $`F(N)`$ of a given size $`N`$, by $`F(N)N^b`$, where $`b`$ \- the slope of linear fits on log-log plots. Additionally they have linked the slopes for small families, and those for large families by $`b_{50}=1+1/b_{500}`$, where $`b_{50}`$ and $`b_{500}`$ stand for the 50 smallest, and the 500 largest families, after ranking them by size.

Nimwegen  has observed power laws, comparing the number of genes in functional categories vs. total number of genes in a genome, with exponents varying both between bacterial, archeal and eukaryotic genomes, and especially between functional categories: from 0.13 for the protein synthesis in bacteria, to as high as 3.36 for the defense response in eukaryotes.

## 3 Current Work

The $`Z_{value}`$  data of all intragenomic pairwise alignments for 61 complete genomes  have been used. In no case an exponential decay for a distribution of paralogous family sizes was found, independently of the cut-off threshold of the $`Z_{value}`$ used as a similarity measure. As the $`Z_{value}`$ depends much on the length of compared sequences , here we use an amended similarity measure between sequences $`A`$ and $`B`$, $`Z_a=Z_{value}(A,B)/\mathrm{max}[Z_{value}(A),Z_{value}(B)]`$. For identical sequences $`Z_a=1`$, and it tends to zero with increasing dissimilarity.

Figure 1a presents the slopes of the log-log fittings as a function of the $`Z_a`$ cut-off values between 0.01 and 0.6 used, for several genomes. For $`Z_a<0.040.05`$, for all genomes there are only one or two huge super-clusters, and small fractions of singletons and doublets (sometimes also triplets). Clearly such a small cut-off is too low to distinguish anything of interest. For high values of $`Z_a`$, but obviously depending much on the genome size, most sequences are similar only to themselves, and there are mostly singletons, with few still remaining doublets/triplets. At the less stringent similarity cut-off there are regions of gradual change, interspersed by sharp changes in behaviour - corresponding obviously to the splitting events, when clusters are broken, and a possible relationship between homology and function within family/cluster is disrupted. Somewhere in between these two extremes there is a small region of usefulness, when the slope of the log-log fits seems to depend more or less linearly on the cut-off $`Z_a`$ value. Tentatively it might be attributed to a $`Z_a`$ range of 0.04 - 0.1, as for most genomes analysed, we can see a relative plateau of the log-log slope changes with increasing $`Z_a`$.

Moreover, as can be seen in Fig. 1a, any comparisons between genomes must depend to a high degree on the cut-off value of the similarity measure actually used. For example, the data of Brenner et al.  for $`Haemophilus`$ $`influenzae`$ would suggest the slope of the log-log plot equal –1.50, which would imply, if compared to the Fig. 1a, the $`Z_a`$ in between of 0.02 and 0.04, clearly in a twilight zone before the supposedly useful region of linear dependence of the slope on $`Z_a`$. However, the last point (Fig. 2, circles) changes the slope of the fit significantly, the slope after its exclusion equals –1.98. The corresponding analysis using $`Z_a`$ reveals (Fig. 2, stars $`Z_a=0.04`$, squares $`Z_a=0.05`$, triangles $`Z_a=0.06`$) that best agreement between ref. 10 and the current work is at $`Z_a=0.05`$, and that in both cases power law approximation underestimates big-sized families (rightmost points, Fig. 2), especially at higher $`Z_a`$. Finally, the results of cut-off $`Z_{value}=8`$, used by Slonimski et al. ,  (Fig. 2, pentagrams), again agree with both Brenner’s and current results.

The often emphassized dependence of the fitted log-log slopes on the genome size can be observed only as a general trend, with many exceptions. Metanococcus janaschii and Haemophilus influenzae are of almost identical size of about 1700 sequences, but their behaviour is strikingly different, with H. influenzae displaying the quickest change of slopes with increasing $`Z_a`$ of all genomes analysed. Also, H. influenzae large clusters are breaking down to singletons much faster (e.g. the rightmost crosses of Haemophilus in Fig. 2, correspond to the bipartite composition of vast majority of singletons, and a very small remainder of what was before one or two big families). Sulfolobus solfataricus \- at approximately one tenth the genome size of Arabidopsis thaliana \- shows the most shallow dependence of slopes on $`Z_a`$ of all genomes under study, comparable to that of Arabidopsis. Even for the smallest genomes (Fig. 1b) of Mycoplasma genitalium (486 genes), Mycoplasma pneumoniae (687 genes), and Mycoplasma pulmonis (778 genes), Fig. 1b (squares, triangles, and circles respectively), which because of their taxonomical proximity can be compared directly relatively easy, the size dependence of the power law exponent is rather perturbed.

## 4 Simulations

The results of earlier modeling efforts can be found in Refs. 2,9,11,14-17,19. In our simulations we return to the problem emphasized in the Introduction, the number of paralogs for one given function or gene. Thus, in contrast to what was described in preceding sections, we assume to know for every part of the genome its function. In a simulation that is easy, since we can follow the whole evolution since the beginning; for real genomes, such knowledge in general still lies in the future. Our model is a simplification of our earlier one , which was shown  to give reasonable ageing results.

The simulations start with $`N`$ bit-strings of length $`L`$ each, which are zero everywhere. Then at each iteration each bit-string with mutation probability $`p_{mut}`$ selects randomly one of its bits and flips it. Before that, also at every time step, for each family (offspring of one ancestor) either the last bit-string is deleted (with probability $`1/2+b`$) or a randomly selected bit-string is duplicated (with probability $`1/2b`$) and then becomes the last; the positive bias $`b`$ keeps the number $`k`$ of copies (“paralogs”) for each of the $`N`$ original bit-strings limited. Also, the number $`k`$ is not allowed to become negative. Thus at any time we have for each of the $`N`$ ancestors a family consisting of the first bit-string and possibly $`k1`$ additional copies or paralogs, amounting to $`k`$ bit-strings in total for one ancestor (=gene = function).

The Hamming distance (= number of bits different in a bit-by-bit comparison of two bit-strings) was calculated for each paralog with all other bit-strings in the same family at the same time, giving $`(k1)k/2`$ Hamming distances.

The simulations mostly used $`L=64,N=10000,b=0.1,p_{mut}=0.01`$ for $`t=200`$ iterations and averaged over 64000 samples. Simulations for $`L=8,\mathrm{\hspace{0.33em}16},\mathrm{\hspace{0.33em}32}`$ barely differed in the results when a comparison was possible. The average number $`k`$ of paralogs was nearly 3, i.e. we had nearly two additional bit-strings (plus the first one) for each ancestor. Semilogarithmic plots, Fig. 3, of the number of paralog pairs for one ancestor with Hamming distance not exceeding $`x`$ different bits typically gave straight lines with slopes only slightly depending on $`x`$. $`x`$ was taken as 0,1,2,4,8,16,32, and 64. For large $`x`$ the curves nearly overlap. For clarity we divided for our figure the number of pairs by the normalizing factor $`[k(k1)/2]`$ and thus for $`L=64`$ get the total number of families.

The overall distributions $`n_k`$, lines in Fig. 3, decay exponentially, proportional to $`[(0.5b)/(0.5+b)]^k=1/1.5^k`$, in the stationary state achieved after dozens of iterations for $`n_k`$, even when the Hamming distances still grow. This formula follows from a detailed balance condition that as many families move on average from size $`k`$ to size $`k+1`$ as move in the opposite direction from size $`k+1`$ to size $`k`$. Thus the fraction of families with only a single bit-string is $`1(0.5b)/(0.5+b)=4b/(1+2b)`$ in this geometric series.

We define the creation of a new paralog as a branching event and store this time. At the end of the simulation we determine for each pair within each family the last event they branched away from each other; the time between this last event and the last iteration of the simulation is the branching time. Within each family the branching times fluctuate strongly but their average value for one given Hamming distance increases roughly linearly with that Hamming distance, until for large Hamming distances the statistics becomes poor, Fig. 4. For longer times (500 and 1000 iterations) the linearity improves.

The above model follows ref.2 except that no selection of the fittest and similar complications are included now. Each of the ancestors is interpreted as one function (or gene) in the whole organism. The bit-string for this ancestor then records important mutations at different places within this gene. The paralogs formed in the simulation from this ancestor all refer to this one function. The first bit-string undergoes mutations just as its paralogs and has the same properties except that it can never be removed. It makes no sense to compare bit-strings for different functions; 00101001 means something entirely different for the function “brain” than for the function “hair”. The $`L`$ bits of each bit-string correspond to $`2^L`$ possible alleles for one function, not to $`L`$ base pairs.

The $`N`$ initial ancestors can also be interpreted as $`N`$ different samples simulated for the same function; more generally, they could be $`M`$ different genomes simulated for a genome of $`N/M`$ functions.

## 5 Summary

We presented here two different sets of plots: In the experimental section we found power-law decay for the number of paralogs found by looking through the whole genome. In the simulation section we found exponential decays for the number of paralogs belonging to one known function. The latter exponential decay agrees nicely with simple arguments based on detailed balance; the slopes in these semilogarithmic plots (Fig.3) are determined by our bias in favour of removal instead of addition of a paralog, and the slopes barely depend on the cut-off parameter $`x`$ for the Hamming distance. This agreement of theory with simulation also makes clear that our results would be quite different if the bias would not be the same for all functions.

Acknowledgements

DS thanks the Julich supercomputer center for time on their Cray-T3E and M. Dudek for help with LNCS formats. JPR was partially supported from the 115/E-343/S/ICM/853/2003 and 115/E-343/BW/ICM/1624/2003 grants.

References

 Fitch WM: Distinguishing homologous from analogous proteins, Syst. Zool. 19 (1970) 99-113

 Cebrat S, Stauffer D: Monte Carlo simulation of genome viability with paralog replacement. J.Appl.Genet. 43 (2002) 391-395

 MIPS 2002 Database, http://mips.gsf.de/proj/yeast/.

 Mackiewicz P, Kowalczuk M, Mackiewicz D, Nowicka A, Dudkiewicz M, Laszkiewicz A, Dudek MR, Cebrat S: How many protein-coding genes are there in the Saccharomyces cerevisiae genome? Yeast 19 (2002) 619-629

 Slonimski PP, Mosse MO, Golik P, Henaut A, Risler JL, Comet JP, Aude JC, Wozniak A, Glemet E, Codani JJ: The first laws of genomics. Microb. Comp. Genomics 3 (1998) 46.

 Koonin EV, Galperin MY: Sequence - Evolution - Function, Computational approaches in Comparative Genomics (2003), Kluwer Academic Publishers

 Mackiewicz P, Mackiewicz D, Kowalczuk M, Dudkiewicz M, Dudek MR, Cebrat S: High divergence rate of sequences located on different DNA strands in closely related bacterial genomes. J. Appl. Genet. 44 (2003) 561-584

 Gerstein M, A structural census of genomes: Comparing bacterial, eukaryotic, and archaeal genomes in terms of protein structure: J.Mol.Biol., 274 (1997) 562-574

 Yanai I, Camacho CJ, DeLisi C: Predictions of gene family distributions in microbial genomes: Evolution by gene duplication and modification. Phys. Rev. Lett., 85 (2000) 2641-2644

 Brenner SE, Hubbard T, Murzin A, Chotia C: Gene duplications in Haemophilus influenzae. Nature, 378 (1995) 140

 Huynen MA, van Nimwegen E: The frequency distribution of gene family sizes in complete genomes. Mol.Biol.Evol., 15 (1998) 583-589

 Codani JJ, Comet JP, Aude JC, Glemet E, Wozniak A, Risler JL, Henaut A, Slonimski PP: Automatic analysis of large-scale pairwise alignments of protein sequences. Methods Microbiol., 28 (1999) 229-244

 Comet JP, Aude JC, Glemet E, Risler JL, Henaut A, Slonimski PP, Codani JJ: Significance of Z-value statistics of Smith-Waterman scores for protein alignments. Comput.Chem., 23 (1999) 317-331

 Qian J, Luscombe NM, Gerstein M: Protein family and fold occurrence in genomes: Power-law behaviour and evolutionary model. J.Mol.Biol. 313 (2001) 673-681

 Unger R, Uliel S, Havlin S: Scaling law in sizes of protein sequence families: From super-families to orphan genes. Proteins 51 (2003) 569-576

 van Nimwegen E: Scaling laws in the functional content of genomes. Trends Genet. 19 (2003) 479-484

 Koonin EV, Wolf Yi, Karev GP: The structure of the protein universe and genome evolution, Nature, 420 (2002) 218-223

 TERAPROT project (CEA, Gene-It, Infobiogen), June 2002

 Alle P: Simulation of gene duplication in the Penna bit-string model of biological ageing. Master’s thesis, Cologne University 2003.


text:
# 1 Introduction

## 1 Introduction

The experimental investigation of ultra-relativistic nuclear collisions offers a unique possibility of studying the properties of strongly interacting matter at high energy density. In that regime, hadronic matter is expected to become deconfined, and a gas of asymptotically free quarks and gluons is formed, the so-called quark-gluon plasma (QGP), in which the colour interactions between partons are screened owing to collective effects . One of the important tools to study QGP properties is transverse and elliptic flow observables.

In particular, the experimentally observed growth of the mean transverse momentum with increasing mass in most central nuclear collisions at SPS  and RHIC  energies is naturally and simply explained with the hydrodynamical model , where the change of momentum $`\mathrm{\Delta }p_T(𝐫)`$ of a hadron of mass $`m`$ due to transverse motion of a fluid element at the point $`𝐫`$ can be written as $`\mathrm{\Delta }p_T(𝐫)=m\mathrm{sinh}Y_T(𝐫)`$, where $`Y_T`$ is the collective transverse rapidity.

Moreover, a strong interest in azimuthal correlation measurements in ultrarelativistic heavy ion collisions has recently gained impetus. Recent anisotropic flow data from SPS  and RHIC  can be described well by hydrodynamical models for semi-central collisions and transverse momentum, $`p_T`$, up to $`2`$ GeV/c (the coefficient of elliptic flow $`v_2`$, which is defined as the coefficient of the second harmonic of the particle azimuthal distribution with respect to the reaction plane, appears to be monotonously growing with increasing $`p_T`$  in this case). On the other hand, the majority of microscopical Monte-Carlo models underestimate the flow effects (see however ). Measurements of $`v_2`$ present one of the effective tools to test various models. In particular, the saturation and gradual decrease of $`v_2`$ for $`p_T>2`$ GeV/c, predicted as a signature of strong partonic energy loss in a QGP, is supported by the recent RHIC data  extending up to $`p_T10`$ GeV/c. The interpolation between the low-$`p_T`$ relativistic hydrodynamics region and the high-$`p_T`$ pQCD-computable region was evaluated in .

The initial gluon densities in Pb$``$Pb reactions at $`\sqrt{s_{\mathrm{NN}}}=5.5`$ TeV at the Large Hadron Collider (LHC) are expected to be significantly higher than at RHIC, implying much stronger QGP effects. The probing experimental capabilities of LHC detectors together with physics and software validation of various Monte-Carlo tools and cross-comparisons among different codes are important tasks in the light of coming LHC Heavy Ion Program . A number of Monte-Carlo generators is available at the moment to generate heavy ion events at LHC energies: HIJING , FRITIOF , LUCIAE , DPMJET-III , PSM , NEXUS , etc. However, flow effects in almost of such models are lacking or implemented insufficiently. Besides, running these codes at LHC energies consumes much computing efforts. On the other hand, macroscopic hydrodynamical models basically reproduce the bulk of hadron spectra observed at SPS and RHIC, and can be in principle used to estimation of particle flow effects at LHC, may be extending this approach to even some higher pT values. Of course, for more detailed simulation, one has to take into account the interplay between hydro flow and semi-hard particle flow due to parton energy loss, secondary scatterings, etc.

## 2 “Thermal” model and fast Monte-Carlo generation

We suggest simple hydrodynamical Monte-Carlo code  giving final hadron spectrum as a superposition of a thermal distribution and a collective flow ,

$`E{\displaystyle \frac{d^3N}{d^3p}}={\displaystyle _\sigma }f(x,p)p^\mu 𝑑\sigma _\mu ,`$ (1)
where the invariant distribution function $`f(x,p)`$ is taken in the Bose-Einstein form for particles of integer spin and in the Fermi-Dirac form for particles of half-integer spin ($`p_\mu `$ is the $`4`$-momentum of hadron, and $`E=p_0`$ is its energy). Integration is performed over the hypersurface $`\sigma `$ at the “freeze-out” temperature $`T=T_f`$. The formation of the cylindrically symmetric hot matter expanding preferably along the cylinder axis is expected in the case of relativistic heavy ion collisions; as to the transverse motion, it can be taken into account as a correction . In this case, the variables $`\tau `$, $`r`$, $`\eta `$ and $`\mathrm{\Phi }`$ ($`r=\sqrt{x^2+y^2},\tau =\sqrt{t^2z^2},\eta =\frac{1}{2}\mathrm{ln}\frac{t+z}{tz},\mathrm{tan}\mathrm{\Phi }=y/x`$) are commonly used instead of the Cartesian coordinates $`t`$, $`x`$, $`y`$, $`z`$. We consider charged and neutral pions, kaons and nucleons only, and kaons and nucleons are supposed to be thermally suppressed by their heavier mass. In addition, the linear transverse velocity profile specification

$$u^r=\mathrm{sinh}Y_T=\frac{dR}{d\tau }\frac{r}{R}$$

(which follows from a solution of the nonrelativistic continuity equation with uniform density) and longitudinal velocity specification in accordance with one-dimensional scaling solution $`Y_L=\eta `$ are assumed ($`Y_T`$ and $`Y_L`$ are, respectively, the transverse and the longitudinal rapidity of collective motion, while $`R`$ is the effective transverse radius of the system).

The following procedure were applied to simulate “thermal” hadron spectra in heavy ion AA collisions at given impact parameter $`b`$.
1. The 4-momentum $`p_\mu ^{}`$ of a hadron of mass $`m`$ was generated at random in the rest frame of a liquid element in accordance with the isotropic Boltzmann distribution

$`f(E^{})E^{}\sqrt{E^2m^2}\mathrm{exp}(E^{}/T_f),1<\mathrm{cos}\theta ^{}<1,0<\varphi ^{}<2\pi ,`$ (2)
where $`E^{}=\sqrt{p^2+m^2}`$ is the energy of the hadron, and the polar angle $`\theta ^{}`$ and the azimuthal angle $`\varphi ^{}`$ specify the direction of its motion in the rest frame of the liquid element.
2. The spatial position of a liquid element and its local 4-velocity $`u_\mu `$ were generated at random in accordance with phase space and the character of motion of the fluid:

$`f(r)=2r/R_f^2(0<r<R_f),\eta _{\mathrm{max}}<\eta <\eta _{\mathrm{max}},0<\mathrm{\Phi }<2\pi ,`$
$`u_r={\displaystyle \frac{r}{R_f}}\mathrm{sinh}Y_T^{\mathrm{max}},u_t=\sqrt{1+u_r^2}\mathrm{cosh}\eta ,u_z=\sqrt{1+u_r^2}\mathrm{sinh}\eta ,`$ (3)
where $`R_f`$ is the effective final transverse radius of the system, which is fixed here by specifying the mean charged multiplicity per unit rapidity interval, $`<dN/dy^h>`$, in the final state; $`\eta _{\mathrm{max}}=Y_L^{\mathrm{max}}`$ and $`Y_T^{\mathrm{max}}`$ are maximum longitudinal and transverse collective rapidities.
3. Further, boost of the hadron 4-momentum in the c.m. frame of the event was performed:

$`p_x`$ $`=`$ $`p^{}\mathrm{sin}\theta ^{}\mathrm{cos}\varphi ^{}+u_r\mathrm{cos}\mathrm{\Phi }\left[E^{}+{\displaystyle \frac{(u^ip^i)}{u_t+1}}\right]`$
$`p_y`$ $`=`$ $`p^{}\mathrm{sin}\theta ^{}\mathrm{sin}\varphi ^{}+u_r\mathrm{sin}\mathrm{\Phi }\left[E^{}+{\displaystyle \frac{(u^ip^i)}{u_t+1}}\right]`$
$`p_z`$ $`=`$ $`p^{}\mathrm{cos}\theta ^{}+u_z\left[E^{}+{\displaystyle \frac{(u^ip^i)}{u_t+1}}\right]`$
$`E`$ $`=`$ $`E^{}u_t+(u^ip^i),`$ (4)
where

$`(u^ip^i)`$ $`=`$ $`u_rp^{}\mathrm{sin}\theta ^{}\mathrm{cos}(\mathrm{\Phi }\varphi ^{})+u_zp^{}\mathrm{cos}\theta ^{}.`$ (5)
Anisotropic flow is introduced here under simple assumption that the spatial ellipticity of “freeze-out” region, $`ϵ=y^2x^2/y^2+x^2`$, is directly related to the ellipticity of the system formed in the region of the initial overlap of nuclei, $`ϵ_0=b/2R_A`$ ($`R_A`$ is nucleus radius). This “scaling” enables one to avoid introducing additional parameters and, at the same time, leads to an azimuthal anisotropy of generated particles due to dependence of effective final radius $`R_f(b)`$ on the angle $`\mathrm{\Phi }`$ :

$$R_f(b)=R_f(b=0)\mathrm{min}\{\sqrt{1ϵ_0^2\mathrm{sin}^2\mathrm{\Phi }}+ϵ_0\mathrm{cos}\mathrm{\Phi },\sqrt{1ϵ_0^2\mathrm{sin}^2\mathrm{\Phi }}ϵ_0\mathrm{cos}\mathrm{\Phi }\}.$$
(6)
Obtained in such a way azimuthal distribution of particles is described well by the elliptic form for the domain of reasonable impact parameter values.

We also set the Poisson multiplicity distribution and assume that the mean multiplicity of particles is proportional to the nuclear overlap function . For estimated “freeze-out” parameters – temperature $`T_f=140`$ MeV, collective longitudinal rapidity $`Y_L^{max}=5`$ and collective transverse rapidity $`Y_T^{max}=1`$ – we get average hadron transverse momentum $`<p_T^h>=0.55`$ GeV/c and following particle ratios:

$$\pi ^\pm :K^\pm :p^\pm =24:6:1,\pi ^\pm :\pi ^0=2:1,K^\pm :K^0=1:1,p:n=1:1.$$

The model has been realized as fast Monte-Carlo event generator, and corresponding Fortran routine is available by the web . The following input parameters should be specified by user to set hadron event configuration: beam and target nucleus atomic number; type of event centrality generation (options “fixed impact parameter” or “impact parameter is generated with standard Glauber geometry between minimum and maximum values” are foreseen); baseline mean charged particle multiplicity per unit rapidity at mid-rapidity, $`<dN^\pm /dy^h>(y^h=0)`$, in central Pb-Pb collisions (total multiplicity for other centralities and atomic numbers will be calculated automatically). Since the output particle information is stored in common block LUJETS of JETSET routine , main users program should be compiled with JETSET Fortran routine with extended size (up to 150000) of LUJETS arrays.

## 3 Conclusions

The simple model to simulate flow effects in heavy ion collisions at LHC energies has been developed. This model is realized as fast Monte-Carlo event generator, and corresponding Fortran routine is available by the web.

To conclude, let us to discuss the physics validity of the model application.

* Internal parameters of the routine for flow were selected as an estimation for LHC heavy ion beam energies. The result for other beam energy ranges, obtained without additional internal parameters adjusting, is not expected to be reasonable.
* Hydro-type description of heavy ion collisions is expected to be applicable for central and semi-central collisions. The result obtained for very peripheral collisions ($`b2R_A`$) can be not adequate.
* Hydro flow mechanism in heavy ion collisions is valid for restricted kinematic range: mid-rapidity, low and intermediate $`p_T`$. The model is not applicable for very forward rapidity ($`|y|\begin{array}{c}>\hfill \\ \hfill \end{array}3`$) and very high $`p_T`$ ($`25`$ GeV/c).

Acknowledgments.
We would like to thank S.V. Petrushanko, C. Roland and L.I. Sarycheva for useful discussions.


text:
# UASLP–IF–03–008 Review of Recent Results in Charm Physics11footnote 1Invited talk the 9th International Conference on B-Physics at Hadron Machines – BEAUTY 2003, Carnegie Mellon University, Pittsburgh, October 14-18, 2003. Proceedings to be published by AIP.

## 1 Introduction

In contrary to the last 5 years or so, were mostly “traditional” charm experiments like E791, FOCUS, SELEX, WA89, WA92, CLEO, and H1/ZEUS published results about more “traditional” topics like production, lifetimes, rare decays, and limits on $`D^0\overline{D^0}`$ mixing, accompanied by a small number of theory and phenomenology papers, in the last year a shift in charm physics occurred. New players like BaBar, Belle and CDF entered the field, new charm states (doubly charmed baryons, hidden double charm ($`J/\mathrm{\Psi }c\overline{c}`$), $`D_s^{}`$, $`X(3872)`$) were discovered, and the first pentaquark was observed. All this triggered a large number of “theory” papers, pre- and post-dicting the spectroscopy and production of these new states. In most of these papers a (back-)shift to the di-quark picture of charmed hadrons can be observed.

We will present here a (biased) selection of recent results in charm physics. In several other talks at this conference charm results were shown.

## 2 $`𝐃^\mathrm{𝟎}\overline{𝐃^\mathrm{𝟎}}`$ Mixing

The usual observable for $`CP`$ violation in the charm system is the lifetime difference between $`D^0K^{}K^+`$ and $`D^0K^{}\pi ^+`$, defined as $`y_{CP}=\tau (K^{}\pi ^+)/\tau (K^{}K^+)1`$, predicted in the Standard Model to $`y_{CP}10^3`$. Another possible analysis is the “wrong-sign” Double Cabbibo Suppressed $`D^0K^+\pi ^{}`$, with the observable $`y^{}`$. Recent results where published by Belle Abe et al. (2003a) and BaBar Aubert et al. (2003a), and are compared with previous results in table 1.

All measurements are compatible with $`0`$, e.g. no $`CP`$ violation was observed yet in the charm system.

## 3 Rare Decays of $`𝐃^\mathrm{𝟎}`$ and $`𝐃^\pm `$ Mesons

FOCUS observed the rare decay $`D^0K^{}K^{}K^+\pi ^+`$ with a yield of $`132\pm 19`$ events, and measured the relative branching ratio to $`\mathrm{\Gamma }(D^0K^{}K^{}K^+\pi ^+)/\mathrm{\Gamma }(D^0K^{}\pi ^{}\pi ^+\pi ^+)=0.00257\pm 0.00034\pm 0.00024`$ Link et al. (2003a). Resonant Resonant substructures with $`\mathrm{\Phi }`$ and $`\overline{K^{}(892)^0}`$ are dominant.

Belle observed $`D^0\varphi \pi ^0`$, $`\varphi \eta `$, and $`\varphi \gamma `$ Abe et al. (2003b).

CLEO performed a Dalitz plot analysis of $`D^0\pi ^{}\pi ^+\pi ^0`$, and studied $`D^0K_s\eta \pi ^0`$ Dubrovin (2003). CLEO also observed the Cabbibo suppressed decays $`D^+\pi ^+\pi ^0`$, $`K^+\overline{K^0}`$, and $`K^+\pi ^0`$ Arms et al. (2003), and the measured Branching Ratios are shown in table 2.

FOCUS studied di-muon decays for $`D^+`$ and $`D_s^+`$ Link et al. (2003b), and obtained new limits on these modes.

A new player in the field, CDF, set a limit for $`D^0\mu ^+\mu ^{}`$ at $`<2.510^6`$ Acosta et al. (2003).

## 4 Scalar Resonances in $`𝐃^+`$ and $`𝐃_𝐬^+`$ Decays

Since a few years E791 is studying the modes $`D^+K^{}\pi ^+\pi ^+`$, $`D^+\pi ^{}\pi ^+\pi ^+`$, and $`D_s^+\pi ^{}\pi ^+\pi ^+`$. To explain the resonant substructures in the decays, they need to include two scalar resonance, one for $`K\pi `$ (the $`\kappa `$) with mass $`(797\pm 19\pm 43)\text{MeV}/c^2`$ and width $`(410\pm 43\pm 87)\text{MeV}/c^2`$, and a second in $`\pi \pi `$ (the $`\sigma `$) with mass $`(478_{23}^{+24}\pm 17)\text{MeV}/c^2`$ and width $`(324_{40}^{+42}\pm 21)\text{MeV}/c^2`$ Aitala et al. (2002, 2001); Bediaga (2003).

## 5 The $`𝐃_𝐬`$ System

On April 12, 2003, BaBar announced the observation of a narrow resonance, decaying to $`D_s\pi ^0`$, at $`2.32\text{GeV}/c^2`$ Aubert et al. (2003c). Shortly after, CLEO not only confirmed the observation, but observed an additional resonance, decaying to $`D_s^{}\pi ^0`$ Besson et al. (2003); Stone and Urheim (2003). During the summer conferences, Belle confirmed both observations Krokovny et al. (2003); Abe et al. (2003c). The most likely nature of these states are excited $`D_s`$ mesons; the search for similar states in the $`D^0`$ and $`D^\pm `$ system already started. More details can be found in these proceedings Wang (2003).

## 6 Charmed Baryons: The $`\mathrm{\Lambda }_c^+`$ and $`\mathrm{\Sigma }_c^{0,++}`$

CLEO reports the observation of the $`\mathrm{\Lambda }_c^+\mathrm{\Lambda }\pi ^+\pi ^+\pi ^{}\pi ^0`$ decay Cronin-Hennessy et al. (2003), with $`=(1.79\pm 0.47\pm 0.43)\text{\%}`$, while most of the decays happen via $`\mathrm{\Lambda }_c^+\mathrm{\Lambda }\omega \pi ^+`$.

CLEO also measured the masses and widths of $`\mathrm{\Sigma }_c^{++}`$ and $`\mathrm{\Sigma }_c^0`$ Artuso et al. (2002) (the results are shown in table 3),

updating previous results on the masses from E791 Aitala et al. (1996).

## 7 Charmed Baryons: The $`\mathrm{\Xi }_c^+`$ and $`\mathrm{\Xi }_c^0`$

FOCUS measured several new decay modes of the $`\mathrm{\Xi }_c^+`$ and re-measured some previously observed ones. A summary is given in table 4.

FOCUS also includs upper limits for resonances in these decay modes.

CLEO obtained a new measurement of the $`\mathrm{\Xi }_c^+`$ lifetime, $`\tau (\mathrm{\Xi }_c^+)=(503\pm 47\pm 18)\text{fs}`$ Mahmood et al. (2002).

CLEO also reports the first observation of the $`\mathrm{\Xi }_c^0pK^{}K^{}\pi ^+`$ decay Danko et al. (2003), with a relative branching ratio of $`(\mathrm{\Xi }_c^0pK^{}K^{}\pi ^+)/(\mathrm{\Xi }_c^0\mathrm{\Xi }^{}\pi ^+)=0.35\pm 0.08\pm 0.05`$. In this decay they see evidence for a resonant $`\overline{K^{}(892)^0}`$ substructure.

## 8 Charmed Baryons: The $`\mathrm{\Omega }_c^0`$

Evidence for the $`\mathrm{\Omega }_c^0`$ in $`e^+e^{}`$ interactions was reported long time ago by ARGUS Albrecht et al. (1992), and now first CLEO Cronin-Hennessy et al. (2001) and recently Belle Ammar et al. (2002); Abe et al. (2003d) confirm this observation. Both measure the mass of the $`\mathrm{\Omega }_c^0`$ (Belle: $`(2693.9\pm 1.1\pm 1.4)\text{MeV}/c^2`$, CLEO: $`(2694.6\pm 2.6\pm 1.9)\text{MeV}/c^2`$) significantly different from the PDG2000: $`(2704\pm 4)\text{MeV}/c^2`$ Groom et al. (2000). Both observe the mode $`\mathrm{\Omega }_c^0\mathrm{\Omega }^{}\pi ^+`$ and $`\mathrm{\Omega }_c^0\mathrm{\Omega }^{}e^+\nu `$, and Belle observes in addition the semileptonic muon mode.

## 9 Doubly Charmed Baryons: The $`\mathrm{\Xi }_{cc}^+`$

The SELEX experiment reported the first observation of a member of the doubly charmed baryon family, the $`\mathrm{\Xi }_{cc}^+`$, in the decay mode $`\mathrm{\Xi }_{cc}^+\mathrm{\Lambda }_c^+K^{}\pi ^+`$ Mattson et al. (2002). Further work on different decay modes is ongoing.

I would like to thank John Cumalat and Erik Gottschalk from FOCUS, Sheldon Stone and JC Wang from CLEO, Jeff Appel from E791, Masa Yamauchi and Karim Trabelsi from Belle, and Livio Lanceri from BaBar for providing me with information and figures from their respective experiments. I would also like to thank the organizers of the conference for the opportunity to give this presentation.