format: text

text:
# X-RAY RESONANCE OPACITY OF OXYGEN AND IRON IN AGN MCG–6-30-15

## 1 INTRODUCTION

The Seyfert 1 galaxy MCG–6-30-15 has been under extensive study with new and continuing observations from Chandra and XMM-Newton . The soft X-ray region exhibits a predominantly non-thermal continuum with ‘breaks’ or ‘spectral turnovers’ with anomalous widths and depths larger than expected due to lines or photoabsorption ‘edges’ (Branduardi-Raymont et al. 2000, Lee et al. 2001, Sako et al. 2001). The primary interest in MCG–6-30-15 stems from eariler ASCA observations of the hard X-ray spectrum that show the prominent 6.4 keV iron Kα line with a large redward component, interpreted as gravitational broadening of emission from the inner region of the accretion disc around a massive black hole (Tanaka et al. 1995). Similarly, the positions and widths of the soft X-ray features were interpreted as gravitational broadening and redshift of recombination emission of H- and He-like Oxygen, and other elements, by Branduardi-Raymont et al. (2000) using the XMM-Newton data. However, Lee et al. (2001) obtained higher resolution Chandra data with the HETG and explained the spectrum in terms of a ‘dusty warm absorber’ model, with Rydberg series of lines from highly charged oxygen and iron ions, without requiring relativistic emission. The HETG observations of MCG–6-30-15 show a prominent break or spectral turnover at $`17.5\AA `$ , at the edges corresponding to line opacity due to higher members of the Rydberg series 1s2 $``$ 1snp of O VII, and the onset of the Fe-L edges. Their model also includes Fe XVII and Fe XVIII lines in the shorter wavelength region $`\lambda <17.5`$ $`\AA `$ . At 22.05 $`\AA `$ Lee et al. identify resonant photoabsorption by a KLL resonance in O VI predicted earlier (Pradhan 2000), and a tentative identification of the O I resonance at $`23`$ $`\AA `$ . These observations appeared to corroborate the Lee et al. warm absorber model. However, whereas the Lee et al. model includes line opacity from O and Fe ions, it does not consider resonance opacity (with the exceptions noted above).

Recently Sako et al. (2002) have reported additional XMM-Newton RGS observations and analysis, reconfirming the conclusions of Branduardi-Raymont et al. (2000) as to gravitational broadening in MCG–6-30-15 . The XMM-Newton RGS data samples the longer wavelength region beyond that of the Chandra HETG, where Sako et al. find considerable differences between the observed flux and the dusty warm absorber model proposed by Lee et al. They also find O IV and O V features, in addition to the O VI feature found earlier. Although the Sako et al. model considers opacity sources from lines and resonances of the identified species (including iron oxides), they note in particular that there is insufficient opacity of O and Fe at the $`17.5\AA `$ break, and that the Lee et al. model overestimates the flux compared to observations. Hence they conclude that the shape and magnitude of the observed features are inconsistent with photoelectric absorption, and required Fe and O abundances, and reaffirm the model with relativistically broadened Ly$`\alpha `$ lines of ionized C,N, and O in irradiated accretion discs of MCG–6-30-15 , as well as another Seyfert 1 galaxy Mrk 766.

The two particular aims of this paper are: (i) to demonstrate resonance opacity from O and Fe ions as a significant contributor at $`17.5\AA `$ (in addition to line opacity), and (ii) to identify inner-shell resonant Kα absorption features from all O-ions, O I - O VI, that manifest themselves as the oxygen signature gap at 22-23 $`\AA `$ in MCG–6-30-15 . The general aim is to illustrate the level of detail and precision required for astrophysical models in order to model Chandra and XMM-Newton sources. Atomic parameters for line, resonant, and continnum absorption are computed using ab intio methods with relativistic fine structure. The calculated oscillator strengths and photoionization cross sections are related directly to the monochromatic opacity spectrum which, in turn, determines the emitted flux and absorption features.

## 2 THEORY AND COMPUTATIONS

Resonance opacity complements line and continuum opacity. The monochromatic absorption coefficient may be defined in terms the quantity differential oscillator strength $`\frac{df}{dϵ}`$ (e.g. Pradhan 2000, Nahar et al. 2001) which subsumes these forms of atomic opacity, including autoionizing resonances. We express the line (bound-bound) and the resonant $``$ non-resonant (bound-free) absorption coefficient in terms of $`\frac{df}{dϵ}`$

$$a^{bb}(ϵ)=N_if=N_i(\frac{\pi e^2}{mc})(\frac{2z^2}{\nu ^3})\frac{df}{dϵ};a^{bf}(ϵ)=N_i\sigma _{PI}(ϵ)=(4\pi ^2\alpha a_o^2)\frac{df}{dϵ},$$
(1)
and where Ni is the ion density, $`z`$ is the ion charge, and $`\nu `$ is the effective quantum number. The differential oscillator strength $`\frac{df}{dϵ}`$ = $`(\nu ^3/2z^2)f_{line}`$ for line opacity, and $`\frac{df}{dϵ}`$ = $`(1/4\pi ^2\alpha a_0^2)\sigma _{PI}`$, where $`f_{line}`$ is the oscillator strength, and $`\sigma _{PI}`$ is the photoionization cross section. The $`\frac{df}{dϵ}`$ thus enables equal representation in magnitude of the b-b and b-f absorption coefficients, and is the basic atomic quantity that determines monochromatic opacity. We compute the $`\frac{df}{dϵ}`$ for all ions under consideration from the oscillator strengths and photoionization cross sections obtained from elaborate and extensive relativistic close coupling calculations using the Breit-Pauli R-matrix (BPRM) method (Scott and Taylor 1982, Hummer et al. 1993, Zhang et al. 1999).

All atomic calculations reported in this work are new, and have been carried out using configuration interaction eigenfunction expansions for the seven core O-ions, O II - O VIII, and for Fe-ions Fe XVI, XVII, and XVIII. In addition to the bound-free results reported herein, line $`f`$-values are also calculated for O VI and O VII, and Fe XVI and Fe XVII, including transitions up to $`n`$ = 10 levels. While the voluminous atomic data calculations are still in progress, and will be reported separately, we present the results pertaining to resonances in the Kα complexes of O I - VI, and L-shell complex of Fe XVI.

## 3 RESULTS

In order to focus on the atomic physics of the opacity in the spectral region of the $`17.5\AA `$ turnover in the MCG–6-30-15 spectra, and the identification of resonant absorption from Kα complexes of O-ions and the LMM complex of Fe XVI, we consider the $`\frac{df}{dϵ}`$ for the relevant ions as obtained from ab initio calculations. In this report we eschew any modeling or fitting. While the relative magnitude of opacities depends on the densities, temperatures, ionization fractions, abundances etc. in a model, the actual spectral features — in energies and shapes — should be basically the same as the detailed structure in $`\frac{df}{dϵ}`$ .

Fig. 1 shows the Kα resonant complexes of oxygen, with inner-shell excitation in all O-ions O I - OVI. Photoabsorption cross sections are from the ground level, and the dominant components and the peak positions of resonances in each ion are shown. In fact each complex has several components; their positions may or may not coincide depending on the exact energies of the contributing angular and spin symmetries. For example, O I and O II show one single peak because the contributing final J$`\pi `$ symmetries all lie at the same energy ($`\pi `$ refers to the parity of the electronic state). On the other hand resonances begin to spread out with ion charge in O III and O IV, which also present more complicated resonance structures. The ground level of O III, $`1s^22s^2p^2(^3P_0)`$, photoionizes into the J = (1)o continuum of $`1s2s^22p^3`$ with the three components shown. O V has only one final J$`\pi (^1P^o)`$ since the initial level is $`1s^22s^2(^1S_0)`$. The KLL O VI is a twin component system discussed in detail in earlier works (Pradhan 2000, Nahar et al. 2001; the latter work includes Li-like C IV, O VI, and Fe XXIV). However, the O VI resonance at 21.87 $`\AA `$ is about an order of magnitude weaker than the stronger one at 22.05 $`\AA `$ ; the latter was identified in the MCG–6-30-15 spectrum by Lee et al. (2001; see Fig. 2 bottom panel). Most of these results for O-ions have been obtained for the first time (prior works on O I and O II resonances are discussed in Paerels et al. 2001, and below). The calculations also include the Kα resonant oscillator strengths $`\overline{f}_r`$ = $`_{\mathrm{\Delta }E_r}(df/dϵ)𝑑ϵ`$ values for all O-ions (to be presented later), that might potentially determine column densities for all ionization stages of oxygen.

Fig. 2(a) presents the $`\frac{df}{dϵ}`$ for O and Fe ions. The O VI and the Fe XVI results are shown including the background, whereas the O I - O V resonances are shown only around the peak values that would be manifest in the observed MCG–6-30-15 spectra (bottom panel). The observed absorption spectrum corresponds to the inverse of the opacity. Therefore in Fig. 2(b) we plot ($`\frac{df}{dϵ}`$ )-1, analogous to the $`1/\kappa (h\nu )`$ term in the integrand of the Rosseland harmonic mean for stellar opacities (e.g. Seaton et al. 1994), where $`\kappa _\nu `$ is the monochromatic opacity. The calculated opacity spectrum matches rather closely the observed spectra, and the large resonant opacity due to inner-shell excitation of six O-ions, O I - O VI, results in the gap or window in the 22-23 $`\AA `$ region clearly discernible in the Chandra MCG–6-30-15 spectrum by Lee et al. (2001). As observed, the O I resonance brackets this region on the longer wavelength side at 23.5 $`\AA `$ , and the stronger component of the O VI KLL at 22.05 $`\AA `$ on the shorter wavelength side.

