text:
# Equilibrium orbit analysis in a free-electron laser with a coaxial wiggler

## I. INTRODUCTION

Most free-electron lasers employ a wiggler with either a helically symmetric magnetic field generated by bifilar current windings or a linearly symmetric magnetic field generated by alternating stacks of permanent magnets. A uniform static guide magnetic field is also frequently employed. Single-particle orbits in these helical and planar fields combined with an axial guide field have been analyzed in detail and have played a role in the development of free-electron lasers. Harmonics of gyroresonance for off-axis electrons caused by the radial variation of the magnetic field of a helical wiggler is found by Chu and Lin . Recently the feasibility of using a coaxial wiggler in a free-electron laser has been investigated. Freund et al. studied the performance of a coaxial hybrid iron wiggler consisting of a central rod and a coaxial ring of alternating ferrite and dielectric spacers inserted in a uniform static axial magnetic field. McDermott et al. proposed the use of a wiggler consisting of a coaxial periodic permanent magnet and transmission line. Coaxial devices offer the possibility of generating higher power than conventional free-electron lasers and with a reduction in the beam energy required to generate radiation of a given wavelength.

In the present paper, single-particle orbits in a coaxial wiggler are studied. The wiggler magnetic field is radially dependent with the fundamental plus the third spatial harmonic component and a uniform static axial magnetic field present. In Sec. II the scalar equations of motion are introduced and reduced to a form which is correct to first order in the wiggler field. In Sec. III solutions of the equations of motion are developed in a form suitable for computing the electron orbital velocity and trajectory in the radially dependent magnetic field of a coaxial wiggler. The special case of a radially independent wiggler is also analyzed. In Sec. IV the results of numerical computations of the wiggler field components, velocity components, radial excursions, and the $`\mathrm{\Phi }`$ function for locating negative mass regimes are presented and discussed. In Sec. V some conclusions are presented.

## II. EQUATIONS OF MOTION

Electron motions in a static magnetic field $`𝐁`$ may be determined by solution of the vector equation of motion

$$\frac{d𝐯}{dt}=\frac{e}{\gamma mc}𝐯\times 𝐁$$
(1)
where $`𝐯`$, $`e`$, and $`m`$ are the velocity, charge, and (rest) mass, respectively, of the electron. Lorentz factor $`\gamma `$ is a constant given by

$$\gamma =(1v^2/c^2)^{1/2}$$
(2)
where $`v=|𝐯|`$ is the constant electron speed.

The total magnetic field inside a coaxial wiggler will be taken to be of the form

$`𝐁=B_r\widehat{𝐫}+B_z\widehat{𝐳},`$ (3)
$`B_r=B_wF_r(r,z),`$ (4)
$`B_z=B_0+B_wF_z(r,z),`$ (5)
where $`B_0`$ is a uniform static axial guide field, and $`F_r`$ and $`F_z`$ are known functions of cylindrical coordinates $`r`$ and $`z`$. Equation (1) may be written in the scalar form

$`{\displaystyle \frac{dv_r}{dt}}{\displaystyle \frac{v_\theta ^2}{r}}=v_\theta (\mathrm{\Omega }_0+\mathrm{\Omega }_wF_z),`$ (6)
$`{\displaystyle \frac{dv_\theta }{dt}}+{\displaystyle \frac{v_\theta v_r}{r}}=v_r(\mathrm{\Omega }_0+\mathrm{\Omega }_wF_z)v_z\mathrm{\Omega }_wF_r,`$ (7)
$`{\displaystyle \frac{dv_z}{dt}}=v_\theta \mathrm{\Omega }_wF_r;`$ (8)
$`\mathrm{\Omega }_0`$ and $`\mathrm{\Omega }_w`$ are relativistic cyclotron frequencies given by

$`\mathrm{\Omega }_0={\displaystyle \frac{eB_0}{\gamma mc}},`$ (9)
$`\mathrm{\Omega }_w={\displaystyle \frac{eB_w}{\gamma mc}}.`$ (10)
Initial conditions will be chosen such that the transverse motion of the electron in the $`B_0`$ field vanishes in the limit as $`B_w`$ approaches zero. Then, in order to develop a solution to first order in the wiggler field $`B_w`$, the scalar equations of motion will be approximated by

$`{\displaystyle \frac{dv_r}{dt}}=\mathrm{\Omega }_0v_\theta ,`$ (11)
$`{\displaystyle \frac{dv_\theta }{dt}}=\mathrm{\Omega }_0v_rv_{}\mathrm{\Omega }_wF_r,`$ (12)
$`{\displaystyle \frac{dv_z}{dt}}=0.`$ (13)
with the wiggler field approximated by the fundamental plus the third spatial harmonic component,

$$F_r=F_{r1}sin(k_wz)+F_{r3}sin(3k_wz),$$
(14)
where

$`F_{rn}G_n^1[S_nI_1(nk_wr)+T_nK_1(nk_wr)],`$ (15)
$`G_nI_0(nk_wR_{out})K_0(nk_wR_{in})I_0(nk_wR_{in})K_0(nk_wR_{out}),`$ (16)
$`S_n{\displaystyle \frac{2}{n\pi }}sin({\displaystyle \frac{n\pi }{2}})[K_0(nk_wR_{in})+K_0(nk_wR_{out})],`$ (17)
$`T_n{\displaystyle \frac{2}{n\pi }}sin({\displaystyle \frac{n\pi }{2}})[I_0(nk_wR_{in})+I_0(nk_wR_{out})],`$ (18)
and $`n=1,3`$; $`R_{in}`$ and $`R_{out}`$ are the inner and outer radii of the coaxial waveguide, $`k_w=2\pi /\lambda _w`$ where $`\lambda _w`$ is the wiggler (spatial) period, and $`I_0`$, $`I_1`$, $`K_0`$, and $`K_1`$ are modified Bessel functions.

## III. ORBITAL ANALYSIS

A. Radially dependent wiggler

The scalar equations of motion may be solved to determine the electron orbital velocity and trajectory in a coaxial wiggler. Equation (13) yields

$$v_z=v_{}$$
(19)
where the constant $`v_{}`$ is the root-mean-square axial velocity component. With the initial axial position taken to be $`z_0=0`$,

$$z=v_{}t.$$
(20)
Equations (11), (12), (14), and (20) may be combined to obtain

$$\frac{d^2v_r}{dt^2}+\mathrm{\Omega }_0^2v_r=f(t)$$
(21)
where

$$f(t)=\mathrm{\Omega }_0\mathrm{\Omega }_wv_{}[F_{r1}sin(k_wv_{}t)+F_{r3}sin(3k_wv_{}t)].$$
(22)
By the method of variation of parameters, a solution of Eq. (21) may be obtained in the form

$`v_r=[v_{\theta 0}+\mathrm{\Omega }_0^1{\displaystyle _0^t}f(\tau )cos(\mathrm{\Omega }_0\tau )𝑑\tau ]sin(\mathrm{\Omega }_0t)`$ (23)
$`+[v_{r0}\mathrm{\Omega }_0^1{\displaystyle _0^t}f(\tau )sin(\mathrm{\Omega }_0\tau )𝑑\tau ]cos(\mathrm{\Omega }_0t)`$ (24)
where $`v_{r0}`$ and $`v_{\theta 0}`$ are initial radial and azimuthal velocity components. Then Eq. (11) yields

$`v_\theta =[v_{\theta 0}\mathrm{\Omega }_0^1{\displaystyle _0^t}f(\tau )cos(\mathrm{\Omega }_0\tau )𝑑\tau ]cos(\mathrm{\Omega }_0t)`$ (25)
$`+[v_{r0}\mathrm{\Omega }_0^1{\displaystyle _0^t}f(\tau )sin(\mathrm{\Omega }_0\tau )𝑑\tau ]sin(\mathrm{\Omega }_0t).`$ (26)
The orbital velocity is given to first order in $`B_w`$ by Eqs. (23), (24), and (19). The trajectory may then be computed using

$`r=r_0+{\displaystyle _0^t}v_r(\tau )𝑑\tau ,`$ (27)
$`\theta =\theta _0+{\displaystyle _0^t}v_\theta (\tau )𝑑\tau ,`$ (28)
and Eq. (20).

B. Radially uniform wiggler

By neglecting the radial variation of $`F_{r1}`$ and $`F_{r3}`$, a solution of Eq. (21) may be obtained in the form

$$v_r=\alpha _1sin(k_wv_{}t)+\alpha _3sin(3k_wv_{}t),$$
(29)
where

$$\alpha _n=\frac{\mathrm{\Omega }_0\mathrm{\Omega }_wv_{}F_{rn}}{\mathrm{\Omega }_0^2n^2k_w^2v_{}^2}(n=1,3).$$
(30)
Equation (11) then yields

$$v_\theta =\mathrm{\Omega }_0^1k_wv_{}\alpha _1cos(k_wv_{}t)\mathrm{\Omega }_0^1(3k_wv_{}\alpha _3)cos(3k_wv_{}t).$$
(31)
The corresponding initial conditions are

$$v_{r0}=0,$$
(32)
$$v_{\theta 0}=\mathrm{\Omega }_0^1k_wv_{}\alpha _1\mathrm{\Omega }_0^1(3k_wv_{}\alpha _3).$$
(33)
Root-mean-square values of the velocity components may be determined by use of Eqs. (27), (28), and (19). Replacing $`v^2`$ by its root-mean-square value in Eq. (2) then yields

$$\frac{v_{}^2}{c^2}[1+\frac{1}{2}(\frac{\alpha _1}{v_{}})^2+\frac{1}{2}\mathrm{\Omega }_0^2k_w^2\alpha _1^2+\frac{1}{2}(\frac{\alpha _3}{v_{}})^2+\frac{9}{2}\mathrm{\Omega }_0^2k_w^2\alpha _3^2]=1\gamma ^2.$$
(34)
The derivative of $`v_{}`$ with respect to $`\gamma `$ may be obtained from Eq. (32) and, after some algebra, cast into the form

$$\frac{dv_{}}{d\gamma }=\frac{c^2}{\gamma \gamma _{}^2v_{}}\mathrm{\Phi }$$
(35)
where

$$\mathrm{\Phi }=1\frac{_{n=1,3}(\mathrm{\Omega }_0^2n^2k_w^2v_{}^2)^3\gamma _{}^2\mathrm{\Omega }_w^2F_{rn}^2\mathrm{\Omega }_0^2(\mathrm{\Omega }_0^2+3n^2k_w^2v_{}^2)}{2+_{n=1,3}(\mathrm{\Omega }_0^2n^2k_w^2v_{}^2)^3\mathrm{\Omega }_w^2F_{rn}^2\mathrm{\Omega }_0^2(\mathrm{\Omega }_0^2+3n^2k_w^2v_{}^2)}.$$
(36)
This equation may be used to establish the existence of a negative mass regime.

## IV. NUMERICAL RESULTS

A numerical computation is conducted to investigate the properties of the equilibrium orbits of electrons inside a coaxial wiggler. Wiggler wavelength $`2\pi /k_w`$ and lab-frame electron density $`n_0`$ were taken to be 3 cm and $`10^{12}`$ cm-3, respectively. The wiggler magnetic field $`B_w`$ was taken to be 3745 G which corresponds to the relativistic wiggler frequency $`\mathrm{\Omega }_w/ck_w=0.442`$. Electron-beam energy $`(\gamma 1)m_0c^2`$ was taken to be $`700`$ keV, corresponding to a Lorentz factor $`\gamma =2.37`$. The axial magnetic field $`B_0`$ was varied from 0 to 25.3 kG, corresponding to a variation from 0 to 3 in the normalized relativistic cyclotron frequency $`\mathrm{\Omega }_0/ck_w`$ associated with $`B_0`$. The inner and outer radii of the coaxial wiggler were assumed to be $`R_{in}=1.5`$ cm and $`R_{out}=3`$ cm, respectively.

Figure 1 shows the variation of the axial velocity of the quasi-steady-state orbits with the axial guide magnetic field for three classes of solutions. Group I orbits for which $`0<\mathrm{\Omega }_0<k_wv_{}`$, group II orbits with $`k_wv_{}<\mathrm{\Omega }_0<3k_wv_{}`$, and group III orbits with $`\mathrm{\Omega }_0>3k_wv_{}`$. Existence of group III orbits is due to the presence of the third spatial harmonic of the wiggler field, which also produces the second magnetoresonance at $`\mathrm{\Omega }_03k_wv_{}`$. The narrow width of the second resonance at $`\mathrm{\Omega }_0/ck_w2.7`$ compared to the width of the first magnetoresonance at $`\mathrm{\Omega }_0k_wv_{}`$ is illustrated in Fig. 1B. This is due to the relatively weak third harmonic compared to the fundamental component of the wiggler field. It should be noted that although the exact resonances $`\mathrm{\Omega }_0=k_wv_{}`$ and $`\mathrm{\Omega }_0=3k_wv_{}`$ occur at the origin where $`v_{}/c=\mathrm{\Omega }_0/ck_w=0`$, the first ”magnetoresonance” in the literature refers to the group II orbits with the cyclotron frequencies around $`\mathrm{\Omega }_0/ck_w1`$ in Fig. 1. Similarly we refer to the group III orbits with the cyclotron frequency around $`\mathrm{\Omega }_0/ck_w2.7`$ as the second magnetoresonance.

