format: text

text:
# The Large-Scale Structure of the X-ray Background and its Cosmological Implications

## 1 Introduction

The X-ray background (XRB) was discovered before the cosmic microwave background (CMB), but only now is its origin being fully understood. The hard ($`210keV`$) XRB has been nearly completely resolved into individual sources; most of these are active galactic nuclei (AGN), but there is a minor contribution from the hot, intergalactic medium in rich clusters of galaxies (Rosati et al. 2002; Cowie et al. 2002; & Mushotzky et al. 2000). In addition, the spectra of these faint X-ray sources are consistent with that of the “diffuse” XRB. If current models of the luminosity functions and evolution of these sources are reasonably correct, then the XRB arises from sources in the redshift range $`0<z<4`$, making them an important probe of density fluctuations intermediate between relatively nearby galaxy surveys ($`z<0.5`$) and the CMB ($`z1000`$).

While there have been several attempts to measure large scale, correlated fluctuations in the hard XRB, these have only yielded upper limits or, at best, marginal detections (e.g. Barcons et al. 2000, Treyer et al. 1998 and references cited therein). On small scales, a recent correlation analysis of 159 sources in the Chandra Deep Field South survey detected significant correlations for separations out to $`100arcsec`$ (Giacconi et al. 2001). (At the survey flux level, these sources comprise roughly two thirds of the hard XRB.) On much larger scales, a recent analysis by Scharf et al. (2000) claims a significant detection of large-scale harmonic structure in the XRB with spherical harmonic order $`1\mathrm{}10`$ corresponding to structures on angular scales of $`\theta >10^{}`$ The auto-correlation results we describe here complement this analysis, indicating clustering on angular scales of $`3^{}`$ to $`10^{}`$, corresponding to harmonic order of $`\mathrm{}<30`$. However, all three detections have relatively low signal to noise and require independent confirmation.

The dipole moment of the XRB has received particular attention, primarily because of its relation to the dipole in the CMB, which is likely due to the Earth’s motion with respect to the rest frame of the CMB. If this is the case, one expects a similar dipole in the XRB with an amplitude that is 3.4 times larger because of the difference in spectral indices of the two backgrounds (Boldt 1987). In the X-ray literature, this dipole is widely known as the Compton-Getting effect (Compton & Getting 1935). In addition, it is quite likely that the XRB has an intrinsic dipole due to the asymmetric distribution in the local matter density that is responsible for the Earth’s peculiar motion in the first place. Searches for both these dipoles have concentrated on the hard XRB, since at lower energies the X-ray sky is dominated by Galactic structure. There have been several tentative detections of the X-ray dipole (e.g. Scharf et al. (2000)), but these have large uncertainties. A firm detection of an intrinsic dipole or even an upper limit on its presence would provide an important constraint on the inhomogeneity of the local distribution of matter via a less often used tracer of mass and a concomitant constraint on cosmological models (e.g., Lahav, Piran & Treyer 1997).

This paper is organized as follows. In section §2 we describe the hard X-ray map used in the analysis, the determination of its effective beam size, and cuts made to remove the foreground contaminants. In section §3, we describe the remaining large scale structures in the map and the determination of their amplitudes. The dipole is of particular interest, and is the topic of section §4. The correlation function of the residual map and its implications for intrinsic correlations are discussed in section §5. In section §6, we compare our results to previous observations and discuss the cosmological implications of these results in §7.

## 2 HEAO1 A2 $`\mathit{2}\mathit{10}\mathrm{𝑘𝑒𝑉}`$ X-ray Map

There has been much recent progress in understanding the X-ray background through instruments such as ROSAT, Chandra and XMM. However, these either have too low an energy threshold or have too small a field of view to study the large scale structure of the hard X-rays. The best observations relevant to large scale structure are still those from the HEAO1 A2 experiment that measured the surface brightness of the X-ray background in the $`0.160keV`$ band (Boldt 1987).

The HEAO1 data set we consider was constructed from the output of two medium energy detectors (MED) with different fields of view ($`3^{}\times 3^{}`$ and $`3^{}\times 1.5^{}`$) and two high energy detectors (HED3) with these same fields of view. These data were collected during the six month period beginning on day 322 of 1977. Counts from the four detectors were combined and binned in 24,576 $`1.3^{}\times 1.3^{}`$ pixels. The pixelization we use is an equatorial quadrilateralized spherical cube projection on the sky, the same as used for the COBE satellite CMB maps (White and Stemwedel 1992). The combined map has a spectral bandpass (quantum efficiency $`>50\%`$) of approximately $`317keV`$ (Jahoda & Mushotzky 1989) and is shown in Galactic coordinates in Figure 1. For consistency with other work, all signals are converted to equivalent flux in the $`210keV`$ band.

Because of the ecliptic longitude scan pattern of the HEAO satellite, sky coverage and therefore photon shot noise are not uniform. However, the variance of the cleaned, corrected map, $`2.1\times 10^2(TOTcountss^1)^2`$, is much larger than the variance of photon shot noise, $`0.8\times 10^2(TOTcountss^1)^2`$, where $`1TOTcountss^12.1\times 10^{11}ergs^1cm^2`$ (Allen, Jahoda & Whitlock 1994). This implies that most of the variance in the X-ray map is due to “real” structure. For this reason and to reduce contamination from any systematics that might be correlated with the scan pattern, we chose to weight the pixels equally in this analysis.

### 2.1 The point spread function

To determine the level of intrinsic correlations, we must account for the effects of beam smearing and so it is essential to characterize the point spread function (PSF) of the above map. The PSF varies somewhat with position on the sky because of the pixelization and the asymmetric beam combined with the HEAO1 scan pattern. We obtained a mean PSF by averaging the individual PSFs of 60 strong HEAO1 point sources (Piccinotti 1982) that were located more than $`20^{}`$ from the Galactic plane. The latter condition was imposed to avoid crowding and to approximate the windowing of the subsequent analysis (see §2.2). The composite PSF, shown in Figure 2, is well fit by a Gaussian with a full width, half maximum (FWHM) of $`3.04^{}`$.

As a check of this PSF, we generated Monte Carlo maps of sources observed with $`3^{}\times 3^{}`$ and $`3^{}\times 1.5^{}`$ (FWHM) triangular beams appropriate for the A2 detectors (Shafer 1983) and then combined the maps with quadcubed pixelization as above. The resulting average PSF from these trials is also well fit by a Gaussian with a FWHM of $`2.91^{}`$, i.e., about $`4.5\%`$ less than that in the Figure 2. Considering that the widths of the triangular beams given above are nominal, that the triangular beam pattern is only approximate (especially at higher energies), and that we did not take into account the slight smearing in the satellite scan direction (Shafer 1983), the agreement is remarkably good. In the following analysis, we use the $`3.04^{}`$ fit derived from the observed map; however, changing the PSF FWHM by a few percent does not significantly affect the results of this paper.

### 2.2 Cleaning the map

To remove the effects of the Galaxy and strong extra-galactic point sources, some regions of the map were excluded from the analysis. The dominant feature in the HEAO map is the Galaxy (see Figure 1) so all data within $`20^{}`$ of the Galactic plane or within $`30^{}`$ of the Galactic center were cut from the map. In addition, large regions ($`6.5^{}\times 6.5^{}`$) centered on $`92`$ discrete X-ray sources with $`210keV`$ fluxes larger than $`3\times 10^{11}ergs^1cm^2`$ (Piccinotti 1982) were removed from the maps. Around the sixteen brightest of these sources (with fluxes larger than $`1\times 10^{10}ergs^1cm^2`$) the cut regions were enlarged to $`9^{}\times 9^{}`$. Further enlarging the area of the excised regions had a negligible effect on the following analysis so we conclude that the sources have been effectively removed. The resulting “cleaned” map (designated Map A) has a sky coverage of $`55.5\%`$ and is our baseline map for further cuts.

To test the possibility of further point source contamination, we also used the ROSAT All-Sky Survey (RASS) Bright Source Catalog (Voges et al. 1996) to identify relatively bright sources. While the RASS survey has somewhat less than full sky coverage ($`92\%`$), it has a relatively low flux limit that corresponds to a $`210keV`$ flux of $`2\times 10^{13}ergs^1cm^2`$ for a photon spectral index of $`\alpha =2`$. Every source in the RASS catalog was assigned a $`210keV`$ flux from its B-band flux by assuming a spectral index of $`3<\alpha <1`$ as deduced from its HR2 hardness ratio. For fainter sources, the computed value of $`\alpha `$ is quite uncertain; if it fell outside the typical range of most X-ray sources, $`3<\alpha <1`$, then $`\alpha `$ was simply forced to be $`1`$ or $`3`$. It is clear that extrapolating RASS flux to the $`210keV`$ band is not accurate, so one must consider the level to which sources are masked with due caution. However, we are only using these fluxes to mask bright sources and so this procedure is unlikely to bias the results.

We considered maps where the ROSAT sources were removed at three different inferred $`210keV`$ flux thresholds. First, we identified sources with fluxes exceeding the Piccinotti level, $`3\times 10^{11}ergs^1cm^2`$. Thirty-four additional, high Galactic latitude RASS sources were removed, resulting in a map with sky coverage of $`52\%`$ (designated Map B). In order to compare more directly with the results of Scharf et al. (2000) (see §6) we removed sources at their flux level, $`2\times 10^{11}ergs^1cm^2`$. The map masked in this way has $`47\%`$ sky coverage (compared to the $`48\%`$ coverage of the Scharf et al. analysis) and is designated Map C. Finally, to check how sensitive our dipole results are to the particular masking of the map, we lowered the flux cut level to $`1\times 10^{11}ergs^1cm^2`$, which reduced the sky coverage to $`34\%`$. The map resulting from this cut is designated Map D in Table 3.

As an alternative to using the RASS sources, the map itself was searched for “sources” that exceeded the nearby background by a specified amount. Since the quad-cubed format lays out the pixels on an approximately square array, we averaged each pixel with its eight neighbors and then compared this value with the median value of the next nearest sixteen pixels (ignoring pixels within the masked regions). If the average flux associated with a given pixel exceeded the median flux of the background by a prescribed threshold, then all 25 pixels ($`6.5^{}\times 6.5^{}`$) were removed from further consideration. For a threshold corresponding to 2.2 times the mean shot noise in the map approximately 120 more “sources” were identified and masked resulting in a sky coverage of $`42\%`$. This map is labeled Map E in Table 3. Finally, we used an even more aggressive cut corresponding to 1.75 times the mean shot noise which resulted in a masked map with $`33\%`$ sky coverage. This map is labeled Map F.

## 3 Modeling the Local Large-Scale Structure

### 3.1 Sources of large scale structure

There are several local sources of large-scale structure in the HEAO map which can not be eliminated by masking isolated regions. These include diffuse emission from the Galaxy, emission (diffuse and/or faint point sources) from the Local Supercluster, the Compton-Getting dipole, and a linear time drift in detector sensitivity. Since none of these are known a priori, we fit an eight parameter model to the data. Of course, the Compton-Getting dipole is known in principle if one assumes the kinetic origin of the dipole in the cosmic microwave background; however, there may also be an intrinsic X-ray dipole that is not accounted for. (See §4 below.) Only one correction was made a priori to the map and that was for the dipole due to the Earth’s motion around the sun; however, this correction has a negligible effect on the results. A more detailed account of the model is given in Boughn (1999).