The spectral turnover or break at $`17.5\AA `$ in Fig. 2 has been discussed by Sako et al. (2002) with respect to both Chandra and XMM-Newton observations. Their warm absorber model flux is overpredicted compared to observations due to ‘lack of O VII and Fe L opacity’ (Sako et al. , Fig. 11). Here we find that the highest O VI KL$`n`$ resonance series limit, as $`n\mathrm{}`$ lies at 17.42 $`\AA `$ . The resonances, towards the longer wavelength side $``$ 17.5 - 17.8 $`\AA `$ , converge to several $`n=2`$ thresholds $`1s2s(^3S_1,^1S_0)`$ and $`1s2p(^3P_{0,1,2}^o,^1P_1^o)`$. Resonances in O VI, up to $`n=50`$, have been fully resolved at about 70,000 energies with an effective quantum number mesh that enables equal resolution for each $`n`$-complex. The downward jump in the theoretical absorpton spectrum in ($`\frac{df}{dϵ}`$ )-1 at $`17.5\AA `$ (Fig. 2b) corresponds directly to the similar jump in the observed flux.

There are actually two discrete jumps as seen in Fig. 3. The enhancement is mainly due to the considerable oscillator strengths in the $`1snp`$ inner-shell resonant transitions, and occurs largely at the lower $`1s2s(^3S_1,^1S_0)`$ thresholds. The increase due to the higher 1s2pns series limits $`1s2p(^3P_{0,1,2}^o,^1P_1^o)`$ is much smaller. The wavelengths corresponding to these threshold span the range 17.74 ($`2^3S_1`$) - 17.55 ($`2^1S_0,2^3P_{0,1,2}^o`$) - 17.42 $`(2^1P_1^o)`$ $`\AA `$ . The O VI resonant absorption cross section, as $`\lambda 17.42`$ $`\AA `$ , rises by a factor of 28 above the background continuum cross section, approaching the $`n=2`$ excitation thresholds of O VII from below. Of course this is also the energy region corresponding to line opacity from the O VII $`1s^21snp`$ transitions (Lee et al. include up to $`n=5`$ in their model shown in the bottom panel of Fig. 2).

Also close to the $`17.5\AA `$ break are the lowest two resonances due to $`2p^53s^2`$ LMM complex of Fe XVI. The first (stronger) LMM resonance lies at 17.38 $`\AA `$ , but the Fe XVI bound-free continuum also has an appreciable value at the $`17.5\AA `$ (the second LMM resoanance is at 17.10 $`\AA `$ ). Moreover, the opacity from the next Rydberg complex in Fe XVI at $``$0.82 keV corresponds to the strong absorption feature in the Chandra MCG–6-30-15 spectrum (even higher $`n`$-complexes become weaker roughly as $`n^3`$).

## 4 DISCUSSION

A few salient points and implications of the present work are discussed.

K- and L-shell resonant absorption from O and Fe ions, respectively, should be a significant contributor to the missing or unidentified X-ray opacity in the warm absorber models of MCG–6-30-15 by Lee et al. (2001) and Sako et al. (2002). However the crucial question — whether the additional resonance opacity is sufficient, or whether relativistic emission still needs to be invoked — depends on the details of the model. In particular the ionic column densities and O:Fe abundances need to explain, for exmaple, the required optical depth of $``$0.7 at $`17.5\AA `$ . Nonetheless, it appears that most if not all atomic features in the observed spectrum may be theoretically modeled.

It appears likely that the Kα resonances of all ionization stages of oxygen are present in the Chandra MCG–6-30-15 spectrum. However, this presents rather a challenge to model, since the plasma source must necessarily imply a widely varying extended environment and/or intervening matter along the line of sight to the AGN. Whereas the O VI resonance opacity spectrum bears a striking resemblance to the observed spectra at the $`17.5\AA `$ , complementing O VII line opacity (Fig. 2), the two ionization stages may differ by an order of magnitude in temperature, depending on the preponderance of photoionization or coronal equilibrium (or a hybrid) of the (e + O VII) $``$ O VI system. We therefore suggest an observational study of the O VI UV $`\lambda \lambda `$ 1031,1038 $`\AA `$ doublet, cross-correlated with the O VI X-ray resonant absorption features described herein. The O VI KLL doublet absorption resonances at $`\lambda \lambda `$ 22.05 and 21.87 $`\AA `$ (Pradhan 2000) lie between the well known forbidden (‘f’ or ‘z’), intercombination (‘i’ or ‘x,y’), and allowed (‘r’ or ‘w’) emission lines of O VII due to transitions $`2(^3S_1,^3P_{2,1}^o,^1P_1^o)1(^1S_0)`$ at $`\lambda \lambda `$ 22.101, 21.804, and 21.602 $`\AA `$ respectively. To augment theoretical studies, new self-consistent cross sections and rates O VI/O VII/O VIII have been computed (Nahar and Pradhan, in preparation) using the same eigenfunction expansion for both photoionization and recombination, and a unified (e + ion) recombination scheme including both radiative and dielectronic recombination, in an ab initio manner using the relativistic BPRM method (e.g. Nahar and Pradhan 1995, Zhang et al. 1999). The accurate new O VII total and level-specific recombination rates and A-values, up to $`n`$ = 10 fine structure levels, should generally help the study of recombination lines, such as the O VII ‘He$`\beta ,\gamma ,\delta ,ϵ`$’ identified by Sako et al. (2002) in the XMM-Newton spectrum, and for which the model absorption widths are ‘severely overpredicted’. Fine structure collisional cross sections and rates for O VII have also been recently computed including up to $`n`$ = 4 levels (Delahaye and Pradhan 2002).

The shape of the oxygen gap in the observed flux at $``$ 0.55 keV (22-23 $`\AA `$ ) is similar to the one in the $``$ 0.94 keV region where Lee et al. (2001) have identified a line from He-like Ne IX ($`1s^21s2p`$). Based on the present study, inner-shell excitation from all Ne-ions should contribute to a ‘neon gap’ in this region. However, this gap would overlay the much stronger Fe L-shell opacity at all energies higher than the spectral break at $`17.5\AA `$ . Nonetheless, in general we might predict similar gaps due to other elements, such as carbon at $``$ 0.3 keV, nitrogen at $``$ 0.4 keV, neon at $``$ 0.9 keV, and from inner-shell Kα resonances in iron in the 6.4 - 6.7 keV range (the Kα complex in He-like iron at 6.7 keV, and Li-like dielectronic satellites at lower energies, are discussed by Oelgoetz and Pradhan 2001). These gaps or windows due to Kα resonant excitation in all ionization stages of an element would lie close together in the X-ray, and should be discernible (subject to the total opacity in that region). We note that the tentative identification by Lee et al. (2001) of the O I resonance in MCG–6-30-15 appears to be slightly higher in energy than the present value, and previous experimental and theoretical values at $`23.5`$ $`\AA `$ discussed by Paerels et al. (2001), who used the non-relativistic theoretical cross sections for O I computed by McLaughlin and Kirby (1998) to analyse interstellar X-ray absorption (the theoretical model spectrum was shifted by 0.051 $`\AA `$ to match the measured centroid wavelength of the O I resonance). Our O II Kα resonance is about 0.08 $`\AA `$ lower than inferred from experimental data; however, new calculations are in progress.

Line and resonance complexes are sometimes referred to as ‘unresolved transition arrays’ (UTA’s, e.g. Sako et al. 2002). The present work demonstrates that it may be necessary to highly resolve the UTA’s, and precisely calculate the resonance profiles and energies, to analyze the high resolution data from Chandra and XMM-Newton . Owing to the convergence of resonance series limits from below threshold, the inner-shell ionization ‘edges’ are always diffuse and exhibit redward broadening. The total resonance averaged photoabsorption cross section is an analytic continuation of the cross section from just above threshold; continuum lowering effects at resonance series limits should also be manifiest under appropriate plasma conditions.

In Fig. 1 we have presented only the Kα photoabsorption cross sections from the ground level of O-ions. Excited fine structure levels of the ground LS term may also be significantly populated; resonances in these excited level cross sections will also contribute to the absorption spectrum. As mentioned, we are computing comprehensive datasets for line $`f`$-values and photoionization cross sections of O-ions and Fe XVI, XVII, and XVIII, that should provide a more complete description of oxygen K-shell opacity for $`\lambda >`$17.5 $`\AA `$ , and iron L-shell opacity for $`\lambda <`$17.5 $`\AA `$ in the region covered by both Chandra and XMM-Newton .

## 5 CONCLUSION

Comparison of ab initio theoretical atomic parameters that determine the X-ray opacity of O and Fe with the high-resolution Chandra and XMM-Newton observations reveal some spectral features heretofore unobserved in laboratory or astrophysical sources. We note the following main conclusions:

