text:
# Faraday Rotation Effect of Intracluster Magnetic Field on Cosmic Microwave Background Polarization

## 1 Introduction

Various observations have revealed that clusters of galaxies are pervaded by the strong magnetic field of microgauss strength (e.g., see Kronberg (1994); Carilli, & Taylor (2001) for reviews and references therein). The multi-frequency Faraday-rotation measurements of polarized radio sources inside or behind a cluster have been used to estimate the magnetic field strength, combined with the X-ray data (Vallée, MacLeod, & Broten (1986); Kim, Tribble, & Kronberg (1991)). Recently, Clarke, Kronberg, & Böhringer (2001) have drawn a firm conclusion that an intracluster hot plasma is universally magnetized by $`110\mu `$G fields under the assumption of $`10100`$kpc field coherent scales, using $`16`$ normal low-$`z`$ ROSAT cluster sample selected to be free of unusual strong radio halos, widespread cooling flow and recent merger activity. However, except for a few cases such as some background rotation measures per square degree in the Coma cluster (Kim et al. (1990)), it is generally difficult to measure the angular profile of the magnetic field strength inside a cluster because of the lack of the number of radio sources available per cluster. The observations of cluster-wide diffuse radio halos have also led to the evidence of the microgauss field, which is believed to be synchrotron radiation by relativistic electrons accelerated in the shock wave. Moreover, in this case hard X-ray emission could be produced by the same relativistic electron population through the inverse Compton scattering of cosmic microwave background (CMB) photons. The combined observation of hard X-ray emission and radio halos is therefore very attractive in the sense that it allows us to directly estimate the magnetic field strength without further restrictive assumptions for the coherent length and the electron distribution. The recent detections of hard X-ray emission have led to an independent estimation of $`0.1\mu `$G fields even in the outer ($`\stackrel{>}{}1\mathrm{Mpc}`$) envelopes of clusters (Bagchi, Pislar, & Neto (1998); Rephaeli, Gruber, & Blanco (1999); Fusco-Femiano et al. (1999)).

However, the origin of the intracluster magnetic fields still rests a mystery in cosmology. The following two scenarios have been usually investigated in the literature. One is based on the idea that the cluster field is related to the fields generated by dynamo mechanism in individual galaxies and subsequent wind-like activity transports and redistributes the magnetic fields in the intracluster medium (e.g. Kronberg, Lesch, & Hopp (1999) and references therein). The general prediction of galactic dynamo mechanism is that the galactic magnetic field could arise from an exponential amplification of a small seed field during a galactic lifetime and energy of the mean magnetic field could grow up to equipartition level with the turbulent energy of fluid (Parker (1979); Zel’dovich, Ruzmaikin, & Sokoloff (1983); Lesch, & Chiba (1997)). It is not still clear, however, that the galactic dynamo theory can explain the detection of microgauss magnetic fields in high-$`z`$ damped Ly$`\alpha `$ absorption systems, which are supposed to be protogalactic clouds (Welter, Perry, & Kronberg (1984); Wolfe, Lanzetta, & Oren (1992)). On the other hand, an alternative scenario is that the intracluster magnetic fields may grow via adiabatic compression of a primordial field frozen with motions of cosmic plasma, where the primordial field is assumed to be produced somehow during the initial stages of cosmic evolution (e.g., Rees (1987); Kronberg (1994); and also see Grasso, & Rubinstein (2000) for a recent review). Recently, using the cosmological, magneto-hydrodynamic simulations of galaxy clusters, Dolag, Bartelmann, & Lesch (1999) have quantitatively shown that, if starting with the initial magnetic field of $`10^9`$G strength, the final intracluster field can be amplified by the gravitationally induced collapsing motions to the observed strength of $`\mu `$G irrespective of uniform or chaotic initial field configurations motivated by scenarios of the primordial or galactic-wind induced initial seed fields on Mpc scales, respectively. It is undoubtedly clear that the knowledge of the intracluster magnetic field will lead to a more complete understanding of the physical conditions of the intracluster medium and of the possible dynamical role of magnetic fields (e.g., Loeb, & Mao (1994); Vikhlinin, Markevitch, & Murray (2001)). Furthermore, the magnetic field should play an essential role to the nonthermal processes such as the synchrotron and high energy radiations and possibly the cosmic ray production (Loeb, & Waxman (2000); Totani, & Kitayama (2000); Waxman, & Loeb (2000)). Hence, it is strongly desirable to perform further theoretical and observational investigations on these issues in more detail.

In this paper we investigate how the Faraday rotation effect due to the intracluster magnetic field causes a secondary effect on the CMB polarization fields. While Thomson scattering of temperature anisotropies on the last scattering surface generates linearly polarized radiation at the decoupling epoch (Kosowsky (1996); Kamionkowski, Kosowsky, & Stebbins 1997a ,b; Zaldarriaga, & Seljak (1997); Hu, & White 1997a ,b), the plane of linear polarization should be rotated to some extent when the CMB radiation propagates through the magnetized intracluster medium at a low redshift. The great advantage is that, since the CMB polarization field is a continuously varying field on the sky, we can measure an angular profile of the rotation measure in a cluster in principle, which cannot be achieved by any other means. Furthermore, thanks to the frequency dependence of the Faraday rotation, one will be able to separate this effect from the primary signal and other secondary signals such as that induced by the gravitational lensing effect due to the large-scale structure (Zaldarriaga, & Seljak (1998)). In this paper, based on the Press-Schechter theory for the cluster abundance under the cold dark matter (CDM) structure formation scenario and a plausible isothermal $`\beta `$-model of the intracluster gas distribution, we compute angular power spectra of the CMB polarization fields including the Faraday rotation mixing effect caused by clusters at low redshifts. As for the unknown field configuration, we assume the uniform field of $`0.1\mu \mathrm{G}`$ strength across a cluster that is consistent with the recent Faraday rotation measurements (Clarke et al. 2001). This model allows us to estimate the impact of this effect in the simplest way. Our study thus proposes a new empirical opportunity to measure or constrain the intracluster magnetic field in the average sense that properties of the magnetic field could be extracted through changes of the statistical quantities, CMB angular power spectra.

So far previous works have focused mainly on investigations of effects of the primordial magnetic fields on the CMB temperature and polarization anisotropies (Kosowsky, & Loeb (1996); Adams et al. (1996); Scannapieco, & Ferreira (1997); Harari, Hayward, & Zaldarriaga (1997); Seshadri, & Subramanian (2001); Mack, Kahniashvili, & Kosowsky (2001); and see also Grasso, & Rubinstein (2000) for a review). Both the amplitudes of the cosmological primordial magnetic field and the mean baryonic density rapidly increase with redshift scaled as $`(1+z)^2`$ and $`(1+z)^3`$, respectively. The dominant contribution to the Faraday rotation effect is therefore imprinted before decoupling ($`z\stackrel{>}{}10^3`$), unless the structure formation at low redshifts causes a significant amplification of the magnetic field. Kosowsky, & Loeb (1996) found that, if the current value of the primordial field is of the order of $`10^9`$G on Mpc scales corresponding to the microgauss galactic field under the adiabatic compression, the effect on the CMB polarization is potentially measurable by satellite missions MAP and Planck Surveyor (see also Scannapieco, & Ferreira (1997); Harari, Hayward, & Zaldarriaga (1997)). It is also shown that such a stochastic magnetic field in the early universe affects the temperature fluctuations through the induced metric vector perturbations and thus current measurements can put an upper limit of $`\stackrel{<}{}10^{11}`$G on the current field amplitude (Mack, Kahniashvili, & Kosowsky (2001)).

This paper is organized as follows. In Section 2 we first construct a model to describe the magnetized hot plasma in a cluster by assuming the uniform magnetic field configuration for simplicity. We then derive the angular power spectrum of the Faraday rotation angle based on the Press-Schechter description of the cluster formation and the $`\beta `$-model of the gas distribution. In Section 3, we present a formalism for calculating the angular power spectra of the CMB polarization fields including the Faraday rotation mixing effect. Section 4 presents the results for the currently favored CDM models. In Section 5 we briefly present the discussions and summary. Unless stated explicitly, we assume the favored $`\mathrm{\Lambda }`$CDM cosmological model with $`\mathrm{\Omega }_{\mathrm{m0}}=0.3`$, $`\mathrm{\Omega }_{\lambda 0}=0.7`$, $`\mathrm{\Omega }_{b0}=0.05`$, $`h=0.7`$, and $`\sigma _8=1.0`$ as supported from observations of CMB anisotropies and large-scale structure (e.g. Netterfield et al. (2001)), where $`\mathrm{\Omega }_{m0}`$, $`\mathrm{\Omega }_{b0}`$, and $`\mathrm{\Omega }_{\lambda 0}`$ are the present-day density parameters of non-relativistic matter, baryon and the cosmological constant, respectively, $`h`$ is the Hubble parameter and $`\sigma _8`$ denotes the rms mass fluctuations of a sphere of $`8h^1`$Mpc radius. We also use the $`c=1`$ unit for the speed of light.

## 2 Model of Faraday Rotation due a Cluster Magnetic Field

### 2.1 Faraday rotation of a magnetic field

If monochromatic radiation of frequency $`\nu `$ is passing through a plasma in the presence of a magnetic field $`𝑩`$ along the propagation direction $`𝜸`$, its linear polarization vector will be rotated through the angle $`\mathrm{\Delta }\phi `$ (e.g., Rybicki, & Lightman (1979)):

