text:
# Neutron Scattering Study of Magnetic Ordering and Excitations in the Doped Spin Gap System Tl(Cu1-xMgx)Cl3

## I Introduction

Recently, the magnetic ordering induced by external field or impurity ions in spin gap systems attracted much interest and thus led to a large number of vivid experimental and theoretical investigations. When a strong magnetic field, which is higher than the gap field $`H_\mathrm{g}`$ corresponding to the energy gap $`\mathrm{\Delta }=g\mu _\mathrm{B}H_\mathrm{g}`$, is applied in a spin gap system, the energy gap vanishes, and the system can undergo the field-induced magnetic ordering with the help of the three-dimensional interactions. Such field-induced magnetic ordering was observed in many spin gap systems, Cu2(C5H12N2)2Cl4 , Ni(C5H14N2)2N3(ClO4) , Ni(C5H14N2)2N3(PF6) , Cu(NO3)2$``$2.5H2O , (CH3)2CHNH3CuCl3 , (C4H12N2)Cu2Cl6  and KCuCl3 . On the other hand, when nonmagnetic ions are substituted for magnetic ions in a spin gap system, the singlet ground state is disturbed so that staggered moments are induced around the impurities. If the induced moments interact through effective exchange interactions, which are mediated by intermediate singlet spins, three-dimensional (3D) long-range order can arise. Such impurity-induced antiferromagnetic ordering was also observed in some spin gap systems, (Cu1-xZnx)GeO3 , (Cu1-xMgx)GeO3 , Sr(Cu1-xZnx)2O3  and Pb(Ni1-xMgx)2V2O8 . Magnetic ordering due to pinning of lattice dimerization by doped nonmagnetic impurities was also observed in Cu(Ge1-xSix)O3 . In (Cu1-xZnx)GeO3 and Cu(Ge1-xSix)O3 with low $`x`$, the coexistence of lattice dimerization, associated with the spin gap, and the ordering has been observed in neutron scattering experiments . The site-impurity effect on spin gap systems has been argued theoretically by many authors , and impurity-induced antiferromagnetic ordering has been demonstrated. Yet there has been no system studied so far, which undergoes both the field and impurity induced magnetic ordering.

This paper is concerned with the impurity-induced antiferromagnetic ordering in the Mg-doped spin gap system Tl(Cu1-xMgx)Cl3 where the parent compound TlCuCl3 is known to undergo the field-induced magnetic ordering and has been extensively studied by author’s group. The parent compound TlCuCl3 has the monoclinic structure (space group $`P2_1/c`$) . The crystal structure is composed of planar dimers of Cu2Cl6, in which Cu2+ ions have spin-$`\frac{1}{2}`$. The dimers are stacked on top of one another to form infinite double chains parallel to the crystallographic $`a`$-axis. These double chains are located at the corners and center of the unit cell in the $`bc`$ plane, and are separated by Tl+ ions.

The magnetic ground state of TlCuCl3 is the spin singlet  with the excitation gap $`\mathrm{\Delta }=7.7`$ K . From the results of analyses of the dispersion relations obtained by neutron inelastic scattering, it was found that the origin of the spin gap in TlCuCl3 is the strong antiferromagnetic interaction in the chemical dimer Cu2Cl6, and that the neighboring dimers couple via the strong three-dimensional interdimer interactions along the double chain and in the $`(1,0,2)`$ plane, in which the hole orbitals of Cu2+ spread . Using the cluster series expansion, the intradimer and the important individual interdimer exchange interactions were obtained . The notation of the exchange interactions is given in Fig. 1. The main intradimer interaction is denoted as $`J`$, and then the exchange interaction per bond between spins in dimers separated by a lattice vector $`l𝕒+m𝕓+n𝕔`$ is denoted as the exchange energy $`J_{lmn}`$ for pairs of spins at equivalent positions in their respective dimer and as $`J_{lmn}^{}`$ for spins at inequivalent positions.

The field-induced magnetic ordering, as mentioned above, was observed in TlCuCl3 . In the ordering of TlCuCl3, two remarkable features have been found. One of them is that the magnetization has the cusplike minimum at the transition temperature $`T_\mathrm{N}`$. Another is that the phase boundary between the paramagnetic phase and the ordered phase can be described by the power law. These features cannot be explained by the mean-field approach from the real space . Nikuni et al.  suggested that the field-induced magnetic ordering in TlCuCl3 can be represented as a Bose-Einstein condensation (BEC) of excited triplets (magnons), and then the above two features were qualitatively well described by the magnon BEC theory based on the Hartree-Fock (HF) approximation.

If the magnons undergo BEC at ordering vector $`_0`$ for $`H>H_\mathrm{g}`$, then the transverse spin components have long-range order, which is characterized by the same wave vector $`_0`$. The transverse magnetic ordering predicted by the theory  was confirmed by the neutron elastic scattering experiments in magnetic fields . The obtained spin structure of field-induced ordered phase for $`b`$ in TlCuCl3 is shown in Fig. 1. The directions of spins are in the $`ac`$ plane which is perpendicular to the applied field. Spins on the same dimers represented by thick lines in Fig. 1 are antiparallel. Spins are arranged in parallel along a leg in the double chain, and make an angle of $`\alpha `$ with the $`a`$-axis. The spins on the same legs in the double chains located at the corner and the center of the unit cell in the $`bc`$ plane are antiparallel. This structure is consistent with the sign of the intradimer and the individual interdimer exchange interactions obtained by the neutron inelastic scattering measurements . Comparing to the magnetic Bragg intensities, the angle $`\alpha `$ was estimated as 39.

More recently, we performed the magnetization measurements in the title compound Tl(Cu1-xMgx)Cl3, and observed the impurity-induced antiferromagnetic ordering, as mentioned above . It was also confirmed that the easy-axis of the magnetic moments lies in the $`(0,1,0)`$ plane at an angle of $`38^{}`$ to the $`a`$-axis. The easy-axis ($`\alpha `$=38) is almost the same as the spin direction ($`\alpha `$=39) in the field-induced ordered phase for the parent compound TlCuCl3.

Experimental studies of impurity-induced antiferromagnetic ordering have been performed only on quasi-1D systems to date. Therefore, for comprehensive understanding of impurity-induced antiferromagnetic ordering, it may be necessary to study the ordering on 3D spin gap systems. Also, it is interesting to investigate the relation between the field-induced magnetic ordering and the impurity-induced antiferromagnetic ordering because there is no system so far studied that undergoes both of the orderings except TlCuCl3 to our best knowledge. With these motivations, we performed the neutron elastic and inelastic scattering measurements in Tl(Cu0.97Mg0.03)Cl3 in order to investigate the spin structure and the magnetic excitations in the impurity-induced antiferromagnetic ordered phase of Tl(Cu1-xMgx)Cl3.

## II Experimental Details

The preparation of the single crystal of Tl(Cu1-xMgx)Cl3 has been reported in reference . Neutron elastic and inelastic scattering measurements were performed using the JAERI-TAS1 and JAERI-LTAS, which are thermal and cold neutron spectrometers respectively, installed at JRR-3M, in Tokai. For the elastic scattering, the constant-$`𝕜_i`$ mode was taken with a fixed incident neutron energy $`E_i`$ of 14.7 meV and collimations were set as open-40’-80’-80’ on JAERI-TAS1. For the inelastic scattering, the constant-$`𝕜_f`$ mode was taken with a fixed final neutron energy $`E_f`$ of 14.7 meV and collimations were set as open-80’-80’-80’ on JAERI-TAS1. In order to investigate the low energy excitation with the higher energy resolution, the inelastic scattering, in which the constant-$`𝕜_f`$ mode was taken with a fixed final neutron energy $`E_f`$ of 5.0 meV and collimations were set as 24’-80’-80’-80’, were also carried out on JAERI-LTAS. A pyrolytic graphite filter was placed to suppress the higher order contaminations. We used a sample with a volume of approximately 1 cm3. The sample was mounted in an ILL-type orange cryostat with its $`a^{}`$\- and $`c^{}`$-axes in the scattering plane. The crystallographic parameters were determined as $`a^{}=1.6139`$ 1/$`\mathrm{\AA }`$, $`c^{}=0.71554`$ 1/$`\mathrm{\AA }`$ and $`\mathrm{cos}\beta ^{}=0.0956`$ at helium temperatures.

## III Results and Discussions

### A Spin Structure

The inset of Fig. 2 shows the $`\theta 2\theta `$ scans for $`=(1,0,3)`$ reflection measured at $`T=1.4`$ and 4.2 K in Tl(Cu0.97Mg0.03)Cl3. Figure 2 depicts the intensity difference $`I(T=1.4`$K$`)I(T=4.2`$K$`)`$ of these scans. A resolution limited additional intensity at low temperature can be clearly seen. Figure 3 shows the temperature dependence of the peak intensity at $`=(1,0,3)`$. The rapid increase of the intensity below $`T_\mathrm{N}=3.45`$ K is observed. This transition temperature is in agreement with the phase diagram of this doped sample obtained from the magnetization measurements . We thus infer that the additional intensity at low $`T`$ is of magnetic origin. These magnetic intensities at low temperature are observed at $`Q=(h,0,l)`$ for integer $`h`$ and odd $`l`$ in the doped sample. These reciprocal points are the same as those, at which the magnetic Bragg peaks indicative of the field-induced transverse Néel ordering were observed in TlCuCl3. In order to determine the spin structure of the impurity-induced antiferromagnetic ordered phase in Tl(Cu0.97Mg0.03)Cl3, we measured the integrated intensities of nine Bragg reflections at $`T=1.4`$ and 4.2 K. The integrated intensities of the magnetic Bragg reflections were obtained by fitting the difference of the observed intensities at $`T=1.4`$ and 4.2 K using a Gaussian function, as shown in Fig. 2. The results are summalized in Table I. The magnetic Bragg reflections are resolution limited (e.g. see Fig. 2) and correspond to a correlation length greater than 150 $`\AA `$. This indicates that the ordering is of a long range nature. The intensities of nuclear Bragg reflections were also measured at $`=(h,0,l)`$ with even $`l`$ in order to estimate the magnitude of the effective magnetic moment averaged per site. Because the parent compound TlCuCl3 belongs to the space group $`P2_1/c`$, nuclear peaks are expected only at $`=(h,0,l)`$ with even $`l`$. However, as shown in the inset of Fig. 2, the nuclear peaks, though weak, were observed also for odd $`l`$ at $`T=4.2`$ K. In the pure TlCuCl3, very weak nuclear peaks have been observed for odd $`l`$  which may be attributed to the impurity induced small distortion lowering the local symmetry. The intensities of the odd $`l`$ nuclear peaks observed in the doped compound Tl(Cu0.97Mg0.03)Cl3 was larger than those observed in the pure TlCuCl3, but still smaller than the allowed even $`l`$ peaks in Tl(Cu0.97Mg0.03)Cl3. We checked that the allowed nuclear Bragg intensities in the present measurements are consistent with the nuclear structure factor evaluated from the crystal structure of TlCuCl3 for the weak reflection, in which the extinction effect is almost ineffective. As shown in reference , it is also confirmed that the magnetic susceptibilities of this doped sample behave the same as TlCuCl3 above $`T=7`$ K, indicating the absence of any structural phase transition. We therefore infer that the nuclear peaks observed at odd $`l`$ are due to the local disturbance of lattice caused by the Mg doping. One possible reason for such a local disturbance could be caused, for instance, by the difference between the Jahn-Teller (JT) distorted CuCl6 octahedra and non JT active ion containing MgCl6 octahedra, so that the extinction law for odd $`l`$ could be locally broken. Although more detailed informations of the observed reflections at odd $`l`$ can be obtained by powder diffraction measurements at low temperature, we believe that the magnetic results presented here will be not affected. To refine the magnetic structure, we therefore used the atomic coordinates of TlCuCl3  and the nuclear scattering lengths $`b_{\mathrm{Tl}}=0.878`$, $`b_{\mathrm{Cu}}=0.772`$ and $`b_{\mathrm{Cl}}=0.958`$ in the unit of 10-12 cm . The magnetic form factors of Cu2+ were taken from reference . The extinction effect was evaluated by comparing observed and calculated intensities for various nuclear Bragg reflections.