$``$ Inner-shell Kα resonances from all O-ions O I - OVI are identified and associated with the window observed in the X-ray flux at $``$ 22-23 $`\AA `$ — spectral signature of oxygen absorption from an ‘all-component’ (mainly) optically thin plasma. Column densities of all ionization stages may be obtained using the calculated resonance oscillator strengths $`\overline{f}_r`$ , and should provide stringent constraints on parameters such as temperatures and ionization fractions in photoioization models.

$``$ Resonance series limits in O VI, and LMM resonances in Fe XVI, should contribute significantly to the opacity at the spectral $`17.5\AA `$ break in the 17.4 - 17.7 $`\AA `$ range, possibly accounting for the missing O and Fe opacity to resolve the discrepancy between the the relativistic redshift and broadening model, and the dusty warm observer model.

$``$ In general, high precision resolution of resonances is essential for theoretical X-ray models to match the high-resolution spectra of Chandra and XMM-Newton , as astrophysical laboratories of fundamental atomic and plasma physics.

This work was partially supported by the NASA Astrophysical Theory Program. The computational work was carried out on the Cray SV1 at the Ohio Supercomputer Center in Columbus, Ohio.


text:
# 1 Introduction

## 1 Introduction

It is a fundamental rule of quantum computation that if a state $`q`$ has an amplitude of $`\sigma `$, then $`q`$ will be observed not with probability $`\sigma `$ but with probability $`\sigma ^2`$. Therefore, if one can increase the amplitude of $`q`$ twice, i.e., from $`\sigma `$ to $`2\sigma `$, then the corresponding probability increases four times, i.e., $`\sigma ^2`$ to $`4\sigma ^2`$. In general, if the amplitude increases $`k`$ times then the probability increases $`k^2`$ times. One observation of the Grover search \[Gro96\], which is apparently one of the most celebrated quantum algorithms, is that it takes advantage of this fact cleverly, by inventing the (efficient) quantum process whose $`k`$ iterations increase the amplitude of a designated state roughly $`k`$ times. As described above, this is equivalent to increasing the probability $`k^2`$ times. Thus the Grover search is faster quadratically than the classic randomized search whose $`k`$ iterations can increase the probability only $`k`$ times.

In this paper, we also exploit this feature, i.e., the difference in probability calculation between quantum and probabilistic computations, but from a bit different angle: Suppose that there are ten pairs of state $`(p_1,q_1),\mathrm{},(p_{10},q_{10})`$ where, for each $`1i10`$, either $`p_i`$ or $`q_i`$ has the amplitude $`1/\sqrt{10}`$ (we say that $`p_i`$ is ON if it has the amplitude and OFF otherwise.). We wish to know how many $`p_i`$’s are ON. This can be done by “gathering” amplitudes by applying a Fourier transform from $`p_i`$’s to $`r_i`$’s and by observing $`r_{10}`$ (see later sections for details). If all ten $`p_i`$’s are ON, then the amplitude of $`r_{10}`$ after Fourier transform is one and it is observed with probability one. If, for example, only three $`p_i`$’s are ON, then the amplitudes of $`r_{10}`$ is 3/10 and is observed with probability 9/100. In the case of probabilistic computation, we can also gather the probability of $`p_i`$’s ($`=`$ 1/10 for each) simply by defining (deterministic) transitions from $`p_i`$ to $`r_{10}`$. If all pairs are ON, then the probability that $`r_{10}`$ is observed is one again, but if only three $`p_i`$’s are ON, its probability is 3/10. If the latter case (only three $`p_i`$’s are ON) is associated with some erroneous situation, this probability, 3/10, is much larger than 9/100 in the quantum case. In other words quantum computation can enjoy much smaller error-probability due to the difference in the rule of probability calculation.

The question is of course whether we can turn this feature into some concrete result or how we can translate this difference in probability into some difference in efficiency like time and space. In this paper we give an affirmative answer to this question by using quantum finite automata; we prove that there is a finite language $`L`$ which contains sentences of length up to $`O(n^{c+1})`$ such that: ($`i`$) There is a one-way quantum finite automaton (qfa) of $`O(n^{c+4})`$ states which recognizes $`L`$. ($`ii`$) However, if we try to simulate this qfa by a probabilistic finite automaton (pfa) using the same algorithm, then it needs $`\mathrm{\Omega }(n^{2c+4})`$ states. It should be noted that we do not prove real lower bounds for pfa’s but show that if pfa’s and qfa’s use exactly the same algorithm (the only difference is the way of gathering amplitudes mentioned above), then qfa’s need much less states.

Quantum finite automata have been popular in the literature since its simplicity is nice to understand merits and demerits of quantum computation\[AF98, AG00, AI99, ANTV99, KW97, Nay99\]. Ambainis and Freivalds \[AF98\] proved an exponential difference in the size of qfa’s and pfa’s for a one-letter language. Their technique highly depends on the rotation of complex amplitudes, which is exceptionally powerful for a certain situation. Nayak\[Nay99\] gave a negative side of qfa’s by showing $`L_n=\{wa|w\{a,b\}^{}and|w|n\}`$ needs exponentially more states for qfa’s than for dfa’s. $`L_{\mathrm{}}`$ is a regular set but is not recognizable by qfa’s as shown by Kondacs and Watrous\[KW97\]. \[KW97\] also introduced 2-way qfa’s which can recognize non-regular languages. To our best knowledge, the notion of gathering amplitudes using Fourier transform appeared in this paper for the first time and played an important role in \[AI99\], too.

## 2 Problem EQ

Suppose that Alice and Bob have $`n`$-bit numbers $`x`$ and $`y`$ and they wish to know whether or not $`x=y`$. This problem, called EQ, is one of the most famous problems for which its randomized communication complexity ($`=\mathrm{\Theta }(\mathrm{log}n)`$) is significantly smaller than its deterministic counterpart ($`=n+1`$) \[KN97\]. In this paper, we need a little bit more accurate argument on the value of randomized (and one-way) communication complexity: Consider the following protocol $`M_{EQ}`$: ($`i`$) Alice selects a single prime $`p`$ among the smallest $`N`$ primes. ($`ii`$) Then she divides $`x`$ by $`p`$ and sends Bob $`p`$ and the residue $`a`$. ($`iii`$) Bob also divides his number $`y`$ by $`p`$ and compares his residue with $`a`$. They accept $`(x,y)`$ iff those residues coincide.

It is obvious that if $`x=y`$ then protocol $`M_{EQ}`$ accepts $`(x,y)`$ with probability one. Let $`E(N)`$ be the maximum (error) probability that $`M_{EQ}`$ accepts $`(x,y)`$ even if $`xy`$. To compute $`E(N)`$, we need the following lemma: (In this paper, $`\mathrm{log}n`$ always means $`\mathrm{log}_2n`$ and $`f(n)`$ for a function $`f(n)`$ is simply written as $`f(n)`$.)

Lemma 1. Suppose that $`xy`$ and let $`S(x,y)`$ be a set of primes such that $`x=y`$ mod $`p`$ for all $`p`$ in $`S(x,y)`$. Also, let $`s`$ be the maximum size of such a set $`S(x,y)`$ for a pair of $`n`$-bit integers $`x`$ and $`y`$. Then $`s=\mathrm{\Theta }(n/\mathrm{log}n)`$.

Proof. Let $`p_i`$ be the $`i`$-th largest prime and $`\pi (n)`$ be the number of different primes $`n`$. Then the prime number theorem says that $`lim_n\mathrm{}\frac{\pi (n)}{n/\mathrm{log}_en}=1`$, which means that $`p_{n/\mathrm{log}n}=\mathrm{\Theta }(n)`$. Consequently, there must be a constant $`c`$ s.t. $`p_1p_2\mathrm{}p_{n/\mathrm{log}n}\mathrm{}p_{cn/\mathrm{log}n}>p_{n/\mathrm{log}n}p_{n/\mathrm{log}n+1}\mathrm{}p_{cn/\mathrm{log}n}>2^n`$ since $`n^{n/\mathrm{log}n}=2^n`$. Thus an $`n`$-bit integer $`z`$ has at most $`cn/\mathrm{log}n`$ different prime factors. Note that $`x=y`$ mod $`a`$ iff $`|xy|=0`$ mod $`a`$. Hence, $`scn/\mathrm{log}n`$. Also it turns out by the prime number theorem that there is an $`n`$-bit integer $`z`$ such that it has $`c^{}n/\mathrm{log}n`$ different prime factors for some constant $`c^{}`$, which proves that $`sc^{}n/\mathrm{log}n`$.

In this paper, $`N_0`$ denotes this number $`s`$ which is $`\mathrm{\Theta }(n/\mathrm{log}n)`$. Then

Lemma 2. $`E(N)=N_0/N`$.

For example, if we use $`N=n^2/\mathrm{log}n`$ different primes in $`M_{EQ}`$, its error-rate is $`1/n`$.

## 3 Our Languages and qfa’s

A one-way qfa is the following model: ($`i`$) Its input head always moves one position to the right each step. ($`ii`$) Global state transitions must be unitary. ($`iii`$) Its states are partitioned into accepting, rejecting and non-halting states. ($`iv`$) Observation is carried out every step, and if acceptance or rejection is observed, then the computation halts. Otherwise, computation continues after proportionally distributing the amplitudes of accepting and rejecting states to non-halting states. We omit the details, see for example \[KW97\]. In this paper, we consider the following three finite languages.