$`\mathrm{\Delta }\phi `$ $`=`$ $`{\displaystyle \frac{e^3}{2\pi m_e^2c^2\nu ^2}}{\displaystyle 𝑑ln_e(𝑩𝜸)}`$ (1)
$``$ $`8.12\times 10^2(1+z)^2\left({\displaystyle \frac{\lambda _0}{1\mathrm{cm}}}\right)^2{\displaystyle \frac{dl}{\mathrm{kpc}}\left(\frac{n_e}{1\mathrm{cm}^3}\right)\left(\frac{𝑩𝜸}{1\mu \mathrm{G}}\right)},`$
where $`e`$ and $`m_e`$ denote the charge and mass of electron, respectively, $`n_e`$ is the number density field of electron along the line of sight, and $`\lambda _0`$ is the observed wavelength. Note that the factor $`(1+z)^2`$ comes from the relation of $`\lambda =\lambda _0(1+z)^1`$ and the sign of $`\mathrm{\Delta }\phi `$ could be negative depending on the orientation of the magnetic field and the reversal scale of magnetic field. The equation above clearly shows that the magnitude of the rotation measure depends on the electron number density, the magnetic field strength and the characteristic scale length of the field, and is larger for longer observed wavelengths because of the dependence $`\lambda _0^2`$. Thus, as a possible source of the Faraday rotation, in this paper we consider the magnetized hot plasma in clusters of galaxies, motivated by the fact that the deep gravitational potential well of dark matter makes the intracluster gas dense and highly ionized and many observations have revealed the existence of the strong magnetic field with $`\mu \mathrm{G}`$ strength(e.g., Clarke et al. 2001).

### 2.2 Cluster model with a uniform magnetic field

To calculate the Faraday rotation measure for the magnetized intracluster hot plasma, we have to assume how the magnetic field is distributed in a cluster along the line of sight. There are two possibilities considered; the uniform field configuration and, more realistically, the tangled field, where the former field has constant strength and direction through the entire cluster while the latter field has reversal scales along the line of sight. For the Coma cluster, Kim et al. (1990) suggested $`10\mathrm{kpc}`$ for the field reversal scale from the observed rotation measures of some sources close in angular position to the cluster, and Feretti et al. (1995) discovered the magnetic field structure with smaller scales down to $`1\mathrm{kpc}`$ from the rotation measures of radio halo in the Coma, leading to the stronger field of $`10\mu \mathrm{G}`$ on the scale. On the other hand, there is observational evidence of coherence of the rotation measures across large radio sources, which indicates that there is at least a field component smoothly distributed across cluster scales of $`100\mathrm{kpc}`$ (e.g., Taylor, & Perley (1993)). Thus, the magnetic field structure is still unknown because of the lack of the number of sources available per cluster for measuring the magnetic field. The angular profile of the rotation measure compiled from all sample of radio sources for 16 different normal clusters (Clarke et al. 2001) yields the field strengths between $`0.5`$ and $`3\mu \mathrm{G}`$ for a uniform field model, while $`5\mu \mathrm{G}(l/10\mathrm{kpc})^{1/2}(h/0.75)^{1/2}`$ for a simple tangled-cell model with a constant coherence length $`l`$. In this paper, we consider a uniform magnetic field model for the sake of revealing the impact of the Faraday rotation effect on the CMB polarization in the simplest way. We then assume that the amplitude of magnetic field at the cluster formation epoch is universally constant, namely it does not depend on redshift; $`B(z_{\mathrm{form}})=B_0=\mathrm{constant}`$.

Next let us consider a model to describe the gas distribution in a cluster. Motivated by the X-ray observations, we adopt the spherical isothermal $`\beta `$-model as for the gas density profile of each cluster expressed by

$$\rho (r)=\rho _0\left[1+(r/r_c)^2\right]^{3\beta /2},$$
(2)
where $`\rho _0`$ is the central gas mass density and $`r_c`$ is the core radius. The observed values of $`\beta `$, obtained from X-ray surface brightness profiles, range from $`0.5`$ to $`0.7`$ (e.g. see Jones, & Forman (1984)). In the following discussion we assume $`\beta =2/3`$ for simplicity. Note that Makino, Sasaki and Suto (1997) showed that the universal density profile of dark matter halo (Navarro, Frenk, & White (1997)) can reproduce the $`\beta `$-model for massive clusters under assumptions of the hydrostatic equilibrium and isothermality. In the spherical collapse model, the virial radius $`r_{\mathrm{vir}}`$ for the halo with mass $`M`$ is obtained from

$$M=\frac{4\pi }{3}\rho _{\mathrm{cr}}(z)\mathrm{\Delta }(z)r_{\mathrm{vir}}^3,$$
(3)
where $`\mathrm{\Delta }(z)`$ is the overdensity of collapse and the fitting formula is given by Bryan & Norman (1998), and $`\rho _{\mathrm{cr}}(z)`$ is the critical matter density at redshift $`z`$ defined by $`\rho _{\mathrm{cr}}(z)=3H_0^2/(8\pi G)(1+z)^3`$.

Once the uniform magnetic field and the gas density profile are given, we can easily calculate the angular profile of the Faraday rotation angle for a cluster projected on the sky similarly as the procedure to calculate the profile of the thermal Sunyaev-Zel’dovich (SZ) effect (Atrio-Barandela, & Mücket (1999); Komatsu, & Kitayama (1999)). Using the gas density profile (2) and equation (1), the angular profile can be calculated as

$`\mathrm{\Delta }\phi (\theta ,z)`$ $`=`$ $`{\displaystyle \frac{e^3n_{\mathrm{e0}}r_\mathrm{c}}{2\pi m_e^2c^2\nu _0^2(1+z)^2}}(B\mathrm{cos}\chi ){\displaystyle \frac{2}{\sqrt{1+(\theta /\theta _c)^2}}}\mathrm{tan}^1\sqrt{{\displaystyle \frac{p^2(\theta /\theta _c)^2}{1+(\theta /\theta _c)^2}}},`$ (4)
where $`pr_{\mathrm{vir}}/r_c`$, $`\chi `$ is the relative angle between the direction of the magnetic field and the line of sight, $`n_{\mathrm{e0}}`$ is the central number density of electron, and $`\theta `$ is the angular separation between the line of sight and the cluster center. The angular core size $`\theta _c`$ is related to $`r_c`$ via $`\theta _c=r_\mathrm{c}/d_A(z)`$, where $`d_A(z)`$ is the angular diameter distance to the cluster at redshift $`z`$. Note that $`p`$, given as the ratio between the viral and the core radius, is not a parameter but a function of mass $`M`$ and redshift $`z`$ in a general case.

We also have to relate the quantities $`r_\mathrm{c}`$ and $`n_{e0}`$ to the total mass $`M`$ and redshift $`z`$. Assuming the full ionization for intracluster gas, the central electron number density is given by $`n_{e0}=(\rho _{\mathrm{gas0}}/m_p)(1Y/2)`$, where $`Y`$ is the helium mass fraction and we fix $`Y=0.24`$ in this paper. It is known that the formation of cluster core regions contains large uncertainties. We here employ the entropy driven model (Kaiser (1991); Evrard, & Henry (1991)) to describe the core radius, motivated by the fact that this model can explain observations such as the X-ray luminosity function better than the simplest self-similar model (Kaiser (1986)) does. In this model the core is supposed to be in a minimum entropy phase $`s_{\mathrm{min}}=c_v\mathrm{ln}(T_{e0}/\rho _{\mathrm{gas0}}^{\gamma 1})`$, where $`T_{e0}`$ denotes the central electron temperature, $`c_v`$ is the specific heat capacity of the gas at constant volume, and $`\gamma `$ is the ratio of specific heats at constant pressure and constant volume. If using $`M=(4\pi /3)\rho _{\mathrm{cr}}(z)\mathrm{\Delta }(z)r_{\mathrm{vir}}^34\pi r_\mathrm{c}^2r_{\mathrm{vir}}(\rho _{\mathrm{gas0}}/f_{\mathrm{gas}})`$ for $`r_{\mathrm{vir}}/r_\mathrm{c}1`$, we can obtain

$`{\displaystyle \frac{r_{\mathrm{vir}}}{r_\mathrm{c}}}(M,z)`$ $``$ $`\left[{\displaystyle \frac{3\rho _{\mathrm{gas0}}(M,z)/f_{\mathrm{gas}}}{\rho _{\mathrm{cr}}(z)\mathrm{\Delta }_c(z)}}\right]^{1/2}`$ (5)
$``$ $`{\displaystyle \frac{T_{e0}^{1/[2(\gamma 1)]}(M,z)}{\mathrm{\Delta }_c^{1/2}(z)}}(1+z)^{3/2},`$
where $`f_{\mathrm{gas}}`$ is the gas mass fraction for a cluster and we assume that $`f_{\mathrm{gas}}`$ is equal to the cosmological mean; $`f_{\mathrm{gas}}M_{\mathrm{gas}}/M=\mathrm{\Omega }_{\mathrm{b0}}/\mathrm{\Omega }_{m0}`$ (White et al. (1993)). The adiabatic index is fixed at $`\gamma =5/3`$ throughout this paper. Moreover, we assume the isothermality and that the central electron temperature $`T_{e0}`$ is equal to the virial temperature $`T_{\mathrm{vir}}`$ given by

$$k_BT_{\mathrm{vir}}=\eta \frac{\mu m_pGM}{3r_{\mathrm{vir}}},$$
(6)
with $`\mu =0.59`$. The quantity $`\eta `$ is a fudge factor of order unity that should be determined by the efficiency of the shock heating of the gas (Eke, Navarro, & Frenk (1998)), and we fix $`\eta =3/2`$. If the proportional constant to calculate $`r_\mathrm{c}`$ in equation (5) is determined by assuming $`r_\mathrm{c}(10^{15}h^1M_{},z=0)=0.15h^1\mathrm{Mpc}`$, we can obtain the core radius for an arbitrary cluster with mass $`M`$ and at redshift $`z`$. This cluster model then yields $`r_{\mathrm{vir}}/r_\mathrm{c}=13.6`$, $`n_{\mathrm{e0}}=5.0\times 10^3\mathrm{cm}^3`$, and $`T_\mathrm{e}=6.5\mathrm{keV}`$ for $`M=10^{15}h^1M_{}`$ at $`z=0`$ in the $`\mathrm{\Lambda }`$CDM model. Using these typical values of physical quantities for a cluster with $`M=10^{15}h^1M_{}`$, equation (4) tells us the magnitude of the rotation measure at the cluster center as

