text:
# A Useful Approximation for Computing the Continuum Polarization of Be Stars

## 1 Motivation

The idea that the H$`\alpha `$ emission lines of Be stars originate from an equatorially flattened circumstellar envelope or disk has now been directly verified by interferometric imaging (Quirrenbach et al. 1997). The related explanation of the linear polarization of Be stars as due to scattering of the starlight by free electrons in the disk was also confirmed, because the observed position angle of the polarization was found to be perpendicular to the direction of elongation of the disk as projected onto the plane of the sky. It is this apparent asymmetry of the scattering region that results in a net polarization, by defeating the cancellation which would take place if there were identical scattering subregions in adjacent quadrants of the projected disk (see Fig. 1).

A thorough historical review of both observation and theory of polarization in Be stars was given by Coyne & McLean (1982). Since that time the major observational developments in the field have been increased spectral resolution by spectropolarimetry and extension of the wavelength coverage into the ultraviolet by space-based observations (Bjorkman 2000). Beginning with the pioneering work of Poeckert & Marlborough (1978a,b), who calculated the single scattering polarization in an NLTE hydrogen envelope, theoretical analysis and modeling of the continuum polarization of Be star disks has progressed through increasingly complicated treatments. Fox (1991) developed analytic equations to calculate the single scattering polarization for axisymmetric envelopes. Bjorkman & Bjorkman (1994) extended the single scattering calculations to include attenuation and emission within the envelope. Hillier (1994) developed polarization source functions using traditional Feutrier methods to integrate the transfer equation for optically thick cases, while Wood, Bjorkman, & Bjorkman (1997, hereafter WBB) developed Monte Carlo methods.

One may wonder, then, if there is anything new to be learned about Be stars from continued broadband polarimetry. The answer is, of course, that even though we now have firmer knowledge of the disk characteristics, including temperature, density, and geometry, broadband polarization monitoring is still a primary source of information on the variability of these quantities over time scales of years to decades, which are typical of the most fundamental aspect of the Be phenomenon: the unpredictable transition from the normal B phase to the Be phase and back again, associated with the formation and later dissipation of the circumstellar envelope.

This paper attempts to establish a simple and approximate, but nevertheless serviceable approach to the modeling and analysis of $`UBVRI`$ polarimetry data to derive the basic envelope parameters. Tracing the observed variability in terms of these parameters still promises to give valuable hints about the nature of the unknown processes involved in the Be phenomenon.

## 2 A Spherical Sector Envelope Model

Figure 2 shows the geometry of the circumstellar envelope model adopted for this study. Introduced by Kruszewski, Gehrels, & Serkowski (1968) to investigate the polarization of red variables, it was later used by Brown & McLean (1977) to illustrate their theoretical formulation of the polarization by electron scattering in a Be disk. Its shape may be described as an axially symmetrical sector of a sphere, with a wedge-shaped cross section opening outward at half-angle $`\alpha `$.

For small opening angles the spherical sector is a good representation of an equatorial disk, with the advantage of being mathematically suited for spherical coordinates. A basic starting point is to assume the disk is pure hydrogen with uniform electron temperature $`T_e`$, extending to infinite distance ($`R_e\mathrm{}`$ in Fig. 2) from a central star of radius $`R_{}`$, with electron number density $`N_e`$ given by a radial power law with exponent $`\eta `$ :

$$N_e(r)=N_{0e}\left(\frac{R_{}}{r}\right)^\eta .$$
(1)
Waters, Coté, & Lamers (1987) derived values of $`2.0<\eta <3.5`$ for some of the stars also studied in this paper using the slope of the infrared continuum from $`IRAS`$ observations, but the spherical sector model with $`R_e\mathrm{}`$ has the peculiarity that the disk mass is infinite unless $`\eta >3.0`$. In what follows, the symbol $`\eta `$ will be retained for generality, but $`\eta =3.1`$ is used as a representative mean value in all the numerical computations.

## 3 An Approximation for the Gray Polarization

According to Fox (1991) except for a sign error in the first argument of the beta function $`B`$, the net polarization of light from a central star due to scattering of photons by free electrons (Thomson scattering) in a surrounding envelope may be roughly approximated for the specific case of the infinite spherical sector geometry as

$$p_0=\frac{3(\eta 1)}{16}B(\frac{\eta 1}{2},\frac{3}{2})\tau _e\mathrm{sin}\alpha \mathrm{cos}^2\alpha \mathrm{sin}^2i,$$
(2)
where $`i`$ is the angle of inclination of the rotation axis of the star to the line of sight and

$`\tau _e`$ $`=`$ $`{\displaystyle _R_{}^{\mathrm{}}}N_{0e}\left({\displaystyle \frac{R_{}}{r}}\right)^\eta \sigma _e𝑑r`$ (3)
$`=`$ $`{\displaystyle \frac{N_{0e}\sigma _eR_{}}{\eta 1}}\text{(finite only for }\eta >1.0)`$
is the total radial optical depth for electron scattering in the equatorial plane of the spherical sector in terms of the Thomson scattering cross section

$$\sigma _e=\frac{8\pi }{3}\left(\frac{e^2}{mc^2}\right)^2.$$
(4)
Equation (2) is only a single-scattering approximation, based on the assumption that the disk is optically thin and neglecting multiple scattering. It includes a correction for the geometrical complication that the star is an extended source of light and cannot be treated as a point source (Cassinelli, Nordsieck, & Murison 1987, hereafter CNM), but it does not take into account the occultation of part of the scattering envelope by the star.

## 4 Including the Wavelength Dependence

So far the calculated polarization has no dependence on wavelength, since it comes from pure electron scattering. However, neutral hydrogen in the envelope absorbs some light both before and after scattering, and the envelope emission (which is treated here as unpolarized and is not considered to scatter) dilutes the polarization. It is therefore necessary to include these wavelength-dependent effects, since they combine to produce the slope of the continuum polarization and the well-known abrupt changes in the polarization at the H I ionization series limits, as first demonstrated by Capps, Coyne, & Dyck (1973) and later refined by McLean (1979).

Assuming LTE ionization fractions and level populations, equation (5) gives the total wavelength-dependent opacity $`\kappa (\lambda )`$ per gram of neutral hydrogen in the ground state (Aller 1963). $`C_0`$ is a fixed numerical factor, $`X(n)`$ is the ionization energy from level $`n`$ in units of $`kT_e`$, and $`C_{se}`$ is the correction factor for stimulated emission. The three individual terms in the equation are a summation over the ionization edges of the first seven discrete energy levels, an integrated term for the combination of all the remaining levels, and a free-free absorption term (with Gaunt factors taken to be unity). See Appendix A for a discussion of NLTE corrections.

$$\kappa (\lambda )=C_0e^{X(1)}\lambda ^3\left(\underset{\lambda <\lambda _n}{\overset{X(n)}{}}\frac{e^{X(n)}}{n^3}+\frac{(e^{X(8)}1)}{2X(1)}+\frac{1}{2X(1)}\right)C_{se},$$
(5)
where

$$C_0=\frac{32\pi ^2e^6R}{3\sqrt{3}m_Hh^3c^3},$$
(6)
$$X(n)=\frac{2\pi ^2m_ee^4}{n^2h^2kT_e},$$
(7)
and

$$C_{se}=\left(1e^{hc/\lambda kT_e}\right).$$
(8)
If the free electron number density $`N_e(r)`$ and the electron temperature $`T_e`$ are known, then the number density $`N_1(r)`$ of neutral hydrogen atoms in the ground state can be found from the Saha equation:

$`N_1(r)`$ $`=`$ $`{\displaystyle \frac{h^3}{(2\pi m_ekT_e)^{3/2}}}N_e^2(r)e^{X(1)}`$ (9)
$`=`$ $`N_{01}\left({\displaystyle \frac{R_{}}{r}}\right)^{2\eta },`$
where

$$N_{01}=\frac{h^3}{(2\pi m_ekT_e)^{3/2}}N_{0e}^2e^{X(1)}.$$
(10)
The total radial optical depth for neutral hydrogen absorption in the equatorial plane of the spherical sector is therefore

$`\tau _a(\lambda )`$ $`=`$ $`{\displaystyle _R_{}^{\mathrm{}}}\kappa (\lambda )m_HN_{01}\left({\displaystyle \frac{R_{}}{r}}\right)^{2\eta }𝑑r`$ (11)
$`=`$ $`{\displaystyle \frac{N_{01}m_H\kappa (\lambda )R_{}}{2\eta 1}}\text{(finite only for }\eta >0.5),`$
which acts as a wavelength-dependent attenuation factor to reduce the gray polarization.

The volume emission coefficient of the envelope is

$$j(\lambda ,r)=m_H\kappa (\lambda )N_{01}\left(\frac{R_{}}{r}\right)^{2\eta }B(\lambda ),$$
(12)
where

