format: text

text:
# On Some Additivity Problems in Quantum Information Theory

## 1 Introduction

Quantum information theory  is not merely a theoretical basis for physics of information and computation. It is also a source of challenging mathematical problems, often having elementary formulation but still resisting solution. It appears that surprisingly little is known about what may be called the combinatorial geometry of tensor products of Hilbert spaces, even in finite dimensions. One group of open problems concerns the additivity properties of various quantities characterizing quantum channels, notably the capacity for classical information, and the “maximal output purity”, defined below. All known results, including extensive numerical work in the IBM group , the Quantum Information group in the Technical University of Braunschweig, and elsewhere, are consistent with the conjecture that these quantities are indeed additive (resp. multiplicative) with respect to tensor products of channels. A proof of this conjecture would have important consequences in quantum information theory: in particular, according to this conjecture, the classical capacity or the maximal purity of outputs cannot be increased by using entangled inputs of the channel.

In this paper we state the additivity/multiplicativity problems, give some relations between them, and prove some new partial results, which also support the conjecture.

## 2 Statement of the problem

Let us give precise formulation of the additivity problem for the classical capacity (see , ). Let $`()`$ be the $``$ -algebra of all operators in a finite dimensional unitary space $``$. We denote the set of states, i.e. positive unit trace operators in $`()`$ by $`𝒮()`$, the set of all $`m`$-dimensional projections by $`𝒫_m()`$ and the set of all projections by $`𝒫()`$. A quantum channel $`\mathrm{\Phi }`$ is a completely positive trace preserving linear map of $`()`$ (we are in the finite dimensional case and we use the Schrödinger picture). These are the maps admitting the Kraus decomposition (see e. g. , )

$$\mathrm{\Phi }(\rho )=\underset{k}{}A_k\rho A_k^{},$$
(1)
where $`A_k`$ are operators satisfying $`_kA_k^{}A_k=I.`$

Let $`H(\rho )=\text{Tr}\rho \mathrm{log}\rho `$ denote the von Neumann entropy of the state $`\rho `$ and define

$$C(\mathrm{\Phi })=\underset{p_i,\rho _i}{\mathrm{max}}[H(\underset{i}{}p_i\mathrm{\Phi }(\rho _i))\underset{i}{}p_iH(\mathrm{\Phi }(\rho _i))],$$

where the maximum is taken over all finite probability distributions $`\{p_i\}`$ on $`𝒮()`$, ascribing probabilities $`p_i`$ to (arbitrary) states $`\rho _i`$. The quantity $`C(\mathrm{\Phi })`$ appears as the “one-step classical capacity” of the quantum channel $`\mathrm{\Phi }`$ or the capacity with unentangled input states (we refer to  for a detailed information-theoretic discussion and the proof of the corresponding coding theorem). A thorough discussion of the properties of $`C(\mathrm{\Phi })`$ is given in .

The additivity problem can be formulated as follows: let $`\mathrm{\Phi }_1,\mathrm{},\mathrm{\Phi }_n`$ be channels in the algebras $`(_1),\mathrm{},(_n)`$ and let $`\mathrm{\Phi }_1\mathrm{}\mathrm{\Phi }_n`$ be their tensor product in $`(_1\mathrm{}_n)`$ . Is it true that

$$C(\mathrm{\Phi }_1\mathrm{}\mathrm{\Phi }_n)=\underset{i=1}{\overset{n}{}}C(\mathrm{\Phi }_i)\mathrm{?}$$
(2)
This obviously holds for reversible unitary channels; in  the additivity was established for the so called classical-quantum and quantum-classical channels, which map from or into an Abelian subalgebra of $`()`$.

Another closely related problem is the additivity of a quantity, which can be read as the “maximal output purity” of a channel. In fact, there are several quantities of this kind, depending on the way we measure “purity”. If we just take the von Neumann entropy as a measure of purity, we arrive at the question ,  whether or not

$$\underset{\rho 𝒮(_1\mathrm{}_n)}{\mathrm{min}}H((\mathrm{\Phi }_1\mathrm{}\mathrm{\Phi }_n)(\rho ))=\underset{i=1}{\overset{n}{}}\underset{\rho 𝒮(_i)}{\mathrm{min}}H(\mathrm{\Phi }_i(\rho ))\mathrm{?}$$
(3)
For a particular class of channels this property implies (2) (see the Lemma in Section 5 below).

We will also consider this problem for other measures of purity, based on the noncommutative $`\mathrm{}_p`$-norms

$$A_p=\left(\mathrm{Tr}|A|^p\right)^{\frac{1}{p}},$$

defined for $`p1`$, and $`A()`$, with the operator norm $`A`$ corresponding naturally to the case $`p=\mathrm{}`$. For an arbitrary quantum channel $`\mathrm{\Phi }`$ let us introduce the following notations for the “highest purity” of outputs of a channel

$`\nu _H(\mathrm{\Phi })`$ $`=`$ $`\underset{\rho }{\mathrm{min}}H(\mathrm{\Phi }(\rho )),`$ (4)
$`\nu _p(\mathrm{\Phi })`$ $`=`$ $`\underset{\rho }{\mathrm{max}}\mathrm{\Phi }(\rho )_p,`$ (5)
$`\nu _{\mathrm{}}(\mathrm{\Phi })`$ $`=`$ $`\underset{\rho }{\mathrm{min}}\mathrm{\Phi }(\rho )^1^1,`$ (6)
where the extrema are taken with respect to all input density matrices $`\rho `$ . By convexity of the norms, the extrema in the above definitions are attained on pure states (in the first (resp. last) case the operator convexity of the function $`xx\mathrm{log}x`$ (resp. $`xx^1`$) is also relevant).

Then the additivity/multiplicativity inequalities

$`\nu _p(\mathrm{\Phi }_1\mathrm{\Phi }_2)`$ $``$ $`\nu _p(\mathrm{\Phi }_1)\nu _p(\mathrm{\Phi }_2)`$ (7)
$`\nu _H(\mathrm{\Phi }_1\mathrm{\Phi }_2)`$ $``$ $`\nu _H(\mathrm{\Phi }_1)+\nu _H(\mathrm{\Phi }_1)`$ (8)
are clear from inserting product density operators into the defining variational expressions. The standing conjecture is that equality always holds in these inequalities, i.e. that choosing entangled input states is never helpful for getting purer output states.

Before proceeding to show some new partial results on this problem, it is helpful to establish the relation between $`\nu _H(\mathrm{\Phi })`$, and $`\nu _p(\mathrm{\Phi })`$ for $`p`$ close to one. Of course, some relationship is expected, as the von Neumann entropy $`H(\rho )`$ can be computed in terms of the derivative of $`\rho _p`$ at $`p=1^+`$. Here we find that if the equality holds in ( 7) for $`p`$ arbitrarily close to $`1`$, then it holds also in (8).

Proof. We shall use the fact that for every $`0<x1`$

$$\frac{1x^p}{p1}x\frac{\mathrm{log}x}{\mathrm{log}e}$$

if $`p1`$. Thus $`\frac{1\mathrm{Tr}\mathrm{\Phi }(\rho )^p}{p1}`$ is a monotonely increasing family of continuous functions of the variable $`\rho `$ which varies in the compact set $`𝒮()`$, converging pointwise to the continuous function $`H(\mathrm{\Phi }(\rho ))`$. By Dini’s Theorem, the convergence is uniform, and

$$\underset{\rho }{\mathrm{min}}H(\mathrm{\Phi }(\rho ))=\underset{p1}{lim}\frac{1\mathrm{max}_\rho \mathrm{Tr}\mathrm{\Phi }(\rho )^p}{p1}.$$

Therefore, if the equality holds in (7) for $`p`$ close to $`1`$,

$$\underset{\rho }{\mathrm{min}}H(\left(\mathrm{\Phi }_1\mathrm{\Phi }_2\right)(\rho ))=\underset{p1}{lim}\frac{1\mathrm{max}_\rho \mathrm{Tr}\left((\mathrm{\Phi }_1\mathrm{\Phi }_2)(\rho )\right)^p}{p1}$$

$$=\underset{p1}{lim}\frac{1\mathrm{max}_\rho \mathrm{Tr}\left(\mathrm{\Phi }_1(\rho )\right)^p\mathrm{max}_\rho \mathrm{Tr}\left(\mathrm{\Phi }_2(\rho )\right)^p}{p1}=\underset{\rho }{\mathrm{min}}H(\mathrm{\Phi }_1(\rho ))+\underset{\rho }{\mathrm{min}}H(\mathrm{\Phi }_2(\rho )).$$

$`\mathrm{}`$

## 3 Tensoring with an ideal channel

The first natural step is to establish the multiplicativity property when one factor is the identity channel.

Lemma. For $`=p,H,\mathrm{}`$

$$\nu _{}(\mathrm{\Phi }\mathrm{Id})=\nu _{}(\mathrm{\Phi }).$$
(9)
Since $`\nu _p(\mathrm{Id})=1`$, and $`\nu _H(\mathrm{Id})=0`$, this is indeed an instance of the additivity/multiplicativity conjecture.

Proof. We shall restrict to the case $`=p,1p\mathrm{}`$ . The argument in the case $`=\mathrm{}`$ is similar and the case $`=H`$ follows by the argument given above.

Let us denote by $`_1,_2`$ the Hilbert spaces of the first and the second system, respectively. Let $`\varphi _{12}`$ be a unit vector in $`_1_2,`$ and write $`\rho _{12}=|\varphi _{12}\varphi _{12}|`$ and $`\rho _1=\mathrm{Tr}_2\rho _{12}`$ for the partial state in $`_1`$. If $`\mathrm{\Phi }`$ is the channel in $`_1`$, we denote $`\rho _{12}^{}=(\mathrm{\Phi }\mathrm{Id})(\rho _{12})`$. Let us dilate the channel $`\mathrm{\Phi }`$ to a unitary evolution $`U_{13}`$ with the environment $`_3`$, initially in a pure state $`\rho _3=|\varphi _3\varphi _3|`$. The the final state of the environment is

$$\rho _3^{}=\mathrm{Tr}_1U_{13}(\rho _1|\varphi _3\varphi _3|)U_{13}^{}\mathrm{\Psi }(\rho _1).$$

Since the state of the composite system $`_1_2_3`$ remains pure after the unitary evolution, its partial states $`\rho _{12}^{},\rho _3^{}`$ are isometric . Therefore

$$(\mathrm{\Phi }\mathrm{Id})(\rho _{12})_p=\rho _{12}^{}_p=\rho _3^{}_p=\mathrm{\Psi }(\rho _1)_p.$$

Now the map $`\rho _1\mathrm{\Psi }(\rho _1)`$ is affine and the norm is convex, therefore the maximum of the quantity above is attained on pure $`\rho _1,`$ whence $`\rho _{12}=\rho _1\rho _2,`$ and the statement follows. $`\mathrm{}`$

We shall specifically need this Lemma in the case $`p=\mathrm{}`$. It is instructive to see an alternative direct proof in this case.

Proof.  In what follows we take $`\rho =|\varphi \varphi |`$. We compute the operator norm of the Hermitian operator $`\mathrm{\Phi }(\rho )`$ as $`\mathrm{\Phi }(\rho )=sup_\psi \psi ,\mathrm{\Phi }(\rho )\psi `$, and take $`\mathrm{\Phi }`$ to be given in the Kraus decomposition (1 ). Then

$$\nu _{\mathrm{}}(\mathrm{\Phi })=\underset{\varphi ,\psi }{sup}\underset{k}{}\psi ,A_k\varphi \varphi ,A_k^{}\psi ,$$