$$\mathrm{\Delta }\phi (z=0,\theta =0)2.34\times 10^1\mathrm{rad}\left(\frac{\nu _0}{10\mathrm{GHz}}\right)^2\left(\frac{B_0\mathrm{cos}\chi }{0.1\mu \mathrm{G}}\right).$$
(7)
Thus, if the line-of-sight component of the uniform magnetic field has a strength of $`0.1\mu \mathrm{G}`$ and we can observe at low frequencies such as $`10\mathrm{GHz}`$, the magnitude of the rotation measure angle could be of the order of $`10^1\mathrm{rad}(6^{})`$ for such a massive cluster. The observed scatter of the normalized rotation measure ($`\mathrm{RM}\mathrm{\Delta }\phi /\lambda _0^2[\mathrm{m}]`$) is $`\mathrm{RM}=0250\mathrm{rad}\mathrm{m}^2`$ at the radius in the range of $`0\stackrel{<}{}r\stackrel{<}{}1h^1\mathrm{Mpc}`$ from the cluster center (Kim et al. 1991; Clarke et al. 2001). The value estimated in equation (7) corresponds to $`\mathrm{RM}260\mathrm{rad}\mathrm{m}^2`$ at the cluster center for the typical case of $`B_0\mathrm{cos}\chi =0.1\mu \mathrm{G}`$. Our model thus seems consistent with the observations. This can be more quantitatively verified as follows. Using our model of the rotation measure angle (4) and the Press-Schechter mass function $`dn/dM`$ (Press, & Schechter (1974)) (see equation (11)), we can compute the variance of the rotation measure for present-day clusters against the radius from the cluster center:

$$\mathrm{RM}^2(r)=_{M_{\mathrm{min}}}^{M_{\mathrm{max}}}𝑑M\frac{dn}{dM}\left[\frac{\mathrm{\Delta }\phi (r,z=0)}{\lambda ^2}\right]^2/_{M_{\mathrm{min}}}^{M_{\mathrm{max}}}𝑑M\frac{dn}{dM}.$$
(8)
In the calculation of the equation above, we use $`\mathrm{cos}^2\chi =1/3`$ for the ensemble average of angle $`\chi `$ between the magnetic field direction and the line of sight, since the field orientation is considered to be random for each cluster. The solid line in Figure 1 shows the average profile $`\sqrt{\mathrm{RM}^2(r)}`$ for $`B_0=0.2\mu \mathrm{G}`$ in the mass range of $`M5\times 10^{14}M_{}`$. Note that this mass range corresponds to $`L_X\stackrel{>}{}10^{44}\mathrm{erg}\mathrm{s}^1`$ for the $`X`$-ray luminosity in the ROSAT $`0.12.4\mathrm{keV}`$ band, where only the thermal bremsstrahlung emission is considered. Thus, this $`X`$-ray luminosity range is roughly consistent with the ROSAT sample of the Faraday rotation measurements used by Clarke et al. (2001). For comparison, square symbols represent the observational data from Clarke et al. (2001) with $`\pm 1\sigma `$ errors arising from the Faraday contributions due to our Galaxy. It is clear that our model with $`B_0=0.2\mu \mathrm{G}`$ can roughly reproduce the observed magnitude and dispersion of the rotation measures as a function of the radius. In this sense, it is likely that we can at least estimate a correct magnitude of the Faraday rotation effect on the angular power spectra of CMB polarization fields, even though the uniform magnetic field is an unrealistic model, because the contribution to the angular power spectra comes from the second moments of the rotation measure angle by definition (see equation (21)). Furthermore, there could be an uncertain selection effect in the observational data. For example, one cluster sample with the large RM value of $`|\mathrm{RM}|=229`$ at the radius of $`r=3\mathrm{kpc}`$ has the $`X`$-ray luminosity of $`L_X=2.0\times 10^{42}\mathrm{erg}\mathrm{s}^1`$ or the mass of $`M7.0\times 10^{13}M_{}`$, which is smaller than the lowest mass of $`M=5\times 10^{14}M_{}`$ used for the theoretical prediction shown by the solid line. To illustrate the sensitivity of the lowest mass to the theoretical prediction, the dashed line in Figure 1 shows the result of equation (8) for $`M10^{14}M_{}`$ ($`L_X\stackrel{>}{}4.4\times 10^{42}\mathrm{erg}\mathrm{s}^1`$) and $`B_0=0.2\mu \mathrm{G}`$, and it clearly underestimates the observational result. For the similar reason, it is thought that Clarke et al. (2001) derived a higher value of $`0.5\mu \mathrm{G}`$ for the uniform magnetic field model from their observational data. In addition to these facts, there is possible contamination of line emissions from the intracluster metal to the observed $`X`$-ray luminosity. Therefore, our model of $`B_0=0.2\mu G`$ often used in the following discussion could lead to the minimum magnitude of the Faraday rotation effect on the CMB polarization power spectra for a realistic effect.

As will be shown in detail, the Faraday rotation effect generates secondary patterns of the CMB polarizations expressed as $`Q\mathrm{\Delta }\phi \stackrel{~}{U}`$ and $`U\mathrm{\Delta }\phi \stackrel{~}{Q}`$ in terms of the Stokes parameters $`Q`$ and $`U`$, where $`\stackrel{~}{Q}`$ and $`\stackrel{~}{U}`$ are those parameters of the primary polarization generated via Thomson scattering at the decoupling ($`z_{}10^3`$). Hence, equation (7) implies that, if we observe the CMB polarization through a cluster at longer wavelengths such as $`\lambda _0\stackrel{>}{}6\mathrm{cm}`$ ($`\nu _0\stackrel{<}{}5\mathrm{GHz}`$), the secondary signals could be comparable to the primary signals for massive clusters with $`B_0\mathrm{cos}\chi =0.1\mu \mathrm{G}`$. In this case, we could directly measure the Faraday rotation effect in an individual cluster like the SZ effect on the CMB temperature fluctuations. This would be also true for particular clusters that have an unusual stronger magnetic field such as $`\stackrel{>}{}1\mu \mathrm{G}`$. Moreover, since the primary CMB polarization field has very smooth structure on angular scales of $`\theta \stackrel{<}{}10^{}`$ because of the Silk damping (Silk (1968); and also see Hu, & Sugiyama (1995) in more detail), the angular profile of the rotation measure could be directly reconstructed in principle from the secondary signals generated on small scales even for a single observed frequency. These interesting possibilities are now being investigated in detail, and the results will be presented elsewhere (Ohno et al. 2001 in preparation).

### 2.3 Angular power spectrum of the rotation measure

We are interested in the secondary effect on the angular power spectra of the CMB polarization due to the Faraday rotation effect caused by clusters. We thus need to compute the angular power spectrum of the rotation measure angle $`\mathrm{\Delta }\phi (\theta )`$, which gives the strength of $`\mathrm{\Delta }\phi `$ in the average sense for the all-sky survey at two-point statistics level. The angular Fourier transformation of the rotation measure (4) is given by

$$\mathrm{\Delta }\phi _l(z)=2\pi _0^{\theta _{\mathrm{vir}}}𝑑\theta \theta \mathrm{\Delta }\phi (\theta ,z)J_0(l\theta ).$$
(9)
where $`\theta _{\mathrm{vir}}r_{\mathrm{vir}}/d_A(z)`$, $`J_0(x)`$ is the zero-th order Bessel function, and we have used the small-angle approximation (Bond & Efstathiou 1987). Since clusters are discrete sources, contributions to the power spectrum of the rotation measure are divided into the Poissonian contribution, $`C_l^{(P)}`$, and the contribution from the spatial correlation between clusters, $`C_l^{(C)}`$ (Peebles 1980). From equation (4) the correlation contribution $`C_l^{(C)}`$ depends on the ensemble average $`\mathrm{cos}\chi _1\mathrm{cos}\chi _2`$, where $`\chi _1`$ and $`\chi _2`$ are the relative angles between the magnetic fields and the line of sights for those two clusters, respectively, while $`C_l^{(P)}`$ depends on $`\mathrm{cos}^2\chi `$, leading to the non-vanishing contribution for any distribution of $`\chi `$. If the origin of the magnetic field is primordial, the correlation between two intracluster magnetic fields could be non-vanishing even on separation scales between clusters like that between the density fluctuation fields, and in this case we have some contribution from $`C_l^{(C)}`$ because $`\mathrm{cos}\chi _1\mathrm{cos}\chi _20`$. However, it is known that the Poissonian contribution always dominates the correlation one because clusters are rare objects (Komatsu, & Kitayama (1999)). For this reason, we here assume $`\mathrm{cos}\chi _1\mathrm{cos}\chi _2=0`$ and consider only the Poisson contribution $`C_l^{(P)}`$ for simplicity. Following the method developed by Cole & Kaiser (1988) and Limber’s equation, we can obtain an integral expression of $`C_l^{(C)}`$;

$`C_l^{\mathrm{RM}(\mathrm{P})}`$ $`=`$ $`{\displaystyle _0^{z_{\mathrm{dec}}}}𝑑z{\displaystyle \frac{dV}{dz}}{\displaystyle _{M_{\mathrm{min}}}^{M_{\mathrm{max}}}}𝑑M{\displaystyle \frac{dn(M,z)}{dM}}|\mathrm{\Delta }\phi _l(M,z)|^2,`$ (10)
where $`V(z)`$ and $`r(z)`$ are the comoving volume and the comoving distance, respectively, and $`dn/M(M,z)`$ is the comoving number density for halos with mass in the range of $`M`$ and $`M+dM`$ at redshift $`z`$. We compute $`dn/dM`$ using the Press-Schechter model (Press, & Schechter (1974)), and in this case we have

$$\frac{dn(M,z)}{dM}=\sqrt{\frac{2}{\pi }}\frac{\overline{\rho }}{M}\left|\frac{d\mathrm{ln}\sigma }{dM}\right|\nu _ce^{\nu _c^2/2},$$
(11)
where $`\nu _c=\delta _c(z)/\sigma (M)`$ denotes the threshold, $`\sigma (M)`$ is the present-day rms mass fluctuation within the top-hat filter corresponding to the mass scale of $`M`$, $`\delta _c(z)1.69/D(z)`$ is the threshold overdensity of the spherical collapse model, and $`D(z)`$ is the linear growth factor of density fluctuations.