The X-ray background has a diffuse (or unresolved) Galactic component which varies strongly with Galactic latitude (Iwan et al. 1982). This emission is still significant at high Galactic latitude ($`b_{II}>20^{}`$) and extrapolates to $`1\%`$ at the Galactic poles. We modeled this emission in two ways. The first model consisted of a linear combination of a secant law Galaxy with the Haslam $`408GHz`$ full sky map (Haslam et al. 1982). The latter was included to take into account X-rays generated by inverse Compton scattering of CMB photons from high energy electrons in the Galactic halo, the source of much of the synchrotron emission in the Haslam map. As an alternative Galaxy model we also considered the two disk, exponentially truncated model of Iwan et al. (1982). Our results are independent of which model is used.

In addition to the Galactic component, evidence has been found for faint X-ray emission from plane of the Local Supercluster (Jahoda 1993, Boughn 1999). Because of its faintness, very detailed models of this emission are not particularly useful. The model we use here is a simple “pillbox”, i.e uniform X-ray emissivity within a circular disk of thickness equal to a $`1/4`$ of the radius and with its center located $`4/5`$ of a radius from us in the direction of the Virgo cluster (see Boughn 1999 for details). The amplitude of this emission, while significant, is largely independent of the details of the model and, in any case, has only a small effect on the results.

Time drifts in the detector sensitivity can also lead to apparent structure in the reconstructed X-ray map. At least one of the A-2 detectors changed sensitivity by $`1\%`$ in the six month interval of the current data set (Jahoda 1993). Because of the ecliptic scan pattern of the HEAO satellite, this results in a large-scale pattern in the sky which varies with ecliptic longitude with a period of $`180^{}`$. If the drift is assumed to be linear, the form of the resulting large-scale structure in the map is completely determined. A linear drift of unknown amplitude is taken into account by constructing a sky map with the appropriate structure and then fitting for the amplitude simultaneously with the other parameters. We investigated the possibility of non-linear drift by considering quadratic and cubic terms as well; however, this did not significantly reduce the $`\chi ^2`$ of the fit nor change the subsequent results.

### 3.2 Modeling the maps

The eight parameters that characterize the amplitude of these structures are used to model the large-scale structure in the HEAO map. Let the X-ray intensity map be denoted by the vector $`𝐈`$, where the element $`I_i`$ is the intensity in the $`i^{th}`$ pixel. The observed intensity is modelled as the sum of eight templates with amplitudes described by the eight dimensional vector $`𝐚`$,

$$𝐈=\stackrel{~}{X}𝐚+𝐧$$
(3-1)
where $`\stackrel{~}{X}`$ is an $`8\times n_{pix}`$ matrix whose elements are the values of each template function at each pixel of the map. As discussed above, these template functions include: a uniform map to represent the monopole of the X-ray background; the three components of a dipole (in equatorial coordinates); the large-scale pattern resulting from a linear instrumental gain drift; a Galactic secant law; the Haslam $`408GHz`$ map ; and the amplitude of the “pillbox” model of the local supercluster. The noise vector $`𝐧`$ is assumed to be Gaussian distributed with correlations described by $`\stackrel{~}{C}𝐧𝐧^T`$.

As discussed above (§2), we chose to weight each pixel equally since the shot noise is considerably less than the “real” fluctuations in the sky. For the purposes of fitting the map to the above model we consider both photon shot noise and fluctuations in the XRB (see Figure 3) to be “noise”. This noise is correlated and a minimum $`\chi ^2`$ fit must take such correlations into account. However, for simplicity, we ignore these correlations when finding the best fit model amplitudes and perform a standard least squares fit by minimizing $`|𝐈\stackrel{~}{X}𝐚|^2`$ on the cleaned HEAO map. From the standard equations of linear regression the values of the parameters that minimize this sum are

$$𝐚=\stackrel{~}{B}^1\stackrel{~}{X}^T𝐈$$
(3-2)
where $`\stackrel{~}{B}=\stackrel{~}{X}^T\stackrel{~}{X}`$ is a symmetric eight by eight matrix. This would be the maximum likelihood estimator if the correlation matrix were uniform and diagonal. Though this fit ignores correlations in the errors, it is unbiased and is likely to be very close to the minimum $`\chi ^2`$ (maximum likelihood) fit, since the noise correlations are on a much smaller scale than the features we are attempting to fit.

The correlated nature of the noise cannot be ignored when computing the uncertainties in the fit since there are far fewer noise independent data points than there are pixels in the map. It is straightforward to show that errors in the estimated parameters $`\delta 𝐚`$ are given by

$$\delta 𝐚\delta 𝐚^T=\stackrel{~}{B}^1\stackrel{~}{X}^T\stackrel{~}{C}\stackrel{~}{X}\stackrel{~}{B}^1$$
(3-3)
This error is likely to be only slightly larger than would be the case for the maximum likelihood estimator. $`\stackrel{~}{C}`$ is a combination of the uncorrelated shot noise and the correlated fluctuations indicated in Figure 3. We assume it to be homogeneous and isotropic, i.e., that $`\stackrel{~}{C}_{ij}`$ depends only on the angular separation of the $`i`$ and $`j`$ pixels.

Table 1 lists the values and errors of the parameters fit to Map C (see §2). Instrument time drift, the Galaxy and structure associated with the local supercluster all appear to be significant detections. The dipole is detected at about the $`2\sigma `$ level and is consistent with that expected for the Compton-Getting dipole (see Table 3). Table 2 lists the elements of the normalized correlation matrix of the fit parameters and it is apparent that the parameters are largely uncorrelated. This was supported by fits that excluded some of the parameters (see §4).

To compute the true $`\chi ^2(𝐈\stackrel{~}{X}𝐚)^T\stackrel{~}{C}^1(𝐈\stackrel{~}{X}𝐚)`$ of the fit requires inverting $`\stackrel{~}{C}`$ which is a $`11,531\times 11,531`$ matrix. Instead we compute an effective reduced $`\chi ^2`$ using

$$\chi _{eff}^2\frac{1}{N}(𝐈\stackrel{~}{X}𝐚)^T\stackrel{~}{D}^1(𝐈\stackrel{~}{X}𝐚)$$
(3-4)
where $`\stackrel{~}{D}`$ is the diagonal part of the correlation matrix, $`\stackrel{~}{D}_{ii}=\sigma _{s,i}^2+\sigma _b^2`$, $`\sigma _{s,i}`$ is the shot noise in the $`i^{th}`$ pixel, $`\sigma _{b}^{}{}_{}{}^{2}`$ is the variance of the fluctuations in the XRB, and $`N`$ is the number of pixels minus eight, the number of degrees of freedom in the fit. The shot noise in a given pixel is inversely proportional to the number of photons received and we assume is inversely proportional to the coverage of that pixel. This is approximately true since all the non-flagged pixels are exposed to approximately the same flux. We find $`\chi _{eff}^{}{}_{}{}^{2}=1.00`$ for this fit, which we take as an indication that we have properly characterized the amplitude of the noise so that the errors quoted in the table have neither been underestimated nor overestimated. However, it should be emphasized that $`\chi _{eff}^{}{}_{}{}^{2}`$ is not to be interpreted statistically as being derived from a $`\chi ^2`$ distribution.

The residual maps show very little evidence for structure on angular scales $`\theta >10^{}`$ above the level of the noise, $`\delta I^2/\overline{I}^210^5`$ where $`\delta I`$ are the residual fluctuations in X-ray intensity and $`\overline{I}`$ is the mean intensity (see Figure 4). Since all the components of the model have significant structure on large angular scales, it appears that these particular systematics have been effectively eliminated.

## 4 The Dipole of the X-ray Background

The dipole fit to the map is consistent with the Compton-Getting dipole and there is no evidence for any additional intrinsic dipole in the XRB. To make this more quantitative, we corrected the maps for the predicted Compton-Getting dipole and fit the corrected map for any residual, intrinsic dipole. These dipole fit parameters are also included in Table 1.

Leaving out any individual model component, such as the time drift, the galaxy, Haslam or supercluster template, made little difference in the amplitude of the fit dipole. This is, perhaps, not too surprising since the Galaxy and time drift models are primarily quadrupolar in nature and the pancake model, while possessing a significant dipole moment, has a relatively small amplitude. All such fits were consistent with the Compton-Getting dipole alone. Even when all four of these parameters were excluded from the fit, the dipole amplitude increased by only $`0.004TOTcountss^1`$ with a direction that was was $`33^{}`$ from that of the CMB dipole. The effective $`\chi ^2`$ for the four parameter fit was, however, significantly worse, i.e., $`\chi _{eff}^{}{}_{}{}^{2}=1.05`$.

Table 3 lists the amplitude and direction of the dipole fit to Map C along with the fits to Maps D, E, and F. All of these fits are consistent with amplitude and direction of the Compton-Getting dipole (as inferred from the CMB dipole) which is also indicated in the Table. The effective $`\chi ^2`$s of these fits range from 0.99 to 1.01, again indicating that the amplitude of the noise is reasonably well characterized. No errors are given for these quantities for reasons that will be discussed below. In order to check for unknown systematics, we performed dipole fits to a variety of other masked maps with larger Galaxy cuts as well as cuts of the brighter galaxies in the Tully Nearby Bright Galaxy Atlas (Tully 1988). The details of these cuts are discussed in Boughn (1999); however, none had a significantly different dipole fit.

Since all of these dipoles are consistent with the Compton-Getting dipole we also fit these maps with a six parameter fit in which the dipole direction was constrained to be the direction of the CMB dipole. The dipole amplitude of these fits and errors computed according to Eq. (3-3) are also given in Table 3.

Even though we find no evidence for an intrinsic dipole in the XRB, it would be useful to place an upper limit on its amplitude. We define the dimensionless dipole by writing the first two moments of the X-ray intensity as

$$I(\widehat{𝐧})=\overline{I}(1+\stackrel{}{\mathrm{\Delta }}\widehat{𝐧}),$$
(4-1)
where $`\stackrel{}{\mathrm{\Delta }}`$ is a vector in the direction of the dipole. There are various approaches one could take to find an upper limit, and the problem is complicated somewhat because the error bars are anisotropic (see Table 1). The dipole in the $`\widehat{y}`$ direction is less constrained than in the other directions because of the anisotropic masking of the map. Here we take the limits on the individual components of the intrinsic dipole and marginalize over the dipole direction to obtain a distribution for its amplitude. For this, we use a Bayesian formalism and assume a uniform prior on the amplitude, $`|\stackrel{}{\mathrm{\Delta }}|`$. We find $`\mathrm{\Delta }<0.0052`$ at the 95 % C.L. If the direction of the dipole is fixed to be that of the CMB dipole then the 95% C.L. upper limits on the dipole amplitudes fall in the range $`0.0030`$ to $`0.0043`$ for the fits listed in Table 3.