$$B(\lambda )=\frac{2hc^2}{\lambda ^5(e^{hc/\lambda kT_e}1)}$$
(13)
is the Planck function (not to be confused with the beta function in §3). The total luminosity of the envelope is then

$`L(\lambda )`$ $`=`$ $`4\pi {\displaystyle _0^{2\pi }}{\displaystyle _{\frac{\pi }{2}\alpha }^{\frac{\pi }{2}+\alpha }}{\displaystyle _R_{}^{\mathrm{}}}j(\lambda ,r)r^2\mathrm{sin}\theta drd\theta d\varphi `$ (14)
$`=`$ $`{\displaystyle \frac{16\pi ^2}{2\eta 3}}N_{01}m_H\kappa (\lambda )B(\lambda )R_{}^3\mathrm{sin}\alpha \text{(finite only for }\eta >1.5),`$
which together with the stellar flux $`F_{}(\lambda )`$ produces a further wavelength dependence of the polarization. Theoretical values of the stellar flux $`F_{}(\lambda )`$ are taken from tabulated model atmospheres by Kurucz (1994).

With the wavelength dependence included, our polarization estimate may now be written as

$$p(\lambda )=\frac{p_0e^{\tau _a(\lambda )}}{1+L(\lambda )/(4\pi R_{}^2F_{}(\lambda ))}.$$
(15)
It should be emphasized that this equation is only an approximation (even if the disk is optically thin), since it includes neither the contribution of scattering of the disk emission to the polarization nor attenuation of the direct starlight by the disk. Also the neutral hydrogen opacity is treated in a very crude way, using only the maximum radial optical depth in the equatorial plane.

It may be of interest to calculate the total mass of the disk, which can be done approximately by simply counting pairs of electrons and protons under the assumption that it consists purely of fully ionized hydrogen:

$`M`$ $`=`$ $`{\displaystyle _0^{2\pi }}{\displaystyle _{\frac{\pi }{2}\alpha }^{\frac{\pi }{2}+\alpha }}{\displaystyle _R_{}^{\mathrm{}}}m_HN_{0e}\left({\displaystyle \frac{R_{}}{r}}\right)^\eta r^2\mathrm{sin}\theta drd\theta d\varphi `$ (16)
$`=`$ $`{\displaystyle \frac{4\pi }{\eta 3}}N_{0e}m_HR_{}^3\mathrm{sin}\alpha \text{(finite only for }\eta >3.0).`$
## 5 Synthesizing Broadband Data

Adjustment of the envelope parameters in the theoretical model to give results consistent with observations might be expected to yield valuable information about the nature of Be disks. To compare with observations on the Johnson-Cousins $`UBVRI`$ system, it is first necessary to convolve the theoretically estimated polarization p($`\lambda `$) from equation (15) with the bandpass characteristics of the optical system.

As a first approximation, let us assume Gaussian filter transmission curves based on the standard $`UBVRI`$ wavelengths and $`fwhm`$ (Bessell 1979), which are closely matched by the system actually used for the observations (see Table 1).

Given the central wavelength $`\lambda _c`$, the standard deviation $`\sigma `$ can be calculated from the $`fwhm\mathrm{\Gamma }`$ since $`\mathrm{\Gamma }=2.354\sigma `$ for a Gaussian distribution, so that the transmission function may be written as

$$T(\lambda )=\mathrm{exp}\left[\frac{1}{2}\left(\frac{\lambda \lambda _c}{\mathrm{\Gamma }/2.354}\right)^2\right].$$
(17)
The theoretical total flux $`F(\lambda )`$ is due to the stellar component $`F_{}(\lambda )`$ plus the envelope component:

$$F(\lambda )=F_{}(\lambda )+L(\lambda )/(4\pi R_{}^2).$$
(18)
Convolving the polarization in terms of flux with the transmission function, where $`\lambda _{min}`$ and $`\lambda _{max}`$ are, to a realistic approximation, the 10% response points, we find a theoretical expression for the expected polarization over the given bandpass:

$$P(BP)=\frac{_{\lambda =\lambda _{min}}^{\lambda _{max}}p(\lambda )F(\lambda )T(\lambda )\mathrm{\Delta }\lambda }{_{\lambda =\lambda _{min}}^{\lambda _{max}}F(\lambda )T(\lambda )\mathrm{\Delta }\lambda }.$$
(19)
## 6 Adjustable Parameters & Model Fits

With the model in hand, an interactive graphical computer interface was designed to allow adjusting the input parameters by trial and error to fit $`UBVRI`$ polarization measurements (McDavid 1999) of eight Be stars. Solutions obtained this way should be viewed with some caution since they may not be unique: different geometrical distributions of scatterers can produce the same net polarization. Moreover, given the gross approximations involved, only order-of-magnitude results should be expected.

The model disk has three adjustable parameters: the maximum electron number density $`N_{0e}`$, the angle of inclination $`i`$ of the rotation axis to the line of sight, and the opening half-angle $`\alpha `$. Additionally required fixed parameters for each individual star are the radius $`R_{}`$, the effective temperature $`T_{}`$, and the surface gravity $`\mathrm{log}g`$, which were estimated from Table 1 of Collins, Truax, & Cranmer (1991) based on spectral types from Slettebak (1982). The electron temperature of the disk was then fixed at $`T_e=0.75T_{}`$ and the appropriate Kurucz flux table chosen to match $`T_{}`$ and $`\mathrm{log}g`$.

The fixed disk temperature $`T_e`$ affects the wavelength dependence of the polarization through its influence on the neutral hydrogen opacity by setting the degree of ionization and the populations of the excited states (eq. ). It influences not only the hydrogen absorption optical depth (eq. ), but also the disk luminosity (eq. ), which is another contributor to the wavelength dependence of the polarization. As a result, $`T_e`$ is important in determining the polarization Balmer jump and the slope of the polarization over the Paschen continuum, both of which generally increase at lower temperatures. Appendix A explains the NLTE corrections to the level populations which are necessary to fit these features for some of the program stars.

It is instructive to summarize individually the effects of the three adjustable parameters on the behavior of $`p(\lambda )`$ according to equation (15).

(1) The overall degree of gray polarization is directly proportional to $`N_{e0}`$ through the factor $`\tau _e`$ in equation (2). However, simply increasing $`N_{e0}`$ does not always result in an overall polarization increase, because it also increases the attenuation and adds to the wavelength dependence of the polarization through $`\tau _a(\lambda )`$ (eq. ) and $`L(\lambda )`$ (eq. ).

(2) The earliest basic electron scattering models (e.g. Brown & McLean 1977) gave a $`\mathrm{sin}^2i`$ dependence of the polarization on $`i`$, and further refinements have not qualitatively changed the simple picture of Figure 1 in which a face-on disk shows no net polarization because of symmetrical cancellation, while the maximum asymmetry of an edge-on disk results in the maximum polarization. It may seem likely that $`i`$ is poorly determined in this model since the same polarization might be obtained, for example, by decreasing $`i`$ while increasing $`\alpha `$, keeping $`N_{e0}`$ constant. Experiments do not bear this out, though, because a thicker disk has a higher luminosity, which changes the wavelength dependence of the polarization enough to ruin the fit (eq. ). Another helpful constraint on $`i`$ is the presence or absence of shell lines, which are thought to be absorption features in the spectral line profiles due to circumstellar material in the line of sight for nearly edge-on equatorial disks. Since Be stars are generally rapid rotators, spectroscopic measurement of the projected rotational velocity $`v\mathrm{sin}i`$ can also suggest roughly the value of $`i`$.

(3) Figure 3 shows how the model polarization $`p^B`$ in the $`B`$ passband varies as $`\alpha `$ increases from $`0\mathrm{°}`$ to $`90\mathrm{°}`$ using a typical set of parameters. The polarization first rises as the widening disk presents an increasing number of scatterers, then begins to decline due to the buildup of enough density at high latitudes to cancel the polarization from the equatorial regions. The model of Waters & Marlborough (1992) also shows this behavior, which becomes of practical concern because the hump-shaped graph allows for both a “thick disk” and a “thin disk” solution, producing identical polarization at $`\alpha `$ values on opposite sides of the peak. For equal densities, however, the thick disk will have a higher luminosity than the thin disk, giving the polarization a recognizably different wavelength dependence.

Figures 4–11 present possible (but not necessarily unique) model fits for the eight program Be stars, with the parameters summarized in Table 2. The observational data points, plotted as open squares with vertical error bars, are intrinsic polarization, corrected for the interstellar component by Stokes vector subtraction (McDavid 1999). The corresponding model result is plotted as a solid line, using open circles for the broadband values with horizontal line segments to show the filter passbands. Several additional quantities derived from the model are also included in Table 2 for each fit: the maximum polarization $`pmax`$ and its wavelength $`\lambda (pmax)`$, the maximum of the H I absorption optical depth $`\tau _amax`$ and its wavelength $`\lambda (\tau _amax)`$, the electron scattering optical depth $`\tau _e`$, the total envelope mass $`M`$, and the NLTE departure coefficients $`b_2`$ and $`b_3`$ for the populations of the first two excited states of the neutral hydrogen in the disk. Refer to Appendix A for a discussion of NLTE considerations.