Figure 2 shows the angular power spectra of the rotation measure through clusters for $`B_0=0.2\mu \mathrm{G}`$ (solid line) and $`0.5\mu \mathrm{G}`$ (dashed) assuming the observed frequency of $`\nu _0=10\mathrm{GHz}`$ in the $`\mathrm{\Lambda }`$CDM model. Note that we have again used $`\mathrm{cos}^2\chi =1/3`$. We have confirmed that dominant contribution to the power spectrum comes from the massive clusters with mass larger than $`10^{14}M_{}`$ at low redshifts such as $`z\stackrel{<}{}0.5`$, similarly as the results of SZ effect due to clusters (e.g., Cooray (2000)).

## 3 Secondary Effect of Faraday Rotation in a Cluster on CMB Polarization

In this section we develop a formalism for calculating the secondary Faraday rotation effect induced by magnetized intracluster hot plasma on the CMB polarization fields and their angular power spectra.

The properties of CMB polarization fields can be described in terms of the Stokes parameters $`Q`$ and $`U`$ (Kosowsky (1996); Kamionkowski, Kosowsky, & Stebbins 1997a ,b; Zaldarriaga, & Seljak (1997)). Let us consider quasi-monochromatic waves propagating in the z-direction, in which the electric and magnetic fields vibrate on the $`x`$-$`y`$ plane. We can then express the electric field $`𝑬`$ in terms of the complex orthogonal unit vectors of circularly polarized waves as $`𝑬=(E_\mathrm{R}e^{i\delta _\mathrm{R}}\mathit{ϵ}_R+E_\mathrm{L}e^{i\delta _\mathrm{L}}\mathit{ϵ}_\mathrm{L})e^{i\omega t}`$, where $`\mathit{ϵ}_{\mathrm{R},\mathrm{L}}(\mathit{ϵ}_xi\mathit{ϵ}_y)/\sqrt{2}`$ and $`\mathit{ϵ}_\mathrm{R}`$ and $`\mathit{ϵ}_\mathrm{L}`$ are the unit vectors of right-hand and left-hand polarized waves, respectively. Using those quantities, the Stokes parameters $`Q`$ and $`U`$ measured in the fixed $`(x,y)`$-coordinates can be expressed as

$`Q`$ $``$ $`|𝑬\mathit{ϵ}_x|^2|𝑬\mathit{ϵ}_y|^2=2E_\mathrm{R}E_\mathrm{L}\mathrm{cos}(\delta _\mathrm{R}\delta _\mathrm{L}),`$
$`U`$ $``$ $`2\mathrm{R}\mathrm{e}\left[(𝑬\mathit{ϵ}_x)^{}(𝑬\mathit{ϵ}_y)\right]=2E_\mathrm{R}E_\mathrm{L}\mathrm{sin}(\delta _\mathrm{R}\delta _\mathrm{L}).`$ (12)
If there is an intervening magnetic field in the ionized plasma between the last scattering surface and the present epoch, the right-hand and left-hand polarized waves travel with different phase velocities by the Faraday rotation effect. Therefore, from equation (12), we can derive the following equation to govern the time evolution of $`Q`$ and $`U`$ in the presence of the magnetized plasma;

$`{\displaystyle \frac{dQ}{dt}}`$ $`=`$ $`U{\displaystyle \frac{d(\delta _\mathrm{R}\delta _\mathrm{L})}{dt}}=2\omega _BU,`$
$`{\displaystyle \frac{dU}{dt}}`$ $`=`$ $`2\omega _BQ,`$ (13)
where $`2\omega _Bd(\delta _R\delta _\mathrm{L})/dt`$, $`t`$ is the cosmic time and we have ignored other effects associated with the Thomson scattering. Note that $`\omega _B`$ is also related to the rotation measure angle $`\mathrm{\Delta }\phi `$ defined by equation (1) as $`\omega _B=d(\mathrm{\Delta }\phi )/dt`$. Equation (13) clearly shows that the Faraday rotation causes the mixing between $`Q`$\- and $`U`$-type polarizations. More importantly, even if the primary CMB anisotropies generate only the $`Q`$-type polarization in the statistical sense (Zaldarriaga, & Seljak (1997)), the Faraday rotation mixing induces the $`U`$-type polarization on the observed sky from the primary $`Q`$ mode.

Since we are interested in the secondary effect on the CMB polarizations, the solutions of equation (13) for $`Q`$ and $`U`$ along the line of sight with direction of $`𝜽`$ can be approximately solved up to the first order of $`\omega _B`$ as

$`Q(t_0,𝜽)`$ $``$ $`\stackrel{~}{Q}(t_{},𝜽)2\stackrel{~}{U}(t_{},𝜽){\displaystyle _t_{}^{t_0}}𝑑t\omega _B(t,𝜽)`$
$`U(t_0,𝜽)`$ $``$ $`\stackrel{~}{U}(t_{},𝜽)+2\stackrel{~}{Q}(t_{},𝜽){\displaystyle _t_{}^{t_0}}𝑑t\omega _B(t,𝜽),`$ (14)
where $`\stackrel{~}{U}`$ and $`\stackrel{~}{Q}`$ denote the primary $`U`$\- and $`Q`$-polarization fluctuations generated at the decoupling epoch ($`z_{}10^3`$), respectively, and we have neglected other secondary polarization fields generated at low redshifts that have insignificant power compared to the primary signal on relevant angular scales for a realistic reionization history (e.g., Hu (2000)). The quantities $`t_{}`$ and $`t_0`$ are the cosmic time at the decoupling and the present time, respectively. In what follows quantities with tilde symbol denote quantities at $`t_{}`$.

The Stokes parameters $`Q`$ and $`U`$ depend on the choice of coordinates and are not invariant under the coordinate rotation. For this reason, it is useful to introduce the new bases of rotationally invariant polarization fields, called the parity-even electric mode ($`E`$) and the parity-odd magnetic mode ($`B`$) (Zaldarriaga, & Seljak (1997); Kamionkowski, Kosowsky, & Stebbins 1997a ,b; Hu, & White 1997a ,b). Any polarization pattern on the sky can be decomposed into these modes. Since the secondary effect due to clusters of galaxies on the CMB polarization is important only on small angular scales such as $`\theta \stackrel{<}{}1^{}`$, we can safely employ the small-angle approximation (Zaldarriaga, & Seljak (1998)). Based on these considerations, $`Q`$ and $`U`$ fields can be expressed using the two-dimensional Fourier transformation in terms of the electric and magnetic modes as

$`Q(𝜽)`$ $`=`$ $`{\displaystyle \frac{d^2𝒍}{(2\pi )^2}\left[E_𝒍\mathrm{cos}2\varphi _𝒍B_𝒍\mathrm{sin}2\varphi _𝒍\right]e^{i𝒍𝜽}},`$
$`U(𝜽)`$ $`=`$ $`{\displaystyle \frac{d^2𝒍}{(2\pi )^2}\left[E_𝒍\mathrm{sin}2\varphi _𝒍+B_𝒍\mathrm{cos}2\varphi _𝒍\right]e^{i𝒍𝜽}},`$ (15)
where $`\varphi _𝒍`$ is defined by $`l_x+il_y=l\mathrm{exp}(i\varphi _𝒍)`$, and $`E_𝒍`$ and $`B_𝒍`$ are the two-dimensional Fourier coefficients for the $`E`$\- and $`B`$-modes, respectively. The Fourier components $`\stackrel{~}{E}_𝒍`$ and $`\stackrel{~}{B}_𝒍`$ for the primary CMB polarization fields satisfy

$`\stackrel{~}{E}_𝒍\stackrel{~}{E}_𝒍^{}^{}=(2\pi )^2C_{\stackrel{~}{E}l}\delta ^2(𝒍𝒍^{}),`$
$`\stackrel{~}{B}_𝒍\stackrel{~}{B}_𝒍^{}^{}=(2\pi )^2C_{\stackrel{~}{B}l}\delta ^2(𝒍𝒍^{}),`$ (16)
where $`C_{\stackrel{~}{E}l}`$ and $`C_{\stackrel{~}{B}l}`$ are the angular power spectra of primary $`E`$\- and $`B`$-modes, respectively. The primary $`B`$-mode polarization is generated by the quadrupole temperature anisotropies associated with the tensor (gravitational wave) and vector perturbations. If we assume the standard inflation-motivated model with a spectral index of $`n_\mathrm{s}=1`$ for the scalar perturbations, the tensor and vector perturbations are sufficiently smaller than the scalar perturbations. In the following discussion we ignore the primary $`B`$-mode power spectrum for simplicity; $`C_{\stackrel{~}{B}l}=0`$.

From equation (14) the two-point correlation functions of $`Q`$ and $`U`$ fields including the Faraday rotation mixing effect can be computed as

$`C_Q(\theta )`$ $``$ $`Q(0)Q(𝜽)C_{\stackrel{~}{Q}}(\theta )+4C_{\stackrel{~}{U}}(\theta )C^{\mathrm{RM}}(\theta ),`$
$`C_U(\theta )`$ $``$ $`U(0)U(𝜽)C_{\stackrel{~}{U}}(\theta )+4C_{\stackrel{~}{Q}}(\theta )C^{\mathrm{RM}}(\theta ),`$ (17)
with

$`C_{\stackrel{~}{Q}}(\theta )`$ $`=`$ $`{\displaystyle \frac{ldl}{2\pi }\frac{C_{\stackrel{~}{E}l}}{2}(J_0(l\theta )+J_4(l\theta ))},`$
$`C_{\stackrel{~}{U}}(\theta )`$ $`=`$ $`{\displaystyle \frac{ldl}{2\pi }\frac{C_{\stackrel{~}{E}l}}{2}(J_0(l\theta )J_4(l\theta ))},`$ (18)
where we have employed a reasonable assumption that the primary fields ($`\stackrel{~}{Q}`$ and $`\stackrel{~}{U}`$) on the last scattering surface and the rotation measure field $`\omega _B`$ induced by low-$`z`$ clusters are statistically uncorrelated. Note that $`C^{\mathrm{RM}}(\theta )`$ is the two-point correlation function of the rotation measure angle and can be expressed in terms of the angular power spectrum of the rotation measure as