The same sort of problem arises when trying to attach an error bar to the amplitude of the dipole fits to the maps which include the Compton-Getting dipole. It seems clear from Table 1 that we find evidence for a dipole at the 2 $`\sigma `$ level. This is supported by the six parameter fits of Table 3, where the various maps indicate positive detections at a 2 to 3 $`\sigma `$ level. However, in the eight parameter fits, the dipole amplitude is a non-linear combination of the fit components. There are two approaches we can take in converting the three dimensional limits to a limit on the dipole amplitude. We can either fix the direction in the direction of the CMB dipole, which results in the constrained limits shown in Table 3. Alternatively, we can marginalize over the possible directions of the dipole, which will necessarily result in weaker limits than when the direction is fixed. This is particularly true here, where the direction of greatest uncertainty in the dipole measurement is roughly orthogonal to the expected dipole direction. In the case of the Compton-Getting dipole, there is a strong prior that it should be in the CMB dipole direction, so our limit is stronger than it would be if we did not have information about the CMB.

In addition to the upper limit on the intrinsic dipole amplitude, we can also constrain the underlying dipole variance, which can, in turn, be used to test theoretically predicted power spectra. While the observed amplitude is related to the dipole variance, $`\mathrm{\Delta }^2=3\sigma _\mathrm{\Delta }^2`$, there is large uncertainty due to cosmic variance. The dipole represents only three independent samplings of $`\sigma _\mathrm{\Delta }`$. To constrain $`\sigma _\mathrm{\Delta }`$, we again take a Bayesian approach and calculate the likelihood of observing the data given the noise and $`\sigma _\mathrm{\Delta }`$,

$$𝒫(\stackrel{}{\mathrm{\Delta }}|\sigma _\mathrm{\Delta })e^{\mathrm{\Delta }_i^2/2(\sigma _i^2+\sigma _\mathrm{\Delta }^2)}(\sigma _i^2+\sigma _\mathrm{\Delta }^2)^{1/2},$$
(4-2)
where the product is over the three spatial directions and we have ignored the small off-diagonal noise correlations (see Table 2). With a uniform prior on $`\sigma _\mathrm{\Delta }`$, its posterior distribution implies a 95% C.L. upper limit of $`\sigma _\mathrm{\Delta }<0.0064`$. This is twice as high as would be inferred from the limit on the dipole because of the significant tail in the distribution due to cosmic variance. The limit implied by the dipole (of Map C), $`\sigma _\mathrm{\Delta }=\mathrm{\Delta }/\sqrt{3}<0.0030`$ is at the 80% C.L. The difference between the limits arises because occasionally a small dipole can occur even when the variance is large.

The bottom line is that we have detected the dipole in the XRB at about the 2 $`\sigma `$ level and that it is consistent with the Compton-Getting dipole. There is no evidence for any other intrinsic dipole at this same level. We will discuss the apparent detection of an intrinsic dipole by Scharf et al. (2000) in §6.

## 5 Correlations in the X-ray Background

A standard way to detect the clustering of sources (or of the emission of these sources) is to compute the auto-correlation function (ACF), defined by

$$\omega (\theta )=\frac{1}{\overline{I}^2}\underset{i,j}{}(I_i\overline{I})(I_j\overline{I})/N_\theta $$
(5-1)
where the sum is over all pairs of pixels, $`i,j`$, separated by an angle $`\theta `$, $`I_i`$ is the intensity of the $`ith`$ pixel, $`\overline{I}`$ is the mean intensity, and $`N_\theta `$ is the number of pairs of pixels separated by $`\theta `$. Figure 3 shows the ACF of the residual map after being corrected with the 8-parameter fit and for photon shot noise in the $`\theta =0^{}`$ bin. The error bars are highly correlated and were determined from Monte Carlo trials in which the pixel intensity distribution was assumed to be Gaussian with the same ACF as in the figure. There is essentially no significant structure for $`\theta >13^{}`$ once local structures have been removed, as is evident in Figures 3, 4, and 5.

It is clear from Figure 3 that the residuals of Map A possess significant correlated structure. It must be determined how much, if any, is due to clustering in the XRB and how much is simply due to smearing by the PSF of the map. It is straightforward to show that an uncorrelated signal smeared by a Gaussian PSF, $`PSF(\theta )e^{\theta ^2/2\sigma _p^2}`$, results in an ACF of the form $`\omega (\theta )e^{\theta ^2/4\sigma _p^2}`$ where $`\sigma _p=1.29^{}`$ is the Gaussian width of the PSF in Figure 2 ($`\theta _{FWHM}^2=8\sigma _p^2\mathrm{ln}2.`$) The dashed curve in Figure 3 is essentially this functional form, modified slightly to take into account the pixelization. In the plot, its amplitude has been forced to agree with $`\theta =0^{}`$ data point, while a maximum likelihood fit results in an amplitude about 5% lower (a consequence of the correlated noise). For $`\theta >3^{}`$, the ACF of the data clearly exceeds that accountable by beam smearing and this excess is even more pronounced with the maximum likelihood fit. The reduced $`\chi ^2`$ for the fit to the first eight data points ($`\theta <9^{}`$) is $`\chi ^2=18.6`$ for six degrees of freedom which is another measure of the excess structure between 3 and 9 degrees. Note, this is a two parameter fit since the photon shot noise (which occurs only at $`\theta =0^{}`$) is also one of the parameters.

While it is apparent that there is some intrinsic correlation in the X-ray background, it cannot be estimated by the residual to the above two parameter fit since that overestimates the contribution of beam smearing in order to minimize $`\chi ^2`$. Instead, we also include in the fit a form for the intrinsic correlation and find its amplitude as well. Since the signal to noise is too small to allow a detailed model of the intrinsic clustering, we chose to model it with a simple power-law $`\omega (\theta )=(\theta _0/\theta )^ϵ`$. This form provides an acceptable fit to the ACF of both radio and X-ray surveys on somewhat smaller angular scales (Cress & Kamionkowski 1998, Soltan et al. 1996, Giacconi et al. 2001). This intrinsic correlation was then convolved with the PSF and applied to the quadcube pixelization of the map (e.g., Boughn 1998).

Finally, it is important to take into account the effects of the 8-parameter fit used to remove the large-scale structure as discussed in §3. If the X-ray background has intrinsic structure on the scale of many degrees, the 8-parameter fit will tend to remove it in order to minimize $`\chi ^2`$. Since the model is composed of relatively large scale features, the greatest effect is expected for the largest angles. The significance of this effect was determined by generating Monte Carlo trials assuming a Gaussian pixel intensity distribution with the same ACF as in Figure 3. The 8-parameter model was then fit and each trial map was corrected accordingly. The ACFs computed for these corrected maps indicate that, as expected, the value of the ACF is significantly attenuated for larger angles. The attenuation factor for $`\theta =9^{}`$ is already 0.55 and decreases rapidly for larger angles. The errors indicated in Figure 3 were also determined from these Monte Carlo trials and, as mentioned above, are highly correlated.

We model the auto-correlation function as a sum of three templates and fit for their best amplitude. Much of the analysis parallels the discussion for the fits of large scale structure in the map, with the exception that here the number of bins is small enough that it is simple to calculate the maximum likelihood fit. Again, we model the observed correlation function vector as $`\omega =\stackrel{~}{W}𝐜+𝐧_\omega `$, where $`\stackrel{~}{W}`$ is a $`3\times n_{bin}`$ matrix containing the templates for shot noise ($`\omega _s`$), beam smearing ($`\omega _{PSF}`$), and intrinsic correlations in the XRB ($`\omega _{intr}`$). The amplitudes are given by the three element vector $`𝐜`$ and the noise is described by the correlation matrix determined from Monte Carlo trials, $`\stackrel{~}{C}_\omega =𝐧_\omega 𝐧_\omega ^T`$.

Shot noise contributes only to the first bin (zero separation) of the ACF and has amplitude given by its variance, $`\omega _s`$. Beam smearing contributes to the ACF with a template that looks like the beam convolved with itself, so appears as a Gaussian with a FWHM a factor of $`\sqrt{2}`$ larger than that of the beam and has amplitude denoted as $`\omega _{psf}`$. Finally, the intrinsic correlations are modelled as $`(\theta _0/\theta )^ϵ`$, which is then smoothed appropriately by the beam. Its amplitude is denoted by its inferred correlation at zero separation, $`\omega _{intr}.`$ We fit using a range of indices, $`0.8ϵ1.6`$, which cover the range of theoretical models of the intrinsic correlation. Both the PSF template and the intrinsic template are modified to include the effects of the attenuation at large angles as discussed above.

Minimizing $`\chi ^2`$ with respect to the three fit parameters, $`𝐜`$, results in the maximum likelihood fit to the model if one assumes Gaussian statistics. This assumption is reasonable by virtue of the central limit theorem since each data point consists of the combination of the signals from a great many pixels, each of which is approximately Gaussian distributed. In the presence of correlated noise, $`\chi ^2`$ is defined by

$$\chi ^2=(\omega \stackrel{~}{W}𝐜)^T\stackrel{~}{C}_\omega ^1(\omega \stackrel{~}{W}𝐜)$$
(5-2)
It is straightforward to show that the value of the parameters that minimize $`\chi ^2`$ are given by

$$𝐜=\mathrm{\Omega }^1\stackrel{~}{W}^T\stackrel{~}{C}_\omega ^1\omega $$
(5-3)
where $`\mathrm{\Omega }=\stackrel{~}{W}^T\stackrel{~}{C}_\omega ^1\stackrel{~}{W}.`$ Because of the large attenuation of the ACF at large angles, we chose to fit to only those data points with $`\theta _i9^{}`$, i.e., $`i8`$, even though there appears to be statistically significant structure out to $`\theta 13^{}`$. The results of the fit of the $`ϵ=1`$ model to the ACF of the residuals of Map A are listed in Table 4 and plotted in Figure 3.

It is also straightforward to show that the correlation matrix of the fit parameters is given by, $`\delta c_n\delta c_m=\mathrm{\Omega }_{nm}^1`$ so the errors given in Table 4 are given by $`\sigma _{c_n}^2=\mathrm{\Omega }_{nn}^1`$ and the normalized correlation coefficients by $`r_{nm}=\mathrm{\Omega }_{nm}^1/(\mathrm{\Omega }_{nn}^1\mathrm{\Omega }_{mm}^1)^{1/2}`$. The correlations are as expected, i.e., $`\omega _{intr}`$ and $`\omega _{psf}`$ are highly correlated, while $`\omega _s`$ is relatively uncorrelated with the other two parameters.

From the results in Table 4 it appears that intrinsic correlations in the X-ray background are detected at the 4 $`\sigma `$ level for sources with flux levels below $`3\times 10^{11}ergs^1cm^2`$. Of course, if we have not successfully eliminated sources with fluxes larger than this, then the clustering amplitude might well be artificially inflated. It was for this reason that we used the RASS catalog to identify and remove additional sources with intensities $`>3\times 10^{11}ergs^1cm^2`$, the result of which was Map B (see §2). The fits to Map B are also listed in Table 4. The clustering amplitude, $`\omega _{intr}`$, of the fits to this modified map were only $`11\%`$ less than that of Map A, i.e., considerably less than 1 $`\sigma `$. The $`\chi ^2`$s of both fits are acceptable.