The rate of change of the electron axial velocity with electron energy is proportional to $`\Phi `$ and is equal to unity in the absence of the wiggler field. Figure 2 illustrates the dependence of $`\Phi `$ on the radial wiggler magnetic field and the axial guide magnetic field $`B_0`$. The curves corresponding to the group I and II orbits are almost unaffected by the third harmonic and are almost the same as in Ref.  where the third harmonic is neglected. A negative mass regime (i.e., negative $`\mathrm{\Phi }`$ for which a decrease in the axial velocity results in an increase in the electron energy) is found for group III orbits which is stronger than that of the group II orbits.

Equations (15)-(18) are used to calculate the radial components of the wiggler field $`F_{r1}`$ and $`F_{r3}`$. For the axial component the following expressions are used

$$F_z=F_{z1}cos(k_wz)+F_{z3}cos(3k_wz),$$
(37)
$$F_{zn}=G_n^1[S_nI_0(nk_wr)T_nK_0(nk_wr)].$$
(38)
Figure 3 shows the variation of the amplitudes of the wiggler magnetic field (divided by $`B_w=3745`$ G) with radius, for the first and third spatial harmonics. For the first harmonic the radial component, $`F_{r1}`$, has a minimum at $`r2.28`$ cm and the axial component, $`F_{z1}`$, changes sign around this point. Mc Dermott $`\mathrm{𝑒𝑡}`$ $`\mathrm{𝑎𝑙}.`$  have demonstrated the stability of a thin annular electron beam when $`F_{r1}`$ is minimum at the beam radius. The radial and axial components of the third harmonic of the wiggler $`F_{r3}`$ and $`F_{z3}`$ are also shown in Fig. 3. Magnitudes of $`F_{r3}`$ and $`F_{z3}`$ both are minimum at $`r2.28`$ cm where $`F_{r1}`$ is minimum. This is actually an inflection point for $`F_{z3}`$.

Variations of the radial components of the first and third spatial harmonics of the normalized wiggler magnetic field $`F_{r1}`$ and $`F_{r3}`$ with the wiggler wave number $`k_w`$ are shown in Fig. 4. Figure 4 also shows the dimensionless transverse velocity coefficients $`\overline{\alpha }_1=\alpha _1/c`$ and $`\overline{\alpha }_3=\alpha _3/c`$ for the initial orbit radius $`r_02.28`$ cm where $`F_{r1}`$ is minimum. The cyclotron frequency $`\mathrm{\Omega }_0/ck_w2.7`$ is taken at the second magnetoresonance, and our choice of 3 cm for the wiggler wavelength corresponds to $`k_w2.1`$ cm-1. It can be observed that at this wave number although the radial component of the wiggler field at the first harmonic $`F_{r1}`$ is much larger than the third harmonic $`F_{r3}`$, the transverse velocity coefficients of the third harmonic $`\overline{\alpha }_3`$ are larger than $`\overline{\alpha }_1`$. This shows that the third harmonic may have considerable effects around the second magnetoresonance at $`\mathrm{\Omega }_03k_wv_{}`$. Away from this resonance Eq. (28) shows that $`\alpha _3`$ will be of the order of $`F_{r3}`$.

In order to study the transverse motion of electrons in the radially dependent wiggler field Eqs. (11), (12), (25), and (26) are solved numerically with the initial conditions chosen so that, in the limit of zero wiggler field, there is axial motion at constant velocity $`v_{}`$ but no Larmor motion. Figure 5 shows the variation of the radial and azimuthal components of electron velocity with $`z(=v_{}t)`$. The normalized cyclotron frequency $`\mathrm{\Omega }_0/ck_w`$ is chosen to be 0.5, 1.2, and 3 for group I, II, and III orbits, respectively, which are somewhat away from the magnetoresonances. Solid curves correspond to the initial orbit radius $`r_0=2.28`$ cm, which is at the point where $`F_{r1}`$ is minimum. Broken curves correspond to $`r_0=1.8`$ cm, which is away from the $`F_{r1}`$ minimum. It can be observed that the spatial periodicity of $`v_r`$ and $`v_\theta `$ for the first two groups is equal to one wiggler wavelength, which is the same as that of the first harmonic. Although group III orbits have a clear sinusoidal shape at $`r_0=2.28`$ cm (solid curves), the slight deviations from sinusoidal shape are obvious at $`r_0=1.8`$ cm (broken curves). This is because that at $`r_0=2.28`$ cm where $`F_{r1}`$ is minimum $`F_{r3}`$ is very small. Therefore away from the resonance the third harmonic plays almost no role, at $`r_0=2.28`$ cm. Moving away from $`F_{r1}`$ minimum to $`r_0=1.8`$ cm, however, increases the magnitude of $`F_{r3}`$ slightly making the effect of the third harmonic noticeable on group III orbits, which are away from the second magnetoresonance, in Fig. 5.

Figure 6 shows the variations of $`v_r/c`$ and $`v_\theta /c`$ with $`z(=v_{}t)`$ for group III orbits when the cyclotron frequency is adjusted at the second magnetoresonance at $`\mathrm{\Omega }_0/ck_w2.7`$. At $`r_0=2.28`$ cm the periodicity is approximately equal to $`\lambda _w/3`$, which is the same as that of the third harmonic, and shows the strong influence of the third harmonic on the transverse velocity components. Going away from the $`F_{r1}`$ minimum to $`r_0=1.8`$ cm makes the amplitudes of oscillations of $`v_r`$ and $`v_\theta `$ larger. Broken curves correspond to the solutions of Eqs. (27) and (29) when the radial variation of the wiggler field is neglected. These solutions do not differ appreciably from the r-dependent solutions for $`r_0=2.28`$ cm because at $`F_{r1}`$ minimum the radial excursions are small for group III orbits. Away from the $`F_{r1}`$ minimum at $`r_0=1.8`$ cm, however, deviations are noticeable due to the larger radial excursions.

Figure 7 shows $`v_r/c`$ versus $`z`$ for group II orbits for r-dependent wiggler (broken curves) and r-independent wiggler (solid curves). The initial orbit radius is taken at $`r_0=2.28`$ cm and the cyclotron frequency is chosen around the first magnetoresonance at $`\mathrm{\Omega }_0/ck_w=0.9`$. Large radial excursions of electrons for group II orbits make the transverse velocity strongly affected by the radial dependency of the wiggler field. The amplitude is also modulated in space with the wavelength of around $`16\lambda _w=48`$ cm.

The radial excursion $`r`$ shown in Fig. 8 corresponds to the cyclotron frequencies away from the magnetoresonances at $`\mathrm{\Omega }_0/ck_w`$ equal to 0.5, 1.2, and 3 for the group I, II, and III orbits, respectively. Solid curves correspond to the $`r_0=2.28`$ cm and the broken curves correspond to $`r_0=1.8`$ cm. It can be noticed that when the electrons are injected into the wiggler at $`r_0=2.28`$ cm, where $`F_{r1}`$ is minimum, electron orbits remain well away from the waveguide walls at $`R_{in}=1.5`$ cm and $`R_{out}=3`$ cm.

Figure 9 compares the radial excursions of group III orbits at the second magnetoresonance at $`\mathrm{\Omega }_0/ck_w=2.7`$, (solid curve) with those slightly away from the resonance at $`\mathrm{\Omega }_0/ck_w=3`$, (broken curve). Influence of the third harmonic can be clearly seen through the modulation of the third harmonic by the first harmonic when the cyclotron frequency is adjusted at the second magnetoresonance.

## V. CONCLUSIONS

The third spatial harmonic of the coaxial wiggler field gives rise to the group III orbits with $`\mathrm{\Omega }_0>3k_wv_{}`$. This relatively weak third harmonic makes the width of the second magnetoresonance narrow compared to the first magnetoresonance. A strong negative mass regime is found for the group III orbits. By adjusting the cyclotron frequency at the second magnetoresonance the wiggler induced velocity of the group III orbits was found to increase considerably. When the electrons are injected into the wiggler where its magnetic field is minimum the electron orbits remain well away from the waveguide boundaries.

Harmonic gyroresonance of electrons in the combined helical wiggler and axial guide magnetic field is reported by Chu and Lin . In their analysis the relativistic single particle equation of motion is used with the axial velocity as well as the axial magnetic field of the wiggler averaged along the axial direction. By assuming near steady-state orbits for off-axis electrons they found that the radial variation of the wiggler magnetic field produces a harmonic structure in the transverse force. This force, in turn, comprises oscillations at all harmonics of $`k_wz`$. It should be noted that there is no harmonic structure in the helical wiggler itself and the higher velocity harmonics vanish for the exact steady-state orbits of the on-axis electrons. Moreover, higher harmonics do not appear in the one dimensional helical wiggler where the radial variation is neglected.

In the present analysis of coaxial wiggler, on the other hand, equation of motion is written to first order in the wiggler amplitude. With this approximation axial component of the wiggler field has no contribution to the problem leaving the axial velocity as a constant. Magnetic field of a coaxial wiggler is composed of a fundamental plus a large number of odd spatial harmonics, which directly appear in the magnetic force represented by $`f(t)`$ in Eq. (22). Third harmonic in $`f(t)`$ appears in the transverse velocity components as a part of the integrands in Eqs. (23) and (24) and is also demonstrated numerically for the radially dependent coaxial wiggler, but for the radially uniform wiggler the third harmonic is explicit in the solutions Eqs. (27)-(29).


format: text

text:
# Ballistic electron transport in stubbed quantum waveguides: experiment and theory

## I INTRODUCTION

Submicron-size T-shaped electron waveguides, defined electrostatically in a two-dimensional electron gas (2DEG) by Schottky gates, are very promising devices for potential applications in microelectronics since their conductance $`G`$ is determined, in the ballistic regime, by quantum interference effects and can be changed by applying voltages to the gates . Such devices, commonly known as Electron Stub Tuners (ESTs), also open the way for studying resonant states of ballistic quantum dots in both the weakly coupled tunneling and in the transmissive open regime . The size of an EST can be controlled by gate voltages, cf. Fig. 1. For a theoretical analysis, an EST can be considered as a rectangular quantum dot connected to 2DEG reservoirs through two oppositely placed Quantum Point Contacts (QPC). When the electron phase-coherence length exceeds the dimensions of the EST, transport through the device is ballistic. A number of theoretical papers ,  have been published on the ballistic transport characteristics of ESTs in the open regime of the QPCs. These works predict an oscillatory dependence of $`G`$ as a function of geometrical size parameters of the device or of the Fermi energy $`E_F`$. A minimum in $`G`$, or a reflection resonance, is said to occur due to resonant reflection of electron waves by quasibound states of the stub cavity (SC) formed by the gates, the quasibound state itself resulting because of the quantization of electron momentum associated with the small device size. Experimentally, it is possible to probe these resonance states through measurements of $`G`$ at low temperatures and has been reported  only very recently. However, so far experimenters have failed to observe well-defined, regular oscillations in $`G`$ with mimima corresponding to excitations of the quasibound states as predicted theoretically. Most of the devices so far used in experiments were geometrically defined by only two gates, which do not allow an adequate independent control of the width of the QPCs and the shape of the SC. This possibly explains the failure to observe experimentally a well-defined, regular pattern of minima in $`G`$.

In this paper we present experimental and theoretical results for the four-gate EST. A preliminary account of some of them has appeared recently . We report the experimental observation of a clear and pronounced oscillatory dependence of the ballistic $`G`$ on the size of the SC as the latter is changed by voltage-biasing the gates. Such oscillations occur on the first conductance plateau of the QPCs. We also present theoretical results for $`G`$ obtained from a numerical solution of Schröedinger’s equation for a two-dimensional (2D) hard-wall electron waveguide with a shape close to the one resulting from the biasing of the Schottky gates. Because of this choice, we believe our results are closer to reality than those reported in previous theoretical work based on a rectangular approximation for the SC shape. A rectangular SC shape is unrealistic since, though the lithographically defined device shape is rectangular, the shape of the SC changes as the gates are biased . Moreover, except for a few papers , the lengths of the QPCs have been considered as infinite; this is a very rough approximation for real devices and we avoid it in our computations. Comparison of the experimentally observed features of the ballistic $`G`$ to those obtained numerically enables us to determine the physical origin of these features and helps us understand what the shape of the SC is and how it can be modified by applied gate voltages.