$$C^{\mathrm{RM}}(\theta )𝑑t\omega _B(t,0)𝑑t^{}\omega _B(t^{},𝜽)=\frac{ldl}{2\pi }C_l^{\mathrm{RM}(\mathrm{P})}J_0(l\theta ),$$
(19)
where $`C_l^{\mathrm{RM}(\mathrm{P})}`$ is given by equation (10).

We are now in the position to derive the angular power spectra of $`E`$ and $`B`$ modes in the observed CMB sky. Following the method developed by Zaldarriaga, & Seljak (1998), $`C_{El}`$ and $`C_{Bl}`$ can be expressed as

$`C_{El}`$ $`=`$ $`\pi {\displaystyle _0^\pi }\theta 𝑑\theta \left[(C_Q(\theta )+C_U(\theta ))J_0(l\theta )+(C_Q(\theta )C_U(\theta ))J_4(l\theta )\right],`$
$`C_{Bl}`$ $`=`$ $`\pi {\displaystyle _0^\pi }\theta 𝑑\theta \left[(C_Q(\theta )+C_U(\theta ))J_0(l\theta )(C_Q(\theta )C_U(\theta ))J_4(l\theta )\right].`$ (20)
Therefore, from equation (18) we have

$`C_{El}`$ $`=`$ $`C_{\stackrel{~}{E}l}+{\displaystyle l^{}𝑑l^{}W_{ll^{}}^EC_{\stackrel{~}{E}l^{}}}`$
$`C_{Bl}`$ $`=`$ $`{\displaystyle l^{}𝑑l^{}W_{ll^{}}^BC_{\stackrel{~}{E}l^{}}},`$ (21)
where $`W_{Ell^{}}`$ and $`W_{Bll^{}}`$ are the window functions defined by

$`W_{ll^{}}^E`$ $``$ $`2{\displaystyle _0^\pi }\theta 𝑑\theta \left[J_0(l\theta )J_0(l^{}\theta )J_4(l\theta )J_4(l^{}\theta )\right]C^{\mathrm{RM}}(\theta ),`$
$`W_{ll^{}}^B`$ $``$ $`2{\displaystyle _0^\pi }\theta 𝑑\theta \left[J_0(l\theta )J_0(l^{}\theta )+J_4(l\theta )J_4(l^{}\theta )\right]C^{\mathrm{RM}}(\theta ).`$ (22)
Equations (21) clearly show that the Faraday rotation mixing generates the non-vanishing angular power spectrum of the $`B`$-mode polarization from the primary $`E`$-mode.

## 4 Results and Estimations of the Detectability

Throughout this paper, we employ the $`\mathrm{\Lambda }`$CDM model with $`\mathrm{\Omega }_{m0}=0.3`$, $`\mathrm{\Omega }_{\lambda 0}=0.7`$, $`\mathrm{\Omega }_{b0}=0.05`$, $`h=0.7`$ and $`\sigma _8=1.0`$ as supported from observations of the CMB anisotropies and the large-scale structure. As for the power spectrum of dark matter used in the calculation of the Press-Schechter mass function, we adopted the Harrison-Zel’dovich spectrum and the BBKS transfer function (Bardeen et al. (1986)) with the shape parameter from Sugiyama (1995).

Figure 3 shows the window functions of $`B`$\- and $`E`$-modes per logarithmic interval in $`l`$, $`l^2W_{ll^{}}^B`$ and $`l^2W_{ll^{}}^E`$, for a given mode $`l^{}=2000`$ as derived by equation (22). We consider the magnetic field strength $`B_0=0.2\mu \mathrm{G}`$ and the observed frequency $`10\mathrm{GHz}`$ in the $`\mathrm{\Lambda }`$CDM model. One can see that the window functions for the mixing between $`E`$ and $`B`$ modes are well localized in $`l`$ space.

In Figure 4 we show the angular power spectra of $`E`$\- and $`B`$-mode polarizations on the observed sky including the Faraday rotation mixing effect due to clusters for the observed frequency of $`10\mathrm{G}\mathrm{H}\mathrm{z}`$. The dot-dashed line shows the $`B`$-mode spectrum for $`B_0=0.5\mu \mathrm{G}`$ that corresponds to the value estimated from the observational data for a model of uniform intracluster magnetic field (Clarke et al. 2001), while the dotted line shows the result of $`B_0=0.2\mu \mathrm{G}`$. For comparison, the $`E`$-mode power spectra with and without the secondary effect of $`B_0=0.2\mu \mathrm{G}`$ are also shown by solid and dashed lines, respectively. One can readily see that the generated $`B`$-mode power spectrum has a peak with magnitude of $`0.1\mu K(B_0/0.1\mu G)(\nu _0/10\mathrm{GHz})^2`$ at $`l1000`$. On smaller scales of $`l\stackrel{>}{}6000`$, the spectra of $`E`$ and $`B`$ modes coincide, and this is similar as the secondary effects caused by the peculiar velocity field of the ionized medium in the reionized universe (Hu (2000); Liu et al. (2001)). These results imply that, if the uniform magnetic field has a strength of $`0.5\mu \mathrm{G}`$ and we can observe at lower frequencies such as $`\nu _0\stackrel{<}{}5\mathrm{GHz}`$, the magnitude of $`B`$-mode could be comparable with the primary polarization amplitude of $`\mu \mathrm{K}`$.

The detectability of the induced $`B`$ mode polarization by the sensitive satellite mission Planck can be estimated following the method developed by Zaldarriaga & Seljak (1998). The relative error on the overall amplitude of the induced $`B`$ component $`\beta `$ can be estimated as

$$\frac{\mathrm{\Delta }\beta }{\beta }=\sqrt{\frac{2}{f_{\mathrm{sky}}_l(2l+1)/(1+w^1e^{l^2\theta _s^2}/C_{\stackrel{~}{B}l})^2}},$$
(23)
where $`f_{\mathrm{sky}}`$ is the fraction of observed sky and we here fix $`f_{\mathrm{sky}}=0.8`$. As for the detector noise and the beam width, we assume $`w^1=4.72\times 10^{16}`$ and $`\theta _\mathrm{s}=\theta _{\mathrm{fwhm}}/\sqrt{8\mathrm{ln}2}=3.71\times 10^3`$ for the $`30`$GHz channel on Planck, where $`\theta _{\mathrm{fwhm}}`$ is the full-width at half-maximum angle. Note that the $`30`$GHz channel we here consider is the lowest frequency channel on Planck. From the dependence $`\lambda _0^2`$ of the rotation measure, the magnitude of the $`B`$-mode angular power spectrum at $`30`$GHz becomes smaller by $`10^2`$ than the results estimated in Figure 4. Accordingly, for the magnetic field of $`B_0=0.2\mu \mathrm{G}`$, we have $`\beta /\mathrm{\Delta }\beta 0.14`$. This means that this effect cannot be detected by the Planck mission for $`B_0=0.2\mu \mathrm{G}`$. Conversely, to get $`\beta /\mathrm{\Delta }\beta 1`$ at the $`30`$GHz channel, the uniform magnetic field component must have $`1.5\mu \mathrm{G}`$ strength, and this seems an unrealistic value. However, we stress that even a null detection of this effect can set a new constraint on the magnetic field strength. It is also worth noting that this signal would be detected more effectively by a ground based experiments at lower frequency bands such as $`\stackrel{<}{}10\mathrm{GHz}`$ observing a small patch of the sky for a sufficiently long integration time to reduce the noise per pixel.

## 5 Discussions and Conclusions

In this paper, we have investigated the secondary effect on the CMB polarization fields induced by the Faraday rotation effect of the magnetic field in an intracluster hot plasma at a low redshift. To illustrate the impact of this effect in the simplest way, we employed the simple model that the magnetic field has a uniform field strength such as $`0.2\mu \mathrm{G}`$ across a cluster universally when the cluster formed, which is consistent with observations of the rotation measures in clusters (Clarke et al. 2001). As shown in Figure 1, our model can roughly reproduce the observed scatter of the rotation measures as a function of the distance from the cluster center (Kim et al. 1991; Clarke et al. 2001). In this sense, since the Faraday rotation effect on the angular power spectra of CMB polarizations comes from the second moments of the rotation measure angle (see equation (21)), it is likely that our model can at least estimate a correct magnitude of the effect, even though detailed shapes of those spectra could be different for a realistic intracluster magnetic field as discussed below. We showed that the parity-odd $`B`$-mode angular power spectrum is generated on the observed sky by the Faraday rotation mixing effect as a new qualitative feature, when if the primary CMB anisotropies includes the parity-even $`E`$-mode only such as predicted by the standard inflation-motivated scenarios with pure primordial scalar perturbations. We estimated that the generated $`B`$-mode power spectrum has a peak with amplitude of $`\sqrt{l^2C_{lB}/2\pi }0.1\mu \mathrm{K}(B_0/0.1\mu \mathrm{G})(\nu _0/10\mathrm{GHz})^2`$ at $`l1000`$ under the plausible scenario of the cluster formation in the currently favored $`\mathrm{\Lambda }`$CDM model. It was also shown that the lowest frequency $`30\mathrm{G}\mathrm{H}\mathrm{z}`$ channel of Planck can be used to set an upper limit of $`B_0\stackrel{<}{}1.5\mu \mathrm{G}`$ for a uniform component of the intracluster magnetic field. Detection or even null detection of the predicted $`B`$-type polarization will therefore be a new empirical tool to provide a calibration of an uncertain magnetic field in a cluster, combined with measurements of the gas distribution from the X-ray or SZ datasince.