These results are not very sensitive to the attenuation corrections. If they are removed from the model, the resulting amplitude of the fit clustering coefficient only decreases by $`20\%`$, less than $`1\sigma `$. It should be noted that the corrections were relatively small (an average attenuation factor of 0.83 ranging from 1.0 at $`\theta =0^{}`$ to 0.55 for $`\theta =9^{}`$) and in all cases, the attenuation was less than the error bar of the corresponding data point. If data points with $`\theta >9^{}`$ are included, the fits become more sensitive to the attenuation corrections which are, in turn, quite sensitive to the 8-parameter fit.

Figure 4 is a plot of the residuals of the fit to the ACF of Map A for $`\theta 9^{}`$ and of the uncorrected ACF from $`10^{}`$ to $`180^{}`$. The vertical scale is the same as for Figure 3. The *rms* of these 140 data points is $`1\times 10^5`$ and it is clear that there is very little residual structure at levels exceeding this value. The observed correlation function for $`\theta >10^{}`$ in Figure 4 is entirely consistent with the noise levels determined from the Monte Carlo simulations: the *rms* of $`\omega /\sigma `$ is 1.03, indicating that there is no evidence for intrinsic fluctuations on these scales. We also take this as an indication that the errors are reasonably well characterized by the Monte Carlo calculation. The variance of the photon shot noise, $`\sigma _{s}^{}{}_{}{}^{2}=\omega _s\overline{I}^2`$, is consistent with that expected from photon counting statistics only (Jahoda 2001). It should be noted that not only the shape but the amplitude of the beam smearing contribution, $`\omega _{PSF}`$, can be computed from source counts as a function of $`210keV`$ flux. We will argue in §6 that, while our fitted value is consistent with current number counts, the latter are not yet accurate enough to correct the data.

Figure 5 shows the model of the intrinsic clustering, $`\omega _{intr}`$, compared to the data with both the shot noise and PSF component removed. The model curve is not plotted beyond $`\theta =9^{}`$ since the attenuation factor due to the 8-parameter fit corrections are large and uncertain at larger angles. The amplitude of $`\omega _{intr}`$ is sensitive to the exponent in the assumed power law for the intrinsic correlations. For example, the fit amplitude for a $`\theta ^{1.6}`$ power law the amplitude is a factor of $`2`$ larger than for a $`\theta ^{0.8}`$ power law. However, for a range of fits with $`0.8ϵ1.6`$, the values of $`\omega _{intr}(\theta )`$ at $`\theta =4.5^{}`$ are all within $`\pm 3\%`$ of each other. Therefore, we chose to normalize the X-ray ACF at $`4.5^{}`$ when comparing to cosmological models (see §7.1). The $`\chi ^2s`$ are reasonable for all these fits.

The bottom line is that there is fairly strong evidence for intrinsic clustering on these angular scales at the level of $`\omega _{intr}3.6\times 10^4\theta ^1`$ (see §6.1). While the exponent is $`ϵ1`$, it is not strongly constrained. The implications of the intrinsic clustering of the X-ray background will be discussed in §7.

## 6 Comparisons with Previous work

### 6.1 Clustering

As mentioned above, the component of the ACF due to beam smearing, $`\omega _{PSF}`$, can be determined with no free parameters if the flux limited number counts of X-ray sources are known. While such counts are still relatively inaccurate for our purposes, we did check to see if our results are consistent with current data. Over a restricted flux range, the X-ray number counts, $`N(<S)`$, are reasonably approximated by a power law, i.e., $`N(<S)=KS^\gamma `$ where $`S`$ is the flux of the source. It is straightforward to show that the variance of flux due to a Poisson distribution of sources is

$$\sigma _{PSF}^2(0)=\pi \sigma _{p}^{}{}_{}{}^{2}A^2\gamma KS^{2\gamma }/(2\gamma )$$
(6-1)
where $`S`$ is the upper limit of source flux, $`\sigma _p`$ is the Gaussian width of the PSF and $`A^1`$ is the flux of a point source that results in a peak signal of $`1TOTcounts^1`$ in our composite map. In our case, $`A=2.05\times 10^{10}erg^1scm^2`$. Using the $`BeppoSAX210kev`$ number count data of Giommi, Perri, & Fiore (2000), the $`Chandra`$ data of Mushotzky et al. (2000), and the $`HEAO1A2`$ data of Piccinotti et al. (1982), we constructed a piecewise power-law $`N(<S)`$ for the range $`6\times 10^{16}<S<3\times 10^{11}ergs^1cm^2`$ and computed $`\omega _{PSF}(0)=\sigma _{PSF}^2/\overline{I}^2`$ to be $`8.4\times 10^4`$. The close agreement of this value with those in Table 4 is fortuitous given that the value depends most sensitively on the number counts at large fluxes which are the most unreliable, typically accurate only to within a factor of two. However, it is clear that the $`\omega _{PSF}`$ of Table 4 are quite consistent with the existing number count data.

The results of §5 clearly indicate the presence of intrinsic clustering in the XRB. Mindful that the detection is only $`4\sigma `$, we tentatively assume that the ACF has an amplitude of $`\omega _{intr}2.5\times 10^4`$ (the average of the two values in Table 4) and is consistent with a $`\theta ^1`$ functional dependence. It is straight forward to relate this to the underlying correlation amplitude, $`\theta _0`$. The variance of correlations smoothed by a beam of Gaussian size $`\sigma `$ is given by

$$\omega _{intr}(0)=\frac{\mathrm{\Gamma }(1ϵ/2)}{2^ϵ}\left(\frac{\theta _0}{\sigma }\right)^ϵ.$$
(6-2)
When $`ϵ=1`$, then $`\theta _0=2\sigma \omega _{intr}/\pi ^{1/2}`$. Using this, we find

$$\omega _{XRB}(\theta )3.6\times 10^4\theta ^1$$
(6-3)
where $`\theta `$ is measured in degrees and the normalization is such that $`\omega _{XRB}(0)=\delta I^2/\overline{I}^2`$.

For comparison, this amplitude is about a factor of three below the $`2\sigma `$ upper limit determined by Carrera et al. (1993) obtained with Ginga data ($`412keV`$) for angular scales between 0.2 and 2.0 degrees. The detection of a significant correlation in the $`HEAO1A2`$ data at the level of $`3\times 10^5`$ at $`\theta =10^{}`$ by Mushotzky and Jahoda (1992) was later attributed to structure near the super-Galactic plane (Jahoda 1993). To check for this effect in the present analysis, we masked all pixels within 15 and 20 degrees from the super-Galactic plane. The results were indistinguishable from those of Table 4. It is interesting that the clustering indicated in Eq. (6-3) is consistent with this level of fluctuations at $`10^{}`$; however, our sensitivity has begun to decline significantly at $`10^{}`$ due to the fit for large scale structures. A correlation analysis of ROSAT soft X-ray background by Soltan et al. (1996) detected correlations about an order of magnitude larger than indicated in Eq. (6-3). Even considering that the ROSAT band ($`0.52.0keV`$) is distinct from the HEAO band, it is difficult to imagine that the two correlation functions could be so disparate unless the lower energy analysis is contaminated by the Galaxy.

While there has yet to be a definitive detection of the clustering of hard X-ray sources, a recent deep Chandra survey of 159 sources shows a positive correlation of source number counts on angular scales of 5 to 100 arcsec (Giacconi et al. 2001). Although the signal to noise is low and dependent on source flux, the implied number count ACF is roughly consistent with $`\omega _N(\theta )3\times 10^3\theta ^1`$ where $`\omega _N(0)\delta N^2/\overline{N}^2`$ and $`\overline{N}`$ is the mean surface density of sources. This is consistent with the correlation function determined by Vikhlinin & Forman (1995) for sources identified within ROSAT PSPC deep pointings. A direct comparison between the Chandra result with that of Eq. (6-3) is complicated by the more than one hundred times difference in the angular scales of the two analyses. It is doubtful that a single powerlaw model is adequate over this range. Furthermore, one is a luminosity ACF while the other is a flux limited, number count ACF. Relating the two requires understanding the luminosity function and its evolution as well as how the X-ray bias depends on scale. For these reasons, a direct comparison would be difficult to interpret. We only note in passing that the small angular scale ACF is a factor of eight larger than that of Eq. (6-3) assuming a $`\theta ^1`$ dependence.

Finally, the recent harmonic analysis of the $`HEAO1A2`$ data by Scharf et al. (2000) yielded a positive detection of structure in the XRB out to harmonic order $`l10`$. The present analysis looks at similar maps, so the results should be comparable. A direct comparison is complicated by the differences in analysis techniques, masking and corrections to the map. A rough comparison can be made by performing a Legendre transform on the $`\theta ^1`$ ACF model of Eq. (6-3). The ACF can be expressed in terms of Legendre polynomials as

$$\omega (\theta )=\frac{1}{4\pi }\underset{\mathrm{}}{}(2\mathrm{}+1)C_{\mathrm{}}P_{\mathrm{}}(\mathrm{cos}\theta )$$
(6-4)
where the $`C_l`$ constitute the angular power spectrum. Taking the Legendre transform

$$C_{\mathrm{}}=2\pi _1^1\omega (\theta )P_{\mathrm{}}(\mathrm{cos}\theta )d(\mathrm{cos}\theta )$$
(6-5)
where $`P_{\mathrm{}}(\theta )`$ is the Legendre polynomial of order $`\mathrm{}`$. Substituting the $`\theta ^1`$ model into this expression results in power spectrum coefficients, $`C_{\mathrm{}}4\times 10^5/\mathrm{}`$ for $`\mathrm{}5.`$ Note that for $`\mathrm{}5`$, this expression is relatively insensitive to the index $`ϵ`$ in the expression for $`\omega _{intr}`$. While these values are highly uncertain, they are comparable to those found by Scharf et al. (2000) when the sky coverage and differences in notation are accounted for. Considering the low signal to noise of the data as well as the differences in the two analyses, a more detailed comparison would not be particularly useful.

### 6.2 The Dipole

Scharf et al. (2000) also searched for the XRB dipole using a $`HEAO1A2`$ map and similar methods to those described in §4. They claim a detection of an intrinsic dipole with amplitude $`\mathrm{\Delta }0.0065`$, though with a rather large region of uncertainty, i.e., $`0.0023<\mathrm{\Delta }<0.0085`$, and in a direction about $`80^{}`$ from that of the Compton-Getting dipole, in the general direction of the Galactic center. They used the $`3^{}\times 1.5^{}`$ $`HEAO1A2`$ map restricted to regions further than $`22^{}`$ from the Galactic plane. In addition, regions about sources with fluxes greater than $`2\times 10^{11}ergs^1cm^2`$ were cut from the map. The sky coverage and the level of source removal closely correspond to those of our Map C. However, since we used a combination of the $`3^{}\times 1.5^{}`$ and $`3^{}\times 3^{}`$ maps, our map has significantly less ($`1/\sqrt{3}`$) photon shot noise. While our analyses are similar, there are some significant differences: they corrected the map beforehand for linear instrument drift and Galaxy emission while we fit for those components simultaneously with the dipole and with emission from the local supercluster which they ignore.