where the supremum is over all unit vectors in the appropriate spaces. The expression under the supremum can be read as the $`\mathrm{}^2`$-norm of a vector with components $`\varphi ,A_k^{}\psi `$. We write this norm also as “the largest scalar product with a unit vector” $`\chi `$, i.e.,

$`\nu _{\mathrm{}}(\mathrm{\Phi })`$ $`=`$ $`\left(\underset{\varphi ,\psi ,\chi }{sup}{\displaystyle \underset{k}{}}\overline{\chi _k}\varphi ,A_k^{}\psi \right)^2=\left(\underset{\psi ,\chi }{sup}{\displaystyle \underset{k}{}}\overline{\chi _k}A_k^{}\psi \right)^2`$ (10)
$`=`$ $`\underset{\chi }{sup}{\displaystyle \underset{k}{}}\overline{\chi _k}A_k^{}^2=\underset{\chi }{sup}{\displaystyle \underset{k}{}}\chi _kA_k^2,`$ (11)
where all suprema are over unit vectors. Obviously, the Kraus operators for $`\mathrm{\Phi }\mathrm{Id}`$ are $`A_kI`$, so

$$\nu _{\mathrm{}}(\mathrm{\Phi }\mathrm{Id})=\underset{\chi }{sup}\underset{k}{}\chi _k(A_kI)^2=\underset{\chi }{sup}\left(\underset{k}{}\chi _kA_k\right)I^2=\nu _{\mathrm{}}(\mathrm{\Phi }).$$

$`\mathrm{}`$

We will also need the analogous result for a quantity in which the two vectors $`\varphi ,\psi `$ in the above proof are fixed to be the same: for any channel $`\mathrm{\Phi }`$, let

$$\nu _{\mathrm{}}(\mathrm{\Phi })=\underset{\psi }{sup}\psi ,\mathrm{\Phi }(|\psi \psi |)\psi ,$$
(12)
where the supremum is again over all unit vectors. Note that this expression only makes sense, if the channel does not change the type of system, i.e., input and output algebra are the same. Then

$$\nu _{\mathrm{}}(\mathrm{\Phi }\mathrm{Id})=\nu _{\mathrm{}}(\mathrm{\Phi }).$$
(13)
Proof:  Again we use Kraus decomposition (1). For $`\psi `$ we use the Schmidt decomposition $`\psi =_\mu \sqrt{c_\mu }e_\mu e_\mu ^{}`$, where the $`e_\mu `$ and $`e_\mu ^{}`$ are orthonormal systems. Then the expression to maximized on the left-hand side becomes

$`{\displaystyle \underset{\mu \nu \alpha \beta k}{}}(c_\mu c_\nu c_\alpha c_\beta )^{1/2}e_\mu e_\mu ^{},(A_kI)e_\nu e_\nu ^{}e_\alpha e_\alpha ^{},(A_k^{}I)e_\beta e_\beta ^{}`$
$`=`$ $`{\displaystyle \underset{\mu \nu \alpha \beta k}{}}(c_\mu c_\nu c_\alpha c_\beta )^{1/2}e_\mu ,A_ke_\nu e_\alpha ,A_k^{}e_\beta \delta _{\mu \nu }\delta _{\alpha \beta }`$
$`=`$ $`{\displaystyle \underset{\mu \alpha k}{}}c_\mu c_\alpha e_\mu ,A_ke_\mu e_\alpha ,A_k^{}e_\alpha ={\displaystyle \underset{k}{}}\mathrm{tr}(\rho _1A_k)\mathrm{tr}(\rho _1A_k^{}),`$
where $`\rho _1=_\mu c_\mu |e_\mu e_\mu |`$ is the reduced density matrix belonging to $`\psi `$. Since the function $`\rho _1|\mathrm{tr}(\rho _1A_k)|^2`$ is convex, this expression attains its maximum with respect to $`\psi `$ when $`\rho _1`$ is pure, i.e., when $`\psi `$ is a product. $`\mathrm{}`$

## 4 Weak Noise

One testing ground for the multiplicativity/additivity conjecture are channels close to the identity. For such channels the purity parameters can be evaluated in lowest order in the deviation from the identity. Doing this for each subchannel and for their tensor product, one can explicitly check the conjecture. As the following result shows, this test supports the conjecture.

Consider a channel with weak noise, i.e. choose some channel $`\mathrm{\Phi }`$ on $`()`$, and set

$$\mathrm{\Phi }^{(ϵ)}=(1ϵ)\mathrm{Id}+ϵ\mathrm{\Phi }.$$
(14)
For small $`ϵ`$ this is a weak noise channel, which has the property that for any pure input the output will be nearly pure.

Theorem. The multiplicativity hypothesis for the quantities $`\nu _p(\mathrm{\Phi })`$ with $`1p\mathrm{}`$ and the additivity hypothesis for the quantity $`\nu _H(\mathrm{\Phi })`$ hold true approximately in the leading order in $`ϵ`$.

Proof. In order to estimate these quantities for the weak noise channels, we need to estimate entropy, and the $`p`$-norms near a pure state. Let $`\rho `$ be a density operator on a $`d`$-dimensional Hilbert space, and suppose that $`\rho =1ϵ+𝐨(ϵ)`$. Then the leading order of the other norms is determined completely by $`ϵ`$:

$`\rho _p`$ $`=`$ $`1ϵ+𝐨(ϵ)\text{for }p>1`$ (15)
$`H(\rho )`$ $`=`$ $`ϵ\mathrm{log}ϵ+𝐨(ϵ\mathrm{log}ϵ),`$ (16)
where as usual $`𝐨(ϵ)`$ stands for terms going to zero faster than $`ϵ`$ as $`ϵ0`$. In this case we can say more: in first line we have $`0\text{remainder}Cϵ^p`$, for $`ϵ<1/2`$, where $`C`$ is a constant depending only on the dimension. Similarly, the estimates in the second line are independent of the details of $`\rho `$. Hence in leading order all the variational expressions are equivalent: each one amounts to maximizing $`ϵ`$.

Let us go back to the weak noise channel (14). To get high fidelity we need to maximize the leading term, so we can take $`\eta =\xi `$ in the following computation:

$`\nu _{\mathrm{}}(\mathrm{\Phi }^{(ϵ)})`$ $`=`$ $`\underset{\xi ,\eta }{sup}\xi ,\mathrm{\Phi }^{(ϵ)}(|\eta \eta |)\xi `$ (17)
$`=`$ $`\underset{\xi ,\eta }{sup}\left((1ϵ)|\xi ,\eta |^2+ϵ\xi ,\mathrm{\Phi }(|\eta \eta |)\xi \right)`$
$`=`$ $`1ϵ+ϵ\underset{\xi }{sup}\xi ,\mathrm{\Phi }(|\xi \xi |)\xi +𝐨(ϵ)`$
$`=`$ $`1ϵ+ϵ\nu _{\mathrm{}}(\mathrm{\Phi })+𝐨(ϵ).`$
Note that in all these estimates the remainder estimates can be done uniformly for all channels, depending only on dimension.

A tensor product of weak noise channels (14) is again of the same form:

$`\mathrm{\Phi }^{(ϵ)}`$ $`=`$ $`\mathrm{\Phi }_1^{(ϵ)}\mathrm{}\mathrm{\Phi }_n^{(ϵ)}`$
$`=`$ $`(1ϵ)^n\mathrm{Id}+ϵ(1ϵ)^{n1}\left(\mathrm{\Phi }_1\mathrm{Id}_{2\mathrm{}n}+\mathrm{}+\mathrm{Id}_{1\mathrm{}n1}\mathrm{\Phi }_n\right)+𝐨(ϵ)`$
$`=`$ $`(1nϵ)\mathrm{Id}+nϵ\delta \mathrm{\Phi }+𝐨(ϵ),`$
where $`\delta \mathrm{\Phi }`$ is the average of the $`n`$ channels $`\mathrm{Id}_{1\mathrm{}k1}\mathrm{\Phi }_k\mathrm{Id}_{k+1\mathrm{}n}`$. Hence, in order to compute the leading order of $`\nu _{\mathrm{}}(\mathrm{\Phi }^{(ϵ)})`$ by formula (17) we have to determine $`\nu _{\mathrm{}}(\delta \mathrm{\Phi })`$. We have

$`{\displaystyle \frac{1}{n}}{\displaystyle \underset{k=1}{\overset{m}{}}}\nu _{\mathrm{}}(\mathrm{\Phi }_k)`$ $``$ $`\nu _{\mathrm{}}(\delta \mathrm{\Phi })`$
$``$ $`{\displaystyle \frac{1}{n}}{\displaystyle \underset{k=1}{\overset{m}{}}}\nu _{\mathrm{}}(\mathrm{\Phi }_k\mathrm{Id})`$
$`=`$ $`{\displaystyle \frac{1}{n}}{\displaystyle \underset{k=1}{\overset{m}{}}}\nu _{\mathrm{}}(\mathrm{\Phi }_k)`$
where we have used in turn: insertion of product states into the supremum defining $`\nu _{\mathrm{}}(\delta \mathrm{\Phi })`$, convexity of $`\nu _{\mathrm{}}`$ as a supremum of affine functionals, and finally the restricted additivity result (13). Hence equality holds, which means that in the leading order in $`ϵ`$ all the variational expressions for the purity quantities $`\nu _{}()`$, with $`=p,H,\mathrm{}`$ are attained at product states. $`\mathrm{}`$

## 5 Depolarizing Channels

A channel is called bistochastic if $`\mathrm{\Phi }(I)=I`$, where $`I`$ is the unit operator in $`()`$. An important example is the depolarizing  channel

$$\mathrm{\Phi }(\rho )=(1p)\rho +\frac{p}{d}(\text{Tr}\rho )I,\rho (),0<p<1,$$

where $`d=\text{dim}`$. A channel is called binary if $`d=2`$.

Lemma. Let $`\mathrm{\Phi }`$ be binary bistochastic channel, then

$$C(\mathrm{\Phi })=\mathrm{log}2\underset{\rho 𝒮()}{\mathrm{min}}H(\mathrm{\Phi }(\rho )).$$
(18)
If $`\mathrm{\Phi }_i`$ are binary bistochastic channels, then (3) implies ( 2).

Proof. The $``$ part of (18) is obvious from the fact that for any channel

$$C(\mathrm{\Phi })\mathrm{log}\text{dim}\underset{\rho 𝒮()}{\mathrm{min}}H(\mathrm{\Phi }(\rho )),$$
(19)
so we need to prove only $``$ part. Since the entropy is convex, the minimum is achieved at the set of extreme points of $`𝒮()`$ which is $`𝒫_1()`$. Let $`\rho `$ be the minimum point, then taking equiprobably $`\rho _0=\rho ,\rho _1=I\rho `$, we obtain

$$C(\mathrm{\Phi })H(\frac{1}{2}\mathrm{\Phi }(I))\frac{1}{2}[H(\mathrm{\Phi }(\rho ))+H(\mathrm{\Phi }(I\rho ))].$$

Since the channel is bistochastic, this is equal to $`H(\frac{1}{2}I)\frac{1}{2}[H(\mathrm{\Phi }(\rho ))+H(I\mathrm{\Phi }(\rho ))]`$, and since it is binary, this is equal to the right-hand side of (18).

To prove the second statement, it is sufficient to prove the $``$ part of ( 2), since $``$ part follows from the definitions. But this follows from (19) and (18). $`\mathrm{}`$