$`L_0(n)=\{w\mathrm{}w^Rw\{0,1\}^n\},`$

$`L_1(n)=\{w_1\mathrm{}w_2\mathrm{}\mathrm{}w_3\mathrm{}w_4\mathrm{}w_1,w_2,w_3,w_4\{0,1\}^n,(w_1=w_2^R)((w_1w_2)=(w_3w_4)^R)\},`$

$`L_2(n,k)=\{w_{11}\mathrm{}w_{12}\mathrm{}\mathrm{}w_{13}\mathrm{}w_{14}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}w_{i1}\mathrm{}w_{i2}\mathrm{}\mathrm{}w_{i3}\mathrm{}w_{i4}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}w_{k1}\mathrm{}w_{k2}\mathrm{}\mathrm{}w_{k3}\mathrm{}w_{k4}\mathrm{}`$
$`w_{i1}`$, $`w_{i2}`$, $`w_{i3}`$, $`w_{i4}`$ $`\{0,1\}^n`$$`1ik`$
and $`1jk`$ s.t. ($`w_{j1}=w_{j2}^R`$) $``$ (for all $`1ij1`$, $`(w_{i1}w_{i2})=(w_{i3}w_{i4})^R`$)}.

In the next section, we first construct a qfa $`M_0^Q`$, which accepts each string $`xL_0`$ with probability 1 and each string $`yL_0`$ with probability at most $`\frac{1}{n}`$. $`M_0^Q`$ simulates the protocol $`M_{EQ}`$ in the following way (see Fig 1). Given an input string $`c/w_1\mathrm{}w_2\$`$ ($`c/`$ is the leftmost and $ is the rightmost symbols), $`M_0^Q`$ first splits into $`N`$ different states $`q_{p_1},\mathrm{},q_{p_i},\mathrm{},q_{p_N}`$ with equal amplitudes by reading $`c/`$. Then from $`q_{p_i}`$, submachine $`M_{1i}`$ starts the task for dividing integer $`w_1`$ by the $`i`$-th prime $`p_i`$. This computation ends up in some state of $`M_{1i}`$ which corresponds to the residue of the division. This residue is shifted to the next submachine $`M_{2i}`$, and then $`M_{2i}`$ carries out a completely opposite operation while reading $`w_2`$. If (and only if) two residues are the same, $`M_{2i}`$ ends up in some specific state $`q_i^0`$. $`M_0^Q`$ then applies a Fourier transform from $`q_i^0`$ to $`s_i`$ for $`1iN`$. $`M_0^Q`$ thus simulates $`M_{EQ}`$ by setting $`s_N`$ as its only accepting state.

For the probabilistic counterpart, pfa $`M_0^P`$, we can use exactly the same state transition, except for deterministic transitions from $`q_i^0`$ to $`s_N`$. As mentioned before we can achieve a quadratic difference in the probability of error, like $`(1/n)^2`$ for $`M_0^Q`$ v.s. $`(1/n)`$ for $`M_0^P`$. It would be nice if this quadratic difference of error can be traded directly to a quadratic difference in the necessary number of primes or to a quadratic difference in the size of automata. Unfortunately that is not possible: The main reason is that we do not need such a small (like $`1/n`$ or $`1/n^2`$) error-rate but something like 1/3 is enough by definition. Then the quadratic difference in the error is reduced to a difference between, say, 1/3 and 1/9, which means only a difference of the constant factor in the necessary number of primes or the necessary number of states.

There is a standard technique to overcome this difficulty, namely, the use of iteration. Consider the following string:

$$w_{11}\mathrm{}w_{12}\mathrm{}\mathrm{}w_{21}\mathrm{}w_{22}\mathrm{}\mathrm{}\mathrm{}\mathrm{}w_{n1}\mathrm{}w_{n2}$$

where the accepting condition is that for some $`1jn`$, $`w_{j1}=w_{j2}^R`$. When all pairs $`(w_{j1},w_{j2})`$ do not satisfy this condition, the (error) probability of accepting such a string is roughly $`O\left(\frac{1}{n}\right)\times n=O(1)`$, which appears desirable for our purpose.

This argument does not seem to cause any difficulty for pfa’s but it does for qfa’s for the following reason: After checking $`w_{11}`$ and $`w_{12}`$, the qfa is in a single accepting state if the condition is met, which is completely fine. However, if $`w_{11}w_{12}^R`$ and the observation is not accepting, then there are many small amplitudes distributed to many different states. Note that we have to continue the calculation for $`w_{21}`$ and $`w_{22}`$ which should be started from a single state. (It may be possible to start the new computation from each non-halting state, but that will result in an exponential blow-up in the number of states, which again implies no clear separation in the size of automata.) One can see easily that we cannot use a Fourier transform this time to gather the amplitudes since there are many different patterns in the distribution of states which have a small nonzero amplitudes.

This is the reason why the next language $`L_1(n)`$ plays an important role. Suppose that $`w_1w_2^R`$. Then the resulting distribution of amplitudes is quite complicated as mentioned above. However, no matter how it is complicated, we can completely “reverse” the previous computation for $`w_1\mathrm{}w_2`$ by reading $`w_3\mathrm{}w_4`$ if $`(w_1w_2)=(w_3w_4)^R`$. This reverse computation should end up in a single state of amplitude one (actually it is a little less than one) since the original computation for $`w_1w_2^R`$ starts from the (single) initial state. Now one can use the iteration scheme, which naturally leads us to the third language $`L_2(n,k)`$.

## 4 Main Results

As mentioned in the previous section, we construct our qfa’s and corresponding pfa’s for $`L_0(n)`$, $`L_1(n)`$ and $`L_2(n,n^c)`$ in a step-by-step fashion. Recall that $`N`$ is the number of primes used in protocol $`M_{EQ}`$ and $`N_0=\mathrm{\Theta }(n/\mathrm{log}n)`$.

Lemma 3. There exists a qfa $`M_0^Q`$ which accepts strings in $`L_0`$ with probability one and strings not in $`L_0`$ with probability at most $`\left(\frac{N_0}{N}\right)^2`$. The number of states in $`M_0^Q`$ is $`\mathrm{\Theta }(N^2\mathrm{log}N)`$.

Proof. $`M_0^Q`$ has the following states: ($`i`$) An initial state $`q_0`$, ($`ii`$) $`q_{p_k,j_k,1}`$ (in submachine $`M_{1i}`$ of Fig 1), ($`iii`$) $`q_{p_k,j_k,2}`$ (in $`M_{2i}`$ of Fig 1), ($`iv`$) $`q_{p_k,j_k,rej}`$ (also in $`M_{2i}`$ of Fig 1), ($`v`$) $`s_l`$, where $`1kN`$, $`0j_kp_k1`$ and $`1lN`$. $`p_k`$ denotes the $`k`$-th largest prime $`>3`$ (two is excluded for the reason mentioned later). $`s_N`$ is the only accepting state, $`q_{p_k,j_k,rej}`$ and $`s_l`$ ($`1lN1`$) are rejecting states and all the others are non-halting states. We give a complete state transition diagram of $`M_0^Q`$ in Table 1, where $`V_\sigma |Q=\alpha _1|Q_1+\mathrm{}+\alpha _i|Q_i+\mathrm{}+\alpha _m|Q_m`$ means that if $`M_0^Q`$ reads symbol $`\sigma `$ in state $`Q`$, it moves to each state $`Q_i`$ with amplitude $`\alpha _i`$ ($`|\alpha _1|^2+\mathrm{}+|\alpha _m|^2=1`$).

When reading $`c/`$ of the input string $`c/w_1\mathrm{}w_2\$`$, $`M_0^Q`$ splits into $`N`$ submachines (denoted by $`M_{1i}`$ in Fig 1) with equal amplitudes (see transition (1) of Table 1). The $`k`$-th submachine $`M_{1k}`$ computes the residue when dividing $`w_1`$ by $`p_k`$ (by using transition $`(2a)`$ to $`(2d)`$ in Table 1). This division can be done simply by simulating the usual division procedure as shown in Fig 2 ($`a`$) and ($`b`$) for $`w_1=110001`$ and $`p_2=101`$ ($`=5`$). State $`j`$ in Fig 2 ($`b`$) corresponds to $`q_{p_2,j,1}`$. The starting state is 0 and by reading the first symbol 1 it goes to state 1. By reading the second symbol 1, it goes to state 3 ($`=11`$). Now reading 0, it goes to state 1 since $`110=1`$ mod 101. This continues until reading the last symbol 1 and $`M_0^Q`$ ends up in state 4. It should be noted that these state transitions are reversible: For example, if the machine reaches state 2 ($`=10`$) from some state $`Q`$ by reading 0, then $`Q`$ must be state 1 since $`Q`$ cannot be greater than 2. (Reason: If $`Q`$ is greater than 2, it means that the quotient will be 1 after reading a new symbol. Since $`M_0^Q`$ reads 0 as the new symbol, the least significant bit of the residue when divided by 5 must be 1, which excludes state 2 as its next state.) Hence the quotient must have been 0, and so the previous state must be 1. Note that this argument holds because we excluded two, which is the only even prime, from $`p_k`$.