The upper limit on the intrinsic dipole we find is about the same amplitude as the Compton-Getting dipole, i.e., $`\mathrm{\Delta }<0.0052`$ at the 95 % C.L. Thus we exclude roughly the upper half of the Scharf et al. range and believe that their claim of a detection is probably an overstatement. While Scharf et al. do not take into account emission from the plane of the local supercluster, even if we leave that component out of our fit, the dipole moment (including the C-G dipole) increases by only $`0.005TOTctss^1`$ and is still consistent with the C-G dipole. The upper limit on the intrinsic dipole with this fit is determined primarily by the noise in the fit and is not significantly different from that value given above. It is difficult to understand how their quoted errors could be two to four times less than those quoted in Table 3. The shot noise variance in the map they used was three times greater than in our combination map and so one would expect their errors would be somewhat larger than those above. They performed only a four parameter fit (offset plus dipole) which would result in a slight reduction of error; however, this is a bit misleading since their Galaxy model and linear time drift are derived from essentially the same data set. It is possible that their lower errors could result from ignoring correlations in the noise (our detected ACF). In any case, we find no evidence for an intrinsic dipole moment in the XRB.

## 7 Implications for Cosmology

### 7.1 Clustering and Bias in the X-ray Background

The observed X-ray auto-correlation can be compared to the matter auto-correlation predicted by a given cosmological model. The linear bias factor for the X-rays can then be determined by normalizing to the observed CMB anisotropies. Since X-rays arise at such high redshifts, the fluctuations we measure are on scales $`\lambda 100h^1Mpc`$, comparable to those constrained by the CMB, i.e., on wavelengths that entered the horizon about the time of matter domination.

The predicted X-ray ACF depends on both the cosmological model and on the model for how the X-ray sources are distributed in redshift, which is constrained by observed number counts and the redshift measurements of discrete sources. We use the redshift distribution described in Boughn, Crittenden and Turok (1998), based on the unified AGN model of Comastri et al. (1995). (See also the more recent analysis by Gilli et al. (2001).) While we will not reproduce those calculations here, the basic result is that the XRB intensity is thought to arise fairly uniformly in redshift out to $`z=4`$. Our results here are not very sensitive to the precise details of this distribution.

Another issue in the calculation of the power spectrum is the possible time dependence of the linear bias. Some recent studies indicate that the bias is tied to the growth of fluctuations and may have been higher at large redshift (Fry 1996, Tegmark & Peebles 1998). For the purposes of the power spectrum, an evolving bias will have the same effect as changing the source redshift distribution. Again, our results are not strongly dependent on these uncertainties, but they comprise an important challenge to using the X-ray fluctuation studies to make precision tests of cosmology.

Figure 6 shows the predicted XRB power spectrum, normalized to our observations. On the scales of interest, the predicted spectra are fairly featureless, and reasonably described by a power law in $`\mathrm{}`$, $`C_{\mathrm{}}\mathrm{}^{ϵ2}`$, which corresponds to the correlation of the form $`\omega (\theta )=(\theta _0/\theta )^ϵ`$. For the models of interest, $`1.1<ϵ<1.6`$ for $`\mathrm{}<100`$, and decreases at higher $`\mathrm{}`$ (smaller separations). Note that the spectra calculated by Treyer et al. (1998) appear to be consistent with our findings, suggesting $`ϵ=1.2`$. The precise index $`ϵ`$ depends on the position of the power spectrum peak which is determined by the shape parameter, $`\mathrm{\Gamma }\mathrm{\Omega }_mh.`$ Larger values of $`\mathrm{\Gamma }`$ imply more small scale power and thus higher $`ϵ.`$

For simplicity, we normalize to the X-ray correlation function at $`4.5^{}`$, $`\omega (4.5^{})=1.0\pm 0.25\times 10^4`$. This separation is large enough to be independent of the PSF contribution to the ACF, but not so large that the attenuation from the large scale fits becomes significant. Also, the value of the fit ACF at $`4.5^{}`$ is nearly independent of the index $`ϵ`$ (see §5). As can be seen from Figure 6, this normalization fixes the power spectrum at $`\mathrm{}57`$.

We normalize the fluctuations to the COBE power spectrum as determined by Bond, Jaffe & Knox (1998). However, it should be noted that fits to smaller angular CMB fluctuations indicate that using COBE alone may somewhat overestimate the matter fluctuation level (Lahav et al. 2002). The biases derived from the models appear to be largely insensitive to the matter density. This is due to a cancellation of two effects: the CMB normalization and the power spectrum shape (White & Bunn 1995). The biases are roughly inversely proportional to $`h`$. Typical biases appear to be $`b_X=2.3\pm 0.3(0.7/h)^{0.9}`$, increasing slightly as $`\mathrm{\Gamma }`$ decreases and the peak of the power spectrum moves to larger scales.

### 7.2 The Intrinsic X-ray Dipole

The theoretical models normalized to our observations predict the intrinsic power on a wide range of scales, assuming the X-ray bias is scale independent. In particular, these models give a prediction for the variance of the intrinsic dipole moment. We can compare our model predictions to the the upper limit for the intrinsic dipole to see if we should have observed it in the X-ray map.

The dipole amplitude in the $`\widehat{z}`$ direction is related to the spherical harmonic amplitude by $`\mathrm{\Delta }_z=\sqrt{3/4\pi }a_{10}`$. Thus, the expected dipole amplitude is related to the power spectrum by

$$\mathrm{\Delta }^2=3\times \frac{3}{4\pi }|a_{1m}|^2=\frac{9}{4\pi }C_1.$$
(7-1)
Note that there is considerable cosmic variance on this, as it is estimated with only three independent numbers; $`\delta C_1/C_1=(2/3)^{1/2}`$, which corresponds to a 40 % uncertainty in the amplitude of the dipole.

Also shown in Figure 6 is the level of our dipole limit, translated using equation (7-1), which corresponds to $`C_1<3.8\times 10^5`$. While our limit on the dipole limit is at the 95 % C.L., this translates to a 80 % C. L. limit on the variance $`C_1`$ when cosmic variance is included. As discussed above, the 95 % upper limit is four times weaker when cosmic variance is included, $`C_1<1.5\times 10^4`$. Normalized to the ACF, all the theories are easily compatible with the $`C_1`$ bound. The large cosmic variance associated with the dipole makes it difficult to rule out any cosmological models.

With our detected level of clustering, typical theories would predict a dipole amplitude of $`\mathrm{\Delta }0.003`$. While the theories are not in conflict with the dipole range claimed by Scharf et al., they strongly prefer the lower end of their range, even for the most shallow of the models. A dipole amplitude $`\mathrm{\Delta }0.005`$ would be very unlikely from the models, indicating either a significantly higher bias than we find or a model with more large scale power ($`ϵ1.1`$).

### 7.3 The dipole and bulk motions

The dipole of the X-ray background provides another independent test of the large scale X-ray bias through its relation to our peculiar velocity (e.g. see Scharf et al. (2000) and references therein.) Like the gravitational force, the flux of a nearby source drops off as an inverse-square law, so the dipole in the X-ray flux is proportional to the X-ray bias times the gravitational force produced by nearby matter. Our peculiar motion is a result of this force, and is related to the gravitational acceleration by a factor which depends on the matter density.

In typical CDM cosmologies, the dipole and our peculiar velocity arise due to matter at fairly low redshifts ($`z<0.1`$). If this is the case, it is straight forward to relate their amplitudes. Following the notation of Scharf et al., we define $`D^\alpha =𝑑\mathrm{\Omega }I(\widehat{𝐧})\widehat{n}^\alpha =4\pi \overline{I}\mathrm{\Delta }^\alpha /3`$. Using linear perturbation theory, one can show the local bulk flow is

$$v^\alpha =\frac{H_0f}{b_X(0)\rho _X(0)}D^\alpha ,$$
(7-2)
where $`\rho _X(0)`$ is the local X-ray luminosity density, $`b_X(0)`$ is the local X-ray bias and $`f\mathrm{\Omega }_m^{0.6}`$ is related to the growth of linear perturbations (Peebles 1993). From the mean observed intensity (Gendreau et al. 1995) and the local X-ray luminosity density (Miyaji et al. 1994) we find that $`\overline{I}2.4\rho _X(0)c/4\pi H_0`$. This implies that

$$|v|2.4\times 10^5\mathrm{\Delta }\frac{\mathrm{\Omega }_m^{0.6}}{b_X(0)}\mathrm{km}\mathrm{s}^1.$$
(7-3)
This relation was derived by Scharf et al. (2000), though their numerical factor was computed from a fiducial model rather than directly from the observations, as above. In any case, the uncertainty in $`\rho _X(0)`$ is considerable, $`6\times 10^{38}ergs^1Mpc^3<\rho _X(0)<15\times 10^{38}ergs^1Mpc^3`$ (Miyaji et al. 1994), and so is the uncertainty in this relation.

Our maps have bright sources removed, which correspond to nearby sources out to $`60h^1Mpc`$. Thus, we need to compare our dipole limit to the motion of a sphere of this radius centered on us. Typical velocity measurements on this scale find a bulk velocity of $`v_{60}300\pm 100`$ km/s (see Scharf et al. (2000) for a summary.) With our dipole limit, this implies that $`\mathrm{\Omega }_m^{0.6}/b_X(0)>0.24\pm 0.08`$ where the uncertainty in $`\overline{I}/\rho _X(0)`$ is not included. This constraint is independent of cosmic variance issues. While the diameter of the local (Virgo) supercluster is generally considered to be in on the order of $`40h^1`$ to $`50h^1Mpc`$ (e.g., Davis et al. 1980), there is evidence that the overdensity in the Supergalactic plane extends significantly beyond $`60h^1Mpc`$ (Lahav et al. 2000). One might, therefore, suspect that our correction for emission from the local supercluster might effectively remove sources at distances greater than $`60h^1Mpc`$ in that plane. In any case, that correction made very little difference in dipole fits (see §6.2) so our conclusions remain the same.

Note that this limit could potentially conflict with previous determinations by Miyaji (1994) who found $`\mathrm{\Omega }_m^{0.6}/b_X(0)=f_{45}/3.5,`$ where $`f_{45}`$ is the fraction of gravitational acceleration arising from $`R45h^1`$ Mpc. This is consistent only for $`f_{45}1`$, which is larger than is usually assumed ($`f_{45}0.5`$). However, this limit comes from studies of a fairly small sample (16) of X-ray selected AGN and is subject to significant uncertainties of its own.

For typical biases suggested by the observed clustering ($`b_X2.3`$), our constraint suggests a somewhat high matter density, $`\mathrm{\Omega }_m>0.37`$, for $`v_{60}300`$ km/s. This is consistent with the ISW constraint discussed below and also with previous analyses of bulk velocities which tend to indicate higher $`\mathrm{\Omega }_m`$. However, if the bulk velocity is smaller and/or $`\rho _X(0)`$ larger, this constraint is weakened. In addition, we have assumed a constant X-ray bias. If the bias evolves with redshift, then the local value could be considerably smaller which would also weaken this bound.

### 7.4 The Integrated Sachs-Wolfe Effect and $`\mathrm{\Omega }_\mathrm{\Lambda }`$