In the paper  the relation(2) was proven for the two binary depolarizing channels $`\mathrm{\Phi }_1,\mathrm{\Phi }_2`$. The proof heavily uses Schmidt decomposition and as such does not generalizes to the case $`n>2`$. The main difficulty is evaluating the entropy of the product channel. However, it appears to be possible to check the additivity in the limiting cases of “weak” and “strong” depolarization in the leading order. Let us consider a collection of depolarizing channels $`\{\mathrm{\Phi }_i\}`$ in the Hilbert spaces $`_i`$, with parameters $`p_i,d_i,i=1,2,\mathrm{},n`$, and denote $`\mathrm{\Phi }=_{i=1}^n\mathrm{\Phi }_i`$, $`=_{i=1}^n_i`$, $`d=_{i=1}^nd_i`$. In the following we shall use symbols $`I_i`$ and $`I=_{i=1}^nI_i`$ for the identity operators in $`_i`$ and $``$ respectively. Let $`ϵ_L`$ be the tensor product $`\varphi _1\mathrm{}\varphi _n`$, where $`\varphi _i(\rho )=\frac{1}{d_i}\text{Tr}(\rho )I_i,iL\{1,2,\mathrm{},n\}`$, and $`\varphi _i(\rho )=\rho `$ otherwise, $`\rho 𝒮(_i)`$. Then $`ϵ_L`$ is a conditional expectation onto the subalgebra $`_L`$, generated by operators of the form $`A_1\mathrm{}A_n`$, where $`A_i=I_i`$ for $`iL`$, and is normalized partial trace with respect to its commutant. It has the property $`\underset{P𝒫(_L)}{\mathrm{min}}\mathrm{dim}P=_{i=1}^nd_i^{\theta _L(i)}`$, where $`\theta _L(i)=1`$ if $`iL`$ and $`\theta _L(i)=0`$ otherwise. Here we denoted by $`𝒫(_L)`$ the set of all orthogonal projections in $`_L`$. Notice that the inclusion $`_{L_1}_{L_2}`$ holds if $`L_2L_1`$. So $`ϵ_{L_1}ϵ_{L_2}=ϵ_{L_1L_2}`$.

We shall use the expansion

$$\mathrm{\Phi }=\underset{L}{}\underset{i=1}{\overset{n}{}}p_i^{\theta _L(i)}(1p_i)^{1\theta _L(i)}ϵ_L.$$
(20)
Weak (strong) depolarization corresponds to the case where all $`p_i`$ (respectively, $`1p_i`$) are small parameters, which we assume to be of the same order.

Proposition. The relation (2) holds in the cases of weak and strong depolarization approximately in the leading order.

Proof. In the case of weak depolarization the statement follows from the Theorem in Section 4.

In the case of strong depolarization we have to retain all the terms up to the second order in $`q_i=1p_i`$. Then the leading terms are

$$\mathrm{\Phi }(P)d^1\left[I+\underset{i=1}{\overset{n}{}}q_i(d_iP_iI)+\underset{1i<jn}{}q_iq_j(1d_iP_id_jP_j+d_id_jP_{ij})\right],$$

where we denoted $`d=_{i=1}^nd_i`$, $`P_i`$ is the partial state of $`P`$ in the $`i`$th Hilbert space, multiplied by the unit operator in the tensor product of the remaining Hilbert spaces, and similarly $`P_{ij}`$. Denoting the first (second) sum in the squared brackets $`A_1`$ (respectively $`A_2`$ ) one easily sees that both are traceless operators. Moreover, up to the second order,

$$\mathrm{\Phi }(P)\mathrm{log}\mathrm{\Phi }(P)d^1\left[(1+A_1+A_2)\mathrm{log}d^1+\left(A_1+A_2+\frac{A_1^2}{2}\right)\right]$$

and

$$H(\mathrm{\Phi }(P))\mathrm{log}d\frac{\mathrm{Tr}A_1^2}{2d}.$$

But

$$\mathrm{Tr}A_1^2=d\underset{i=1}{\overset{n}{}}q_i^2(d_i\mathrm{Tr}\rho _i^21),$$

where $`\rho _i`$ is the partial state of $`P`$ in the $`i`$th Hilbert space, which is maximized if and only if $`\rho _i`$ is one-dimensional projection, i.e. $`P=\rho _1\mathrm{}\rho _n.\mathrm{}`$

Partial answers to the multiplicativity hypothesis are given by the following Theorem. In fact, multiplicativity of $`\nu _{\mathrm{}}(\mathrm{\Phi })`$ for binary bistochastic maps follows from a more general result in .

Theorem.

$$\begin{array}{cccc}(i)\hfill & \nu _2(\mathrm{\Phi })\hfill & =\underset{i=1}{\overset{n}{}}\nu _2(\mathrm{\Phi }_i)\hfill & =\underset{i=1}{\overset{n}{}}\left(\frac{d_i1}{d_i}(1p_i)^2+\frac{1}{d_i}\right)^{1/2},\hfill \\ (ii)\hfill & \nu _{\mathrm{}}(\mathrm{\Phi })\hfill & =\underset{i=1}{\overset{n}{}}\nu _{\mathrm{}}(\mathrm{\Phi }_i)\hfill & =\underset{i=1}{\overset{n}{}}\left(1\frac{p_i(d_i1)}{d_i}\right),\hfill \\ (iii)\hfill & \nu _{\mathrm{}}(\mathrm{\Phi })\hfill & =\underset{i=1}{\overset{n}{}}\nu _{\mathrm{}}(\mathrm{\Phi }_i)\hfill & =\underset{i=1}{\overset{n}{}}\frac{p_i}{d_i}.\hfill \end{array}$$

Proof. $`(i)`$ It follows from the relation $`\underset{P𝒫(_L)}{\mathrm{min}}\text{dimP}=_{i=1}^nd_i^{\theta _L(i)}`$ that

$$\text{Tr}(ϵ_{L_1}(P)ϵ_{L_2}(P))=\text{Tr}(Pϵ_{L_1L_2}(P))=\text{Tr}(ϵ_{L_1L_2}(P)^2)\underset{i=1}{\overset{n}{}}d_i^{\mathrm{max}(\theta _{L_1}(i),\theta _{L_2}(i))}$$

for arbitrary $`P𝒫_1()`$ and equality holds only for factorizable projections. Hence

$$\text{Tr}((\mathrm{\Phi }(P))^2)=\text{Tr}((\underset{L}{}\underset{i=1}{\overset{n}{}}p_i^{\theta _L(i)}(1p_i)^{1\theta _L(i)}ϵ_L(P))^2)$$

$$\underset{L_1,L_2}{}\underset{i=1}{\overset{n}{}}p_i^{\theta _{L_1}(i)+\theta _{L_2}(i)}(1p_i)^{2\theta _{L_1}(i)\theta _{L_2}(i)}d_i^{\mathrm{max}(\theta _{L_1}(i),\theta _{L_2}(i))}=$$

$$=\underset{i=1}{\overset{n}{}}\underset{\theta _1,\theta _2=0,1}{}p_i^{\theta _1+\theta _2}(1p_i)^{2\theta _1\theta _2}d_i^{\mathrm{max}(\theta _1,\theta _2)}=\underset{i=1}{\overset{n}{}}\left(\frac{d_i1}{d_i}(1p_i)^2+\frac{1}{d_i}\right).$$

$`(ii)`$ Let us estimate

$$\mathrm{\Phi }(P)\underset{L}{}\underset{i=1}{\overset{n}{}}p_i^{\theta _L(i)}(1p_i)^{1\theta _L(i)}ϵ_L(P)$$

$$\underset{L}{}\underset{i=1}{\overset{n}{}}\left(\frac{p_i}{d_i}\right)^{\theta _L(i)}(1p_i)^{1\theta _L(i)}=\underset{i=1}{\overset{n}{}}\left(1\frac{p_i(d_i1)}{d_i}\right).$$

which proves the second statement.

$`(iii)`$ We have

$$||\mathrm{\Phi }(P))^1||_{k=0}^+\mathrm{}||\mathrm{\Phi }(IP)||^k.$$
(21)
Let us calculate

$$\underset{P𝒫_1(())}{\mathrm{max}}\mathrm{\Phi }(IP)\underset{Q𝒫_{d1}(())}{\mathrm{max}}\mathrm{\Phi }(Q).$$

We have

$$\mathrm{\Phi }(Q)\underset{i=1}{\overset{n}{}}p_iϵ_{\{1,2,\mathrm{},n\}}(Q)$$

$$+\underset{L\{1,2,\mathrm{},n\}}{}\underset{i=1}{\overset{n}{}}p_i^{\theta _L(i)}(1p_i)^{1\theta _L(i)}ϵ_L(Q)$$

$$\left(1d^1\right)\underset{i=1}{\overset{n}{}}p_i+\underset{L\{1,2,\mathrm{},n\}}{}\underset{i=1}{\overset{n}{}}p_i^{\theta _L(i)}(1p_i)^{1\theta _L(i)}=1\underset{i=1}{\overset{n}{}}\frac{p_i}{d_i}.$$
(22)
Here we have used the equality $`\underset{L}{}\underset{i=1}{\overset{n}{}}p_i^{\theta _L(i)}(1p_i)^{1\theta _L(i)}=1`$. Substituting (22) into ( 21), we get the last statement. $`\mathrm{}`$

Acknowledgment. The second author (ASH) acknowledges the support of the A. von Humboldt Foundation.


text:
# 1 Introduction

## 1 Introduction

In nature there exists the mass hierarchy such as the Planck mass ($`10^{19}`$GeV), the GUT scale ($`10^{15}`$Gev), the electro-weak scale ($`10^2`$GeV), the neutrino mass($`10^{11}10^9`$GeV) and the cosmological size($`10^{41}`$GeV). How to naturally explain these different scales ranging over $`10^{60}`$ (so huge !) order has been the long-standing problem (the mass hierarchy problem). One famous approach is the Dirac’s large number theory. He tried to explain some ratios between basic physical quantities ( the electric force/the gravitational force, the age of the universe/the period during the light’s passing through the (classical) electron, the total mass in the universe/the proton mass) using the idea of the variable gravitational constant. Triggered by the development of the string and D-brane theories, some interesting new approaches to the compactification mechanism have recently been proposed  and are applied to the hierarchy problem. Here we examine the Randall-Sundrum (RS) model which has some attractive features compared with the Kaluza-Klein compactification. The model is becoming a strong candidate that could solve the mass hierarchy problem. It looks, however, that the domain wall configuration is usually introduced ”by hand” ( not solving the field equation properly ) and is often ”approximated” by some distribution such as $`\delta `$-function or $`\theta `$-function. Such approximate approach sometimes hinders us from treating delicate (but important) procedures such as the boundary condition, the (infrared) regularization and the cosmological term. We present a solution of the field equation, which clarifies the compactification mechanism much more than the usual treatment. Especially the full-fledged treatment of the vacuum in terms of the 5D Higgs potential is an advantage. For the purpose of treating the model starting from the Lagrangian, we consider the model in a simplified case: One-wall model which was considered in . An interesting stable (kink) solution is found for a family of vacua. The solution does not miss the key points of the original one. Some new features are 1) the (5D) cosmological constant has both the upper bound and the lower bound (15); 2) the wall-thickness parameter $`k`$ (defined later) is regarded as the most important quantity to control the whole configuration properly and should be bounded both from below and from above (26); 3) As a plausible numerical choice, we propose $`k10^4`$GeV to explain quark, lepton and neutrino masses (Sec.5 and Sec.6).