The paper is organized as follows. In Sec. II we give a brief description of the device fabrication and measurement techniques and then present results of conductance measurements as function of gate voltages. Section III outlines the theoretical model and of the calculations presents numerical results. Finally, an interpretation of the experimental results based on the theoretical analysis of Sec. III. and conclusions follow in Sec. IV.

## II EXPERIMENTAL ASPECTS

### A Device fabrication and measurement techniques

The ESTs used in this study were fabricated from modulation doped AlGaAs/GaAs heterostructure wafers grown by MBE and having a two-dimensional electron gas (2DEG) at a depth of 80 nm below the surface. The carrier concentration $`n_{2D}`$ of the 2DEG was $`2.4\times 10^{15}`$ m-2 with a mobility $`\mu `$ of 100 m2/V s at 4.2 K. These values of $`n_{2D}`$ and $`\mu `$ give a 2DEG Fermi energy $`E_F=`$8 meV. The ESTs were defined by four Schottky gates S1, T, S2, and B patterned by electron beam lithography on the surface of the wafer. Figure 1 gives a schematic drawing of an EST device while Fig. 2 shows a scanning electron micrograph of a fabricated EST sample. Lighter areas are the Schottky metal gates on the wafer surface. The central part of the EST, where the SC is located, forms a lithographically rectangular planar quantum dot of length 0.55 and width 0.25 $`\mu `$m. The lithographic lengths of the QPCs is 0.1 $`\mu `$m. The samples were clamped to the mixing chamber of a dilution refrigerator. Considerable care was taken to ensure good thermal contact to the sample. The two-terminal conductance G of the devices was measured at 90 mK as function of a gate voltage, while the other gates were biased at fixed voltages. Standard low-bias, low-frequency, lock-in techniques were used to measure G, which was corrected for a low series resistance due to the 2DEG reservoirs. A source-drain rms excitation of 10 $`\mu `$V was typically used to drive a current along the length ($`x`$-direction) of the QPCs.

Since the four gates are independent, it was possible to characterize the QPCs of the EST device independently by biasing the appropriate gates while grounding the rest of them. High-quality, well-defined conductance quantization staircase was observed for both QPCs. The gates of the QPCs were negatively biased to assure fundamental-mode transport through them. The conductance G of the device was then measured as function of the size of the SC by sweeping the voltage $`V_T`$ of the top gate, or $`V_B`$ of the bottom gate, or $`V_S`$ of the side gates, while the other gates were biased at fixed negative voltages. The sweeping gate voltage was changed until the device was completely pinched off, allowing measurements in both the single-mode open and the tunneling regime of electron transport. Measurements were made on a few EST devices. All of them gave nearly identical and reproducible results differing only in the pinch-off voltages.

### B Experimental results

Figures 3 to 7 show the experimental results. Very well-defined oscillations in the ballistic conductance G are observed as a function of a sweeping gate voltage, which changes the size of the SC, while the other gates are biased at fixed voltages. These oscillations exhibit several features which are found to be generic to the EST devices studied. All results shown correspond to transport in the fundamental mode through the QPCs until they are pinched off.

Figure 3 shows the oscillations in G observed when the bias voltage $`V_T`$ of the top gate is swept, while the other gates are kept at fixed voltages. The solid curve is obtained when the bottom and the two side gates are biased, respectively, at $`V_B=765`$ mV, $`V_{S1}=860`$ mV, and $`V_{S2}=964`$ mV. As $`V_T`$ is made more negative the size of the SC shrinks. This also adds to the depletion due to the side gates and narrows the QPCs until they are pinched off when the device conductance drops to zero. The oscillations in $`G`$ are found to occur in two distinct regimes of the sweeping gate voltage, one for which $`G<e^2/h`$ and the other for which $`G>e^2/h`$. The one with $`G<e^2/h`$ is the tunneling regime when $`E_F`$ is below the bottom of the lowest conduction subband of the QPCs, which now form energy barriers through which electrons can tunnel. The oscillations of G in this regime are found to be periodic, quite sharp, and well resolved. The regime for which $`G>e^2/h`$ may be called the open regime. This happens when $`E_F`$ is above the bottom of the lowest subband of the QPCs such that transport is in the fundamental mode. The $`G`$ oscillations in this regime are located on the first quantized conductance plateau of the QPCs. Though quite robust, clear, and nearly periodic, they are relatively broad and show a certain degree of overlapping with the resulting convolution effect. The peak values are less than the expected quantized value of $`2e^2/h`$ and, as will be seen later, result from backscattering at the QPC entrance and/or from boundary roughness at the QPC walls. The dotted $`G`$ curve of Fig. 3 is obtained for $`V_B=780`$ mV and differs from the solid one in two important respects. First, the average conductance is substantially lower. Second, the oscillations in $`G`$ in the open regime become irregular due to the appearance of broad troughs or depressions in the conductance.

The size of the central ballistic cavity of the device can also be altered by varying the bias voltages of the side gates while keeping those of the top and bottom gates at fixed values. Figure 4 shows the variation in $`G`$ as function of the side gate bias voltage $`V_S`$ ($`V_S=V_{S1}=V_{S2}+104`$ mV). The solid curve was generated with $`V_T=1400`$ mV and $`V_B=755`$ mV, while the dotted curve was obtained for $`V_T=800`$ mV and $`V_B=790`$ mV. Results obtained by sweeping $`V_B`$ are illustrated in Fig. 5. For these measurements the side gates were biased as follows: $`V_{S1}=860`$ and $`V_{S2}=964`$ mV. The solid and dotted curves correspond, respectively, to $`V_T=1085`$ and $`635`$ mV. Comparing the results of Figs. 4 and 5 to those of Fig. 3, we notice that, except for the device pinch-off voltages and the oscillation periods, the features of the oscillations in $`G`$ are similar. The solid curves show the same characteristics, as do the dotted ones, though the features are different for the two sets. This is not surprising since in all cases we are changing the size of the central cavity. An interesting question, however, is what causes the difference in the characteristic features of the $`G`$ oscillations observed on the first conductance plateau for the solid and the dotted curves. If we look more closely and compare the constant gate bias voltages used for generating the two sets of $`G`$ curves, an empirical consistency emerges. The voltages used for the dotted curves are such as to result in a SC which is long compared to that for the corresponding solid curves. As an example, the oscillatory $`G`$ of the dotted curve in Fig. 4 is obtained for a $`V_T=800`$ mV, while for the solid curve $`V_T`$ is equal to $`1400`$ mV. A more negative top gate voltage certainly makes the SC shorter. These observations lead us to conclude that a lower average value of $`G`$ and broad depressions in it occur when the stub cavity is long. We call the oscillatory $`G`$ pattern with regular minima observed for the solid curves a ”regular” pattern and that for the dotted curves an ”irregular” pattern.

In order to better understand the origin of the observed oscillations in $`G`$ and to distinguish between the peaks in the tunneling and the open regime, we have studied the dependence of the regular $`G`$ pattern on temperature, drain-source excitation voltage, and a magnetic field applied perpendicular to the plane of the 2DEG. Figure 6 shows the temperature dependence of a regular $`G`$ pattern obtained by sweeping the top gate voltage $`V_T`$ with $`V_B=765`$ mV, $`V_{S1}=860`$ mV, and $`V_{S2}=964`$ mV. As the temperature is increased, all peaks in both the tunneling and the open regime broaden, and eventually they are washed out. At 4.2 K, the oscillatory $`G`$ pattern has disappeared and is replaced by the conductance step and plateau. At the highest temperature of 2.5 K measured in the dilution refrigerator, the peaks in the open regime have practically disappeared, while those in the tunneling regime show a trace existence. The influence of the source-drain voltage $`V_{ds}`$ on the regular $`G`$ pattern has also been studied and is shown in Fig. 7. Notice that the effect of increasing $`V_{ds}`$ is similar to that of temperature. The oscillations in $`G`$ are found to practically fade out and be replaced by the conductance step and plateau when $`V_{ds}`$ is increased to a rms value of 700 $`\mu `$V.

## III THEORETICAL TREATMENT

### A Cavity potential

A realistic, theoretical description of ballistic electron transport through a cavity, such as the stub of an EST, must take into account the electrostatic potential inside the cavity since it determines the actual shape of the conducting channel. Accordingly, we have calculated the electrostatic potential created in the plane of a 2DEG situated at a distance $`d=`$80 nm below the surface, at $`z=0`$, of a two-gate EST, defined by two surface Schottky gates with voltages $`V_T`$ and $`V_B`$, when $`S1`$, $`T`$, and $`S2`$ are connected together, cf. Fig. 1. The distance between the gates at entrance and exit is $`2w=`$250 nm, the bottom gate $`G_B`$ is flat, while the top gate $`G_T`$ contains the stub-like opening of width $`2w`$ and of length $`L=`$300 nm. This value of $`d`$ and the lithographic dimensions correspond to the experimental device described above, although the present model of just two gates is somewhat idealized but necessary for simplifying the calculations. The potential $`\phi (x,y,z)`$ has been calculated from the Laplace equation in the semi-space $`z>0`$, with Dirihlet boundary conditions $`\phi (x,y,0)=V_i`$ on the $`i`$th gate region ($`i=T,B`$) and Newmann boundary conditions $`\phi (x,y,z)/z|_{z=0}=4\pi en_{2D}/ϵ`$ at the exposed surface region; $`n_{2D}`$ is the electron concentration in the 2D gas in the absence of depletion and $`ϵ`$ is the dielectric constant. The last boundary condition expresses the so-called ”frozen surface model” in which the electric charge at the exposed surface is constant; this model appears appropriate at low temperatures and is often used in theoretical calculations. To make our model finite in the $`x`$ direction, we choose a length $`l=L`$ and use the boundary condition $`\phi (x,y,z)/x|_{x=\pm l}=0`$. We have also assumed that the concentration of the ionized donors in the doping region between the surface and the 2D gas plane is equal to a sum of the $`n_{2D}`$ and surface charge concentration and is not changed appreciably when the voltages are applied to the gates.

In Fig. 8 we present the resulting contour plot of the potential $`\phi (x,y,d)`$; since $`\phi (x,y,z)=\phi (x,y,z)`$, we show $`\phi `$ only for the right half of the stub. Although we do not take into account the free-electron charge in the plane $`z=d`$, in order to avoid the heavily involved self-consistent calculations, we expect that the screening effect due to these electrons will not change the shape of the equipotential lines considerably but would cause at most a flattening of the bottom of the potential distribition. As a result, we expect the shape of the conducting channel to follow, more or less, the calculated equipotential lines. This enables us to draw the following important qualitative conclusions.

i) The shape of the cavity inside the stub region does not follow that defined by the gate edges and is not rectangular as has been assumed in previous pertinent theoretical works.
ii) The width of the cavity is close to the lithographic width of the stub, and since the Fermi wavelength at $`E_F`$ 8 meV is about 53 nm, which is considerably less than the lithographic stub width $`2w`$, the cavity accommodates not just one longitudinal mode, as has been frequently assumed, but several modes.
iii) When the width of the narrowest part of the conducting channel, in our model at $`x=l`$, is small compared to the lithographic one $`2w`$ of the wire, the length of the cavity at $`x=0`$ is considerably smaller than the lithographic length $`L`$.
iv) The length of the cavity is even smaller when the upper gate voltage $`V_T`$ is more negative ($`V_T<V_B`$) so that there is an overall shift of the conducting channel towards the bottom gate. In going beyond the two-gate model towards the four-gate device shown in Fig. 1, it is reasonable to expect that when the top gate voltage is more negative than that of the side gates, the height of the cavity decreases, while in the opposite case it should increase.
In the following we use this qualitative information to appropriately model the shape of the conducting channel in the four-gate EST and calculate the electron transmission through the cavity.

### B Model of the cavity and numerical method

We model the conducting channel of the device in Fig. 1 with a 2D waveguide having hard-wall boundaries described, in an obvious notation, by the functions

$`y_{bot}(x)=y_{wire}(x),y_{wire}(x)=W/[1+\mathrm{exp}((x+r)/\beta )]+W/[1+\mathrm{exp}((x+r)/\beta )],`$ (1)
$`y_{top}(x)=y_{wire}(x)+a+y_{cav}(x),y_{cav}(x)=h\mathrm{exp}(x^2/b^2).`$ (2)
We describe the cavity with the Gaussian function $`y_{cav}(x)`$ since it gives us the most relevant elementary-function approximation of the equipotential lines shown in Fig. 8. The function $`y_{wire}(x)`$ describes the transition from the constricted region near $`x=0`$ to the 2D reservoirs at $`x=\pm \mathrm{}`$. Here we set $`\beta =W/4`$ to model the square-angle opening of the conducting channel of the experimental device (Fig. 1). The parameter $`W`$, which describes the semiwidth of the channels away from the constriction and must be large enough, is chosen as $`W=w`$. For this value of $`W`$, the channels away from the constriction already accommodate about 10 transverse modes and can be effectively treated as 2D leads. The remaining parameter $`r`$ is chosen, by inspection, as $`r=w+l+3\beta `$, where $`l`$ is the lithographic length of the QPCs; this gives a more or less suitable correspondence between the outer parts of the conducting channel and the gate corners. The resulting shape of the conducting channel, together with the lithographic gate layout, is shown in Fig. 9.