In models where the matter density is less than unity, microwave background fluctuations can be created very recently by the evolution of the linear gravitational potential. This is known as the late time integrated Sachs-Wolfe (ISW) effect. Photons gain energy as they fall into a potential well, and loose a similar amount of energy as they exit. However, if the potential evolves significantly as the photon passes through, the energy of the photons will be changed, leaving an imprint on the CMB sky. The spectrum is modified most on large scales where the photons receive the largest changes.

The CMB anisotropies created in this way are naturally correlated with the gravitational potential. Thus, we expect to see correlations between the CMB and tracers of the local ($`z2`$) gravitational potential such as the X-ray background (Crittenden & Turok 1996). These correlations are primarily on large scales such as those probed by the HEAO survey.

In an earlier paper, we searched for a correlation between the HEAO maps and maps of the CMB sky produced by COBE. We failed to find such a cross correlation and were able to use our limit to constrain the matter density and the X-ray bias (Boughn, Crittenden & Turok 1998, hereafter BCT). However, translating our measurement into a cosmological bound was ambiguous because the level of the intrinsic structure of the XRB was unknown at the time. With the observation of the X-ray ACF presented here, we are in a position to revisit the cosmological limits implied by these measurements.

To make cosmological constraints, we compare the observed X-ray/CMB cross correlation to those predicted by $`\mathrm{\Lambda }CDM`$ models. As above, we normalize the CMB fluctuations using the band powers of COBE (Bond, Jaffe & Knox 1998) and also normalize the X-ray fluctuations as discussed in §7.1. The cross correlation analysis of BCT was performed with a coarser pixelization ($`2.6^{}\times 2.6^{}`$) than the ACF discussed above. We include this effect by using the numerically calculated pixelization window function. The COBE PSF used was that found by Kneissl & Smoot (1993) and we used a $`2.9^{}`$ FWHM Gaussian for the underlying X-ray PSF (recall that the $`3.04^{}`$ FWHM beam found above includes a $`1.3^{}\times 1.3^{}`$ pixelization.)

The calculation of the HEAO-COBE cross correlation was discussed in BCT and has not changed. The results are shown in Figure 7, along with predictions for three different values of $`\mathrm{\Omega }_\mathrm{\Lambda }`$. While the X-ray bias depends strongly on the Hubble parameter, the predicted cross correlation is only weakly dependent on it, changing only 10% for reasonable values of $`H_0`$. The cross correlation depends primarily on $`\mathrm{\Omega }_\mathrm{\Lambda }`$; no correlation is expected if there is no cosmological constant and the ISW effect increases as $`\mathrm{\Omega }_\mathrm{\Lambda }`$ grows. The error bars in Figure 7 are calculated from Monte Carlo simulations and arise primarily due to cosmic variance in the observed correlation. The error bars are significantly correlated.

The observed correlation is most consistent with there being no intrinsic cross correlation ($`\mathrm{\Omega }_\mathrm{\Lambda }=0.0`$). We set limits by calculating the likelihood of a model relative to this no correlation model. Using the frequentist criterion used in BCT, $`\mathrm{\Omega }_\mathrm{\Lambda }0.65`$ at the 98% C.L., $`\mathrm{\Omega }_\mathrm{\Lambda }0.60`$ at the 95%. C.L. Almost identical limits arise from a Bayesian approach, where the relative likelihoods are marginalized over, assuming a constant prior for $`\mathrm{\Omega }_\mathrm{\Lambda }0`$. Figure 8 shows a one-dimensional slice through the likelihood surface, where only the cross correlation information has been used to calculate the likelihood.

One of the major assumptions we made in interpreting the above result is how the sources of the XRB are distributed in redshift. It is likely that current models of the luminosity function will have to be substantially modified as further deep observations of the sources of the XRB are made. However, as pointed out above, the ISW is relatively insensitive to the exact shape of the redshift distribution of luminosity. If the true distribution includes a substantial fraction of the luminosity at redshifts greater than 1, then the above results will not change dramatically. On the other hand, our constraint on $`\mathrm{\Omega }_\mathrm{\Lambda }`$ is quite sensitive to the value of the bias parameter. If the sources of the XRB should turn out to be unbiased, i.e., $`b_X=1`$, then the constraint on $`\mathrm{\Omega }_\mathrm{\Lambda }`$ could be weakened dramatically. We hasten to add that such a low bias would require that the ACF of Figure 5 be reduced by more than a factor of four, which seems unlikely. Previous determinations of X-ray bias have resulted in a wide range of values, $`1<b_X<7`$ (see Barcons et al. 2000 and references therein). Its clear that firming up the value of $`b_X`$ and determining how it varies with scale and redshift will be required before the ISW effect can be unambiguously interpreted.

The above limit may be compared to what we found from cross correlating COBE with the NVSS radio galaxy survey (Boughn & Crittenden 2002). There we also found no evidence for correlations, and were able to put a 95 % C.L. limit of $`\mathrm{\Omega }_\mathrm{\Lambda }0.74`$, with some weak dependence on the Hubble constant. While the above limit provides important confirmation of that result, it should be noted that these two limits are not entirely independent. Radio galaxies and the X-ray background are, indeed, correlated with each other (Boughn 1998).

An important source of noise in the cross correlation of Figure 7 is instrument noise of the COBE DMR receivers. In addition, the relatively poor angular resolution of the COBE radiometers reduce, somewhat, the amplitude of the ISW signal. Therefore, some improvement can be expected by repeating the analysis on future CMB maps, such as that soon to be produced by NASA’s MAP satellite mission. If such an analysis still finds the absence of an ISW effect, then the current $`\mathrm{\Lambda }CDM`$ model would be in serious conflict with observational data if the X-ray bias can be similarly constrained. On the other hand, a positive detection would provide important evidence about the dynamics of the universe even if the X-ray bias remains uncertain.

## 8 Conclusions

By carefully reconstructing the HEAO beam and analysing its auto-correlation function, we have been able to confirm the presence of intrinsic clustering in the X-ray background. This gives independent verification of the multipole analysis of Scharf et al. (2000) and the level of clustering we see is comparable. The clustering we see is in excess of that predicted by standard cold dark matter models and indicates that some biasing is needed. The amount of biasing required depends on the cosmological model and on how the bias evolves over time; if the bias is constant, typical models indicate that $`b_X2.`$ The biases of galaxies, clusters of galaxies, radio sources, and quasars have yet to be adequately characterized and so whether or not the above X-ray bias is excessive is a question that, for the present, remains unanswered.

We have also confirmed, at the 2-3 $`\sigma `$ level, the detection of the Compton-Getting dipole in the X-ray background due to the Earth’s motion with respect to the rest frame of the CMB. However, we have been unable to confirm the presence of an intrinsic dipole in the XRB and have actually been able to exclude a significant part of the range reported by Scharf et al. (2000). While our dipole limit is still too small to conflict with any of the favored CDM models, combining our dipole limit with observations of the local bulk flow enable us to constrain $`\mathrm{\Omega }_m^{0.6}/b_X(0)>0.24`$. For constant bias models, this suggests a relatively large matter density, as is also seen in for other velocity studies; however, the uncertainty in this limit is still considerable.

With the observed X-ray clustering, large $`\mathrm{\Lambda }CDM`$ models predict a detectable correlation with the cosmic microwave background arising via the integrated Sachs-Wolfe effect. That we have not observed this effect suggests $`\mathrm{\Omega }_\mathrm{\Lambda }<0.60`$. This is beginning to conflict with models preferred by a combination of CMB, LSS and SNIA data (e.g., de Bernardis et al. 2000 & Bahcall et al. 1999).

This work gives strong motivation for further observations of the large scale structure of the hard X-ray background. Better measurements of the full sky XRB anisotropy are needed, as is more information about the redshift distribution of the X-ray sources. This will be essential for cross correlation with the new CMB data from the MAP satellite and to bridge the gap between the CMB scales and those probed by galaxy surveys such as 2-dF and SDSS.

We would like to acknowledge Keith Jahoda who is responsible for constructing the HEAO1 A2 X-ray map and who provided us with several data-handling programs. We also thank Neil Turok for useful discussions, Ed Groth for a variety of analysis programs, and Steve Raible for his help with some of the analysis programs. RC acknowledges support from a PPARC Advanced Fellowship. This work was supported in part by NASA grant NAG5-9285.


text:
# Pattern recognition on a quantum computer

## I Introduction

Pattern recognition is one of the basic problems in artificial intelligence, see e.g. . For example, generally a short look at a picture like the one in Fig. 1 suffices for the human brain to spot the region with the pattern. However, it is a rather non-trivial task to accomplish the same performance with a computer – in particular if the orientation and the structure of the pattern are not known a priori and it is not perfect (in contrast to the one in Fig. 1).

Besides the detection and localisation of pattern (for example identifying seismic waves in the outputs of seismographs) the comparison and matching of the observed pattern to a set of templates (such as face recognition) is another interesting question. Usually these problems are solved with special classifiers, such as neuronal networks or Fourier analysis, etc., cf. .

The specific properties of the task of pattern recognition (one may consider many combinations simultaneously and is interested in global features only) give raise to the hope that quantum algorithms may be advantageous in comparison with classical (local) computational methods (with a unique entry).

During the last decade the topic of quantum information processing has attracted increasing interest, see e.g.  for a review. It has been shown that quantum algorithms can be enormously faster than the best (known) classical techniques: Shor’s factoring algorithm , which exhibits an exponential speed-up relative to the best known classical method; Grover’s search routine  with a quadratic speed-up; and several black-box problems , some of which also exhibit an exponential speed-up; etc.

In the following a quantum algorithm for the detection, identification, and localisation of certain patterns in an otherwise (macroscopically) unstructured data set is presented. It turns out that this method is exponentially faster than its classical counterpart too. Furthermore, it outperforms the (also extremely fast) method of optical filtering in terms of accuracy.

The advantages of using quantum memories and computers for the aforementioned task of template matching (which is somewhat different from pattern detection/localisation) have been discussed in . Note, however, that the necessity of loading the complete data set into a quantum memory may represent a drawback (cf. the next Sections). In Ref.  an algorithm for data clustering (in pattern recognition problems) is developed, which is based on/inspired by principles of quantum mechanics – but does not involve quantum computation.

## II Description of the Problem

Let us consider a rectangular $`N\times M`$ array of unit cells which are either absorptive (black) or reflective/transparent (white), cf. Fig. 1. In the following we shall assume that these cells are perfectly absorbing or reflecting/transmitting, respectively, but reasonable deviations from this idealised behaviour resulting in finite absorption, reflection, and transmission coefficients do not alter the following considerations.

The white cells are distributed with a roughly homogeneous density $`\varrho <1`$ (for example $`\varrho =1/2`$) and will later be called points for brevity, i.e., the $`N\times M`$ array contains $`P=\varrho NM`$ points. A small fraction $`\chi `$ of these points (say $`\chi =1/10`$) forms a pattern in a connected (but not necessarily rectangular) region of the size $`\chi NM`$, cf. Fig. 1.

In contrast to Fig. 1 the pattern does not need to be perfect – average symmetries are sufficient, see Section V below. For simplicity we restrict our consideration to linear (but again not necessarily rectangular) patterns. I.e., the patterns are supposed to be (approximately) invariant under at least two symmetry transformations described by global translations into different directions. Geometrically speaking, the angles within the pattern do not change, think of, for example, a set of parallel and equidistant lines or a periodic repetition of small elements as in some wall papers, etc.