Thus, if $`w_1`$ mod $`p_k=j_k`$, then $`M_0^Q`$ is in superposition $`\frac{1}{\sqrt{N}}_{k=1}^N|q_{p_k,j_k,1}`$ after reading $`w_1`$. Then $`M_0^Q`$ reads $`\mathrm{}`$ and this superposition is “shifted” to $`\frac{1}{\sqrt{N}}`$ $`_{k=1}^N|q_{p_k,j_k,2}`$, where $`M_0^Q`$ checks if $`w_2^R`$ mod $`p_k`$ is also $`j_k`$ by using transition $`(4a)`$ to $`(4d)`$ in Table 1. This job can be done by completely reversing the previous procedure of dividing $`w_1`$ by $`p_k`$. Actually, the state transitions are obtained by simply reversing the directions of previous state diagrams. Since previous transitions are reversible, new transitions are also reversible. Now one can see that the $`k`$-th submachine $`M_{2k}`$ is in state $`q_{p_k,0,2}`$ iff the two residues are the same.

Finally by reading $`\$`$, Fourier transform is carried out only from these zero-residue states $`q_{p_k,0,2}`$ to $`s_l`$. From other states $`q_{p_k,j,2}`$ ($`j0`$) $`M_0^Q`$ goes to rejecting states $`q_{p_k,j,rej}`$. If the residues are the same in only $`t`$ submachines out of the $`k`$ ones, the amplitude of $`s_N`$ is computed as

$$\frac{1}{N}\underset{|t|}{}\underset{l=1}{\overset{N}{}}\mathrm{exp}\left(\frac{2\pi i}{N}kl\right)|s_l=\frac{t}{N}|s_N+\frac{1}{N}\underset{|t|}{}\underset{l=1}{\overset{N1}{}}\mathrm{exp}\left(\frac{2\pi i}{N}kl\right)|s_l,$$

namely that is equal to $`t/N`$. Thus the probability of acceptance is $`\left(\frac{t}{N}\right)^2`$. If the input string is in $`L_0`$, then this probability becomes 1. Otherwise, it is at most $`\left(N_0/N\right)^2`$ by Lemma 2. The number of states in $`M_0^Q`$ is given as

$$1+2\underset{k=1}{\overset{N}{}}p_k+\underset{k=1}{\overset{N}{}}(p_k1)+N=1+3\underset{k=1}{\overset{N}{}}p_k1+3Np_N=O(N^2\mathrm{log}N),$$

which completes the proof.

$$\begin{array}{cccc}(1)\hfill & V_{c/}|q_0=\frac{1}{\sqrt{N}}_{k=1}^N|q_{p_k,0,1},\hfill & (4a)\hfill & V_0|q_{p_k,j,2}=|q_{p_k,\frac{j}{2},2}(j:even),\hfill \\ (2a)\hfill & V_0|q_{p_k,j,1}=|q_{p_k,2j,1}(0j<\frac{p_k}{2}),\hfill & (4b)\hfill & V_0|q_{p_k,j,2}=|q_{p_k,\frac{j+p_k}{2},2}(j:odd),\hfill \\ (2b)\hfill & V_0|q_{p_k,j,1}=|q_{p_k,2jp_k,1}(\frac{p_k}{2}<j<p_k),\hfill & (4c)\hfill & V_1|q_{p_k,j,2}=|q_{p_k,\frac{j1+p_k}{2},2}(j:even),\hfill \\ (2c)\hfill & V_1|q_{p_k,j,1}=|q_{p_k,2j+1,1}(0j<\frac{p_k}{2}1),\hfill & (4d)\hfill & V_1|q_{p_k,j,2}=|q_{p_k,\frac{j1}{2},2}(j:odd),\hfill \\ (2d)\hfill & V_1|q_{p_k,j,1}=|q_{p_k,2j+1p_k,1}(\frac{p_k}{2}1<j<p_k),\hfill & (5a)\hfill & V_\$|q_{p_k,0,2}=\frac{1}{\sqrt{N}}_{l=1}^N\mathrm{exp}\left(\frac{2\pi i}{N}kl\right)|s_l,\hfill \\ (3)\hfill & V_{\mathrm{}}|q_{p_k,j,1}=|q_{p_k,j,2},\hfill & (5b)\hfill & V_\$|q_{p_k,j,2}=|q_{p_k,j,rej}(1j<p_k).\hfill \end{array}$$

Table 1. State transition diagram of $`M_0^Q`$

Let us consider the pfa whose state transition is exactly the same as $`M_0^Q`$ of $`f(N)`$ states excepting that the state transitions from $`q_{p_k,0,2}`$ to $`s_l`$ for the Fourier transform are replaced by simple (deterministic) transitions from $`q_{p_k,0,2}`$ to $`s_N`$. We call such a pfa emulates the qfa. Suppose that $`M^P`$ emulates $`M^Q`$. Then the size of $`M^P`$ is almost the same as that of $`M^Q`$, i.e., it is also $`\mathrm{\Theta }(f(N))`$ if the latter is $`f(N)`$, since the Fourier transform does not make much difference in the number of states. The following lemma is easy:

Lemma 4. Suppose that $`M_0^P`$ emulates $`M_0^Q`$. Then $`M_0^P`$ accepts strings in $`L_0`$ with probability one and those not in $`L_0`$ with probability $`N_0/N`$.

Let us set, for example, $`N=N_0\sqrt{n}`$. Then the error-rate of $`M_0^Q`$ is $`(N_0/N)^2=\frac{1}{n}`$ and its size is $`O(n^3/\mathrm{log}n)`$. To achieve the same error-rate by a pfa, we have to set $`N=N_0n`$, which needs $`O(n^4/\mathrm{log}n)`$ states.

Remark. Suppose that we have once designed a specific qfa $`M_0^Q`$ (similarly for $`M_0^P`$). Then it can work for inputs of any length or it does not reject the input only by the fact that its length is not $`2n+1`$. The above calculation of the acceptance and rejection rates is only true when our input is restricted to strings $`\{0,1\}^n\mathrm{}\{0,1\}^n`$.

The following lemmas, Lemma 5 and 6 (see Acknowledgment), are important for the analysis of error probability of $`M_1^Q`$, a qfa which recognizes the second language $`L_1(n)`$. Here, $`\psi `$ means the norm of a vector $`\psi `$ and $`\psi _{acc}`$ the norm of $`\psi `$ after being projected onto accepting space, i.e., the accepting probability is $`\psi _{acc}^2`$. $`\psi |\varphi `$ denotes the inner product between $`\psi `$ and $`\varphi `$.

Lemma 5. Let $`\psi `$ be a quantum state such that applying a unitary transformation $`U`$ followed by a measurement to $`\psi `$ causes acceptance with probability $`1`$, i.e., $`U\psi _{acc}^2=1`$. If $`\psi `$ can be decomposed into two orthogonal states $`\psi _1`$ and $`\psi _2`$ s.t. $`\psi =\psi _1+\psi _2`$, then $`U\psi _1_{acc}^2\psi _1^4`$.

Proof. Let $`H=span\{\varphi U\varphi _{acc}=1and\varphi =1\}`$, i.e., $`H`$ is obtained by applying $`U^1`$ to the subspace spanned by accepting states only. The accepting probability of $`U\psi _1`$ is equal to the squared projection of $`U\psi _1`$ on the subspace spanned by accepting states. Since $`U`$ is unitary and any unitary transformation preserves the inner product, it turns out that this projection is the same as the projection of $`\psi _1`$ onto $`H`$. Let $`H^{}=span\{\psi \}`$. Since $`U\psi _{acc}^2=1`$, we have $`H^{}H`$. Therefore the projection of $`\psi _1`$ to $`H`$ is at least the projection of $`\psi _1`$ to $`H^{}`$, namely at least $`\psi _1|\psi =\psi _1^2`$. To summarize, $`U\psi _1_{acc}^2\psi _1|\psi ^2=\psi _1^4`$.

Lemma 6. Let $`\psi `$ be a quantum state such that applying a unitary transformation $`U`$ followed by a measurement to $`\psi `$ causes acceptance with probability at most $`\alpha ^2`$, i.e., $`U\psi _{acc}^2\alpha ^2`$. If $`\psi `$ can be decomposed into two orthogonal states $`\psi _1`$ and $`\psi _2`$ s.t. $`\psi =\psi _1+\psi _2`$, then

$$U\psi _1_{acc}^2\psi _1^2\left(\alpha \psi _1+\psi _2\right)^2.$$

Proof. Let $`H`$ be the Hilbert space spanned by $`\psi _1`$ and $`\psi _2`$. Then, $`\psi _1`$ can also be written as

$$\psi _1=\psi |\psi _1\psi +\overline{\psi }|\psi _1\overline{\psi },$$

where $`\overline{\psi }`$ is a normalized vector in $`H`$ and perpendicular to $`\psi `$. Note that $`\psi `$ is also $`1`$. Again $`\psi |\psi _1=\psi _1^2`$ and from the above equation we obtain that $`\psi _1|\psi _1=\psi |\psi _1^2+\overline{\psi }|\psi _1^2`$, which implies that $`\overline{\psi }|\psi _1^2=\psi _1^2(1\psi _1^2)`$. Note that $`\psi _1^2+\psi _2^2=1`$. Thus, $`\overline{\psi }|\psi _1=\psi _1\psi _2`$. Since $`U\psi _1=\psi |\psi _1U\psi +\overline{\psi }|\psi _1U\overline{\psi }`$ and our observation is a simple projection, it follows by triangular inequality that