To determine the transmission coefficients of electron waves through the device, we solved numerically the 2D Schrödinger equation

$$\frac{\mathrm{}^2}{2m}\left(\frac{^2}{x^2}+\frac{^2}{y^2}\right)\mathrm{\Psi }(x,y)+[U(x,y)\epsilon ]\mathrm{\Psi }(x,y)=0,$$
(3)
using the following expansion for the wave function

$$\mathrm{\Psi }(x,y)=\underset{n}{}\psi _n(x)\chi _n(x,y),\chi _n(x,y)=\sqrt{\frac{2}{Y(x)}}\mathrm{sin}\left[\frac{\pi n}{Y(x)}(yy_{bot}(x))\right],$$
(4)
where $`Y(x)=y_{top}(x)y_{bot}(x)`$ is the $`x`$-dependent channel width. The basis functions $`\chi _n(x,y)`$ already satisfy the boundary conditions for hard-wall confinement. Substituting Eq. (4) into Eq. (3) leads to the 1D matrix equation for $`\psi _n(x)`$

$$\left[\frac{d^2}{dx^2}\left(\frac{\pi n}{Y(x)}\right)^2+k^2\right]\psi _n(x)+\underset{m}{}\left[2B_{nm}(x)\frac{d}{dx}+C_{nm}(x)K_{nm}(x)\right]\psi _m(x)=0;$$
(5)
here $`k^2=2m\epsilon /\mathrm{}^2`$ and

$`B_{nm}(x)={\displaystyle _{y_{bot}\left(x\right)}^{y_{top}\left(x\right)}}𝑑y\chi _n(x,y){\displaystyle \frac{}{x}}\chi _m(x,y),`$ (6)
$`C_{nm}(x)={\displaystyle _{y_{bot}\left(x\right)}^{y_{top}\left(x\right)}}𝑑y\chi _n(x,y){\displaystyle \frac{^2}{x^2}}\chi _m(x,y),`$ (7)
$`K_{nm}(x)={\displaystyle \frac{2m}{\mathrm{}^2}}{\displaystyle _{y_{bot}\left(x\right)}^{y_{top}\left(x\right)}}𝑑y\chi _n(x,y)U(x,y)\chi _m(x,y).`$ (8)
Since we assume $`U(x,y)=0`$ far away from the constriction, all parameters defined by Eqs. (6) depend on $`x`$ only in the constriction region. We choose $`x_{max}`$ and $`x_{min}`$ far enough from the constriction and discretize Eq. (5) on a $`N+1`$-point grid according to $`x=x_i=x_{min}+is`$, $`s=(x_{max}x_{min})/N`$. The resulting finite-difference equation for $`\psi _m(x_i)`$ is solved subject to the boundary conditions $`A_{nm}(1)\psi _m(x_1)+A_{nm}(0)\psi _m(x_0)=A_n^\alpha `$ and $`A_{nm}(N1)\psi _m(x_{N1})+A_{nm}(N)\psi _m(x_N)=0`$, appropriate to a wave, in state $`\alpha `$, incident from the left side. Since $`\chi _n(x,y)`$ are the exact normalized eigenfunctions of the problem at $`x=\pm \mathrm{}`$, the boundary matrices $`A_{nm}`$ are diagonal $`A_{nm}(1)=A_{nm}(N1)=\delta _{nm},A_{nm}(0)=A_{nm}(N)=\delta _{nm}\mathrm{exp}(ip_ns)`$, while $`A_n^\alpha =\delta _{n\alpha }[\mathrm{exp}(ip_ns)\mathrm{exp}(ip_ns)]`$. In these matrix expressions we introduced the longitudinal quantum number

$$p_n=\sqrt{k^2(\pi n/Y(\mathrm{}))^2},$$
(9)
which can be either real or imaginary ($`Imp_n>`$0); in the latter case the waves are evanescent in the leads. Far away from the constriction $`p_n`$ is the longitudinal momentum in the leads.

The ballistic conductance $`G`$ at zero temperature is given by the multichannel Landauer-Büttiker formula

$$G=\frac{2e^2}{h}\underset{\alpha \alpha ^{}}{}|T_{\alpha \alpha ^{}}|^2\frac{p_\alpha ^{}}{p_\alpha }.$$
(10)
The transmission amplitude $`T_{\alpha \alpha ^{}}`$ in Eq. (8) is equal to $`\psi _\alpha ^{}(x_N)`$ for the problem with the incident wave in state $`\alpha `$ and $`\epsilon =E_F`$. The sum runs over all propagating states (for which $`p_\alpha `$ are real). The generalization of Eq. (8) to finite temperatures is straightforward, see, e.g., Eq. (7) in Ref. 10. The actual number $`M`$ of transverse subbands involved in the numerical calculations is determined by the condition that further increase of $`M`$ does not produce any perceptible change of the calculated wave functions and transmission coefficients. For the calculations described below it is sufficient to take $`M`$ between 10 and 15; this results in a reasonably short calculation time.

### C Numerical results

In order to decrease the number of the unknown parameters, we restricted ourselves to the flat-band approximation, $`U(x,y)=0`$, in all calculations. As a result, we have only the three geometrical parameters $`a`$, $`h`$ and $`b`$, which are assumed to be controlled by the gates. The first of them, $`a`$, characterizes the width of the constriction in its narrowest parts, although it is somewhat smaller than the constriction width, cf. Eqs. (1) and (2). Assuming that the depletion of the 2DEG by the gates follows a linear law, which is confirmed by our experimental studies of the conductance quantization in a single constriction, we can directly associate a change of the value of $`a`$ with a change of the gate voltages. As for $`h`$ and $`b`$, they describe mostly the shape of the cavity formed in the stub region and are related, respectively, to its height and width. It is convenient to measure all these parameters in units of the cut-off length $`a_0=\mathrm{}\pi /\sqrt{2mE_F}`$, which is the width of the hard-wall quantum wire, when it stops conducting, and is equal to 26.5 nm for $`E_F=`$8 meV, a value of $`E_F`$ used in all calculations, and $`GaAs`$ effective mass $`m=0.067m_e`$.

Varying the bottom gate voltage $`V_B`$, in our model, means simply changing the parameter $`a`$ while keeping $`h`$ and $`b`$ constant. This describes the case when the lower (bottom) boundary of the conducting channel is shifted linearly by $`V_B`$, while the upper boundary remains insensitive to this voltage because of screening by the electron gas inside the channel. These assumptions are supported by previous calculations of the potential distribution in homogeneous, along $`x`$ axis, split-gate structures . The calculated dependence of the conductance on $`a/a_0`$, in the range of the first and second plateau, for two values of $`h`$ and $`b=w`$ is shown in Fig. 10. The following qualitative features are evident: for small $`h`$ the transmission pattern shows narrow, almost equally spaced minima of resonance reflections of similar shape: we call this the ”regular” pattern. The number of the minima on the first plateau (5-7) is consistent with the experimentally observed number (Fig. 5, solid curve). As $`h`$ increases ($`V_T`$ less negative), the oscillations become irregular and show broad troughs, on which are superimposed the closely spaced resonances, and the average conductance is considerably smaller than that of the shorter cavity. These results are consistent with experimental observations (Fig. 5, dotted curve). Results for a narrower cavity show a similar but less regular pattern.

The situation is more complex when the top gate voltage $`V_T`$ is varied. Making $`V_T`$ less negative obviously leads to an increase of $`h`$, and, as mentioned earlier, it also widens the constriction. To describe this situation $`a`$ and $`h`$ should be varied. Very likely the cavity width $`b`$ also changes in this situation, but we expect this change to be small and make the following assumptions in order to generate the numerical results: $`b`$ remains unchanged while $`h`$ varies linearly as $`h=h_0+va`$ as $`V_T`$ is changed. Since the distance of the top gate from the highest part of the cavity is smaller, but not much smaller, than its distance from the narrowest part of the constriction, we expect $`v`$ to be positive but not much larger than unity.

The dependence of $`G`$ on $`a/a_0`$, for fixed $`b=w`$ and different $`h_0`$ and $`v`$, is shown in Fig. 11 for the region of the first plateau. The curves marked (1) and (2) are obtained, respectively, with the $`h_0=1.2a_0`$, $`v=`$1, for (1), and $`h_0=0.6a_0`$, $`v=`$2 for (2). The parameters are chosen in such a way that at the beginning of the plateau ($`a/a_0`$ 0.6) the cavity height is equal to 1.8 $`a_0`$ for both curves. Curve (1), with smaller $`v`$, shows an oscillatory $`G`$ with regular minima, similar to those of curve (2) in Fig. 10 for constant $`h`$. But there is also a difference: the average conductance shows a small depression near the end of the plateau. As $`v`$ increases (curve (2)), the depression becomes more pronounced and broad, spreading over the second half of the plateau. Similar results, but with a less regular oscillatory pattern, are obtained for cavities with larger $`h`$, e.g., with $`h2.6a_0`$ at the beginning of the plateau. Also similar qualitative features have been obtained for narrower cavities ($`b=0.75w`$).

We do not discuss separately the case when the side-gate voltage $`V_S`$ is varied, with $`h`$ and $`a`$ changing simultaneously, since we expect the effect to be the same as when $`V_T`$ changes. The experimental results of Figs. 3 and 4 show no qualitative difference between the two cases and confirm this assessment.

## IV DISCUSSION AND CONCLUSIONS

Comparison of the experimental and theoretical results shows that the qualitative behavior of the ballistic conductance, as a function of different gate voltages, is the same in either case. This indicates that our choice of parameters and the assumptions about their variation with gate voltages, supported in part by the solution of the electrostatic problem, represent fairly the experimental situation. Below we discuss this in more detail.

When we make $`V_S`$ and $`V_T`$ more negative than $`V_B`$, the conducting channel is shifted towards the bottom gate and the cavity height $`h`$ decreases. In this situation we obtain rather regular oscillations of the conductance as a function of bottom, top or side gate voltages. The minima correspond to resonant reflections of the electron waves from quasibound states in the cavity . Variation of one of the gate voltages sweeps the levels of the quasibound states through the Fermi level $`E_F`$ and results in a resonance minimum each time $`E_F`$ coincides with one of them. The regularity in shape and spacing of these minima, for cavities with small heights, follows from the fact that these minima originate from the same set of quasibound states. For confirmation, we calculated again curves (1) in Figs. 10 and 11 with just two transverse cavity modes in the expansion (4); in the region of the first plateau the first mode is transmitted through the constrictions, while the second one is quasibound in the cavity. Comparing these results with the curves (1) of Figs. 10 and 11, we find that all regular resonances occuring on the first plateau appear also in this simplified calculation and their shapes are very similar. We, therefore, conclude that the regular resonance reflection pattern results from quasibound states associated with the second transverse mode and each of them characterized by a proper wavenumber that expresses longitudinal quantization along the $`x`$ direction. Higher transverse quantization states bring additional resonant features and make the dependence of the conductance on the gate voltages less regular. The experimental results of Figs. 3-5 (solid curves) show well-defined regularly spaced minima in $`G`$ and fully corroborate this analysis. Note that the number of the minima obtained from the theory is about the same as that observed experimentally; this means that the cavity width is really close to the lithographic width $`2w`$ of the stub, as we assumed in our model. The experimental dependences of the conductance on the top, side, and bottom gate voltages are similar and show almost the same number of oscillations. This is in agreement with our assumption that we are dealing with a wide cavity of small height. For the same $`h`$ the minima are narrower for wider cavities since in such a case the upper boundary of the cavity is smoother and the electron motion through the cavity is more adiabatic. In terms of our model this means that the derivative $`dy_{cav}(x)/dx`$ is smaller. Experimentally, a broadening of the cavity without changing its height can be achieved by applying less negative voltages to the side gates.