It is known that there are other secondary sources on the CMB polarization fields caused in the low redshift universe, and these nonlinear effects generally induce the $`B`$-type polarization pattern from the coupling with the primary $`E`$-mode. The main source is the gravitational lensing effect of the large-scale structure, leading to the $`B`$-type polarization that has a peak of $`0.3\mu \mathrm{K}`$ at $`l1000`$ and then a power of $`\stackrel{<}{}0.01\mu \mathrm{K}`$ at $`l\stackrel{>}{}5000`$ for the simliar $`\mathrm{\Lambda }`$CDM model as considered in this paper (Zaldarriaga, & Seljak (1998)). One of authors (N.S.) has quantitatvely shown that the secondary effect due to the peculiar motion of ionized medium in the large-scale structure also generates the $`B`$-mode polarization with $`0.01\mu K`$ at $`100\stackrel{<}{}l\stackrel{<}{}10^4`$ for a realistic patchy reionization model of the universe (Liu et al. (2001)). From these results, if the uniform magnetic field has a larger strength of $`B0.5\mu \mathrm{G}`$ as a common feature of clusters and we observe at lower frequencies such as $`\nu _0\stackrel{<}{}5\mathrm{GHz}`$, the generated $`B`$-mode amplitude due to the Faraday rotation effect would be comparable with the primary polarization amplitude and larger than the other secondary signals at $`l\stackrel{>}{}1000`$, although observations at such low frequencies would suffer from large foreground contamination of the syncrhrotron radiation from our galaxy (Tegmark et al. (2000)). Even if the uniform magnetic field is not as strong as $`0.5\mu \mathrm{G}`$, the sensitive multi low-frequency measurements will allow one to separate this signal from primary and those other secondary signals in principle thanks to the frequency dependence of $`\nu _0^4`$ on $`C_{Bl}`$, which is analogous to measurements of secondary temperature fluctuations by the SZ effect.

There are possible contributions to affect our results that we have ignored in this paper. The intracluster tangled magnetic fields, as implied by the rotation measures of some sources inside the Coma cluster (Kim et al. (1990)), would provide contributions to our results in addition to the contribution due to the uniform field. However, the coherent scale of tangled fields in a cluster is still unknown. The recent complete measurements of the rotation measures (Clarke et al. 2001) imply the $`110\mu \mathrm{G}`$ strength of the tangled field under the assumption of the coherent scale of $`10100\mathrm{kpc}`$. It is also known that the strong radio halos embedded within a (cooling flow) cluster are pervaded by stronger magnetic fields on smaller scales such as $`50\mu G`$ for Hydra A (Taylor, & Perley (1993); Taylor et al. (2001)). Although the simplest tangled-cell model with a constant coherence length $`l`$ has often been considered in the literature, the possible important mechanism to affect our results is the deporlarization effect (Tribble (1991)), leading to the cancellations to some extent between the Faraday rotations in independent cells with random orientations of the magnetic fields within a cluster. The finite beam size will also lead to the artificial cancellations between the Faraday rotations of cells covered within one beam. From these considerations, the depolarization effect may lead to an intuitive result that a feature of the $`B`$-mode spectrum can be sensitive to the characteristic angular scale, $`l_c`$, originating from the coherent length. This investigation is now in progress, and will be presented elsewhere (Ohno et al. 2001). Recently, it has been suggested that outflow or jet acitivities of quasars or black holes leave behind an expanding magnetized bubble in the itergalactic medium (IGM) resulting in the possibility that the IGM is filled by magnetic fields to some extent (Furlanetto, & Loeb (2001); Kronberg et al. (2001)). Even thgouh the IGM field has a smaller strength than $`10^9\mathrm{G}`$ on $`\mathrm{Mpc}`$ scales, a large volume coverage of the ionized plasma might lead to non-negligible contribution connected to the reionization history of the universe.

Finally, we comment on implications of our results to the nonthermal processes in a cluster. The observations of diffuse synchrotron halos and nonthermal hard X-ray emission have implied the existence of nonthermal relativistic electrons in a cluster (e.g., Rephaeli, Gruber, & Blanco (1999)). These electrons are produced by the shock acceleration in an intracluster medium, and it will allow us to derive additional information on the physical conditions of the intracluster medium environment, which cannot be obtained from the thermal plasma emission only. The intracluster magnetic field should then play an important role to these nonthermal processes. In particular, it is being recognized that the nonthermal process can be a unique probe of measuring the dynamically forming clusters before thermalization of the intracluster gas. Recently, Waxman & Loeb (2000) pointed out that the synchrotron radiation from those forming clusters could be foreground sources of the CMB temperature fluctuations at low frequency observations such as $`10\mathrm{GHz}`$. Those clusters could also produce the high energy gamma ray emission through the inverse Compton scattering of CMB photons by relativistic electrons and thus be identified as gamma ray clusters by the future sensitive telescope GLAST, which are difficult to detect by X-ray or optical surveys because of their extended angular size of about $`1^{}`$ (Totani, & Kitayama (2000)). Based on these ideas, it will be very interesting to investigate cross-correlations between the synchrotron radiation or the gamma ray sources and the Faraday rotation signal in CMB polarization map. This investigation is expected to provide complementary constraints on the nonthermal physical processes in the forming clusters.

## Acknowledgments

M. T. is grateful to Prof. T. Futamase and O. Aso. This work was initiated from the conversation with Prof. T. Futamase about the original idea of O. Aso. They and M. Hattori have also done the similar work as this paper. M. T. also thanks M. Chiba, M. Hattori, N. Seto and H. Akitaya for useful discussions and comments. We thank U. Seljak and M. Zaldarriaga for their available CMBFAST code. M. T. acknowledges support from the Japan Society for Promotion of Science (JSPS) Research Fellowships for Young Scientist. This work was supported by Japanese Grant-in-Aid for Science Research Fund of the Ministry of Education, Science, Sports and Culture Grant Nos. 01607 and 11640235, and Sumitomo Fundation.


format: text

text:
# Simulations of the adiabatic quantum optimization for the Set Partition Problem.

## 1 Introduction

Most common computationally intensive tasks encountered in practice may be formulated as combinatorial optimization problems (COPs), many of which are found to belong to the algorithmic class *nondeterministic-polynomial complete* (NP-complete) . The NP-complete problems are computationally hard - they are characterized (in the worst cases) by exponential scaling of the running time or memory requirements with the problem size. A special property of the class is that any NP-complete problem can be converted into any other NP-complete problem in polynomial time on a classical computer; therefore, it is sufficient to find a deterministic algorithm that can be guaranteed to solve all instances of just one of the NP-complete problems within a polynomial time bound.

An instance of a COP of size $`n`$ may be encoded using bit strings $`\text{z}=z_0z_1\mathrm{}z_{n1}`$, $`z_j=0,1`$, with a corresponding value of the cost function (or “energy”) $`E=E_\text{z}`$ for each string. The objective is to find the bit string(s) with the minimum cost (and the corresponding cost value). In quantum computation, bits $`z_j`$ are replaced by spin-$`\frac{1}{2}`$ *qubits*; the qubit states $`|0`$ and $`|1`$ are eigenstates of the $`\pm z`$ component of the $`j`$-th spin, respectively. The Hilbert space of a quantum *register* with $`n`$ qubits is spanned by $`N=2^n`$ basis vectors $`|\text{z}=|z_0\mathrm{}|z_{n1}`$.

## 2 Optimization by Adiabatic Quantum Evolution

Following , we consider a quantum evolution of duration $`T`$ based on the time-dependent Hamiltonian

$$H(t)=\alpha (s)V+\beta (s)H_P,ss(t).$$
(1)
Here, $`H_P=_\text{z}E_\text{z}|\text{z}\text{z}|`$ is the “problem” Hamiltonian that embodies the problem structure in its energy spectrum and eigenstates, the summation being performed over all $`N`$ $`n`$-bit strings, and $`V`$ is a “driver” Hamiltonian that is constructed in such a way as to cause transitions between those states - essentially an Ising-type spin Hamiltonian corresponding to 1- and 2-gate operations:

$$V=\underset{i=0}{\overset{n1}{}}B_i\sigma _x^i\frac{1}{2}\underset{i,j=0}{\overset{n1}{}}J_{ij}\sigma _x^i\sigma _x^j.$$
(2)
Coefficients $`\alpha \left(s\left(t\right)\right)`$ and $`\beta (s(t))`$ vary in time in such a way that at the initial instant of time $`H(0)=V`$ and at the final instant $`H(T)=H_P`$. A particular choice of the coefficients is

$$\alpha (s)=1s,\beta (s)=s,s(t)=t/T$$
(3)
The total Hamiltonian (1) produces a nontrivial quantum evolution from some initial (superposition) state $`\psi (0)`$ to a final (solution) state $`\psi (T)`$. If no knowledge about the solution is available *a priori*, then the initial state may be chosen as the symmetric state (cf. )

$$\psi (0)=2^{n/2}\underset{\text{z}=0}{\overset{2^n1}{}}|\text{z}.$$
(4)
This choice is appropriate provided (4) is a ground state of $`V`$ (e.g., $`B_i,J_{ij}0`$). Now, if $`T`$ is sufficiently large, then functions $`\alpha (t/T)`$ and $`\beta (t/T)`$ vary in time slowly and the system will remain in the instantaneous (adiabatic) ground state of $`H(t)`$ during its entire evolution $`0<t<T`$ (cf. ). Accordingly, $`\psi (T)`$ will be a superposition of states $`|z`$ corresponding to the ground state of $`H_P`$. It is clear that in this case a measurement performed on the quantum register at $`t=T`$ will find with certainty one of the solutions of COP. In this case the complexity of the quantum algorithm is determined by its duration $`T`$. If we expand the wavefunction of the system $`\psi (t)`$ in the basis of the adiabatic eigenfunctions $`\mathrm{\Psi }_k(t)`$ of the Hamiltonian $`H(t)`$