$`U\psi _1_{acc}`$ $``$ $`\psi |\psi _1U\psi _{acc}+\overline{\psi }|\psi _1U\overline{\psi }_{acc}`$
$``$ $`\psi _1^2\alpha +\psi _1\psi _2`$
$`=`$ $`\psi _1\left(\alpha \psi _1+\psi _2\right).`$
This proves the lemma.

Now we shall design a qfa $`M_1^Q`$ which recognizes the second language $`L_1(n)`$.

Lemma 7. There exists a qfa $`M_1^Q`$ which accepts strings in $`L_1`$ with probability at least $`1(\frac{N_0}{N_1})^2+(\frac{N_0}{N_1})^4`$ and strings not in $`L_1`$ with at most $`(\frac{N_0}{N_1})^2+(1(\frac{N_0}{N_1})^2)(\frac{N_0^{}}{N_2}+\frac{N_0}{N_1})^2`$. $`M_1^Q`$ has $`\mathrm{\Theta }((N_1N_2)^2\mathrm{log}N_1\mathrm{log}N_2)`$ states. Here $`N_0^{}`$ denotes the number $`s`$ in Lemma 1 but for $`x`$ and $`y`$ of length $`2n`$.

Proof. Again a complete state transition diagram is shown in Table 2, where accepting states are $`s_{N_1,0,p_l,f}`$ such that $`0fp_l1`$ and $`t_{N_1}`$. Rejecting states are $`q_{p_k,e,p_l,f,rej}`$ such that $`e0`$ or $`f0`$, $`0ep_k1`$, $`0fp_l1`$, $`t_{p_k,0,y}`$ such that $`1yN_21`$, and $`t_z`$ such that $`1zN_11`$. All other states are non-halting.

$`M_1^Q`$ checks whether $`w_1=w_2^R`$ using $`N_1`$ primes and also whether $`(w_1w_2)=(w_3w_4)^R`$ using $`N_2`$ primes. Note that those two jobs have to be done at the same time using composite automata while reading $`w_1\mathrm{}w_2`$. Hence $`M_1^Q`$ first splits into $`N_1N_2`$ submachines, each of which is denoted by $`M(k,l)`$, $`1kN_1`$, $`1lN_2`$. As shown in Fig 3, $`M(k,l)`$ has six stages, from stage 1 thorough stage 6. It might be convenient to think that each state of $`M(k,l)`$ be a pair of state $`(q_L,q_R)`$ and to think $`M(k,l)`$ be a composite of $`M_L`$ and $`M_R`$. In stages 1 and 2, $`M_L`$ has similar state transitions to those of Table 1 for checking $`w_1w_2^R`$. $`M_R`$ has also similar transitions but only for the first part of it, i.e., to compute $`w_1w_2`$ mod $`p_l`$. This portion of transitions are given in (2) to (4) of Table 2.

Now we go to stage 3. Here $`M_L`$, reading the first $`\mathrm{}`$, carries out the Fourier transform exactly as $`M_0^Q`$ (see ($`5a`$) in Table 2). After that $`M_L`$, reading the second $`\mathrm{}`$, execute Inverse Fourier transform from states $`s_{m,0,p_l,f}`$ ($`1mN_1`$), which is shown in $`(6a)`$ of Table 2. In this stage, $`M_R`$ does nothing; it just shifts the state information about $`(w_1w_2)`$ mod $`p_l`$ (but only when $`w_1w_2^R`$) to stage 4.

Stages 4 and 5 are for the complete reverse operation of stages 2 and 1, respectively. By doing this, the amplitudes for state $`q_L`$, which were once in turmoil after stage 2, are reorganized and gathered in specific states, namely $`q_{p_k,0,p_l,0,4}`$ if $`(w_1w_2)=(w_3w_4)^R`$. Therefore, what we do is to gather the amplitude of $`q_{p_k,0,p_l,0,4}`$ to $`t_{p_k,0,N_2}`$ by Fourier transform reading $`\mathrm{}`$. Now reading the rightmost symbol, we do another Fourier transform, which gathers the amplitudes of $`t_{p_k,0,N_2}`$ to $`t_{N_1}`$.

For the analysis of error probability, Lemma 5 and 6 are convenient. The basic idea is as follows: When $`w_1w_2^R`$, a small amplitude, $`\frac{1}{\sqrt{N_2}}\frac{N_0}{N_1}`$ is “taken” by each of the $`N_2`$ accepting states in stage 3. This is basically the same as $`M_0^Q`$ since its probability of observing acceptance is $`_{l=1}^{N_2}\left(\frac{1}{\sqrt{N_2}}\frac{N_0}{N_1}\right)^2=\left(\frac{N_0}{N_1}\right)^2`$. So, the problem is how much of the remaining amplitudes distributed on the other states in this stage can be retrieved in the final accepting state $`t_{N_1}`$ when $`(w_1w_2)=(w_3w_4)^R`$.

Suppose that we construct a new qfa $`M^{}`$ which is exactly the same as $`M_1^Q`$ but all the $`N_2`$ halting states of $`M_1^Q`$ in stage 3 are changed to non-halting states. Thus $`M^{}`$ only checks the longer strings, whether $`(w_1w_2)=(w_3w_4)^R`$ or not. It is clear that $`M^{}`$ accepts with probability exactly one when $`(w_1w_2)=(w_3w_4)^R`$ and with probability at most $`(\frac{N_0^{}}{N_2})^2`$ when $`(w_1w_2)(w_3w_4)^R`$.

Note that Lemma 5 and 6 also hold for any sequence of unitary transformations and measurements since we can delay measurements and replace them with a single unitary transformation $`U`$ followed by a measurement\[ANTV99\]. Next, consider ($`i`$)$`\psi `$, ($`ii`$)$`\psi _1`$ and ($`iii`$)$`\psi _2`$ in Lemma 5 and 6 as ($`i`$)the quantum state, ($`ii`$)the superposition of non-halting states and ($`iii`$)the superposition of accepting states in stage 3 of $`M_1^Q`$ right after Fourier transform, respectively. In our case, $`\psi _1^2=(1(\frac{N_0}{N_1})^2)`$, $`\psi _2^2=(\frac{N_0}{N_1})^2`$ and $`\alpha ^2=(\frac{N_0^{}}{N_2})^2`$. Thus, from Lemma 5 we can obtain that when $`(w_1w_2)=(w_3w_4)^R`$, $`M_1^Q`$ accepts with probability at least $`\left(\frac{N_0}{N_1}\right)^2+\left(1\left(\frac{N_0}{N_1}\right)^2\right)^2.`$ Also from Lemma 6, when $`(w_1w_2)(w_3w_4)^R`$, $`M_1^Q`$ accepts with probability at most $`\left(\frac{N_0}{N_1}\right)^2+\left(1\left(\frac{N_0}{N_1}\right)^2\right)\left(\sqrt{\left(1\left(\frac{N_0}{N_1}\right)^2\right)}\frac{N_0^{}}{N_2}+\frac{N_0}{N_1}\right)^2\left(\frac{N_0}{N_1}\right)^2+\left(1\left(\frac{N_0}{N_1}\right)^2\right)\left(\frac{N_0^{}}{N_2}+\frac{N_0}{N_1}\right)^2.`$

Finally, we count the number of states in $`M_1^Q`$. This is not hard since the whole machine is a composition of two machines, one for using $`N_1`$ different primes and the other for $`N_2`$ different primes. Therefore the size of the composite machine is $`O((N_1N_2)^2\mathrm{log}N_1\mathrm{log}N_2)`$.

Suppose that we set $`N_1=N_0\sqrt{n}`$, and $`N_2=dN_0^{}`$. Then $`\frac{N_0}{N_1}=\frac{1}{\sqrt{n}}`$ and $`\frac{N_0^{}}{N_2}+\frac{N_0}{N_1}\frac{1}{2}`$ if we select a sufficiently large constant $`d`$, e.g. $`d=3`$ when $`n36`$. Namely, $`M_1^Q`$ accepts strings in $`L_1`$ with probability at least $`11/n+1/n^2`$ and those not in $`L_1`$ with probability at most $`\frac{1}{4}+\frac{3}{4n}`$. The number of states is $`\mathrm{\Theta }(\frac{n^5}{\mathrm{log}^2n})`$. The probability distribution for each state of $`M_1^Q`$ is illustrated in Fig 4 (for example, above $`11/n+1/n^2`$ is the sum of $`1/n`$ and $`12/n+1/n^2`$).

Let us consider pfa $`M_1^P`$ which recognizes $`L_1(n)`$. The state transition of $`M_1^P`$ is the same as that of $`M_1^Q`$ except for Fourier transform and Inverse Fourier transform only $`M_1^Q`$ performs. If string $`x`$ satisfies $`w_1w_2^R`$, then $`M_1^P`$ accepts $`x`$ with probability at most $`\frac{N_0}{N_1}`$ after reading $`w_1\mathrm{}w_2`$ instead of with at most $`(\frac{N_0}{N_1})^2`$ in the case of $`M_1^Q`$. There are subtle differences between $`M_1^P`$ and $`M_1^Q`$. For example, in the case of $`M_1^P`$, the distributed small amplitudes after reading $`w_3\mathrm{}w_4`$ can be collected completely (there is some loss due to Inverse Fourier transform in the case of $`M_1^Q`$). This causes a slight difference in the accepting probability of the next lemma (proof is omitted).