When we make $`V_S`$ and/or $`V_T`$ less negative compared to the values of the ”regular” case discussed above, the channel widens and the cavity height $`h`$ increases. In this ”irregular” case the situation is modified as follows. i) More quasibound states occur and influence the resonant reflection, ii) The coupling between transmitted and quasibound states increases due to the increase of the non-adiabaticity. Both these factors should lead to a decrease of the average conductance $`G`$. This decrease of $`G`$ is clearly seen in the theoretical results, cf. Figs. 10-11. Besides, the theory shows that the behavior of $`G`$ as a function of different gate voltages has a qualitative difference: the variation of $`V_B`$ produces broad minima and depression of the average $`G`$ over the entire plateaus while the variation of $`V_T`$ or $`V_S`$ gives narrower minima and the average $`G`$ has pronounced troughs near the ends of the plateaus. Our theoretical calculations show that the troughs are more pronounced when the height $`h`$ is larger and when it increases faster with the opening of the constriction. A simple explanation is as follows. Sweeping $`V_T`$ or $`V_S`$ towards less negative values along the conductance plateau substantially increases $`h`$ and leads to a departure from the short-cavity, ”regular” pattern to the ”irregular” one of a long-cavity. Therefore, the averaged $`G`$ decreases at the end of the first plateau and then increases, when the second transverse mode is allowed in the constriction, reaching the next plateau. If the initial value of $`h`$ is already large, we need a lesser increase in $`h`$ in order to move to the long-cavity regime; then the decrease of the average $`G`$ appears earlier and gives rise to a broader trough. The experimentally observed behavior of $`G`$, cf. dashed curves in Figs. 3-5, shows pronounced troughs and a decrease in its average value in agreement with the above interpretation. We emphasize that the appearance of these troughs in $`G`$ is a very common and reproducible feature of the stubbed quantum devices studied in this work.

Possible EST applications require a regular, periodic dependence of the conductance on the gate voltages. The initial idea1, followed in subsequent theoretical works, was to use a narrow cavity, containing one quantized state, or mode, in the ($`x`$) transport direction, and control the conductance through it by changing the height of the cavity by a top-gate voltage. However, from our results it is clear that real EST devices do not satisfy these conditions because the electrostatic potential created by the gates is rounded near the corners, cf. Fig. 8. Moreover, for a real device, as this work shows, if the cavity is long enough, the dependence of the conductance on the gate voltages is rather irregular. We have shown that it is possible to obtain a short-length cavity by a proper choice of the gate voltages that is wide in the transport direction. The conductance through such a cavity shows a regular pattern of resonant reflection minima associated with the quasibound states in it that result from longitudinal quantization.

###### Acknowledgements.

One of us (P. D.) gratefully acknowledges the award of a Senior Research Associateship by the National Research Council, Washington, DC. The work of P. V. was supported by the Canadian NSERC Grant No. OGP0121756.


text:
# Quantum lower bounds by quantum arguments

## 1 Introduction

In the query model, algorithms access the input only by querying input items and the complexity of the algorithm is measured by the number of queries that it makes. Many quantum algorithms can be naturally expressed in this model. The most famous examples are Grover’s algorithm for searching an $`N`$-element list with $`O(\sqrt{N})`$ quantum queries and period-finding which is the basis of Shor’s factoring algorithm.

In the query setting, one can not only construct efficient quantum algorithms but also prove lower bounds on the number of queries that any quantum algorithm needs. For example, it can be shown that any algorithm solving the unordered search problem needs $`\mathrm{\Omega }(\sqrt{N})`$ queries. (This implies that Grover’s algorithm is optimal.)

The lower bounds in quantum query model provide insights into the limitations of quantum computing. For example, the unordered search problem provides an abstract model for NP-complete problems and the $`\mathrm{\Omega }(\sqrt{N})`$ lower bound of  provided evidence of the difficulty of solving these problems on a quantum computer.

For two related problems - inverting a permutation (often used to model one-way permutation) and AND of ORs only weaker lower bounds have been known. Both of these problems can be solved using Grover’s algorithm with $`O(\sqrt{N})`$ queries for inverting a permutation and $`O(\sqrt{N}\mathrm{log}N)`$ queries for AND of ORs. However, the best lower bounds have been $`\mathrm{\Omega }(\sqrt[3]{N})`$ and $`\mathrm{\Omega }(\sqrt[4]{N})`$, respectively.

We present a new method for proving lower bounds on quantum query algorithms and use it to prove $`\mathrm{\Omega }(\sqrt{N})`$ lower bounds for inverting a permutation and AND of ORs. It also provides a unified proof for several other results that have been previously proven via variety of different techniques.

In contrast to  that use a classical adversary argument (an adversary runs the algorithm with one input and, after that, changes the input slightly so that the correct answer changes but the algorithm does not notice that), we use a quantum adversary. In other words, instead of running the algorithm with one input, we run it with a superposition of inputs. This gives stronger bounds and can also simplify the proofs.

More formally, we consider a bipartite quantum system consisting of the algorithm and an oracle answering algorithm’s queries. At the beginning, the algorithm part is in its starting state (normally $`|0`$), the oracle part is in a uniform superposition over some set of inputs and the two parts are not entangled.

In the query model, the algorithm can either perform a unitary transformation that does not depend on the input or a query transformation that accesses the input. The unitary transformations of the first type become unitary transformations over the algorithm part of the superposition. The queries become transformations entangling the algorithm part with the oracle part.

If the algorithm works correctly, the algorithm part becomes entangled with the oracle part because the algorithm part must contain different answers for different inputs. We obtain lower bounds on quantum algorithms by bounding the number of query transformations needed to achieve such entanglement.

Previously, two main lower bound methods were classical adversary (called ’hybrid argument’ in ) and polynomials methods. The classical adversary/hybrid method of  starts with running the algorithm on one input. Then the input is modified so that the behavior of algorithm does not change much but the correct answer does change. That implies that the problem cannot be solved with a small number of queries. Polynomials method uses the fact that any function computable with a small number of queries can be approximated by a polynomial of a small degree and then applies results about inapproximability by polynomials.

Our “quantum adversary” method can be used to give more unified proofs for many (but not all) results that were previously shown using different variants of hybrid and/or polynomials method.

There is also a new proof of the $`\mathrm{\Omega }(\sqrt{N})`$ lower bound on unordered search by Grover. This proof is based on considering the sum of distances between superpositions on different inputs. While the motivation for Grover’s proof (sum of distances) is fairly different from ours (quantum adversary), these two methods are, in fact, closely related. We discuss this relation in section 7.

## 2 The model

We consider computing a Boolean function $`f(x_1,\mathrm{},x_N):\{0,1\}^N\{0,1\}`$ in the quantum query model. In this model, the input bits can be accessed by queries to an oracle $`X`$ and the complexity of $`f`$ is the number of queries needed to compute $`f`$.

A quantum computation with $`T`$ queries is just a sequence of unitary transformations

$$U_0OU_1O\mathrm{}U_{T1}OU_T.$$

$`U_j`$’s can be arbitrary unitary transformations that do not depend on the input bits $`x_1,\mathrm{},x_N`$. $`O`$ are query (oracle) transformations. To define $`O`$, we represent basis states as $`|i,b,z`$ where $`i`$ consists of $`\mathrm{log}N`$ bits, $`b`$ is one bit and $`z`$ consists of all other bits. Then, $`O`$ maps $`|i,b,z`$ maps to $`|i,bx_i,z`$. (i.e., the first $`\mathrm{log}N`$ bits are interpreted as an index $`i`$ for an input bit $`x_i`$ and this input bit is XORed on the next qubit.) We use $`O_x`$ to denote the query transformation corresponding to an input $`x=(x_1,\mathrm{},x_n)`$.

Also, we can define that $`O`$ maps $`|i,b,z`$ to $`(1)^{bx_i}|i,b,z`$ (i.e., instead of XORing $`x_i`$ on an extra qubit we change phase depending on $`x_i`$). It is well known that both definitions are equivalent up to a constant factor: one query of the $`1^{\mathrm{st}}`$ type can be simulated with a one query of the $`2^{\mathrm{nd}}`$ type and one query of the $`2^{\mathrm{nd}}`$ type can be simulated with 2 queries of the $`1^{\mathrm{st}}`$ type. For technical convenience, we use the $`2^{\mathrm{nd}}`$ definition in most of this paper.

The computation starts with a state $`|0`$. Then, we apply $`U_0`$, $`O`$, $`\mathrm{}`$, $`O`$, $`U_T`$ and measure the final state. The result of the computation is the rightmost bit of the state obtained by the measurement.

The quantum computation computes $`f`$ with bounded error if, for every $`x=(x_1,\mathrm{},x_N)`$, the probability that the rightmost bit of $`U_TO_xU_{T1}\mathrm{}O_xU_0|0`$ equals $`f(x_1,\mathrm{},x_N)`$ is at least $`1ϵ`$ for some fixed $`ϵ<1/2`$.

This model can be easily extended to functions defined on a larger set (for example, $`\{1,\mathrm{},N\}`$) or functions having more than 2 values. In the first case, we replace one bit $`b`$ with several bits ($`\mathrm{log}N`$ bits in the case of $`\{1,\mathrm{},N\}`$). In the second case, we measure several rightmost bits to obtain the answer.

## 3 The main idea

Let $`S`$ be a subset of the set of possible inputs $`\{0,1\}^N`$. We run the algorithm on a superposition of inputs in $`S`$. More formally, let $`_A`$ be the workspace of the algorithm. We consider a bipartite system $`=_A_I`$ where $`_I`$ is an “input subspace” spanned by basis vectors $`|x`$ corresponding to inputs $`xS`$.

Let $`U_TOU_{T1}\mathrm{}U_0`$ be the sequence of unitary transformations on $`_A`$ performed by the algorithm $`A`$ (with $`U_0,\mathrm{},U_T`$ being the transformations that do not depend on the input and $`O`$ being the query transformations). We transform it into a sequence of unitary transformations on $``$. A unitary transformation $`U_i`$ on $`_A`$ corresponds to the transformation $`U_i^{}=U_iI`$ on the whole $``$. The query transformation $`O`$ corresponds to a transformation $`O^{}`$ that is equal to $`O_x`$ on subspace $`H_A|x`$.

We perform the sequence of transformations $`U_T^{}O^{}U_{T1}^{}\mathrm{}U_0^{}`$ on the starting state

$$|\psi _{start}=|0\underset{xS}{}\alpha _x|x.$$

Then, the final state is

$$|\psi _{end}=\underset{xS}{}\alpha _x|\psi _x|x$$

where $`|\psi _x`$ is the final state of $`A=U_TOU_{T1}\mathrm{}U_0`$ on the input $`x`$. This follows from the fact that the restrictions of $`U_T^{},O^{},U_{T1}^{},\mathrm{},U_0^{}`$ to $`_A|x`$ are $`U_T`$, $`O_x`$, $`U_{T1}`$, $`\mathrm{}`$, $`U_0`$ and these are exactly the transformations of the algorithm $`A`$ on the input $`x`$.

In the starting state, the $`_A`$ and $`_I`$ parts of the superposition are unentangled. In the final state, however, they must be entangled (if the algorithm works correctly). To see that, consider a simple example where the algorithm has to recover the whole input.

Let $`\alpha _x=1/\sqrt{m}`$ (where $`m=|S|`$) for all $`xS`$. In the exact model (the algorithm is not allowed to give the wrong answer even with a small probability), $`|\psi _x`$ must be $`|x|\phi _x`$ where $`|x`$ is the answer of the algorithm and $`|\phi _x`$ are algorithm’s workbits. This means that the final state is

$$\frac{1}{\sqrt{m}}\underset{xS}{}|x|\phi _x|x,$$

i.e., it is fully entangled state. In the bounded error model (the algorithm can give a wrong answer with a probability at most $`ϵ`$), $`|\psi _x`$ must be $`(1ϵ)|x|\phi _x+|\psi _x^{}`$ and the final state must be

$$\frac{1}{\sqrt{m}}\underset{xS}{}((1ϵ)|x|\phi _x+|\psi _x^{})|x$$

which is also quite highly entangled.

In the general case (we have to compute some function $`f`$ instead of learning the whole input $`x`$), the parts of $`_I`$ corresponding to inputs with $`f(x)=z`$ must become entangled with parts of $`_A`$ corresponding to the answer $`z`$.

Thus, we can show a lower bound on quantum query algorithms by showing that, given an unentangled start state, we cannot achieve a highly entangled end state with less than a certain number of query transformations.

Next, we describe more formally how we bound this entanglement. If we trace out $`_A`$ from the states $`|\psi _{start}`$ and $`|\psi _{end}`$, we obtain mixed states over $`_I`$. Let $`\rho _{start}`$ and $`\rho _{end}`$ be the density matrices describing these states.

$`\rho _{start}`$ is a $`m\times m`$ matrix corresponding to the pure state $`_{xS}\alpha _x|x`$. Entries of this matrix are $`(\rho _{start})_{xy}=\alpha _x^{}\alpha _y`$. In particular, if the start state is $`\frac{1}{\sqrt{m}}_{xS}|x`$, all entries of the $`\rho _{start}`$ are $`1/m`$.

For $`\rho _{end}`$ we have

###### Lemma 1

Let $`A`$ be an algorithm that computes $`f`$ with probability at least $`1ϵ`$. Let $`x,y`$ be such that $`f(x)f(y)`$. Then,

$$|(\rho _{end})_{xy}|2\sqrt{ϵ(1ϵ)}|\alpha _x||\alpha _y|.$$