$`H(t)\mathrm{\Psi }_k(t)=g_k(t)\mathrm{\Psi }_k(t),k=0,1,\mathrm{},2^n1.`$ (5)
$`\psi (t)={\displaystyle \underset{k=0}{\overset{2^n1}{}}}C_k(t)\mathrm{\Psi }_k(t)\mathrm{exp}\left(i/\mathrm{}{\displaystyle _0^t}𝑑t^{}g_k(t^{})\right),`$ (6)
then adiabatic approximation corresponds to $`\psi (t)\mathrm{\Psi }_0(t)`$ (up to the oscillating phase factor). Coefficients $`C_k(t)`$ with $`k>0`$ correspond to nonadiabatic corrections. Using perturbation theory in the basis of eigenfunctions $`\mathrm{\Psi }_k(t)`$ the total probability $`p_{nad}(t)`$ of not finding the system at the instant $`t`$ in its adiabatic ground state equals

$`p_{nad}(t)=\left({\displaystyle \frac{\dot{s}(t)}{s(t)}}\right)^2{\displaystyle \underset{k=1}{\overset{2^n1}{}}}{\displaystyle \frac{|V_{0k}|^2}{[g_k(t)g_0(t)]^4}}`$ (8)
$`V_{0k}=\mathrm{\Psi }_0|V|\mathrm{\Psi }_k.`$
Here we used the explicit form of coefficients $`\alpha ,\beta `$ given in (3). It is seen that during the quantum evolution coefficients $`C_k(t)\dot{s}/s1/T`$ and the largest admixture of the exited states into the total superposition occurs at the instant of time when one of the exited levels $`g_k(t)`$ closely approaches the ground state (avoided-crossing). From here the overall criterion for the adiabatic evolution can be expressed in the well-known form

$$\eta =\frac{\stackrel{~}{V}}{T\mathrm{\Delta }g_{min}^2}1,$$
(9)
where $`\mathrm{\Delta }g_{min}`$ is the closest approach of the ground state to one of the excited states during the evolution - a minimum gap- and $`\stackrel{~}{V}`$ is the characteristic energy scale for the matrix elements of $`V`$. We note that although instantaneous nonadiabatic corrections (8) are quadratic in the parameter $`\eta `$ (near the avoided crossing) the probability of nonadiabatic transitions $`W_{nad}`$ away from the ground state is exponentially small in $`\eta `$ . This probability is defined on an infinite time axis and its logarithm is proportional to the imaginary part of the integral along the contour in the complex plane of $`t`$ that begins and ends on the real time axis and loops around the complex branching point $`t^{}`$

$$W_{nad}\mathrm{exp}\left(|\mathrm{Im}g_0(t)𝑑t|\right).$$
(10)
Here $`t^{}`$ correspond to one of the roots of the equation

$$g_k(t^{})=g_0(t^{})$$
(11)
that provides the smallest value for the exponential in (10) (out of all possible complex solutions of (10) for different excited states $`\mathrm{\Psi }_k`$). In a standard (Landau-Zener) theory of nonadiabatic transitions the value of the exponent is approximately of the order of the parameter $`\eta `$ in (9), and therefore it is the size of the minimum gap $`\mathrm{\Delta }g_{min}`$ that determines the condition for T and hence the complexity of the quantum adiabatic search algorithm according to . We note finally that, as pointed out in , the improved complexity of the adiabatic algorithm is determined by the instantaneous rate $`\dot{s}(t)/s(t)`$ of the variation of the control parameter $`s(t)`$ near the avoided crossing. We will not discuss in this paper such modifications and focus primarily on intrinsic properties of the quantum system in question.

## 3 Set Partition Problem

In this paper, we will analyze the complexity of the adiabatic quantum optimization for the *set partition problem* (SPP), which is one of the basic NP-complete problems of theoretical computer science . The optimization version of SPP is to partition a set of $`n`$ positive integers $`\{\alpha _0,a_1,\mathrm{},\alpha _{n1}\}`$ into two disjoint subsets $`𝒜_1`$ and $`𝒜_2`$ such that the “residue” $`|_{\alpha _j𝒜_1}\alpha _j_{\alpha _j𝒜_2}\alpha _j|`$ is minimized. The complexity of the problem substantially depends on the size of the integers $`\alpha _j`$ (see below). It is often customary for the analysis of the random instances of the problem to introduce finite-precision rational numbers $`a_j`$ that are independently and identically distributed (i.i.d.) in the unit interval $`(0,1]`$.

$$\alpha _j2^bj,a_j=2^b\alpha _j(0,1]$$
(12)
Here $`b`$ is the total number of bits used to represent the numbers $`a_j`$. The values of the partition can be encoded in binaries by attaching “sign” bits $`s_j`$ to the numbers $`a_j`$. The partition residue can be defined as $`|\mathrm{\Omega }_\text{z}|`$ where

$$\mathrm{\Omega }_\text{z}=\underset{j=0}{\overset{n1}{}}s_ja_j,s_j=12z_j=\pm 1(z_j=0,1)$$
(13)
Here $`\mathrm{\Omega }_\text{z}`$ is a signed partition residue. We note that by definition the problem is symmetric: two bit strings that can be obtained from each other by flipping all the bits ($`s_js_j`$) correspond to two values of $`\mathrm{\Omega }_\text{z}`$ that differ only in sign. We note that the minimum-residue partition(s) may be thought of as the ground state(s) of the following spin Hamiltonian

$$\mathrm{\Omega }_\text{z}^2=\underset{i,j=0}{\overset{n1}{}}a_ia_js_is_j.$$
(14)
This is an infinite range Ising spin glass with Mattis type antiferromagnetic coupling, $`J_{ij}=a_ia_j`$. Infinite range coupling clearly represents a major problem with direct (‘analog’) physical implementation of this Hamiltonian on a quantum computer. Therefore one can consider using an oracle-type cost function $`E(\text{z})=|\mathrm{\Omega }_\text{z}|`$ to implement the problem Hamiltonian in (1) for SPP. The corresponding unitary transformation will multiply the basis states $`|z`$ by phase factors $`\mathrm{exp}\left(i\mathrm{\Delta }tE(\text{z})\right)`$ during the elementary discrete steps of the ‘continuous-time’ adabatic quantum optimization (1). Although this approach is natural for the satisfiability problem  it has a serious limitation for SPP (as well as some other NP-complete problems like integer programming, where the precision of integers is of central importance). To demonstrate this point we need to consider the density of states of the partition residues.

#### 3.0.1 Density of states

We define the density of states for a given instance of SPP as follows

$$\rho (\mathrm{\Omega })=\underset{\text{z}}{}\delta (\mathrm{\Omega }\mathrm{\Omega }_\text{z}).$$
(15)
The exact form of $`\rho (\mathrm{\Omega })`$ depends on a given instance of SPP (i.e., a particular set of numbers $`a_j`$). However we introduce a coarse-grained density of states

$$\overline{\rho }(\mathrm{\Omega })=\frac{1}{\mathrm{\Delta }\mathrm{\Omega }}_\mathrm{\Omega }^{\mathrm{\Omega }+\mathrm{\Delta }\mathrm{\Omega }}\rho (\zeta )d\zeta $$
(16)
where averaging is over an interval of $`\mathrm{\Delta }\mathrm{\Omega }`$ whose size will be determined below. Using (13) and (15) we can rewrite this expression in the form

$$\overline{\rho }(\mathrm{\Omega })=\frac{2^n}{2\pi }_{\mathrm{}}^{\mathrm{}}\frac{e^{iw(\mathrm{\Omega }+\mathrm{\Delta }\mathrm{\Omega })}e^{iw\mathrm{\Omega }}}{iw}I(w)dw,I(w)=\underset{j=0}{\overset{n1}{}}\mathrm{cos}(a_jw).$$
(17)
Note that $`I(\pi k2^b)=(1)^k,k=0,\pm 1,\mathrm{}`$ and $`I(w)`$ has very sharp maxima (minima) at those points. In their vicinities the integral in (17) can be evaluated by steepest descent method for any given problem instance. The sum over the contributions from different saddle points was obtained by Mertens  in his derivation of the partition function for the corresponding spin glass model. We emphasize however that $`I(w)`$ can have multiple sharp resonances at the intermediate points $`|w|<2^b`$. The positions of these resonances are at the multiples of $`\pi /q`$ where $`q`$ is an approximate greatest common divisor (g.c.d.) of the set of $`n`$ numbers $`a_j`$ such that $`a_j=f_jq+r_j`$ where $`f_j`$ are integers and $`r_j`$ are residues of the division. Provided that most of the residues are sufficiently small

$$\frac{\pi ^2}{2}\underset{j=1}{\overset{p}{}}r_j^21,pn,$$

the function $`I(w)`$ will have steep peaks at those points. It can be shown that in the general case the value of the approximate g.c.d. for a set of $`n`$ $`bbit`$ numbers inside the unit interval scales as $`2^n`$ for $`n<b`$. Obviously it equals $`2^b`$ for $`n>b`$. In what follows we will be interested in the high-precision case $`n<b`$. We choose the size of the averaging window $`\mathrm{\Delta }\mathrm{\Omega }2^n`$ and this introduces a cut-off in the integral (14) at

$$|w|\pi /\mathrm{\Delta }\mathrm{\Omega }2^n$$

It follows from above that in this case the values of the g.c.d. will lie outside the cutoff and corresponding resonances will not contribute to the integral. The value of the integral can be estimated near the single remaining maximum at $`w=0`$. The width of the maximum near that point is $`\delta wn^{1/2}1`$ and therefore the window function in (13) works as a step function in that region. Finally we obtain

$$\overline{\rho }(\mathrm{\Omega })=\frac{2^n}{\sqrt{2\pi n\sigma ^2}}\mathrm{exp}\left(\frac{\mathrm{\Omega }^2}{2n\sigma ^2}\right),\sigma ^2=\frac{1}{n}\underset{j=0}{\overset{n1}{}}a_j^2.$$
(18)
Here the variance $`\sigma `$ is a “self-averaging” quantity, and the coarse-graining is performed over an interval much larger than the characteristic separation between neighboring partition residue values