Let us suppose that we know $`N`$, $`M`$, and $`\varrho `$, for these quantities can easily be measured having at hand the $`N\times M`$ array of unit cells (which might be some sensitive nano-device, for example) – but we neither know the size $`\chi `$ of the pattern (or whether there is a pattern at all) nor its structure and orientation (except that it is linear). The task is to find an algorithm for extracting this information.

In principle, we may find out the position of all points (white cells) by shining appropriately focused light beams on the array and measuring the reflection or transmission. However, the array is also assumed to be very sensitive and each absorbed photon causes a certain amount of damage – similar to the Elitzur-Vaidman problem (detection without destruction), cf. . Therefore, the number of incident photons should be as small as possible.

At the same time, we wish to obtain the characteristic parameters of the pattern with maximally attainable accuracy and minimal effort (i.e. number of subsequent operations). In order to cast the above requirements into a well-defined complexity theoretic form we consider the limit of very large arrays $`N,M1`$. Furthermore, we assume $`N=2^n`$ and $`M=2^m`$ with integers $`n,m`$ allowing for a binary representation. (Otherwise we may enlarge the array accordingly or consider a part of it only.)

## III Data Processing

It is probably most convenient to view the data set as a (quantum) black box

$`:\left[\begin{array}{c}|x\\ |y\\ |0\end{array}\right]\left[\begin{array}{c}|x\\ |y\\ |f(x,y)\end{array}\right],`$ (7)
where the input state encodes the coordinates $`x`$ and $`y`$ of a potential point (a white cell) in the array as $`n`$\- and $`m`$-qubit strings, respectively, together with a third one-qubit register $`|0`$ needed for unitarity. The output function $`f(x,y)`$ assumes the value 1 if there is a point at these coordinates and 0 if not.

As a possible physical realization one might imagine a configuration like the following: a focused light beam passes $`n+m`$ controlled refractors (e.g. non-linear Kerr media) which change its direction by definite angles $`\phi _j`$ if the control qubit is $`|1`$ and do not affect it otherwise. For suitably chosen angles ($`\phi _j^{x,y}=\phi _0^{x,y}/2^j`$ with $`j`$) the final direction of the beam encodes the position $`(x,y)`$ on the $`N\times M`$ array if the digits of the coordinates $`|x,|y`$ are inserted as the control qubits. Shining the so directed light beam (which may consist of only one photon) through an aperture mask like Fig. 1 on a detector reproduces the action of the black box in Eq. (7).

Note that, in this realization, it is not necessary to load the complete (classical) information of the array into a quantum memory. This would slow down the whole process drastically and hence represent a serious caveat. (The same problem limits the region of applicability of Grover’s quantum search procedure, for example.) In addition, it is hard to see how this could be done without shining a relatively large number of photons on the array and thereby destroying it, cf. Section II.

Moreover, the involved number ($`n+m`$) of devices (refractors) is very small in this case. Each refractor acts roughly similar to a controlled swap or a switch gate

$`𝒮𝒲:\left[\begin{array}{c}|\alpha \\ |\beta \\ |0\end{array}\right]\left[\begin{array}{c}|\alpha \\ |\neg \alpha \beta \\ |\alpha \beta \end{array}\right],`$ (14)
with $`\alpha ,\beta =0,1`$; but the series connection of these refractors allows for a very efficient data processing.

## IV Quantum Algorithm

Now we may apply the well-known trick of inquiring all possible values of the coordinates $`(x,y)`$ in only one run of the black box (quantum parallelism). To this end we prepare a state as the superposition of all possibilities by using the Hadamard gate $``$. For a single qubit in the $`|0,|1`$ basis the (unitary) Hadamard gate $``$ acts as $`|0=(|0+|1)/\sqrt{2}`$. By multiple application of $``$ and running the black box (only once) we arrive at the desired superposition

$`\left[\begin{array}{c}^{(n)}|0^{(n)}\\ ^{(m)}|0^{(m)}\\ |0\end{array}\right]={\displaystyle \frac{1}{\sqrt{NM}}}{\displaystyle \underset{x=0}{\overset{N1}{}}}{\displaystyle \underset{y=0}{\overset{M1}{}}}\left[\begin{array}{c}|x\\ |y\\ |f(x,y)\end{array}\right].`$ (21)
Now measuring the third register $`|f`$ and obtaining 1 prepares the state $`|\mathrm{\Psi }`$ as a superposition of the coordinates $`|x`$ and $`|y`$ of all points. Assuming an ideal black box, the outcome $`f=0`$ would just imply the complementary set $`\varrho 1\varrho `$. However, in the presence of absorbing units as described in Section II, the resulting entanglement with the state of the absorptive cells would destroy the coherence completely in the case $`f1`$.

It will be advantageous to reorganise the array by dividing it into $`M`$ rows of length $`N`$ and combining them all to one string of length $`S=NM`$. The coordinate of a given point is now one $`n+m=s`$-digit binary number $`z=x+Ny`$ (instead of two numbers $`x`$ and $`y`$). The corresponding quantum state is simply given by $`|z=|x|y`$. In terms of this representation the quantum state $`|\mathrm{\Psi }`$ prepared by the measurement of $`f=1`$ reads

$`|\mathrm{\Psi }={\displaystyle \frac{1}{\sqrt{\varrho S}}}{\displaystyle \underset{l=1}{\overset{\varrho S}{}}}|z_l,`$ (22)
where $`0z_lS1`$ denotes position of $`l`$-th point (as a $`s`$-digit binary number).

The next basic part of the quantum algorithm is the application of the quantum Fourier transform (QFT). It acts on a basis element like $`|z=|110100\mathrm{}`$ as

$`𝒬𝒯:|z{\displaystyle \frac{1}{\sqrt{S}}}{\displaystyle \underset{k=0}{\overset{S1}{}}}\mathrm{exp}\left(2\pi i{\displaystyle \frac{zk}{S}}\right)|k.`$ (23)
Hence the superposition state $`|\mathrm{\Psi }`$ in Eq. (22) will be transformed into

$`𝒬𝒯|\mathrm{\Psi }={\displaystyle \underset{k=0}{\overset{S1}{}}}{\displaystyle \underset{l=1}{\overset{\varrho S}{}}}{\displaystyle \frac{1}{S\sqrt{\varrho }}}\mathrm{exp}\left(2\pi i{\displaystyle \frac{z_lk}{S}}\right)|k.`$ (24)
Assuming a distribution of points $`z_l`$ without any (macroscopic) pattern (e.g. purely random) there will be no privileged values of $`k`$ (except $`k=0`$) and the measurement of $`k>0`$ yields just noise. However, the presence of a pattern within the data set introduces a typical length scale and thus leads to peaks of the factor in front of $`|k`$ at certain values of $`k`$ – which hence can be used as an indicator, see the next Section. In this way the QFT efficiently solves the problem of feature selection – i.e., extracting a small amount of relevant quantities (such as wave-numbers) from a large data set.

## V Pattern localisation

The task of pattern recognition does not only include the mere detection of a pattern but also its localisation and classification. The comparison with a given set of templates will not be discussed here, see e.g. . The next step is to extract informations about the pattern from the peaks in the measurements of $`k`$ – in close analogy to the reconstruction of the probe structure from the Laue diagram in diffraction experiments.

Consider, for example, a simple pattern consisting of parallel lines like the one in Fig. 1. In this case the basic quantities are the distance $`D=\mathrm{const}`$ of the lines as well as their orientation as described by the (constant) angle $`\pi /2\vartheta \pi /2`$. Here $`\vartheta `$ denotes the deviation of the line from a vertical one, i.e., after going down $`R`$ rows the sequence is shifted by $`\mathrm{tan}\vartheta R`$ columns to the right. So the points $`z`$ marking the centre of a particular line are given by

$`z=z_0+[(N+\mathrm{tan}\vartheta )]_{\mathrm{integer}}.`$ (25)
Note that (in contrast to Fig. 1) the lines do not need to be perfect – it is sufficient if, in average, the density of points within a line-width of, say, $`D/2`$ deviates by a finite amount $`\mathrm{\Delta }\varrho `$ (e.g. $`\mathrm{\Delta }\varrho =1/4`$) from the mean $`\varrho `$.

According to Eq. (24) every row of the pattern generates peaks at

$`k=\left[\mathrm{cos}\vartheta {\displaystyle \frac{S}{D}}\pm 𝒪\left({\displaystyle \frac{M}{D\sqrt{\chi }}}\right)\right]_{\mathrm{integer}},`$ (26)
with the second term denoting their width. Both, the position and the width of the peaks can be obtained from the associated Laue function $`𝔏(\xi ,\kappa )=\mathrm{sin}^2(\pi \xi \kappa )/\mathrm{sin}^2(\pi \kappa )`$ with $`k=\kappa \mathrm{cos}\vartheta S/D`$ and $`\xi =𝒪(N\sqrt{\chi })`$ in this case.

However, the sum of all rows interferes constructively only if $`k`$ is fine-tuned according to

$`k=\left[{\displaystyle \frac{N\mathrm{tan}\vartheta }{N}}M\pm 𝒪\left({\displaystyle \frac{1}{\sqrt{\chi }}}\right)\right]_{\mathrm{integer}},`$ (27)
which again can be obtained from the associated Laue function with now $`\kappa =k(N+\mathrm{tan}\vartheta )/S`$ and $`\xi =𝒪(M\sqrt{\chi })`$. The strongest peaks in the measurements of $`k`$ occur for values which satisfy both conditions (26) and (27) simultaneously. Accordingly, the wave-numbers of those potential peaks read

$`k\left[\left(\mathrm{cos}\vartheta {\displaystyle \frac{S}{D}}\mathrm{sin}\vartheta {\displaystyle \frac{M}{D}}\right)\right]_{\mathrm{integer}},`$ (28)
where the corresponding width/uncertainty has been omitted.

However, for large enough $`D`$, not every peak in Eq. (26) will contain wave-numbers matching Eq. (27) in general. The condition for this to happen is that the integer ($``$) in Eq. (26) multiplied by $`\mathrm{cos}\vartheta N/D`$ is again close to another integer – the one in Eq. (27) – within an accuracy of $`𝒪(1/[D\sqrt{\chi }])`$.

Therefore, not all the $`k`$-values in Eq. (28) do necessarily represent large peaks – the first few of them may be suppressed. On the other hand, the larger $`D`$ is the more $`k`$-values of potential peaks in Eq. (28) are contained in the interval $`0<k<S`$. Consequently, from the number $`D/\mathrm{cos}\vartheta `$ of potential peaks in Eq. (28) there must be at least a few $`𝒪(1/\sqrt{\chi })`$ which match both conditions (26) and (27).

Determining the largest common factor of all the wave-numbers of the peaks (within the given accuracy) we obtain a value for the expression in Eq. (28) or integer multiples of it. Unfortunately, this information alone is not sufficient for extracting $`D`$ and $`\vartheta `$. To this end we may simply transpose the array (e.g. Fig. 1) by interchanging rows and columns $`NM`$ and run the same algorithm again. Since transposing corresponds to $`\vartheta \pi /2\vartheta `$ the wave-numbers of the peaks are now