Because the magnetic Bragg reflections were observed at $`=(h,0,l)`$ with integer $`h`$ and odd $`l`$, the antiferromagnetic ordering as shown in Fig. 1 is expected. As mentioned in Introduction, it is suggested that the spin lies in the $`ac`$ plane from the magnetization measurements . Hence the free parameters in this calculation are only $`\alpha `$ and $`C`$, which are the angle between the spins and the $`a`$-axis, and the scale factor, respectively. The calculated intensities of the best fit with $`\alpha =34.0^{}\pm 4.7^{}`$ are indicated in Table I and the overall agreement can be considered as being satisfactory. The obtained angle $`\alpha `$ is consistent with the magnetization measurements of Tl(Cu1-xMgx)Cl3, and is, with in error bars, the same as that in the spin structure of the field-induced ordered phase of TlCuCl3 for $`b`$. Hence we conclude that the spin structure of the impurity-induced antiferromagnetic ordered phase on average in Tl(Cu0.97Mg0.03)Cl3 is the same as that of the field-induced magnetic ordered phase for $`b`$ in the parent compound TlCuCl3 (”on average” means that the magnitude of the ordered moments in the impurity-induced antiferromagnetic ordered phase may be not uniform.).

Comparing magnetic peak intensities with those of nuclear reflections, the magnitude of the effective magnetic moment averaged per site at $`T=1.4`$ K was evaluated as $`m_{\mathrm{eff}}=g\mu _\mathrm{B}S_{\mathrm{eff}}=0.12(1)`$ $`\mu _\mathrm{B}`$. On the right abscissa of Fig. 3, we show $`m_{\mathrm{eff}}^2`$. This value is much smaller than 1 $`\mu _\mathrm{B}`$, which is the full moment of Cu2+, and close to that in the impurity-induced ordered phase observed in the other doped-Cu2+ compounds, (Cu1-xZnx)GeO3  and (Cu1-xMgx)GeO3 . As shown in Fig. 3, no pronounced diffuse scattering can be seen, and the increase of the magnetic peak intensity is almost linear in the vicinity of $`T_\mathrm{N}`$.

### B Magnetic Excitations

Constant-$``$ energy scan profiles were measured along $`(h,0,1)`$, $`(0,0,l)`$, $`(h,0,2h+1)`$ and $`(h,0,2h+1.4)`$ with $`0h0.5`$ and $`1l2`$ at $`T=1.5`$ K, which is lower than the Néel temperature $`T_\mathrm{N}=3.45`$ K in Tl(Cu0.97Mg0.03)Cl3. Figure 4 shows the representative scan profiles for $`=(h,0,2h+1)`$ and $`(h,0,2h+1.4)`$, in which the magnetic excitation is most dispersive and less dispersive, respectively. A well-defined single excitation can be observed in almost all scans. The scan profiles were fitted with a Gaussian function to evaluate the excitation energy, as shown by the solid lines in Fig. 4. The obtained scan profiles in Tl(Cu0.97Mg0.03)Cl3 were almost the same as those obtained in the parent compound TlCuCl3 , and we confirmed that the origin of the observed excitation is magnetic from the temperature dependence. Hence we can expect that the observed excitation is the triplet magnetic excitation in the impurity-induced ordered state. The dispersion relation $`\omega ()`$ of the excitation obtained for the $`a^{}c^{}`$ scattering plane at $`T=1.5`$ K is summarized in Fig. 5. The dispersion curves of the triplet excitation in the parent compound TlCuCl3  is also depicted in Fig. 5 by the dashed lines. As shown in Fig. 5, there is not much difference between the dispersion relations of Tl(Cu0.97Mg0.03)Cl3 and those of TlCuCl3, except in the vicinity of $`=(0,0,1)`$. Based on the present results, it is evident that the periodicity of the triplet excitation in Tl(Cu0.97Mg0.03)Cl3 is the same as that of the nuclear reciprocal lattice along the $`a^{}`$-axis, but doubled along the $`c^{}`$-axis, as observed in TlCuCl3 . Hence, it is deduced that the lowest triplet excitation, corresponding to the spin gap, occurs at $`=(h,0,l)`$ with integer $`h`$ and odd $`l`$ in the $`a^{}c^{}`$ plane. Figure 6 shows the constant-$``$ energy scan profiles in Tl(Cu0.97Mg0.03)Cl3 for $`=(0,0,1)`$ at various temperatures. A well-defined single excitation was also observed at all temperatures. Hence it is confirmed that the spin gap remains even in the impurity-induced ordered phase. Because the excitation was also observed at $`T=5.2`$ K, which is higher than $`T_\mathrm{N}`$, the excitation is not spin-wave excitation by the antiferromagnetic ordering, but the triplet excitation from the ground state. The horizontal bars in Fig. 6 denote the calculated instrumental resolution widths. The broadening of the spectra can be seen. Far from $`=(0,0,1)`$, it was confirmed that almost all triplet excitations have widths equal to the resolution limit, though studied with coarser resolution. Such behaviors were also reported in (Cu1-xZnx)GeO3  and Cu(Ge1-xSix)O3 . The solid lines in Fig. 6 are fits to the dispersion relations convoluted with the instrumental resolution. A Lorentzian function for the magnetic excitation is used. The free parameters are $`I`$, $`\mathrm{\Gamma }`$ and $`E_{(0,0,1)}`$, which are the integrated intensity, the Lorentzian width and the spin gap, respectively. The shape of the dispersion relation in the vicinity of $``$=(0, 0, 1) was fixed to that obtained from the RPA approximation (see below). The temperature dependence of the energy of the triplet excitation at $`=(0,0,1)`$ is shown in Fig. 7. The rapid increase of the excitation energy can be clearly seen below $`T_\mathrm{N}=3.45`$ K. The triplet excitation depends on temperature due to the temperature dependence of the occupation difference between the singlet and triplet states . However, the increase of temperature causes to flatten the dispersion relation due to the suppression of the interdimer correlations by the decrease of the occupation difference, namely the energy of the lowest excitation corresponding to the spin gap should rather decrease upon decreasing temperature. Hence, we can expect that the rapid increase of the spin gap is caused by the impurity-induced antiferromagnetic ordering and can conclude that the impurity-induced antiferromagnetic ordering coexists with the spin gap in Tl(Cu0.97Mg0.03)Cl3. The energy of the lowest excitation is $`E=1.3`$ meV at $`T=5.2`$ K, which is higher than $`T_\mathrm{N}`$, and is a little larger than that of 0.65 $``$ 0.8 meV estimated for the pure TlCuCl3 . This indicates that the spin gap is also enhanced by the Mg doping, irrespective of the ordering. The temperature dependence of $`\mathrm{\Gamma }`$ is also shown in inset of Fig. 7. No significant variation of $`\mathrm{\Gamma }`$ can be seen.

We fit the obtained dispersion relations, as shown in Fig. 5, by the following equation obtained from the RPA approximation, which is applied to the parent compound TlCuCl3

$$\omega _\pm ()=\sqrt{J^2+2J\delta \omega _\pm ()},$$
(1)
where

$`\delta \omega _\pm ()`$ $`=`$ $`[J_{(100)}^{\mathrm{eff}}\mathrm{cos}(2\pi h)+J_{(200)}^{\mathrm{eff}}\mathrm{cos}(4\pi h)`$ (5)
$`+J_{(201)}^{\mathrm{eff}}\mathrm{cos}\{2\pi (2h+l)\}]`$
$`\pm 2[J_{(1\frac{1}{2}\frac{1}{2})}^{\mathrm{eff}}\mathrm{cos}\{\pi (2h+l)\}\mathrm{cos}(\pi k)`$
$`+J_{(0\frac{1}{2}\frac{1}{2})}^{\mathrm{eff}}\mathrm{cos}(\pi k)\mathrm{cos}(\pi l)].`$
In the equations, $`J`$ denotes the main intradimer exchange interaction, and $`J_{(lmn)}^{\mathrm{eff}}`$ denote the effective interactions between dimers separated by a lattice vector $`l𝕒+m𝕓+n𝕔`$ and are expressed as

$`J_{(100)}^{\mathrm{eff}}`$ $`=`$ $`{\displaystyle \frac{1}{2}}\left(2J_{(100)}J_{(100)}^{}\right),`$ (6)
$`J_{(200)}^{\mathrm{eff}}`$ $`=`$ $`{\displaystyle \frac{1}{2}}\left(2J_{(200)}J_{(200)}^{}\right),`$ (7)
$`J_{(1\frac{1}{2}\frac{1}{2})}^{\mathrm{eff}}`$ $`=`$ $`{\displaystyle \frac{1}{2}}\left(J_{(1\frac{1}{2}\frac{1}{2})}J_{(1\frac{1}{2}\frac{1}{2})}^{}\right),`$ (8)
$`J_{(0\frac{1}{2}\frac{1}{2})}^{\mathrm{eff}}`$ $`=`$ $`{\displaystyle \frac{1}{2}}\left(J_{(0\frac{1}{2}\frac{1}{2})}J_{(0\frac{1}{2}\frac{1}{2})}^{}\right),`$ (9)
$`J_{(201)}^{\mathrm{eff}}`$ $`=`$ $`{\displaystyle \frac{1}{2}}J_{(201)}^{},`$ (10)
where $`J_{lmn}`$ and $`J_{lmn}^{}`$ are shown in Fig. 1. Under the present experimental condition, i.e., $``$ in the $`a^{}c^{}`$ plane, the $`\omega _+()`$ branch gives the only nonvanishing contribution. The solid lines in Fig. 5 indicate the calculated results with the exchange parameters, as shown in Table II. The experimental dispersion curves can be reproduced well by the fitting. Compared to the parent compound TlCuCl3, the magnitude of the intradimer interaction $`J`$ becomes slightly larger, while that of the important effective interdimer interactions $`J_{(100)}^{\mathrm{eff}}`$, $`J_{(1\frac{1}{2}\frac{1}{2})}^{\mathrm{eff}}`$ and $`J_{(201)}^{\mathrm{eff}}`$ become slightly smaller.

Because the impurity-induced antiferromagnetic ordering occurs, we can expect that the antiferromagnetic spin-wave excitation is observed together with the triplet excitation, as observed in (Cu1-xZnx)GeO3  and Cu(Ge1-xSix)O3 . However, no antiferromagnetic spin-wave excitation emerging from the antiferromagnetic zone center could be observed in the present neutron scattering experiments though the antiferromagnetic resonance has been observed in this system by the ESR measurements . In both (Cu1-xZnx)GeO3  and Cu(Ge1-xSix)O3 , it was reported that the energy of the antiferromagnetic spin-wave excitation is very small compared with that of the triplet excitation and that the line width broadens rapidly with increasing $`q`$, which is distance from the antiferromagnetic zone center in reciprocal space. Hence it may be that we could not observe the low energy spin-wave excitation due to the large incoherent scattering by the chlorine near the zone center $`=(0,0,1)`$ and due to the rapid broadening of the spectra far from $`=(0,0,1)`$.

The present measurements were performed in zero magnetic field. We plan to perform the neutron scattering measurements for Tl(Cu1-xMgx)Cl3 in a magnetic field. Especially, when a magnetic field higher than the gap field $`H_\mathrm{g}`$ is applied at the temperature lower than $`T_\mathrm{N}`$, the spin gap between the ground state, in which the impurity-induced antiferromagnetic ordering occurs, and one of the triplet excited states vanishes due to the Zeeman interaction, and then an additional phase transition may occur, similar to the field-induced magnetic ordering in the parent compound TlCuCl3.