The domain wall configuration, which is exploited in the RS model, has been frequently discussed so far in the literature. Especially the relation between some anomalies is examined in . The regularization of the chiral fermion problem on lattice was examined in . The similarity to these works is shown by clarifying the parameters correspondence. The difference between them is only the interpretation of the extra axis; In the chiral fermion case it is regarded as a purely technical axis for the regularization, whereas, in the RS model, it is a physical axis whose size is too small to measure at present. The analysis using the RS model can be regarded as a geometrical approach to the chiral fermion problem.

At present there exists no sign of the extra dimension(s) experimentally. Hence one might wonder about the worth of the present line of research. We remind you, however, of the following important aspects behind.

1. The higher dimensional view to the present world has been taken , since Kaluza-Klein, by many physicists. The latest approaches are unified models based on the supergravity, the string and the D-brane. This is one basic standpoint to understand the nature from geometry. The RS model is one of such approaches and has many distinguished properties compared with the past ones.
2. Use of the extra dimension(s) is one possible ingredient, independent of the supersymmetry, which can make us go beyond the standard model.
3. Many aspects appearing in the RS model overlap with those in the recent 10-15 years development of the theoretical physics: the chiral fermion problem (the previous paragraph), anomaly problem, D-brane physics, AdS/CFT, etc..
4. As reported in ICHEP2000, some interesting phenomena await the experimental tests.

We introduce the present model in Sec.2. A solution is obtained in Sec.3, where it is essentially described by three parameters specifying the Higgs vacuum. In Sec.4, the asymptotic behaviors, in the dimensional reduction from 5D to 4D, are evaluated for the three parameters. In Sec.5, the orders of magnitude for the two quantities, the thickness parameter ($`k`$) and the 5D Planck mass ($`M`$), are examined from the information of the 4D Planck mass, the 4D cosmological constant and the present experimental status of the Newton’s law. In Sec.6, similarity between the present analysis and the the chiral fermion problem is pointed out. Using the 4D fermion (quarks,leptons) masses, we examine the value of the size of the extra dimension ($`r_c`$). The three parameters referred above are precisely determined in Sec.7, where two constraints coming from the boundary condition are solved for the parameters. We conclude and discuss in Sec.8.

## 2 Model set-up

We start with the 5D gravitational theory, where the metric is Lorenzian, with the 5D Higgs potential.

$`S[G_{AB},\mathrm{\Phi }]={\displaystyle d^5X\sqrt{G}(\frac{1}{2}M^3\widehat{R}\frac{1}{2}G^{AB}_A\mathrm{\Phi }_B\mathrm{\Phi }V(\mathrm{\Phi }))},`$
$`V(\mathrm{\Phi })={\displaystyle \frac{\lambda }{4}}(\mathrm{\Phi }^2v_{0}^{}{}_{}{}^{2})^2+\mathrm{\Lambda },`$ (1)
where $`X^A(A=0,1,2,3,4)`$ is the 5D coordinates and we also use the notation $`(X^A)(x^\mu ,y),\mu =0,1,2,3.`$ $`X^4=y`$ is the extra axis which is taken to be a space coordinate. The signature of the 5D metric $`G_{AB}`$ is $`(++++)`$. $`\mathrm{\Phi }`$ is a 5D scalar field, $`G=detG_{AB}`$, $`\widehat{R}`$ is the 5D Riemannian scalar curvature. $`M(>0)`$ is the 5D Planck mass and is regarded as the fundamental scale of this dimensional reduction scenario. $`V(\mathrm{\Phi })`$ is the Higgs potential and serves for preparing the (classical) vacuum in 5D world. See Fig.1.

The three parameters $`\lambda ,v_0`$ and $`\mathrm{\Lambda }`$ in $`V(\mathrm{\Phi })`$ are called here vacuum parameters. $`\lambda (>0)`$ is a coupling, $`v_0(>0)`$ is the Higgs field vacuum expectation value, and $`\mathrm{\Lambda }`$ is the 5D cosmological constant. It is later shown that the sign of $`\mathrm{\Lambda }`$ must be negative for the proposed domain wall vacuum configuration. Following , we take the line element shown below.

$`ds^2=\mathrm{e}^{2\sigma (y)}\eta _{\mu \nu }dx^\mu dx^\nu +dy^2,`$ (2)
where $`\eta _{\mu \nu }=\text{diag}(1,1,1,1)`$. In this choice, the 4D Poincaré invariance is preserved. The ”warp” factor $`\mathrm{e}^{2\sigma (y)}`$ plays an important role throughout this paper. Note that, for the fixed $`y`$ case ($`dy=0`$), the metric is the Weyl transformation of the flat (Minkowski) space $`\eta _{\mu \nu }dx^\mu dx^\nu `$ (See Sec.6).

## 3 A solution

Let us solve the 5D Einstein equation.

$`M^3(\widehat{R}_{MN}{\displaystyle \frac{1}{2}}G_{MN}\widehat{R})=_M\mathrm{\Phi }_N\mathrm{\Phi }+G_{MN}({\displaystyle \frac{1}{2}}G^{KL}_K\mathrm{\Phi }_L\mathrm{\Phi }+V(\mathrm{\Phi })),`$
$`^2\mathrm{\Phi }={\displaystyle \frac{\delta V}{\delta \mathrm{\Phi }}}.`$ (3)
Following Callan and Harvey, we consider the case that $`\mathrm{\Phi }`$ depends only on the extra coordinate $`y`$, $`\mathrm{\Phi }=\mathrm{\Phi }(y)`$. The above equations reduce to

$`6M^3(\sigma ^{})^2={\displaystyle \frac{1}{2}}(\mathrm{\Phi }^{})^2+V,`$ (4)
$`3M^3\sigma ^{\prime \prime }=(\mathrm{\Phi }^{})^2.`$ (5)
We note that the ”matter equation”, the last one of (3), can also be obtained from $`(M,N)=(4,4)`$ component of the ”gravitational equation”, the first one of (3) which is given by (4). As the extra space (the fifth dimension), we take the real number space $`𝐑=(\mathrm{},+\mathrm{})`$. This is a simplified version of the original RS-model where $`S^1/𝐙_2`$ is taken. We impose the following asymptotic behaviour for the (classical) vacuum of $`\mathrm{\Phi }(y)`$.

$`\mathrm{\Phi }(y)\pm v_0,y\pm \mathrm{}`$ (6)
This means $`\mathrm{\Phi }^{}0`$, and from (5), $`\sigma ^{\prime \prime }0`$. Integrating eq.(5), we obtain

$`3M^3\{\sigma ^{}|_{y=+\mathrm{}}\sigma ^{}|_{y=\mathrm{}}\}={\displaystyle _{\mathrm{}}^{\mathrm{}}}(\mathrm{\Phi }^{})^2𝑑y>0.`$ (7)
From this result, we are led to $`\sigma ^{}\pm \omega ,\sigma \omega |y|`$ as $`y\pm \mathrm{}`$, where $`\omega (>0)`$ is some constant to be determined soon. We can scale out $`M`$ in (4) by rescaling all fields ($`\mathrm{\Phi },\sigma `$), all vacuum parameters ($`\lambda ,v_0,\mathrm{\Lambda }`$) and the coordinate $`y`$ with appropriate powers of $`M`$. ($`\mathrm{\Phi }=M^{3/2}\stackrel{~}{\mathrm{\Phi }},\sigma =\stackrel{~}{\sigma },v_0=M^{3/2}\stackrel{~}{v}_0,\lambda =M^1\stackrel{~}{\lambda },\mathrm{\Lambda }=M^5\stackrel{~}{\mathrm{\Lambda }},X^A=M^1\stackrel{~}{X}^A,`$) Therefore we may set $`M=1`$ without ambiguity. (Only when it is necessary, we explicitly write down $`M`$-dependence.)

First we fix the parameter $`\omega `$, by considering $`y\pm \mathrm{}`$ in (4), as

$`\omega =\sqrt{{\displaystyle \frac{\mathrm{\Lambda }}{6}}}M^{\frac{3}{2}},`$ (8)
where we see the sign of $`\mathrm{\Lambda }`$ must be negative, that is, the 5D geometry must be anti de Sitter in the asymptotic regions.

Let us take the following form for $`\sigma ^{}(y)`$ and $`\mathrm{\Phi }(y)`$ as a solution.

$`\sigma ^{}(y)=k{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{c_{2n+1}}{(2n+1)!}}\{\mathrm{tanh}(ky+l)\}^{2n+1},`$
$`\mathrm{\Phi }(y)=v_0{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{d_{2n+1}}{(2n+1)!}}\{\mathrm{tanh}(ky+l)\}^{2n+1},`$ (9)
where $`c`$’s and $`d`$’s are coefficient-constants (with respect to $`y`$) to be determined. The free parameter $`l`$ comes from the translation invariance of (4) and (5). A new mass scale $`k(>0)`$ is introduced here to make the quantity $`ky`$ dimensionless. The physical meaning of $`1/k`$ is the ”thickness” of the domain wall. The parameter $`k`$, with $`M`$ and $`r_c`$(defined later), plays a central role in this dimensional reduction scenario. We call $`M,k`$ and $`r_c`$ fundamental parameters. The distortion of 5D space-time by the existence of the domain wall should be small so that the quantum effect of 5D gravity can be ignored and the present classical analysis is valid. This requires the condition

$`kM.`$ (10)
The coefficient-constants $`c`$’s and $`d`$’s have the following constraints

$`\sqrt{{\displaystyle \frac{\mathrm{\Lambda }}{6}}}=k{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{c_{2n+1}}{(2n+1)!}},1={\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{d_{2n+1}}{(2n+1)!}},`$ (11)
which are obtained by considering the asymptotic behaviours $`y\pm \mathrm{}`$ in (9). We will use these constraints in Sec.7.

We first obtain the recursion relations between the expansion coefficients, from the field equations (4) and (5). For $`n2`$, they are given by

$`{\displaystyle \frac{c_{2n+1}}{(2n)!}}{\displaystyle \frac{c_{2n1}}{(2n2)!}}={\displaystyle \frac{v_{0}^{}{}_{}{}^{2}}{3}}(D_{}^{}{}_{n}{}^{}2D_{}^{}{}_{n1}{}^{}+D_{}^{}{}_{n2}{}^{}),`$
$`6C_{n1}={\displaystyle \frac{v_{0}^{}{}_{}{}^{2}}{2}}(D_{}^{}{}_{n}{}^{}2D_{}^{}{}_{n1}{}^{}+D_{}^{}{}_{n2}{}^{})+{\displaystyle \frac{\lambda }{4}}{\displaystyle \frac{v_{0}^{}{}_{}{}^{4}}{k^2}}(E_{n2}2D_{n1}),`$ (12)
where

$`D_n={\displaystyle \underset{m=0}{\overset{n}{}}}{\displaystyle \frac{d_{2n2m+1}d_{2m+1}}{(2n2m+1)!(2m+1)!}},D_{}^{}{}_{n}{}^{}={\displaystyle \underset{m=0}{\overset{n}{}}}{\displaystyle \frac{d_{2n2m+1}d_{2m+1}}{(2n2m)!(2m)!}},`$
$`C_n={\displaystyle \underset{m=0}{\overset{n}{}}}{\displaystyle \frac{c_{2n2m+1}c_{2m+1}}{(2n2m+1)!(2m+1)!}},E_n={\displaystyle \underset{m=0}{\overset{n}{}}}D_{nm}D_m.`$ (13)
The first few terms, $`(c_1,d_1),(c_3,d_3)`$, are explicitly given as