Lemma 8. Suppose that $`M_1^P`$ emulates $`M_1^Q`$. Then $`M_1^P`$ accepts strings in $`L_1`$ with probability 1 and those not in $`L_1`$ with probability at most $`\frac{N_0}{N_1}+\left(1\frac{N_0}{N_1}\right)\frac{N_0^{}}{N_2}`$. The number of states is approximately the same as the one of $`M_1^Q`$, i.e., $`\mathrm{\Theta }((N_1N_2)^2\mathrm{log}N_1\mathrm{log}N_2)`$.

If we set $`N_1=N_0n`$ and $`N_2=dN_0^{}`$, then strings such that $`w_1w_2^R`$ are accepted with probability at most $`\frac{1}{n}`$ after reading $`w_1\mathrm{}w_2`$. Thus this probability is the same as qfa $`M_1^Q`$ such that $`N_1=N_0\sqrt{n}`$ and $`N_2=dN_0^{}`$, but the lemma says that we need $`\mathrm{\Omega }\left(\frac{n^6}{\mathrm{log}^2n}\right)`$ states. See Fig. 5 for a probability distribution.

Now we are ready to give our main theorem:

Theorem 1. For any integer $`c`$, there is a qfa $`M^Q`$ such that $`M^Q`$ recognizes $`L(n,n^c)`$ and the number of states in $`M^Q`$ is $`O\left(\frac{n^{c+4}}{\mathrm{log}^2n}\right)`$.

Proof. The construction of $`M^Q`$ is easy: We just add a new deterministic transition from the last accepting state in stage 6 of $`M_1^Q`$ to its initial state by reading $`\mathrm{}`$, by which we can manage iteration. Also, we need some small changes to handle the very end of the string: Formally speaking, transition (11) in Table 2 is modified into

$$V_{\mathrm{}}|t_{p_k,0,N_2}=\frac{1}{\sqrt{N_1}}\underset{z=1}{\overset{N_1}{}}\mathrm{exp}\left(\frac{2\pi i}{N_2}kz\right)|t_z,$$

$`t_{N_1}`$ is now not an accepting state but a non-halting state and two new transitions

$$\begin{array}{cc}(10c)\hfill & V_\$|q_{p_k,e,p_l,f,4}=|q_{p_k,e,p_l,f,rej}\\ (12)\hfill & V_{\mathrm{}}|t_{N_1}=|q_1\end{array}$$

are added.

We set $`N_1=2N_0n^{c/2}`$ and $`N_2=dN_0^{}`$. Then $`N_0/N_1=\frac{1}{2n^{c/2}}`$ and $`\frac{N_0^{}}{N_2}+\frac{N_0}{N_1}<\frac{1}{2}`$ if we select a sufficiently large constant as $`d`$. Suppose that $`M^Q`$ has not halted yet and is now reading the $`i`$-th block $`w_{i1}\mathrm{}w_{i2}\mathrm{}\mathrm{}w_{i3}\mathrm{}w_{i4}`$. Then, we can conclude the following by Lemma 7: $`(i)`$ If $`w_{i1}=w_{i2}^R`$, then $`M^Q`$ accepts the input with probability one. ($`ii`$) If $`(w_{i1}w_{i2})=(w_{i3}w_{i4})^R`$, then $`(iia)`$ $`M^Q`$ also accepts the input with probability at most $`1/4n^c`$ and $`(iib)`$ rejects the input with at most $`\frac{1}{4n^c}\frac{1}{16n^{2c}}`$ and $`(iic)`$ goes back to the initial state with at least $`1\frac{2}{4n^c}+\frac{1}{16n^{2c}}`$. $`(iii)`$ If $`(w_{i1}w_{i2})(w_{i3}w_{i4})^R`$, then $`(iiia)`$ $`M^Q`$ accepts the input with at most $`\frac{1}{4n^c}`$, $`(iiib)`$ rejects it with at least $`\frac{3}{4}\frac{3}{16n^c}`$ and $`(iiic)`$ goes back to the initial state with at most $`\frac{1}{4}\frac{1}{16n^c}`$. The number of state is $`O(n^{c+4}/\mathrm{log}^2n)`$.

Recall that the number of iteration is $`n^c`$. Now suppose that the input $`x`$ is in $`L(n,n^c)`$. Then, the probability that $`x`$ is rejected is equal to the probability that $`(iib)`$ happens before ($`i`$) happens. The probability that $`(iib)`$ happens is at most $`\frac{1}{4n^c}`$ per iteration, and so the probability that ($`iib`$) happens in some iteration is at most $`n^c\frac{1}{4n^c}=\frac{1}{4}`$. Therefore the probability that $`x`$ is finally accepted is well larger than 1/2. Suppose conversely that $`x`$ is not in $`L(n,n^c)`$. Then the probability that $`(iia)`$ happens in some iteration is the same as above and is at most $`\frac{1}{4}`$. If $`M^Q`$ does not meet a block such that $`(w_{i1}w_{i2})(w_{i3}w_{i4})^R`$ until the end, then the accepting probability is at most this $`1/4`$. If $`M^Q`$ does meet such a block in some iteration, it rejects $`x`$ with probability at least $`(1\frac{1}{4})(\frac{3}{4}\frac{3}{16n^c})`$ which is again well above 1/2. Thus $`M^Q`$ recognizes $`L(n,n^c)`$.

Theorem 2. Suppose that $`M^P`$ which emulates $`M^Q`$ recognizes $`L_2(n,n^c)`$. Then the number of states of $`M^P`$ is $`\mathrm{\Omega }(n^{2c+4}/\mathrm{log}^2n)`$.

Proof. $`M^P`$ is constructed by applying the same modification (as given in the above proof) to $`M_1^P`$. Then it turns out that we must set $`N_0^{}/N_21/d`$, where $`d`$ is a sufficiently large constant, to reject the strings such that $`(w_{i1}w_{i2})(w_{i3}w_{i4})^R`$ since $`M_1^P`$ accepts such bad strings with probability at least $`\frac{N_0}{N_1}+(1\frac{N_0}{N_1})\frac{N_0^{}}{N_2}`$ by Lemma 8. So we have to set $`N_2=dN_0^{}`$ and suppose that we set $`N_1=\frac{1}{a}N_0n^c`$. Then, as shown below, $`M^P`$ does not recognize $`L_2(n,n^c)`$ if $`a`$ is large. That means we have to set $`N_1=\frac{1}{a}N_0n^c`$ for a sufficiently small $`a>0`$, which implies, from Lemma 8, that we need $`\mathrm{\Omega }(n^{2c+4}/\mathrm{log}^2n)`$ states.

Now suppose that the input $`x`$ includes a long repetition of blocks such that $`(w_{i1}w_{i2})=(w_{i3}w_{i4})^R`$. Then $`x`$ is accepted in each iteration with probability $`a/n^c`$. Therefore the probability that this happens in the first $`k`$ iterations is

$$\underset{i=1}{\overset{k}{}}\left(1\frac{a}{n^c}\right)^{i1}\frac{a}{n^c}=1\left(1\frac{a}{n^c}\right)^k.$$

Since the number of repetitions $`(=k)`$ can be as large as $`n^c`$,

$$\underset{n\mathrm{}}{lim}\left(1\frac{a}{n^c}\right)^{n^c}=\frac{1}{e^a}.$$

Thus if we select a sufficiently large constant $`a`$, then the probability of acceptance can be arbitrarily close to one. Such an $`M^P`$ does not recognize $`L(n,n^c)`$ obviously, which proves the theorem.

## 5 Concluding Remarks

The question in this paper is whether or not we can exploit the difference in probability calculation between quantum and probabilistic computations. We have shown that the answer is yes using quantum finite automata. However, what remains apparently is whether or not we can exploit this property for other types of models and/or for other types of problems which are preferably less artificial. Also it should be an important future research to obtain a general lower bound for the number of states which is needed to recognize $`L_2(n,n^c)`$ by pfa’s.

Acknowledgment. We are grateful to Mario Szegedy for his many valuable comments to this research. We also thank the anonymous reviewer for Lemma 5. In the earlier version of this paper, the proof of Lemma 7 was very lengthy. Using this lemma and Lemma 6 which is developed under the same idea as Lemma 5, the proof of Lemma 7 was greatly simplified.