## IV Conclusion

We have presented the results of neutron elastic and inelastic scattering on the doped spin gap system Tl(Cu1-xMgx)Cl3 with $`x=0.03`$. The magnetic Bragg reflections indicative of the impurity-induced antiferromagnetic ordering was observed at $`=(h,0,l)`$ with integer $`h`$ and odd $`l`$ below $`T_\mathrm{N}=3.45`$ K. The spin structure in the impurity-induced ordered phase was determined, as shown in Fig. 1, with $`\alpha =34.0^{}\pm 4.7^{}`$. It was found that the spin structure of the impurity-induced antiferromagnetic ordered phase on average in Tl(Cu0.97Mg0.03)Cl3 is the same as that of the field-induced magnetic ordered phase for $`b`$ in the parent compound TlCuCl3. The triplet magnetic excitation was clearly observed in the $`a^{}`$-$`c^{}`$ plane. The dispersion relations of the triplet excitation were determined, as shown in Fig. 5. The main intradimer interaction and the effective interdimer interactions were obtained, as shown in Table II, using the RPA approximation. The lowest triplet excitation corresponding to the spin gap was also observed at $`=(h,0,l)`$ with integer $`h`$ and odd $`l`$, as observed in TlCuCl3. We found the rapid increase of the spin gap below $`T_\mathrm{N}`$ upon decreasing temperature. This indicates that the impurity-induced antiferromagnetic ordering coexists with the spin gap in Tl(Cu0.97Mg0.03)Cl3. No antiferromagnetic spin-wave excitation could be observed.

###### Acknowledgements.

We would like to thank N. Metoki for experimental support on neutron scattering measurements and for stimulating discussions. The technical support of Y. Shimojo is also acknowledged. This work was supported by the Toray Science Foundation and a Grant-in-Aid for Scientific Research on Priority Areas (B) from the Ministry of Education, Culture, Sports, Science and Technology of Japan.


format: text

text:
# Radiation-induced magnetoresistance oscillation in a two-dimensional electron gas in Faraday geometry

## Abstract

Microwave-radiation induced giant magnetoresistance oscillations recently discovered in high-mobility two-dimensional electron systems are analyzed theoretically. Multiphoton-assisted impurity scatterings are shown to be the primary origin of the oscillation. Based on a theory which considers the interaction of electrons with electromagnetic fields and the effect of the cyclotron resonance in Faraday geometry, we are able not only to reproduce the correct period, phase and the negative resistivity of the main oscillation, but also to predict the secondary peaks and additional maxima and minima observed in the experiments. These peak-valley structures are identified to relate respectively to single-, double- and triple-photon processes.

The discovery of a new type of giant magnetorersistance oscillations in a high mobility two-dimensional (2D) electron gas (EG) subject to crossed microwave (MW) radiation field and a magnetic field,Zud01 ; Ye ; Mani ; Zud03 ; Mani05507  especially the observation of ”zero-resistance” states developed from the oscillation minima,Mani ; Zud03 ; Yang ; Dor  has revived tremendous interest in magneto-transport in 2D electron systems.Durst ; Andreev ; Anderson ; Xie ; Phil ; Koul  These radiation-induced oscillations of longitudinal resistivity $`R_{xx}`$ are accurately periodical in inverse magnetic field $`1/B`$ with period determined by the MW frequency $`\omega `$ rather than the electron density $`N_\mathrm{e}`$. The observed $`R_{xx}`$ oscillations exhibit a smooth magnetic-field variation with resistivity maxima at $`\omega /\omega _c=j\delta _{}`$ and minima at $`\omega /\omega _c=j+\delta _+`$ ($`\omega _c`$ is the cyclotron frequency, $`j=1,2,3\mathrm{}`$) having positive $`\delta _\pm `$ around $`\frac{1}{4}`$.Mani  The resistivity minimum goes downward with increasing sample mobility and/or increasing radiation intensity until a ”zero-resistance” state shows up, while the Hall resistivity keeps the classical form $`R_{xy}=B/N_\mathrm{e}e`$ with no sign of quantum Hall plateau over the whole magnetic field range exhibiting $`R_{xx}`$ oscillation.

To explore the origin of the peculiar ”zero-resistance” states, different mechanisms have been suggested.Durst ; Andreev ; Anderson ; Xie ; Phil ; Koul  It is understood that the appearance of negative longitudinal resistivity or conductivity in a uniform model suffices to explain the observed vanishing resistance.Andreev  The possibility of absolute negative photoconductance in a 2DEG subject to a perpendicular magnetic field was first explored 30 years ago by Ryzhii.Ryz ; Ryz86  Recent worksDurst ; Anderson ; Xie  indicated that the periodical structure of the density of states (DOS) of the 2DEG in a magnetic field and the photon-excited electron scatterings are the origin of the magnetoresistance oscillations. Durst et al.Durst  presented a microscopic analysis for the conductivity assuming a $`\delta `$-correlated disorder and a simple form of the 2D electron self-energy oscillating with the magnetic field, obtaining the correct period, phase and the possible negative resistivity. Shi and XieXie  reported a similar result using the Tien and Gorden current formulaTien  for photon-assisted coherent tunneling. In these studies, however, the magnetic field is to provide an oscillatory DOS only and the high frequency (HF) field enters as if there is no magnetic field or with a magnetic field in Voigt configuration. The experimental setup requires to deal with the magnetic field $`𝐁`$ perpendicular to the HF electric field. In this Faraday configuration, the electron moving due to HF field, experiences a Lorentz force which gives rise to additional electron motion in the perpendicular direction. In the range of $`\omega \omega _c`$, the electron velocities in both directions are of the same order of magnitude and are resonantly enhanced. This cyclotron resonance (CR) of the HF current response will certainly change the way how the photons assist the electron scattering.

In this Letter, we construct a microscopic model for the interaction of electrons with electromagnetic fields in Faraday geometry. The basic idea is that, under the influence of a spatially uniform HF electric field, the center-of-mass (CM) of the whole 2DEG in a magnetic field performs a cyclotron motion modulated by the HF field of frequency $`\omega `$. In an electron gas having impurity and/or phonon scatterings, there exist couplings between this CM motion and the relative motion of the 2D electrons. It is through these couplings that a spatially uniform HF electric field affects the relative motion of electrons by opening additional channels for electron transition between different states. Based on the theory for photon-assisted magnetotransport developed from this physical idea, we show that the main experimental results of the radiation-induced magnetoresistance oscillations can be well reproduced. We also obtain the secondary peaks and additional maxima and minima observed in the experiments.Zud03 ; Dor

For a general treatment, we consider $`N_\mathrm{e}`$ electrons in a unit area of a quasi-2D system in the $`x`$-$`y`$ plane with a confining potential $`V(z)`$ in the $`z`$-direction. These electrons, besides interacting with each other, are scattered by random impurities/disorders and by phonons in the lattice. To include possible elliptically polarized MW illumination we assume that a uniform dc electric field $`𝐄_0`$ and ac field $`𝐄_t𝐄_s\mathrm{sin}(\omega t)+𝐄_c\mathrm{cos}(\omega t)`$ of frequency $`\omega `$ are applied in the $`x`$-$`y`$ plane, together with a magnetic field $`𝐁=(0,0,B)`$ along the $`z`$ direction. In terms of the 2D CM momentum and coordinate of the electron system,Lei85 ; Lei851 ; Ting  which are defined as $`𝐏_j𝐩_j`$ and $`𝐑N_\mathrm{e}^1_j𝐫_j`$ with $`𝐩_j(p_{jx},p_{jy})`$ and $`𝐫_j(x_j,y_j)`$ being the momentum and coordinate of the $`j`$th electron in the 2D plane, and the relative electron momentum and coordinate $`𝐩_j^{}𝐩_j𝐏/N_\mathrm{e}`$ and $`𝐫_j^{}𝐫_j𝐑`$, the Hamiltonian of the system can be written as the sum of a CM part $`H_{\mathrm{cm}}`$ and a relative-motion part $`H_{\mathrm{er}}`$ ($`𝐀(𝐫)`$ is the vector potential of the $`𝐁`$ field),

$`H_{\mathrm{cm}}={\displaystyle \frac{1}{2N_\mathrm{e}m}}(𝐏N_\mathrm{e}e𝐀(𝐑))^2N_\mathrm{e}e(𝐄_0+𝐄_t)𝐑,`$ (1)
$`H_{\mathrm{er}}={\displaystyle \underset{j}{}}\left[{\displaystyle \frac{1}{2m}}\left(𝐩_j^{}e𝐀(𝐫_j^{})\right)^2+{\displaystyle \frac{p_{jz}^2}{2m_z}}+V(z_j)\right]`$
$`+{\displaystyle \underset{i<j}{}}V_c(𝐫_i^{}𝐫_j^{},z_i,z_j),`$ (2)
together with couplings of electrons to impurities and phonons, $`H_{\mathrm{ei}}`$ and $`H_{\mathrm{ep}}`$. Here $`m`$ and $`m_z`$ are respectively the electron effective mass parallel and perpendicular to the plane, and $`V_c`$ stands for the electron-electron Coulomb interaction. Note that although in $`H_{\mathrm{cm}}`$ and $`H_{\mathrm{er}}`$ the CM and the relative electron motion are completely separated, the CM coordinate $`𝐑`$ enters $`H_{\mathrm{ei}}`$ and $`H_{\mathrm{ep}}`$.Lei85 ; Lei851  Starting from the Heisenberg operator equations for the rate of change of the CM velocity $`\dot{𝐕}=i[𝐕,H]+𝐕/t`$ with $`𝐕=i[𝐑,H]`$, and that of the relative electron energy $`\dot{H}_{\mathrm{er}}=\mathrm{i}[H_{\mathrm{er}},H]`$, we proceed with the determination of their statistical averages.

The CM coordinate $`𝐑`$ and velocity $`𝐕`$ in these equations can be treated classically, i.e. as the time-dependent expectation values of the CM coordinate and velocity,Lei85  $`𝐑(t)`$ and $`𝐕(t)`$, such that $`𝐑(t)𝐑(t^{})=_t^{}^t𝐕(s)𝑑s`$. We are concerned with the steady transport under an irradiation of single frequency and focus on the photon-induced dc resistivity and the energy absorption of the HF field. These quantities are directly related to the time-averaged and/or base-frequency oscillating components of the CM velocity. At the same time, in an ordinary semiconductor the effect of higher harmonic current is safely negligible for the HF field intensity in the experiments. Hence, it suffices to assume that the CM velocity, i.e. the electron drift velocity, consists of a dc part $`𝐯_0`$ and a stationary time-dependent part that

$$𝐕(t)=𝐯_0+𝐯_1\mathrm{cos}(\omega t)+𝐯_2\mathrm{sin}(\omega t).$$
(3)
This time-dependent CM velocity enters all the operator equations having couplings to impurities and/or phonons in the form of the following exponential factor, which can be expanded in terms of Bessel functions $`\mathrm{J}_n(x)`$:

$`\mathrm{e}^{\mathrm{i}𝐪_t^{}^t𝐕(s)𝑑s}={\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}\mathrm{J}_n^2(\xi )\mathrm{e}^{\mathrm{i}(𝐪𝐯_0n\omega )(tt^{})}+`$
$`{\displaystyle \underset{m0}{}}\mathrm{e}^{\mathrm{i}m(\omega t\phi )}{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}\mathrm{J}_n(\xi )\mathrm{J}_{nm}(\xi )\mathrm{e}^{\mathrm{i}(𝐪𝐯_0n\omega )(tt^{})}.`$
Here $`\xi \sqrt{(𝐪_{}𝐯_1)^2+(𝐪_{}𝐯_2)^2}/\omega `$ and $`\mathrm{tan}\phi =(𝐪𝐯_2)/(𝐪𝐯_1)`$. On the other hand, for 2D systems having electron sheet density of order of 1015 m-2, the intra-band and inter-band Coulomb interactions are sufficiently strong that it is adequate to describe the relative-electron transport state using a single electron temperature $`T_\mathrm{e}`$. Except this, the electron-electron interaction is treated only in a mean-field level under random phase approximation (RPA).Lei85 ; Lei851  For the determination of unknown parameters $`𝐯_0`$, $`𝐯_1`$, $`𝐯_2`$, and $`T_\mathrm{e}`$, it suffices to know the damping force up to the base frequency oscillating term $`𝐅(t)=𝐅_0+𝐅_s\mathrm{sin}(\omega t)+𝐅_c\mathrm{cos}(\omega t)`$, and the energy-related quantities up to the time-average term. We finally obtain the following force and energy balance equations:

$`0`$ $`=`$ $`N_\mathrm{e}e𝐄_0+N_\mathrm{e}e(𝐯_0\times 𝐁)+𝐅_0,`$ (4)
$`𝐯_1`$ $`=`$ $`{\displaystyle \frac{e𝐄_s}{m\omega }}+{\displaystyle \frac{𝐅_s}{N_\mathrm{e}m\omega }}{\displaystyle \frac{e}{m\omega }}(𝐯_2\times 𝐁),`$ (5)
$`𝐯_2`$ $`=`$ $`{\displaystyle \frac{e𝐄_c}{m\omega }}+{\displaystyle \frac{𝐅_c}{N_\mathrm{e}m\omega }}{\displaystyle \frac{e}{m\omega }}(𝐯_1\times 𝐁),`$ (6)
$$N_\mathrm{e}e𝐄_0𝐯_0+S_\mathrm{p}W=0.$$
(7)
Here

$`𝐅_0={\displaystyle \underset{𝐪_{}}{}}\left|U(𝐪_{})\right|^2{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}𝐪_{}\mathrm{J}_n^2(\xi )\mathrm{\Pi }_2(𝐪_{},\omega _0n\omega )`$
$`+{\displaystyle \underset{𝐪}{}}\left|M(𝐪)\right|^2{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}𝐪_{}\mathrm{J}_n^2(\xi )\mathrm{\Lambda }_2(𝐪,\omega _0+\mathrm{\Omega }_𝐪n\omega )`$ (8)
is the time-averaged damping force, $`S_\mathrm{p}`$ is the time-averaged rate of the electron energy-gain from the HF field, $`\frac{1}{2}N_\mathrm{e}e(𝐄_s𝐯_2+𝐄_c𝐯_1)`$, which can be written in a form obtained from the right hand side of Eq. (8) by replacing the $`𝐪_{}`$ factor with $`n\omega `$, and $`W`$ is the time-averaged rate of the electron energy-loss due to coupling with phonons, whose expression can be obtained from the second term on the right hand side of Eq. (8) by replacing the $`𝐪_{}`$ factor with $`\mathrm{\Omega }_𝐪`$, the energy of a wavevector-$`𝐪`$ phonon. The oscillating frictional force amplitudes $`𝐅_s𝐅_{22}𝐅_{11}`$ and $`𝐅_c𝐅_{21}+𝐅_{12}`$ are given by ($`\mu =1,2`$)

$`𝐅_{1\mu }={\displaystyle \underset{𝐪_{}}{}}𝐪_{}\eta _\mu |U(𝐪_{})|^2{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}\left[\mathrm{J}_n^2(\xi )\right]^{}\mathrm{\Pi }_1(𝐪_{},\omega _0n\omega )`$
$`{\displaystyle \underset{𝐪}{}}𝐪_{}\eta _\mu |M(𝐪)|^2{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}\left[\mathrm{J}_n^2(\xi )\right]^{}\mathrm{\Lambda }_1(𝐪,\omega _0+\mathrm{\Omega }_𝐪n\omega ),`$
$`𝐅_{2\mu }={\displaystyle \underset{𝐪_{}}{}}𝐪_{}{\displaystyle \frac{\eta _\mu }{\xi }}|U(𝐪_{})|^2{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}2n\mathrm{J}_n^2(\xi )\mathrm{\Pi }_2(𝐪_{},\omega _0n\omega )`$
$`+{\displaystyle \underset{𝐪}{}}𝐪_{}{\displaystyle \frac{\eta _\mu }{\xi }}|M(𝐪)|^2{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}2n\mathrm{J}_n^2(\xi )\mathrm{\Lambda }_2(𝐪,\omega _0+\mathrm{\Omega }_𝐪n\omega ).`$
In these expressions, $`\eta _\mu 𝐪_{}𝐯_\mu /\omega \xi `$; $`\omega _0𝐪_{}𝐯_0`$; $`U(𝐪_{})`$ and $`M(𝐪)`$ stand for effective impurity and phonon scattering potentials, $`\mathrm{\Pi }_2(𝐪_{},\mathrm{\Omega })`$ and $`\mathrm{\Lambda }_2(𝐪,\mathrm{\Omega })=2\mathrm{\Pi }_2(𝐪_{},\mathrm{\Omega })[n(\mathrm{\Omega }_𝐪/T)n(\mathrm{\Omega }/T_\mathrm{e})]`$ (with $`n(x)1/(\mathrm{e}^x1)`$) are the imaginary parts of the electron density correlation function and electron-phonon correlation function in the presence of the magnetic field. $`\mathrm{\Pi }_1(𝐪_{},\mathrm{\Omega })`$ and $`\mathrm{\Lambda }_1(𝐪,\mathrm{\Omega })`$ are the real parts of these two correlation functions. The effect of interparticle Coulomb interactions are included in them to the degree of level broadening and RPA screening.

The HF field enters through the argument $`\xi `$ of the Bessel functions in $`𝐅_0`$, $`𝐅_{\mu \nu }`$, $`W`$ and $`S_\mathrm{p}`$. Compared with that without the HF field ($`n=0`$ term only),Lei98  we see that in an electron gas having impurity and/or phonon scattering (otherwise homogeneous), a HF field of frequency $`\omega `$ opens additional channels for electron transition: an electron in a state can absorb or emit one or several photons and scattered to a different state with the help of impurities and/or phonons. The sum over $`|n|1`$ represents contributions of single and multiple photon processes of frequency-$`\omega `$ photons. These photon-assisted scatterings help to transfer energy from the HF field to the electron system ($`S_\mathrm{p}`$) and give rise to additional damping force on the moving electrons. Note that $`𝐯_\mathrm{𝟏}`$ and $`𝐯_2`$ always exhibit CR in the range $`\omega \omega _c`$, as can be seen from Eqs.(5) and (6) rewritten in the form

$`𝐯_1=(1\omega _c^2/\omega ^2)^1\{{\displaystyle \frac{e}{m\omega }}[𝐄_s+{\displaystyle \frac{e}{m\omega }}(𝐄_c\times 𝐁)]`$
$`+{\displaystyle \frac{1}{N_\mathrm{e}m\omega }}[𝐅_s+{\displaystyle \frac{e}{m\omega }}(𝐅_c\times 𝐁)]\},`$ (9)
$`𝐯_2=(\omega _c^2/\omega ^21)^1\{{\displaystyle \frac{e}{m\omega }}[𝐄_c{\displaystyle \frac{e}{m\omega }}(𝐄_s\times 𝐁)]`$
$`+{\displaystyle \frac{1}{N_\mathrm{e}m\omega }}[𝐅_c{\displaystyle \frac{e}{m\omega }}(𝐅_s\times 𝐁)]\}.`$ (10)
Therefore, $`\xi `$ may be significantly different from the argument of the corresponding Bessel functions in the case without a magnetic field or with a magnetic field in Voigt configuration.Lei98

Eqs. (4)-(7) can be used to describe the transport and optical properties of magnetically-biased quasi-2D semiconductors subject to a dc field and a HF field. Taking $`𝐯_0=(v_{0x},0,0)`$ in the $`x`$ direction, Eq. (4) yields transverse resistivity $`R_{xy}E_{0y}/N_\mathrm{e}ev_{0x}=B/N_\mathrm{e}e`$, and longitudinal resistivity $`R_{xx}E_{0x}/N_\mathrm{e}ev_{0x}=F_0/N_\mathrm{e}^2e^2v_{0x}`$. The linear magnetoresistivity is then

$`R_{xx}`$ $`=`$ $`{\displaystyle \underset{𝐪_{}}{}}q_x^2{\displaystyle \frac{|U(𝐪_{})|^2}{N_\mathrm{e}^2e^2}}{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}\mathrm{J}_n^2(\xi ){\displaystyle \frac{\mathrm{\Pi }_2}{\mathrm{\Omega }}}|_{\mathrm{\Omega }=n\omega }`$ (11)
$`{\displaystyle \underset{𝐪}{}}q_x^2{\displaystyle \frac{\left|M(𝐪)\right|^2}{N_\mathrm{e}^2e^2}}{\displaystyle \underset{n=\mathrm{}}{\overset{\mathrm{}}{}}}\mathrm{J}_n^2(\xi ){\displaystyle \frac{\mathrm{\Lambda }_2}{\mathrm{\Omega }}}|_{\mathrm{\Omega }=\mathrm{\Omega }_𝐪+n\omega }.`$
The parameters $`𝐯_1`$, $`𝐯_2`$ and $`T_\mathrm{e}`$ in (11) should be determined by solving equations (5), (6) and (7) with vanishing $`𝐯_0`$. We see that although the transverse resistivity $`R_{xy}`$ remains the classical form, the longitudinal resistivity $`R_{xx}`$ can be strongly affected by the irradiation.

We calculate the unscreened $`\mathrm{\Pi }_2(𝐪_{},\mathrm{\Omega })`$ function of the 2D system in a magnetic field by means of Landau representation:Ting

$`\mathrm{\Pi }_2(𝐪_{},\mathrm{\Omega })={\displaystyle \frac{1}{2\pi l_\mathrm{B}^2}}{\displaystyle \underset{n,n^{}}{}}C_{n,n^{}}(l_\mathrm{B}^2q_{}^2/2)\mathrm{\Pi }_2(n,n^{},\mathrm{\Omega }),`$ (12)
$`\mathrm{\Pi }_2(n,n^{},\mathrm{\Omega })={\displaystyle \frac{2}{\pi }}{\displaystyle 𝑑\epsilon \left[f(\epsilon )f(\epsilon +\mathrm{\Omega })\right]}`$
$`\times \mathrm{Im}G_n(\epsilon +\mathrm{\Omega })\mathrm{Im}G_n^{}(\epsilon ),`$ (13)
where $`l_\mathrm{B}=\sqrt{1/|eB|}`$ is the magnetic length, $`C_{n,n+l}(Y)n![(n+l)!]^1Y^le^Y[L_n^l(Y)]^2`$ with $`L_n^l(Y)`$ the associate Laguerre polynomial, $`f(\epsilon )=\{\mathrm{exp}[(\epsilon \mu )/T_\mathrm{e}]+1\}^1`$ the Fermi distribution function, and $`\mathrm{Im}G_n(\epsilon )`$ is the imaginary part of the Green’s function, or the DOS, of the Landau level $`n`$. The real part functions $`\mathrm{\Pi }_1(𝐪_{},\mathrm{\Omega })`$ and $`\mathrm{\Lambda }_1(𝐪_{},\mathrm{\Omega })`$ can be obtained from their imaginary parts via the Kramers-Kronig relation.