Proof: Let $`|\psi _x`$, $`|\psi _y`$ be the final superpositions of the algorithm $`A`$ on inputs $`x,y`$. We take a basis for $`_A`$ consisting of the vectors of the form $`|z|v`$ where $`|z`$ is a basis for the answer part (the part which is measured at the end of algorithm to obtain the answer) and $`|v`$ is a basis for the rest of $`_A`$ (workbits). We express $`|\psi _x`$ and $`|\psi _y`$ in this basis. Let

$$|\psi _x=\underset{z,v}{}a_{z,v}|z|v,\text{ }|\psi _y=\underset{z,v}{}b_{z,v}|z|v.$$

The final state of the algorithm is $`_{xS}\alpha _x|\psi _x|x`$. By tracing out $`_A`$ in the $`|z|v`$ basis, we get

$$(\rho _{end})_{xy}=\alpha _x\alpha _y\underset{z,v}{}a_{z,v}^{}b_{z,v}.$$

Define $`ϵ_1=_{z,v:zf(x)}|a_{z,v}|^2`$ and $`ϵ_2=_{z,v:z=f(x)}|b_{z,v}|^2`$. Then, $`ϵ_1ϵ`$ and $`ϵ_2ϵ`$ (because these are the probabilities that the measurement at the end of algorithm gives us a wrong answer: not $`f(x)`$ for the input $`x`$ and $`f(x)`$ for the input $`y`$). We have

$$|\underset{z,v}{}a_{z,v}^{}b_{z,v}|\underset{z,v}{}|a_{z,v}||b_{z,v}|=\underset{z,v:z=f(x)}{}|a_{z,v}||b_{z,v}|+\underset{z,v:zf(x)}{}|a_{z,v}||b_{z,v}|$$

$$\sqrt{\underset{z,v:z=f(x)}{}|a_{z,v}|^2}\sqrt{\underset{z,v:z=f(x)}{}|b_{z,v}|^2}+\sqrt{\underset{z,v:zf(x)}{}|a_{z,v}|^2}\sqrt{\underset{z,v:zf(x)}{}|b_{z,v}|^2}=\sqrt{(1ϵ_1)ϵ_2}+\sqrt{ϵ_1(1ϵ_2)}.$$

This expression is maximized by $`ϵ_1=ϵ_2=ϵ`$, giving us $`2\sqrt{ϵ(1ϵ)}`$. Therefore,

$$|(\rho _{end})_{xy}|=|\alpha _x||\alpha _y||\underset{z,v}{}a_{z,v}^{}b_{z,v}|2\sqrt{ϵ(1ϵ)}|\alpha _x||\alpha _y|.$$

$`\mathrm{}`$

In particular, if $`|\psi _{start}`$ is the uniform $`\frac{1}{\sqrt{m}}_{xS}|x`$, we have $`(\rho _{end})_{xy}2\sqrt{ϵ(1ϵ)}/m`$. Note that, for any $`ϵ<1/2`$, $`2\sqrt{ϵ(1ϵ)}<1`$. Thus, if the algorithm $`A`$ works correctly, the absolute value of every entry of $`\rho _{end}`$ that corresponds to inputs $`x,y`$ with $`f(x)f(y)`$ must be smaller than the corresponding entry of $`\rho _{start}`$ by a constant fraction.

To prove a lower bound on the number of queries, we bound the change in $`\rho _{xy}`$ caused by one query. Together with Lemma 1, this implies a lower bound on the number of queries.

## 4 Lower bound on search

Next, we apply this technique to several problems. We start with the simplest case: the lower bound on unordered search problem (Theorem 1). Then, we show two general lower bound theorems (Theorems 2 and 6).

Each of these theorems is a special case of the next one: Theorem 2 implies Theorem 1 and Theorem 6 implies Theorem 2. However, more general theorems have more complicated proofs and it is easier to see the main idea in the simple case of unordered search. Therefore, we show this case first, before general theorems 2 and 6.

Problem: We are given $`x_1,\mathrm{},x_N\{0,1\}`$ and we have to find $`i`$ such that $`x_i=1`$.

###### Theorem 1

 Any quantum algorithm that finds $`i`$ with probability $`1ϵ`$ uses $`\mathrm{\Omega }(\sqrt{N})`$ queries.

Proof: Let $`S`$ be the set of inputs with one $`x_i`$ equal to 1 and the rest 0. Then, $`|S|=N`$ and $`_I`$ is an $`N`$-dimensional space. To simplify the notation, we use $`|i`$ to denote the basis state of $`_I`$ corresponding to the input $`(x_1,\mathrm{},x_N)`$ with $`x_i=1`$.

Let $`\rho _k`$ be the density matrix of $`_I`$ after $`k`$ queries. Note that $`\rho _0=\rho _{start}`$ and $`\rho _T=\rho _{end}`$. We consider the sum of absolute values of all its off-diagonal entries $`S_k=_{x,y,xy}|(\rho _k)_{xy}|`$. We will show that

1. $`S_0=N1`$,
2. $`S_T2\sqrt{ϵ(1ϵ)}(N1)`$
3. $`S_{k1}S_k2\sqrt{N1}`$ for all $`k\{1,\mathrm{},T\}`$.

This implies that the number of queries $`T`$ is at least $`(12\sqrt{ϵ(1ϵ)})\sqrt{N1}/2`$.

The first two properties follow straightforwardly from the results at the end of section 3. $`N\times N`$ matrices $`\rho _i`$ have $`N(N1)`$ non-diagonal entries and each of these entries is $`1/N`$ in $`\rho _{start}`$ and at most $`2\sqrt{ϵ(1ϵ)}/N`$ in $`\rho _{end}`$ (Lemma 1 together with the fact that each of these entries corresponds to two inputs with different answers).

It remains to prove the third part. First, notice that

$$S_{k1}S_k=\underset{x,y:xy}{}|(\rho _{k1})_{xy}|\underset{x,y:xy}{}|(\rho _k)_{xy}|\underset{x,y:xy}{}|(\rho _{k1})_{xy}(\rho _k)_{xy}|.$$

Therefore, it suffices to bound the sum of $`|(\rho _{k1})_{xy}(\rho _k)_{xy}|`$.

A query corresponds to representing the pure state before the query as

$$|\psi _{k1}=\underset{i,z}{}\sqrt{p_{i,z}}|i,z|\psi _{i,z},$$

$$|\psi _{i,z}=\underset{j=1}{\overset{n}{}}\alpha _{i,z,j}|j$$

and changing the phase on the $`|i`$ component of $`|\psi _{i,z}`$. If we consider just the $`H_I`$ part, the density matrix $`\rho _{k1}`$ before the query is $`_{i,z}p_{i,z}|\psi _{i,z}\psi _{i,z}|`$. The density matrix $`\rho _k`$ after the query is $`_{i,z}p_{i,z}|\psi _{i,z}^{}\psi _{i,z}^{}|`$ where

$$|\psi _{i,z}^{}=\underset{ji}{}\alpha _{i,z,j}|j\alpha _{i,z,i}|i.$$

Consider $`\rho _{i,z}=|\psi _{i,z}\psi _{i,z}|`$ and $`\rho _{i,z}^{}=|\psi _{i,z}^{}\psi _{i,z}^{}|`$. Then, $`\rho _{k1}=_{i,z}p_{i,z}\rho _{i,z}`$ and $`\rho _k=_{i,z}p_{i,z}\rho _{i,z}^{}`$.

The only entries where $`\rho _{i,z}`$ and $`\rho _{i,z}^{}`$ differ are the entries in the $`i^{\mathrm{th}}`$ column and the $`i^{\mathrm{th}}`$ row. These entries are $`\alpha _{i,z,j}^{}\alpha _{i,z,i}`$ in $`\rho _{i,z}`$ and -$`\alpha _{i,z,j}^{}\alpha _{i,z,i}`$ in $`\rho _{i,z}^{}`$. The sum of absolute values of the differences of all entries in the $`i^{\mathrm{th}}`$ row is

$$\underset{ji}{}2|\alpha _{i,z,j}^{}\alpha _{i,z,i}|2|\alpha _{i,z,i}|\underset{ji}{}|\alpha _{i,z,j}|.$$

Similarly, the sum of absolute values of the differences of all entries in the $`i^{\mathrm{th}}`$ column is at most $`2|\alpha _{i,z,i}|_{ji}|\alpha _{i,z,j}|`$ as well. So, the sum of absolute values of all differences is at most $`4|\alpha _{i,z,i}|_{ji}|\alpha _{i,z,j}|`$.

By Cauchy-Schwartz inequality,

$$\underset{ji}{}|\alpha _{i,z,j}|\sqrt{N1}\sqrt{\underset{ji}{}|\alpha _{i,z,j}|^2}=\sqrt{N1}\sqrt{1|\alpha _{i,z,i}|^2}.$$

Therefore,

$$\underset{ji}{}4|\alpha _{i,z,j}^{}\alpha _{i,z,i}|4\sqrt{N1}|\alpha _{i,z,i}|\sqrt{1|\alpha _{i,z,i}|^2}2\sqrt{N1}.$$

Define $`S_{i,z}=_{x,y:xy}|(\rho _{i,z})_{xy}(\rho _{i,z}^{})_{xy}|`$. Then, we have just shown $`S_{i,z}2\sqrt{N1}`$. This implies a bound on the sum $`_{x,y:xy}|(\rho _{k1})_{xy}(\rho _k)_{xy}|`$.

$$\underset{x,y:xy}{}|(\rho _{k1})_{xy}(\rho _k)_{xy}|=\underset{x,y:xy}{}|\underset{i,z}{}p_{i,z}(\rho _{i,z})_{xy}\underset{i,z}{}p_{i,z}(\rho _{i,z}^{})_{xy}|$$

$$\underset{i,z}{}p_{i,z}\underset{x,y:xy}{}|(\rho _{i,z})_{xy}(\rho _{i,z}^{})_{xy}|\underset{i,z}{}p_{i,z}2\sqrt{N1}=2\sqrt{N1}.$$

This completes the proof. $`\mathrm{}`$

## 5 The general lower bound

### 5.1 The result

Next, we obtain a general lower bound theorem.

###### Theorem 2

Let $`f(x_1,\mathrm{},x_N)`$ 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 $`xX`$ and $`i\{1,\mathrm{},n\}`$, there are at most $`l`$ different $`yY`$ such that $`(x,y)R`$ and $`x_iy_i`$.
4. For every $`yY`$ and $`i\{1,\mathrm{},n\}`$, 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.

Proof: Consider the set of inputs $`S=XY`$ and the superposition

$$\frac{1}{\sqrt{2|X|}}\underset{xX}{}|x+\frac{1}{\sqrt{2|Y|}}\underset{yY}{}|y$$

over this set of inputs. Let $`S_i`$ be the sum of $`|(\rho _i)_{xy}|`$ over all $`x,y`$ such that $`(x,y)R`$. Then, the theorem follows from

1. $`S_0S_T(12\sqrt{ϵ(1ϵ)})\sqrt{mm^{}}`$
2. $`S_{k1}S_k\sqrt{ll^{}}`$

To show the first part, let $`(x,y)R`$. Then, $`(\rho _0)_{xy}=\frac{1}{\sqrt{|X||Y|}}`$ and $`|(\rho _T)_{xy}|\frac{2\sqrt{ϵ(1ϵ)}}{\sqrt{|X||Y|}}`$ (Lemma 1). Therefore,

$$|(\rho _0)_{xy}||(\rho _T)_{xy}|\frac{12\sqrt{ϵ(1ϵ)}}{\sqrt{|X||Y|}}.$$

The number of $`(x,y)R`$ is at least $`\mathrm{max}(|X|m,|Y|m^{})`$ because for every $`xX`$, there are at least $`m`$ possible $`yY`$ and, for every $`yY`$, there are at least $`m^{}`$ possible $`xX`$. We have

$$\mathrm{max}(|X|m,|Y|m^{})\frac{|X|m+|Y|m^{}}{2}\sqrt{|X||Y|mm^{}},$$

$$S_0S_T\sqrt{|X||Y|mm^{}}\frac{12\sqrt{ϵ(1ϵ)}}{\sqrt{|X||Y|}}=(12\sqrt{ϵ(1ϵ)})\sqrt{mm^{}}.$$

Next, we prove the second part. Similarly to the previous proof, we represent

$$|\psi _{k1}=\underset{i,z}{}\sqrt{p_{i,z}}|i,z|\psi _{i,z},$$

$$|\psi _{i,z}=\underset{xS}{}\alpha _{i,z,x}|x.$$

A query corresponds to changing the sign on all components with $`x_i=1`$. It transforms $`|\psi _{i,z}`$ to

$$|\psi _{i,z}^{}=\underset{xS:x_i=0}{}\alpha _{i,z,x}|x\underset{xS:x_i=1}{}\alpha _{i,z,x}|x.$$

Let $`\rho _{i,z}=|\psi _{i,z}\psi _{i,z}|`$ and $`\rho _{i,z}^{}=|\psi _{i,z}^{}\psi _{i,z}^{}|`$. We define $`S_{i,z}=_{(x,y)R}|(\rho _{i,z})_{xy}(\rho _{i,z}^{})_{xy}|`$.