$`d_1=\pm {\displaystyle \frac{\sqrt{2}}{v_0k}}\sqrt{\mathrm{\Lambda }+{\displaystyle \frac{\lambda v_{0}^{}{}_{}{}^{4}}{4}}},c_1={\displaystyle \frac{2}{3k^2}}(\mathrm{\Lambda }+{\displaystyle \frac{\lambda v_{0}^{}{}_{}{}^{4}}{4}}),`$
$`{\displaystyle \frac{d_3}{d_1}}=2+{\displaystyle \frac{1}{k^2}}\{{\displaystyle \frac{8}{3}}(\mathrm{\Lambda }+{\displaystyle \frac{\lambda v_{0}^{}{}_{}{}^{4}}{4}})\lambda v_{0}^{}{}_{}{}^{2}\},{\displaystyle \frac{c_3}{c_1}}=2+{\displaystyle \frac{1}{k^2}}\{{\displaystyle \frac{16}{3}}(\mathrm{\Lambda }+{\displaystyle \frac{\lambda v_{0}^{}{}_{}{}^{4}}{4}})2\lambda v_{0}^{}{}_{}{}^{2}\},`$ (14)
where $`\pm `$ sign in $`d_1`$ reflects $`\mathrm{\Phi }\mathrm{\Phi }`$ symmetry in (4) and (5). We take the positive one in the following. We can confirm that the above relations, (12) and (14), determine all $`c`$’s and $`d`$’s recursively in the order of increasing $`n`$. This is because eq.(12) is the coupled linear equation with respect to ($`c_{2n+1},d_{2n+1}`$) when lower-order $`c^{}`$s and $`d^{}`$s are regarded as obtained quantities. (Note: $`D_n^{}=\frac{2d_1}{(2n)!}d_{2n+1}+`$lower-order terms, $`D_n=\frac{2d_1}{(2n+1)!}d_{2n+1}+`$lower-order terms, $`C_n=\frac{2c_1}{(2n+1)!}c_{2n+1}+`$lower-order terms, $`E_n=\frac{8d_{1}^{}{}_{}{}^{3}}{(2n+1)!}d_{2n+1}+`$lower-order terms. ) All coefficients are solved and are described by the three dimensionless vacuum parameters:
$`(\mathrm{\Lambda }+\frac{\lambda v_{0}^{}{}_{}{}^{4}}{4})/k^2M^3,\lambda v_{0}^{}{}_{}{}^{2}/k^2,v_{0}^{}{}_{}{}^{2}/M^3`$.

In order for this solution to make sense, as seen from the expression for $`d_1`$, the 5D cosmological term $`\mathrm{\Lambda }`$ should be bounded also from below, in addition to from above.

$`{\displaystyle \frac{\lambda v_{0}^{}{}_{}{}^{4}}{4}}<\mathrm{\Lambda }<0.`$ (15)
At this stage the two constraints (11) are not taken into account. These impose some relations between vacuum parameters which will be explained in Sec.7.

## 4 Vacuum parameters: $`M`$ and $`k`$-dependence in the dimensional reduction

Let us examine the behaviour of the vacuum parameters ($`\mathrm{\Lambda },v_0,\lambda `$) near the 4D world: $`k\mathrm{}`$(the dimensional reduction). This should be taken consistently with (10). We will specify the above limit in the more well-defined way later. We take the following assumption which will be later checked using the final solution,

$`{\displaystyle \frac{c_{2n+1}}{c_1}}O(k^0)\times O(n^0),{\displaystyle \frac{d_{2n+1}}{d_1}}O(k^0)\times O(n^0),`$
$`\text{as}k\mathrm{},n\mathrm{},`$ (16)
where $`O(k^0)`$ and $`O(n^0)`$ are some constants of order $`k^0`$ and $`n^0`$. $`O(n^0)`$ behaviour for $`n\mathrm{}`$ is a sufficient condition for the convergence of the infinite series (9). Then the expressions (9) has the following asymptotic form, as $`k\mathrm{}`$.

$`\sigma ^{}(y)kc_1\times \theta (ky)\times \text{const}={\displaystyle \frac{2}{3k}}(\mathrm{\Lambda }+{\displaystyle \frac{\lambda v_{0}^{}{}_{}{}^{4}}{4}})\theta (ky)\times \text{const},`$
$`\mathrm{\Phi }(y)v_0d_1\times \theta (ky)\times \text{const}={\displaystyle \frac{\sqrt{2}}{k}}\sqrt{\mathrm{\Lambda }+{\displaystyle \frac{\lambda v_{0}^{}{}_{}{}^{4}}{4}}}\theta (ky)\times \text{const},`$ (17)
where $`\theta (y)`$ is the step function: $`\theta (y)=1`$ for $`y>0`$,$`\theta (y)=1`$ for $`y<0`$. (Note: $`(\mathrm{tanh}ky)^{2n+1}\theta (ky),k\mathrm{}`$.) Taking relations (6) and (8) into account, (17) means $`\lambda v_{0}^{}{}_{}{}^{4}\mathrm{\Lambda }k\sqrt{\mathrm{\Lambda }}k^2v_{0}^{}{}_{}{}^{2}`$. These relations say

$`\mathrm{\Lambda }M^3k^2,v_0M^{3/2},\lambda M^3k^2\text{as}k\mathrm{}.`$ (18)
These are leading behaviour of the vacuum parameters in the dimensional reduction. The first one above is given in the original . The more precise forms of (18) will be obtained, in Sec.7, using the constraints (11).

## 5 Parameter fitting

In order to express some physical scales in terms of the fundamental parameters $`M`$, $`k`$ and $`r_c`$( to be introduced soon), we consider the case that the 4D geometry is slightly fluctuating around the Minkowski (flat) space.

$`ds^2=\mathrm{e}^{2\sigma (y)}g_{\mu \nu }(x)dx^\mu dx^\nu +dy^2,g_{\mu \nu }=\eta _{\mu \nu }+h_{\mu \nu },h_{\mu \nu }O({\displaystyle \frac{1}{k}}).`$ (19)
The leading order $`O(k^0)`$ results of the previous section remain valid.

### 5.1 The Planck mass

The gravitational part of 5D action (1) reduces to 4D action as

$`{\displaystyle d^5X\sqrt{G}M^3\widehat{R}}M^3{\displaystyle _{r_c}^{r_c}}𝑑y\mathrm{e}^{2\sigma (y)}{\displaystyle d^4x\sqrt{g}R}+\mathrm{},`$ (20)
where the infrared regularization parameter $`r_c`$ is introduced. $`r_c`$ specifies the length of the extra axis. Using the asymptotic forms, $`\sigma (y)\omega |y|`$ as $`y\pm \mathrm{}`$ and $`\omega =\sqrt{\frac{\mathrm{\Lambda }}{6}}M^{\frac{3}{2}}k`$ as $`k\mathrm{}`$, we can evaluate the order of $`M_{pl}`$ as

$`M_{pl}^{}{}_{}{}^{2}M^3{\displaystyle _{r_c}^{r_c}}𝑑y\mathrm{e}^{2\omega |y|}={\displaystyle \frac{M^3}{\omega }}(1\mathrm{e}^{2\omega r_c}){\displaystyle \frac{M^3}{k}},`$ (21)
where we have used the 4D reduction condition:

$`kr_c1.`$ (22)
The result (21) is again same as in . The above condition should be interpreted as the precise (well regularized) definition of $`k\mathrm{}`$ used so far. We note $`r_c`$ dependence in (21) is negligible for $`kr_c1`$. This behaviour shows the distinguished contrast with the Kaluza-Klein reduction ($`M_{pl}^{}{}_{}{}^{2}M^3r_c`$) as stressed in .

### 5.2 The cosmological term

The cosmological part of (1) reduces to 4D action as

$`{\displaystyle d^5X\sqrt{G}\mathrm{\Lambda }}\mathrm{\Lambda }{\displaystyle _{r_c}^{r_c}}𝑑y\mathrm{e}^{4\sigma (y)}{\displaystyle d^4x\sqrt{g}}\mathrm{\Lambda }_{4d}{\displaystyle d^4x\sqrt{g}},`$
$`\mathrm{\Lambda }_{4d}{\displaystyle \frac{\mathrm{\Lambda }}{2\omega }}(1\mathrm{e}^{4\omega r_c})M^3k<0,kr_c1.`$ (23)
$`\mathrm{\Lambda }_{4d}`$ is the cosmological term in the 4D space-time. It does not, like $`M_{pl}`$, depend on $`r_c`$ strongly. The result says the 4D space-time should also be anti de Sitter.

### 5.3 Numerical fitting

Let us examine what orders of values should we take for the fundamental parameters $`M`$ and $`k`$. ( $`r_c`$ is later fixed by the information of the 4D fermion masses. ) Using the value $`M_{pl}10^{19}`$GeV , the ”rescaled” cosmological parameter $`\stackrel{~}{\mathrm{\Lambda }}_{4d}\mathrm{\Lambda }_{4d}/M_{pl}^{}{}_{}{}^{2}`$  has the relation:

$`\sqrt{\stackrel{~}{\mathrm{\Lambda }}_{4d}}kM^3\times 10^{38}\text{GeV},`$ (24)
where the relations (21) and (23) are used. The unit of $`M`$ is GeV and this mass unit is taken in the following. The observed value of $`\stackrel{~}{\mathrm{\Lambda }}_{4d}`$ is not definite, even for its sign. If we take into account the quantum effect, the value of $`\stackrel{~}{\mathrm{\Lambda }}_{4d}`$ could run along the renormalization. Furthermore if we consider the parameter $`\stackrel{~}{\mathrm{\Lambda }}_{4d}`$ represents some ”effective” value averaging over all matter fields, the value, no doubt, changes during the evolution of the universe. (Note the model (1) has no (ordinary) matter fields.) Therefore, instead of specifying $`\stackrel{~}{\mathrm{\Lambda }}_{4d}`$, it is useful to consider various possible cases of $`\stackrel{~}{\mathrm{\Lambda }}_{4d}k^2`$. Some typical cases are 1) ($`k=10^{41},M=0.1`$), 2) ($`k=10^{13},M=10^8`$) 3) ($`k=10,M=10^{13}`$) 4) ($`k=10^4,M=10^{14}`$) and 5) ($`k=10^{19},M=10^{19}`$). Case 1) gives the most plausible present value of the cosmological constant. The wall thickness $`1/k=10^{41}`$\[GeV<sup>-1</sup>\] , however, is the radius of the present universe. This implies the extra dimensional effect appears at the cosmological scale, which should be abandoned. Case 2) gives $`1/k=10^{13}`$ GeV<sup>-1</sup> $`1`$mm which is the minimum length at which the Newton’s law is checked. Usually $`k`$ should be larger than this value so that we keep the observed Newton’s law. 5) is an extreme case $`M=M_{pl}`$. The fundamental scale $`M`$ is given by the Planck mass. In this case, $`r_c1/k=1/M_{pl}`$ is acceptable, while $`\sqrt{\stackrel{~}{\mathrm{\Lambda }}_{4d}}M_{pl}`$ is completely inconsistent with the experiment and requires explanation. Most crucially the condition (10) breaks down. Cases 3) and 4) are some intermediate cases which are acceptable except for the cosmological constant. They will be used in Sec.8. At present any choice of ($`k,M`$) looks to have some trouble if we take into account the cosmological constant. We consider the observed cosmological constant ($`10^{41}`$GeV) should be explained by some unknown mechanism. (No successful explanation of the small cosmological constant exists . Ordinarily (without fine-tuning) the quantum-loop correction leads to the case 5). Compared with case 5), the cases 3) and 4) should be regarded as ”much improved” cases in this respect.)

