text:
# Variable stars in the Magellanic Clouds: II. The data and infrared properties

## 1 Introduction

Because of their proximity and comparatively well-known distances, the Large and Small Magellanic Clouds (LMC and SMC, respectively) are the ideal places to study stellar evolution. To search for the gravitational lensing events, several projects are now underway monitoring the sky toward the Magellanic Clouds and also the Galactic bulge, where there are a large number of background stars that are potential targets for microlensing. As the natural by-products of these surveys, many variable stars were newly found. The Optical Gravitational Lensing Experiment (OGLE) project is one of such surveys and its $`I`$ band time-series data in the Magellanic Clouds (Żebruń et al. 2001) obtained during four years of OGLE-II run (Udalski, Kubiak & Szymanski 1997; January 1997 - November 2000) is now available over the Internet (OGLE homepage; http://sirius.astrouw.edu.pl/ogle/).

To detect dust-enshrouded variables that have possibly escaped from the ongoing/previous optical projects, we started the $`JHK`$ monitoring survey toward the Large and Small Magellanic Clouds using the InfraRed Survey Facility (IRSF) at the South African Astronomical Observatory Sutherland station. The IRSF consists of a dedicated 1.4m telescope to which is attached a near infrared (NIR) camera SIRIUS, which can observe the sky in the three wave bands ($`JHK_s`$) simultaneously. The filter characteristics are shown in table 1. The field of view of this system is about 7.7$`\times `$7.7 with a scale of 0.453′′/pixel. Details of the instrument are found in Nagashima et al. (1999) and Nagayama et al. (2002). This campaign was initiated in December 2000, and so far, many dust-enshrouded variables were found and their light variation data has been steadily accumulating (see Ita et al. 2002 for the first results).

In the previous paper (Ita et al. 2004a, hereafter referred to as Paper I), we cross-identified the OGLE data and the single-epoch SIRIUS $`JHK`$ data from the monitoring survey, and studied the pulsation properties and metallicity effects on period-$`K`$ magnitude relations by comparing the variable stars in the LMC and SMC. In this paper, we present the data of the variable stars in the Magellanic Clouds and discuss their infrared properties.

## 2 DATA

The total areas covered by the SIRIUS variable star survey are three and one square degrees in the LMC and SMC, respectively. These areas are divided into 27(9) regions of 20$`\times `$20 meshes in the LMC(SMC). Tables 2 and 3 define the central coordinates of them. Each of the 20$`\times `$20 regions is further subdivided into nine sub regions due to the field of view of the SIRIUS, which is about 7.7$`\times `$7.7.

We cross-identified OGLE variables in the Magellanic Clouds (Żebruń et al. 2001) with the SIRIUS NIR sources that have been detected at least two of the three ($`JHK`$) wave bands, and then determined their pulsation periods by using the Phase Dispersion Minimization (PDM) technique (Stellingwerf, 1978). Details of the cross-identifications and period findings are described in Paper I. We did not analyze multi-periodic stars (e.g., Bedding et al. 1998) and/or variable stars that show too complex light curves in the phase space (see the bottom panel of figures 2 and 3) to find a predominant period. We made two catalogs presenting data of variable stars in the LMC and SMC. They contain the following information: OGLE name, pulsation period in days, statistical parameter $`\theta `$ calculated by the PDM, pulsation amplitude ($`\mathrm{\Delta }I=I_{\text{max}}I_{\text{min}}`$), intensity mean $`I`$ magnitude $`<I>`$, $`JHK`$ magnitudes and positional difference $`r`$ between the SIRIUS coordinate and the OGLE coordinate in arcsec. The $`\theta `$ is a measure of the regularity of the light variation, being near 0 for the regular variation and near 1 for the irregular variation.

Table 4 is a sample that shows the first five records of the LMC catalog. The full version of the data, including the SMC catalog is available in the on-line version of this paper. In cases the $`JHK`$ measurements are saturated or below the detection limit, the corresponding columns contain the value 99.999. The $`JHK`$ magnitudes in the catalog are referred to the Las Campanas Observatory (LCO) system ones based on observations of a few dozen stars from Persson et al. (1998) and are not corrected for the interstellar absorption. We used the following colour equations

$$J_{\text{LCO}}=J+\left(\begin{array}{c}\hfill 0.007\pm 0.002\\ \hfill 0.005\pm 0.002\\ \hfill 0.003\pm 0.002\end{array}\right)+$$
(4)
$$\left(\begin{array}{c}\hfill 0.016\pm 0.011(JH)\\ \hfill 0.009\pm 0.005(JK)\\ \hfill 0.000\pm 0.000(HK)\end{array}\right)$$
(8)
$$H_{\text{LCO}}=H+\left(\begin{array}{c}\hfill 0.001\pm 0.002\\ \hfill 0.002\pm 0.002\\ \hfill 0.000\pm 0.002\end{array}\right)+$$
(12)
$$\left(\begin{array}{c}\hfill 0.001\pm 0.000(JH)\\ \hfill 0.004\pm 0.000(JK)\\ \hfill 0.004\pm 0.000(HK)\end{array}\right)$$
(16)
$$K_{\text{LCO}}=K+\left(\begin{array}{c}\hfill 0.001\pm 0.004\\ \hfill 0.001\pm 0.004\\ \hfill 0.005\pm 0.004\end{array}\right)+$$
(20)
$$\left(\begin{array}{c}0.002\pm 0.000(JH)\\ 0.002\pm 0.000(JK)\\ 0.041\pm 0.004(HK)\end{array}\right)$$
(24)
to transform the IRSF instrumental magnitudes to the LCO system based ones. The $`JK`$ ones were usually used, but $`JH`$($`HK`$) ones were employed if the $`K`$($`J`$) magnitudes were unavailable. Note that the SIRIUS measures the $`K_s`$ magnitudes and they were converted to the LCO $`K`$ magnitudes.

To enhance the image quality, we stacked the top 10 best seeing images111These 10 images were taken on different days and hence under the different conditions, and a single image comprises 10 dithered 5 sec exposures. (typically the seeing ranges from about 0.9′′ to 1.2′′ at $`K_s`$) that we have been collecting in the ongoing SIRIUS monitoring survey. We used the ISIS.V2.1 package (Alard & Lupton 1998; Alard 2000) to build a composite image that comprises 100 dithered 5 sec exposures. Photometry was performed on the composite image with DoPHOT (Schechter, Mateo & Saha 1993), and then, the measured magnitudes were calibrated with the single-epoch photometry data by matching the magnitudes of the non-variable stars. Eventually, the photometry has a signal-to-noise ratio (S/N) of about 10 at 17.40, 17.38 and 16.63 mag in $`J`$, $`H`$ and $`K`$, respectively. Also, traditional experiments of adding artificial stars to the composite images revealed that the 90% completeness (detection probability) limits at $`J`$, $`H`$ and $`K`$ are about 17.25, 17.22 and 16.45 mag, respectively (Ita 2004b).

## 3 Discussion

In the following discussions, we use the $`JHK`$ magnitudes that are corrected for the interstellar absorption based on the relations in Koornneef (1982), assuming $`R=`$ 3.2. We adopted ($`A_J`$, $`A_H`$, $`A_K`$) $`=`$ (0.129, 0.084, 0.040) and (0.082, 0.053, 0.025), corresponding to the total mean reddening of $`E_{BV}=`$ 0.137 and 0.087 as derived by Udalski et al. (1999) for the OGLE’s observing fields in the LMC and SMC, respectively. The reddening of the Magellanic Clouds is still somewhat controversial (e.g., Westerlund 1997), and it is certain that this type of statistical average approach can not account for individual corrections. However, the adopted reddening should not affect any of the conclusions of this paper. The coefficients we calculated in equations 25 to 28 depend on reddening, but the effects should be small.

### 3.1 Classification of the variable stars on the period-$`K`$ magnitude plane

Wood et al. (1999) discovered that variable red giants in the LMC form parallel sequences in the period-$`K`$ magnitude plane and suggested that these sequences can be interpreted as the differences in the pulsation modes (Wood 2000).

In Paper I, we classified variable stars into nine (LMC) and eight (SMC) prominent groups based on their locations on the period-$`K`$ magnitude plane. Refer to Paper I for the details of the grouping. For the easier reading and completeness of this paper, we show the period-$`K`$ magnitude diagram with classification boxes in figure 1, and also for conciseness, we tabulated the colour mapping chart in table 5. Stars outside the classification boxes are represented by black tiny dots. Throughout this paper, we use the same labels and colours for each group. In the LMC, there is a clump of variables around $`\mathrm{log}P`$ $``$0.1 and $`K`$ 15.0. This is a group of RR Lyrae variables, which we do not analyze in this paper.

Roughly speaking, five types of variable stars constitute the majority of the catalog; Cepheids, Miras, Semi-regulars, Irregular variables and Eclipsing binaries. However, telling Semi-regulars from Mira variables is rather difficult and there are not necessarily deep physical criteria. Several authors (e.g., Alard et al. 2001; Cioni et al. 2001) use a simple criterion that is based on a certain limiting pulsation amplitude to separate Semi-regulars and Miras. Meanwhile, Kiss & Bedding (2003, 2004) showed that there is a good correlation between the amplitude and mode of pulsation. In this paper, we do not separate Semi-regulars and Miras explicitly. Instead, we distinguish “regularly pulsating variables, ($`\theta `$ 0.55)” from “less regularly pulsating variables, ($`\theta >0.55`$)” relying on the parameter “$`\theta `$”. In figures 2 and 3, we show the representative light curves of two variable stars on sequence $`C`$, having similar periods ($``$109 and $``$126 days) and the same amplitudes ($`\mathrm{\Delta }I`$0.490 mag) but different $`\theta `$s.

### 3.2 Colour-magnitude and colour-colour diagram

The NIR data from the SIRIUS survey enabled us to study the infrared properties of the OGLE variables. Figure 4 and 5 show the NIR colour-magnitude and colour-colour diagram of the OGLE variables. In the inset of the figure 4, we show the colour-magnitude diagram of the SIRIUS data (including non-variables), closing-up around the tip of the first giant branch (TRGB). By comparing the insets and the main diagrams, it is clear that the stars of group $`A^{}`$ and $`B^{}`$ accumulate at the exact location of the TRGB (Ita et al. 2002; Kiss & Bedding 2003, 2004; Ita et al. 2004a).

Most of the stars from group $`D`$ are found at the place a bit brighter than the TRGB. Wood et al. (1999) identified the sequence $`D`$ with suspected binaries, and Wood et al. (2004) discussed the possible explanations for the $`D`$ variables. On the other hand, some of the $`D`$ variables are very red ($`JH>1.8`$, $`HK>1.5`$ and $`JK>3.2`$) and relatively bright (11.0 $`K`$ 12.5), properties associated with carbon-rich stars and dusty AGB stars (Nikolaev & Weinberg 2000). In the present sample, 14 out of 471 (6 out of 71) $`D`$ stars in the LMC (SMC) have these properties. A possible explanation for these red stars in the group $`D`$ is that, these stars could in fact be very dusty AGB stars that are subjected to severe circumstellar extinctions, even in the $`K`$ band. Whitelock et al. (2003) studied obscured variables in the LMC and showed that the $`K`$ magnitudes of obscured stars cover a wide range at a given pulsation period. For instance, their data indicates that the difference can be more than two magnitudes in the case of the carbon-rich stars. It is interesting to note that their red stars (those with long periods and $`K`$ magnitudes fainter than $``$11 mag) clearly locate the brighter part of sequence $`D`$ on the period-$`K`$ magnitude plane. In addition, Kiss & Bedding (2003) suggested that there is a group of stars located below the Mira sequence (sequence $`C`$) and identified them with dusty AGB stars.

### 3.3 Period-colour diagram

Figure 6 shows the $`JK`$ colours of OGLE variables in the Magellanic clouds as a function of their periods. The insets are the close-ups for the sake of clarity. A general trend that the colours get redder with increasing period can be seen.

The dashed lines are the least-square fit of a linear relation to the Cepheid variables ($`F`$ and $`G`$ stars), which yields the period-$`JK`$ colour relations of

$$JK\text{[mag]}=0.147(\pm 0.010)\mathrm{log}P\text{[days]}+0.248(\pm 0.006)$$
(25)
for the LMC ($`\sigma `$ = 0.062) and

$$JK\text{[mag]}=0.167(\pm 0.009)\mathrm{log}P\text{[days]}+0.272(\pm 0.004)$$
(26)
for the SMC ($`\sigma `$ = 0.074), respectively. The quoted errors are the 1$`\sigma `$ errors of each coefficient. Although the fundamental (group $`F`$) and first overtone (group $`G`$) Cepheids are clearly separated in the period-$`K`$ magnitude plane, we don’t see any significant difference between them in this diagram. This means, if we compare the fundamental and first overtone Cepheids with the same pulsation periods, the stellar radii of first overtone Cepheids should be larger than those of fundamental Cepheids because their stellar temperatures are nearly the same but the first overtone Cepheids are brighter than the fundamental ones. Theories predict exactly the same conclusion (e.g., Bono et al. 2001), and if the stellar radius of the Cepheid variables could be measured accurately, it will help to identify the pulsation modes.

The less regularly pulsating red giants (group $`A^\pm `$ and $`B^\pm `$) also follow a tight sequence on the period-$`JK`$ colour plane. The thick solid lines in the figure indicate the least-square fit of a linear relation to the stars from the four groups, whose $`JK`$ colours and periods are within the ranges, 0.7 $`<JK<`$ 1.3 and 1.2 $`<\mathrm{log}P<`$ 2.1. Their period-$`JK`$ colour relations are also calculated and they are,

$$JK\text{[mag]}=0.231(\pm 0.004)\mathrm{log}P\text{[days]}+0.671(\pm 0.007).$$
(27)
for the LMC ($`\sigma `$ = 0.058) and

$$JK\text{[mag]}=0.272(\pm 0.011)\mathrm{log}P\text{[days]}+0.560(\pm 0.019).$$
(28)
for the SMC ($`\sigma `$ = 0.068), respectively.

It is obvious that most of the $`C`$ and $`C^{}`$ stars in the LMC, and also some $`B^+`$ stars and most of $`C`$ stars in the SMC do not follow the extension of these relations. In Paper I, we confirmed the conclusion of Wood & Sebo (1996) and suggested that stars on sequences $`C`$ and $`C^{}`$ are Mira variables pulsating in the fundamental and first overtone mode respectively, by comparing their model calculations with our observational data. Figure 6 clearly shows that $`C`$ and $`C^{}`$ stars behave very similarly on the period-$`JK`$ colour plane. This corroborates the idea that the $`C`$ and $`C^{}`$ stars are the same type of stars (i.e., Miras), but only different in the pulsation modes. Also, it is likely that the “some $`B^+`$ stars” in the SMC are the counterparts of the $`C^{}`$ stars in the LMC.

In earlier work, Feast et al. (1989), Glass et al. (1995) and Whitelock, Marang & Feast (2000) obtained period-$`JK`$ colour relations of Mira variables in the LMC, Sgr I Baade window of the Galactic Bulge and solar neighborhood, respectively. These relations are all based on the SAAO system. The atmospheres of Mira variables are rather complex, making their quantitative comparisons difficult between different filter systems. Thus here we make only qualitative discussions. Just to get a rough idea, we indicated in the upper panel of figure 6 the period-$`JK`$ colour relations obtained by Feast et al. (1989) for carbon- (labeled I) and oxygen-rich (labeled II) Miras and by Whitelock et al. (2000) (labeled III) after referring to the LCO system by assuming $`(JK)_{\text{LCO}}=0.928(JK)_{\text{SAAO}}0.004`$ (Carpenter, 2001). Of course we can not tell exactly which of our stars are carbon- or oxygen-rich, but it is statistically fair to say that stars with $`JK`$ colours redder than 1.4 are primarily carbon-rich stars (Nikolaev & Weinberg 2000). In this point of view, we confirmed the result of Feast et al. (1989) that oxygen- and carbon-rich Miras follow different period-$`JK`$ colour relations.

Now that we see the $`C`$ and $`C^{}`$ stars separate on the period-$`JK`$ colour plane, it will be interesting to search for the Galactic counterpart of the first overtone Miras ($`C^{}`$ stars) by using this tool. Then we can redetermine their distances using their exclusive period-$`K`$ magnitude relation, which we obtained in Paper I. It will help to understand the differences between the fundamental and first overtone Miras through more detailed studies that are technically difficult in the Magellanic Clouds (i.e., spectroscopic work and mid-infrared observations etc.). Because not only $`C`$ and $`C^{}`$ stars but also the other variables separate on the period-$`JK`$ colour plane, the same argument is true for them, such as $`D`$ stars.

However, before applying this tool to different environments, we should know whether it depends on chemical abundance. Wray, Eyer & Paczyński (2004) showed that small amplitude red giant variables in the Galactic Bar can be separated into two groups, and they follow different period-colour relations. Also, they suggest that their $`A`$ and $`B`$ stars correspond to type $`A^{}`$ and $`B^{}`$ variables, respectively of Paper I. The insets of the figure 6 clearly confirm their result, showing that $`A^{}`$ and $`B^{}`$ are well separated on the period-$`JK`$ color plane. This infers that the period-$`JK`$ relations we derived in equations 27 and 28 are merely the general trends of the variable red giants, and in fact there are exclusive period-colour relations for each population. Rejkuba et al. (2003) studied infrared properties of long period variables in Cen A. Although they did not mention it, it is likely that there are two groups in their period-colour diagrams (see their figure 10). We suggest that their short-period ($`\mathrm{log}P2.45`$) and long-period ($`\mathrm{log}P2.65`$) groups could correspond to type $`C^{}`$ and $`C`$ stars in the LMC, respectively. These facts strengthen the idea that, period-colour diagram is a good and universal tool, at least to tell the type of variable stars within a system.

Lebzelter, Schultheis & Melchior (2002) studied the AGAPEROS/DENIS variables in the LMC and showed that so-called Semi-regular variables follow a period-colour relation but the “regular” variables do not (see their figure 12). To see the regularity of the light variation quantitatively, we show the relationship between the statistic parameter $`\theta `$ and period in figure 7. The figure clearly confirmed the Lebzelter’s suggestion and shows that stars that follow period-$`JK`$ relation ($`A^\pm `$ and $`B^\pm `$ stars with $`\mathrm{log}P`$ 2.1) are less regularly pulsating, and those that don’t ($`B^+`$ stars with $`\mathrm{log}P2.1`$, $`C^{}`$ and $`C`$ stars) are regularly pulsating.

### 3.4 Period-amplitude ($`\mathrm{\Delta }I`$) and colour-amplitude diagram

Figure 8 is a plot to show the relationship between the pulsation period and amplitude ($`\mathrm{\Delta }I`$). The pulsation amplitude is determined from the OGLE’s $`I`$ band data, given as $`\mathrm{\Delta }I=I_{\text{max}}I_{\text{min}}`$. Note that all of the original OGLE light curves were carefully eye-inspected, and we calculated the $`\mathrm{\Delta }I`$ after eliminating the obvious spurious data points.

The figure shows that the fundamental Cepheids show larger amplitude variations than the first overtone Cepheids. Also, the upper envelope of Cepheid amplitude goes down with increasing period. This trend contrasts markedly with that of red giants, because their pulsation amplitudes generally go up with increasing period.

Variables stars with $`K`$ magnitudes below the TRGB ($`A^{}`$ and $`B^{}`$ stars) pulsate with very small amplitude. With a few exceptions, most of the stars from $`D`$ group also pulsate with relatively small amplitude. The large amplitude pulsation ($`\mathrm{\Delta }I`$ 0.9) seems to occur only among the long-period ($`\mathrm{log}P`$ 2.3) variables. If one had to separate Semi-regular from Mira variables based on pulsation amplitudes, the threshold would be about $`\mathrm{\Delta }I`$ 0.9, because one can see a discernible gap around there.

Figure 9 shows the relationship between the $`JK`$ colour and pulsation amplitude ($`\mathrm{\Delta }I`$). The variable red giants show the clear trend that the amplitude gets larger with increasing colour. According to Nikolaev & Weinberg (2000), obscured carbon-rich AGB stars have the $`JK`$ colours redder than about 2.0 mag. Almost all of such dusty carbon-rich stars in the Magellanic Clouds have large pulsation amplitudes. Some of the relatively blue stars (0.8 $`JK`$ 1.2) on the sequence $`C`$ also show large amplitude pulsation. Judging from their $`JK`$ colour and being on the sequence $`C`$, they are likely to be oxygen-rich Mira variables. It is remarkable that the carbon-rich Miras tend to have greater $`I`$-band amplitudes at redder $`JK`$ colour, but the amplitudes of oxygen-rich Miras are almost independent of the colour. This might reflect the difference in the molecular opacities at $`I`$-band between the two groups.

### 3.5 Similarities and differences between the LMC and SMC samples

In a large sense, variable stars in the Magellanic Clouds behave similarly in the figures we discussed so far. However, on closer view, there are differences between variable stars in the two galaxies. In the colour-amplitude diagram (figure 9), we see smaller number of oxygen-rich large amplitude Mira variables in the SMC (counterpart of LMC Miras with $`JK`$ colours bluer than 1.4) compared to the LMC. This is probably because the difference in average chemical abundance and/or in age between the two galaxies (e.g., Cioni & Habing 2003; Mouhcine & Lançon 2003).

## 4 Summary

We presented the data of 8,852 and 2,927 variable stars in the Large and Small Magellanic Clouds. Based on these data, we discussed the infrared properties of the variable stars. We showed that period-$`JK`$ colour diagram is a good tool to tell the pulsation modes of the Mira variables. A follow-up campaign searching for the Galactic counterpart of the first overtone mode Miras would tell us the difference between them and fundamental mode Miras.

## Acknowledgments

We thank the referee for the constructive and helpful comments that improved this paper. We are grateful to people involved in OGLE project for making their data so easy to access and use. We would like to thank Dr. Michael Feast and Dr. Ian Glass for the valuable and helpful comments on the first version of the manuscript. We also thank Dr. Bohdan Paczyński and Dr. Tim Bedding for the kind comments. This research is supported in part by the Grant-in-Aid for Scientific Research (C) No. 12640234 and Grant-in-Aids for Scientific on Priority Area (A) No. 12021202 and 13011202 from the Ministry of Education, Science, Sports and Culture of Japan. The IRSF/SIRIUS project was initiated and supported by Nagoya University, National Astronomical Observatory of Japan and University of Tokyo in collaboration with South African Astronomical Observatory under a financial support of Grant-in-Aid for Scientific Research on Priority Area (A) No. 10147207 of the Ministry of Education, Culture, Sports, Science, and Technology of Japan.


format: text

text:
# Bounds on the Power of Constant-Depth Quantum Circuits

## 1 Introduction

Quantum decoherence is a major obstacle to maintaining long quantum computations. The first working quantum computers will almost certainly be limited to realizing shallow—i.e., small-depth—quantum circuits. This dilemma has inspired much theoretical interest in the capabilities of these circuits, particularly circuits that have constant depth and polynomial size.

Recently, people have found that much can be done with $`O(\mathrm{log}n)`$-depth circuits. For example, Cleve & Watrous were able to approximate the Quantum Fourier Transform over modulus $`2^n`$ with $`O(\mathrm{log}n)`$-depth circuits \[CW00\]. Log-depth seems to present a barrier for many computational problems, however; getting significantly shallower circuits appears difficult if not impossible—unless gates of unbounded width (i.e., number of qubits, or fan-in) are allowed. This has led to the study of constant-depth quantum circuits that can contain certain classes of unbounded fan-in gates.

There are a number of unbounded-width gate classes studied in the literature, most being defined in analogy to classical Boolean gates. The generalized Toffoli gate (see Section 2.1) is the quantum equivalent of the unbounded Boolean AND-gate. Likewise, there are quantum equivalents of Mod-gates and threshold gates. One particular quantum gate corresponds to something taken almost completely for granted in Boolean circuits—fan-out. A fan-out gate copies the (classical) value of a qubit to several other qubits at once.444There is no violation of the No-Cloning Theorem here; only the classical value is copied. Using these gates, one can define quantum versions of various classical circuit classes: $`\mathrm{𝐐𝐍𝐂}^k`$ (Moore & Nilsson \[MN02\]), $`\mathrm{𝐐𝐀𝐂}^k`$ and $`\mathrm{𝐐𝐀𝐂𝐂}^k`$ (Moore \[Moo99\], Green et al. \[GHMP02\]), and $`\mathrm{𝐐𝐓𝐂}^k`$ are analogous to $`\mathrm{𝐍𝐂}^k`$, $`\mathrm{𝐀𝐂}^k`$, $`\mathrm{𝐀𝐂𝐂}`$, and $`\mathrm{𝐓𝐂}^k`$, respectively. The case of particular interest is when $`k=0`$. All these classes are allowed constant-width gates drawn from a finite family. The classes differ in the additional gates allowed. $`\mathrm{𝐐𝐍𝐂}^0`$ is the most restrictive class; all gates must have bounded width. $`\mathrm{𝐐𝐀𝐂}^k`$ circuits are allowed generalized Toffoli gates, and $`\mathrm{𝐐𝐀𝐂𝐂}^k`$ circuits are allowed $`\mathrm{Mod}_q`$-gates, where $`q`$ is kept constant in each circuit family. $`\mathrm{𝐐𝐓𝐂}^k`$ circuits are allowed quantum threshold gates. See Section 2.1 for detailed definitions of most of these classes.

Although quantum classes are defined analogously to Boolean classes, their properties have turned out to be quite different from their classical versions. A simple observation of Moore \[Moo99\] shows that the $`n`$-qubit fan-out gate and the $`n`$-qubit parity ($`\mathrm{Mod}_2`$) gate are equivalent up to constant depth, i.e., each can be simulated by a constant-depth circuit using the other. This is completely different from the classical case, where parity cannot be computed even with $`\mathrm{𝐀𝐂}^0`$ circuits, where fan-out is unrestricted \[Ajt83, FSS84\]. Later, Green et al. showed that quantum $`\mathrm{Mod}_q`$-gates are constant-depth equivalent for all $`q>1`$, and are thus all equivalent to fan-out. Thus, for any $`q>1`$,

$$\mathrm{𝐐𝐍𝐂}_f^0=\mathrm{𝐐𝐀𝐂𝐂}^0(q)=\mathrm{𝐐𝐀𝐂𝐂}^0.$$

(The $`f`$ subscript means, “with fan-out.”) The classical analogs of these classes are provably different. In particular, classical $`\mathrm{Mod}_p`$ and $`\mathrm{Mod}_q`$ gates are not constant-depth equivalent if $`p`$ and $`q`$ are distinct primes, and neither can be simulated by $`\mathrm{𝐀𝐂}^0`$ circuits \[Raz87, Smo87\].

Using $`\mathrm{𝐐𝐍𝐂}^0`$ circuits with unbounded fan-out gates, Høyer & Špalek managed to parallelize a sequence of commuting gates applied to the same qubits, and thus greatly reduced the depth of circuits for various purposes \[HŠ03\]. They showed that threshold gates can be approximated in constant depth this way, and they can be computed exactly if Toffoli gates are also allowed. Thus $`\mathrm{𝐐𝐓𝐂}_f^0=\mathrm{𝐐𝐀𝐂𝐂}^0`$ as well. Threshold gates, and hence fanout gates, are quite powerful; many important arithmetic operations can be computed in constant depth with threshold gates \[SBKH93\]. This implies that the quantum Fourier transform—the quantum part of Shor’s factoring algorithm—can be approxmated in constant depth using fanout gates.

All these results rely for their practicality on unbounded-width quantum gates being available, especially fan-out or some (any) Mod gate. Unfortunately, making such a gate in the lab remains a daunting prospect; it is hard enough just to fabricate a reliable CNOT gate. Much more likely in the short term is that only one- and two-qubit gates will be available, which brings us back to the now more interesting question of $`\mathrm{𝐐𝐍𝐂}^0`$. How powerful is this class? Can $`\mathrm{𝐐𝐍𝐂}^0`$ circuits be simulated classically, say, by computing their acceptance probabilities either exactly or approximately? Is there *anything* that $`\mathrm{𝐐𝐍𝐂}^0`$ circuits can compute that cannot be computed in classical polynomial time? The present paper addresses these questions.

A handful of hardness results about simulating constant-depth quantum circuits with constant-width gates were given recently by Terhal & DiVincenzo \[TD02\]. They showed that if one can classically efficiently simulate, via sampling, the acceptance probability of quantum circuits of depth at least three using one- and two-qubit gates, then $`\mathrm{𝐁𝐐𝐏}\mathrm{𝐀𝐌}`$. They also showed that the polynomial hierarchy collapses if one can efficiently compute the acceptance probability exactly for such circuits. (Actually, a much strong result follows from their proof, namely, $`𝐏=\mathrm{𝐏𝐏}`$.) Their technique uses an idea of Gottesman & Chuang for teleporting CNOT gates \[GC99\] to transform an arbitrary quantum circuit with CNOT and single-qubit gates into a depth-three circuit whose acceptance probability is proportional to, though exponentially smaller than, the original circuit. Their results, however, only hold on the supposition that depth-three circuits with *arbitrary* single-qubit and CNOT gates are simulatable. We build on their techniques, making improvements and simplifications. We weaken their hypothesis by showing how to produce a depth-three circuit with essentially the same gates as the original circuit. In addition, we can get by with only with simple qubit state teleportation \[BBC+93\]. Our results immediately show that the class $`\mathrm{𝐍𝐐𝐍𝐂}^0`$ (the constant-depth analog of $`\mathrm{𝐍𝐐𝐏}`$, see below), is actually the same as $`\mathrm{𝐍𝐐𝐏}`$, which is known to be as hard as the polynomial hierarchy \[FGHP99\]. We give this result in Section 3.1. It underscores yet another drastic difference between the quantum and classical case: while $`\mathrm{𝐀𝐂}^0`$ is well contained in $`𝐏`$, $`\mathrm{𝐐𝐍𝐂}^0`$ circuits (even just depth-three) can have amazingly complex behavior. Our result is also tight; Terhal & DiVincenzo showed that the acceptance probabilities of depth-two circuits over one- and two-qubit gates are computable in polynomial time.

In Section 3.2, we give contrasting upper bounds for $`\mathrm{𝐐𝐍𝐂}^0`$-related language classes. We show that various bounded-error versions of $`\mathrm{𝐐𝐍𝐂}^0`$ (defined below) are contained in $`𝐏`$. Particularly, $`\mathrm{𝐄𝐐𝐍𝐂}^0𝐏`$, where $`\mathrm{𝐄𝐐𝐍𝐂}^0`$ is the constant-depth analog of the class $`\mathrm{𝐄𝐐𝐏}`$ (see below). Our proof uses elementary probability theory, together with the fact that single output qubit measurement probabilities can be computed directly, and the fact that output qubits are “largely” independent of each other. In hindsight, it is not too surprising that $`\mathrm{𝐄𝐐𝐍𝐂}^0𝐏`$. $`\mathrm{𝐄𝐐𝐍𝐂}^0`$ sets a severe limitation on the behavior of the circuit: it must accept with certainty or reject with certainty. This containment is more surprising (to us) for the bounded-error $`\mathrm{𝐐𝐍𝐂}^0`$ classes.

We give open questions and suggestions for further research in Section 4.

## 2 Preliminaries

### 2.1 Gates and circuits

We assume prior knowledge of basic concepts in computational complexity: polynomial time, $`𝐏`$, $`\mathrm{𝐍𝐏}`$, as well as the counting class $`\mathrm{\#}𝐏`$ \[Val79\]. Information can be found, for example, in Papadimitriou \[Pap94\]. The class $`𝐂_{}𝐏`$ ($`\mathrm{co}𝐂_=𝐏`$) was defined by Wagner \[Wag86\]. One way of defining $`𝐂_{}𝐏`$ is as follows: a language $`L`$ is in $`𝐂_{}𝐏`$ iff there are two $`\mathrm{\#}P`$ functions $`f`$ and $`g`$ such that, for all $`x`$, $`xLf(x)g(x)`$. $`𝐂_{}𝐏`$ was shown to be hard for the polynomial hierarchy by Toda & Ogihara \[TO92\].

We will also assume some (but less) background in quantum computation and the quantum circuit model. See Nielsen and Chuang \[NC00\] for a good reference of basic concepts and notation.

We review some standard quantum (unitary) gates. Among the single-qubit gates, we have the Pauli gates $`X`$, $`Y`$, and $`Z`$, the Hadamard gate $`H`$, and the $`\pi /8`$ gate $`T`$, which are defined thus, for $`b\{0,1\}`$:

$`X|b`$ $`=`$ $`|\neg b,`$
$`Y|b`$ $`=`$ $`i(1)^b|\neg b,`$
$`Z|b`$ $`=`$ $`(1)^b|b,`$
$`H|b`$ $`=`$ $`(|0+(1)^b|1)/\sqrt{2},`$
$`T|b`$ $`=`$ $`e^{i\pi b/4}|b.`$
For $`n1`$, the $`(n+1)`$-qubit *generalized Toffoli gate* $`T_n`$ satisfies

$$T_n|x_1,\mathrm{},x_n,b=|x_1,\mathrm{},x_n,b\underset{i=1}{\overset{n}{}}x_i.$$

Here $`b`$ is the *target qubit* and $`x_1,\mathrm{},x_n`$ are the *control qubits*. $`T_n`$ is a kind of multiply controlled $`X`$-gate (or NOT-gate), and is the quantum analog of the Boolean AND-gate with fanin $`n`$. $`T_2`$ is known simply as the Toffoli gate. $`T_1`$ is also known as the controlled NOT (CNOT) gate and is depicted below. Here, $`a,b\{0,1\}`$.

A gate closely related to $`T_n`$ is the controlled $`Z`$-gate defined by

$$Z_n|x_1,\mathrm{},x_n=(1)^{_{i=1}^nx_i}|x_1,\mathrm{},x_n.$$

Since $`HXH=Z`$, the gate $`Z_{n+1}`$-gate can be implemented by placing $`H`$-gates on either side of a $`T_n`$ gate on its target qubit.

The $`(n+1)`$-qubit fan-out gate $`F_n`$ is defined as follows:

$$F_n|x_1,\mathrm{},x_n,b=|x_1b,\mathrm{},x_nb,b.$$

For $`q>1`$, the $`(n+1)`$-qubit $`\mathrm{Mod}_q`$-gate acts on a basis state $`|x_1,\mathrm{},x_n,b`$ by flipping the target qubit $`b`$ iff $`x_1+\mathrm{}+x_n0(modq)`$. The control qubits $`x_1,\mathrm{},x_n`$ are left alone. The $`\mathrm{Mod}_2`$ gate is also known as the parity gate. The *width* of a gate is the number of qubits on which it acts.

Our notion of quantum circuits is fairly standard (again see, for example, \[NC00\]): a series of quantum gates, drawn from some specified set of unitary operators, acting on some specified number of qubits, labeled $`1,\mathrm{},m`$. The first few qubits are considered *input* qubits, which are assumed to be in some basis state initially (i.e., classical input); the rest are ancillæ, each assumed to be in the $`|0`$ state initially. Thus the initial state of the qubits is $`|x,00\mathrm{}0`$, for some binary string $`x`$. Some arbitrary set of qubits are specified as *output* qubits, and these qubits are measured in the computational basis at the final state. We assume that the sets of input and output qubits are part of the description of the circuit. The circuit *accepts* its input if all the output qubits are observed to be 0 in the final state. Otherwise the circuit rejects. We let $`\mathrm{Pr}[C(x)]`$ denote the probability that $`C`$ accepts input $`x`$.

If $`C`$ is any quantum circuit, it will be convenient for us to define $`|C|`$, the *size* of $`C`$, to be the number of output qubits plus the number of “contact points” between qubits and gates, so for example, a single-qubit gate counts one towards the size, while a two-qubit gate counts two, etc. $`C`$ may be laid out by partitioning its gates into *layers* $`1,\mathrm{},d`$, such that (i) gates in the same layer all act on pairwise disjoint sets of qubits, and (ii) all gates in layer $`i`$ are applied before any gates in layer $`i+1`$, for $`1i<d`$. The *depth* of $`C`$ is then the smallest possible value of $`d`$. The *width* of $`C`$ is the number of qubits in $`C`$.

The standard quantum complexity classes can be defined in terms of quantum circuit families. A quantum circuit family is a sequence $`\{C_n\}_{n0}`$ of quantum circuits, where each $`C_n`$ has $`n`$ inputs. We say that $`\{C_n\}`$ is *uniform* if there is a (classical) polynomial-time algorithm that outputs a description of $`C_n`$ on input $`0^n`$.

###### Definition 2.1 (\[BV97, BBBV97, ADH97\])

Let $`L`$ be a language.

* $`L\mathrm{𝐄𝐐𝐏}`$ iff there is a uniform quantum circuit family $`\{C_n\}`$ such that, for all $`x`$ of length $`n`$,

$`xL`$ $``$ $`\mathrm{Pr}[C_n(x)]=1,`$
$`xL`$ $``$ $`\mathrm{Pr}[C_n(x)]=0.`$
* $`L\mathrm{𝐁𝐐𝐏}`$ iff there is a uniform quantum circuit family $`\{C_n\}`$ such that, for all $`x`$ of length $`n`$,

$`xL`$ $``$ $`\mathrm{Pr}[C_n(x)]2/3,`$
$`xL`$ $``$ $`\mathrm{Pr}[C_n(x)]<1/3.`$
* $`L\mathrm{𝐍𝐐𝐏}`$ iff there is a uniform quantum circuit family $`\{C_n\}`$ such that, for all $`x`$ of length $`n`$,

$`xL`$ $``$ $`\mathrm{Pr}[C_n(x)]>0,`$
$`xL`$ $``$ $`\mathrm{Pr}[C_n(x)]=0.`$

It is known that $`𝐏\mathrm{𝐄𝐐𝐏}\mathrm{𝐁𝐐𝐏}`$. It was shown in \[FGHP99, YY99\] that $`\mathrm{𝐍𝐐𝐏}=𝐂_{}𝐏`$, and is thus hard for the polynomial hierarchy.

### 2.2 Complexity classes using $`\mathrm{𝐐𝐍𝐂}`$ circuits

The circuit class $`\mathrm{𝐐𝐍𝐂}`$ was first suggested by Moore and Nilsson \[MN02\] as the quantum analog of the class $`\mathrm{𝐍𝐂}`$ of bounded fan-in Boolean circuits with polylogarithmic depth and polynomial size. We define the class $`\mathrm{𝐐𝐍𝐂}^k`$ in the same fashion as definitions in Green, Homer, Moore, & Pollett \[GHMP02\] with some minor modifications.

###### Definition 2.2 (\[MN02\])

$`\mathrm{𝐐𝐍𝐂}^k`$ is the class of quantum circuit families $`\{C_n\}_{n0}`$ for which there exists a polynomial $`p`$ such that each $`C_n`$ contains $`n`$ input qubits and at most $`p(n)`$ many ancillæ. Each $`C_n`$ has depth $`O(\mathrm{log}^kn)`$ and uses only single-qubit gates and CNOT gates. The single-qubit gates must be from a fixed finite set.

Next we define the language classes $`\mathrm{𝐍𝐐𝐍𝐂}^k`$ and $`\mathrm{𝐄𝐐𝐍𝐂}^k`$. These are $`\mathrm{𝐐𝐍𝐂}^k`$ analogs of the classes $`\mathrm{𝐍𝐐𝐏}`$ and $`\mathrm{𝐄𝐐𝐏}`$, respectively.

###### Definition 2.3 (\[GHMP02\])

Let $`k0`$ be an integer.

* $`\mathrm{𝐍𝐐𝐍𝐂}^k`$ is the class of languages $`L`$ such that there is a uniform $`\{C_n\}\mathrm{𝐐𝐍𝐂}^k`$ such that, for all $`x`$,

$$xL\mathrm{Pr}[C_{|x|}(x)]>0.$$
* $`\mathrm{𝐄𝐐𝐍𝐂}^k`$ is the class of languages $`L`$ such that there is a uniform $`\{C_n\}\mathrm{𝐐𝐍𝐂}^k`$ such that, for all $`x`$, $`\mathrm{Pr}[C_{|x|}(x)]\{0,1\}`$ and

$$xL\mathrm{Pr}[C_{|x|}(x)]=1.$$

#### Remark.

Green, Homer, Moore, & Pollett implicitly consider the output qubits of $`C_n`$ to be all the qubits in $`C_n`$ \[GHMP02\]. In our model we allow any subset of qubits to be the output qubits of $`C_n`$, and we do not restrict our circuits to be clean, i.e., the non-output qubits could end up in an arbitrary state, possibly entangled with the output qubits. The reason we define our circuits this way is based on the observation that, in their model, if a language $`L`$ is in $`\mathrm{𝐄𝐐𝐍𝐂}^k`$ (or $`\mathrm{𝐁𝐐𝐍𝐂}_{ϵ,\delta }^k`$ for large enough $`\delta `$), then $`L`$ can contain no more than one string of each length.

Bounded-error $`\mathrm{𝐐𝐀𝐂}^k`$ classes were mentioned in \[GHMP02\], and one can certainly ask about similar classes for $`\mathrm{𝐐𝐍𝐂}^k`$ circuits. It is not obvious that there is one robust definition of $`\mathrm{𝐁𝐐𝐍𝐂}^0`$—perhaps because it is not clear how to reduce error significantly by amplification in constant depth.555One can always reduce error classically by just running the circuit several times on the same input. In this case, the best definition of $`\mathrm{𝐁𝐐𝐍𝐂}^0`$ may be that the gap between the allowed accept and reject probabilities should be at least $`1/\mathrm{poly}`$. In the next definition, we will try to be as general as possible while still maintaining our assumption that $`\stackrel{}{0}`$ is the only accepting output.

###### Definition 2.4

Let $`ϵ`$ and $`\delta `$ be functions mapping (descriptions of) quantum circuits into real numbers such that, for all quantum circuits $`C`$, $`0<ϵ(C)\delta (C)1`$. We write $`ϵ_C`$ and $`\delta _C`$ to denote $`ϵ(C)`$ and $`\delta (C)`$, respectively. $`\mathrm{𝐁𝐐𝐍𝐂}_{ϵ,\delta }^k`$ is the class of languages $`L`$ such that there is a uniform $`\{C_n\}\mathrm{𝐐𝐍𝐂}^k`$ such that for any string $`x`$ of length $`n`$,

$`xL`$ $``$ $`\mathrm{Pr}[C_n(x)]\delta _{C_n},`$
$`xL`$ $``$ $`\mathrm{Pr}[C_n(x)]<ϵ_{C_n}.`$
An interesting special case is when $`ϵ_C=\delta _C=1`$, that is, the input is accepted iff the circuit accepts with probability 1, and there is no promise on the acceptance probability. One might expect that, by the symmetry of the definitions, this class $`\mathrm{𝐁𝐐𝐍𝐂}_{1,1}^0`$ is the same as $`\mathrm{𝐍𝐐𝐍𝐂}^0`$, but it is almost certainly not, as we will see.

### 2.3 Other classes of constant-depth quantum circuits

###### Definition 2.5

Let $`k0`$ and $`q>1`$ be integers.

* $`\mathrm{𝐐𝐀𝐂}^k`$ is the same as $`\mathrm{𝐐𝐍𝐂}^k`$ except that generalized Toffoli gates are allowed in the circuits.
* $`\mathrm{𝐐𝐀𝐂𝐂}(q)`$ is the same as $`\mathrm{𝐐𝐍𝐂}^0`$ except that $`\mathrm{Mod}_q`$ gates are allowed in the circuits.
* $`\mathrm{𝐐𝐀𝐂𝐂}=_{q>1}\mathrm{𝐐𝐀𝐂𝐂}(q)`$.

## 3 Main results

### 3.1 Simulating $`\mathrm{𝐐𝐍𝐂}^0`$ circuits exactly is hard

###### Theorem 3.1

$`\mathrm{𝐍𝐐𝐍𝐂}^0=\mathrm{𝐍𝐐𝐏}=𝐂_{}𝐏`$.

As a corollary, we essentially solve an open problem of Green et al. \[GHMP02\]. They conjectured that $`\mathrm{𝐍𝐐𝐀𝐂𝐂}\mathrm{𝐓𝐂}^0`$, the class of constant-depth Boolean circuits with threshold gates.

###### Corollary 3.2

For any $`k0`$,

$$\mathrm{𝐍𝐐𝐍𝐂}^0=\mathrm{𝐍𝐐𝐍𝐂}^k=\mathrm{𝐍𝐐𝐀𝐂}^k=\mathrm{𝐍𝐐𝐀𝐂𝐂}=𝐂_{}𝐏.$$

Thus, $`\mathrm{𝐍𝐐𝐀𝐂𝐂}\mathrm{𝐓𝐂}^0`$ unless $`𝐂_{}𝐏=\mathrm{𝐓𝐂}^0`$.

Let $`B`$ be the two-qubit Bell gate, defined as

Also let

which produces the EPR state $`(|00+|11)/\sqrt{2}`$. We prove the following lemma, from which the theorem follows quickly.

###### Lemma 3.3

For any quantum circuit $`𝒞`$ using gates drawn from any family $``$, there is a depth-three quantum circuit $`𝒞^{}`$ of size linear in $`|𝒞|`$ using gates drawn from $`\{B,B^{}\}`$ such that for any input $`x`$ of the appropriate length,

$$\mathrm{Pr}[𝒞^{}(x)]=2^m\mathrm{Pr}[𝒞(x)],$$

for some $`m2|𝒞|`$ depending only on $`𝒞`$. The middle layer of $`𝒞^{}`$ contains each gate in $`𝒞`$ exactly once and no others. The third layer contains only $`B^{}`$-gates, and the first layer contains only $`B`$-gates, which are used only to create EPR states.

Proof. Our construction is a simplified version of the main construction in Terhal & DiVincenzo \[TD02\], but ours is stronger in one crucial respect discussed below: it does not significantly increase the family of gates used. To construct $`𝒞^{}`$, we start with $`𝒞`$ and simply insert, for each qubit $`q`$ of $`𝒞`$, a simplified teleportation module (shown in Figure 1)

between any two consecutive quantum gates of $`𝒞`$ acting on $`q`$. No further gates involve the qubits $`r_1`$ and $`r_2`$ to the right of the $`B^{}`$-gate. This module, which lacks the usual corrective Pauli gates, is a nonadaptive version of the standard single-qubit teleportation circuit \[BBC+93\]. It faithfully teleports the state if and only if the observed output of the $`B^{}`$-gate on the right is $`00`$. After inserting each teleportation circuit, the gates acting before and after it are now acting on different qubits. Further, it is important to note that any entanglement the qubit state has with other qubits is easily seen to be preserved in the teleported qubit. The input qubits of $`𝒞^{}`$ are those of $`𝒞`$. The output qubits of $`𝒞^{}`$ are of two kinds: output qubits corresponding to outputs of $`𝒞`$ are the *original outputs*; the other outputs are the qubits (in pairs) coming from the added $`B^{}`$-gates. We’ll call the measurement of each such pair a *Bell measurement*, even though it is really in the computational basis.

In addition to the gates in $`𝒞`$, $`𝒞^{}`$ uses only $`B`$-gates to make the initial EPR pairs and $`B^{}`$-gates for the Bell measurements. A sample transformation is shown in Figure 2.

$`𝒞^{}`$ has depth three since it uses the first layer to make the initial EPR states and the third layer to rotate the Bell basis back to the computational basis. All the gates of $`𝒞`$ appear on the second layer. From the above constuction and the properties of the teleportation module, it is not hard to see that for all $`x`$ of the appropriate length,

$`\mathrm{Pr}[𝒞(x)]`$ $`=`$ $`\mathrm{Pr}[\text{all original outputs of }𝒞^{}\text{ are 0}\text{all qubit states are teleported correctly}]`$
$`=`$ $`\mathrm{Pr}[\text{all original outputs of are 0}\text{all Bell measurement results are 00}]`$
$`=`$ $`{\displaystyle \frac{\mathrm{Pr}[𝒞^{}(x)]}{\mathrm{Pr}[\text{all Bell measurement results are 00}]}},`$
since the Bell measurements are among the output measurements of $`𝒞^{}`$. Let $`k`$ be the number of $`B^{}`$-gates on layer 3. Clearly, $`k|𝒞|`$, and it is well-known that each Bell measurement will give 00 with probability $`1/4`$, independent of all other measurements. So the lemma follows by setting $`m=2k`$. $`\mathrm{}`$

Proof of Theorem 3.1. As mentioned before, $`\mathrm{𝐍𝐐𝐏}`$ \[ADH97\] is defined as the class of languages recognized by quantum Turing machines (equivalently, uniform quantum circuit families over a finite set of gates) where the acceptance criterion is that the accepting state appear with nonzero probability. It is known \[FGHP99, YY99\] that $`\mathrm{𝐍𝐐𝐏}=𝐂_{}𝐏`$, which contains $`\mathrm{𝐍𝐏}`$ and is hard for the polynomial hierarchy. Since $`\mathrm{𝐐𝐍𝐂}^0`$ circuit families must also draw their gates from some finite set, we clearly have $`\mathrm{𝐍𝐐𝐍𝐂}^0\mathrm{𝐍𝐐𝐏}`$. The reverse containment follows from our construction: an arbitrary circuit $`𝒞`$ is transformed into a depth-three circuit $`𝒞^{}`$ *with the same gates* as $`𝒞`$ plus $`B`$ and $`B^{}`$. Moreover, $`𝒞^{}`$ accepts with nonzero probability iff $`𝒞`$ does. Thus an $`\mathrm{𝐍𝐐𝐏}`$ language $`L`$ recognized by a uniform quantum circuit family over a finite set of quantum gates is also recognized by a uniform depth-three circuit family over a finite set of quantum gates, and so $`L\mathrm{𝐍𝐐𝐍𝐂}^0`$. $`\mathrm{}`$

Using the gate teleportation apparatus of Gottesmann and Chuang \[GC99\], Terhal & DiVincenzo also construct a depth-three666They count the depth as four, but they include the final measurement as an additional layer whereas we do not. quantum circuit $`𝒞^{}`$ out of an arbitrary circuit $`𝒞`$ (over CNOT and single-qubit gates) with a similar relationship of acceptance probabilities. However, they only teleport the CNOT gate, and their $`𝒞^{}`$ may contain single-qubit gates formed by compositions of arbitrary numbers of single-qubit gates from $`𝒞`$. (Such gates may not even be approximable in constant depth by circuits over a fixed finite family of gates.) When their construction is applied to each circuit in a uniform family, the resulting circuits are thus not generally over a finite gate set, even if the original circuits were.

Our construction solves this problem by teleporting every qubit state in between all gates involving it. Besides $`B`$ and $`B^{}`$, we only use the gates of the original circuit. We also are able to bypass the CNOT gate teleportation technique of \[GC99\], using instead basic single-qubit teleportation \[BBC+93\], which works with arbitrary gates.

### 3.2 Simulating $`\mathrm{𝐐𝐍𝐂}^0`$ circuits approximately is easy

In this section we prove that $`\mathrm{𝐁𝐐𝐍𝐂}_{ϵ,\delta }^0𝐏`$ for certain $`ϵ,\delta `$. For convenience we will assume that all gates used in quantum circuits are either one- or two-qubit gates that have “reasonable” matrix elements—algebraic numbers, for instance. Our results can apply more broadly, but they will then require greater care to prove.

For a quantum circuit $`𝒞`$, we define a dependency graph over the set of its output qubits.

###### Definition 3.4

Let $`𝒞`$ be a quantum circuit and let $`p`$ and $`q`$ be qubits of $`𝒞`$. We say that *$`q`$ depends on $`p`$* if there is a forward path in $`𝒞`$ starting at $`p`$ before the first layer, possibly passing through gates, and ending at $`q`$ after the last layer. More formally, we can define dependence by induction on the depth of $`𝒞`$. For depth zero, $`q`$ depends on $`p`$ iff $`q=p`$. For depth $`d>0`$, let $`𝒞^{}`$ be the same as $`𝒞`$ but missing the first layer. Then $`q`$ depends on $`p`$ (in $`𝒞`$) iff there is a qubit $`r`$ such that $`q`$ depends on $`r`$ (in $`𝒞^{}`$) and either $`p=r`$ or there is a gate on the first layer of $`𝒞`$ that involves both $`p`$ and $`r`$.

###### Definition 3.5

For $`𝒞`$ a quantum circuit and $`q`$ a qubit of $`𝒞`$, define

$$D_q=\{pq\text{ depends on }p\}.$$

If $`S`$ is a set of qubits of $`𝒞`$, define $`D_S=_{qS}D_q`$. Let the *dependency graph of $`𝒞`$* be the undirected graph with the output qubits of $`𝒞`$ as vertices, and with an edge between two qubits $`q_1`$ and $`q_2`$ iff $`D_{q_1}D_{q_2}\mathrm{}`$.

If $`𝒞`$ has depth $`d`$, then it is easy to see that the degree of its dependency graph is less than $`2^{2d}`$. The following lemma is straightforward.

###### Lemma 3.6

Let $`𝒞`$ be a quantum circuit and let $`S`$ and $`T`$ be sets of output qubits of $`𝒞`$. Fix an input $`x`$ and bit vectors $`u`$ and $`v`$ with lengths equal to the sizes of $`S`$ and $`T`$, respectively. Let $`E_{S=u}`$ (respectively $`E_{T=v}`$) be the event that the qubits in $`S`$ (respectively $`T`$) are observed to be in the state $`u`$ (respectively $`v`$) in the final state of $`𝒞`$ on input $`x`$. If $`D_SD_T=\mathrm{}`$, then $`E_{S=u}`$ and $`E_{T=v}`$ are independent.

For an algebraic number $`a`$, we let $`a`$ be the size of some reasonable representation of $`a`$.

The results in this section follow from the next theorem.

###### Theorem 3.7

There is a deterministic decision algorithm $`A`$ which takes as input

1. a quantum circuit $`𝒞`$ with depth $`d`$ and $`n`$ input qubits,
2. a binary string $`x`$ of length $`n`$, and
3. an algebraic number $`t[0,1]`$,

and behaves as follows: Let $`D`$ be one plus the degree of the dependency graph of $`𝒞`$. $`A`$ runs in time $`\mathrm{Poly}(|𝒞|,2^{2^d},t)`$, and

* if $`\mathrm{Pr}[𝒞(x)]1t`$, then $`A`$ accepts, and
* if $`\mathrm{Pr}[𝒞(x)]<1Dt`$, then $`A`$ rejects.

Note that since $`D2^{2d}`$, if $`t<2^{2d}`$, then $`A`$ will reject when $`\mathrm{Pr}[𝒞(x)]<12^{2d}t`$.

Proof of Theorem 3.7. On input $`(𝒞,x,t)`$ as above,

1. $`A`$ computes the dependency graph $`G=(V,E)`$ of $`𝒞`$ and its degree, and sets $`D`$ to be the degree plus one.
2. $`A`$ finds a $`D`$-coloring $`c:V\{1,\mathrm{},D\}`$ of $`G`$ via a standard greedy algorithm.
3. For each output qubit $`qV`$, $`A`$ computes $`P_q`$—the probability that 0 is measured on qubit $`q`$ in the final state (given input $`x`$).
4. For each color $`i\{1,\mathrm{},D\}`$, let $`B_i=\{qVc(q)=i\}`$. $`A`$ computes

$$P_{B_i}=\underset{qB_i}{}P_q,$$

which by Lemma 3.6 is the probability that all qubits colored $`i`$ are observed to be 0 in the final state.
5. If $`P_{B_i}1t`$ for all $`i`$, the $`A`$ accepts; otherwise, $`A`$ rejects.

We first show that $`A`$ is correct. If $`\mathrm{Pr}[𝒞(x)]1t`$, then for each $`i\{1,\mathrm{},D\}`$,

$$1t\mathrm{Pr}[𝒞(x)]P_{B_i},$$

and so $`A`$ accepts. On the other hand, if $`\mathrm{Pr}[𝒞(x)]<1Dt`$, then

$$Dt<1\mathrm{Pr}[𝒞(x)]\underset{i=1}{\overset{D}{}}\left(1P_{B_i}\right),$$

so there must exist an $`i`$ such that $`t<1P_{B_i}`$, and thus $`A`$ rejects.

To show that $`A`$ runs in the given time, first we show that the measurement statistics of any output qubit can be calculated in time polynomial in $`2^{2^d}`$. Pick an output qubit $`q`$. By looking at $`𝒞`$ we can find $`D_q`$ in time $`\mathrm{Poly}(|𝒞|)`$. Since $`𝒞`$ has depth $`d`$ and uses gates on at most two qubits each, $`D_q`$ had cardinality at most $`2^d`$. Then we simply calculate the measurement statistics of output qubit $`q`$ from the input state restricted to $`D_q`$, i.e., with the other qubits traced out. This can be done by computing the state layer by layer, starting with layer one, and at each layer tracing out qubits when they no longer can reach $`q`$. Because of the partial traces, the state will in general be a mixed state so we maintain it as a density operator. We are multiplying matrices of size at most $`2^{2^d}\times 2^{2^d}`$ at most $`O(d)`$ times. All this will take time polynomial in $`2^{2^d}`$, provided we can show that the individual field operations on the matrix elements do not take too long.

Since there are finitely many gates to choose from, their (algebraic) matrix elements generate a field extension $`F`$ of $``$ with finite index $`r`$. We can thus store values in $`F`$ as $`r`$-tuples of rational numbers, with the field operations of $`F`$ taking polynomial time. Furthermore, one can show that for $`a,bF`$, $`ab=O(a+b)`$ and $`_{i=1}^na_i=O(n\mathrm{max}_ia_i)`$ for any $`a_1,\mathrm{},a_nF`$. A bit of calculation then shows that the intermediate representations of numbers do not get too large.

The dependency graph and its coloring can clearly be computed in time $`\mathrm{Poly}(|𝒞|)`$. The only things left are the computation of the $`P_{B_i}`$ and their comparison with $`1t`$. For reasons similar to those above for matrix multiplication, this can be done in time $`\mathrm{Poly}(|𝒞|,2^{2^d},t)`$. $`\mathrm{}`$

###### Corollary 3.8

Suppose $`ϵ`$ and $`\delta `$ are polynomial-time computable, and for any quantum circuit $`C`$ of depth $`d`$, $`\delta _C=12^{2d}(1ϵ_C)`$. Then

$$\mathrm{𝐁𝐐𝐍𝐂}_{ϵ,\delta }^0𝐏.$$

Proof. For each $`C`$ of depth $`d`$ in the circuit family and each input $`x`$, apply the algorithm $`A`$ of Theorem 3.7 with $`t=1\delta _C=2^{2d}(1ϵ_C)`$, noting that $`D2^{2d}`$. $`\mathrm{}`$

The following few corollaries are instances of Corollary 3.8.

###### Corollary 3.9

For quantum circuit $`C`$, let $`\delta _C=12^{(2d+1)}`$, where $`d`$ is the depth of $`C`$. Then

$$\mathrm{𝐁𝐐𝐍𝐂}_{(1/2),\delta }^0𝐏.$$

Proof. Apply algorithm $`A`$ to each circuit, setting $`t=2^{(2d+1)}`$. $`\mathrm{}`$

###### Corollary 3.10

$`\mathrm{𝐁𝐐𝐍𝐂}_{1,1}^0𝐏`$.

Proof. Apply algorithm $`A`$ to each circuit, setting $`t=0`$. $`\mathrm{}`$

###### Corollary 3.11

$`\mathrm{𝐄𝐐𝐍𝐂}^0𝐏`$.

Proof. Clearly, $`\mathrm{𝐄𝐐𝐍𝐂}^0\mathrm{𝐁𝐐𝐍𝐂}_{1,1}^0`$. $`\mathrm{}`$

Corollaries 3.10 and 3.11 can actually be proven more directly. We simply compute, for each output, its probability of being 0. We accept iff all probabilities are 1.

We observe here that by a simple proof using our techniques, one can show that the generalized Toffoli gate cannot be simulated by a $`\mathrm{𝐐𝐍𝐂}^0`$ circuit, since the target of the Toffoli gate can only depend on constantly may input qubits.

## 4 Conclusions, open questions, and further research

Our upper bound results in Section 3.2 can be improved in certain ways. For example, the containment in $`𝐏`$ is easily seen to apply to $`(\mathrm{log}\mathrm{log}n+O(1))`$-depth circuits as well. Can we increase the depth further? Another improvement would be to put $`\mathrm{𝐁𝐐𝐍𝐂}_{ϵ,\delta }^0`$ into classes smaller than $`𝐏`$. LOGSPACE seems managable. How about $`\mathrm{𝐍𝐂}^1`$?

There are some general questions about whether we have the “right” definitions for these classes. For example, the accepting outcome is defined to be all outputs being 0. One can imagine more general accepting conditions, such as arbitrary classical polynomial-time postprocessing. If we allow this, then all our classes will obviously contain $`𝐏`$. If we allow arbitrary classical polynomial-time *pre*processing, then all our classes will be closed under ptime $`m`$-reductions (Karp reductions).

Finally, there is the question of the probability gap in the definitions of $`\mathrm{𝐁𝐐𝐍𝐂}^0`$. Certainly we would like to narrow this gap (ideally, to $`1/\mathrm{poly}`$) and still get containment in $`𝐏`$.

## Acknowledgments

We would like to thank David DiVincenzo and Mark Heiligman for helpful conversations on this topic. This work was supported in part by the National Security Agency (NSA) and Advanced Research and Development Agency (ARDA) under Army Research Office (ARO) contract numbers DAAD 19-02-1-0058 (for S. Homer, and F. Green) and DAAD 19-02-1-0048 (for S. Fenner and Y. Zhang).


text:
# From Linear Optical Quantum Computing to Heisenberg-Limited Interferometry

## 1 Effective nonlinearities from projective measurements

Looking back, scalable quantum computation with linear optics was considered to be impossible due to the lack of efficient two-qubit logic gates, despite the ease of implementation of one-qubit gates. Two-qubit gates necessarily need a nonlinear interaction between the two photons, and the efficiency of this nonlinear interaction is typically very tiny in bulk materials . However, Knill, Laflamme, and Milburn recently showed that this barrier can be circumvented with effective nonlinearities produced by projective measurements , and with this work scalable linear optical quantum computation (LOQC) becomes a reality.

Let us consider the Kerr nonlinearity, which can be described by a Hamiltonian

$`_{\mathrm{Kerr}}=\mathrm{}\kappa \widehat{a}^{}\widehat{a}\widehat{b}^{}\widehat{b},`$ (1)
where $`\kappa `$ is a coupling constant depending on the third-order nonlinear susceptibility, and $`\widehat{a}^{}`$, $`\widehat{b}^{}`$ and $`\widehat{a}`$, $`\widehat{b}`$ are the creation and annihilation operators for two optical modes. One convenient choice of the logical qubit can then be represented by the two modes containing a single photon, denoted as

$`|0_L`$ $`=`$ $`|0_l|1_k`$
$`|1_L`$ $`=`$ $`|1_l|0_k,`$ (2)
where $`l,k`$ represent the relevant modes, and we have used the notation $`|_L`$ for a logical qubit, in order to distinguish it from the photon-number states $`|_k`$.

For a two-qubit gate, let us assign mode 1,2 for the control qubit, and 3,4 for the target qubit. Suppose now only the modes 2,4 are coupled under the interaction given by Eq.(1). For a given interaction time $`\tau `$, the transformation can be written as

$`|0_L|0_L`$ $`|0_L|0_L`$
$`|0_L|1_L`$ $`|0_L|1_L`$
$`|1_L|0_L`$ $`|1_L|0_L`$
$`|1_L|1_L`$ $`e^{i\phi }|1_L|1_L,`$ (3)
where $`\phi \kappa n_an_b\tau `$ and $`n_a=\widehat{a}^{}\widehat{a},n_b=\widehat{b}^{}\widehat{b}`$. This operation yields a conditional phase shift . When $`\phi =\pi `$, we have the two two-qubit gate called the conditional sign-flip gate. A typical two-qubit gate, controlled-NOT (CNOT), is then simply constructed by using the conditional sign flip and two one-qubit gates (e.g., Hadamard on the target, followed by the conditional sign flip and another Hadamard on the target). In order to have $`\phi \pi `$ at the single-photon level, however, a huge third-order nonlinear coupling is required . Instead, Knill, Laflamme, and Milburn devised a nondeterministic conditional sign flip gate using nonlinear sign gate defined by

$`\alpha |0+\beta |1+\gamma |2\alpha |0+\beta |1\gamma |2.`$ (4)
The nonlinear sign gate can be implemented non-deterministically by three beam splitters, two photo-detectors, and one ancilla photon  (see Fig. 1).

The implementation of conditional sign flip gate is then made by the combination of the nonlinear sign gate and the physics of Hong-Ou-Mandel (HOM) interferometer . For two arbitrary qubits

$`|Q_1`$ $`=`$ $`\alpha _0|0_L+\alpha _1|1_L=\alpha _0|0_1|1_2+\alpha _1|1_1|0_2,`$
$`|Q_2`$ $`=`$ $`\alpha _0^{}|0_L+\alpha _1^{}|1_L=\alpha _0^{}|0_3|0_4+\alpha _1^{}|1_3|0_4,`$ (5)
the transformation of applying a condition sign flip gate can be written as

$`|Q_1|Q_2`$ $``$ $`\alpha _0\alpha _0^{}|0_L|0_L+\alpha _0\alpha _1^{}|0_L|1_L+\alpha _1\alpha _0^{}|1_L|0_L\alpha _1\alpha _1^{}|1_L|1_L`$ (6)
$`=\alpha _0\alpha _0^{}|0,1,0,1+\alpha _0\alpha _1^{}|0,1,1,0+\alpha _1\alpha _0^{}|1,0,0,1`$
$`\alpha _1\alpha _1^{}|1,0,1,0.`$
where the modes 1 and 2 are designated for the control qubit, and 3 and 4 are for the target qubit. A sign change happens only when there is one photon in mode 1 and one photon in mode 3.

The implementation of the desired operation is achieve by two 50:50 beam splitters and two nonlinear sign gates (see Fig. 2), with probability of success 1/16. Effectively then, a Kerr nonlinearity can be generated by linear optics and projective measurements. The probability of success then can be boosted by using gate-teleportation technique and sufficient number of ancilla photons. It has been also demonstrated that such a nondeterministic two-qubit gate can be made for qubits defined by the polarization degree of freedom . A general formalism for the effective photon nonlinearities generated by conditional measurement schemes in linear optics has been developed in some of our recent work . Naturally, we emphasized that the ability to discriminate the number of incoming photons plays an essential role in the realization of such nonlinear quantum gates in LOQC .

## 2 Optical lithography beyond diffraction limit

Since the projective measurement can produce an effective photon-photon interaction, it can be a useful tool to manipulate quantum correlations between photons. A particularly interesting type of quantum state of light is the maximally entangled photon-number state. In our recent work, it has been shown that the Rayleigh diffraction limit in optical lithography can be overcome  by using a quantum state of light of the following form:

$`\frac{1}{\sqrt{2}}\left(|N,0_{ab}+|0,N_{ab}\right),`$ (7)
where $`a,b`$ denote two different paths. It is well known that the $`N=2`$ path-entangled state of Eq. (7) can be generated using a Hong-Ou-Mandel interferometer and two single-photon input states. A 50:50 beam splitter, however, is not sufficient for producing path-entangled states with a photon number larger than two . On the other hand, the generation of these states with $`N>2`$ seems to involve a large Kerr nonlinearity, which makes their physical implementation very difficult .

Using the technique of projective measurement, we have shown that by conditioning on single-photon–detection, the generation of path-entangled photon-number states is possible for more than two photons . Figure 3 depicts a simple Mach-Zehnder type interferometric scheme for producing such a state with $`N=4`$, using dual Fock-state inputs, $`|N_a|N_b`$.

Suppose that we have the $`|3,3`$ state as the input entering into the modes $`a`$ and $`b`$. Then, the first beam splitter transforms $`|3,3`$ into a linear superposition of $`|6,0`$, $`|4,2`$, $`|2,4`$, and $`|0,6`$. After passing through the two intermediate beam splitters, and if one and only one photon is counted at each detector, the state is then projected onto an equal superposition of $`|3,1`$ and $`|1,3`$. Simply, the states $`|6,0`$ or $`|0,6`$ are discarded by this feedback from the photodetectors, since they cannot yield a click at both detectors. The $`|4,2`$ and $`|2,4`$ states, on the other hand, lose one photon in each arm of the interferometer and are projected to $`|3,1`$ and $`|1,3`$, respectively. Thus, just before the last beam splitter, we have a superposition of $`|3,1`$ and $`|1,3`$ with a known phase. We use an appropriate phase shifter in one of the two arms of interferometer so that the state after the projective measurement is reduced to $`|3,1|1,3`$. Consequently after the last beam splitter, we get the desired state $`|4,0|0,4`$. We have further shown that it is possible to produce any two-mode, entangled, photon-number state with only linear optical devices conditioned on photodetection . Although the probability of success generally decreases exponentially as $`N`$ increases , it was shown that the scaling can be sub-exponential in $`N`$ by using quantum memory . For some applications, however, it can already be useful to have four-photon entanglement. Quantum interferometric lithography is such an example. Our approach has been used in a recent experiment to produce maximally entangled three-photon polarization states .

## 3 Phase-noise reduction beyond shot-noise limit

In a typical optical interferometer, in which ordinary coherent laser light enters via one input port, the phase sensitivity in the shot-noise limit scales as $`\mathrm{\Delta }\phi =1/\sqrt{\overline{N}}`$ where $`\overline{N}`$ is the mean number of photons. Over the last two decades, a lot of effort was devoted to overcoming this limit, due to the obvious practical applications. In the early 1980’s, Caves first demonstrated that squeezing the vacuum noise in the unused input port of an interferometer causes the phase sensitivity to beat the standard shot-noise limit by $`1/\sqrt{\overline{N}}1/\overline{N}`$ in the limit of infinite squeezing . Bondurant and Shapiro proposed a multifrequency squeezed state interferometer for this same purpose . Hermann Haus pioneered in the generation of squeezed light in optical fibers  as well as in Mach-Zehnder interferometers , towards achieving the goal of Heisenberg-limited interferometry.

On the other hand, in 1986 it had been suggested by Yurke and by Yuen that the phase-noise reduction can also be achieved using inputs with number eigenstates incident upon both input ports of a Mach-Zehnder interferometer . In particular, Yurke and collaborators showed that if the photons entered into each input port of the interferometer in nearly equal numbers with a certain type of correlation, then, it was possible to obtain an asymptotic phase sensitivity of $`1/N`$, the Heisenberg limit . The so-called Yurke state is of the form:

$`\frac{1}{\sqrt{2}}\left[|N,N1_{ab}+|N1,N_{ab}\right],`$ (8)
where $`a,b`$ denote the two input modes.

Then, in the early 1990’s, Holland and Burnett proposed Heisenberg-limited interferometry by the use of so-called dual Fock states of the form $`|N,N_{ab}`$ . Such a state can be approximately generated by degenerate parametric down conversion or by optical parametric oscillation. In a conventional Mach-Zehnder interferometer, only the difference of the number of photons at the output is measured. However, to obtain increased sensitivity with dual Fock states, some special detection scheme is required, for which Hall and co-workers proposed a combination of a direct measurement of the variance of the difference current as well as a data-processing method based on Bayesian analysis . Other types of special input states have been proposed for achieving the Heisenberg-limited phase sensitivity .

In particular, the Yurke state approach has the same measurement scheme as the conventional Mach-Zehnder interferometer; a direct detection of the difference current . It is, however, not easy to generate the desired correlation in the input state. On the other hand, the dual Fock-state approach finds a rather simple input state, but requires a complicated data processing methods. However, by a simple utilization of the projective measurements with linear optical devices, it is possible to generate a desired correlation in the Yurke state directly from the dual Fock state.

Let us consider a linear optical setup depicted in Fig. 4. For a given dual Fock-state input $`|N,N_{ab}`$, the output state conditioned on, for example, a two-fold coincident count is given by

$`\frac{1}{\sqrt{2}}\left[|N,N2+|N2,N\right].`$ (9)
It is not difficult to see that the condition of the coincident detection yields either one of the two modes before the beam splitter must contain two photons while the other modes contains no photon. This is an inverse-HOM situation where one photon at each mode cannot contribute to the coincident detection. Consequently, the coincident detection results in a situation where the main modes $`a`$ and $`b`$ can only lose two photons or not at all. Here the probability success of this event can be optimized by choosing the reflection coefficient of the first beam splitters. For the reflection coefficient of $`|r|^2=1/N`$, its asymptotic value is found as $`1/(2e^2)`$, independent of $`N`$ . Furthermore, using a stack of such devices with appropriate phase shifters, we have developed a method for the generation of maximally path-entangled states of the form Eq. (7) with an arbitrary number of photons .

## 4 Single-photon QND measurement devices

In quantum optics the quantum nondemolition (QND) devices are usually considered in the context of photon-number measurements . In 1985 Imoto, Haus, and Yamamoto developed the basic idea of QND in quantum optics, which consists of coupling the signal beam to the ‘meter’ beam in a nonlinear medium and the detection of the phase shift of the meter beam measures the number of photons in the signal beam . The readouts of the number of photons in the signal beam are performed by phase-sensitive homodyne detection of the meter beam in interferometer arrangements.

By the same token, as discussed in Section 1, QND measurements at the single-photon level becomes extremely difficult due to the tiny strength of the nonlinear interaction between photons. In a recent experiment, a single-photon QND has been demonstrated by using a resonant coupling between a cavity field and the meter atoms . Such a QND device at the single photon level can provide a key tool for optical quantum information processing, perhaps most importantly in quantum error correction. In contrast to the cavity approach, we have proposed a probabilistic device that signals the presence of a single photon without destroying it using the technique of projective measurement .

A simple way to perform a single-photon QND measurement is to use quantum teleportation. For example, a maximally polarization-entangled photon pair produced by a parametric down-converter can serve as a quantum channel. If the input state is in a arbitrary superposition of zero and one photon with a fixed polarization, the detector coincidence in Bell state measurement, signals the present of a single photon in the input and also the output states. Simply, a vacuum input can never yield a two-fold detector coincidence.

This teleportation-based QND scheme works only if the input states are restricted to one or zero photons. However, it breaks down if there are more than two photons in the input. For example, if the input state is of the form:

$`|\psi _{in}`$ $`=`$ $`c_0|0+c_1|1+c_2|2,`$ (10)
the two-photon term will contribute to the two-fold coincidence even when the output of the down-converter is vacuum, yielding a false identification of a single photon in the output state, conditioned on a detector coincidence.

If we restrict the number of photons in the input up to two, we can eliminate such a false identification by using an interferometric setup depicted in Fig.5. In Fig. 5, we assume that the input state of the form Eq.(10) enters into in mode $`a`$, and we further prepare single photons for mode $`c`$ and $`d`$. Assuming beam splitters are 50:50, the transformation of the probe photons in the mode $`c`$ and $`d`$ can then be written as

$`\widehat{c}^{}\widehat{d}^{}`$ $``$ $`\frac{1}{4}(\widehat{b}^2\widehat{a}^2+\widehat{d}^2\widehat{c}^22\widehat{a}^{}\widehat{c}^{}+2\widehat{b}^{}\widehat{d}^{}).`$ (11)
Then we post select the photodetection outcome for one and only one photon counted at each detector. This condition requires either two photons are in mode $`c`$ or two photons are in mode $`d`$, which eliminates the contribution from $`c_0|0`$ of the input state. For one-photon and two-photon input states, we have

$`\widehat{a}^{}`$ $``$ $`(\widehat{a}^{}\widehat{c}^{})/\sqrt{2},\widehat{a}^2(\widehat{a}^22\widehat{a}^{}\widehat{c}^{}+\widehat{c}^2)/2.`$ (12)
Now the only two-fold coincidence in the mode $`c^{}`$ and $`d^{}`$ by a two-photon input is possible when the $`2\widehat{b}^{}\widehat{d}^{}`$ from Eq.(11) and $`2\widehat{a}^{}\widehat{c}^{}`$ from Eq.(12) combine, yielding $`\widehat{a}^{}\widehat{b}^{}\widehat{c}^{}\widehat{d}^{}`$. However, further postselecting on the vacuum in the mode $`a^{}`$ eliminates this two-photon contribution to the two-fold coincidence in $`c^{}`$ and $`d^{}`$.

A single photon in mode $`a`$ yields a contribution $`\widehat{b}^{}\widehat{c}^{}\widehat{d}^{}`$, indicating that there is a two-fold coincidence in mode $`c^{}`$ and $`d^{}`$, and a single photon in the output mode $`b^{}`$. As can be seen if Eqs.(11,12), the probability of success for this interferometric device is given by 1/8. By adjusting the transmission coefficients of the beam splitters in modes $`c`$ and $`d`$, the probability of success can be increased further. Obviously, this scheme does not work when the incoming state has an unknown polarization. However, it turns out that a more sophisticated interferometric setup with polarization beam splitters can do the job while preserving the unknown polarization . Of course, such a scheme is not a full QND measurement of the photon-number observable, since it works for only zero, one, and two photons. It can, however, still play an important role in linear optical quantum computation, where up to only two photons are used in each logic gate . Furthermore, such a single-photon QND device can be used in various quantum communication protocols such as quantum repeaters .

## 5 Summary

Linear optics with projective measurements, can be used to replace the use Kerr nonlinearities and provide a much higher efficiency. Using this technique, we have studied the generation of useful photonic quantum correlations. The maximally path-entangled photon-number states provide an essential way for optical lithography to proceed beyond the Rayleigh diffraction limit. The Yurke-type path-entanglement is of particular importance in Heisenberg-limited interferometry. Projective measurements also enable us to construct a device that signals the presence of a single photon without destroying it. Single-photon non-demolition measurement is of great importance in quantum information processing with photons, since most error-correction codes in the presence of qubit loss requires QND measurements .

This work was carried out at the Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronautics and Space Administration. The authors wish to thank C. Adami, N.J. Cerf, J.D. Franson, G.J. Milburn, W.J. Munro, T.B. Pittman, and T.C. Ralph for helpful discussions. We would like to acknowledge support from the NASA Intelligent Systems Program, the National Security Agency, the Advanced Research and Development Activity, the Defense Advanced Research Projects Agency, the National Reconnaissance Office, the Office of Naval Research, and the Army Research Office. P.K. thanks the National Research Council and NASA Code Y for support.

## References


text:
# Effects of Helium Phase Separation on the Evolution of Giant Planets

## 1 Introduction

The interiors of Jupiter and Saturn, extrasolar giant planets (EGPs), and brown dwarfs (BDs) are all described by similar physics: these bodies are mainly composed of liquid metallic hydrogen, and their interior energy transport mainly occurs through efficient convection Hubbard et al. (2002), leading to largely isentropic interiors. Jupiter and Saturn, whose radius, mass, luminosity, and age are known precisely, can serve as calibrators of thermal-history calculations for the entire class of objects. They can provide a test of the adequacy of the diverse physical models, including interior thermodynamics, heat transport mechanisms, and model-atmosphere grid, that enter into the general thermal-history theory for EGPs and BDs. However, at very low effective temperatures ($``$ 100 K), the corresponding interior temperatures may become low enough for phase separation of abundant interior components to occur, and this effect must be quantitatively evaluated before Jupiter and Saturn can be used as calibrators. This work provides a quantitative assessment of inhomogeneous evolution in Jupiter, Saturn, and low-mass EGPs.

Relevant calculations and data for Jupiter and Saturn follow:

* Saturn is currently over 50% more luminous than one would predict with a homogeneous, adiabatic cooling model. Saturn models reach the planet’s known $`T_{eff}`$ of 95.0 K in only 2.0 to 2.5 Gyr Fortney & Hubbard (2003).
* For Jupiter, homogeneous, adiabatic cooling models allow Jupiter to reach its known $`T_{eff}`$ of 124.4 K in $``$ 4.7 Gyr. This is a good match.
* The atmospheres of both Jupiter and Saturn are depleted in helium relative to the expected protosolar helium mass fraction of $`0.27`$. $`Y_{atmos}`$ for Jupiter is 0.231 von Zahn et al. (1998) and for Saturn is likely 0.18-0.25 Conrath & Gautier (2000), but is poorly constrained.

## 2 Hydrogen and Helium under High Pressure

Under extreme pressure dense molecular hydrogen dissociates and ionizes to become liquid metallic hydrogen. The transition is likely continuous over a pressure of 1-5 Mbar at the temperatures of interest ($`10^4`$ K) in giant planets. Also at these temperatures, helium, which makes up about 8% of the atoms in a solar composition mixture, likely becomes immiscible in liquid metallic hydrogen Stevenson (1975); Hubbard & Dewitt (1985); Pfaffenzeller et al. (1995). Figure 1 shows the interior temperature-pressure profile of Jupiter and Saturn superimposed on a hydrogen phase diagram.

Detailed calculations on the dynamics and distribution of helium in giant planets have been performed Stevenson & Salpeter (1977b). These authors found that when helium becomes immiscible in liquid metallic hydrogen, the composition that separates out is essentially pure helium, and this helium on fairly short timescales (relative to the convective timescale) will coalesce to form helium droplets. These droplets, being denser than the surrounding liquid metallic hydrogen, will fall through the planet’s gravitational field. If the droplets reach a region where helium is again miscible at higher concentration, they will redissolve, enriching the deeper regions of the planet in helium. Helium would be lost from $`all`$ regions with pressures lower than the pressures in the immiscibility region, since the planet is fully convective up to the atmosphere. Excess helium would be mixed down to the immiscibility region and be lost to deeper layers. This “helium rain” could be a substantial additional energy source for giant planets.

## 3 Calculations

We find that the calculated phase diagram of HDW Hubbard & Dewitt (1985), which is essentially equivalent to that of Stevenson Stevenson (1975), are inapplicable to the interiors of giant planets, if helium phase separation is Saturn’s only additional energy source. As Figure 2 shows, this phase diagram prolongs Saturn’s cooling 0.8 Gyr, even in the most favorable circumstance that all energy liberated is available to be radiated, and does not instead go into heating the planet’s deep interior. As we show in our published work Fortney & Hubbard (2003), we find that a modified version of the phase diagram of Pfaffenzeller et al. Pfaffenzeller et al. (1995), with a higher temperature for the onset of helium immiscibility (see Figure 1), allows Saturn to reach its known $`T_{eff}`$ and age, while Jupiter evolves homogeneously until $`t`$ 5 Gyr. Saturn’s $`Y_{atmos}`$ falls to 0.185 at 4.5 Gyr, which is at the low end of Saturn’s derived value Conrath & Gautier (2000).

This modified phase diagram can be applied to various hypothetical giant planets Fortney & Hubbard (2004). We follow the evolution of planets with masses from 0.15 $`M_\mathrm{J}`$ (1/2 Saturn’s mass) to 3.0 $`M_\mathrm{J}`$. Figure 3 shows the evolution of these planets with and without the effects of helium phase separation. These planets are in isolation and possess 10 $`M_{\mathrm{Earth}}`$ cores. At Gyr ages the model planets undergoing phase separation can have $`T_{eff}`$s 10-15 K higher than the homogeneous models, making the planets somewhat easier to detect.

We thank Adam Burrow, Dave Sudarksy, & Tristan Guillot for interesing conversations. JJF is funded by a NASA GSRP Fellowship and WBH by a NASA PG&G grant.


text:
# Porosity dependence of sound propagation in liquid 4He filled aerogel

## Abstract

Longitudinal sound wave propagation has been studied in an aerogel-liquid 4He system for various porosities of aerogel. The superfluid transition was identified as the absorption peak, whose magnitude was suppressed by aerogel. The sound velocity was analyzed within a hydrodynamic theory in both normal and superfluid phases. The absorption peak due to phonon-roton interaction around 1 K was not observed even with the most porous aerogel. The low temperature sound velocity and attenuation show that direct collisions of phonons with aerogel strands plays an important role in the acoustic properties.

preprint: APS/123-QED

Porous media filled with fluid have been intensively studied experimentally and theoretically because of their physical and technological importance. The effect of disordered pore structures on the properties of the fluid can be examined in these systems. There has been considerable interest in the behavior of superfluid 4He in the presence of a random disorder induced by highly open porous media. Recent experiments on the superfluid transition of 4He contained in porous media such as Aerogel, Xerogel and Vycor glass have revealed that the superfluid transition differs from that of bulk 4He Wong ; Chan . The superfluid transition of 4He in aerogel has been observed to be sharpWong ; Chan , and has suggested to manifest a genuine phase transition. The transition temperature in aerogel Tc has been suppressed with decreasing aerogel porosity.

Understanding the results of acoustic experiments is important when dealing with porous media. Use of liquid 4He offers unique advantages due to the existence of the superfluid phase with more than one sound mode. The bulk fluid displays two propagating modes: first sound (a compressional wave) and second sound (a temperature wave)Khalatnikov . In a porous media where the normal component is clamped by its viscosity and only the superfluid component can move, fourth sound (relative motion of the superfluid and normal fluids) propagates and can be used to determine the superfluid fraction.

Longitudinal and transverse ultrasound velocity have been measured in 4He filled Vycor glassBeamishHikata . Warner and BeamishWarnerBeamish  studied the transverse sound velocity and attenuation in alumina ceramics with various porosities. They argued that the experimental results in both the low and high frequency regimes for normal and superfluid phases can be quantitatively elucidated by the Biot modelBiot1 ; Biot2 ; Biot3 ; Biot4 .

Silica aerogels are synthesized via a sol-gel process and hypercritical drying which enable production of tenuous solids with porosity $`\varphi `$ as large as 99.8 $`\%`$ and unique acoustic properties. Silica aerogel is thought of as a network of nanoscale SiO2 strands. The elastic moduli of aerogels are a few orders of magnitude smaller than that of bulk solids and the sound speed substantially depends on the porosity. Ultrasound measurements have shown sound speeds as low as 20 m/s for the highest porosity aerogelFricke .

The high-porosity aerogels are so soft that the aerogel matrix and the clamped normal fluid moves as the results of pressure and temperature gradients, unlike other porous media. This results in sound modes intermediate between first and fourth soundMaKenna1  and a second-sound-like modeMaKenna2 . McKenna et al. MaKenna2  calculated the longitudinal sound velocity for the two modes using modified two-fluid hydrodynamic equations in order to take aerogel motion into consideration. They also observed the propagation of both the fast (intermediate between first and fourth sound) and the slow (second-sound-like) modes in 4He in aerogel from 1.1 K to Tc. They found agreement of the model with the observed sound velocity within the experimental temperature range.

We have observed the 10 MHz longitudinal ultrasound signal with three different porosity (92.6, 94.0 and 94.8 %) aerogels from 0.5 to 4.2 K, and measured the sound velocity and attenuation in order to study sound propagation in the liquid 4He filled aerogel system both in the normal and superfluid phases. Preliminary results have been published elsewhereMatsumoto12 . The viscous penetration depth of liquid 4He at 10 MHz (about 40 nm) is estimated to be longer than the typical SiO2 strand distance (about 10 nm for 98 % aerogel and much shorter for 95 %) ; thus the normal fluid in these systems is expected to be completely locked to aerogel matrix by viscosity. The sound velocity of aerogel largely depends on the porosity so that we can obtain an aerogel whose sound velocity is larger or smaller than that of bulk fluid. Sound experiment with aerogel has an advantage to investigate what happens when the relation of sound velocities between fluid and porous media is changed.

Three aerogels were grown by a sol-gel process from tetramethoxysilane (TMOS) as a one step process. The porosities were determined using a standard dry weight method. We machined aerogels into cylinders (7 mm in diameter) which were enclosed in brass shells of 8.5 mm diameter and 3.0 mm length. The ends of the samples were polished flat and parallel. The sample cylinder was sandwiched between two LiNbO3 transducers with springs. We used the same pair of transducers for every sample in order to easily compare the signal attenuation among aerogels. Aerogels were immersed in liquid 4He at SVP. Temperatures were measured with a ruthenium oxide resistance thermometer and stabilized using a PI controller. The ultrasonic measurements were made using a standard pulse transmission and a phase sensitive detection technique.

We were able to observe the sound signal throughout the temperature range from 0.5 to 4.2 K. The transmitted sound signal through the aerogel in a vacuum, however, could not be observed because of the imperfect connection between the transducers and aerogel or large attenuation from the aerogel itself.

Figure 1 and 2, respectively, shows the sound velocity $`c`$ and attenuation $`\alpha `$ for the three aerogels as a function of temperature; for comparison, those of bulk helium obtained in a different run were plotted as well. The superfluid transitions Tc were identified as a dip in velocity and by an absorption peak for each aerogel. Those in aerogels were as sharp as in bulk, which represented a homogeneous transition in aerogel. Tc in aerogels is 2.165, 2.168, and 2.168 K for 92.6, 94.0, and 94.8 % porosity, respectively. The magnitude of Tc suppression and porosity dependence agree with specific heat measurementWong ; Chan .

The temperature dependence of the sound velocity is similar to that of bulk for each aerogel. The absolute value varies inversely to the porosity. In ordinary porous media, the sound velocity is modified by tortuosity and the acoustic index $`n`$ decreases with increasing porosity. The absolute value varies in opposition to the porosity dependence of the acoustic index; thus, tortuosity may not explain the behavior, but may still have an effect. The observed signal results from a compressional wave within liquid helium modified by aerogel.

The similarity of the temperature variation brings a scaled behavior to mind. Velocity for each aerogel and bulk liquid was scaled as $`(c(T)c(4.2K))/(c(2.5K)c(4.2K))`$ and $`(c(T)c(T_c))/(c(0.5K)c(T_c))`$ in normal and superfluid phase, respectively. The scaled temperature variations in the normal phase for each aerogel and for bulk liquid coincide with each other as shown in the inset of Fig. 1. This means the temperature variation is determined mainly by the bulk liquid. However, that in the superfluid phase depends on the porosity. We will discuss this behavior in detail below. It is useful to compare it with the longitudinal sound velocity in 4He filled VycorBeamishHikata . In the normal phase, the sound velocity in the Vycor system was almost constant, reflecting the constant sound velocity of Vycor glass. Contrary to the aerogel case, Vycor glass dominated the sound velocity of the composite system.

In a series of papersBiot1 ; Biot2 ; Biot3 ; Biot4 , Biot proposed a phenomenological theory of acoustic propagation in porous, fluid filled, macroscopically homogeneous and isotropic media. We applied Biot’s theory in the low frequency limit since the viscous penetration depth is larger than the mean separation of SiO2 strands. Biot argued that there are two (fast and slow) modes in the composite system. The observed signal in the present study corresponds to the fast mode. The corresponding mechanical properties of aerogel and the complex system were evaluated by fitting the experimental data for each aerogel. We could fit the temperature dependence with this theory only if the coupling constant was nearly zero or even negative for each aerogel. As shown by JohnsonJohnson , $`n`$ is given as square root of the coupling constant so that this becomes nearly zero. According to this, $`n`$ as evaluated by the Biot theory had no physical meaning. The Biot theory is applicable to a situation in which sound propagation is mainly determined by a solid and fluid provides a small perturbation to the system and works well in 4He filled VycorBeamishHikata  and alumina ceramicsWarnerBeamish . The equation which represents the sound velocityJohnson  has no analytical solution in the case that sound velocity of solid and liquid is close. The aerogel-liquid 4He system is really this case. We concluded that Biot’s theory is not applicable to the aerogel-liquid 4He case.

Here we present only a very simple phenomenological model for sound propagation in the normal phase, a more complicated theory will be published elsewhereMatsuTayu . On the assumption that two different elastic media (the fluid and aerogel) are in parallel, the bulk modulus of the composite medium $`K_m`$ can be estimated to be $`\varphi K_{He}+K_a`$ using that of the fluid $`K_{He}`$ and aerogel $`K_a`$. The total density is expressed using the density of aerogel $`\rho _a`$, that of liquid helium $`\rho _{He}`$ and $`\varphi `$ as $`\rho _a+\varphi \rho _{He}`$. Then, the sound velocity, c is expressed as

$$c^2=\frac{\varphi K_a+K_{He}}{\rho _a+\varphi \rho _{He}}=\frac{c_a^2\rho _a+\varphi c_{He}^2\rho _{He}}{\rho _a+\varphi \rho _{He}},$$
(1)
where $`c_a`$, $`c_{He}`$ is the sound velocity of aerogel and that of liquid helium, respectively.

Equation 1 has been used to estimate the sound velocity of aerogel by fitting the temperature dependence of the observed sound velocity in the normal phase. The aerogel sound velocities are assumed to be constant with temperature, considering other experimentsXieBeamish ; DaughtonMulders . The best fitting is obtained with the aerogel sound velocity, 256, 212, and 181 m/s for 92.6, 94.0 and 94.8 % porosity, respectively. These values are consistent with the sound velocity obtained by Gross et al.Fricke . We will use these values to analyze the sound mode in the superfluid phase.

For numerical calculations in the superfluid phase, we use two-fluid hydrodynamic equations which take into account the ability of aerogel to move Brusov . The velocities of three sound modes calculated for 92.6 and 94.8 % as above are shown in Fig. 3. The solid, broken and dotted line corresponds to fast, intermediate and slow mode, respectively. The sound velocity of these modes converges to that of bulk helium and aerogel, since there is neither normal component or viscous coupling between the two media at low temperatures. The slow mode velocity goes to zero at Tc. The intermediate acoustic mode includes the complicated motion of all three components in our system (normal and superfluid components and aerogel) and one needs additional investigations of coupling mechanism between 4He and aerogel to get more detailed pictures about this mode as well as two others. It is clearly shown that the experimentally observed sound mode corresponds to the fast mode; these agree well between 1 K and $`T_c`$ for all aerogels. However, the discrepancy becomes significant below 1 K. The calculated fast mode converges to the greatest sound velocity in the composite system (for 94.0 and 94.8 % aerogel - to bulk liquid velocity, for 92.6 % aerogel - to aerogel sound velocity). On the other hand, the experimentally observed sound velocities at low temperature are lower than the calculated values. The porosity dependence of the velocity could not result from the tortuosity as in the case of normal phase. Then, the coupling between liquid and aerogel should be considered apart from viscosity of the normal fluid. We compared mean free path of phonons and rotons and that determined geometrically by aerogel strands. The geometrically limited mean free path becomes shorter than that of phonons and rotons below 1K. Acoustic phonons are thought to be scattered by aerogel strands and to give rise to the momentum transfer between aerogel and phonons. This means that the simple hydrodynamic theory is not applicable to this temperature range because there is no mechanism of momentum transfer due to there being no viscous fluid. A new theory is necessary in which momentum transfer between aerogel and phonon should be taken into account as in the case of the liquid 3He-aerogel systemNagai . We applied the simple idea used in the normal phase to sound velocity at low temperatures because the ultrasound wavelength was long enough to regard the micro structure of aerogel as homogenous and there was only one fluid component. The calculated sound velocities using Eq. 1 and aerogel sound velocities obtained by fitting in the normal phase are slower than experimental ones for all aerogels; this may result from weaker coupling compared to the normal phase. A detailed coupling mechanism seems necessary to fit the sound velocity at low temperatures.

The attenuations in the normal phase were so large that the attenuation variations are experimental artifacts resulting from inadvertent interference between the ultrasound signal and electrical feed-through from the transducer and amplifier. There is no substantial porosity dependence in the normal phase. At Tc, a sharp absorption peak was observed for each aerogel as was observed in the bulk liquid. In the specific heat measurementWong ; Chan , two distinct singularities of specific heat were observed. The higher temperature singularities were verified as coincident with the bulk liquid singularities. In our experiment, the absorption peak which corresponds to the Tλ was not observed for every aerogel. In fact, the temperature resolution of our experiment was not as good as the specific heat measurementsWong ; Chan , but was adequate to distinguish between the peaks at Tc and Tλ. In the sound experiment, the attenuation due to the bulk liquid may be obscured by the large attenuation of the aerogel.

The observed constant attenuation in the superfluid phase below 1 K strongly depends on the porosity (or in other words on the density of SiO2 strands that act as scattering centers) and there is no temperature dependent contribution from phonons and rotons. This behavior qualitatively agrees with the geometrically limited mean free path picture. The general tendency of our results (attenuation is large in the normal phase and decreases with temperature in the superfluid phase) is similar to those of alumina ceramicsWarnerBeamish .

The absorption peak around 1 K which is observed in bulk liquid was not observed in the aerogel system. In the bulk liquid, the absorption peak is due to the phonon-roton interaction and the peak appears at the temperature that corresponds to $`\omega \tau 1`$, where $`\omega `$ is the angular frequency of sound and $`\tau `$ is the relaxation time. The absence of the attenuation peak can be qualitatively explained as follows: The phonon mean free path increases with decreasing temperature and finally exceeds the geometrically limited mean free path in the aerogel. The relaxation time is limited by the aerogel and cannot satisfy the relation $`\omega \tau 1`$, so that the attenuation peak is not observed. Similar peak suppression has been observed in the 4He-3He mixtureHardingWilks , where the existence of 3He excitations means that there will be more collisions, or in other words $`\tau `$ is smaller than that in pure 4He. The peak of the attenuation occurs at lower temperatures compared to pure 4He. Because of the lower temperature, the number of phonons and rotons is lower and the value of the peak attenuation is reduced compared to that of bulk 4He. The same scenario may apply in the aerogel-4He system.

In conclusion, we have studied the low temperature acoustic properties of a liquid 4He filled aerogel system for aerogels of various porosities and observed a compressional wave in both the normal and superfluid phases using 10 MHz ultrasound. It has been found that sound velocity and attenuation are strongly influenced by aerogel. The scaling behavior has been found in the normal phase. In the superfluid phase, the three sound modes are calculated from the hydrodynamic model and the observed sound mode has been shown to correspond to the fast mode. The attenuation peak due to the phonon-roton interaction has not been observed in the present system. The geometrical limited phonon mean free path by aerogel strand seems to play an important role in the acoustic properties at low temperature. More detailed theoretical consideration is in progressMatsuTayu .

This work was partially supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan. The authors would like to express their appreciation to H. Suzuki and S. Abe for their useful discussions. They also wish to thank T. Higaki for his contribution to the early stage of this study.