If $`x_i=y_i`$, then $`(\rho _{i,z})_{xy}`$ and $`(\rho _{i,z}^{})_{xy}`$ are the same. If one of $`x_i`$, $`y_i`$ is 0 and the other is 1, $`(\rho _{i,z})_{xy}=(\rho _{i,z}^{})_{xy}`$ and $`|(\rho _{i,z})_{xy}(\rho _{i,z}^{})_{xy}|=2|(\rho _{i,z})_{xy}|=2|\alpha _{i,z,x}||\alpha _{i,z,y}|`$. Therefore,

$$S_{i,z}=\underset{(x,y)R:x_iy_i}{}2|\alpha _{i,z,x}||\alpha _{i,z,y}|\underset{(x,y)R:x_iy_i}{}\sqrt{\frac{l^{}}{l}}|\alpha _{i,z,x}|^2+\sqrt{\frac{l}{l^{}}}|\alpha _{i,z,y}|^2$$

$$\underset{xX}{}l\sqrt{\frac{l^{}}{l}}|\alpha _{i,z,x}|^2+\underset{yY}{}l^{}\sqrt{\frac{l}{l^{}}}|\alpha _{i,z,y}|^2=\sqrt{ll^{}}\underset{xXY}{}|\alpha _{i,z,x}|^2=\sqrt{ll^{}}.$$

Similarly to the previous proof, this implies the same bound on $`S_{k1}S_k`$. $`\mathrm{}`$

### 5.2 Relation to block sensitivity bound

Our Theorem 2 generalizes the block sensitivity bound of .

Let $`f`$ be a Boolean function and $`x=(x_1,\mathrm{},x_n)`$ an input to $`f`$. For a set $`S\{1,\mathrm{},n\}`$, $`x^{(S)}`$ denotes the input obtained from $`x`$ by flipping all variables $`x_i`$, $`iS`$. $`f`$ is sensitive to $`S`$ on input $`x`$ if $`f(x)f(x^{(S)})`$.

The block sensitivity of $`f`$ on input $`x`$ is the maximal number $`t`$ such that there exist $`t`$ pairwise disjoint sets $`S_1`$, $`S_2`$, $`\mathrm{}`$, $`S_t`$ such that, for all $`i\{1,\mathrm{},t\}`$, $`f`$ is sensitive to $`S_i`$ on $`x`$. We denote it by $`bs_x(f)`$. The block sensitivity of $`f`$, $`bs(f)`$ is just the maximum of $`bs_x(f)`$ over all inputs $`x`$.

###### Theorem 3

 Let $`f`$ be any Boolean function. Then, any quantum query algorithm computing $`f`$ uses $`\mathrm{\Omega }(\sqrt{bs(f)})`$ queries.

To see that this is a particular case of Theorem 2, let $`x`$ be the input on which $`f`$ achieves $`bs(f)`$ block sensitivity. Then, we can take $`X=\{x\}`$ and $`Y=\{x^{(S_1)},\mathrm{},x^{(S_{bs(f)})}\}`$.

Let $`R=\{(x,x^{(S_1)}),(x,x^{(S_2)}),\mathrm{},(x,x^{(S_{bs(f)})})\}`$. Then, $`m=bs(f)`$, $`m^{}=1`$. Also, $`l=1`$ (because, by the definition of the block sensitivity, $`m`$ blocks of input variables have to be disjoint) and $`l^{}=1`$. Therefore, we get $`\frac{mm^{}}{ll^{}}=bs(f)`$ and Theorem 2 gives the $`\mathrm{\Omega }(\sqrt{bs(f)})`$ lower bound for any Boolean function $`f`$.

In the next subsection we show some problems for which our method gives a better bound than the block-sensitivity method.

### 5.3 Applications

For a first application, consider AND of ORs:

$$f(x_1,\mathrm{},x_N)=(x_1ORx_2\mathrm{}ORx_\sqrt{N})AND$$

$$(x_{\sqrt{N}+1}\mathrm{}x_{2\sqrt{N}})AND\mathrm{}AND(x_{N\sqrt{N}+1}OR\mathrm{}ORx_N)$$

where $`x_1,\mathrm{},x_N\{0,1\}`$.

$`f`$ can be computed with $`O(\sqrt{N}\mathrm{log}N)`$ queries by a two-level version of Grover’s algorithm (see ). However, a straightforward application of lower bound methods from  only gives an $`\mathrm{\Omega }(\sqrt[4]{N})`$ bound because the block sensitivity of $`f`$ is $`\mathrm{\Theta }(\sqrt{N})`$ and the lower bound on the number of queries given by hybrid or polynomials method is the square root of block sensitivity. Our method gives

###### Theorem 4

Any quantum algorithm computing AND of ORs uses $`\mathrm{\Omega }(\sqrt{N})`$ queries.

Proof: For this problem, let $`X`$ be the set of all $`x=(x_1,\mathrm{},x_n)`$ such that, for every $`i\{1,\mathrm{},\sqrt{N}\}`$, there is exactly one $`j\{1,\mathrm{},\sqrt{n}\}`$ with $`x_{(i1)\sqrt{N}+j}=1`$. $`Y`$ is the set of all $`y=(y_1,\mathrm{},y_n)`$ such that $`y_{(i1)\sqrt{N}+1}=\mathrm{}=y_{i\sqrt{N}}=0`$ for some $`i`$ and, for every $`i^{}i`$, there is a unique $`j\{1,\mathrm{},\sqrt{N}\}`$ with $`y_{(i1)\sqrt{N}+j}=1`$. $`R`$ consists of all pairs $`(x,y)`$, $`xX`$, $`yY`$ such that there is exactly one $`i`$ with $`x_iy_i`$.

Then, $`m=m^{}=\sqrt{n}`$ because, given $`xX`$, there are $`\sqrt{n}`$ 1s that can be replaced by 0 and replacing any one of them gives some $`yY`$. Conversely, if $`yY`$, there are $`\sqrt{n}`$ ways to add one more 1 so that we get $`xX`$. On the other hand, $`l=l^{}=1`$ because, given $`xX`$ (or $`yY`$) and $`i\{1,\mathrm{},n\}`$, there is only one input that differs from $`x`$ only in the $`i^{\mathrm{th}}`$ position. Therefore, $`\sqrt{\frac{mm^{}}{ll^{}}}=\sqrt{n}`$ and the result follows from Theorem 2. $`\mathrm{}`$

Our theorem can be also used to give another proof for the following theorem of Nayak and Wu.

###### Theorem 5

 Let $`f:\{0,1,\mathrm{},n1\}\{0,1\}`$ be a Boolean function that is equal to 1 either at exactly $`n/2`$ points of the domain or at exactly $`(1+ϵ)n/2`$ points. Then, any quantum algorithm that determines whether the number of points where $`f(x)=1`$ is $`n/2`$ or $`(1+ϵ)n/2`$ uses $`\mathrm{\Omega }(\frac{1}{ϵ})`$ queries.

This result implies lower bounds on the number of quantum queries needed to compute (or to approximate) the median of $`n`$ numbers. It was shown in  using polynomials method. No proof that uses adversary arguments similar to  is known.

With our “quantum adversary” method, Theorem 5 can be proven in similarly to other theorems in this paper.

Proof: Let $`X`$ be the set of all $`f`$ that are 1 at exactly $`n/2`$ points, $`Y`$ be the set of all $`f`$ that are 1 at $`(1+ϵ)n/2`$ points and $`R`$ be the set of all $`(f,f^{})`$ such that $`fX`$, $`f^{}Y`$ and they differ in exactly $`ϵn/2`$ points.

Then, $`m=\left(\genfrac{}{}{0pt}{}{n/2}{ϵn/2}\right)`$ and $`m^{}=\left(\genfrac{}{}{0pt}{}{(1+ϵ)n/2}{ϵn/2}\right)`$. On the other hand, $`l=\left(\genfrac{}{}{0pt}{}{n/21}{ϵn/21}\right)`$ and $`l^{}=\left(\genfrac{}{}{0pt}{}{(1+ϵ)n/21}{ϵn/21}\right)`$. Therefore,

$$\frac{mm^{}}{ll^{}}=\frac{\left(\genfrac{}{}{0pt}{}{n/2}{ϵn/2}\right)\left(\genfrac{}{}{0pt}{}{(1+ϵ)n/2}{ϵn/2}\right)}{\left(\genfrac{}{}{0pt}{}{n/21}{ϵn/21}\right)\left(\genfrac{}{}{0pt}{}{(1+ϵ)n/21}{ϵn/21}\right)}=\frac{\frac{n}{2}\frac{(1+ϵ)n}{2}}{\frac{ϵn}{2}\frac{ϵn}{2}}=\frac{1+ϵ}{ϵ^2}>\frac{1}{ϵ^2}.$$

By Theorem 2, the number of queries is $`\mathrm{\Omega }(\sqrt{\frac{mm^{}}{ll^{}}})=\mathrm{\Omega }(1/ϵ)`$.

$`\mathrm{}`$

There are several other known lower bounds that also follow from Theorem 2. In particular, Theorem 2 implies $`\mathrm{\Omega }(N)`$ lower bounds for MAJORITY and PARITY of .

## 6 Inverting a permutation

### 6.1 Extension of Theorem 2

For some lower bounds (like inverting a permutation), we need a following extension of Theorem 2. This is our most general result.

###### Theorem 6