## 6 Domain wall in the chiral fermion problem

We point out the mechanism presented here has a strong similarity to that in the chiral fermion determinant. The interpretation of the extra axis only is the difference. The axis is regarded as a real (but hardly measurable) axis here, whereas it is a regularization axis in the chiral problem. The parameter correspondence is

Randal-Sundrum Chiral Fermion
$`k:\text{(thickness of the wall)}^1`$ $``$ $`M_F:\text{1+4 dim fermion mass or}`$
$`\text{(thickness of the wall)}^1`$
$`M:\text{fundamental scale}`$ $``$ $`1/t:\text{temperature or}`$
$`1/a:\text{(lattice spacing)}^1`$
$`r_c:\text{Infrared reg.}`$ $``$ $`1/|k^\mu |:\text{(4D fermion mom.)}^1\text{or}`$
$`=\text{size of the extra axis}`$ $`1/m_q:\text{(quark mass)}^1`$
The condition on $`k`$ in the RS model, from (10) and (22), is given as

$`{\displaystyle \frac{1}{r_c}}kM.`$ (26)
The corresponding one of the chiral fermion is given by

$`|k^\mu |M_F{\displaystyle \frac{1}{t}}.`$ (27)
Both conditions guarantee the mechanism effectively works.

It is known, in the lattice chiral fermion, the choice of the parameter $`M_F`$ is so important to produce a good numerical output, say, the pion mass( where $`M_F`$ is denoted as $`M_5`$ and is called ”domain wall height”). Only for well-chosen value of $`M_F`$, the chiral properties are controlled. In this analogy the thickness parameter $`k`$, in the RS model, is considered to be a key quantity for controlling the whole configuration and for fitting with the real world quatities such as fermion masses.

The line element of (2) or (19) for a fixed $`y`$ is the Weyl scaling $`g_{\mu \nu }(x)\mathrm{e}^{2\sigma (y)}g_{\mu \nu }(x)`$ of the 4D world: $`(ds^2)_{4D}=g_{\mu \nu }(x)dx^\mu dx^\nu `$. $`\sigma (y)`$ is related to the 4D dynamics through the 5D geometrical setting. The extra dimension $`y`$ plays the role of the scaling parameter. On the other hand, in the chiral problem, the extra axis can be regarded as the Schwinger’s proper time (inverse temperature) $`t`$ through the relation :

$`({\displaystyle \frac{}{t}}+\widehat{D})G(x,y;t)=0,G(x,y;t)=<x|\mathrm{e}^{t\widehat{D}}|y>,`$ (28)
where $`\widehat{D}`$ is the general 4D operator and $`G(x,y;t)`$ is the density matrix. Formally it says $`\frac{G}{t}G^1=\frac{}{t}\mathrm{ln}G=\widehat{D}`$. This shows the scaling property of $`\mathrm{ln}G`$ along the coordinate $`t`$. These similar roles of $`y`$ and $`t`$ strongly indicate the both mechanisms are essentially the same.

In the view of , the ”direction” of the system evolvement of the present model is given by the sign change of the 5D Higgs field around the origin $`y=0`$.

As in the Callan and Harvey’s paper, we can have the 4D massless chiral fermion bound to the wall by introducing 5D Dirac fermion $`\psi `$ into (1).

$`S[G_{AB},\mathrm{\Phi }]+{\displaystyle d^5X\sqrt{G}(\overline{\psi }\text{ }\text{/}\text{ }\psi +g\mathrm{\Phi }\overline{\psi }\psi )}.`$ (29)
If we regulate the extra axis by the finite range $`r_cyr_c`$, the 4D fermion is expected to have a small mass $`m_fk\mathrm{e}^{kr_c}`$ (This is known for the two-walls case in ). If we take the case 3) in Subsec.5.3 ($`k=10,M=10^{13}`$) and regard the 4D fermion as a neutrino ($`m_\nu 10^{11}10^9\text{GeV}`$), we obtain $`r_c=2.762.30\text{GeV}^1`$. If we take case 4) ($`k=10^4,M=10^{14}`$), we obtain $`r_c=(3.452.99)\times 10^3\text{GeV}^1`$. When the quarks or other leptons ($`m_q,m_l10^310^2\text{GeV}`$) are taken as the 4D fermion, and take the case 4) in Subsec.5.3, we obtain $`r_c=(1.610.461)\times 10^3`$GeV<sup>-1</sup>. It is quite a fascinating idea to identify the chiral fermion zero mode bound to the wall with the neutrinos, quarks or other leptons.

## 7 Precise form of vacuum parameters

As shown in (18), an interesting aspect of the present solution is that some family of vacua is selected as the consistent (classical) configuration. Let us determine the precise form of (18) using the two constraints (11). In terms of new parameters $`\mathrm{\Omega }\mathrm{\Lambda }+\frac{\lambda }{4}v_{0}^{}{}_{}{}^{4}(0<\mathrm{\Omega }<\frac{\tau }{4}v_{0}^{}{}_{}{}^{2}),\tau \lambda v_{0}^{}{}_{}{}^{2}`$, instead of $`\mathrm{\Lambda }`$ and $`\lambda `$, the precise forms are obtained by the $`\frac{1}{k^2}`$-expansion for the case $`kr_c1`$ as

$`\mathrm{\Omega }=M^3k^2(\alpha _0+{\displaystyle \frac{\alpha _1}{(kr_c)^2}}+\mathrm{})=M^3k^2{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{\alpha _n}{(kr_c)^{2n}}},`$
$`\tau =k^2(\gamma _0+{\displaystyle \frac{\gamma _1}{(kr_c)^2}}+\mathrm{})=k^2{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{\gamma _n}{(kr_c)^{2n}}},`$
$`v_0=M^{3/2}(\beta _0+{\displaystyle \frac{\beta _1}{(kr_c)^2}}+\mathrm{})=M^{3/2}{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{\beta _n}{(kr_c)^{2n}}},`$ (30)
where $`\alpha `$’s,$`\gamma `$’s and $`\beta `$’s are some numerical (real) numbers to be consistently chosen using (11). If we assume the relation (16), the infinite series of (11) can be safely truncated at the first few terms. In order to demonstrate how the vacuum parameters are fixed, we take into account up to $`n=2`$ in (11) and up to $`O(1/(kr_c)^{2\times 2})`$ in (30). For general $`M,k,r_c`$ except the condition $`kr_c1`$, the coefficients are determined as

$`\text{Vacuum 1:}(\alpha _0,\alpha _1,\alpha _2)(1,0,0)\text{input}`$
$`(\beta _0,\beta _1,\beta _2;\gamma _0,\gamma _1,\gamma _2)=(1.6,0,0;4.2,0,0),`$
$`\text{Vacuum 2:}(\alpha _0,\alpha _1,\alpha _2)(1,1,0)\text{input}`$
$`(\beta _0,\beta _1,\beta _2;\gamma _0,\gamma _1,\gamma _2)=(1.6,1.1,0.67;4.2,1.8,1.7),`$
$`\text{Vacuum 3:}(\alpha _0,\alpha _1,\alpha _2)(1,1,1)\text{input}`$
$`(\beta _0,\beta _1,\beta _2;\gamma _0,\gamma _1,\gamma _2)=(1.6,1.1,0.45;4.2,1.8,3.5).`$ (31)
We notice our solution has one free parameter for each $`n`$-th set ($`\alpha _n,\beta _n,\gamma _n`$). This is because the number of constraints for $`c^{}`$s and $`d^{}`$s is two (11), whereas that of quantities to be determined is three (30). Using this freedom we can adjust one of the three vacuum parameters in the way the observed physical values are explained. In (31), we take $`\alpha `$’s as the input. Taking the value $`kr_c=10`$, Vac.3 has the vacuum expectation value $`v_0M^{3/2}=1.6`$, the cosmological constant $`\mathrm{\Lambda }k^2M^3=1.7`$ and the coupling $`\lambda k^2M^3=1.6`$. Other vacua have almost the same values because the first order term dominate in (30) for the thin wall case $`kr_c1`$. We notice the dimensionless vacuum parameters, $`v_0M^{3/2},\mathrm{\Lambda }k^2M^3`$ and $`\lambda k^2M^3`$, are specified only by the value of $`kr_c`$ and the input data, say, $`\alpha ^{}`$s. If we specify $`k`$ and $`M`$, as considered in Subsec 5.3, the values $`v_0,\mathrm{\Lambda }`$ and $`\lambda `$ are obtained. Any higher-order, in principle, can be obtained by the $`\frac{1}{k^2}`$-expansion.

For the Vac.3, we plot $`\mathrm{\Phi }(y)`$ and $`\mathrm{\Phi }^{}(y)`$ for two cases $`kr_c=10`$ and $`kr_c=20`$ in Fig.2.

## 8 Discussion and conclusion

The assumption used in the present explanation is (16) only. The first some values in the series of $`n`$$`(c_3/c_1,d_3/d_1)=(1.05,0.48),(c_5/c_1,d_5/d_1)=(11.9,0.90)`$ for Vac.3 with $`kr_c=10`$ indicate its validity. Another evidence of the (strong) convergence is the fact that the normalization in Fig.2 is quite correctly reproduced.

If we take the boundary condition: $`\mathrm{\Phi }(y)v_0,y\pm \mathrm{}`$, instead of (6), the opposite chirality solution is obtained. Both of the pair, $`+`$ and $``$ chiralities, are indispensable when the ”vector-like” or non-chiral theory, such as QCD, is taken into account.

One of the fundamental parameters, $`r_c`$, is introduced in Sec.5 and 6 as the infrared regularization. This is quite natural in the standpoint of the discretized approach such as lattice. The treatment, however, should be regarded as an ”effective” approach or a ”temporary” stage of the unknown right treatment. The scale $`r_c`$ should be introduced naturally in the continuum approach. If we can generalize the present analysis to the case of the $`S^1/Z_2`$ extra space (two-walls case), $`r_c`$ is interpreted as the distance between the two walls . Another interesting possibility is that the scale $`r_c`$ could be given by some (at present) unknown mechanism in the space-time manifold such as the non-commutative geometry. It also looks that the AdS/CFT view of the present model could give a clue to the problem.

An important task to establish the RS scenario is to introduce the standard electro-weak model (chiral), QCD (non-chiral) and SUSY theories into this scheme. Recently the bulk standard model has been examined by . In  a supersymmetric extension is examined. The RS model has given us richer possibilities for the mass hierarchy problem than before. It is hoped that the future experiments can select them.

Acknowledgment

The author thanks G.W.Gibbons for much discussions about the RS-model. Especially eq.(7) was pointed out by him. The author also thanks M.Yamaguchi for some comment.


text:
# QUIP—A Tool for Computing Nonmonotonic Reasoning TasksThis work was partially supported by the Austrian Science Fund Project N Z29-INF.

## General Information

Designing theorem provers for nonmonotonic reasoning formalisms is challenged by the increased computational complexity compared to the inherent complexity of classical reasoning. As is well-known (????), the main reasoning tasks for almost all propositional nonmonotonic logics are either $`\mathrm{\Sigma }_2^p`$-complete or $`\mathrm{\Pi }_2^p`$-complete, i.e., they are located at the second level of the polynomial hierarchy, whereas classical reasoning resides at the first level of that hierarchy.