## 7 Test of Accuracy

Since the model presented here is such a crude approximation, it is important to compare its results with those from a more sophisticated model to investigate, at least qualitatively, the accuracy we can expect. The Monte Carlo code of WBB is one such standard, and it is based on the same set of input parameters except that the density input is the electron scattering optical depth rather than the electron number density, which requires only a minor conversion. Ideally we would like to determine WBB fits to the program star observations, and then quantitatively evaluate the simplified model by direct comparison of the fit parameters. Unfortunately, because of the slow convergence of the Monte Carlo method, deriving a WBB fit is a complex process requiring substantial amounts of cpu time even on a fast computer. Otherwise there would be no reason for interest in the kind of quick approximation that is the subject of this paper.

For the time being, though, we can at least make use of the existing WBB fit to $`\zeta `$ Tau. Figure 12 shows examples of $`p(\lambda )`$ for the quick approximation (solid line with broadband filter points marked by open circles) compared to the full optically thick multiple scattering WBB simulation (dashed line connecting filled circles). Errors in the WBB data points are on the order of 0.03%, limited by computing time. The observed $`UBVRI`$ data are plotted as open squares with error bars. Using the parameters $`R_{}=5.5R_{\mathrm{}}`$, $`T_{}=19,000`$ K, $`T_e=15,000`$ K, $`\alpha =2\stackrel{}{\mathrm{.}}5`$, and $`i=82\stackrel{}{\mathrm{.}}0`$ from the WBB solution as input to both models, the six plots show what happens as $`\tau _e`$ is increased by steps from 0.10 to 3.00 (the best fit value according to WBB).

This test shows that the optically thin approximation agrees quite well with the WBB calculation up to and including an optical depth of 1.00. It is also encouraging that for $`\zeta `$ Tau the best fit of the approximate method as shown in Figure 7 and Table 2 has $`N_{e0}=4.20\times 10^{12}\mathrm{cm}^3`$, which is well within the range of $`2.38\times 10^{12}N_{0e}7.54\times 10^{12}\mathrm{cm}^3`$ found by Waters, Coté, & Lamers (1987) in their infrared study.

However, it must be noted that there is a possibly serious disagreement between the WBB model and the simplified model presented here with regard to the best-fit values of $`\tau _e`$ and $`\alpha `$ for $`\zeta `$ Tau. While the WBB disk ($`\tau _e=3.00`$ and $`\alpha =2\stackrel{}{\mathrm{.}}5`$) is optically thick but geometrically thin, the simplified model disk ($`\tau _e=0.65`$ and $`\alpha =6\stackrel{}{\mathrm{.}}0`$) is optically thin and geometrically thicker (although it still qualifies as “geometrically thin”).

In Figure 12 the approximate model fails to produce a polarization large enough to fit the observations of $`\zeta `$ Tau by increasing $`\tau _e`$ at constant $`\alpha `$ because it becomes dominated by H I opacity. As shown in Table 2, this problem is seemingly avoided by increasing $`\alpha `$ instead of $`\tau _e`$, but the resulting optically thin solution could possibly be ruled out on other grounds, such as the associated infrared emission as discussed by WBB. This is only one cautionary example emphasizing the importance of independent observational consistency checks in the interpretation of Be-star polarimetry data.

## 8 Conclusion

In summary, the model presented here appears to give reasonable results for optically thin cases, but we should only trust it for order-of-magnitude accuracy because it is based on so many simplifying assumptions. Even so, it may be useful for estimating trial values of the parameters as starting points for rigorous fitting with more elaborate models.

An interesting result from applying the model to observations of the eight program stars is that all of them may be fit with geometrically thin disks, with opening half-angles of ten degrees or less. This adds tentative support to the statistics in favor of thin disks as presented by Bjorkman & Cassinelli (1990) and later discussed at length by WBB. If most Be disks prove to be similarly flat, it will surely have important implications concerning their formation process.

It may seem discouraging that this model will never find optically thick solutions even if they physically exist. And with three adjustable parameters, there might be any number of apparently valid optically thin fits to a set of $`UBVRI`$ data points, rendering the entire exercise inconclusive. Nevertheless, there are good reasons for a more optimistic point of view. Due to the efforts of many investigators, as documented, for example, in the references in §1 of this paper, the range of physically allowable parameters has been narrowed significantly. And within even the most liberal of these constraints, experience with a quick, interactive trial-and-error system based on even the elementary physics presented here will show that it is surprisingly difficult to find multiple solutions with qualitatively different sets of parameters. I will be glad to share my IDL modeling program with interested users on request.

Thanks to Joe Cassinelli for critical reading and commentary on early drafts of this paper, and especially for suggesting a method to estimate the NLTE departure coefficients for the neutral hydrogen in a Be disk. Kenny Wood and Barbara Whitney also provided very helpful discussions, and Jon Bjorkman kindly gave me a version of the Monte Carlo polarization code. I especially thank the anonymous referee for pointing out many serious errors in the original manuscript and for patiently explaining the necessary corrections.

## Appendix A Estimating the NLTE Departure Coefficients

Fits to the polarization Balmer jump were difficult and in some cases impossible without NLTE corrections to the level populations of the first two excited states of H I. According to the combined Saha and Boltzmann equations, the maximum population of the first excited state normally occurs at a temperature of about 10,000 K and declines rapidly toward higher temperatures with increasing excitation and ionization. At temperatures closer to 20,000 K appropriate for Be disks, the LTE value of the absorption coefficient at the $`U`$-band is sometimes too small to match the large polarization Balmer jumps which are commonly observed. NLTE correction is applied only to the first two excited states because they dominate the opacity at optical wavelengths for the conditions of density and temperature of interest.

Since only averages over a line of sight are required for this very approximate polarization model, departure coefficients were simply estimated from the calculations of CNM. Their Figure 3 shows mean population parameters $`\overline{q}_n`$ for $`n=2`$ and $`n=3`$ defined by

$`\overline{q}_{nNLTE}`$ $``$ $`{\displaystyle \frac{_R_{}^{\mathrm{}}q_n(r,T_{})N_e^2𝑑r}{_R_{}^{\mathrm{}}N_e^2𝑑r}}`$ (A1)
$`=`$ $`{\displaystyle \frac{_R_{}^{\mathrm{}}N_n𝑑r}{_R_{}^{\mathrm{}}N_e^2𝑑r}},`$
based on the detailed NLTE analysis of a stellar wind immersed in the radiation field of a central star, with statistical balance between photoionization and radiative recombination. The departure coefficient for level n is then the ratio of the NLTE and LTE values of $`\overline{q}_n`$ .

The calculation of $`\overline{q}_{nLTE}`$ is done as follows:

$`{\displaystyle _R_{}^{\mathrm{}}}N_n(r)𝑑r`$ $`=`$ $`n^2N_{01}e^{X(n)X(1)}{\displaystyle _R_{}^{\mathrm{}}}\left({\displaystyle \frac{R_{}}{r}}\right)^{2\eta }𝑑r`$ (A2)
$`=`$ $`{\displaystyle \frac{n^2N_{01}R_{}}{2\eta 1}}e^{X(n)X(1)}`$
and

$`{\displaystyle _R_{}^{\mathrm{}}}N_e^2𝑑r`$ $`=`$ $`N_{0e}^2{\displaystyle _R_{}^{\mathrm{}}}\left({\displaystyle \frac{R_{}}{r}}\right)^{2\eta }𝑑r`$ (A3)
$`=`$ $`{\displaystyle \frac{N_{0e}^2R_{}}{2\eta 1}},`$
so that