$$\mathrm{\Delta }E\sqrt{n}\mathrm{\hspace{0.17em}\hspace{0.17em}2}^n$$
(19)
yet much smaller than the scale of variation of $`\rho (\mathrm{\Omega })`$: $`\mathrm{\Delta }E\mathrm{\Delta }\mathrm{\Omega }\sqrt{n}`$. We note that in the high-precision regime ($`n<b`$), partition residues $`\mathrm{\Omega }_\text{z}`$ are irregularly spaced and well separated from each other (on the scale of $`2^b`$). However this structure is being averaged out in (18) and the result indicates that, in general, no more structure exists on a scale $`2^n`$ other than that given by the Gaussian distribution in (18). We note that this distribution is usually obtained for the SPP using averaging over different instances of the problem (cf. , (*b*)); here we recovered it as a coarse-grained distribution for a given instance which is more consistent with our goal of studying the complexity of the adiabatic quantum optimization algorithm .

### 3.1 Cost function

Computational complexity of SPP depends critically on the number of bits $`b`$: numerical simulations with independent identically distributed (i.i.d.) random $`b`$-bit numbers $`a_j`$ show  that the solution time grows exponentially with $`n`$ for $`2^{nb}1`$ (high-precision, computationally ‘hard phase’), and polynomially for $`2^{nb}1`$ (low-precision, computationally ‘easy phase’), exhibiting a behavior similar to a phase transition (*a*).

In the low-precision phase, values of $`\mathrm{\Omega }_\text{z}`$ are equally spaced (in $`2^b`$) and strongly degenerate each corresponding to (roughly) $`2^{bn}1`$ number of bit-strings. This degeneracy grows exponentially with n if $`b`$ remains fixed. The total number of solutions with zero residues accumulate correspondingly and this is why the complexity eventually becomes polynomial in $`n`$. The quantum algorithm suggested in  directly computes the density of states (15) of the SPP and is efficient in finding the number of solutions in the low-precision case. In this case it is also feasible to use a cost function $`E(\text{z})=|\mathrm{\Omega }_\text{z}|`$ (provided the number of possible values does not grow exponentially with $`n`$).

The situation is qualitatively different in the high-precision case. Implementation of the approach based on the above cost function will require a quantum computer using exponentially high precision physical parameters (external fields, etc) to control small differences in the phases of unitary transformations on the scale at least $`2^n`$. This is a technical difference from the constraint satisfaction problem in which the cost function generally takes only the set of values that scales polynomially with $`n`$; the size of the set equals the total number of constraints $`m`$ (the computationally most difficult case corresponds to $`mn`$ and the case of $`m2^n`$ is not of general interest there). To avoid the above restriction in the implementation of the adabatic quantum optimization algorithm for SPP, we introduce a cost function $`E(\mathrm{\Omega })`$ based on a logarithmic scale of the partition residue values:

$`E(\mathrm{\Omega })=0,\mathrm{for}0|\mathrm{\Omega }|/\mathrm{\Delta }<1,`$ (20)
$`E(\mathrm{\Omega })=k,\mathrm{for}2^{k1}|\mathrm{\Omega }|/\mathrm{\Delta }<2^k,k=0,1,\mathrm{}L,`$
$`2^{L1}A/\mathrm{\Delta }<2^L,A={\displaystyle \underset{j=0}{\overset{n1}{}}}a_j.`$
Since the density of states is linear at $`\mathrm{\Omega }\sqrt{n}`$ number of states $`d_k`$ per energy level $`E(\mathrm{\Omega }_\text{z})=k`$ will grow exponentially with $`k`$ in that range ($`2^k`$). The total number of levels $`L`$ depends on the value of $`\mathrm{\Delta }`$. Using the density of states (18) for $`\mathrm{\Omega }_\text{z}\sqrt{n}`$ one can set

$$\mathrm{\Delta }=\sqrt{n}\mathrm{\hspace{0.17em}2}^nK.$$
(21)
where $`K`$ is some fixed number (a few dozen) independent of $`n`$. The number of ground states of the problem Hamiltonian

$$H_P=\underset{k=0}{\overset{L1}{}}E(\mathrm{\Omega }_z)|zz|$$
(22)
approximately equals $`K`$, and the total number of energy levels $`L`$ is close to $`n`$. It can be estimated from (20) that $`nLlog_2K`$. The distribution of the low-lying states $`d_k`$ with cost function (20) is somewhat similar to that in the slightly underconstrained cases of the satisfiability problem.

## 4 Results

To study the complexity of the adiabatic quantum optimization algorithm for SPP, we numerically integrate the time dependent Schrödinger equation with the Hamiltonian $`H(t)`$ (1), (2) in which we set $`B_i=1`$ and $`J_{ij}=0`$. We start from the symmetric initial state (4) and integrate the Schrödinger equation in the interval $`0tT`$. Unlike the approach adopted in  we do not set a-priori a value of success probability. Instead we introduce a complexity metric for the algorithm

$$𝒞(T)=\frac{T+1}{p_0(T)}d_0.$$
(23)
Here $`p_0(T)`$ is the total probability of finding the system in its ground level (with $`E(\mathrm{\Omega }_\text{z})=0`$) at the end of the algorithm, $`t=T`$, and $`d_0`$ is the number of states at the ground level. The algorithm has to be repeated on average $`d_0/p_0(T)`$ number of times to reach success probability $``$ 1. A typical plot of $`𝒞(T)`$ for an instance of SPP with $`n`$=15 numbers is shown in Fig. 1. At very small $`T`$ the wavefunction is close to the symmetric initial state and the complexity is $`2^n`$. The extremely sharp decrease in $`𝒞(T)`$ with $`T`$ is due to the buildup of the population $`p_0(T)`$ in the ground level as quantum evolution approaches adiabatic limit. At certain $`t=T^{}`$ the function $`𝒞(T)`$ goes through the minimum: for $`T>T^{}`$ the decrease in the number of trials $`d_0/p_0(T)`$ does not compensate anymore for the overall increase in the runtime $`T`$ for each trial. The minimal complexity $`C^{}=C(T^{})`$ is defined via one dimensional minimization over $`T`$ for a given problem instance .

In Fig.2 we plotted the data for optimal complexities $`C^{}`$ at different values of $`n`$ on a logarithmic scale. Vertical sets of points on the plot indicate the results for all simulation data we currently have for each $`n`$. The results indicate that the median value of complexity $`C^{}`$ scales exponentially with $`n`$; linear fit to the graph gives $`\mathrm{log}C^{}0.56n`$. This corresponds to the scaling law $`C^{}2^{0.8n}`$. The exponential behavior of the algorithm clearly manifests itself for the larger values of $`n`$ 11. The scatter in the values of $`\mathrm{log}C^{}`$ appears to decreases with $`n`$ however this result is probably due to the smaller number of data points available for larger $`n`$ values.

In Fig. 3 we show the distribution of the probabilities $`|z|\psi (T)|^2`$ for different values of $`T`$ for an instance of SPP with $`n`$=15 (plots for different $`T`$ shown with different colors)and precision b=25 bits. Values of $`z`$ are ordered with respect to the corresponding values of the partition residues $`|\mathrm{\Omega }_\text{z}|`$. It is clearly seen on logarithmic scale that probability distribution forms ’steps’ corresponding to different values of the cost function $`E(\mathrm{\Omega }_\text{z})`$ defined in (20). Within each step, the distribution of probabilities does not reveal any structure. The same property holds also for intermediate times ($`t<T`$). Detailed analytical results  indicate that it is this absence of structure in $`\psi _z(t)`$ that is responsible for the exponential complexity of the algorithm.

### The Stationary Schrödinger equation

In addition to solving the time-dependent Schrödinger equation we also analyzed the adiabatic solutions of the stationary Schrödinger equation with the same form of the Hamiltonian $`H(t)`$ (1) as above. Our preliminary results were obtained using Mathematica for modest values of $`n`$ 10. The results for n=10 are shown in Figs. 4 and 5. Figure 5 represents the magnified part of Fig. 4 near the avoided crossing region. Adiabatic eigenvalues were computed for different values of the scaled time parameter $`s=t/T(0,1)`$. The solid line represents the evolution of the ground state eigenvalue between $`s=0`$ and $`s=1`$. The vertical sets of points correspond to excited adiabatic levels for a given $`s`$. At the beginning ($`s=0`$) eigenvalues correspond to those of the Hamiltonian $`V`$: equally spaced levels -n,-n+2, $`\mathrm{}`$, n, corresponding to different number of spin excitations along the $`x`$ quantization axis. The first excited state is $`n`$fold degenerate, the second is $`n(n1)`$, the k-th exited state is $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$-fold degenerate, etc. For $`s>0`$ the degeneracy is removed. For $`s1`$ the eigenvalue spectrum is the one for the problem Hamiltonian $`H_P`$ (in 22). We have shifted the energy reference in the Hamiltonian $`H_P`$ by $`n`$ (cf. also (1)) to match the energy scale for the symmetric case which emphasizes the avoided crossing region. In our case the ground state was 13-fold degenerate and the corresponding eigenvalues merge at $`s1`$. The close approach of these eigenvalues is not relevant for the minimum-gap analysis since they all end up in the same final level. However the minimum separation of the instantaneous adiabatic ground state eigenvalue from the excited state eigenvalues that do not end up on the same ground level at $`s=1`$ is clearly seen in the figures. Note that the size of this separation is much greater than the separations between the excited states. This behavior clearly departs from the standard 2-level avoided crossing picture and is due to the contributions from the exponential number of terms in (8) as will be analyzed elsewhere . We also note that the value n=10 does not correspond to the exponential scaling regime for the algorithmic complexity that appears to start for greater $`n`$ values as follows from the discussion above.

In conclusion, we have performed numerical simulations of the adiabatic quantum optimization for SPP using a step-like density of states defined on a logarithmic scale of partition residues. The results indicate an exponential scaling of the algorithmic complexity as a function of the problem size. The apparent reason is the loss of structure in SPP during the effective coarse-graining over the intervals of partition residues corresponding to the same cost function values.