Important constituents in establishing the $`\mathrm{\Sigma }_2^p`$-completeness results for the different nonmonotonic reasoning tasks are so-called quantified boolean formulae (QBFs), which generalize ordinary propositional formulae by the admission of quantifiers ranging over propositional variables. To wit, demonstrating $`\mathrm{\Sigma }_2^p`$-hardness of a given nonmonotonic decision problem, say nmp, is usually achieved by reducing the problem $`\text{qsat}_2`$ to nmp, where $`\text{qsat}_2`$ is the problem of deciding the truth of QBFs being in prenex normal-form whose leading quantifiers are ordered like $`PQ`$ ($`P,Q`$ are lists of propositional variables), which is complete for $`\mathrm{\Sigma }_2^p`$. (In general, for any class $`\mathrm{\Sigma }_i^p`$, $`i1`$, there is a corresponding decision problem, $`\text{qsat}_i`$, complete for $`\mathrm{\Sigma }_i^p`$, whose task is to check the truth of QBFs of the form $`P_1P_2\mathrm{}P_{n1}P_n\mathrm{\Phi }`$, where $`P_1,\mathrm{},P_n`$ are lists of propositional variables and $`\mathrm{\Phi }`$ is a propositional formula.) More precisely, $`\mathrm{\Sigma }_2^p`$-hardness of nmp is shown by constructing a (polynomial) transformation $`𝒮`$ such that for every instance $`I`$ of $`\text{qsat}_2`$ it holds that $`I`$ is a yes-instance of $`\text{qsat}_2`$ iff $`𝒮(I)`$ is a yes-instance of nmp.

Now, given the membership of a nonmonotonic reasoning task nmp in the class $`\mathrm{\Sigma }_2^p`$, and from the $`\mathrm{\Sigma }_2^p`$-hardness of $`\text{qsat}_2`$, it follows immediately that every such decision problem nmp can be reduced to $`\text{qsat}_2`$, i.e., there is a (polynomial) transformation $`𝒯`$ such that for every instance $`I`$ of nmp it holds that $`I`$ is a yes-instance of nmp iff $`𝒯(I)`$ is a yes-instance of $`\text{qsat}_2`$.

In this paper, we describe the prototype system QUIP (??), an automated reasoning tool utilizing transformations of the latter kind to implement several different reasoning formalisms. The basic idea is to employ *existing sophisticated theorem provers for quantified boolean formulae*, taking care of evaluating the resultant instances of $`\text{qsat}_2`$.

At present, QUIP handles the following propositional nonmonotonic reasoning approaches:

* abduction;
* autoepistemic logic;
* default logic;
* disjunctive stable model semantics;
* circumscription.

The system has been implemented in C using standard tools like LEX and YACC (comprising a total of 2000 lines of code, excluding the used QBF-solver); it runs currently in a Unix environment (Sun/Solaris and Linux), but is easily portable to other operating systems as well.

The use of QBFs expressing advanced reasoning tasks has been advocated in (??) and is a natural generalization of a similar method applied for problems in NP. Such problems are often solved by a reduction to sat, the satisfiability problem of classical propositional logic, which is NP-complete (see, e.g., (??)). Besides the applications discussed in this paper, a reduction of planning problems to QBFs has been given in (?).

In general, since the evaluation of *arbitrary* QBFs is PSPACE-complete (in contrast to the $`\mathrm{\Sigma }_i^p`$-completeness of the restricted QBFs mentioned above), in principle *any* formalism having a decision problem in PSPACE can be handled by QUIP, provided a proper transformation has been found.

The next section outlines the overall architecture of QUIP and gives some background information on the different reasoning tasks implemented in QUIP. Then, the usability of the approach is described. The last section contains a discussion on benchmark problems and a comparison with other implementations.

## Description of the System

### System Architecture

The overall architecture of QUIP is depicted in Figure 1. QUIP consists of three parts, namely the filter program, the QBF-evaluator boole, and the output interpreter int.

The input filter translates the given problem description (e.g., a default theory, a disjunctive logic program, an abductive problem, etc.) into a quantified boolean formula, which is then sent to the QBF-evaluator boole. The result of boole, usually a formula in disjunctive normal form (often called *sum of products*, SOP), is interpreted by int. The latter part associates a meaningful interpretation to the formulae occurring in SOP and provides an explanation in terms of the underlying problem instance (e.g., an extension, a stable model, abductive explanations, etc.). The interpretation relies on a mapping of internal variables of the generated QBF into concepts of the problem description which is provided by filter.