In principle, to obtain the Green’s function $`G_n(\epsilon )`$, a self-consistent calculation has to be carried out with all the scattering mechanisms included.Leadley  In this Letter we do not attempt a self-consistent calculation of $`G_n(\epsilon )`$ but choose a Gaussian-type function for the purpose of demonstrating the $`R_{xx}`$ oscillations ($`\epsilon _n`$ is the energy of the $`n`$-th Landau level):Ando82

$$\mathrm{Im}G_n(\epsilon )=(\pi /2)^{\frac{1}{2}}\mathrm{\Gamma }^1\mathrm{exp}[(\epsilon \epsilon _n)^2/(2\mathrm{\Gamma }^2)]$$
(14)
with a broadening parameter $`\mathrm{\Gamma }=(2e\omega _c\alpha /\pi m\mu _0)^{1/2}`$, where $`\mu _0`$ is the linear mobility at temperature $`T`$ in the absence of the magnetic field and $`\alpha >1`$ is a semiempirical parameter to take account the difference of the transport scattering time determining the mobility $`\mu _0`$, from the single particle lifetime.Mani ; Durst ; Anderson

The moderate microwave intensity for the $`R_{xx}`$ oscillation in these high-mobility samples yield only slight electron heating, which is unimportant as far as the main phenomenon is concerned and is neglected for simplicity. We consider scatterings from remote impurities as well as from acoustic phonons. After solving $`𝐯_1`$ and $`𝐯_2`$ from Eqs. (9) and(10) the magnetoresisivity $`R_{xx}`$ can be obtained directly from Eq. (11). At lattice temperature $`T=1`$ K, the contribution from photon-assisted phonon scattering is minor. The role of acoustic phonons, however, becomes essential at elevated lattice temperatures. Calculations were carried out for linearly polarized MW fields with multiphoton processes included.

Fig. 1 shows the calculated longitudinal resistivity $`R_{xx}`$ versus $`\omega /\omega _c\gamma _c`$ subject to a linearly polarized MW radiation of frequency $`\omega /2\pi =100`$ GHz at four values of amplitude: $`E_s=20,45,65`$ and 80 V/cm. Shubnikov-de Haas (SdH) oscillations show up strongly at high $`\omega _c`$ side, and gradually decay away as $`1/\omega _c`$ increases. All resistivity curves exhibit pronounced oscillation having main oscillation period $`\gamma _c=1`$ (they are crossing at integer points $`\gamma _c=2,3,4,5`$). The resistivity maxima locate around $`\gamma _c=j\delta _{}`$ and minima around $`\gamma _c=j+\delta _+`$ with $`\delta _\pm 0.230.25`$ for $`j=3,4,5`$, $`\delta _\pm 0.170.21`$ for $`j=2`$, and even smaller $`\delta _\pm `$ for $`j=1`$. The magnitude of the oscillation increases with increasing HF field intensity for $`\gamma _c>1.5`$. Resistivity gets into negative value for $`E_s=80`$ V/cm around the minima at $`j=1,2`$ and 3, for $`E_s=65`$ V/cm at $`j=1`$ and 2, and for $`E_s=20`$ and 45 V/cm at $`j=1`$. All these features, which are in fairly good agreement with experimental findings,Zud01 ; Mani05507 ; Mani ; Zud03  are relevant mainly to single-photon ($`|n|=1`$) processes. Anomaly appears in the vicinity of $`\gamma _c=1`$, where the CR greatly enhances the effective amplitude of the HF field in photon-assisted scatterings and multiphoton processes show up. The amplitudes of the $`j=1`$ maximum and minimum no longer monotonically change with field intensity. Furthermore, there appears a shoulder around $`\gamma _c=1.5`$ on the curves of $`E_s=45`$ and 65 V/cm, and it develops into a secondary peak in the $`E_s=80`$ V/cm case. This has already been seen in the experiment (Fig. 2 in Ref. Zud03, ). The valley between $`\gamma _c=1.4`$ and 1.8 peaks can descend down to negative as $`E_s`$ increasing further (Fig. 1b). The appearance of the secondary peak is due to two-photon ($`|n|=2`$) processes.

Radiation-induced resistivity behavior at $`\gamma _c<1`$ is shown more clearly in the $`\omega /2\pi =60`$ GHz case. As seen in Fig. 1c, a shoulder around $`\gamma _c=`$ 0.4-0.6 with a minmum at $`\gamma _c=0.6`$ can be indentified from the SdH oscillation background for all three curves, which is related to two-photon process. With increasing MW strength there appears a clear peak around $`\gamma _c=0.68`$ and a valley around $`\gamma _c=0.76`$. This peak-valley is mainly due to three-photon ($`|n|=3`$) process. In the case of $`40`$ GHz, similar peak and valley also show up (Fig. 1d).

Qualitatively, the main oscillation features come from the symmetrical property of the DOS function in a magnetic field. Since $`G_n(\epsilon j\omega _c)=G_{nj}(\epsilon )`$ for any integer $`j`$, the impurity contribution to $`R_{xx}`$ from the $`n`$-photon process, which is related to the weighted summation of the derivative $`\mathrm{\Pi }_2`$ function over all the Landau levels at frequency $`n\omega `$ \[Eq. (11)\], has an intrinsic periodicity characterized by $`n\omega =j\omega _c`$. The main oscillation of $`R_{xx}`$ shown in Fig. 1a relates to single-photon process and characterized by $`\omega =j\omega _c`$. We have also performed calculation using a Lorentz-type DOS function and find that, although the oscillating amplitude and the exact peak and valley positions are somewhat different, the basic periodic feature of the radiation-induced magnetoresistivity oscillation remains.

This work was supported by the National Science Foundation of China, the Special Funds for Major State Basic Research Project, and the Shanghai Municipal Commission of Science and Technology.


text:
# Quantum Evaluation of Multi-Valued Boolean Functions

## Abstract

Our problem is to evaluate a multi-valued Boolean function $`F`$ through oracle calls. If $`F`$ is one-to-one and the size of its domain and range is the same, then our problem can be formulated as follows: Given an oracle $`f(a,x):\{0,1\}^n\times \{0,1\}^n\{0,1\}`$ and a fixed (but hidden) value $`a_0`$, we wish to obtain the value of $`a_0`$ by querying the oracle $`f(a_0,x)`$. Our goal is to minimize the number of such oracle calls (the query complexity) using a quantum mechanism.

Two popular oracles are the EQ-oracle defined as $`f(a,x)=1`$ iff $`x=a`$ and the IP-oracle defined as $`f(a,x)=axmod2`$. It is also well-known that the query complexity is $`\mathrm{\Theta }(\sqrt{N})`$ ($`N=2^n`$) for the EQ-oracle while only $`O(1)`$ for the IP-oracle. The main purpose of this paper is to fill this gap or to investigate what causes this large difference. To do so, we introduce a parameter $`K`$ as the maximum number of 1’s in a single column of $`T_f`$ where $`T_f`$ is the $`N\times N`$ truth-table of the oracle $`f(a,x)`$. Our main result shows that the (quantum) query complexity is heavily governed by this parameter $`K`$: ($`i`$) The query complexity is $`\mathrm{\Omega }(\sqrt{N/K})`$. ($`ii`$) This lower bound is tight in the sense that we can construct an explicit oracle whose query complexity is $`O(\sqrt{N/K})`$. ($`iii`$) The tight complexity, $`\mathrm{\Theta }(\frac{N}{K}+\mathrm{log}K)`$, is also obtained for the classical case. Thus, the quantum algorithm needs a quadratically less number of oracle calls when $`K`$ is small and this merit becomes larger when $`K`$ is large, e.g., $`\mathrm{log}K`$ v.s. constant when $`K=cN`$.

## 1 Introduction

In , Ambainis introduced the problem of evaluating a (multi-valued and incompletely specified) Boolean function $`F(x_0,\mathrm{},x_{N1})`$ using a quantum mechanism. This problem includes many interesting specific problems. For example, if we define