$$\begin{array}{cc}\left(1\right)\hfill & V_{c/}|q_0=\frac{1}{\sqrt{N_1N_2}}_{k=1}^{N_1}_{l=1}^{N_2}|q_{p_k,0,p_l,0,1},\hfill \\ \left(2a\right)\hfill & V_0|q_{p_k,e,p_l,f,1}=|q_{p_k,2e,p_l,2f,1}(0e<\frac{p_k}{2},0f<\frac{p_l}{2}),\hfill \\ \left(2b\right)\hfill & V_0|q_{p_k,e,p_l,f,1}=|q_{p_k,2e,p_l,2fp_l,1}(0e<\frac{p_k}{2},\frac{p_l}{2}<f<p_l),\hfill \\ \left(2c\right)\hfill & V_0|q_{p_k,e,p_l,f,1}=|q_{p_k,2ep_k,p_l,2f,1}(\frac{p_k}{2}<e<p_k,0f<\frac{p_l}{2}),\hfill \\ \left(2d\right)\hfill & V_0|q_{p_k,e,p_l,f,1}=|q_{p_k,2ep_k,p_l,2fp_l,1}(\frac{p_k}{2}<e<p_k,\frac{p_l}{2}<f<p_l),\hfill \\ \left(2e\right)\hfill & V_1|q_{p_k,e,p_l,f,1}=|q_{p_k,2e+1,p_l,2f+1,1}(0e<\frac{p_k}{2}1,0f<\frac{p_l}{2}1),\hfill \\ \left(2f\right)\hfill & V_1|q_{p_k,e,p_l,f,1}=|q_{p_k,2e+1,p_l,2f+1p_l,1}(0e<\frac{p_k}{2}1,\frac{p_l}{2}1<f<p_l),\hfill \\ \left(2g\right)\hfill & V_1|q_{p_k,e,p_l,f,1}=|q_{p_k,2e+1p_k,p_l,2f+1,1}(\frac{p_k}{2}1<e<p_k,0f<\frac{p_l}{2}1),\hfill \\ \left(2h\right)\hfill & V_1|q_{p_k,e,p_l,f,1}=|q_{p_k,2e+1p_k,p_l,2f+1p_l,1}\hfill \\ & \left(\frac{p_k}{2}1<e<p_k,\frac{p_l}{2}1<f<p_l\right),\hfill \\ \left(3\right)\hfill & V_{\mathrm{}}|q_{p_k,e,p_l,f,1}=|q_{p_k,e,p_l,f,2},\hfill \\ \left(4a\right)\hfill & V_0|q_{p_k,e,p_l,f,2}=|q_{p_k,\frac{e}{2},p_l,2f,2}(e:even,0f<\frac{p_l}{2}),\hfill \\ \left(4b\right)\hfill & V_0|q_{p_k,e,p_l,f,2}=|q_{p_k,\frac{e}{2},p_l,2fp_l,2}(e:even,\frac{p_l}{2}<f<p_l),\hfill \\ \left(4c\right)\hfill & V_0|q_{p_k,e,p_l,f,2}=|q_{p_k,\frac{e+p_k}{2},p_l,2f,2}(e:odd,0f<\frac{p_l}{2}),\hfill \\ \left(4d\right)\hfill & V_0|q_{p_k,e,p_l,f,2}=|q_{p_k,\frac{e+p_k}{2},p_l,2fp_l,2}(e:odd,\frac{p_l}{2}<f<p_l),\hfill \\ \left(4e\right)\hfill & V_1|q_{p_k,e,p_l,f,2}=|q_{p_k,\frac{e1+p_k}{2},p_l,2f+1,2}(e:even,0f<\frac{p_l}{2}1),\hfill \\ \left(4f\right)\hfill & V_1|q_{p_k,e,p_l,f,2}=|q_{p_k,\frac{e1+p_k}{2},p_l,2f+1p_l,2}(e:even,\frac{p_l}{2}1<f<p_l),\hfill \\ \left(4g\right)\hfill & V_1|q_{p_k,e,p_l,f,2}=|q_{p_k,\frac{e1}{2},p_l,2f+1,2}(e:odd,0f<\frac{p_l}{2}1),\hfill \\ \left(4h\right)\hfill & V_1|q_{p_k,e,p_l,f,2}=|q_{p_k,\frac{e1}{2},p_l,2f+1p_l,2}(e:odd,\frac{p_l}{2}1<f<p_l),\hfill \\ \left(5a\right)\hfill & V_{\mathrm{}}|q_{p_k,0,p_l,f,2}=\frac{1}{\sqrt{N_1}}_{m=1}^{N_1}\mathrm{exp}\left(\frac{2\pi i}{N_1}km\right)|s_{m,0,p_l,f},\hfill \\ \left(5b\right)\hfill & V_{\mathrm{}}|q_{p_k,e,p_l,f,2}=|q_{p_k,e,p_l,f}\left(1e<p_k\right),\hfill \\ \left(6a\right)\hfill & V_{\mathrm{}}|s_{m,0,p_l,f}=\frac{1}{\sqrt{N_1}}_{r=1}^{N_1}\mathrm{exp}\left(\frac{2\pi i}{N_1}mr\right)|q_{p_r,0,p_l,f,3}\left(1mN_1\right),\hfill \\ \left(6b\right)\hfill & V_{\mathrm{}}|q_{p_k,e,p_l,f}=|q_{p_k,e,p_l,f,3}\left(1e<p_k\right),\hfill \\ \left(7a\right)\hfill & V_0|q_{p_k,e,p_l,f,3}=|q_{p_k,2e,p_l,\frac{f}{2},3}(0e<\frac{p_k}{2},f:even),\hfill \\ \left(7b\right)\hfill & V_0|q_{p_k,e,p_l,f,3}=|q_{p_k,2e,p_l,\frac{f+p_l}{2},3}(0e<\frac{p_k}{2},f:odd),\hfill \\ \left(7c\right)\hfill & V_0|q_{p_k,e,p_l,f,3}=|q_{p_k,2ep_k,p_l,\frac{f}{2},3}(\frac{p_k}{2}<e<p_k,f:even),\hfill \\ \left(7d\right)\hfill & V_0|q_{p_k,e,p_l,f,3}=|q_{p_k,2ep_k,p_l,\frac{f+p_l}{2},3}(\frac{p_k}{2}<e<p_k,f:odd),\hfill \\ \left(7e\right)\hfill & V_1|q_{p_k,e,p_l,f,3}=|q_{p_k,2e+1,p_l,\frac{f1+p_l}{2},3}(0e<\frac{p_k}{2}1,f:even),\hfill \\ \left(7f\right)\hfill & V_1|q_{p_k,e,p_l,f,3}=|q_{p_k,2e+1,p_l,\frac{f1}{2},3}(0e<\frac{p_k}{2}1,f:odd),\hfill \\ \left(7g\right)\hfill & V_1|q_{p_k,e,p_l,f,3}=|q_{p_k,2e+1p_k,p_l,\frac{f1+p_l}{2},3}(\frac{p_k}{2}1<e<p_k,f:even),\hfill \\ \left(7h\right)\hfill & V_1|q_{p_k,e,p_l,f,3}=|q_{p_k,2e+1p_k,p_l,\frac{f1}{2},3}(\frac{p_k}{2}1<e<p_k,f:odd),\hfill \\ \left(8\right)\hfill & V_{\mathrm{}}|q_{p_k,e,p_l,f,3}=|q_{p_k,e,p_l,f,4},\hfill \\ \left(9a\right)\hfill & V_0|q_{p_k,e,p_l,f,4}=|q_{p_k,\frac{e}{2},p_l,\frac{f}{2},4}(e:even,f:even),\hfill \\ \left(9b\right)\hfill & V_0|q_{p_k,e,p_l,f,4}=|q_{p_k,\frac{e}{2},p_l,\frac{f+p_l}{2},4}(e:even,f:odd),\hfill \\ \left(9c\right)\hfill & V_0|q_{p_k,e,p_l,f,4}=|q_{p_k,\frac{e+p_k}{2},p_l,\frac{f}{2},4}(e:odd,f:even),\hfill \\ \left(9d\right)\hfill & V_0|q_{p_k,e,p_l,f,4}=|q_{p_k,\frac{e+p_k}{2},p_l,p_l,\frac{f+p_l}{2},4}(e:odd,f:odd),\hfill \\ \left(9e\right)\hfill & V_1|q_{p_k,e,p_l,f,4}=|q_{p_k,\frac{e1+p_k}{2},p_l,\frac{f1+p_l}{2},4}(e:even,f:even),\hfill \\ \left(9f\right)\hfill & V_1|q_{p_k,e,p_l,f,4}=|q_{p_k,\frac{e1+p_k}{2},p_l,\frac{f1}{2},4}(e:even,f:odd),\hfill \\ \left(9g\right)\hfill & V_1|q_{p_k,e,p_l,f,4}=|q_{p_k,\frac{e1}{2},p_l,\frac{f1+p_l}{2},4}(e:odd,f:even),\hfill \\ \left(9h\right)\hfill & V_1|q_{p_k,e,p_l,f,4}=|q_{p_k,\frac{e1}{2},p_l,\frac{f1}{2},4}(e:odd,f:odd),\hfill \\ \left(10a\right)\hfill & V_{\mathrm{}}|q_{p_k,0,p_l,0,4}=\frac{1}{\sqrt{N_2}}_{y=1}^{N_2}\mathrm{exp}\left(\frac{2\pi i}{N_2}ly\right)|t_{p_k,0,y},\hfill \\ \left(10b\right)\hfill & V_{\mathrm{}}|q_{p_k,e,p_l,f,4}=|q_{p_k,e,p_l,f,rej}\left(1f<p_l\right),\hfill \\ \left(11\right)\hfill & V_\$|t_{p_k,0,N_2}=\frac{1}{\sqrt{N_1}}_{z=1}^{N_1}\mathrm{exp}\left(\frac{2\pi i}{N_2}kz\right)|t_z,\hfill \end{array}$$

Table 2. state transition diagram of $`M_1^Q`$