$`k^{}\left[\left(\mathrm{sin}\vartheta {\displaystyle \frac{S}{D}}\mathrm{cos}\vartheta {\displaystyle \frac{N}{D}}\right)\right]_{\mathrm{integer}}.`$ (29)
Combining the possible values for $`D/\mathrm{cos}\vartheta `$ from Eq. (28) with the ones for $`D/\mathrm{sin}\vartheta `$ from Eq. (29) we obtain approximate candidates for $`D`$ and $`\vartheta `$. Comparison with the fine-tuning conditions such as Eqs. (26) and (27) as well as the knowledge of which peaks are suppressed and which are not allows us to extract the actual values of $`D`$ and $`\vartheta `$ with high (in fact, maximally attainable) precision $`𝒪(1/\sqrt{\chi })`$.

The height of the peaks can be estimated by means of Eq. (24). In the resonance case the sum includes $`S\chi \mathrm{\Delta }\varrho `$ constructively interfering addends which lead to an amplitude of order $`𝒪(\chi \mathrm{\Delta }\varrho /\sqrt{\varrho })`$. Thus the probability $`p`$ of measuring the peaks in Eqs. (28) and (29) is given by

$`p=𝒪\left({\displaystyle \frac{(\chi \mathrm{\Delta }\varrho )^2}{\varrho }}\right),`$ (30)
i.e. independent of $`N`$ and $`M`$ – and therefore drastically enhanced over the (random) noise.

Consequently, if a number $`\mathrm{\Omega }`$ of measurements yields one or more pronounced peaks besides $`k=0`$ then there exists a pattern larger than $`\chi _{\mathrm{min}}=𝒪(1/\sqrt{\mathrm{\Omega }})`$ and otherwise not (at least with a very high probability). Quite reasonably, the smaller the pattern, i.e. $`\chi `$, the longer one has to search.

After having solved the feature selection problem efficiently by the quantum algorithm the remaining analysis (peak finding and stopping criteria, etc.) of a small (independent of $`N`$ and $`M`$) amount of measured wave-numbers can be accomplished by a classical algorithm.

In this way one can determine the size of the pattern $`\chi `$ by the frequency of measuring the peaks at $`k`$ and $`k^{}`$ (and their width). Its structure, i.e. the values of $`D`$ and $`\vartheta `$, can be inferred from the location of the peaks.

Having found the parameters $`D`$, $`\vartheta `$, and $`\chi `$ of the pattern it can be localised easily – for example by dividing the total $`N\times M`$ array into smaller pieces (according to $`\chi `$) and running the same quantum algorithm again in the smaller domains.

More complicated (but still linear) patterns, such as a regularly recurring pictures***Again, these pictures do not need to be perfect – average features are sufficient. (like in many wall papers), possess more than one characteristic angles $`\vartheta `$ in general and therefore generate a richer peak structure – but the main idea remains the same.

## VI Complexity analysis

Let us estimate the size of the proposed algorithm, i.e. the number of involved computational steps, and compare it with the classical method, in the limit $`S\mathrm{}`$ while $`\varrho `$, $`\mathrm{\Delta }\varrho `$, and $`\chi `$ remain finite.

In view of Eq. (30) we need only a few $`𝒪(S^0)`$ queries of the black box in order to find a pattern of a given size with high probability. Clearly, this is not possible with any classical algorithm – demonstrating the advantage of the global quantum computation over the local (only one point at the time) classical technique. Since the number of queries of the black box corresponds to the total amount of photons shining on the array, the quantum algorithm causes less damage (cf. Section II) than any classical method, see also .

Given the explicit physical realization of the black box described in Section III it is also possible to compare the total number of fundamental manipulations. For the preparation of the initial state in Eq. (21) one has to apply the Hadamard gate $`m+n=s=\mathrm{log}_2S`$ times. The black box itself involves about the same number of operations. The quantum Fourier transform (QFT) in Eq. (23) requires $`𝒪(\mathrm{log}_2^2S)`$ steps for obtaining the exact result and is even faster $`𝒪(\mathrm{log}_2S)`$ if we measure  the outcome immediately afterwards – as it is the case here.

In contrast, the best known classical algorithm, the fast Fourier transform (FFT), implements $`𝒪(S\mathrm{log}_2S)`$ operations and is therefore exponentially slower. Note that, since we do not know the typical “wave-numbers” $`k`$ associated with the pattern a priori, we would have to calculate the FFT for a large number $`𝒪(S)`$ of possible values of $`k`$ – whereas the QFT accomplishes all this simultaneously and automatically gives us the values $`k`$ with the largest amplitudes in average measurements.

Unfortunately, it cannot be excluded here that perhaps a classical algorithm exists which is better than the FFT and may compete with the proposed quantum algorithm (though not in the number of queries of the black box). But since the processing of the coordinates of only one single point already requires $`𝒪(\mathrm{log}_2S)`$ operations, one would have to find the pattern by considering a few $`𝒪(S^0)`$ points in order to outrun the quantum computer – which is apparently not possible.

Nevertheless, in certain situations – e.g. for perfect lines with $`D=𝒪(1)`$ such as in Fig. 1 – it is possible to design an appropriate classical algorithm which determines $`\vartheta `$ by using only $`𝒪(\mathrm{log}_2^qS)`$ points with $`q1`$, which requires $`𝒪(\mathrm{log}_2^{q+1}S)`$ computational steps. In this case the speed-up is merely polynomial.

In the more general case, however, where $`D`$ can be very large $`D1`$ and the lines are not perfect, it is really hard to see how one might extract basically the same information as the FFT in (polynomially) logarithmic time classically. (An $`𝒪(\sqrt{S})`$ algorithm, for example, would also be exponentially slower than the QFT.)

Assuming that there is indeed no such classical algorithm (or, that the set of patterns for which the Fourier transform is the best classifier is not empty) the problem under consideration represents another example for the (conjectured) exponential speed-up of quantum computation – based on the power of QFT for problems related to (quasi) periodical structures (which is also the basic ingredient for Shor’s algorithm ; though in that case the periodicity is exact – in contrast to the situation considered here).

Of course, this speed-up has only been possible since it was not necessary to load the complete array into a quantum memory (cf. ) – this would have involved about $`𝒪(S)`$ operations and thereby lead to a drastic (exponential) slow-down.

## VII Summary and Outlook

In summary, quantum algorithms are capable of solving certain problems of pattern recognition (i.e. detection, localisation, and classification) besides template matching  much faster $`𝒪(\mathrm{log}_2S)`$ than their classical counterparts .

Although this has been demonstrated explicitly in this article for line patterns only, the basic idea applies to more difficult (but still linear) patterns as well. (In some sense, this idea arises from the often successful approach to copy the elegant solutions which nature reveals to us – such as the possibility of distinguishing a crystal from an amorphous material via X-ray diffraction or the method of optical filtering, see the next Section.) The investigation of non-linear patterns, such as a set of concentric circles, is apparently more involved and probably requires adapted methods.

Together with the findings in Refs.  the results of the present article give raise to the hope that quantum algorithms are also advantageous for more general pattern recognition problems.

## VIII Optical filtering

Interestingly, the manipulations involved in the proposed quantum algorithm – apart from the physical realization of the black box itself – can be accomplished (at least in principle) with present-day optical devices: Hadamard gates as well as the calculation of the quantum Fourier transform with subsequently measuring the outcome can be realized using beam splitters and classically controlled phase shifters, cf. . This observation leads to the question of whether one could achieve a similar performance with purely optical techniques.

Indeed, the method of optical filtering reproduces some key features of the proposed quantum algorithm. Shining a plane wave with an appropriate wave-number on an aperture mask like Fig. 1 the far field diffraction amplitudes are given by the Fourier transform of the object (e.g. Fig. 1) in terms of the perpendicular wave-number. Using an ordinary convex lens one may convert these wave-numbers into positions in the focal plane of the lens, see e.g. .

In this way the described apparatus effectively calculates the desired Fourier transform. However, achieving the same accuracy as the proposed quantum algorithm, i.e. $`𝒪(\mathrm{log}_2S)`$ digits for $`\vartheta `$ and $`D`$, would require exponential precision and hence exponential effort: number of detectors in the focal plane, etc. Another problem is the fact that $`D`$ is not known a priori and may vary over several orders of magnitude – which makes it difficult to select a suitable wave-number for the incident light.

These obstacles are caused by the main difference between optical filtering and the proposed quantum algorithm. In optical filtering, the relevant quantities (such as wave-number, position in the focal plane, $`\vartheta `$, and $`D`$) are directly, i.e. linearly, related to each other – whereas the quantum algorithm employs the digital representation and therewith outperforms the former method.

On the other hand, if we happen to know the order of magnitude of $`D`$ in advance and would be willing to settle for a limited accuracy of only a few $`𝒪(S^0)`$ digits, we may detect the pattern with optical filtering by using only a few $`𝒪(S^0)`$ photons. Although much less powerful, i.e. accurate, this method would be significantly faster than the proposed quantum algorithm, which also uses only a few photons shining on the pattern – but it requires $`𝒪(\mathrm{log}_2S)`$ photons (or, more generally, qubits) for the subsequent data analysis (QFT, etc.). (This enhancement in speed – although at a certain cost – reflects the fact that a quantum field theoretical object such as a photon has more degrees of freedom than just one single qubit.)

## IX Appendix

If there were no absorptive cells in the array at all but only (perfectly) reflective (white) and transparent (black) ones, one could (in principle) realize the following generalisation of the black box in Eq. (7)

$`:\left[\begin{array}{c}|x\\ |y\\ |\alpha \end{array}\right]\left[\begin{array}{c}|x\\ |y\\ |\alpha f(x,y)\end{array}\right],`$ (37)
with $`\alpha =0,1`$. Here $``$ denotes summation modulo 2, i.e., $`10=01=1`$ and $`00=11=0`$. In this case one may improve the quantum algorithm by sending the superposition state in Eq. (21) with the third register being $`(|0|1)/\sqrt{2}`$ instead of $`|0`$ to the black box. The third register does not change during this procedure and the resulting state encodes the information about the points in the array in the phases ($`+1`$ or $`1`$) instead of the amplitudes ($`1`$ or $`0`$)

$`|\mathrm{\Psi }={\displaystyle \frac{1}{\sqrt{S}}}{\displaystyle \underset{z=0}{\overset{S1}{}}}(1)^{f(z)}|z.`$ (38)
Assuming $`\varrho =1/2`$, the quantum Fourier transform of this state has certain advantages over the one in Eq. (22) – one gets rid of the (useless) peak at $`k=0`$ and enhances the probabilities of the other peaks by a factor of 2. Unfortunately, it is hard to see how one might be able to exploit this advantage of the modified black box in the presence of absorbing units.

## Acknowledgements

The author acknowledges valuable discussions with L. D’Afonseca, D. Curtis, S. Fuchs, Y. Gusev, D. Meyer, N. Pippenger, S. Popescu, G. Schaller, C. Trugenberger, and B. Unruh. This work was supported by the Alexander von Humboldt foundation and by the Natural Science and Engineering Research Council of Canada.