$$F(x_0,\mathrm{},x_{N1})=\{\begin{array}{cc}a\hfill & \text{if }x_a=1\text{ and }x_j=0\text{ for all }ja,\hfill \\ \text{undefined}\hfill & \text{otherwise},\hfill \end{array}$$

then evaluating this function $`F`$ is the same as the so-called Grover search. Also, if we define

$$F(x_0,\mathrm{},x_{N1})=\{\begin{array}{cc}a\hfill & \text{if }x_i=ai\text{ mod 2 for all }0iN1,\hfill \\ \text{undefined}\hfill & \text{otherwise},\hfill \end{array}$$

then this is the same as the so-called Bernstein-Vazirani problem  introduced in . “Quantum evaluation” assumes that we can obtain the value of variable $`x_i`$ only through an oracle $`O(i)`$. Since both functions are one-to-one, and their domain and range are of the same size, we can formulate the problem as follows.

Let $`n`$ be an integer $`1`$ and $`N=2^n`$. Then, given an oracle defined as a function

$$f(a,x):\{0,1\}^n\times \{0,1\}^n\{0,1\}$$

such that $`f(a_1,x)f(a_2,x)`$ for some $`x`$ if $`a_1a_2`$, and a fixed (and hidden) value $`a`$, we wish to obtain the value $`a`$, using the oracle $`f(a,x)`$. For the Grover search, one can easily see that the definition as

$$f(a,x)=\{\begin{array}{cc}1\hfill & \text{if }x=a,\hfill \\ 0\hfill & \text{otherwise},\hfill \end{array}$$

completely specifies the problem. This oracle is sometimes called the EQ oracle and is denoted by $`EQ_a(x)`$. See Fig. 1 for $`n=4`$. As illustrated in this figure, $`f(a,x)`$ is given by a truth table of size $`N\times N`$, where each row gives the value of the function $`F`$ of the previous definition. For example, we have $`F(1,0,\mathrm{},0)=0000`$ from the first row of the table. If the hidden value $`a`$ is $`0010`$ for example, the oracle returns value $`1`$ only when it is queried with $`x=0010`$. For the Bernstein-Vazirani problem, the similar definition is given as

$$f(a,x)=ax\text{mod }2,$$

which is called the inner product (IP) oracle and denoted by $`IP_a(x)`$. Its truth table for $`n=4`$ is given in Fig. 2. (Through this paper, we assume that the domain of the Boolean function $`F`$ has the same size as its range. More general cases, e.g., the size of the range is larger than the domain, will be mentioned briefly in the last section.)

As usual, our interest is in the (quantum) query complexity, i.e., how many oracle calls are needed to obtain the hidden value of $`a`$. It is well-known that the query complexity for the EQ-oracle is $`\mathrm{\Theta }(\sqrt{N})`$, while only $`O(1)`$ for the IP-oracle. Why does such a big difference exist between the EQ and IP oracles? The difference might become clearer if we compare their truth tables given in Figs. 1 and 2. One can immediately see that the table for $`IP_a`$ is well-balanced in terms of the numbers of $`0`$’s and $`1`$’s, but quite unbalanced for $`EQ_a`$. The natural consequence is that there should be intermediate oracles between those extreme ones for which the query complexity is also intermediate between $`\mathrm{\Theta }(\sqrt{N})`$ and $`O(1)`$. Furthermore these intermediate oracles could be characterized by some parameter in such a way that the query complexity heavily depends upon this parameter value and both $`EQ_a`$ and $`IP_a`$ are obtained as special cases. The main purpose of this paper is to show that this conjecture is true.

Our Contribution. Let $`T_f`$ be the truth-table of an oracle $`f(a,x)`$ like the ones given in Figs. 1 and 2. We can assume without loss of generality that the number of $`1`$’s is less than or equal to the number of $`0`$’s in each column of $`T_f`$. Let $`\mathrm{\#}_i(T_f)`$ denote the number of $`1`$’s ($`N/2`$) in the $`i`$-th column of $`T_f`$ and $`\mathrm{\#}(T_f)=\underset{i}{\mathrm{max}}\mathrm{\#}_i(T_f)`$. Then we can show that this single parameter $`\mathrm{\#}(T_f)`$ plays a key role, namely: ($`i`$) Let $`f(a,x)`$ be any oracle and $`K=\mathrm{\#}(T_f)`$. Then the query complexity of the search problem for $`f(a,x)`$ is $`\mathrm{\Omega }(\sqrt{N/K})`$. For this result, we extend the main theorem in . Although the extension may seem moderate in terms of the statement, it actually increases a lot of usefulness of the theorem. ($`ii`$) This lower bound is tight in the sense that we can construct an explicit oracle whose query complexity is $`O(\sqrt{N/K})`$. This oracle again includes both EQ and IP oracles as special cases. ($`iii`$) The tight complexity, $`\mathrm{\Theta }(\frac{N}{K}+\mathrm{log}K)`$, is also obtained for the classical case. Thus, the quantum algorithm needs a quadratically less number of oracle calls when $`K`$ is small and the merit is even larger when $`K`$ is large, e.g., $`\mathrm{log}K`$ v.s. constant when $`K=cN`$.

It should be noted that our (tight) bound $`\mathrm{\Theta }(\sqrt{N/K})`$ looks similar to the tight bound of the $`K`$-solution Grover search. This paper also examines the similarity and dissimilarity between our problem and the multi-solution (MS) Grover: In our notation, MS-Grover is the problem for obtaining, for a fixed oracle $`f(a,x)`$ and a fixed value $`a`$ both of which are hidden, the value $`b\{0,1\}^n`$ such that $`f(a,b)=1`$. ($`i`$) There is an oracle for which our problem needs $`\mathrm{\Omega }(\sqrt{N})`$ oracle calls while MS-Grover $`O(1)`$ ones. ($`ii`$) The complexity of the two problems is approximately the same if the oracle is “balanced” (defined later) and $`KN^{1/3}`$. Intuitively our problem seems at least as hard as MS-Grover, but we can also show the existence of an oracle which objects this intuition.

Related Results. Query complexity has constantly been one of the central topics in quantum computation, especially in proving lower bounds of quantum algorithms with oracles. Generally speaking, there are two popular techniques to derive quantum lower bounds, i.e., polynomials and adversary methods. The polynomials method was firstly introduced in quantum computation by  who borrowed the idea from the classical polynomial method. For example, it was shown that for bounded error cases, evaluations of $`AND`$ and $`OR`$ functions need $`\mathrm{\Theta }(\sqrt{N})`$ number of queries, while parity and majority functions at least $`N/2`$ and $`\mathrm{\Theta }(N)`$, respectively. Recently,  used the polynomials method to show the lower bounds for collisions and element distinctness problems.

The adversary method was used in , although their method resembles the classical one and for that reason it is called the hybrid method. Their method can be used, for example, to show the lower bound of the Grover Search. Recently, Ambainis introduced a quite general method, which is known as quantum adversary argument, for obtaining lower bounds of various problems, e.g., the Grover Search, AND of ORs and inverting a permutation. Some lower bounds are easier to obtain using the quantum adversary method than the polynomials one. The most recent result is by  who extended  to establish a lower bound of $`\mathrm{\Omega }(\sqrt{N})`$ on the bounded-error quantum query complexity of read-once Boolean functions.

## 2 Quantum Lower Bounds

Our lower bound result is related to the main theorem of . In this section, we give a slight extension of the Ambainis’ result, from which our result immediately follows. We first review Theorem 5.1 in . (Note that the statement uses the original definition of our problem.)

###### Proposition 1

Let $`F(x_0,\mathrm{},x_{N1})`$ be a function of $`N`$ $`\{0,1\}`$valued variables and $`X,Y`$ be two sets of inputs such that $`F(x)F(y)`$ if $`xX`$ and $`yY`$. Let $`RX\times Y`$ be such that
1. For every $`xX`$, there exist at least $`m`$ different $`yY`$ such that $`(x,y)R`$.
2. For every $`yY`$, there exist at least $`m^{}`$ different $`xX`$ such that $`(x,y)R`$.
3. For every $`x`$ and $`i\{0,\mathrm{},N1\}`$, there are at most $`l`$ different $`yY`$ such that $`(x,y)R`$ and $`x_iy_i`$.
4. For every $`y`$ and $`i\{0,\mathrm{},N1\}`$, there are at most $`l^{}`$ different $`xX`$ such that $`(x,y)R`$ and $`x_iy_i`$.
Then, any quantum algorithm computing $`F`$ uses $`\mathrm{\Omega }(\sqrt{\frac{mm^{}}{ll^{}}})`$ queries.

Our extension is due to the fact that the selection of the two sets, $`X`$ and $`Y`$, may not necessarily be unique but may alter for each column.

###### Theorem 1

Let $`F(x_0,\mathrm{},x_{N1})`$ be a function of $`N`$ $`\{0,1\}`$valued variables and $`X_i,Y_i`$, for $`i\{0,\mathrm{},N1\}`$, be sets of inputs such that $`F(x)F(y)`$ if $`xX_i`$ and $`yY_i`$, and $`X_0Y_0=\mathrm{}=X_{N1}Y_{N1}`$. Let $`R_iX_i\times Y_i`$ be such that
1. For every $`xX_i`$, there exist at least $`m`$ different $`yY_i`$ such that $`(x,y)R_i`$.
2. For every $`yY_i`$, there exist at least $`m^{}`$ different $`xX_i`$ such that $`(x,y)R_i`$.
3. For every $`x`$ and $`j\{0,\mathrm{},N1\}`$, there are at most $`l`$ different $`yY_i`$ such that $`(x,y)R_0\mathrm{}R_{N1}`$ and $`x_jy_j`$.
4. For every $`y`$ and $`j\{0,\mathrm{},N1\}`$, there are at most $`l^{}`$ different $`xX_i`$ such that $`(x,y)R_0\mathrm{}R_{N1}`$ and $`x_jy_j`$.
Then, any quantum algorithm computing $`F`$ uses $`\mathrm{\Omega }(\sqrt{\frac{mm^{}}{ll^{}}})`$ queries.

* Omitted since it is enough to make word-to-word replaces in the original proof of .

Now our lower-bound result is almost immediate. Recall that our oracle is defined by $`f(a,x):\{0,1\}^n\times \{0,1\}^n\{0,1\}`$. If we use the notation $`F`$, its range is $`\{0,1\}^n`$ and for any $`x,y\{0,1\}^N`$ such that $`xy`$, it is guaranteed that $`F(x)F(y)`$ if they are defined.

###### Corollary 1

Let $`f`$ be an oracle such that $`\mathrm{\#}(T_f)=K`$. Then any quantum algorithm that computes a target $`a`$ with probability $`1\epsilon `$ needs $`\mathrm{\Omega }(\sqrt{N/K})`$ oracle calls for some fixed $`\epsilon <1/2`$.

* Recall that $`KN/2`$. So we can select $`X_i`$ and $`Y_i`$ of Theorem 1 such that $`|X_i|=|Y_i|=N/2`$ and if $`x_i=1`$ then $`xX_i`$ (i.e., all $`Y_i`$ do not include $`y`$ such that $`y_i=1`$). Now it is not hard to see that we can set $`m=m^{}=l=N/2`$ and $`l^{}=K`$. Hence, Theorem 1 implies that the query complexity is $`\mathrm{\Omega }(\sqrt{\frac{mm^{}}{ll^{}}})=\mathrm{\Omega }(\sqrt{\frac{(N/2)^2}{NK/2}})=\mathrm{\Omega }(\sqrt{\frac{N}{K}})`$.

Note that Proposition 1 is, if we use it as it is, not so powerful; we cannot prove the lower bound of the Grover search for instance. In , Ambainis made a different kind of extension against Proposition 1 to prove several lower bounds including Grover’s. This extension is quite powerful but does not seem appropriate for our purpose. Our extension is also powerful, which will be used later to prove other lower bounds.

## 3 Quantum Upper Bounds

In this section, we show that there exists a specific oracle whose query complexity is $`O(\sqrt{N/K})`$. The oracle intuitively works partly as the EQ-oracle and partly as the IP-oracle and therefore we call it a hybrid oracle. The hybrid oracle with a parameter $`1kn`$, denoted by $`h_k(a,x)`$, is defined as follows ($`k`$ indicates the size of its IP-part): Let $`a=(a_1,a_2,\mathrm{},a_{nk},a_{nk+1},\mathrm{},a_n)`$ and $`x=(x_1,x_2,\mathrm{},x_{nk},x_{nk+1},\mathrm{},x_n).`$ Then $`h_k(a,x)=1`$ iff (i) $`(a_1,\mathrm{},a_{nk})=(x_1,\mathrm{},x_{nk})`$ and (ii) $`(a_{nk+1},\mathrm{},a_n)(x_{nk+1},\mathrm{},x_n)=0`$ (mod $`2`$). Fig. 3 shows $`h_2`$ for $`n=4`$. One can see that the small $`4\times 4`$ matrix is the negation of the IP-oracle.

###### Theorem 2

There exists a quantum algorithm to find a target $`a`$ using $`O(\sqrt{2^{nk}})`$ calls of $`h_k`$.

* We combine Grover search with BV algorithm to find a target $`a`$ using the hybrid oracle $`h_k`$. At first, we can determine the first $`nk`$ bits of $`a`$. Fixing the last $`k`$ bits to $`|0`$, we apply Grover search using oracle $`h_k`$ for the first $`nk`$ bits to determine $`a_1,\mathrm{},a_{nk}`$. It should be noted that $`h_k(a,(a_1,\mathrm{},a_{nk},0,\mathrm{},0))=1`$ and $`h_k(a,(x_1,\mathrm{},x_{nk},0,\mathrm{},0))=0`$ for any $`x_1,\mathrm{},x_ka_1,\mathrm{},a_k`$. Next, we apply BV algorithm to determine the remaining $`k`$ bits. This algorithm requires $`O(\sqrt{N/K})`$ queries for Grover search and $`O(1)`$ queries for BV algorithm.

###### Corollary 2

There exists an oracle $`f`$ such that $`\mathrm{\#}(T_f)=K`$ and its query complexity is $`O(\sqrt{N/K})`$.

Thus Corollary 1 is tight in the sense that we cannot improve it in general. Note that both Corollaries 1 and 2 hold for the EQ- and IP-oracles. We can also prove the same upper bound, $`O(\sqrt{N/K})`$, for a more general class of oracles if we restrict the value of $`K`$. An oracle $`f`$ is said to be balanced if all columns and all rows have the same number of 1’s.

###### Theorem 3

For a balanced oracle $`f(a,x)`$ with $`KN^{1/3}`$, there exists a quantum algorithm to find a target $`a`$ using $`O(\sqrt{N/K})`$ queries of $`f`$.

* Since $`f(a,x)`$ is balanced, each row and each column of $`T_f`$ has exactly $`K`$ 1’s. Our algorithm consists of two parts; the first part is quantum and the second part classical: The first part of the algorithm is to reduce the size of the search space from $`N`$ to $`K`$ which is achieved by using (multi-solution) Grover search. It first finds an $`x`$ such that $`f(a,x)=1`$. Since each row of $`T_f`$ has $`K`$ 1’s, the query complexity of this first part is $`O(\sqrt{N/K})`$. Also since each column has $`K`$ 1’s, the number of $`a`$ satisfying $`f(a,x)=1`$ for a particular $`x`$ is exactly $`K`$. Now, let a subset $`R=\{a|f(a,x)=1\}`$, which includes the candidates of $`a`$.

The second part of the algorithm is to repeatedly choose an index $`y`$ such that $`a,bR`$ where $`f(a,y)f(b,y)`$. Clearly, unless $`|R|=1`$, there must exist such $`y`$, which can reduce the number of the candidates at least by one. More formally, let the query’s result for such $`y`$ is $`m\{0,1\}`$. Then, we can substitute $`R\{b|f(b,y)=m\}`$ for $`R`$, by which $`|R|`$ decreases at least by one. The total query complexity is thus $`O(\sqrt{N/K})+K`$, which is $`O(\sqrt{N/K})`$ for $`KN^{1/3}`$.

## 4 Relation to Grover Upper and Lower Bounds

As described in Section 1, our problem is closely related to MS-Grover. However, there exist some gaps between those two problems. In this section, we show some explicit oracles such that the query complexities of those two problems are quite different. The following theorem shows the oracle such that our problem is harder than MS-Grover.

###### Theorem 4

There is an oracle $`f`$ such that the query complexity of our search problem is $`\mathrm{\Omega }(\sqrt{N})`$ and that of MS-Grover is $`O(1)`$.

* Consider an oracle $`f`$ whose truth-table is such that the upper left and the lower right of the table is exactly the same as the EQ-oracle, and all the elements of the upper right and the lower left of the table are 1’s. (See Fig. 4 for $`N=16`$.) Then it is obvious that we need only $`O(1)`$ queries to find $`x`$ such that $`f(a,x)=1`$ since the number of such $`x`$ is so large that even choosing $`x`$ randomly suffices. On the other hand, we can show the hardness of finding $`a`$ for this oracle by Theorem 1. We select $`X_i`$ and $`Y_i`$ of Theorem 1 such that $`X_iY_i`$ is equal to the upper half of the truth-table, $`|X_i|=|Y_i|=N/4`$ and if $`x_i=1`$ then $`xX_i`$ for $`iN/2`$. Then, one can easily see that $`m=m^{}=l=N/4`$ and $`l^{}=1`$. Therefore, we need $`\mathrm{\Omega }(\sqrt{N})`$ queries to find $`a`$.

Thus our problem is much harder than MS-Grover in this particular oracle. It is also true, as shown in the previous section, that our problem has approximately the same query complexity as MS-Grover for balanced oracles with $`KN^{1/3}`$. Then, is there any oracle for which MS-Grover is harder than our problem? We have no formal answer to this question, but the following example suggests that the answer is probably yes: Let $`IP_a^{}`$ be an oracle which is exactly the same as $`IP_a`$ except that $`f(0,z)=1`$ for some single $`z`$ (recall that $`f(0,z)=0`$ in $`IP_a`$). Then, if we simply use the Grover search, it needs $`\sqrt{N}`$ queries when $`a=0`$. (Recall that we assumed that MS-Grover does not have any information on the oracle table $`T_f`$ so that this seems to be the best we can do.) In contrast, if we use the BV algorithm, then we can get the value of $`a`$ with high probability since $`IP_a^{}`$ is so close to $`IP_a`$. (It is easy to compute the success probability, which may be omitted.)

## 5 Classical Lower and Upper Bounds

We first give the classical lower bound and then prove the matching upper bound using the same oracle given in the previous section.

###### Theorem 5

Suppose that $`f`$ is an arbitrary oracle such that $`\mathrm{\#}(T_f)`$ is $`K`$. Then any classical algorithm needs at least $`\frac{N}{K}+\mathrm{log}K2`$ oracle calls to obtain a target in the worst case.

* The following proof is due to the standard adversary argument. Let $`A`$ be any classical algorithm using the oracle $`f`$. Suppose that the target is $`a\{0,1\}^n`$. Then the execution of $`A`$ is described as follows: (i) In the first round, $`A`$ calls the oracle with the predetermined value $`x_0`$ and the oracle answers with $`d_0=f(a,x_0)`$. (ii) In the second round, $`A`$ calls the oracle with value $`x_1`$, which is determined by $`d_0`$ and the oracle answers with $`d_1=f(a,x_1)`$. (iii) In the $`(i+1)`$-st round, $`A`$ calls the oracle with $`x_i`$ which is determined by $`d_0,d_1,\mathrm{},d_{i1}`$ and the oracle answers with $`d_i=f(a,x_i)`$. (iv) In the $`m`$-th round $`A`$ outputs the target $`a`$ which is determined by $`d_0,d_1,\mathrm{},d_{m1}`$ and stops. Thus, the execution of $`A`$ is completely determined by the sequence $`(d_0,d_1,\mathrm{},d_{m1})`$ which is denoted by $`A(a)`$. (Obviously, if we fix a specific target $`a`$, then $`A(a)`$ is uniquely determined).

Let $`m_0=N/K+\mathrm{log}K3`$ and suppose that $`A`$ halts in the $`m_0`$-th round. We compute the sequence $`(c_0,c_1,\mathrm{},c_{m_0}),c_i\{0,1\}`$, and another sequence $`(L_0,L_1,\mathrm{},L_{m_0}),L_i\{a|a\{0,1\}^n\}`$, as follows (note that $`c_0,\mathrm{},c_{m_0}`$ are similar to $`d_0,\mathrm{},d_{m1}`$ above and are chosen by the adversary): (i) $`L_0=\{0,1\}^n`$. (ii) Suppose that we have already computed $`L_0,\mathrm{},L_i`$, and $`c_0,\mathrm{},c_{i1}`$. Let $`x_i`$ be the value with which $`A`$ calls the oracle in the $`(i+1)`$-st round. (Recall that $`x_i`$ is determined by $`c_0,\mathrm{},c_{i1}`$.) Let $`L^0=\{s|f(s,x_i)=0\}`$ and $`L^1=\{s|f(s,x_i)=1\}`$. Then if $`|L_iL^0||L_iL^1|`$ then we set $`c_i=0`$ and $`L_{i+1}=L_iL^0`$. Otherwise, i.e., if $`|L_iL^0|<|L_iL^1|`$, then we set $`c_i=1`$ and $`L_{i+1}=L_iL^1`$.

Now we can make the following two claims.

Claim 1. $`|L_{m_0}|2`$. (Reason: Note that $`|L_0|=N`$ and the size of $`L_i`$ decreases as $`i`$ increases. By the construction of $`L_i`$, one can see that until $`|L_i|`$ becomes $`2K`$, its size decreases additively by at most $`K`$ in a single round and after that it decreases multiplically at most one half. The claim then follows by a simple calculation.)

Claim 2. If $`aL_{m_0}`$, then $`(c_0,\mathrm{},c_{m_0})=A(a)`$. (Reason: Obvious since $`aL_0L_1\mathrm{}L_{m_0}`$.)

Now it follows that there are two different $`a_1`$ and $`a_2`$ in $`L_{m_0}`$ such that $`A(a_1)=A(a_2)`$ by Claims 1 and 2. Therefore $`A`$ outputs the same answer for two different targets $`a_1`$ and $`a_2`$, a contradiction.

Next, we consider classical upper bounds for the hybrid oracle discussed in Section 3. Recall that $`K=2^k`$.

###### Theorem 6

There exists a classical algorithm to find a target $`a`$ using $`O(\frac{N}{K}+\mathrm{log}K)`$ calls of $`h_k`$.

* The algorithm consists of an exhaustive and a binary search. First, we determine the first $`nk`$ bits by fixing the last $`k`$ bits to all $`0`$’s and using exhaustive search. Second, we determine the last $`k`$ bits by using binary search. This algorithm needs $`2^{nk}(=\frac{N}{K})`$ queries in the exhaustive search, and $`O(k)(=O(\mathrm{log}K))`$ queries in the binary search. Therefore, the total complexity of this algorithm is $`O(2^{nk}+k)(=O(\frac{N}{K}+\mathrm{log}K))`$.

## 6 Concluding Remarks

We have assumed through this paper that the size of $`T_f`$ is $`N\times N`$, i.e., the size of the domain and the size of the range of the Boolean function $`F`$ are the same. This restriction can of course be removed. For example, consider the $`\left(\begin{array}{c}N\\ K\end{array}\right)\times N`$ table $`T_f`$ which includes every string $`y`$ consisting of $`K1`$’s and $`(NK)0`$’s in its rows. One can see this is exactly the same as the $`K`$-solution Grover search if our answer is to obtain an $`x`$ such that $`f(a,x)=1`$ and its complexity is $`\mathrm{\Theta }(\sqrt{\frac{N}{K}})`$. Recall again that our present problem is different, i.e., we need to obtain $`a`$. We can also use Theorem 1, which implies (details are omitted) a lower bound of $`\mathrm{\Omega }(\sqrt{\frac{N}{K}})`$. This lower bound is the same as the lower bound of MS-Grover and seems too weak as a lower bound of obtaining $`a`$. Fortunately it is not hard to improve this lower bound up to $`\mathrm{\Omega }(\sqrt{N})`$ if $`K=cN`$: By selecting $`K`$ rows appropriately, we can obtain a smaller table which is similar to the table given in Fig. 4. Nevertheless, this $`\sqrt{N}`$ lower bound still seems weak; the real bound is probably much larger than $`\sqrt{N}`$. To obtain such a “huge” lower bound for natural oracles ( has obtained one for an artificial oracle) should be interesting future work.

Another future direction is to find a different parameter which can control upper bounds of the query complexity of evaluating functions. Note that the Hamming distance between two rows of $`T_f`$ is $`O(1)`$ for the EQ-oracle and $`N/2`$ for the IP-oracle. This fact might be a good hint for this direction.


text:
# A possible deformed algebra and calculus inspired in nonextensive thermostatistics

## 1 Introduction

The definition of the so-called nonextensive entropy, $`S_qk(_i^Wp_i^q1)/(1q)`$ ($`q`$ is the nonextensive entropic index, $`k`$ is a positive constant which defines the unity in which $`S_q`$ is measured), and its applications to nonextensive thermostatistics (NEXT)  have opened new possibilities for the thermodynamical treatment of complex systems , with a continuously increasing number of works (for an updated bibliography, see Ref. ). Nonextensive statistical mechanics has been treated basically along three (complementary) lines: formal mathematical developments  (in which this paper is included), observation of consistent concordance with experimental (or natural) behavior , and theoretical physical developments  (see Ref.  for some epistemological remarks on NEXT).

The basis of the formal developments inspired in NEXT is the definition of deformed expressions for the beautiful and ubiquitous logarithm and exponential functions, namely, the $`q`$-logarithm and the $`q`$-exponential, first proposed within this context in 1994 :

$`\mathrm{ln}_qx{\displaystyle \frac{x^{1q}1}{1q}}(x>0),e_q(x)[1+(1q)x]_+^{\frac{1}{1q}}(x,q),`$ (1)
where $`[A]_+\text{max}\{A,0\}`$. Note that $`e_q(x)=+\mathrm{}`$ if $`q>1`$ and $`1+(1q)x0`$. Of course there are infinitely many ways of generalizing a function, and many have already been proposed, for instance (see Ref. ), $`\mathrm{exp}_qx_{n=0}^{\mathrm{}}x^n/[n]_q!`$, with $`[n]_q!=_{j=1}^n[j]_q`$ and $`[j]_q=(q^j1)/(q1)`$ and also $`[0]_q!=1`$, but we focus here specifically on those ones that naturally emerge from NEXT (Eq. (1)). Some works have appeared developing properties of such $`q`$-deformed functions, e.g., Ref. , and have also stimulated the definition of other (alternative) deformations, as in Ref. .

It is remarkable that in less than one decade (since Ref. ) these functions ($`\mathrm{ln}_qx`$ and $`e_q(x)`$) have become so popular among the practitioners of NEXT that in many papers they are referred to as if they were known since long, which is a very positive symptomatic behavior. And they are known since long, indeed: the $`q`$-exponential is a particular solution of Bernoulli’s equation, known by Leibniz (according to Refs. ). (The independent re-discovering of laws, natural phenomena etc. is much more frequent in science than one outsider would be inclined to think.)

This paper presents some formal, and curious, properties of $`q`$-exponentials and $`q`$-logarithms, hopefully inspiring for further developments. In some sense, we follow the work of Kaniadakis, who has explored his own $`\kappa `$-deformation of the exponential and logarithm functions .

## 2 $`q`$-Algebra111We point out that parts of the contents of this section have appeared independently and almost simultaneously in the early versions of Ref.  and also in the early version of the present work, as explained in the Acknowledgments.

We focus on the (now well known) following relations:

$`\mathrm{ln}_q(xy)=\mathrm{ln}_qx+\mathrm{ln}_qy+(1q)\mathrm{ln}_qx\mathrm{ln}_qy`$ (2)
(which justifies the terminology “nonextensive”) and

$`e_q(x)e_q(y)=e_q(x+y+(1q)xy),`$ (3)
which holds if $`e_q(x)`$ and $`e_q(y)`$ differ from zero and from $`+\mathrm{}`$. These properties inspire us to define a generalization of the sum operation between two numbers $`x`$ and $`y`$:

$`x_qyx+y+(1q)xy,`$ (4)
which brings the usual sum as a particular case $`_1+`$. The $`q`$-sum is commutative ($`x_qy=y_qx`$), associative ($`x_q(y_qz)=(x_qy)_qz`$), but it is not distributive in relation to the usual multiplication ($`a(x_qy)(ax_qay)`$). The neutral element of the $`q`$-sum is zero, $`x_q0=x`$. We can define the opposite (or inverse additive) of $`x`$ (calling it $`_qx`$) as the element that, when $`q`$-summed with $`x`$, yields the neutral element: $`x_q(_qx)=0`$. So, we have

$`_qx{\displaystyle \frac{x}{1+(1q)x}}(x1/(q1)).`$ (5)
This definition permits us to define the $`q`$-difference, as the $`q`$-sum with the $`q`$-opposite

$`x_qyx_q(_qy)={\displaystyle \frac{xy}{1+(1q)y}}(y1/(q1)).`$ (6)
The $`q`$-difference obeys $`x_qy=_qy_qx`$ and $`x_q(y_qz)=(x_qy)_qz`$, but $`a(x_qy)(ax_qay)`$.

We now search for a generalization of the multiplication operation in such a way that we can compactly rewrite Eqs. (2) and (3) as $`\mathrm{ln}_q(x_qy)=\mathrm{ln}_qx+\mathrm{ln}_qy`$ and $`e_q(x)_qe_q(y)=e_q(x+y).`$ This leads us to the definition of the $`q`$-product between two numbers

$`x_qy\left[x^{1q}+y^{1q}1\right]_+^{\frac{1}{1q}}(x,y>0).`$ (7)
The $`q`$-product is commutative ($`x_qy=y_qx`$) and associative ($`x_q(y_qz)=(x_qy)_qz`$), provided $`x_qy`$ and $`y_qz`$ differ from zero and from infinity. It is easy to see that the number one is the neutral element of the $`q`$-product ($`x_q1=x`$), and this permits us to define the inverse multiplicative, $`1_qx`$, by means of $`x_q(1_qx)1`$. We find

$`1_qx\left[2x^{1q}\right]_+^{\frac{1}{1q}}(x0).`$ (8)
The relation $`1_q(1_qx)=1`$ holds only if $`0x^{1q}2`$. It is curious to note that $`1_q0`$ does not diverge for $`q<1`$. The $`q`$-ratio is thus defined by

$`x_qy\left[x^{1q}y^{1q}+1\right]_+^{\frac{1}{1q}}(x,y>0),`$ (9)
and satisfies $`x_qy=1_q(y_qx)`$, provided $`x^{1q}1+y^{1q}`$, and also $`x_q(y_qz)=(x_qy)_qz=(x_qz)_qy`$, provided $`z^{1q}1y^{1q}x^{1q}+1`$. These $`q`$-algebraic relations permit us to express the properties of the $`q`$-logarithm and the $`q`$-exponential in a more compact form:

$`\mathrm{ln}_q(xy)=\mathrm{ln}_qx_q\mathrm{ln}_qy`$ $`e_q(x)e_q(y)=e_q(x_qy)`$ (10)
$`\mathrm{ln}_q(x_qy)=\mathrm{ln}_qx+\mathrm{ln}_qy`$ $`e_q(x)_qe_q(y)=e_q(x+y)`$ (11)
$`\mathrm{ln}_q(x/y)=\mathrm{ln}_qx_q\mathrm{ln}_qy`$ $`e_q(x)/e_q(y)=e_q(x_qy)`$ (12)
$`\mathrm{ln}_q(x_qy)=\mathrm{ln}_qx\mathrm{ln}_qy`$ $`e_q(x)_qe_q(y)=e_q(xy)`$ (13)
The equalities hold only under certain restrictions, as indicated in the following table

$`\begin{array}{cc}& \\ x>0,y>0\hfill & x_q0\text{ or }y_q0\hfill \\ x^{1q}+y^{1q}1\hfill & x_q0\text{ and }y_q0\hfill \\ x>0,y>0\hfill & y>_q0\hfill \\ x^{1q}+1y^{1q}\hfill & x_q0\text{ or }y_q0\hfill \end{array}`$ (18)
Here, the notation $`x_q0`$ means $`1+(1q)x0`$. Among these relations, we call attention to Eq. (11), that shows how to $`q`$-factorize the kinetic and potential parts of the Hamiltonian of a system (and further $`q`$-factorize each one of them individually). It is straightforward to define a $`q`$-power,

$`x^{_q^n}\underset{\text{n times}}{\underset{}{x_qx_qx_q\mathrm{}_qx}}=\left[nx^{1q}(n1)\right]_+^{\frac{1}{1q}},`$ (19)
with $`x^{_1^n}x^n`$. It follows also straightforwardly the $`q`$-sum of $`n`$ identical terms (see Eq. (7) of Ref. ):

$`\underset{\text{n terms}}{\underset{}{x_qx_qx_q\mathrm{}_qx}}={\displaystyle \frac{1}{1q}}\left\{\left[1+(1q)x\right]^n1\right\}.`$ (20)
We call attention that this Equation may be the basis for the definition of a different, non-commutative, $`q`$-product (that we could note $`_q`$): $`n_qxx_qn`$, with $`1_qx=x`$ and $`n_1x=nx`$. There is another possibility of generalizing the $`q`$-algebra, along nonextensive lines, recovering the distributivity, as done in Ref. , following Ref. . We don’t explore these possibilities in the present work.

## 3 $`q`$-Calculus

We now focus on a possible $`q`$-calculus associated with NEXT. Abe  has shown that the Jackson’s $`q`$-derivative, $`𝒟_qf(x)[f(qx)f(x)]/[(q1)x]`$, (that is related to dilations) is intimately connected to nonextensive entropy, as the usual (Newtonian) derivative (that is related to translations) is connected to Boltzmann-Gibbs entropy. But this Jackson’s operator is not the proper one we are searching here. The usual exponential function is invariant in relation to derivation, $`dy/dx=y`$, or, in other words, $`e^x`$ is eigenfunction of the derivative operator. The $`q`$-exponential satisfies $`dy/dx=y^q`$. So we can ask: what is the operator for which the $`q`$-exponential is an eigenfunction? The answer to this question may be found by following the steps of Kaniadakis . Let us define the $`q`$-derivative as

$`D_{(q)}f(x)\underset{yx}{lim}{\displaystyle \frac{f(x)f(y)}{x_qy}}=[1+(1q)x]{\displaystyle \frac{df(x)}{dx}}.`$ (21)
It is promptly verified that the $`q`$-exponential is eigenfunction of $`D_{(q)}`$. We have the corresponding $`q`$-integral (noted as $`_{(q)}`$) given by

$`{\displaystyle _{(q)}}f(x)d_qx={\displaystyle \frac{f(x)}{1+(1q)x}𝑑x},`$ (22)
where

$`d_qx\underset{yx}{lim}x_qy={\displaystyle \frac{1}{1+(1q)x}}dx.`$ (23)
Naturally $`_{(q)}D_{(q)}f(x)d_qx=D_{(q)}_{(q)}f(x)d_qx=f(x).`$ Eqs. (21)–(23) are restricted to $`1+(1q)x0`$. There is a dual derivative operator $`D^{(q)}`$, associated with $`D_{(q)}`$, defined by

$`D^{(q)}f(x)\underset{yx}{lim}{\displaystyle \frac{f(x)_qf(y)}{xy}}={\displaystyle \frac{1}{1+(1q)f(x)}}{\displaystyle \frac{df(x)}{dx}},`$ (24)
and its corresponding dual $`q`$-integral

$`{\displaystyle ^{(q)}}f(x)𝑑x{\displaystyle [1+(1q)f(x)]f(x)𝑑x}.`$ (25)
Also here $`^{(q)}D^{(q)}f(x)𝑑x=D^{(q)}^{(q)}f(x)𝑑x=f(x)`$. Similarly to the restrictions of $`D_{(q)}`$ and $`_{(q)}`$, Eqs. (24) and (25) are valid if $`1+(1q)f(x)0`$. We have $`D^{(q)}\mathrm{ln}_qx=1/x`$, while $`D^{(1)}\mathrm{ln}_qx=\frac{d}{dx}\mathrm{ln}_qx=1/x^q`$. The usual derivative and the usual integral are obviously auto-dual. The dual $`q`$-derivatives are related by

$`D^{(q)}f(x)={\displaystyle \frac{1}{[1+(1q)x][1+(1q)f(x)]}}D_{(q)}f(x).`$ (26)
The $`q`$-derivatives follow the chain rule in the forms:

$`D_{(q)}[f(x)g(x)]=D_{(q)}[f(x)]g(x)+f(x)D_{(q)}[g(x)]`$ (27)
and

$`\begin{array}{ccc}D^{(q)}[f(x)g(x)]\hfill & =\hfill & {\displaystyle \frac{1}{[1+(1q)f(x)g(x)]}}\hfill \\ & & \times \{[1+(1q)f(x)]D^{(q)}[f(x)]g(x)\hfill \\ & & +[1+(1q)g(x)]f(x)D^{(q)}[g(x)]\}.\hfill \end{array}`$ (31)
## 4 Concluding Remarks

The relations presented are compact and relatively simple, though there are many exceptions that have to be taken into account originated from the cutoff that appears in the $`q`$-deformed exponential function (see, for instance, restrictions (18)), and it is of course important that we are aware of them. Despite these limitations, it is remarkable that many phenomena seem to be fairly fitted by $`q`$-exponentials, or functions that belong to its family. Examples range over physical, biological, economical and social systems (all of them may be classified into the category of complex systems). Besides the observation of fair description of phenomena, there are increasingly many works on theoretical developments of nonextensive ideas. Just to cite an important and very recent example, let us mention the exact analytical results by Baldovin and Robledo  about the $`q`$-Pesin identity for the dynamics at the edge of chaos of the logistic map. For the interested reader, we give the address of the web page . Of course all these elements (mathematical framework, experimental evidence, theoretical developments) are not yet enough to be conclusive, and many efforts have been made in order to clarify the domain of validity of Boltzmann-Gibbs statistical mechanics, of nonextensive statistical mechanics, or even others that might happen in nature.

## Acknowledgments

We gratefully acknowledge Giorgio Kaniadakis for calling us attention to the existence of the duality in the $`q`$-derivatives. We also thank Q. Alexandre Wang (together with his coauthors) for sending to us their paper Ref. , while it was in its e-print form \[http://arXiv.org/math-ph/0303061\], soon after he took notice of the early e-print version of the present work \[http://arXiv.org/ cond-mat/0304545\]. These works present many similarities, specially regarding the $`q`$-algebra (Section 2). I am deeply indebted to Jan Naudts, who introduced many valuable improvements on this work. Last but not least, the unforgettable hospitality of the organizers of NEXT 2003 is warmly acknowledged.