The QBF-evaluator boole is a commonly available propositional theorem prover based on *binary decision diagrams* (BDDs) (?).111For a comparison between different BDD packages, cf. (?). We chose to use this particular tool because of several reasons. For one, the program, together with its source code, is in the public domain and can be downloaded from the web (see http://www.cs.cmu.edu/$``$modelcheck/bdd.html). Second, it represents a sophisticated reasoning engine with several years of development. Third, it does not require of the input formula to be in a specific normal form. The latter point distinguishes boole from other QBF-solvers, like those proposed in (??), which operate on formulae being in *prenex conjunctive normal form*. Although these provers can in principle also be employed in QUIP, their inclusion would require an additional normal form translation, since the “natural” reductions of nonmonotonic reasoning tasks to QBFs do in general *not* result in formulae being in a particular normal form.

In order to incorporate new formalisms into QUIP, one has to extend the filter program responsible for the appropriate reductions, the mapping of the variables, and the interpreter int. The deductive engine remains unchanged in this process.

### Implemented Reasoning Tasks

In this subsection, we briefly discuss the different reasoning tasks currently implemented in QUIP. We will not present the concrete transformations into QBFs expressing these tasks; details are given in (?).

All formalisms processed by QUIP are propositional. In what follows, we assume a propositional language $``$ generated by a finite set of propositional variables $`V`$ using the standard sentential connectives $`\neg `$, $``$, $``$, $``$, and $``$. A theory is a finite set $`T`$, which will be identified with the formula $`_{\varphi T}\varphi `$.

Note that, strictly speaking, the different decision problems presented below return either *yes* or *no*, but usually one is more interested in the corresponding *function problem* returning the actual objects responsible for a *yes* answer (like the extensions of a default theory, the stable models of a logic program, etc.). QUIP permits queries of this form, by engaging the so-called *detail mode* (see discussion below).

#### Abduction.

Classical abduction from a theory $`T`$ on $`V`$ may be defined as follows (???). Let $`HV`$ be a set of hypotheses, and let $`pV`$ be a distinguished atom. A subset $`EH`$ is an abductive explanation for $`p`$ from $`T`$ and $`H`$, if

$`TE`$ is consistent, and

$`TEp`$, i.e., $`TE`$ logically implies $`p`$.

An explanation $`E`$ is minimal, if no proper subset $`E^{}E`$ is an abductive explanation.

The following tasks are implemented in QUIP:

* Given a theory $`T`$, a set $`H`$ of variables, and an atom $`p`$. Is there a (minimal) abductive explanation $`EH`$ for $`p`$ from $`T`$ and $`H`$?
* The *relevance problem*: Given a theory $`T`$, a set $`H`$ of variables, an atom $`p`$, and some hypothesis $`hH`$. Is there a (minimal) abductive explanation $`EH`$ for $`p`$ from $`T`$ and $`H`$ containing $`h`$?
* The *necessity problem*: Given a theory $`T`$, a set $`H`$ of variables, an atom $`p`$, and some hypothesis $`hH`$. Does $`h`$ occur in every (minimal) abductive explanation $`EH`$ for $`p`$ from $`T`$ and $`H`$?

#### Autoepistemic logic.

The language of Moore’s autoepistemic logic (?) contains the modal operator $`L`$, where $`L\varphi `$ intuitively means that $`\varphi `$ is believed. By $`_L`$ we denote the language $``$ extended by $`L`$. Formulae $`L\varphi `$ are viewed as propositional variables, which are called modal atoms.

A *stable expansion* of an autoepistemic theory $`T_L`$ is a set $`E_L`$ such that

$$E=Th(T\{L\varphi \varphi E)\{\neg L\varphi \varphi E\}),$$

where $`Th()`$ is the classical consequence operator with respect to the extended language $`_L`$.

QUIP handles the following tasks:

* Given an autoepistemic theory $`T_L`$, is there a stable expansion $`E`$ of $`T`$?
* *Brave reasoning*: Given an autoepistemic theory $`T_L`$ and some formula $`\mathrm{\Phi }`$, is there a stable expansion $`E`$ of $`T`$ containing $`\mathrm{\Phi }`$?
* *Skeptical reasoning*: Given an autoepistemic theory $`T_L`$ and some formula $`\mathrm{\Phi }`$, is $`\mathrm{\Phi }`$ contained in every stable expansion $`E`$ of $`T`$?

For brave and skeptical reasoning, if the detail mode is engaged, QUIP returns *witnesses* corresponding to theses tasks: for brave reasoning, all stable expansions containing $`\mathrm{\Phi }`$ are returned, whereas for skeptical reasoning, all stable expansions *not* containing $`\mathrm{\Phi }`$ are returned.

#### Default logic.

A *default theory* is a pair $`\mathrm{\Delta }=(T,D)`$, where $`T`$ is a set of formulae and $`D`$ is a set of *defaults* of the form $`\frac{\alpha :\beta }{\gamma }`$.222For simplicity, we omit multiple justifications here. Intuitively, the default is applied ($`\gamma `$ is concluded) if $`\alpha `$ is provable and the justification $`\beta `$ can be consistently assumed.

The semantics of $`\mathrm{\Delta }=(T,D)`$ is defined in terms of *extensions* (?). Following (?), extensions can be characterized thus. For any $`S`$, let $`D(S)`$ be the monotonic rules $`\{\frac{\alpha }{\gamma }\frac{\alpha :\beta }{\gamma }D,\neg \beta S\}`$. Then, $`E`$ is an extension of $`\mathrm{\Delta }`$ iff $`E=Th^{D(E)}(T)`$, where $`Th^{D(E)}(T)`$ is the set of all formulae derivable from $`T`$ using classical logic together with the rules from $`D(E)`$.

QUIP expresses the following reasoning tasks:

* Given a default theory $`\mathrm{\Delta }`$, is there an extension $`E`$ of $`\mathrm{\Delta }`$?
* *Brave reasoning*: Given a default theory $`\mathrm{\Delta }`$ and some formula $`\mathrm{\Phi }`$, is there an extension $`E`$ of $`\mathrm{\Delta }`$ containing $`\mathrm{\Phi }`$?
* *Skeptical reasoning*: Given a default theory $`\mathrm{\Delta }`$ and some formula $`\mathrm{\Phi }`$, is $`\mathrm{\Phi }`$ contained in every extension $`E`$ of $`\mathrm{\Delta }`$?

As for stable expansions, QUIP returns witnesses if the detail mode is engaged. Moreover, each of these reasoning tasks has been implemented in terms of two independent transformations: The first category of reductions is based on the characterization of extensions discussed above; the second category is based on a characterization of extensions using the notion of a *full set* (?). Interestingly, although the transformations based on the latter method are more succinct than the corresponding reductions of the first kind, they have often an inferior performance compared to the former transformations.

#### Disjunctive Logic Programming.

A *disjunctive logic program*, $`\mathrm{\Pi }`$, is a set of rules

$$r:H(r)P(r),N(r)$$

where $`H(r)`$ is a disjunction of variables, $`P(r)`$ is a conjunction of variables, and $`N(r)`$ is a conjunction of negated variables. A Herbrand interpretation $`I`$ of $`V`$ is a stable model of $`\mathrm{\Pi }`$ (??), if it is a minimal model (with respect to set-inclusion) of the program $`\mathrm{\Pi }^I`$ resulting from $`\mathrm{\Pi }`$ as follows: remove each rule $`r`$ such that $`Ia`$ for some $`\neg a`$ in $`N(r)`$, and remove $`N(r)`$ from all remaining clauses.

Similar to autoepistemic logic and default logic, QUIP handles the problem whether a given logic program has a stable model, as well as brave and skeptical reasoning.

#### Circumscription.

In contrast to the formalisms described above, propositional circumscription is already a quantified boolean formula, hence it does not require a separate reduction. So, QUIP can handle circumscription in a straightforward way.

In the propositional case, the parallel circumscription of a set of atoms $`P=\{p_1,\mathrm{},p_n\}`$ in a theory $`T`$, where the atoms $`Q`$ are fixed and the remaining atoms $`Z=\{z_1,\mathrm{},z_m\}=V(PQ)`$ may vary, is given by the following QBF $`\mathrm{𝐶𝐼𝑅𝐶}(T;P,Z)`$, cf. (?):

$$TP^{}Z^{}\left((T[P/P^{},Z/Z^{}](P^{}P))(PP^{})\right).$$

Here, $`P^{}=\{p_1^{},\mathrm{},p_n^{}\}`$ and $`Z^{}=\{z_1^{},\mathrm{},z_m^{}\}`$ are sets of new propositional variables corresponding to $`P`$ and $`Z`$, respectively, and $`T[P/P^{},Z/Z^{}]`$ results from $`T`$ by substitution of the variables in $`P^{}Z^{}`$ for those in $`PZ`$. QUIP implements circumscriptive inference of a formula $`\varphi `$ from $`T`$, which is expressed by the QBF

$$V(\mathrm{𝐶𝐼𝑅𝐶}(T;P,Z)\varphi ).$$

## Applying the System

### Methodology

One of the basic motivations for the development of QUIP was to make a rapid prototyping tool available, aimed for experimenting with different knowledge-representation formalisms. Accordingly, QUIP is designed in such a way that the important reasoning tasks corresponding to the different formalisms under consideration can be directly encoded as queries. So, the methodology of specifying queries suitable to be processed by QUIP is the same as the methodology of formalizing a particular problem with one of the formalisms implemented in QUIP (subject to the restriction, of course, that QUIP currently accepts only queries specified over a propositional language; but in a future version it is planned to extend the language to allow function-free formulae with variables as well.)

### Specifics

Let us illustrate how the queries of QUIP are structured. Generally, QUIP takes an input file as argument and writes the output to standard-out:

> quip input\_file

The input file comprises nonmonotonic theories and specifications of reasoning tasks. The format of the input uses two major concepts: *definitions* and *commands*. In the definitions, one can specify abductive theories, autoepistemic theories, default theories, logic programs, and propositional theories in general. The commands specify which reasoning tasks (with respect to the chosen formalism) have to be executed. Theories and formulas can be nested by using suitable names, so definitions can be edited rather conveniently. Further, commands can refer to specified theories without the need to describe them more than once. An input file can contain several definitions and commands, even referring to different formalisms.

In the following we describe some of these features using a simple example from default logic. Consider the following default theory $`\mathrm{\Delta }=(T,D)`$, representing the well-known Nixon-diamond:

$`T`$ $`=`$ $`\{\text{Republican},\text{Quaker}\};`$
$`D`$ $`=`$ $`\{{\displaystyle \frac{\text{Republican}:\neg \text{Pacifist}}{\neg \text{Pacifist}}},{\displaystyle \frac{\text{Quaker}:\text{Pacifist}}{\text{Pacifist}}}\}.`$
This default theory has two extensions:

> $`Th(\{\text{Republican},\text{Quaker}\}\{\neg \text{Pacifist}\})`$;
>
> $`Th(\{\text{Republican},\text{Quaker}\}\{\text{Pacifist}\})`$.

The extensions of this example can be computed by QUIP using the following input file, named nixon:

```
   @SET DETAIL
      T :=   Republican & Quaker
   @D D := { Republican : !Pacifist | !Pacifist,
             Quaker : Pacifist | Pacifist
           }

   @DL ( T ; @D D )

```

Executing the command

> quip nixon

results in the following output:

> Th( {(Republican)&(Quaker)} u {(Pacifist)} )
> Th( {(Republican)&(Quaker)} u {(!Pacifist)} )

The meaning of the different commands and definitions in the input file nixon can be explained as follows. First of all, the command @SET DETAIL invokes the detail mode, i.e., all extensions will be displayed. (Recall that QUIP admits the processing of both *decision problems* and *function problems*.) Choosing the command @UNSET DETAIL would have resulted in a simple yes/no answer.

The next tokens of the input file specify the constituents of the default theory $`\mathrm{\Delta }`$: T represents the background knowledge of $`\mathrm{\Delta }`$, and D contains the defaults. To avoid ambiguities, references to defaults always have to start with a special string “@D”. The logical operators are represented in the obvious way (“&” denotes conjunction, “!” negation, and “|” separates a default’s consequent from its justification).

The command @DL tells QUIP to compute the extensions of the specified default theory. To perform brave or skeptical reasoning, the input file nixon would be changed as follows:

```
   @SET DETAIL
      T :=   Republican & Quaker
   @D D := { Republican : !Pacifist | !Pacifist,
             Quaker : Pacifist | Pacifist
           }

   @SET BRAVE
   @DL ( W ; @D D ) |= Pacifist

   @SET SKEPTICAL
   @DL ( W ; @D D ) |= Pacifist

```

The @SET-commands switches between the two reasoning modes; “|=” is the symbol standing for the respective default consequence relations. The first command checks whether *Pacifist* is a brave consequence of $`\mathrm{\Delta }`$, the second commands checks skeptical consequence of *Pacifist* from $`\mathrm{\Delta }`$. Observe that it is permitted that an input file contains a sequence of reasoning tasks.

The output corresponding to the first command will be

> Th( {(Republican)&(Quaker)} u {(Pacifist)} )

while the second command displays the extensions from which *Pacifist* does *not* follow:

> Th( {(Republican)&(Quaker)} u {(!Pacifist)} )

### Users and Usability

Obviously, proper usage of QUIP depends on a potential user’s ability to express a given problem in terms of the implemented formalisms. However, a particular advantage of QUIP is that it incorporates several different knowledge representation formalisms. Hence, users have a *choice* selecting among different (yet closely related) approaches, singling out that particular formalism best suited for a specific purpose, or choosing a method based on a user’s personal preference (e.g., because he/she understands that particular approach best). As well, the problem can be represented with different methods *simultaneously*, specifying the instances of the resultant formalizations in a single input file, which can then be processed by QUIP requiring only one initial execution command.

## Evaluating the System

### Benchmarks

There are different approaches how systems handling knowledge representation formalisms can be evaluated. One is to perform comparisons taking into account the representational power of the implemented formalisms. That is to say, under such a comparison, one chooses some “natural” problems, encodes it with respect to the specific methodologies associated with the implemented formalisms, and uses the resultant instances as queries of the respective systems. So, basically, different systems are compared on the basis of (possibly) different representations *of the same problem*. However, to achieve a fair comparison, it is necessary that the experimenter is able to encode the given problem “in the best possible way” with respect to the particular formalisms. Also, incompatibilities of the underlying formalisms render comparisons between different systems often difficult.

Another possibility is to compare systems on problem classes *common* to each of the considered systems. Such a comparison is appropriate if different implementations of *the same formalism* are evaluated.

Since QUIP incorporates a wide array of different knowledge representation methods, comparisons with other implementations can in general be achieved employing the latter procedure.

Accepted benchmarks for nonmonotonic theorem provers have been realized by the well-known TheoryBase system (?). This test-bed provides encodings of various graph problems in terms of default theories or equivalent logic programs. However, the generated problems are at most NP-hard (or co-NP-hard, depending on the reasoning task), and thus do not take full advantage of the expressibility supported by the nonmonotonic formalisms. The only practically applied benchmark test utilizing a $`\mathrm{\Sigma }_2^p`$-hard problem is the strategic companies example carried out for testing the system dlv (?).

Here, we propose a straightforward method how $`\mathrm{\Sigma }_2^p`$-hard benchmark problems for propositional nonmonotonic reasoning formalisms can be generated. The idea is to use the class of problems establishing the $`\mathrm{\Sigma }_2^p`$-hardness of a formalism. Recall from our previous discussion that $`\mathrm{\Sigma }_2^p`$-hardness of a nonmonotonic formalism is usually demonstrated by constructing a (polynomial) transformation $`𝒮`$ mapping instances $`I`$ of $`\text{qsat}_2`$ (the evaluation problem of QBFs having quantifier order $``$) into instances $`𝒮(I)`$ of the considered nonmonotonic reasoning task, nmp, such that $`I`$ is a yes-instance of $`\text{qsat}_2`$ iff $`𝒮(I)`$ is a yes-instance of nmp. Thus, in some sense, the class of problems $`𝒮(I)`$ represents “worst-case” examples for the problem nmp, and therefore is particularly useful estimating the performance of a theorem prover solving the task nmp. Moreover, these problems are easily scalable by parameterizing different instances of $`\text{qsat}_2`$. An added feature of QUIP is that these examples provide at the same time a simple method for *testing* whether the implementation works correct, because QUIP turns instances $`𝒮(I)`$ of nmp back to instances $`𝒯(𝒮(I))`$ of $`\text{qsat}_2`$, satisfying the condition that $`I`$ is a yes-instance of $`\text{qsat}_2`$ iff $`𝒯(𝒮(I))`$ is a yes-instance of $`\text{qsat}_2`$. The next subsection describes comparisons between QUIP and some state-of-the-art provers on the basis of these benchmark problems.

### Comparison

We compare the default-logic module of QUIP with DeReS (?) and the logic-programming module of QUIP with dlv (?), using the class of examples discussed above. Space limits preclude a discussion on the structure of these problems; details can be found in the relevant literature (e.g., (????)). We do not include a comparison with smodels (?) here, because that system is currently not designed to handle $`\mathrm{\Sigma }_2^p`$-problems (a comparison between QUIP, DeReS, dlv, smodels, and Theorist (?), using examples from TheoryBase and some abduction problems, is given in (?)).

Results of the comparison are given Table 1. All tests have been performed on a SUN ULTRA 60 with 256MB RAM; the run-time is measured in seconds with an upper limit of 90sec (i.e., instances requiring a longer period are not displayed). The first group of entries gives the results for the disjunctive logic programming test; the second group gives the results for the default logic test; and the final row contains some measurements using instances of the corresponding abductive problem class. The respective input-QBFs have been randomly generated and are parameterized by the number $`k`$ of existential quantifiers (the number of variables was held fixed and was set to 20). Although the given results represent only a small sample, they do indicate that our *ad hoc* implementation performs sufficiently well.

### Problem Size

It is rather obvious that QUIP cannot compete with state-of-the-art implementations like dlv or smodels in terms of problem size. These tools are highly optimized systems developed with a particular semantics in mind, whereas the purpose of QUIP is to provide a *uniform* method dealing with several knowledge representation tasks at the same time. Under this perspective, and taking into account that QUIP utilizes at present no optimizations whatsoever, our results demonstrate that implementing nonmonotonic reasoning formalisms using reductions to quantified boolean formulae is a feasible approach. Moreover, the modular architecture of QUIP allows an easy scalability and parallelization, by using, e.g., several QBF-provers simultaneously, each of which with its own optimization method.