$`\overline{q}_{nLTE}`$ $`=`$ $`{\displaystyle \frac{_R_{}^{\mathrm{}}N_n𝑑r}{_R_{}^{\mathrm{}}N_e^2𝑑r}}`$ (A4)
$`=`$ $`{\displaystyle \frac{N_{01}}{N_{0e}^2}}n^2e^{X(n)X(1)}`$
$`=`$ $`(2\pi m_ekT_e)^{1.5}h^3n^2e^{X(n)}.`$
The population parameters $`\overline{q}_{2NLTE}`$ and $`\overline{q}_{3NLTE}`$ may be estimated by extrapolation of power law fits to the disk temperatures (10,000–20,000 K) and mass-loss rates ($`10^8M_{\mathrm{}}yr^1)`$ characteristic of Be stars, based on Figure 3 of CNM:

$$\overline{q}_{2NLTE}=1.11\times 10^8T_e^{2.83},$$
(A5)
$$\overline{q}_{3NLTE}=4.59\times 10^{13}T_e^{2.02}.$$
(A6)
The approximate departure coefficients are then $`b_2=\overline{q}_{2NLTE}/\overline{q}_{2LTE}`$ and $`b_3=\overline{q}_{3NLTE}/\overline{q}_{3LTE}`$, so that the corrected level populations are roughly $`N_{2NLTE}=b2\times N_{2LTE}`$ and $`N_{3NLTE}=b3\times N_{3LTE}`$. These correction factors are applied to the appropriate terms in the summation inside the parentheses in equation (5). The corrected form of $`\kappa (\lambda )`$ is used only in calculating the absorption optical depth and not in calculating the emission coefficient, since recombination and free-free emission are LTE processes.


format: text

text:
# Quantum Communication Complexity (a survey)

## 1 Introduction

It is well known that the use of quantum information allows for tasks that would be provably impossible in a classical world, such as the transmission of unconditionally confidential information between parties that share only a short secret key . Apart from this *quantum cryptography*, are there advantages to be gained in setting up an infrastructure that would facilitate the transmission of quantum information? In particular, are there advantages to be gained in terms of communication *efficiency*? A different but related question concerns quantum entanglement: can entangled parties make better use of a classical communication channel than their non-entangled counterparts? Better still: can entangled parties benefit from their entanglement if they are not allowed any form of direct communication?

There are good reasons to believe at first that the answer to all the above questions is negative. In particular, Holevo’s theorem  states that no more than $`n`$ bits of expected classical information can be communicated between unentangled parties by the transmission of $`n`$ quantum bits—henceforth called *qubits*—regardless of the coding scheme that could be used. If the communicating parties share prior entanglement, twice as much classical information can be transmitted , but no more. This applies even if the communication is not restricted to be one-way . It is thus reasonable to expect that no significant savings in communication can be achieved by the transmission of qubits, and possibly no savings at all if the communicating parties do not share prior entanglement. As for the last question, it is well known that entanglement alone cannot be used to signal information—otherwise faster-than-light communication would be possible and causality would be violated—and thus it would seem that entanglement is useless if it is not supplemented by direct forms of communication. Here we survey striking results to the effect that all the intuition in this paragraph is wrong.

After a review of classical communication complexity in Section 2, we consider in Section 3 the situation in which quantum communication is allowed. In Section 4, we revert to classical communication but allow unlimited prior entanglement between the communicating parties. Section 5 investigates in more detail the power of prior entanglement when no direct communication is allowed to take place, which we call spooky communication complexity. In Section 6, we determine how expensive it is to simulate the effect of entanglement in a purely classical world. Finally, we conclude with open problems in Section 7. Although we do not cover the important topic of lower bounds for quantum communication complexity, we encourage the reader to consult  for early results and  for powerful new techniques.

## 2 Classical Communication Complexity

Let Alice and Bob be two distant parties who wish to collaborate on a common task that depends on distributed inputs. More precisely, let $`X`$, $`Y`$ and $`Z`$ be sets and consider a function $`f:X\times YZ`$. Assume Alice and Bob are given some $`xX`$ and $`yY`$, respectively, and their goal is to compute $`z=f(x,y)`$. Sometimes, we add a *promise* $`P(x,y)`$ for some Boolean function $`P`$, in which case Alice and Bob are required to compute the correct answer $`f(x,y)`$ only when $`P(x,y)`$ holds. Whether or not there is a promise, the obvious recipe is for Alice to communicate $`x`$ to Bob, which allows him to compute $`z`$. Once obtained, Bob can then communicate $`z`$ back to Alice if both parties need to know the answer. If we are concerned with the amount of communication required to achieve this task—paying no attention to the computing effort involved in the process—could there be more efficient solutions for some functions $`f`$ ? For *all* functions?

The answer is obviously positive for the first question. For example, if $`X=Y=\{0,1\}^n`$ for some integer $`n`$, $`Z=\{0,1\}`$ and $`f(x,y)`$ is defined to be 0 if and only if $`x`$ and $`y`$ have the same Hamming weight (the same number of 1s), it suffices for Alice to communicate the Hamming weight of $`x`$ to Bob for him to verify the condition. Thus, about $`\mathrm{lg}n`$ bits 111 The symbol “$`\mathrm{lg}`$” is used to denote the base-two logarithm. of communication are sufficient for this task, which is much more economical than if Alice had transmitted all $`n`$ bits of her input to Bob. The answer to the second question, however, is negative: There are functions for which the obvious solution *is* optimal. For instance, $`n`$ bits of communication are necessary and sufficient in the worst case for Bob to decide whether or not Alice’s input is the same as his. This unsurprising statement is not easy to prove, but a host of techniques have been developed to handle that kind of questions. See  for a survey.

A more interesting scenario takes place when we do not insist on the correct answer to be obtained with certainty. If we accept a small error probability, we can do significantly better on the above-mentioned equality-testing problem. Let $`\epsilon >0`$ be the tolerated error probability and let $`p`$ be the smallest prime number larger than $`n/\epsilon `$. Let $`𝔽`$ be the finite field with $`p`$ elements. Upon receiving their inputs $`x`$ and $`y`$, Alice forms polynomial $`P(z)=x_1+x_2z+x_3z^2+\mathrm{}+x_nz^{n1}`$ over $`𝔽`$ and Bob forms $`Q(z)=y_1+y_2z+y_3z^2+\mathrm{}+y_nz^{n1}`$. Then, Alice chooses a random element $`w𝔽`$. She computes $`v=P(w)`$ and transmits both $`w`$ and $`v`$ to Bob, who computes $`Q(w)`$ and compares the answer with $`v`$. If $`Q(w)v`$, it has been established that $`xy`$. Otherwise, Bob can claim with confidence that $`x=y`$ because two distinct polynomials of degree smaller than $`n`$ cannot agree on more than $`n`$ distinct points and therefore the proportion of points in $`𝔽`$ on which $`P(z)`$ and $`Q(z)`$ agree must be less than $`n/\mathrm{\#}𝔽=n/p<\epsilon `$. Note that $`p2n/\epsilon `$ since there is always a prime number between any number and its double, and hence each of $`w`$ and $`v`$ can be written with no more than $`2+\mathrm{lg}n+\mathrm{lg}\frac{1}{\epsilon }`$ bits. The communication complexity of this protocol is therefore at most twice this many bits, which is much less than $`n`$ for any fixed error probability $`\epsilon `$ when $`n`$ is large enough.

In the classical model of communication complexity, it is often allowed for Alice and Bob to *share random variables* even though one may argue that this does not make much sense from a mathematical point of view. In this scenario, we assume that Alice draws a random bit string (or integer) according to some specific distribution—or sometimes even a random real number—and she tells Bob the outcome of this draw in an *initialization phase*. This communication is not accounted for in the complexity of the protocol because it takes place *before* Alice and Bob are given their respective inputs. When correctness of the protocol is analysed for a given input, probabilities are taken over the possible choices of that random variable, as if it had been chosen *after* the inputs were determined 222 Note that drawing shared random bits once Alice and Bob are separated makes perfect sense in a quantum world if they share entanglement: they simply have to measure corresponding qubits from $`|\mathrm{\Phi }^+=\frac{1}{\sqrt{2}}|00+\frac{1}{\sqrt{2}}|11`$ pairs in the computational basis.. In this model, the equality-testing problem can be solved with error probability $`\epsilon `$ with only $`m=\mathrm{lg}1/\epsilon `$ bits of communication, regardless of the value of $`n`$. In the initialization phase, Alice and Bob share $`m`$ random bit strings $`a_1`$, $`a_2`$, …, $`a_m`$ , each of length $`n`$. Once they receive their inputs $`x`$ and $`y`$, Alice computes $`b_i=xa_i`$ for each $`i`$, where $`xa`$ is the *inner product*333 To compute the inner product between two bit strings of equal length, line them up one under the other and count the number of positions in which they both have a 1. If this number is even, the inner product is 0; otherwise it is 1. Mathematically, it is the exclusive or (sum modulo 2) of the bitwise and of the two strings. between bit strings $`x`$ and $`a`$. Alice transmits $`b_1`$, $`b_2`$, …, $`b_m`$ to Bob, who verifies whether or not $`b_i=ya_i`$ for each $`i`$. If not, it has been established that $`xy`$. Otherwise, Bob can claim with confidence that $`x=y`$ because the probability of error of this strategy is $`2^m\epsilon `$ since it is $`^1/_2`$ independently for each $`i`$.

## 3 Quantum Communication Complexity

The topic of classical communication complexity was introduced and first studied by Andrew Yao in 1979 . Almost 15 years elapsed before the same pioneer thought of asking how the situation might change if Alice and Bob were allowed to exchange quantum rather than classical bits . It seems at first that no savings in communication are to be expected at all because of Holevo’s theorem , which states that no more than $`n`$ bits of expected classical information can be communicated between unentangled parties by the transmission of $`n`$ qubits. (It was implicit in Yao’s original model that Alice and Bob were not allowed to share prior entanglement in the initialization phase.)

The first hint that quantum communication could be more efficient than classical communication was given in August 1997 by Richard Cleve, Wim van Dam, Michael Nielsen and Alain Tapp  in a probabilistic setting 444 For the sake of historical completeness, it is easy to modify a protocol given three months earlier by Buhrman, Cleve and van Dam  (original quant-ph version) to achieve a similar goal, and indeed this is done in the final version of that paper, which is to appear in SIAM Journal on Computing.. Alice and Bob are given two-bits vectors $`x_1x_2`$ and $`y_1y_2`$, respectively. They must both decide if $`x_1y_1+x_2y_2`$ is even or odd, and they are restricted to two bits of communication. Shared random variables are allowed. It is proven in  that no classical protocol for this task can give the correct answer with a probability better than $`^7/_9`$. Yet, if two quantum bits of communication are allowed, instead of two classical bits, the correct answer can be obtained with an improved probability of $`^4/_5`$.

A more convincing case for the superiority of quantum communication came the following year when Harry Buhrman, Richard Cleve and Avi Wigderson  proved that quantum communication can be *exponentially* better than classical communication in the error-free model, provided the inputs respect a given promise, and almost quadratically better in the bounded-error promise-free model. Subsequently, Ran Raz proved that an exponential advantage exists to quantum communication even in the bounded-error promise-problem model .

The first exponential separation  was inspired by the famous Deutsch–Jozsa problem , which was used in 1992 to show for the first time that quantum computers could be exponentially faster than classical computers in an oracle-based  error-free setting. More specifically, Buhrman, Cleve and Wigderson defined the following scenario, where $`\mathrm{\Delta }(x,y)`$ denotes the *Hamming distance* between bit strings $`x`$ and $`y`$, which is the number of bit positions on which they differ. Let $`k`$ be an integer, $`n=2^k`$, $`X=Y=\{0,1\}^n`$ and $`Z=\{0,1\}`$. Function $`f:X\times YZ`$ is the equality function: $`f(x,y)=1`$ if and only if $`x=y`$. We have seen already that this communication complexity problem requires $`n`$ bits of classical communication if errors are not tolerated. Now, we introduce the promise $`P(x,y)`$, which is defined to be true if and only if $`\mathrm{\Delta }(x,y)\{0,n/2\}`$. In other words, $`P(x,y)`$ holds if and only if either $`x=y`$ or $`x`$ and $`y`$ differ on exactly half their positions. It is proven in  that the error-free equality-testing problem requires at least $`cn`$ classical bits of communication, for some real positive constant $`c`$ and all sufficiently large $`n`$, even when the correct answer is required only when the promise holds. (The hard part of that proof is taken from .) Even though quantum communication cannot be significantly more efficient than classical communication for the straight equality-testing problem , it is shown in  that it can be solved with certainty using as few as $`k`$ quantum bits of communication whenever the promise holds, which is exponentially better than the $`cn`$ bits that would be required in a classical scenario. A quantum protocol for this problem is easily derived from the first example of “spooky communication” given in Section 5.

This exponential “superiority” of quantum over classical communication is not entirely convincing because it vanishes as soon as we tolerate an arbitrarily small probability of error. Indeed, we have seen that the equality-testing problem can be solved with a *constant* number of bits of classical communication, for any fixed error probability, when shared random variables are allowed 555 Even if we do not allow shared random variables, the problem can be solved with $`2k+c`$ bits of classical communication, where $`k=\mathrm{lg}n`$ and $`c`$ is a constant that depends only on the error probability.. The other problem featured in  is more interesting, even though the quantum superiority is merely almost quadratic, because it applies in the more realistic bounded-error model. Consider the following scenario. Alice and Bob are very busy and they would like to find a time when they are simultaneously free for lunch. They each have an engagement calendar, which we think of as an $`n`$–bit string $`x`$ (resp $`y`$), where $`x_i=1`$ (resp. $`y_i=1`$) means that Alice (resp. Bob) is free for lunch on day $`i`$. Mathematically, they want to find an index $`i`$ such that $`x_i=y_i=1`$ or establish that such an index does not exist. Balasubramanian Kalyanasundaram and Georg Schnitger  proved in 1987 that this task requires at least $`cn`$ classical bits of expected communication in the worst case, for some real positive constant $`c`$ and all sufficiently large $`n`$, even when the answer is only required to be correct with probability at least $`^2/_3`$. Intuitively, this means that lunch cannot be scheduled short of exchanging a constant fraction of the appointment calendar. In sharp contrast, it is shown in  that this problem can be solved with the exchange of at most $`d\sqrt{n}\mathrm{lg}n`$ quantum bits for some constant $`d`$ and all sufficiently large $`n`$. This is accomplished by implementing a distributed version of Grover’s quantum search algorithm  in which we search for a $`1`$ in the bitwise and of $`x`$ and $`y`$. A $`\mathrm{lg}n`$–qubit quantum register is shuttled back and forth between Alice and Bob for each of the approximately $`\sqrt{n}`$ iterations of Grover’s algorithm.

## 4 Substituting Entanglement for Communication

A slightly different model was introduced by Richard Cleve and Harry Buhrman . Assume Alice and Bob are restricted to communicating classical information. Are there tasks for which they could save on the required amount of communication if they share prior entanglement? Again, it is tempting to think that this is not possible because entanglement cannot be used to increase the capacity of a classical channel: Alice cannot communicate more than $`n`$ expected bits of classical information to Bob if less than $`n`$ bits are actually transmitted between them—even if they are allowed two-way communication and unlimited use of entanglement. And again, this intuition is wrong.

In their original paper , Cleve and Buhrman were able to show that entanglement can be used to save one bit of classical communication, but only in a three-party scenario. Still, this was the very first example of a distributed task that could be solved more efficiently (in terms of communication) in our quantum world than would be possible in a sad classical world, because it predates  by four months. Subsequently, Buhrman, Cleve and van Dam  found a *two-party* distributed problem that can be solved with a probability of success exceeding $`85\%`$ if prior shared entanglement is available, whereas the probability of success in a classical world could not exceed $`75\%`$ with the same amount of communication, even if shared random variables are allowed.

The first problem for which communication complexity could be reduced by more than a constant additive amount was also discovered in this shared-entanglement scenario, rather than in Yao’s original qubit-transmission scenario described in the previous section: Harry Buhrman, Wim van Dam, Peter Høyer and Alain Tapp  gave a $`k`$–party distributed task that requires roughly $`k\mathrm{lg}k`$ bits of communication in a classical world, yet it can be carried out with exactly $`k`$ bits of classical communication if the parties are allowed to share prior entanglement.

The exponential and almost-quadratic improvements mentioned in the previous section  apply just as well in the shared-entanglement scenario. This is obvious since the effect of any protocol that requires the communication of $`\mathrm{}`$ quantum bits can be achieved by the transmission of $`2\mathrm{}`$ classical bits—through *quantum teleportation* —provided $`\mathrm{}`$ bits of shared entanglement are available.

There is yet another natural communication complexity scenario, in which the parties are allowed to share prior entanglement *and* to communicate quantum bits. For the sake of brevity, we shall not elaborate on this approach here.

## 5 Spooky Communication Complexity

An even more intriguing question is to determine if entanglement can be used *instead of* communication. Are there tasks that would be impossible to achieve in a classical world if Alice and Bob were not allowed to communicate, yet those tasks can be performed without *any* form of communication provided the participants share prior entanglement? In the words of Alain Tapp, this would provide a form of *pseudo telepathy* because it would give the *illusion* of communication between Alice and Bob when in fact no such communication takes place. And indeed there would be no communication because entanglement cannot be used to signal information: nothing Alice can do locally on her quantum system can cause a measurable change in Bob’s, no matter how they are entangled.

A moment’s thought suffices to realize that pseudo telepathy is possible if we are content with probabilistic tasks. Define the *EPR task* as follows. Once separated, Alice and Bob are given each a real number $`x`$ and $`y`$, respectively, between 0 and $`\pi `$. They are to produce each a single bit: $`a`$ for Alice and $`b`$ for Bob. Alice’s output must be equally likely to be 0 or 1, and so must Bob’s output, but the required correlation is that $`a=b`$ with probability $`\mathrm{cos}^2(xy)`$. It is precisely the essence of Bell’s theorem  that such correlations cannot be established in a classical world if communication between Alice and Bob is not allowed, even if the inputs are restricted to binary choices $`x\{0,\pi /6\}`$ and $`y\{0,5\pi /6\}`$. Yet, it is easy for participants who share a $`|\mathrm{\Phi }^+=\frac{1}{\sqrt{2}}|00+\frac{1}{\sqrt{2}}|11`$ state to realize this task. If we think of this state as a pair of entangled polarized photons, it suffices for Alice and Bob to measure their photons at polarization angles $`x`$ and $`y`$, respectively, and the outcomes of the measurements provide the required outputs $`a`$ and $`b`$.

But is pseudo telepathy possible when there is a deterministic criterion to decide if the goal has been achieved and when errors are not tolerated? This brings us to our last form of communication complexity, which we call *spooky communication complexity*. As usual, let $`X`$, $`Y`$ and $`Z`$ be sets and consider a function $`f:X\times YZ`$ such that it is not possible to compute the value of $`f(x,y)`$ with certainty from knowledge of either $`x`$ or $`y`$ alone. It follows that if Alice and Bob are given $`xX`$ and $`yY`$, respectively, they cannot compute $`f(x,y)`$ without communication. Can such a function $`f`$ exist so that Alice and Bob—or at least one of them—could compute $`f(x,y)`$ nevertheless provided the participants share prior entanglement? Of course not, since this would allow for faster-than-light communication! Thus, we have to define spooky communication complexity in a more subtle way, through a *relation* rather than a function.

Let $`X`$, $`Y`$, $`A`$ and $`B`$ be sets and consider a relation $`RX\times Y\times A\times B`$. In an *initialization phase*, Alice and Bob are allowed to discuss strategy and share random variables. They are also allowed to share entanglement. After Alice and Bob are physically separated, they are given $`xX`$ and $`yY`$, respectively. Without being allowed any forms of communication, their goal is to produce $`aA`$ and $`bB`$, respectively, such that $`(x,y,a,b)R`$. We say that *spooky communication*, or *pseudo telepathy*, takes place if this task could not be fulfilled with certainty in a classical world, whereas it can provided Alice and Bob share prior entanglement. The amount of spooky communication *complexity* is measured in the number of bits of entanglement that are required to succeed in the worst case. The *spooky advantage* is defined as the function that relates the spooky complexity to the number of classical bits of communication that would be needed in the worst case to succeed in the classical setting.

The first example of spooky communication was provided by Gilles Brassard, Richard Cleve and Alain Tapp  as yet another variation on the Deutsch–Jozsa problem . Let $`k`$ be an integer, $`n=2^k`$, $`X=Y=\{0,1\}^n`$ and $`A=B=\{0,1\}^k`$. The *Deutsch–Jozsa relation* $`R`$ is defined as follows, where $`\mathrm{\Delta }(x,y)`$ denotes again the Hamming distance between $`x`$ and $`y`$.

$$(x,y,a,b)R\{\begin{array}{c}x=y\text{ and }a=b,\text{ or}\hfill \\ \mathrm{\Delta }(x,y)=n/2\text{ and }ab,\text{ or}\hfill \\ \mathrm{\Delta }(x,y)\{0,n/2\}\hfill \end{array}$$

In other words, Alice and Bob are promised that either their inputs are the same, or that they differ on exactly half the bits. They must produce identical outputs if and only if their inputs are the same. But if the promise is not fulfilled, there are no conditions on what Alice and Bob produce. The challenge comes from the fact that the outputs $`a`$ and $`b`$ must be exponentially shorter than the inputs $`x`$ and $`y`$.

It is not immediate that the Deutsch–Jozsa relation requires communication to be established in the classical setting. After all, it *can* be established when $`n=2`$ (easily) and $`n=4`$ (think about it!). But it is proven in  that there exists a positive constant $`c`$ such that the Deutsch–Jozsa relation cannot be established classically with fewer than $`cn`$ bits of communication provided $`n`$ is sufficiently large, based on the similar lower bound from  that we had mentioned in Section 3. On the other hand, we show below that the Deutsch–Jozsa relation *can* be established in the spooky setting with as few as $`k`$ bits of entanglement. It follows that the spooky advantage of this problem is exponential because $`n`$ is exponential in $`k`$.

To establish the Deutsch–Jozsa relation, Alice creates a $`2k`$-qubit register in state

$$\underset{z\{0,1\}^k}{}\mathrm{\hspace{0.17em}2}^{k/2}|z,z,$$

which is the same as $`k`$ pairs in state $`|\mathrm{\Phi }^+`$ up to ordering of the qubits. She keeps the first $`k`$ qubits of that register and gives the other $`k`$ qubits to Bob. After Alice and Bob are separated, they receive their respective inputs $`x`$ and $`y`$. To each integer $`i`$, $`1in`$, associate the bit string $`z_i\{0,1\}^k`$ that represents number $`i1`$ in binary. Now, Alice applies to her register the unitary transformation that maps $`|z_i`$ to $`(1)^{x_i}|z_i`$ for each $`i`$, and Bob does the same to his register, but with $`y_i`$ instead of $`x_i`$. This produces joint state

$$\underset{i=1}{\overset{n}{}}\mathrm{\hspace{0.17em}2}^{k/2}(1)^{x_i}(1)^{y_i}|z_i,z_i=\underset{i=1}{\overset{n}{}}\mathrm{\hspace{0.17em}2}^{k/2}(1)^{x_iy_i}|z_i,z_i.$$

Next, Alice applies the Walsh–Hadamard transform, which sends $`|0`$ to $`\frac{1}{\sqrt{2}}|0+\frac{1}{\sqrt{2}}|1`$ and $`|1`$ to $`\frac{1}{\sqrt{2}}|0\frac{1}{\sqrt{2}}|1`$, to each of the $`k`$ qubits of her register, and Bob does the same on his register. Finally, Alice and Bob measure their registers in the computational basis. The resulting classical strings, $`a`$ and $`b`$, are their final output. It is proven in  that this process accomplishes the required job.

## 6 Classical Simulation of Entanglement

Once we have established that pseudo telepathy is possible, the next natural question is to determine how much classical communication is necessary and sufficient to simulate the effect of $`k`$ bits of entanglement. It follows from the previous section (and Bell’s theorem  for small values of $`k`$) that at least $`c2^k`$ bits are required, for some constant $`c>0`$ and all $`k1`$. But are these many bits of classical communication *sufficient* to simulate *everything* that can be accomplished with $`k`$ bits of entanglement?

In fact, can the effect of entanglement be simulated *at all* with a finite amount of classical communication? As the simplest possible example, can the EPR task, as defined in Section 5, be simulated by classical communication? In particular, we must have $`a=b`$ if $`x=y`$ and $`ab`$ if $`|xy|=\pi /2`$. Surely, it is not possible for Alice to communicate her input $`x`$ to Bob, for this would require an infinite amount of communication. Yet, it is shown in  that *four* bits of classical communication are sufficient in the worst case for an exact simulation of the EPR task, provided Alice and Bob are allowed to share a continuous real random variable in the initialization phase—admittedly an unreasonable proposition. The essence of the idea is best explained if we further restrict the inputs $`x`$ and $`y`$ to be between $`0`$ and $`1`$, rather than between $`0`$ and $`\pi `$. In this case, *a single bit* of classical communication suffices to simulate the EPR task exactly. This restriction is somewhat bizarre since it translates to requiring the angles to be between $`0`$ and approximately $`57.3`$ degrees. Without this restriction, a rather painful piecewise construction has to be implemented, as explained in , and we need four bits of classical communication to take care of the various possible cases.

In the initialization phase, Alice and Bob share a boolean variable $`c`$, which is equally likely to be 0 or 1, and a continuous real variable $`r`$ chosen uniformly in the interval $`(0,1)`$. After they are separated, they receive their angles $`x`$ and $`y`$, respectively. Alice outputs $`a=c`$, a random bit as required. Then, she tells Bob if $`a<x`$ with a single bit of classical communication. This allows Bob to determine whether or not $`r`$ lies in between $`x`$ and $`y`$. In case it does not, Bob outputs the same bit $`b=c`$ as Alice. Note in particular that if $`x=y`$, then we get $`a=b`$ with certainty, as required. On the other hand, if $`r`$ does lie between $`x`$ and $`y`$, then Bob outputs $`b=1c`$, a bit complementary to Alice’s, with probability $`\mathrm{sin}(2|yr|)`$, otherwise he outputs $`b=c`$ just like Alice.

The probability that $`a=b`$ is calculated as an integral over the various possibilities for $`r`$, as if it had been chosen after $`x`$ and $`y`$ are fixed. For simplicity, assume that $`xy`$. The probability that $`a=b`$ is 1 if $`0rx`$ or $`yr1`$ since, in that case, $`r`$ does not lie between $`x`$ and $`y`$. Otherwise, if $`x<r<y`$, the probability that $`a=b`$ is $`1\mathrm{sin}(2(yr))`$. Therefore, the global probability that $`a=b`$ is

$$_{r=0}^x1\text{d}r+_{r=x}^y[1\mathrm{sin}(2(yr))]\text{d}r+_{r=y}^11\text{d}r$$

$$=\frac{1}{2}+\frac{1}{2}\mathrm{cos}(2(yx))=\mathrm{cos}^2(xy),$$

as required. It is tempting to “improve” on this approach and make it work for all angles between $`0`$ and $`\pi `$, simply with an appropriate change in the probability function $`\mathrm{sin}(2|yr|)`$ that determines whether or not Bob will output the same bit as Alice when $`r`$ lies between $`x`$ and $`y`$. Unfortunately, any such attempt will result in “probabilities” that are either negative or greater than 1 !

It is shown in  how to simulate an arbitrary von Neumann measurement with only *eight* classical bits of communication in the worst case, but it is left as an open question to determine whether or not the effect of an arbitrary positive-operator-valued measurement (povm) can be simulated with a bounded amount of classical communication in the worst case.

A different approach to the classical simulation of entanglement was taken independently by Michael Steiner , who showed that the EPR relation can be simulated exactly with significantly fewer *expected* bits of classical communication, provided we accept that there be no upper limit on the required amount of communication in the case of bad luck. Steiner’s technique was subsequently refined by Nicolas Cerf, Nicolas Gisin and Serge Massar , who showed that as few as 1.19 expected bits of classical communication suffice to simulate exactly an arbitrary von Neumann measurement. Even an arbitrary povm can be simulated by this technique, at the expected cost of 6.38 bits of classical communication.

Building on , Serge Massar, Dave Bacon, Nicolas Cerf and Richard Cleve  discovered that the exact classical simulation of quantum entanglement can be achieved without any need for shared random variables, provided we are satisfied with an *expected* bounded amount of classical communication. In particular, they show how to simulate the effect of an arbitrary povm on one bit of entanglement with less than 20 bits of expected classical communication. Conversely, they also show that the exact simulation of quantum entanglement with a worst-case bounded amount of classical communication (as in the scenario of  described earlier in this section) is *not* possible without an infinite amount of shared randomness.

Finally, the question asked at the beginning of this section is almost resolved in . It is still unknown if there exists a constant $`c`$ such that $`c2^k`$ bits of classical communication are sufficient to simulate exactly the effect of $`k`$ bits of entanglement for all values of $`k`$. However, it is shown in  that as few as $`(3k+6)2^k`$ expected bits of classical communication suffice to simulate the outcome of any povm that Alice and Bob could perform on their respective shares of $`k`$ bits of entanglement. This simulation protocol does not require Alice and Bob to share random variables in the initialization phase. No similar results are known for worst-case bounded communication even if we allow the sharing of continuous random variables.

## 7 Conclusions and Open Problems

We have seen a variety of scenarios according to which quantum mechanics allows for a significant improvement in the efficiency of communication, compared to what would be possible in a classical world. This is surprising because the transmission of $`n`$ quantum bits cannot serve to communicate more than $`n`$ classical bits of information, and because quantum entanglement on its own cannot be used to communicate at all. Perhaps the most interesting aspect of quantum communication complexity is that the advantage provided by quantum mechanics has been established rigourously. This is in sharp contrast with the field of quantum *computing*, in which it is merely *believed* that quantum mechanics allows for an exponential speedup in some computational tasks, such as the factorization of large numbers . Indeed, it has not yet been ruled out that there might exist an efficient factorization algorithm for the classical computer.

Several interesting questions are still open. The exponential advantage of quantum communication over classical communication has been established only in the case of promise problems, in both the error-free  and bounded-error  scenarios. Could there be a (total) function $`f:X\times YZ`$, where $`X=Y=\{0,1\}^n`$, for which the distributed computation of $`f`$ would be exponentially more efficient with quantum communication compared to classical communication?

We have seen at the end of Section 4 that the amount of classical communication required for the accomplishment of a distributed task in the presence of unlimited entanglement cannot be more than twice the amount of quantum communication that would suffice for the same task, because quantum teleportation can be used to transmit quantum bits through a classical channel. How about the other direction? Could there be a task that can be accomplished with a small amount of classical communication in the presence of unlimited entanglement, but that would require a much larger amount of quantum communication if prior entanglement were not available?

We have seen in Section 5 that the Deutsch–Jozsa relation can be established classically without communication when $`n=2`$ or $`n=4`$, but not when $`n`$ is arbitrarily large. But how large must “large” be? In particular, can it be established for $`n=8`$? It is interesting to note that the Deutsch–Jozsa relation becomes easier and easier to *fake* when $`n`$ becomes larger. Indeed, if Alice and Bob share $`k`$ random variables $`t_1`$, $`t_2`$, …, $`t_k\{0,1\}^n`$ in the initialization phase, and if they output $`a_i=xt_i`$, and $`b_i=yt_i`$, respectively, their probability of being caught with $`a=b`$ if in fact $`\mathrm{\Delta }(x,y)=n/2`$ goes down as $`2^k`$. A nice open question is to determine the task on $`n`$ input and $`k`$ output bits that can be handled with certainty given sufficient entanglement and no communication, but for which the probability of success would be as small as possible in a classical world.

Finally, several open questions are given in Section 6 concerning the classical simulation of quantum entanglement. Is it possible to achieve the EPR task with fewer than four bits of classical communication in the worst case? Is it possible to simulate an arbitrary povm with a *worst-case* bounded amount of classical communication? How much classical communication is sufficient in the worst case to simulate the effect of $`k`$ bits of entanglement? In the expected case? We have seen how classical communication can be used to simulate entanglement for tasks that did not involve classical communication in the quantum setting. How about the classical simulation of tasks that use not only quantum entanglement but also classical (or perhaps quantum) communication?

## Acknowledgements

I am grateful to Richard Cleve for introducing me to the fascinating field of quantum communication complexity and to Alain Tapp for sharing with me some of his best thoughts on the topic. In addition to discussions with Richard and Alain, this paper has benefited from insightful comments from Harry Buhrman and Ronald de Wolf.


text:
# Scalars convected by a 2D incompressible flow

## 1 Abstract

We provide a test for numerical simulations, for several two dimensional incompressible flows, that appear to develop sharp fronts. We show that in order to have a front the velocity has to have uncontrolled velocity growth.

## 2 Introduction

The aim of this paper is to study the possible formation of sharp fronts in finite time for a scalar convected by a two dimensional divergence-free velocity field, with $`x=(x_1,x_2)R^2`$ or $`R^2/Z^2`$, and $`t[0,T)`$ with $`T\mathrm{}`$. The scalar function $`\theta (x,t)`$ and the velocity field $`u(x,t)=(u_1(x,t),u_2(x,t))R^2`$ satisfy the following set of equations

$`\left(_t+u\right)\theta =0`$ (1)
$`^{}\psi =u,`$
where $`_x^{}f=(\frac{f}{x_2},\frac{f}{x_1})`$ for scalar functions f. The function $`\psi `$ is the stream function.

There are many physical examples where the solutions satisfy the equations above, with an extra equation or operator that relates $`\theta `$ with the velocity field. Examples include; Passive scalars, Unsteady Prandtl equations, 2D incompressible Euler equations, Boussinesq, 2D Ideal Magnetohydrodynamics and the Quasi-geostrophic equation.

In the literature on numerical simulations for the 2D Ideal Magneto-hydrodynamics (MHD) a standard candidate for a current sheet formation (see Fig. 1) is when the level sets of the magnetic stream function ( represented in (1) by $`\theta `$) contain a hyperbolic saddle (an X-point configuration). The front is formed when the hyperbolic saddle closes, and becomes two Y-points configuration joined by a current sheet. (See Parker , Priest-Titov-Rickard , Friedel-Grauer-Marliani  and Cordoba-Marliani .)

The same configuration was observed in numerical simulations for the Quasi-geostrophic equation (QG). In this case the geometry of the level sets of the temperature has a hyperbolic structure (See Constantin-Majda-Tabak , Okhitani-Yamada , Cordoba  and Constantin-Nie-Schorghofer ). The QG literature discusses X-points, but not Y-points. In the case of Boussinesq there is no mention, on any numerical simulation study, that a possible singularity is due to the closing of a hyperbolic saddle. In the work of Pumir-Siggia  there has been observed evidence for a formation of a front in finite time, across which $`\theta `$ varies dramatically, on a cap of a symmetric rising bubble. E-Shu  performed numerical simulations with the same initial data as in , which suggest that the thickness of the bubble decreases only exponentially.

The equations for MHD, QG and Boussinesq are as follows

MHD:

$`(_t+u)\theta `$ $`=`$ $`0`$
$`(_t+u)\omega `$ $`=`$ $`^{}\theta (\mathrm{\Delta }\theta )`$
$`u`$ $`=`$ $`^{}\psi `$
and initial conditions $`\theta (x,0)=\theta _0`$ and $`u(x,0)=u_0`$. The $`^{}\theta `$ represents the magnetic field, $`\mathrm{\Delta }\theta `$ represents the current density and $`\omega =\mathrm{\Delta }\psi `$ the vorticity.

QG:

$`(_t+u)\theta =0`$
$$u=^{}\psi where\theta =(\mathrm{})^{\frac{1}{2}}\psi $$

and initial condition $`\theta (x,0)=\theta _0`$. The temperature is represented by $`\theta `$.

Boussinesq:

$`\left(_t+u_x\right)\theta `$ $`=`$ $`0`$
$`\left(_t+u_x\right)\omega `$ $`=`$ $`\theta _{x_1}`$
$`u`$ $`=`$ $`^{}\psi `$
Again, $`\theta `$ and u are specified at time t=0.

## 3 Criterion

A singularity can be formed by collision of two particle trajectories. A trajectory X(q,t) is obtain by solving the following ordinary differential equation

$`{\displaystyle \frac{dX(q,t)}{dt}}`$ $`=`$ $`u(X(q,t),t)`$
$`X(q,0)`$ $`=`$ $`q`$
Therefore,

$$(X(q,t)X(p,t))_t|X(q,t)X(p,t)||u|_L^{\mathrm{}}$$

$$|X(q,t)X(p,t)||X(q,0)X(p,0)|e^{_0^t|u|_L^{\mathrm{}}𝑑s}$$

By this trivial argument; in order to have a collision the quantity $`_0^t|u|_L^{\mathrm{}}𝑑s`$ has to diverge.

A classic criterion for formation of singularities in fluid flows is the theorem of Beale-Kato-Majda (BKM); (see ), which improves the estimate described above, and deals with arbitrary singularities, not just collisions. Analogues of the BKM theorem for the above 2-dimensional equations include the following results

For MHD,a singularity cannot develop at a finite time T, unless we have

$`{\displaystyle _0^T}sup_x|\omega (x,t)|+sup_x|\mathrm{}_x\theta (x,t)|dt=\mathrm{},`$
where $`\omega `$ denotes the vorticity.(See Caflisch-Klapper-Steele .)

For QG, a singularity cannot develop at a finite time T, unless we have

$`{\displaystyle _0^T}sup_x|_x\theta (x,t)|𝑑t=\mathrm{},`$
(See Constantin-Majda-Tabak ).

For Boussinesq, if a singularity develops at a finite time T then

$`{\displaystyle _0^T}sup_x|\omega (x,t)|𝑑t=\mathrm{}and{\displaystyle _0^T}{\displaystyle _0^t}sup_x|_x\theta (x,s)|𝑑s𝑑t=\mathrm{}.`$
(See E-Shu .)

See also Constantin-Majda-Tabak  and Constantin-Fefferman-Majda  for other conditions involving direction fields, that rule out formation of singularities in fluids.

In the case of 2D Euler, a singularity cannot develop at a finite time. From the BKM viewpoint this follows from the fact that $`\omega `$ is advected by the fluid, and therefore $`sup_x|\omega (x,t)|`$ is independent of t. (See BKM .)

Instead of looking at particle trajectories we look at level curves. Because the scalar function $`\theta `$ is convected by the flow, that implies that the level curves are transported by the flow. A possible singular scenario is due to level curves approaching each other very fast which will lead to a fast growth of the gradient of the scalar function. In this paper we present a variant of the BKM criterion for sharp front formation. We provide a test for numerical simulations that appear to develop sharp fronts. The BKM Theorem shows that the vorticity grows large if any singularity forms; our Theorem 1 shows that the velocity grows large if a sharp front forms.

The theorem we present in this paper was announced in .

## 4 Sharp Fronts

The scalar function $`\theta `$ is convected by the flow, therefore the level curves move with the flow. A sharp front forms when two of these level curves collapse on a single curve. We define two level curves to be two distinct time-dependent arcs $`\mathrm{\Gamma }_+(t)`$, $`\mathrm{\Gamma }_{}(t)`$ that move with the fluid and collapse at finite time into a single arc $`\mathrm{\Gamma }`$. More precisely, suppose the arcs are given by

$`\mathrm{\Gamma }_\pm =\{(x_1,x_2)R^2:x_2=f_\pm (x,t),x_1[a,b]\}for0t<T,`$ (2)
with

$`f_\pm C^1([a,b]\times [0,T))`$ (3)
and

$`f_{}(x_1,t)<f_+(x_1,t)forallx_1[a,b],t[0,T).`$ (4)
We call the length b-a of the interval \[a,b\] the length of the front. The assumption that $`\mathrm{\Gamma }_\pm (t)`$ move with the fluid means that

$`u_2(x_1,x_2,t)={\displaystyle \frac{f_\pm }{x_1}}(x_1,t)u_1(x_1,x_2,t)+{\displaystyle \frac{f_\pm }{t}}(x_1,t)atx_2=f_\pm (x_1,t).`$ (5)
This holds in particular for level curves of scalar functions g(x,t) that satisfy $`\left(_t+u_x\right)g=0`$. The collapse of $`\mathrm{\Gamma }_\pm (t)`$ into a single curve $`\mathrm{\Gamma }`$ at time T means here simply that

$`lim_{tT^{}}(f_+(x_1,t)f_{}(x_1,t))=0forallx_1[a,b].`$ (6)
and $`f_+(x_1,t)f_{}(x_1,t)`$ is bounded for all $`x_1[a,b]`$, $`t[0,T)`$.

When (2), (3), (4), (5) and (6) hold, then we say that the fluid forms a sharp front at time T.

The standard candidates for a singularity for MHD and QG are described by the definition given for a sharp front. We investigate the possible formation of a sharp front.

The following assumption will allow us to rule out formation of sharp fronts. We say that the fluid has controlled velocity growth if we have

$`{\displaystyle _0^T}sup\{|u(x_1,x_2,t)|:x_1[a,b],f_{}(x_1,t)x_2f_+(x_1,t)\}dt<\mathrm{}.`$ (7)
If (7) fails, then we say that the fluid has uncontrolled velocity growth.

###### Lemma 1.

Let $`\theta `$ be a smooth solution of Eq.1 defined for $`t[0,T)`$. Assume there is a sharp front at time T. Then

$`\left({\displaystyle \frac{d}{dt}}\right)\left({\displaystyle _a^b}[f_+(x_1,t)f_{}(x_1,t)]𝑑x_1\right)`$ $`=`$ $`\psi (a,f_+(a,t),t)\psi (a,f_{}(a,t),t)`$ (8)
$`+`$ $`\psi (b,f_{}(b,t),t)\psi (b,f_+(b,t),t).`$
Proof: Take the derivative of the stream function with respect to $`x_1`$ along an arc $`\mathrm{\Gamma }_\pm (t)`$

$`{\displaystyle \frac{\psi (x_1,f_\pm (x_1,t),t)}{x_1}}=u_2(x_1,f_\pm (x_1,t),t){\displaystyle \frac{f_\pm }{x_1}}u_1(x_1,f_\pm (x_1,t),t)`$ (9)
by combining (9) and (5) we obtain

$`{\displaystyle \frac{\psi (x_1,f_\pm (x_1,t),t)}{x_1}}={\displaystyle \frac{f_\pm }{t}}(x_1,t)`$ (10)
Expression (8) follows from integrating (10) with respect to $`x_1`$ between a and b.

###### Theorem 1.

Let u(x,t) be a divergence-free velocity field, with controlled velocity growth. Then a sharp front cannot develop at time T.

Proof: Assume there is a sharp front at time T. We define

$`A(t)={\displaystyle _{\stackrel{~}{a}(t)}^{\stackrel{~}{b}(t)}}[f_+(x_1,t)f_{}(x_1,t)]𝑑x_1`$
where

$`\stackrel{~}{a}(t)=a+{\displaystyle _t^T}sup\{|u(x_1,x_2,s)|:x_1[a,b],f_{}(x_1,s)x_2f_+(x_1,s)\}ds`$
and

$`\stackrel{~}{b}(t)=b{\displaystyle _t^T}sup\{|u(x_1,x_2,s)|:x_1[a,b],f_{}(x_1,s)x_2f_+(x_1,s)\}ds`$
There is controlled velocity growth, therefore there exists $`t^{}[0,T)`$ such that $`\stackrel{~}{a}(t)[a,b]`$ and $`\stackrel{~}{b}(t)[a,b]`$ for all $`t[t^{},T)`$.

We take the derivative of A(t) with respect to time

$`{\displaystyle \frac{dA(t)}{dt}}=sup|u|\delta (\stackrel{~}{b},t)+sup|u|\delta (\stackrel{~}{a},t)+{\displaystyle _{\stackrel{~}{a}(t)}^{\stackrel{~}{b}(t)}}{\displaystyle \frac{}{t}}[f_+(x_1,t)f_{}(x_1,t)]𝑑x_1.`$
where $`sup|u|=sup\{|u(x_1,x_2,t)|:x_1[a,b],f_{}(x_1,t)x_2f_+(x_1,t)\}`$ and $`\delta (z,t)=f_+(z,t)f_{}(z,t)`$.

Using the definition of the stream function, the mean value theorem and (8), it is easy to check that $`\frac{dA(t)}{dt}>0`$ for $`t>t^{}`$. This contradicts (6) by the dominated convergence theorem.

###### Acknowledgments 1.

This work was initially supported by the American Institute of Mathematics.