Let $`f(x_1,\mathrm{},x_N)`$ be a function of $`n`$ variables with values from some finite set 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`$.

Let $`l_{x,i}`$ be the number of $`yY`$ such that $`(x,y)R`$ and $`x_iy_i`$ and $`l_{y,i}`$ be the number of $`xX`$ such that $`(x,y)R`$ and $`x_iy_i`$. Let $`l_{max}`$ be the maximum of $`l_{x,i}l_{y,i}`$ over all $`(x,y)R`$ and $`i\{1,\mathrm{},N\}`$ such that $`x_iy_i`$. Then, any quantum algorithm computing $`f`$ uses $`\mathrm{\Omega }(\sqrt{\frac{mm^{}}{l_{max}}})`$ queries.

The parameters $`l`$ and $`l^{}`$ of Theorem 2 are just $`\mathrm{max}_{xX,i}l_{x,i}`$ and $`\mathrm{max}_{yY,i}l_{y,i}`$. It is easy to see that

$$\underset{(x,y)R,x_iy_i}{\mathrm{max}}l_{x,i}l_{y,i}\underset{x,i}{\mathrm{max}}l_{x,i}\underset{y,i}{\mathrm{max}}l_{y,i}.$$

Therefore, the lower bound given by Theorem 6 is always greater than or equal to the lower bound of Theorem 2. However, Theorem 6 gives a better bound if, for every $`(x,y)R`$ and $`i`$, at least one of $`l_{x,i}`$ or $`l_{y,i}`$ is less than its maximal value (which happens for inverting a permutation).

Also, Theorem 6 allows $`\{1,\mathrm{},N\}`$-valued variables instead of only $`\{0,1\}`$-valued in Theorem 2.

Proof: Similarly to Theorem 6, we consider the set of inputs $`S=XY`$ and the superposition

$$\frac{1}{\sqrt{2|X|}}\underset{xX}{}|x+\frac{1}{\sqrt{2|Y|}}\underset{yY}{}|y$$

over this set of inputs. Let $`S_k`$ be the sum of $`|(\rho _k)_{xy}|`$ over all $`x,y`$ such that $`(x,y)R`$. The theorem follows from

1. $`S_TS_0(12\sqrt{ϵ(1ϵ)})\sqrt{mm^{}}`$
2. $`S_{k1}S_k\sqrt{l_{max}}`$

The first part is shown in the same way as in the proof of Theorem 2. For the second part, express the state before the $`k^{\mathrm{th}}`$ query as

$$|\psi _{k1}=\underset{i,a,z,x}{}\alpha _{i,a,z,x}|i,a,z|x$$

where $`i`$ is the index of the input variable $`x_i`$ being queried, $`a`$ are $`\mathrm{log}N`$ bits for the answer, $`z`$ is the part of $`_A`$ that does not participate in the query (extra workbits) and $`x`$ is $`_I`$ part of the superposition. A query changes this to

$$|\psi _k=\underset{i,a,z,x}{}\alpha _{i,a,z,x}|i,ax_i,z|x=\underset{i,a,z,x}{}\alpha _{i,ax_i,z,x}|i,a,z|x.$$

Denote

$$|\psi _{i,a,z}=\underset{x}{}\alpha _{i,a,z,x}|x,\text{ }|\psi _{i,a,z}^{}=\underset{x}{}\alpha _{i,ax_i,z,x}|x.$$

$`\rho _{k1,i}=_{a,z}|\psi _{i,a,z}\psi _{i,a,z}|`$ and $`\rho _{k,i}=_{a,z}|\psi _{i,a,z}^{}\psi _{i,a,z}^{}|`$ are the parts of $`\rho _{k1}`$ and $`\rho _k`$ corresponding to querying $`i`$. We have $`\rho _{k1}=_{i=1}^n\rho _{k1,i}`$ and $`\rho _k=_{i=1}^n\rho _{k,i}`$.

Let $`S_{k,i}`$ be sum of absolute values of differences $`|(\rho _{k1,i})_{xy}(\rho _{k,i})_{xy}|`$ over all $`(x,y)R`$. Then, for every $`x,y`$,

$$|(\rho _{k1})_{xy}||(\rho _k)_{xy}||(\rho _{k1})_{xy}(\rho _k)_{xy}|=|\underset{i}{}(\rho _{k1,i})_{xy}\underset{i}{}(\rho _{k,i})_{xy}|\underset{i}{}|(\rho _{k1,i})_{xy}(\rho _{k,i})_{xy}|.$$

Therefore (by summing over all such $`x`$ and $`y`$), $`S_{k1}S_k_iS_{k,i}`$ and we can bound $`S_{k1}S_k`$ by bounding $`S_{k,i}`$.

Let $`x`$, $`y`$ be two inputs such that $`x_i=y_i`$. Then, it is easy to see that

$$(\rho _{k1,i})_{xy}=\underset{a,z}{}\alpha _{i,a,z,x}^{}\alpha _{i,a,z,y}=\underset{a,z}{}\alpha _{i,ax_i,z,x}^{}\alpha _{i,ay_i,z,y}=(\rho _{k,i})_{xy}.$$

Therefore, the only non-zero entries in $`S_{k,i}`$ are the entries corresponding to $`(x,y)R`$ with $`x_iy_i`$. The sum of their differences $`|(\rho _{k1,i})_{xy}(\rho _{k,i})_{xy}|`$ is at most the sum of absolute values of such entries in $`\rho _{k1,i}`$ plus the sum of absolute values of them in $`\rho _{k,i}`$. We bound these two sums.

First, any density matrix is semipositive definite. This implies that

$$|(\rho _{k1,i})_{xy}|\frac{1}{2}\left(\sqrt{\frac{l_{y,i}}{l_{x,i}}}|(\rho _{k1,i})_{xx}|+\sqrt{\frac{l_{x,i}}{l_{y,i}}}|(\rho _{k1,i})_{yy}|\right).$$

for any $`x`$ and $`y`$. Therefore,

$$\underset{x,y:(x,y)R}{}_{x_iy_i}|(\rho _{k1,i})_{xy}|\frac{1}{2}\underset{x,y:(x,y)R}{}_{x_iy_i}\sqrt{\frac{l_{y,i}}{l_{x,i}}}|(\rho _{k1,i})_{xx}|+\sqrt{\frac{l_{x,i}}{l_{y,i}}}|(\rho _{k1,i})_{yy}|=\frac{1}{2}\underset{xXY}{}l_{x,i}\sqrt{\frac{l_{y,i}}{l_{x,i}}}|(\rho _{k1,i})_{xx}|$$

$$=\frac{1}{2}\underset{xXY}{}\sqrt{l_{x,i}l_{y,i}}|(\rho _{k1,i})_{xx}|\frac{1}{2}\sqrt{l_{max}}\underset{xXY}{}|(\rho _{k1,i})_{xx}|=\frac{\sqrt{l_{max}}}{2}Tr\rho _{k1,i}.$$

The same argument shows that a similar sum is at most $`\frac{\sqrt{l_{max}}}{2}Tr\rho _{k,i}`$ for the matrix $`\rho _{k,i}`$. Therefore,

$$S_{k1}S_k\underset{i}{}S_{k,i}\underset{i}{}\frac{\sqrt{l_{max}}}{2}(Tr\rho _{k1,i}+Tr\rho _{k,i})=\frac{\sqrt{l_{max}}}{2}(Tr\rho _{k1}+Tr\rho _k)=\sqrt{l_{max}}.$$

This completes the proof. $`\mathrm{}`$

### 6.2 Application

We use Theorem 6 to prove a lower bound for inverting a permutation.

Problem: We are given $`x_1,\mathrm{},x_N\{1,\mathrm{},N\}`$ such that $`(x_1,\mathrm{},x_N)`$ is a permutation of $`\{1,\mathrm{},N\}`$. We have to find the $`i`$ such that $`x_i=1`$.

This problem was used in  to show $`NP^AcoNP^ABQP^A`$ for an oracle $`A`$. It is easy to see that it can be solved by Grover’s algorithm (search for $`i`$ with $`x_i=1`$). This takes $`O(\sqrt{N})`$ queries.

However, the $`\mathrm{\Omega }(\sqrt{N})`$ lower bound proof for search problem from  does not work for this problem.  showed a weaker $`\mathrm{\Omega }(\sqrt[3]{N})`$ bound with a more complicated proof.

###### Theorem 7

Any quantum query algorithm that inverts a permutation with probability $`1ϵ`$ uses $`\mathrm{\Omega }(\sqrt{N})`$ queries.

Proof: Let $`X`$ be the set of all permutations $`x`$ with $`x_i=1`$ for an even $`i`$ and $`Y`$ be the set of all permutations $`y`$ with $`y_i=1`$ for an odd $`i`$. $`(x,y)R`$ if $`x=(x_1,\mathrm{},x_N)`$, $`y=(y_1,\mathrm{},y_N)`$ and there are $`i,j`$, $`ij`$ such that $`x_i=y_j=1`$, $`x_j=y_i`$ and all other elements of $`x`$ and $`y`$ are the same.

For every $`xX`$, there are $`m=n/2`$ $`y`$ with $`(x,y)R`$. Similarly, for every $`yY`$, there are $`m^{}=n/2`$ $`x`$ such that $`(x,y)R`$.

Finally, if we take a pair $`(x,y)R`$ and a location $`i`$ such that $`x_iy_i`$, then one of $`x_i`$, $`y_i`$ is 1. We assume that $`x_i=1`$. (The other case is similar.) Then, there are $`n/2`$ $`y^{}`$ such that $`(x,y^{})R`$ and $`x_iy_i^{}`$. However, the only $`x^{}`$ such that $`(x^{},y)R`$ and $`x_i^{}y_i`$ is $`x^{}=x`$. (Any $`x^{}`$ such that $`(x^{},y)R`$ and $`x_i^{}y_i^{}`$ must also have $`x_j^{}y_j`$ where $`j`$ is the variable for which $`y_j=1`$ and $`x`$ is the only permutation that differs from $`y`$ only in these two places.)

Therefore, $`l_{x,i}=n/2`$, $`l_{y,i}=1`$ and $`l_{max}=n/2`$. By Theorem 6, this implies that any quantum algorithm needs $`\mathrm{\Omega }(\sqrt{\frac{n^2}{n}})=\mathrm{\Omega }(\sqrt{n})`$ queries. $`\mathrm{}`$

## 7 Relation to Grover’s proof

Grover presents a proof of the $`\mathrm{\Omega }(\sqrt{n})`$ lower bound on the search problem based on considering the sum of distances

$$\mathrm{\Delta }(t)=\underset{i,j\{1,\mathrm{},n\},ij}{}\varphi _i^t\varphi _0^t^2$$

where $`\varphi _i^t`$ is the state of the algorithm after $`t`$ queries on the input $`x_1=\mathrm{}=x_{i1}=0`$, $`x_i=1`$, $`x_{i+1}=\mathrm{}=x_n=1`$ and $`\varphi _0^t`$ is the state of the algorithm after $`t`$ queries on the input $`x_1=\mathrm{}=x_n=0`$.

Grover shows that, after $`t`$ queries, $`\mathrm{\Delta }(t)4t^2`$. If the algorithm outputs the correct answer with probability 1, the final vectors $`\varphi _1^t`$, $`\mathrm{}`$, $`\varphi _n^t`$ have to be orthogonal, implying that $`\mathrm{\Delta }(t)2N2\sqrt{N}`$ (cf. ). This implies that the number of queries must be $`\mathrm{\Omega }(\sqrt{N})`$.

A similar idea (bounding a certain sum of distances) has been also used by Shi to prove lower bounds on the number of quantum queries in terms of average sensitivity.

These “distance-based” ideas can be generalized to obtain another proof of our Theorems 2 and 6. Namely, for Theorem 2, one can take

$$\mathrm{\Delta }(t)=\underset{(x,y)R}{}\varphi _x^t\varphi _y^t^2$$

where $`\varphi _x^t`$, $`\varphi _y^t`$ are the states of the algorithm after $`t`$ steps on the inputs $`x`$ and $`y`$. Then,

$$\varphi _x^t\varphi _y^t^2=1\varphi _x^t|\varphi _y^t^2.$$

Let $`\rho _t`$ be the density matrix of $`_I`$ after $`t`$ steps. By writing out the expressions for $`\varphi _x^t|\varphi _y^t`$ and $`(\rho _t)_{xy}`$, we can see that

$$(\rho _t)_{xy}=\frac{1}{4|X||Y|}\varphi _x^t|\varphi _y^t.$$

This shows that the two quantities (the sum of entries in the density matrix and the sum of distances) are quite similar. Indeed, we can give proofs for Theorems 2 and 6 in terms of distances and their sums $`\mathrm{\Delta }(t)`$. (Namely, $`\mathrm{\Delta }(0)=0`$ before the first query, $`\mathrm{\Delta }(T)`$ should be large if the algorithm solves the problem with $`T`$ queries and we can bound the difference $`\mathrm{\Delta }(t)\mathrm{\Delta }(t1)`$. This gives the same bounds as bounding the entries of density matrices.)

Thus, Theorems 2 and 6 have two proofs that are quite similar algebraically but come from two completely different sources: running a quantum algorithm with a superposition of inputs (our “quantum adversary”) and looking at it from a geometric viewpoint (sum of distances).

The “quantum adversary” approach may be more general because one could bound other quantities (besides the sum of entries in the density matrix) which have no simple geometric interpretation.

## 8 Conclusion and open problems

We introduced a new method for proving lower bounds on quantum algorithms and used it to prove tight (up to a multiplicative or logarithmic factor) lower bounds on Grover’s search and 3 other related problems. Two of these bounds (Grover’s search and distinguishing between an input with 1/2 of values equal to 1 and $`1/2+ϵ`$ values equal to 1) were known before. For two other problems (inverting a permutation and AND of ORs), only weaker bounds were known. One advantage of our method is that it allows to prove all 4 bounds in a similar way. (Previous methods were quite different for different problems.)

Some open problems:

1. Collision problem.

We are given a function $`f:\{1,\mathrm{},n\}\{1,\mathrm{},n/2\}`$ and have to find $`i`$, $`j`$ such that $`f(i)=f(j)`$. Classically, this can be done by querying $`f(x)`$ for $`O(\sqrt{n})`$ random values of $`x`$ and it is easy to see that this is optimal. There is a quantum algorithm that solves this problem with $`O(\sqrt[3]{n})`$ queries. However, there is no quantum lower bound at all for this problem (except the trivial bound of $`\mathrm{\Omega }(1)`$).

The collision problem is an abstraction for collision-resistant hash functions. If it can be solved with $`O(\mathrm{log}n)`$ queries, there no hash function is collision-resistant against quantum algorithms.

The exact argument that we gave in this paper (with bounding a subset of the entries in the density matrix) does not carry over to the collision problem. However, it may be possible to use our idea of running the algorithm with a superposition of oracles together with some other way of measuring the entanglement between the algorithm and the oracle.
2. Simpler/better lower bound for binary search.

It may be possible to simplify other lower bounds proven previously by different methods. In some cases, it is quite easy to reprove the result by our method (like Theorem 5) but there are two cases in which we could not do that. The first is the bound of  on the number of queries needed to achieve very small probability of error in database search problem. The second is the lower bound on the ordered search. It seems unlikely that our technique can be useful in the first case but there is a chance that some variant of our idea may work for ordered search (achieving both simpler proof and better constant under big-$`\mathrm{\Omega }`$).
3. Communication complexity of disjointness.

Quantum communication complexity is often related to query complexity. Can one use our method (either “quantum adversary” or distance-based formulation) to prove lower bounds on quantum communication complexity?

A particularly interesting open problem in quantum communication complexity is set disjointness. The classical (both deterministic and probabilistic) communication complexity of set disjointness is $`\mathrm{\Omega }(n)`$. There is a quantum protocol (based on Grover’s search algorithm) that computes set disjointness with an $`O(\sqrt{n}\mathrm{log}n)`$ communication but the best lower bound is only $`\mathrm{\Omega }(\mathrm{log}n)`$.

Acknowledgements. I would like to thank Dorit Aharonov, Daniel Gottesman, Ashwin Nayak, Umesh Vazirani and Ronald de Wolf for useful comments.