text:
# Long-range order and low-energy spectrum of diluted 2D quantum AF

\[

## Abstract

The problem of diluted two-dimensional (2D) quantum antiferromagnet (AF) on a square lattice is studied using spin-wave theory. The influence of impurities on static and dynamic properties is investigated and a good agreement with experiments and Monte Carlo (MC) data is found. The hydrodynamic description of spin waves breaks down at characteristic wavelengths $`\mathrm{\Lambda }\mathrm{exp}(\frac{const}{x})`$, $`x`$ being an impurity concentration, while the order parameter is free from anomalies. We argue that this dichotomy originates from strong scattering of the low-energy excitations in 2D.

\]

The interest in magnetic properties of high-Tc compounds has been a major driving force of intensive studies of low-dimensional magnetic systems during the last decade . One of such systems is the La2Cu1-xZn(Mg)xO4, a parental compound doped with static vacancies, which shows greater stability of the AF order against doping than its mobile hole doped counterpart La2-xSrxCuO4 . It represents a fine example of a diluted 2D quantum $`S=1/2`$ AF whose properties are the subject of this study. The problem of diluted spin systems has attracted much attention in the past  and their physics is well understood. The general understanding is that the low-energy excitations of these systems are weakly damped spin waves which belong to the infinite cluster  and are well defined up to the percolation threshold. In this work we show that quantum effects and low dimensionality prevent the excitation spectrum to be defined in these hydrodynamic terms  at arbitrarily small doping and lead to a paradoxical situation where the long-range order is preserved but the long-wavelength spectrum is not ballistic.

The site-diluted AF on a square lattice is described by:

$`=J{\displaystyle \underset{ij}{}}p_ip_j𝐒_i𝐒_j,`$ (1)
with $`p_i=1(0)`$ for the magnetic (non-magnetic) site. The pure system at long wavelengths can be described by the nonlinear $`\sigma `$-model . Its applicability in the presence of a quenched disorder has been questioned  since impurities destroy the Lorentz invariance of the model. Some generalizations of the $`\sigma `$-model have nevertheless been proposed with parameters modified according to MC data  and the classical percolation theory .

In this work we study the problem of disorder using the $`t`$-matrix approach combined with a configurational average over the random positions of impurities. It also leads to description of the system in terms of an effective medium with renormalized parameters. In an earlier work Harris and Kirkpatrik  have shown that in 2D a non-hydrodynamic term appears in the spin-wave self-energy which explicitly violates Lorentz invariance: $`\mathrm{\Sigma }_𝐤(\omega )xk(\mathrm{ln}|\omega |i\pi /2)`$. A recent study by Wan et al.  has confirmed this result. One can show that the spectrum is overdamped at wavelengths $`\mathrm{\Lambda }\mathrm{exp}(\pi /4x)`$ which implies the existence of a new lengthscale in the system. The absence of a well-defined long-wavelength mode also suggests that the true order should be unstable under an infinitesimal impurity doping, or that $`d=2`$ is the upper critical dimension for this problem.

In this work we study the effect of impurities on the spectrum, staggered magnetization, $`M(x)`$, and Néel temperature, $`T_N(x)`$, to clarify the problem of stability of a (quasi-)2D AF order. We show that neither $`M(x)`$ nor $`T_N(x)`$ possesses anomalous contributions which would imply an instability. Thus, we have a somewhat paradoxical situation when the spectrum is ill-defined while the order parameter is not affected. Such a dichotomy comes from the strong influence of disorder in the low-energy excitations in 2D. The averaging procedure, which effectively restores translational invariance, fails to recover the long-wavelength excitation spectrum of this effective medium . The low-frequency modes do exist in some form but they cannot be classified in terms of an effective wave-vector and thus the long-wavelength propagation is entirely diffusive. This scheme implies an existence of a disorder-induced energy scale which restricts the applicability of the continuum approach.

We start with the Hamiltonian (1) in the spin-wave approximation $`=_0+_{imp}^A+_{imp}^B`$:

$`_04SJ{\displaystyle \underset{𝐤}{}}\omega _𝐤(\alpha _𝐤^{}\alpha _𝐤+\beta _𝐤^{}\beta _𝐤),`$ (2)
$`_{imp}^A4SJ{\displaystyle \underset{lA,𝐤,𝐤^{}}{}}e^{i(𝐤𝐤^{})𝐑_l}[V_{A,\mathrm{𝐤𝐤}^{}}^{\alpha \alpha }\alpha _𝐤^{}\alpha _𝐤^{}`$ (3)
$`+V_{A,\mathrm{𝐤𝐤}^{}}^{\beta \beta }\beta _𝐤^{}\beta _𝐤^{}+V_{A,\mathrm{𝐤𝐤}^{}}^{\alpha \beta }(\alpha _𝐤^{}\beta _𝐤^{}^{}+\text{H.c.})],`$ (4)
where the quadratic part of the pure host Hamiltonian $`_0`$ is diagonalized using Bogolyubov transformation: $`S_{𝐤,A}^{}/\sqrt{2S}a_𝐤=u_𝐤\alpha _𝐤+v_𝐤\beta _𝐤^{}`$, $`S_{𝐤,B}^{}/\sqrt{2S}b_𝐤^{}=u_𝐤\beta _𝐤^{}+v_𝐤\alpha _𝐤`$, $`A`$ and $`B`$ denote the sublattices, with $`u_𝐤^2v_𝐤^2=1`$, $`2u_𝐤v_𝐤=\gamma _𝐤/\omega _𝐤`$, $`\gamma _𝐤=(\mathrm{cos}(k_x)+\mathrm{cos}(k_y))/2`$, and bare spin-wave frequency $`\omega _𝐤=\sqrt{1\gamma _𝐤^2}`$. All momenta belong to the magnetic Brillouin zone $`k_x+k_y\pi `$. $`_{imp}^B=_{imp}^A(AB)`$, interactions are given by $`V_A^{\alpha \alpha }=V_B^{\beta \beta }=u_1u_2+\gamma _{12}v_1v_2+\gamma _1v_1u_2+\gamma _2v_2u_1`$, $`V_A^{\beta \beta }=V_B^{\alpha \alpha }=v_1v_2+\gamma _{12}u_1u_2+\gamma _1u_1v_2+\gamma _2u_2v_1`$, and $`V_{A,1,2}^{\alpha \beta }=V_{B,2,1}^{\alpha \beta }=u_1v_2+\gamma _{12}v_1u_2+\gamma _1v_1v_2+\gamma _2u_2u_1`$, $`l`$ runs over the impurity sites. As a first step we solve the scattering problem for the single impurity. Since the impurity potential is short-ranged one uses the $`t`$-matrix approach. The advantage of this method is that the single impurity problem can be solved exactly (within the spin-wave approximation) . Therefore, the results of this approach become exact in the dilute limit $`x0`$.

In our case the square lattice site-defect scatters only in $`s`$-, $`p_x`$-, $`p_y`$-, and $`d`$-symmetric channels and one needs to solve the $`t`$-matrix for each harmonic. The $`t`$-matrix equations are:

$`\mathrm{\Gamma }_{A,i}^{\alpha \alpha }=V_{A,i}^{\alpha \alpha }V_{A,i}^{\alpha \alpha }G_\alpha ^0\mathrm{\Gamma }_{A,i}^{\alpha \alpha }V_{A,i}^{\alpha \beta }G_\beta ^0\mathrm{\Gamma }_{A,i}^{\alpha \beta },`$ (5)
$`\mathrm{\Gamma }_{A,i}^{\alpha \beta }=V_{A,i}^{\alpha \beta }V_{A,i}^{\beta \beta }G_\beta ^0\mathrm{\Gamma }_{A,i}^{\alpha \beta }V_{A,i}^{\alpha \alpha }G_\alpha ^0\mathrm{\Gamma }_{A,i}^{\alpha \alpha },`$ (6)
where $`V_i`$’s are the $`i=s,p_x,p_y,d`$ components of V’s (3). We suppress $`𝐤`$ and $`\omega `$ in vertex functions $`\mathrm{\Gamma }_i(𝐤,𝐤^{},\omega )`$, bare Green’s functions $`G_\alpha ^0(𝐤,\omega )=G_\beta ^0(𝐤,\omega )=\{\omega \omega _𝐤+i0\}^1`$, and interactions $`V_{\mathrm{𝐤𝐤}^{}}`$. Products $`VG\mathrm{\Gamma }`$ involve summation over the internal momenta, all energies are in units of $`4SJ`$. An equivalent set of equations gives the vertices $`\mathrm{\Gamma }_{A,i}^{\beta \beta }`$. For the impurity in $`B`$ sublattice $`\mathrm{\Gamma }_{B,i}\mathrm{\Gamma }_{A,i}(\alpha \beta )`$. Since the impurity potential in each partial wave is separable: $`V_{A,s}^{\alpha \alpha }=u_𝐤\omega _𝐤u_𝐤^{}\omega _𝐤^{}`$, $`V_{A,p_\sigma }^{\alpha \alpha }=\varphi _{k_\sigma }v_𝐤\varphi _{k_\sigma ^{}}v_𝐤^{}/2`$, $`V_{A,d}^{\alpha \alpha }=\gamma _𝐤^{}v_𝐤\gamma _𝐤^{}^{}v_𝐤^{}`$, $`V_{A,i}^{\beta \beta }=V_{A,i}^{\alpha \alpha }(uv)`$, $`V_{A,s}^{\alpha \beta }=u_𝐤\omega _𝐤v_𝐤^{}\omega _𝐤^{}`$, $`V_{A,p_\sigma }^{\alpha \beta }=\varphi _{k_\sigma }v_𝐤\varphi _{k_\sigma ^{}}u_𝐤^{}/2`$, $`V_{A,d}^{\alpha \beta }=\gamma _𝐤^{}v_𝐤\gamma _𝐤^{}^{}u_𝐤^{}`$, where $`\varphi _{k_\sigma }=\mathrm{sin}(k_\sigma )`$, $`\gamma _𝐤^{}=(\mathrm{cos}(k_x)\mathrm{cos}(k_y))/2`$, Eqs. (5) can be readily solved: $`\mathrm{\Gamma }_{A,i}^{\sigma \sigma ^{}}(𝐤,𝐤^{},\omega )=V_{A,i}^{\sigma \sigma ^{}}(𝐤,𝐤^{})\stackrel{~}{\mathrm{\Gamma }}_i(\omega )`$, where

$`\stackrel{~}{\mathrm{\Gamma }}_s(\omega )=1/\omega (1+\omega )\rho (\omega )/[1\omega (1+\omega )\rho (\omega )],`$ (9)
$`\stackrel{~}{\mathrm{\Gamma }}_p(\omega )=2/[1+\omega +(1\omega )(\omega ^2\rho (\omega )\rho _d(\omega ))],`$
$`\stackrel{~}{\mathrm{\Gamma }}_d(\omega )=1/[1+(1\omega )\rho _d(\omega )],`$
with $`\rho =_𝐩1/(\omega ^2\omega _𝐩^2)`$ and $`\rho _d=_𝐩(\gamma _𝐩^{})^2/(\omega ^2\omega _𝐩^2)`$, which can be expressed through the complete elliptic integrals . For the impurity in $`B`$ sublattice $`\mathrm{\Gamma }_{B,i}^{\sigma \sigma ^{}}=V_{B,i}^{\sigma \sigma ^{}}\stackrel{~}{\mathrm{\Gamma }}_i(\omega )`$. The $`s`$-wave scattering (9) reveals a zero-frequency mode which originates from the oscillations of the fictitious degrees of freedom at the impurity site. Roughly speaking, since in the spin-wave approximation spins are quantized through bosons even if $`S^{}`$ at the impurity site is set to zero there is still $`a_0^{}a_0`$ left in $`S_0^z`$ (for discussion see Ref. ). This gives rise to the unphysical zero-frequency mode which has to be projected out. We do so by introducing magnetic fields at the impurity sites (similar to Refs. ) $`\mathrm{\Delta }=H_z_la_i^{}a_i`$. Within this approach after straightforward algebra  in the limit $`H_z\mathrm{}`$ one obtains: $`\mathrm{\Gamma }_{A,s}^{\sigma \sigma ^{}}(𝐤,𝐤^{},\omega )=V_{A,s}^{\sigma \sigma ^{}}(𝐤,𝐤^{})\stackrel{~}{\mathrm{\Gamma }}_s(\omega )+\mathrm{\Delta }\mathrm{\Gamma }_{A,s}^{\sigma \sigma ^{}}(𝐤,𝐤^{},\omega )`$,

$`\stackrel{~}{\mathrm{\Gamma }}_s(\omega )=(1+\omega )\rho (\omega )/[1\omega (1+\omega )\rho (\omega )],`$ (10)
which is free from the zero-frequency pole. $`\mathrm{\Delta }\mathrm{\Gamma }_{A,s}^{\alpha \alpha }=u_𝐤u_𝐤^{}[\omega _𝐤+\omega _𝐤^{}\omega ]`$, $`\mathrm{\Delta }\mathrm{\Gamma }_{A,s}^{\beta \beta }=v_𝐤v_𝐤^{}[\omega _𝐤+\omega _𝐤^{}+\omega ]`$, $`\mathrm{\Delta }\mathrm{\Gamma }_{A,s}^{\alpha \beta }=u_𝐤v_𝐤^{}[\omega _𝐤\omega _𝐤^{}+\omega ]`$. $`\mathrm{\Gamma }_B=\mathrm{\Gamma }_A(\omega )\{\alpha \beta \}`$ as before, $`p`$ and $`d`$ waves are not affected by the projection.

The next step is the averaging procedure which restores translational invariance. Assuming random distribution of impurities one readily transforms scattering vertices into the spin-wave self-energies: $`\mathrm{\Sigma }_𝐤^{\sigma \sigma ^{}}(\omega )=_i\mathrm{\Sigma }_{i,𝐤}^{\sigma \sigma ^{}}(\omega )`$, with $`\mathrm{\Sigma }_{i,𝐤}^{\sigma \sigma ^{}}(\omega )=x\delta _{𝐤𝐤^{}}[\mathrm{\Gamma }_{A,i}^{\sigma \sigma ^{}}(𝐤,𝐤^{},\omega )+\mathrm{\Gamma }_{B,i}^{\sigma \sigma ^{}}(𝐤,𝐤^{},\omega )]`$

$`\mathrm{\Sigma }_{s,𝐤}^{\alpha \alpha }(\omega )/x=\omega _𝐤^2\left[u_𝐤^2\stackrel{~}{\mathrm{\Gamma }}_s(\omega )+v_𝐤^2\stackrel{~}{\mathrm{\Gamma }}_s(\omega )\right]+2\omega _𝐤\omega ,`$ (11)
$`\mathrm{\Sigma }_{p(d),𝐤}^{\alpha \alpha }(\omega )=xA_𝐤^{p(d)}\left[v_𝐤^2\stackrel{~}{\mathrm{\Gamma }}_{p(d)}(\omega )+u_𝐤^2\stackrel{~}{\mathrm{\Gamma }}_{p(d)}(\omega )\right],`$ (12)
$`\mathrm{\Sigma }_{i,𝐤}^{\alpha \beta }(\omega )=xB_𝐤^i\left[\stackrel{~}{\mathrm{\Gamma }}_i(\omega )+\stackrel{~}{\mathrm{\Gamma }}_i(\omega )\right],\mathrm{\Sigma }_{i,𝐤}^{\beta \beta }(\omega )=\mathrm{\Sigma }_{i,𝐤}^{\alpha \alpha }(\omega ),`$ (13)
where $`A_𝐤^p=\omega _𝐤^2+(\gamma _𝐤^{})^2`$, $`A_𝐤^d=(\gamma _𝐤^{})^2`$, $`B_𝐤^s=\omega _𝐤^2u_𝐤v_𝐤`$, $`B_𝐤^p=A_𝐤^pu_𝐤v_𝐤`$, $`B_𝐤^d=A_𝐤^du_𝐤v_𝐤`$. It is interesting that “on shell” ($`\omega =\omega _𝐤`$) Eqs. (9) and (10) yield identical $`\mathrm{\Sigma }_{s,𝐤}(\omega _𝐤)`$.

At low energies $`\omega ,\omega _𝐤0`$ self-energies are given by:

$`\mathrm{\Sigma }_𝐤^{\alpha \alpha }(\omega )x\omega _𝐤\left[\rho (\omega )+2\pi /2\right]x\omega +𝒪(\omega _𝐤\omega ^2\rho ^3),`$ (16)
$`\mathrm{\Sigma }_𝐤^{\alpha \beta }(\omega )x\omega _𝐤\left[\rho (\omega )+\pi /2\right]+𝒪(\omega _𝐤\omega ^2\rho ^3),`$
$`\text{with}\rho (\omega )(2/\pi )\mathrm{ln}(|\omega |/4)i,`$
which includes contributions from $`s`$\- and $`p`$-wave scattering, $`\mathrm{\Sigma }_d𝒪(\omega _𝐤^3)`$. One can see that besides the “normal” softening of the long-wavelength mode and the damping proportional to the higher power of $`k`$ ($`k^3`$) one acquires a non-linear dispersion term with the damping $`\stackrel{~}{\gamma }_𝐤/\omega _𝐤x`$ having only parametric smallness with respect to the bare spectrum. Renormalization of the real part of the spectrum is dominated by the $`\mathrm{ln}(|\omega |)`$ term at low frequencies. A naive “on-shell” pole equation $`\stackrel{~}{\omega }_𝐤^{}=\omega _𝐤+\mathrm{}\mathrm{\Sigma }_𝐤^{\alpha \alpha }(\omega _𝐤)`$ suggests a vanishing of the spectrum  and an instability of the ground state. Consideration of the diagrammatic series for the Green’s functions shown in Fig. 1 with self-energies defined in Eq. (11) and $`G_𝐤^{11}(\omega )=\{\omega \omega _𝐤\mathrm{\Sigma }_𝐤^{\alpha \alpha }(\omega )\}^1`$ gives:

$`G_𝐤^{\alpha \alpha }(\omega )={\displaystyle \frac{G_𝐤^{11}(\omega )^1}{[G_𝐤^{11}(\omega )G_𝐤^{11}(\omega )]^1(\mathrm{\Sigma }_𝐤^{\alpha \beta }(\omega ))^2}},`$ (17)
$`G_𝐤^{\alpha \beta }(\omega )={\displaystyle \frac{\mathrm{\Sigma }_𝐤^{\alpha \beta }(\omega )}{[G_𝐤^{11}(\omega )G_𝐤^{11}(\omega )]^1(\mathrm{\Sigma }_𝐤^{\alpha \beta }(\omega ))^2}}.`$ (18)
At $`k\omega _0\mathrm{exp}(\pi /4x)`$ spectral function reveals damped quasiparticle peak at $`\omega k`$ plus some structure at low frequencies $`\omega \omega _0`$. At low $`k\omega _0`$ the quasiparticle peak merges with this structure and disappears. The spectrum is completely overdamped at $`k\omega _0`$. Beyond this scale no hydrodynamic description is possible.

A potential concern is whether an anomaly in Eq. (16) can be fixed by the higher order terms. General discussion of this problem in terms of the susceptibility (Ref.) concluded that the divergency should be unrelated to the expansion in $`x`$. One can also show that the summation of the Green’s function series (17) and dressing of the inner lines in self-energies using self-consistent equation on $`\rho (\omega )`$ and $`G^{\sigma \sigma }`$ actually enhance the anomaly.

In a complementary problem of a quasi-2D AF a small inter-plane coupling $`\alpha =J_{}/J`$ cuts off the log-singularity: $`\rho _{3D}(\omega )(1/\pi )\mathrm{ln}(\alpha /32)+i𝒪(\omega )`$ at $`\omega <\sqrt{2\alpha }`$. Therefore a “safe” range of concentrations $`x<x^{}\mathrm{ln}^1(1/\alpha )`$ can be found where the long-wavelength quasiparticles are still well defined deep in the 3D region of the $`𝐤`$-space ($`\mathrm{\Lambda }^1\sqrt{\alpha }`$). However, one should be able to observe a nonlinearity of the spectrum and an abnormal damping of the spin waves in the 2D long-wavelength region ($`\sqrt{\alpha }<\mathrm{\Lambda }^11`$) similar to the quasi-1D problem . For the real materials $`\alpha 10^4`$ giving $`x^{}20\%`$. Above the concentration $`x^{}`$ all the low-energy excitations are incoherent because the 2D disorder-induced scale $`\omega _0^1`$ is shorter than the 3D length $`1/\sqrt{\alpha }`$ so the spin waves lose coherence before they can propagate in 3D. The same consideration applies to the case of small anisotropies introducing gaps in the spectrum with a modified $`\alpha =\alpha _{eff}`$ accumulating the total effect of the gaps and 3D coupling. It should be noted that the incoherence comes from the averaging procedure which converts the dissipation of momentum into the dissipation of the energy. Therefore, the overdamped excitations should be understood as diffusive. It is interesting that it requires 2D and “strong” disorder to restrict the number of Euclidean paths for spin waves and to break down the description of the problem in terms of an effective medium.

Now we proceed with quantities whose expansion in $`x`$ can be shown to be reliable. Staggered magnetization at the magnetic site $`M(x)=M_0\delta M(x)`$, $`M_0=S\delta \lambda `$,

$`\delta M(x)={\displaystyle \underset{𝐤}{}}[\alpha _𝐤^{}\alpha _𝐤\gamma _𝐤\alpha _𝐤^{}\beta _𝐤^{}]/\omega _𝐤=`$ (19)
$`{\displaystyle \underset{𝐤}{}}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{n(\omega )\text{d}\omega }{\pi \omega _𝐤}}\text{Im}[G_{R,𝐤}^{\alpha \alpha }(\omega )\gamma _𝐤G_{R,𝐤}^{\alpha \beta }(\omega )],`$ (20)
where $`\delta \lambda =_𝐤v_𝐤^20.1966`$ is from zero-point fluctuations, $`n(\omega )=[e^{\omega /T}1]^1`$ is the Bose occupation number, index $`R`$ denotes retarded. At $`T=0`$ $`n(\omega )=\theta (\omega )`$ and integrals in (19) with $`G^{\sigma \sigma ^{}}`$ from (17) can be taken numerically. It can be shown  that the expansion in $`x`$ for $`G^{\sigma \sigma ^{}}`$ can be performed before the integration $`G^{\alpha \alpha }G_\alpha ^0+G_\alpha ^0\mathrm{\Sigma }^{\alpha \alpha }G_\alpha ^0`$, $`G^{\alpha \beta }G_\beta ^0\mathrm{\Sigma }^{\alpha \alpha }G_\alpha ^0`$ and that all integrals for the linear in $`x`$ term are convergent giving $`\delta M(x)=0.209(8)x+𝒪(x^2)`$. For $`S=1/2`$ $`M(x)/M_010.691(5)x`$. This linear slope together with the results of calculations using $`G^{\sigma \sigma ^{}}`$ from Eq. (17), MC  and NMR data  are shown in Fig. 2. Note that Fig. 2 and Eq. (19) are showing the reduction of the magnetic moment by the quantum fluctuations induced by impurities. In order to extract the same quantity from the MC data , which are averaged over all sites, one needs to deduct a probability of finding a spin-occupied site from them. One can see a very good agreement of our results with numerical data up to high concentrations. The oxidation of the crystals can be the reason of a faster decrease of $`M(x)`$ in NMR data. The absolute value of $`\delta M(x)`$ is independent of $`S`$ in the linear spin-wave approximation similar to the quantum reduction of $`S`$ by $`\delta \lambda `$. We plot $`\delta M(x)`$ in Fig.2 (right axes) in order to emphasize the agreement with the MC data for $`S=1/2`$ and $`S=1`$, which show only weak $`S`$-dependence.

The quantity which one would expect to exhibit a different behavior is $`T_N`$ for quasi-2D problem. The thermal corrections to the staggered magnetization $`\delta M^TT\mathrm{ln}(T/\omega )|_{\omega =\sqrt{\alpha }}`$ yield a finite $`T_N\mathrm{ln}(1/\alpha )^1`$ for a pure system. Since the original spectrum is bent from the linear form this should manifest itself in the finite temperature part of Eq. (19) as a stronger divergency. One indeed finds such contributions in Eq.(19) ($`xT\mathrm{ln}^2|\omega |`$) already in a perturbative limit ($`x\mathrm{ln}|\omega |1`$). However, these anomalous terms from diagonal and off-diagonal parts cancel each other. From the mean-field equation $`M^{T_N}(x)=0`$ after some algebra one obtains (at $`\alpha 0`$): $`T_N(x)/T_N(0)1xA`$ with $`A=\pi 2/\pi +0.209(8)/M_0`$. For $`S=1/2`$, $`A=3.196(5)`$ , which fits very well experimental data , see Fig.3.

Thus the order is preserved up to a high $`x`$ value  while the long-wavelength spectrum is not well defined at any $`x`$. Experimentally one would need to probe directly the spin-wave spectrum close to the AF ordering vector and look for anomalous broadening and nonlinearity. The actual overdamped part of the spectrum is associated with a small energy scale (and small momenta, e.g. at $`x=0.2`$, $`k_00.01\pi /a`$) and it is not clear if it is observable within the range of doping where conclusions of this work are reliable. The observed deviation from the simple exponential behavior of the correlation length $`\xi (T,x)`$ v.s. $`1/T`$  might be related to the character of the low-energy spectrum we discuss.

Another aspect relates our problem to the other problems of disorder in 2D. We observe that some weight from every mode is transferred to the low energies $`\omega \omega _0`$ which can be understood as some sort of localization, though the localization criteria for this problem is unclear. Altogether these low-energy states result in a peak in the density of states. From $`x`$-expanded form of the Green’s function $`G^{\alpha \alpha }G_\alpha ^0+G_\alpha ^0\mathrm{\Sigma }^{\alpha \alpha }G_\alpha ^0`$ one readily gets $`N(\omega )=2\omega /\pi +xC+𝒪(x\omega \mathrm{ln}|\omega |)`$, which implies a finite density of states at $`\omega =0`$. With $`G^{\alpha \alpha }`$ from Eq. (17) one obtains $`N(\omega )2\omega /\pi +xC/[(1+4x\mathrm{ln}|\omega |/\pi )^2+4x^2]`$ which is zero strictly at $`\omega =0`$ but has a sharp peak $`1/x`$ at $`\omega =\omega _0`$. This is very close to the dispute over $`N(\omega )`$ for the certain types of disorder in 2D systems with linear excitation spectrum . Note that in our case there is no “weak” limit for disorder since the perturbation ($`JSz`$) is of the same strength as the pure coupling .

In conclusion, we have provided evidence for the stability of the long-range order in the 2D and quasi-2D AF doped with static vacancies. At the same time the long-wavelength excitation spectrum is shown to be diffusive for any value of doping, restricting a hydrodynamic approach to the problem from low energies.

We would like to acknowledge enlightening discussions with A. Abanov, Ar. Abanov, A. Balatsky, A. Chubukov, C. Chamon, M. Greven, A. B. Harris, O. Vajk, L. Pryadko, A. Sandvik, O. Starykh, O. Sushkov, and M. Zhitomirsky. We are indebted to M. Greven and O. Vajk for sharing their results prior to publication and to S. Todo for providing us with the MC data. The support is provided in part by a CULAR research grant under the auspices of the US Department of Energy.


format: text

text:
# Untitled Document

ON THE CALCULATION OF GROUP CHARACTERS

M. Gungormez

Dept. Physics, Fac. Science, Istanbul Tech. Univ.

80626, Maslak, Istanbul, Turkey

e-mail: gungorm@itu.edu.tr

H. R. Karadayi

Dept. Physics, Fac. Science, Istanbul Tech. Univ.

80626, Maslak, Istanbul, Turkey

e-mail: karadayi@itu.edu.tr

and

Dept. Physics, Fac. Science, Istanbul Kultur University

34156, Atakoy, Istanbul, Turkey

Abstract

It is known that characters of irreducible representations of finite Lie algebras can be obtained by Weyl character formula including Weyl group summations which make actual calculations almost impossible except for a few Lie algebras of lower rank. By starting from Weyl character formula, we show that these characters can be re-expressed without referring to Weyl group summations. Some useful technical points are given in detail in the instructive example of $`G_2`$ Lie algebra.

I. INTRODUCTION

It is known that the character formula of Weyl  gives us a direct way to calculate the character of irreducible representations of finite Lie algebras. For this, let $`G_r`$ be a Lie algebra of rank r, $`W(G_r)`$ its Weyl group, $`\alpha _i`$’s and $`\lambda _i`$’s be, respectively, its simple roots and fundamental dominant weights. The notation here and in the following sections will be as in our previous work . For further reading, we refer to the beautiful book of Humphreys . A dominant weight $`\mathrm{\Lambda }^+`$ is expressed in the form

$$\mathrm{\Lambda }^+=\underset{i=1}{\overset{r}{}}s_i\lambda _i$$
$`(I.1)`$
where $`s_i`$’s are some positive integers (including zero). An irreducible representation $`V(\mathrm{\Lambda }^+)`$ can then be attributed to $`\mathrm{\Lambda }^+`$ . The character $`Ch(\mathrm{\Lambda }^+)`$ of $`V(\mathrm{\Lambda }^+)`$ is defined by

$$Ch(\mathrm{\Lambda }^+)\underset{\lambda ^+}{}\underset{\mu W(\lambda ^+)}{}m_{\mathrm{\Lambda }^+}(\mu )e^\mu $$
$`(I.2)`$
where $`m_{\mathrm{\Lambda }^+}(\mu )`$ ’s are multiplicities which count the number of times a weight $`\mu `$ is repeated for $`V(\mathrm{\Lambda }^+)`$. The first sum here is over $`\mathrm{\Lambda }^+`$ and all of its sub-dominant weights $`\lambda ^+`$’s while the second sum is over the elements of their Weyl orbits $`W(\lambda ^+)`$’s. Formal exponentials are taken just as in the book of Kac  and in (I.2) we extend the concept for any weight $`\mu `$, in the form $`e^\mu `$. Note here that multiplicities are invariant under Weyl group actions and hence it is sufficient to determine only $`m_{\mathrm{\Lambda }^+}(\lambda ^+)`$ for the whole Weyl orbit $`W(\lambda ^+)`$.

An equivalent form of (I.2) can be given by

$$Ch(\mathrm{\Lambda }^+)=\frac{A(\rho +\mathrm{\Lambda }^+)}{A(\rho )}$$
$`(I.3)`$
where $`\rho `$ is the Weyl vector of $`G_r`$. (I.3) is the celebrated Weyl Character Formula which gives us the possibility to calculate characters in the most direct and efficient way. The central objects here are $`A(\rho +\mathrm{\Lambda }^+)`$’s which include a sum over the whole Weyl group:

$$A(\rho +\mathrm{\Lambda }^+)\underset{\sigma W(G_r)}{}ϵ(\sigma )e^{\sigma (\rho +\mathrm{\Lambda }^+)}.$$
$`(I.4)`$
In (I.4), $`\sigma `$ denotes an element of Weyl group,i.e. a Weyl reflection, and $`ϵ(\sigma )`$ is the corresponding signature with values either +1 or -1.

The structure of Weyl groups is completely known for finite Lie algebras in principle. In practice, however, the problem is not so trivial, especially for Lie algebras of some higher rank. The order of $`E_8`$ Weyl group is, for instance, 696729600 and any application of Weyl character formula needs for $`E_8`$ an explicit calculation of a sum over 696729600 Weyl reflections. Our main point here is to overcome this difficulty in an essential manner.

For an actual application of (I.3), an important notice is the specialization of formal exponentials $`e^\mu `$ as is called in the book of Kac . In its most general form, we consider here the specialization

$$e^{\alpha _i}u_i,i=1,2,\mathrm{},r.$$
$`(I.5)`$
which allows us to obtain $`A(\rho )`$ in the form of

$$A(\rho )=P(u_1,u_2,\mathrm{},u_r)$$
$`(I.6)`$
where $`P(u_1,u_2,\mathrm{},u_r)`$ is a polynomial in indeterminates $`u_i`$’s. We also have

$$A(\rho +\mathrm{\Lambda }^+)=P(u_1,u_2,\mathrm{},u_r;s_1,s_2,\mathrm{},s_r)$$
$`(I.7)`$
where $`P(u_1,u_2,\mathrm{},u_r;s_1,s_2,\mathrm{},s_r)`$ is another polynomial of indeterminates $`u_i`$’s and also parameters $`s_i`$’s defined in (I.1). The Weyl formula (I.3) then says that polynomial (I.7) always factorizes on polynomial (I.6) leaving us with another polynomial $`R(u_1,u_2,\mathrm{},u_r;s_1,s_2,\mathrm{},s_r)`$ which is nothing but the character polynomial of $`V(\mathrm{\Lambda }^+)`$.

The specialization (I.5) will always be normalized in such a way that (I.3) gives us the Weyl dimension formula , in the limit $`u_i=1`$ for all $`i=1,2,\mathrm{},r`$. One also expects that

$$P(u_1,u_2,\mathrm{},u_r;0,0,\mathrm{},0)P(u_1,u_2,\mathrm{},u_r).$$
$`(I.8)`$
II. RECREATING $`A(\rho +\mathrm{\Lambda }^+)`$ FROM $`A(\rho )`$

In this section, without any reference to Weyl groups, we give a way to calculate polynomial (I.7) directly from polynomial (I.6). For this, we first give the following explicit expression for polynomial (I.6):

$$A(\rho )=\frac{\underset{\alpha \mathrm{\Phi }^+}{}(e^\alpha 1)}{_{i=1}^r(e^{\alpha _i})^{k_i}}$$
$`(II.1)`$
where

$$k_i\frac{1}{2}(\alpha _i,\alpha _i)(\lambda _i,\rho )$$
$`(II.2)`$
and $`\mathrm{\Phi }^+`$ is the positive root system of $`G_r`$. Exponents $`k_i`$’s are due to the fact that the monomial of maximal order is

$$\underset{i=1}{\overset{r}{}}(e^{\alpha _i})^{2k_i}$$

in the product $`_{\alpha \mathrm{\Phi }^+}(e^\alpha 1)`$. All the scalar products like $`(\lambda _i,\alpha _j)`$ or $`(\alpha _i,\alpha _i)`$ are the symmetrical ones and they are known to be defined via Cartan matrix of a Lie algebra. The crucial point, however, is to see that (II.1) is equivalent to

$$A(\rho )=\underset{A=1}{\overset{|W(G_r)|}{}}ϵ_A(e^{\alpha _i})^{\xi _i^0(A)}$$
$`(II.3)`$
where $`|W(G_r)|`$ is the order of Weyl group $`W(G_r)`$ and as is emphasized in section I, $`ϵ_A`$’s are signatures with values $`ϵ_A=1`$. Note here that, by expanding the product $`_{\alpha \mathrm{\Phi }^+}(e^\alpha 1)`$, the precise values of signatures can be determined uniquely.

To get an explicit expression for exponents $`\xi _i^0(A)`$ in (II.3), let us define $`R^+`$ is composed out of elements of the form

$$\beta ^+\underset{i=1}{\overset{r}{}}n_i\alpha _i$$
$`(II.4)`$
where $`n_i`$’s are some positive integers including zero. $`R^+`$ is a subset of the Positive Root Lattice of $`G_r`$. The main emphasis here is on some special roots

$$\gamma _i(I_i)R^+$$

which are defined by following conditions

$$(\lambda _i\gamma _i(I_i),\lambda _j\gamma _j(I_j))=(\lambda _i,\lambda _j),i,j=1,2,\mathrm{},r.$$
$`(II.5)`$
Note here that $`(\lambda _i,\lambda _j)`$’s are defined by inverse Cartan matrix. For the range of indices $`I_j`$’s, we assume that they take values from the set $`\{1,2,\mathrm{},|I_j|\}`$, that is

$$I_j\{1,2,\mathrm{},|I_j|\},j=1,2,\mathrm{},r.$$

We also define the sets

$$\mathrm{\Gamma }(A)\{\gamma _1(I_1(A)),\gamma _2(I_2(A)),\mathrm{},\gamma _r(I_r(A))\},A=1,2,\mathrm{},D$$
$`(II.6)`$
are chosen by conditions (II.5) where $`I_j(A)\{1,2,\mathrm{},|I_j|\}`$ and D is the maximal number of these sets.

Following two statements are then valid:

(1) $`𝐃=|𝐖(𝐆_𝐫)|`$

(2) $`|𝐈_𝐣|=|𝐖(\lambda _𝐣)|`$

where $`|W(\lambda _j)|`$ is the order, i.e. the number of elements, of the Weyl orbit $`W(\lambda _j)`$. As is known, a Weyl orbit is stable under Weyl reflections and hence all its elements have the same length. It is interesting to note however that the lengths of any two elements $`\gamma _i(j_1)`$ and $`\gamma _i(j_2)`$ could, in general, be different while the statement (2) is, still, valid.

The exponents in (II.3) can now be defined by

$$\xi _i^0(A)\frac{1}{2}(\alpha _i,\alpha _i)(\lambda _i\gamma _i(A),\rho ).$$
$`(II.7)`$
We then also state that the natural extension of (II.3) is as in the following:

$$A(\rho +\mathrm{\Lambda }^+)=\underset{A=1}{\overset{|W(G_r)|}{}}ϵ_A(e^{\alpha _i})^{\xi _i(A)}$$
$`(II.8)`$
for which the exponents are

$$\xi _i(A)\frac{1}{2}(\alpha _i,\alpha _i)(\lambda _i\gamma _i(A),\rho +\mathrm{\Lambda }^+).$$
$`(II.9)`$
as a natural extension of (II.7). Signatures have the same values in both expressions, (II.3) and (II.8). This reduces the problem of explicit calculation of character polynomial $`Ch(\mathrm{\Lambda }^+)`$ to the problem of finding solutions to conditions (II.5). It is clear that this is more manageable than that of using Weyl character formula directly.

$`\mathrm{𝐈𝐈𝐈}.\mathrm{𝐀𝐍}\mathrm{𝐄𝐗𝐀𝐌𝐏𝐋𝐄}:𝐆_\mathrm{𝟐}`$

It is known that $`G_2`$ is characterized by two different root lengths

$$(\alpha _1,\alpha _1)=6,(\alpha _2,\alpha _2)=2$$
$`(III.1)`$
and also

$$(\alpha _1,\alpha _2)=3.$$
$`(III.2)`$
Its positive root system is thus

$$\mathrm{\Phi }^+=\{\alpha _1,\alpha _2,\alpha _1+\alpha _2,\alpha _1+2\alpha _2,\alpha _1+3\alpha _2,2\alpha _1+3\alpha _2\}$$
$`(III.3)`$
Beyond $`\mathrm{\Phi }^+`$, first few elements of $`R^+`$ are determined by

$$\begin{array}{cc}& 2\alpha _2,2\alpha _1+2\alpha _2,2\alpha _1+4\alpha _2,\alpha _1+4\alpha _2,\hfill \\ & 2\alpha _1+\alpha _2,2\alpha _1+5\alpha _2,3\alpha _1+4\alpha _2,3\alpha _1+5\alpha _2,3\alpha _2,\hfill \\ & 3\alpha _1+3\alpha _2,3\alpha _1+6\alpha _2,2\alpha _1,2\alpha _1+6\alpha _2,4\alpha _1+6\alpha _2\hfill \end{array}$$

as will be seen from the definition (II.4). This will be sufficient to obtain following elements which fulfill conditions (II.5):

$$\begin{array}{cc}& \gamma _1(1)=0,\hfill \\ & \gamma _1(2)=\alpha _1,\hfill \\ & \gamma _1(3)=\alpha _1+3\alpha _2,\hfill \\ & \gamma _1(4)=3\alpha _1+3\alpha _2,\hfill \\ & \gamma _1(5)=3\alpha _1+6\alpha _2,\hfill \\ & \gamma _1(6)=4\alpha _1+6\alpha _2\hfill \end{array}$$

and

$$\begin{array}{cc}& \gamma _2(1)=0,\hfill \\ & \gamma _2(2)=\alpha _2,\hfill \\ & \gamma _2(3)=\alpha _1+\alpha _2,\hfill \\ & \gamma _2(4)=\alpha _1+3\alpha _2,\hfill \\ & \gamma _2(5)=2\alpha _1+3\alpha _2,\hfill \\ & \gamma _2(6)=2\alpha _1+4\alpha _2\hfill \end{array}$$

from which we obtain,as in (II.6), following 12 sets of 2-elements:

$$\begin{array}{cc}\hfill \mathrm{\Gamma }_1& =\{\gamma _1(1),\gamma _2(1)\},ϵ_1=+1\hfill \\ \hfill \mathrm{\Gamma }_2& =\{\gamma _1(2),\gamma _2(3)\},ϵ_2=+1\hfill \\ \hfill \mathrm{\Gamma }_3& =\{\gamma _1(3),\gamma _2(2)\},ϵ_3=+1\hfill \\ \hfill \mathrm{\Gamma }_4& =\{\gamma _1(4),\gamma _2(5)\},ϵ_4=+1\hfill \\ \hfill \mathrm{\Gamma }_5& =\{\gamma _1(5),\gamma _2(4)\},ϵ_5=+1\hfill \\ \hfill \mathrm{\Gamma }_6& =\{\gamma _1(6),\gamma _2(6)\},ϵ_6=+1\hfill \\ \hfill \mathrm{\Gamma }_7& =\{\gamma _1(1),\gamma _2(2)\},ϵ_7=1\hfill \\ \hfill \mathrm{\Gamma }_8& =\{\gamma _1(2),\gamma _2(1)\},ϵ_8=1\hfill \\ \hfill \mathrm{\Gamma }_9& =\{\gamma _1(3),\gamma _2(4)\},ϵ_9=1\hfill \\ \hfill \mathrm{\Gamma }_{10}& =\{\gamma _1(4),\gamma _2(3)\},ϵ_{10}=1\hfill \\ \hfill \mathrm{\Gamma }_{11}& =\{\gamma _1(5),\gamma _2(6)\},ϵ_{11}=1\hfill \\ \hfill \mathrm{\Gamma }_{12}& =\{\gamma _1(6),\gamma _2(5)\},ϵ_{12}=1\hfill \end{array}$$
$`(III.4)`$
Note here that $`|W(G_2)|=12`$, $`|W(\lambda _1)|=6`$ and $`|W(\lambda _2)|=6`$ show, for $`G_2`$, the validity of our two statements mentioned above. The signatures are given on the right-hand side of (III.4). They can be easily found to be true by comparing two expressions (II.1) and (II.3) for the case in hand. As in (I.5), let us choose the most general specialization

$$e^{\alpha _1}=x,e^{\alpha _2}=y.$$

Then, in view of (I.8), character polynomial

$$R(x,y,s_1,s_2)\frac{P(x,y,s_1,s_2)}{P(x,y,0,0)}$$
$`(III.5)`$
for an irreducible $`G_2`$ representation originated from a dominant weight $`\mathrm{\Lambda }^+=s_1\lambda _1+s_2\lambda _2`$ will be expressed in its following ultimate form:

$$\begin{array}{cc}\hfill P(x,y,s_1,s_2)=& +x^{3+2s_1+s_2}y^{5+3s_1+2s_2}+x^{32s_1s_2}y^{53s_12s_2}\hfill \\ & +x^{2s_1s_2}y^{1s_2}+x^{2+s_1+s_2}y^{1+s_2}\hfill \\ & +x^{1s_1}y^{43s_1s_2}+x^{1+s_1}y^{4+3s_1+s_2}\hfill \\ & x^{1+s_1}y^{1s_2}x^{1s_1}y^{1+s_2}\hfill \\ & x^{2s_1s_2}y^{53s_12s_2}x^{2+s_1+s_2}y^{5+3s_1+2s_2}\hfill \\ & x^{32s_1s_2}y^{43s_1s_2}x^{3+2s_1+s_2}y^{4+3s_1+s_2}\hfill \end{array}$$
$`(III.6)`$
In the following we will give some examples to illustrate (III.5);

$$\begin{array}{cc}& Ch(\lambda _1)=R(x,y,1,0)=\frac{1}{x^2y^3}(1+x+xy+xy^2+x^2y^2+xy^3+2x^2y^3+x^3y^3\hfill \\ & +x^2y^4+x^3y^4+x^3y^5+x^3y^6+x^4y^6)\hfill \\ & Ch(\lambda _2)=R(x,y,0,1)=\frac{1}{xy^2}(1+y+xy+xy^2+xy^3+x^2y^3+x^2y^4)\hfill \\ & Ch(\lambda _1+\lambda _2)=R(x,y,1,1)=\frac{1}{x^3y^5}(1+x)(1+y)(1+xy)(1+xy^2)(1+\hfill \\ & xy^3)(1+x^2y^3)\hfill \\ & Ch(2\lambda _2)=R(x,y,0,2)=\frac{1}{x^2y^4}(1+y+y^2)(1+xy+x^2y^2)(1+xy^2+x^2y^4)\hfill \end{array}$$

where

$$P(x,y,0,0)=\frac{1}{x^3y^5}(1x)(1y)(1xy)(1xy^2)(1xy^3)(1x^2y^3)$$

A useful application of (III.5) is in the calculation of tensor coupling coefficients . We note, for instance, that the coefficients in decomposition

$$\begin{array}{cc}\hfill V(\lambda _1)V(\lambda _1+\lambda _2)& =V(2\lambda _1+\lambda _2)V(\lambda _1+2\lambda _2)V(4\lambda _2)V(3\lambda _2)\hfill \\ & 2V(\lambda _1+\lambda _2)V(2\lambda _2)V(\lambda _2)\hfill \end{array}$$

can be calculated easily by

$$\begin{array}{cc}\hfill R(x,y,1,0)R(x,y,1,1)& =R(x,y,2,1)R(x,y,1,2)R(x,y,0,4)R(x,y,0,3)\hfill \\ & 2R(x,y,1,1)R(x,y,0,2)R(x,y,0,1)\hfill \end{array}$$

where the terms above are already known by (III.5).

CONCLUSION

Although application of our method is given here in case of $`G_2`$ Lie algebra, there are no serious difficulty to do the same for classical chains $`A_r,B_r,C_r`$ and $`D_r`$ of finite Lie algebras. Our results for exceptional Lie algebras $`F_4`$ and $`E_6`$ will be given soon in a subsequent publication. In case of $`E_7`$ and $`E_8`$ Lie algebras, one must however emphasize that rather than the most general specialization (I.5) of formal exponentials we need in practice more simple specializations though there are some other methods  which work equally well for $`E_7`$ and $`E_8`$. For Affine Lie Algebras, a similar study of Weyl-Kac character formula will also be interesting.

REFERENCES

 H.Weyl, The Classical Groups, N.J. Princeton Univ. Press (1946)

 H.R.Karadayi and M.Gungormez, J.Phys.A:Math.Gen. 32 (1999) 1701-1707

 J.E.Humphreys, Introduction to Lie Algebras and Representation Theory, N.Y., Springer-Verlag (1972)

 V.G.Kac, Infinite Dimensional Lie Algebras, N.Y., Cambridge Univ. Press (1990)

 Weyl dimension formula cited in p.139 of ref

 Steinberg formula cited in p.140 of ref

 H.R.Karadayi and M.Gungormez, Summing over the Weyl Groups of $`E_7`$ and $`E_8`$, math-ph/9812014


text:
# Quantum Algorithms for Weighing Matrices and Quadratic Residues

## 1 Introduction

The theory of quantum computation investigates how we can use quantum mechanical effects to solve computational problems more efficiently than we can by classical means. So far, the strongest evidence that there is indeed a real and significant difference between quantum and classical computation is provided by Peter Shor’s polynomial-time factoring algorithm. Most other quantum complexity results are expressed in the black-box, or oracle, setting of computation with various degrees of separation between the two models. The algorithms of—for example—Deutsch, Deutsch & Jozsa, Berthiaume & Brassard, Bernstein & Vazirani, Simon, Grover, and Buhrman & van Dam define problems for which we have a quantum reduction in the query complexity, whereas the lower bounds of Jozsa, Bennett *et al.*, and Beals *et al.* show that there are limits to the advantage that quantum computation can give us. The general picture that has emerged from these results is that we can only expect a superpolynomial difference between classical and quantum computation if we can use the specific structure of the problem that we try to solve. The promise on the function of Simon’s problem is a typical example of such a structure that establishes an exponential quantum improvement over the classical complexity. It was this same improvement that inspired Shor for his result.

In this article we introduce a general family of structured problems for which we prove a better-than-classical query complexity. These results rely heavily on the properties of weighing matrices (as defined in combinatorics) and encompass the earlier query protocols by Grover and Bernstein & Vazirani. Following Paley’s construction of Hadamard matrices, we also define a more specific problem that concerns the determination of a shifted Legendre sequence over finite fields.

In the next section we start with a brief overview of the essential ingredients of quantum computation and some of the relevant complexity results for the black-box model. Section 3 then explains how the theory of weighing matrices can be used as a source for non-trivial, yet structured, unitary operations. In the last part of the article (Section 5) our attention will focus on Raymond Paley’s construction of Hadamard matrices and the theory of quadratic residues for finite fields that it uses. This will lead to the definition of a query problem which is akin to the inner-product problem of Bernstein & Vazirani.

## 2 Quantum Computation

We assume the reader to be familiar with the theory of quantum computation. (Otherwise, see the standard references by Berthiaume, Nielsen and Chuang, or Preskill.) Here we will mainly fix the terminology and notation for the rest of the article.

### 2.1 Quantum Information Processing

A system $`\psi `$ of $`n`$ quantum bits (qubits) is a superposition of all possible $`n`$-bit strings. It can therefore be represented as a normalized vector (or “ket”) $`|\psi `$ in a $`2^n`$-dimensional Hilbert space:

$`|\psi `$ $`=`$ $`{\displaystyle \underset{x\{0,1\}^n}{}}\alpha _x|x,`$
with $`\alpha _x`$ and the normalization restriction $`_x|\alpha _x|^2=1`$. The probability of observing the outcome “$`x`$” when measuring the state $`\psi `$ equals $`|\alpha _x|^2`$. More general, when we try to determine if $`\psi `$ equals the measurement vector $`|m=_x\beta _x|x`$, we will get an affirmative answer with probability

$`\mathrm{Prob}(m|\psi ):=|m|\psi |^2`$ $`=`$ $`\left|{\displaystyle \underset{x\{0,1\}^n}{}}\overline{\beta }_x\alpha _x\right|^2`$
(with $`\overline{\beta }`$ the complex conjugate of $`\beta `$). An *orthogonal measurement basis* for an $`N`$-dimensional Hilbert space $`_N`$ is a set $`\{m_1,m_2,\mathrm{},m_N\}`$ of mutually orthogonal state vectors $`|m_i`$. For such a basis it holds that $`_{i=1}^N\mathrm{Prob}(m_i|\psi )=1`$, for every state $`|\psi _N`$, and that if $`\psi =m_s`$ for a certain $`s`$, then $`\mathrm{Prob}(m_i|\psi )=1`$ if $`i=s`$, and $`\mathrm{Prob}(m_i|\psi )=0`$ otherwise.

The quantum mechanical time evolution of a system $`\psi `$ is a linear transformation that preserves the normalization restriction. Hence, for a finite-dimensional state space $`_N`$, such a transformation can be represented by a unitary matrix $`M𝖴(N)`$, for which we can write $`M|\psi =_{x=1}^N\alpha _xM|x`$. An example of a one-qubit transformation is the ‘Hadamard transform’, which is represented by the unitary matrix

H $`:=`$ $`\frac{1}{\sqrt{2}}\left(\begin{array}{cc}+1& +1\\ +1& 1\end{array}\right).`$
On the standard zero/one basis for a bit this transformation has the following effect: $`\text{H}|0=\frac{1}{\sqrt{2}}(|0+|1)`$ and $`\text{H}|1=\frac{1}{\sqrt{2}}(|0|1)`$.

### 2.2 Quantum versus Classical Query Complexity

Consider a problem that is defined in terms of $`n`$ (unknown) values $`f(1),\mathrm{},f(n)`$. The *(probabilistic) query complexity* of such a problem is the minimum number of times that an algorithm has to ‘consult’ the string $`f(1),\mathrm{},f(n)`$ to solve the problem (with high probability). A typical example of this setting is the calculation of the OR of $`n`$ bit values: the question whether there is an index $`i`$ with $`f(i)=1`$. The classical probabilistic, query complexity of this task is $`\mathrm{\Omega }(n)`$, whereas in the quantum setting we only need $`O(\sqrt{n})`$calls to $`f`$ to solve the problem with high probability. We therefore say that we have a ‘quadratic’ separation between the classical and the quantum query complexity of the OR function. The question which tasks allow a quantum reduction in the query complexity (and if so, how much) is a central one in quantum complexity research.

### 2.3 Some Earlier Results in Quantum Computing

In this article we are especially concerned with the query complexity of procedures that prepare a state that depends on the values of a black-box function. For example, how often do we have to read out the bit values of a function $`f:`$ if we want to create the state $`_if(i)|i`$? The following lemma shows us that if the range of the function is limited to $`\{1,+1\}`$, this can be done with a single query.

###### Fact 1 (Phase-kick-back trick)

Given a function $`f:\{1,+1\}`$, the phase changing transition $`_i\alpha _i|i_if(i)\alpha _i|i`$ can be established with only one call to the unknown binary values of $`f`$.

Proof:  (See  for the original proof.) First, attach to the superposition of $`_i\alpha _i|i`$ the (two qubit state)

$`|\phi `$ $`:=`$ $`\frac{1}{2}(|0+\sqrt{1}|1|2\sqrt{1}|3).`$
Then, in superposition, add modulo $`4`$ the values $`f(i)`$ to this register (step $`a`$). Finally, apply a general phase change $`|\mathrm{\Psi }\sqrt{1}|\mathrm{\Psi }`$ (step $`b`$). It is straightforward to see that this yields the desired phase change according to the equation:

$`|i|\phi `$ $`_a`$ $`\{\begin{array}{cc}\hfill \sqrt{1}|i|\phi & \text{if }f(i)=+1\hfill \\ \hfill \sqrt{1}|i|\phi & \text{if }f(i)=1\hfill \end{array}`$
$`_b`$ $`f(i)|i|\phi ,`$
for every $`i`$ in the superposition.  $``$$``$

The usefulness of such a phase-changing operation is made clear by the following result, which is mentioned because the Theorems 1 and 2 of this article are of a similar fashion. In 1993 Bernstein & Vazirani gave the following example of a family of functions $`g_1,g_2,\mathrm{}`$ that are more easily distinguished with quantum queries to $`g`$ than with classical ones.

###### Fact 2 (Inner-Product Problem)

Let the black-box function $`g_s:\{0,1\}^n\{0,1\}`$ be defined by $`g_s(x)=(x,s):=_{i=1}^ns_ix_imod2`$, where $`s=(s_1,\mathrm{},s_n)\{0,1\}^n`$ is an unknown $`n`$-bit mask. A quantum computer can determine the value $`s`$ exactly with one call to the function $`g_s`$, whereas any probabilistic, classical algorithm needs at least $`n+\mathrm{log}(1\epsilon )`$ queries to $`g_s`$ to perform the same task with an error rate of at most $`\epsilon `$.

Proof:  See  for the original proof by Bernstein & Vazirani, and  for the single query version of it.  $``$$``$

The above result uses the unitarity of $`\text{H}^n`$ and its connection with the inner-product function. In Section 5 of this article we will do a similar thing for a different family of unitary matrices and the Legendre function that it uses.

Another key result in quantum computation is the square-root speed-up that one can obtain when querying a database for a specific element.

###### Fact 3 (Grover’s search algorithm)

Let the function values $`f(1),\mathrm{},f(n)`$ form a string of $`nk`$ zeros and $`k`$ ones. Knowing $`k`$, but not the specific entries $`s`$ for which $`f(s)=1`$, the amplitude changing evolution

$`{\displaystyle \frac{1}{\sqrt{n}}}{\displaystyle \underset{j=1}{\overset{n}{}}}|i`$ $``$ $`{\displaystyle \frac{1}{\sqrt{k}}}{\displaystyle \underset{j=1}{\overset{n}{}}}f(i)|i`$
can be established exactly with $`\frac{\pi }{4}\sqrt{\frac{n}{k}}`$ quantum queries to the function $`f`$.

Proof:  See the original article by Lov Grover, or better yet, the excellent analysis of it by Boyer *et al.*  $``$$``$

## 3 Hadamard Matrices and Weighing Matrices in Combinatorics

The matrix H that we mentioned in the previous section is—in the context of quantum computation—called the ‘Hadamard matrix’. This terminology is a bit unfortunate because the same term has already been used in combinatorics to cover a much broader concept. (See the 1893 article by Jacques Hadamard for the origin of this term.)

###### Definition 1 (Hadamard matrix in combinatorics)

In combinatorics, a matrix $`M\{1,+1\}^{n\times n}`$ is called a *Hadamard matrix* if and only if $`MM^T=n\mathrm{I}_n`$, where “$`T`$” denotes the transpose of a matrix.

Obviously, when $`M`$ is a Hadamard matrix in the above sense, then $`\frac{1}{\sqrt{n}}M`$ is a unitary matrix $`𝖴(n)`$. Also, if $`M_1`$ and $`M_2`$ are Hadamard matrices, then their tensor product $`M_1M_2`$ is a Hadamard matrix as well. It is a famous open problem if there exists a Hadamard matrix for every dimension $`4k`$.

The $`\text{H}^n`$ matrices that we encountered in the section on quantum computation form only a small subset of all the Hadamard matrices that we know in combinatorics. Instead, the matrices $`\sqrt{2^n}\text{H}^n`$ should perhaps be called “Hadamard matrices of the Sylvester kind” after the author who first discussed this specific family of matrices.

The properties of Hadamard matrices (especially the above mentioned $`4k`$-conjecture) is an intensively studied topic in combinatorics, and its complexity is impressive given the simple definition. In 1933, Raymond Paley proved the existence of two families of Hadamard matrices that are very different from Sylvester’s $`2^n`$-construction.

###### Fact 4 (Paley construction I and II)

Construction I: For every prime $`p`$ with $`p=3mod4`$ and every integer $`k`$, there exists a Hadamard matrix of dimension $`(p^k+1)\times (p^k+1)`$. Construction II: For every prime $`p`$ with $`p=1mod4`$ and every integer $`k`$, there exists a Hadamard matrix of dimension $`(2p^k+2)\times (2p^k+2)`$.

Proof:  See the original article , or any other standard text on combinatorial objects.  $``$$``$

For here it sufficient to say that Paley’s construction uses the theory of quadratic residues of finite fields $`𝔽_{p^k}`$. Its properties that are relevant for this article are discussed in the appendix.

We can extend the notion of Hadamard matrices by allowing three possible matrix entries $`\{1,+1,0\}`$, while still requiring the $`MM^T\mathrm{I}_n`$ restriction. We thus reach the following definition.

###### Definition 2 (Weighing matrix )

In combinatorics, a matrix $`M\{1,0,+1\}^{n\times n}`$ is called a *weighing matrix* if and only if $`MM^T=k\mathrm{I}_n`$ for some $`0kn`$. We will denote the set of such matrices by $`𝖶(n,k)`$.

Every column and row of a $`𝖶(n,k)`$ weighing matrix has $`nk`$ zeros, and $`k`$ entries “$`+1`$” or “$`1`$”. Clearly, $`𝖶(n,n)`$ are the Hadamard matrices again, whereas $`𝖶(n,n1)`$ are also called *conference matrices.* The identity matrix $`\mathrm{I}_n`$ is an example of a $`𝖶(n,1)`$ matrix. If $`M_1𝖶(n_1,k_1)`$ and $`M_2𝖶(n_2,k_2)`$, then their tensor product $`M_1M_2`$ is an element of $`𝖶(n_1n_2,k_1k_2)`$. This implies that for every weighing matrix $`M𝖶(n,k)`$ we have in fact a whole family of matrices $`M^t𝖶(n^t,k^t)`$, indexed by $`t`$.

###### Example 1

$$\left(\begin{array}{cccc}\hfill +1& \hfill +1& \hfill +1& \hfill 0\\ \hfill +1& \hfill 1& \hfill 0& \hfill +1\\ \hfill +1& \hfill 0& \hfill 1& \hfill 1\\ \hfill 0& \hfill +1& \hfill 1& \hfill +1\end{array}\right)^t\text{ is a }𝖶(4^t,3^t)\text{ weighing matrix for every }t\text{.}$$

The observation that for every $`M𝖶(n,k)`$ the matrix $`\frac{1}{\sqrt{k}}M𝖴(n)`$ is a unitary matrix makes the connection between combinatorics and quantum computation that we explore in this article. In the next section we will see how the mutually orthogonal basis of such a matrix can be used for a query efficient quantum algorithm. The classical lower bound for the same problem is proven using standard, decision tree arguments.

## 4 Quantum Algorithms for Weighing Matrices

In this section we will describe a general weighing-matrix-problem and its quantum solution. But before doing so, we first mention the following state construction lemma which follows directly from earlier results on Grover’s search algorithm.

###### Lemma 1 (State construction lemma)

Let $`f:\{1,\mathrm{},n\}\{1,0,+1\}`$ be a black-box function. If we know that $`k`$ of the function values are “$`+1`$” or “$`1`$”, and the remaining $`nk`$ entries are “$`0`$”, then the preparation of the state

$`|f`$ $`:=`$ $`{\displaystyle \frac{1}{\sqrt{k}}}{\displaystyle \underset{i=1}{\overset{n}{}}}f(i)|i,`$
requires no more than $`\frac{\pi }{4}\sqrt{\frac{n}{k}}+1`$ quantum evaluations of the black-box function $`f`$. When $`k=n`$, a single query is sufficient.

Proof:  First, we use the amplitude amplification process of Grover’s search algorithm described in Fact 3 to create exactly the state $`\frac{1}{\sqrt{k}}_{i=1,\mathrm{},n}^{f(i)0}|i`$ with no more than $`\frac{\pi }{4}\sqrt{\frac{n}{k}}`$ queries to $`f`$. (See the article by Boyer *et al.*  for a derivation of this upper bound. Obviously, no queries are required if $`k=n`$.) After that, following Fact 1, one additional $`f`$-call is sufficient to insert the proper amplitudes, yielding the desired state $`|f`$.  $``$$``$

### 4.1 Weighing Matrix Problem and Its Quantum Solution

We will now define the central problem of this article, which assumes the existence of a weighing matrix.

###### Definition 3 (Weighing Matrix Problem)

Let $`M`$ be a $`𝖶(n,k)`$ weighing matrix. Define a set of $`n`$ functions $`f_s^M:\{1,\mathrm{},n\}\{1,0,+1\}`$ for every $`s\{1,\mathrm{},n\}`$ by $`f_s^M(i):=M_{si}`$. Given a function $`f_s^M`$ in the form of a black-box, we want to determine the parameter $`s`$. The (probabilistic) query complexity of the weighing matrix problem is the minimum number of calls to the function $`f`$ that is necessary to determine the value $`s`$ (with error probability at most $`1\epsilon `$).

With the quantum protocol of Lemma 1 we can solve this problem in a straightforward way.

###### Theorem 1 (Quantum procedure for the Weighing Matrix Problem)

For every weighing matrix $`M𝖶(n,k)`$ with the corresponding Weighing Matrix Problem of Definition 3, there exists a quantum algorithm that determines $`s`$ exactly with at most $`\frac{\pi }{4}\sqrt{\frac{n}{k}}+1`$ queries to $`f_s^M`$. When $`n=k`$, the problem can be solved with one query to the function.

Proof:  First, prepare the state $`|f_s^M=\frac{1}{\sqrt{k}}_{i=1}^nf_s^M(i)|i`$ with $`\frac{\pi }{4}\sqrt{\frac{n}{k}}+1`$ queries to the function $`f`$ (Lemma 1). After that, measure the state in the basis spanned by the vectors $`|f_1^M,\mathrm{},|f_n^M`$. Because $`M`$ is a weighing matrix, this basis is orthogonal and hence the outcome of the measurement gives us the value $`s`$ (via the outcome $`|f_s^M`$) without error.  $``$$``$

### 4.2 Classical Bounds for Weighing Matrix Problems

For every possible weighing matrix, the above result establishes a separation between the quantum and the classical query complexity of the problem, as is shown by the following classical lower bound.

###### Lemma 2 (Classical lower bounds for the Weighing Matrix Problem)

Consider the Weighing Matrix Problem of Definition 3 for a matrix $`M𝖶(n,k)`$. Let $`d`$ be the number of queries used by a classical algorithm that recovers $`s`$ with an error probability of at most $`\epsilon `$. This query complexity $`d`$ is bounded from below by the following three inequalities:

$`d`$ $``$ $`\mathrm{log}_3n+\mathrm{log}_3(1\epsilon ),`$
$`d`$ $``$ $`(1\epsilon )\frac{n}{k}\frac{1}{k},`$
$`d`$ $``$ $`\mathrm{log}(\frac{n}{nk+1})+\mathrm{log}(1\epsilon ).`$
For the case where $`k=n`$, this last lower bound equals $`d\mathrm{log}n+\mathrm{log}(1\epsilon )`$.

Proof:  We will prove these bounds by considering the decision trees that describe the possible classical protocols. The procedure starts at the root of the tree and this node contains the first index $`i`$ that the protocol queries to the function $`f`$. Depending on the outcome $`f(i)\{1,0,+1\}`$, the protocol follows one of the three outgoing edges to a new node $`v`$, which contains the next query index $`i_v`$. This routine is repeated until the procedure reaches one of the leaves of the tree. At that point, the protocol guesses which function it has been querying. With this representation, the depth of such a tree reflects the number of queries that the protocol uses, while the number of leaves (nodes without outgoing edges) indicates how many different functions the procedure can distinguish.

For a probabilistic algorithm with error probability $`\epsilon `$, we need to use decision trees with at least $`(1\epsilon )n`$ leaves. Because the number of outgoing edges cannot be bigger than $`3`$, a tree with depth $`d`$ has maximally $`3^d`$ leaves. This proves the first lower bound via $`3^d(1\epsilon )n`$.

For the second and third bound we have to analyze the maximum size of the decision tree as it depends on the values $`k`$ and $`n`$. We know that for every index $`i_v`$, there are only $`k`$ different functions with $`f(i_v)0`$. This implies that at every node $`v`$ the joint number of leaves of the two subtrees associated with the outcomes $`f(i_v)=1`$ and $`+1`$ cannot be bigger than $`k`$. Hence, by considering the path (starting from the root) along the edges that correspond to the answers $`f(i_v)=0`$, we see that a decision tree with $`d`$ queries, can distinguish no more than $`dk+1`$ functions. The second bound is thus obtained by the resulting inequality $`dk+1(1\epsilon )n`$. (The case $`k=1`$ is the strongest example of this bound.)

In a similar fashion, we can use the observation that there are exactly $`nk`$ functions with $`f(i_v)=0`$ for every node $`v`$. Now we should consider the binary subtree that is spanned by the edges that correspond to the answers $`f(i_v)=+1`$ and $`f(i_v)=1`$. With depth $`d`$, this subtree has at most $`2^d`$ leaves and $`2^d1`$ internal nodes. For the complete tree, each such internal node $`v`$ gives at most $`nk`$ additional leaves, which are the functions with $`f(i_v)=0`$. In sum, this tells us that the total tree (with depth $`d`$) has a maximum number of leaves of $`2^d+(2^d1)(nk)`$, leading to the third result: $`d\mathrm{log}(\frac{n}{nk+1})+\mathrm{log}(1\epsilon )`$.  $``$$``$

### 4.3 Additional Remarks

The above bounds simplify significantly when we express them as functions of big enough $`n`$, giving us the following table:

| $`k`$ | quantum upper bound | classical lower bound |
| --- | --- | --- |
| $`o(n)`$ | $`\frac{\pi }{4}\sqrt{\frac{n}{k}}+2`$ | $`(1\epsilon )\frac{n}{k}O(1)`$ |
| $`\mathrm{\Theta }(n)`$ | $`O(1)`$ | $`\mathrm{log}_3n+\mathrm{log}_3(1\epsilon )`$ |
| $`n`$ | $`1`$ | $`\mathrm{log}n+\mathrm{log}(1\epsilon )`$ |

.

Note that the $`n`$-dimensional identity matrix is a $`𝖶(n,1)`$ weighing matrix, and that for this $`\mathrm{I}_n`$ the previous theorem and lemma are just a rephrasing (with $`k=1`$) of the results on Grover’s search algorithm for exactly one matching entry. The algorithm of Bernstein & Vazirani is also captured by the above as the case where $`k`$ has the maximum value $`k=n`$ (with the weighing matrices $`(\sqrt{2}\text{H})^t𝖶(2^t,2^t)`$). Hence we can think of those two algorithms as the extreme instances of the more general weighing matrix problem.

As we phrased it, a weighing matrix $`M𝖶(n,k)`$ gives only one specific problem for which there is a classical/quantum separation, but not a problem that is defined for every input size $`N`$, as is more customary. We know, however, that for every such matrix $`M`$, the tensor products $`M^t`$ are also $`W(n^t,k^t)`$ weighing matrices (for all $`t`$). We therefore have the following direct consequence of our results.

###### Corollary 1

Every weighing matrix $`M𝖶(n,k)`$ defines an infinite family of $`𝖶(N,K)`$ weighing matrix problems, with parameters $`N=n^t`$ and $`K=k^t=N^{\mathrm{log}_nk}`$ for every $`t`$. By defining $`\gamma =1\mathrm{log}_nk`$ we have, for every suitable $`N`$, a quantum algorithm with query complexity $`\frac{\pi }{4}\sqrt{N^\gamma }`$ for which there is a classical, probabilistic lower bound of $`(1\epsilon )N^\gamma +o(1)`$.

###### Example 2

Using the $`𝖶(4^t,3^t)`$ weighing matrices of Example 1, we have $`\gamma =1\frac{1}{2}\mathrm{log}30.21`$, and hence a quantum algorithm with query complexity $`\frac{\pi }{4}N^{0.10\mathrm{}}`$. The corresponding classical probabilistic, lower bound of this problem is $`(1\epsilon )N^{0.21\mathrm{}}+o(1)`$.

A legitimate objection against the Weighing Matrix Problem is that it does not seem to be very useful for solving real-life problems. In order to obtain more natural problems one can try to look into the specific structure that constitutes the weighing matrix or matrices. An example of such an approach will be given in the next section via Paley’s construction of Hadamard matrices. We will see how this leads to the definition of a problem dealing with quadratic residues of finite fields that has a quantum solution that is more efficient than any classical protocol.

## 5 The Shifted Legendre Sequence Problem

The query task that we will define in this section relies on some standard properties of finite fields. See the appendix of this article for a short but sufficient overview of this theory. Especially important is the following function which generalizes the Legendre symbol $`(\frac{i}{p})`$ over $`/(p)`$ to all finite fields $`𝔽_q`$. (From now on, $`p`$ will alway denote an odd prime, and $`q=p^k`$ a power of such a prime.)

###### Definition 4 (Legendre symbol over a Finite Field)

For every finite field $`𝔽_q`$, with $`q=p^k`$ an odd prime power, the Legendre symbol function $`\chi :𝔽_q\{1,0,+1\}`$ indicates if a number is a quadratic residue or not:

$`\chi (i)`$ $`:=`$ $`\{\begin{array}{cc}\hfill 0& \text{if }i=0\hfill \\ \hfill +1& \text{if }j0:j^2=i\hfill \\ \hfill 1& \text{if }j:j^2i\text{.}\hfill \end{array}`$
This function is a quadratic, multiplicative character over $`𝔽_q`$, which implies the following result.

###### Fact 5 (Near Orthogonality of Shifted Legendre Sequences)

For the ‘inner product’ between two Legendre sequences that are shifted by $`s`$ and $`r𝔽_q`$ it holds that

$`{\displaystyle \underset{i𝔽_q}{}}\chi (i+r)\chi (i+s)`$ $`=`$ $`\{\begin{array}{cc}\hfill q1& \text{if }s=r\text{,}\hfill \\ \hfill 1& \text{if }sr.\hfill \end{array}`$
Proof:  See the proof of Fact 6 in the appendix.  $``$$``$

Raymond Paley used this near orthogonality property for the construction of his Hadamard matrices. Here we will use the same property to describe a problem that, much the like the weighing matrix problem of the previous section, has a clear gap between its quantum and classical query complexity. In light of Theorem 1 and Lemma 2 the results of this section are probably not very surprising. Rather, we wish to give an example of how we can borrow the ideas behind the construction of combinatorial objects for the design of new quantum algorithms. In this case this is done by stating a problem that uses the Legendre symbol over finite fields.

###### Definition 5 (Shifted Legendre Sequence/SLS Problem)

Assume that we have a black-box for a shifted Legendre function $`f_s:𝔽_q\{1,0,+1\}`$ that obeys $`f_s(i):=\chi (i+s)`$, with the—for us unknown—shift parameter $`s𝔽_q`$. The task is to determine (with probability $`1\epsilon `$) the value $`s`$ with a minimum number of calls to the function $`f`$.

### 5.1 Classical Query Complexity of the SLS Problem

Before describing the quantum algorithm for the Shifted Legendre Sequence Problem, we will first determine its classical query complexity. The following lower bound is established in a way similar to the proof of Lemma 2.

###### Lemma 3 (Classical lower bound SLS Problem)

Assume a classical algorithm that tries to solve the shifted Legendre sequence problem over a finite field $`𝔽_q`$. To determine the requested value $`s`$ with a maximum error rate $`\epsilon `$, requires more than $`\mathrm{log}q+\mathrm{log}(\frac{1\epsilon }{2})`$ queries to the function $`f_s`$.

Proof:  Consider, like in the proof of Lemma 2, a decision tree with nodes $`v`$ and corresponding query indices $`i_v`$. For every index $`i_v`$ there is exactly one function with $`f(i_v)=0`$. For the tree this implies that every node $`v`$ can only have two proper subtrees (corresponding to the answers $`f(i)=+1`$ and $`1`$) and one deciding leaf (the case $`f_{(i)}(i)=0`$). Hence, a decision tree of depth $`d`$ can distinguish no more than $`2^{d+1}1`$ different functions. In order to be able to differentiate between $`(1\epsilon )q`$ functions, we thus need a depth $`d`$ of at least $`\mathrm{log}((1\epsilon )q+1)1`$.  $``$$``$

This lower bound of $`\mathrm{log}q`$ queries is also optimal as is shown by the following result.

###### Lemma 4 (Classical upper bound SLS Problem)

There exists a deterministic, classical protocol that solves the Shifted Legendre Sequence Problem with $`O(\mathrm{log}q)`$ queries to the black-box function $`f_s`$.

Proof:  Let $`S𝔽_q`$ be the set of possible values of $`s`$ at a given moment during the execution of the protocol. (Thus, initially we have $`S=𝔽_q`$, and we want to end with the unique answer determined by $`|S|=1`$.) Below we will show that if $`S`$ has at least $`4`$ elements, then there always exists an index $`i`$ such that all three possible answers to the query “$`f(i)`$?” lead to a reduced the set of options $`S^{}`$ with $`|S^{}|<\frac{3}{4}|S|`$. By repeating this procedure no more than $`\mathrm{log}q/\mathrm{log}(\frac{4}{3})`$ times, we can reduce the initial set $`S=𝔽_q`$ to four possibilities, which can then be checked with three additional queries.

What follows is the existence proof of such an index for every possible subset $`S𝔽_q`$. Given a set $`S`$ and an index $`i`$, we have a partition of $`S`$ in three subsets according to the answer $`\chi (s+i)`$ to the query “$`f(i)`$?”

$`S_i^+`$ $`:=`$ $`\{j|jS\text{ and }\chi (s+j)=+1\},`$
$`S_i^{}`$ $`:=`$ $`\{j|jS\text{ and }\chi (s+j)=1\},`$
$`S_i^0`$ $`:=`$ $`\{j|jS\text{ and }\chi (s+j)=0\}.`$
Note that, depending on whether $`s`$ is an element of $`S`$ or not, $`S_i^0`$ is either $`\{s\}`$ or the empty set. Clearly, one of these three sets will be the reduced set $`S^{}`$ mentioned in the first part of the proof.

Define the Legendre matrix $`L\{1,0,+1\}^{q\times q}`$ by $`L_{ij}:=\chi (i+j)`$, and let $`z_S`$ be the characteristic vector $`\{0,1\}^q`$ of the subset $`S𝔽_q`$. The product of $`L`$ and $`z_S`$ yields a new vector $`w_s`$ with the following property for its $`i`$-th entry:

$$(w_S)_i=\underset{j𝔽_q}{}\chi (i+j)(z_S)_j=\underset{jS}{}\chi (i+j)=|S_i^+||S_i^{}|.$$

By the near orthogonality property of the Legendre sequence (Fact 5) we know that for the matrix $`L`$ we have $`L^TL=q\mathrm{I}_q\mathrm{J}_q`$, where $`\mathrm{J}_q`$ is the ‘all ones’ matrix of dimension $`q\times q`$. The inner product $`z_S^Tz_S`$ is the Hamming weight of $`z_S`$ and hence equals the size $`|S|`$ of the set $`S`$. This implies for the inner product of $`Lz_S`$ with itself: $`(z_S^TL^T)(Lz_S)=z_S^T(q\mathrm{I}_q\mathrm{J}_q)z_S=q|S||S|^2`$. By the previous equation for $`w_S`$, we thus see that

$$q|S||S|^2=w_S^Tw_S=\underset{i𝔽_q}{}\left(|S_i^+||S_i^{}|\right)^2.$$

This proves that there exist at least one index $`i`$ for which $`(|S_i^+||S_i^{}|)^2\frac{1}{q}(q|S||S|^2)`$, and hence $`\sqrt{|S|}<|S_i^+||S_i^{}|<\sqrt{|S|}`$. In combination with the general bound $`|S_i^+|+|S_i^{}||S|`$, this gives that for this $`i`$ both $`|S_i^+|`$ and $`|S_i^{}|`$ are less than $`\frac{1}{2}|S|+\frac{1}{2}\sqrt{|S|}`$. For $`|S|4`$ this proves that indeed all three $`S_i^+`$, $`S_i^{}`$ and $`S_i^0`$ have size less than $`\frac{3}{4}|S|`$.  $``$$``$

### 5.2 Quantum Query Complexity of the SLS Problem

The above classical upper bound for the Shifted Legendre Sequence Problem relied on the near orthogonality property of the Legendre sequence. The same is done by the quantum protocol for the SLS Problem, but in a more efficient way: only $`2`$ quantum queries are required.

###### Theorem 2 (Two query quantum protocol for the SLS Problem)

For any finite field $`𝔽_q`$, the Shifted Legendre Sequence Problem of Definition 5 can be solved exactly with two quantum queries to the black-box function $`f_s`$.

Proof:  We exhibit the quantum algorithm in detail. We start with the superposition

$$\frac{1}{\sqrt{q+1}}(\underset{i𝔽_q}{}|i|0+|\text{dummy}|1).$$

(The reason for the “dummy” part of state that we use will be clear later in the analysis.) The first oracle call is used to calculate the different $`f_s(i)=\chi (i+s)`$ values for the non-dummy states, giving a superposition of states $`|i,\chi (i+s)`$. At this point, we measure the rightmost register to see if it contains the value “zero”. If this is indeed the case (probability $`\frac{1}{q+1}`$), the state has collapsed to $`|s|0`$ which directly gives us the desired answer $`s`$. Otherwise, we continue with the now reduced state

$$\frac{1}{\sqrt{q}}(\underset{i𝔽_q\{s\}}{}|i|\chi (i+s)+|\text{dummy}|1),$$

on which we apply a conditional phase change (depending on the $`\chi `$ values in the rightmost register). We finish the computation by ‘erasing’ this rightmost register with a second call to $`f_s`$. (For the dummy part, we just reset the value to “zero”.) This gives us the final state $`\psi `$, depending on $`s`$, of the form

$`|\psi _s|0`$ $`:=`$ $`{\displaystyle \frac{1}{\sqrt{q}}}({\displaystyle \underset{i𝔽_q}{}}\chi (i+s)|i+|\text{dummy})|0.`$
What is left to show is that $`\{|\psi _s|s𝔽_q\}`$ forms a set of orthogonal vectors. Fact 5 tells us that for the inner product between two states $`\psi _s`$ and $`\psi _r`$ it holds that $`\psi _r|\psi _s=1`$ if $`s=r`$, and $`\psi _r|\psi _s=0`$ if $`sr`$. In other words, the states $`\psi _s`$ for $`s𝔽_q`$ are mutually orthogonal. Hence, by measuring the final state in the $`\psi `$-basis, we can determine without error the shift factor $`s𝔽_q`$ after only two oracle calls to the function $`f_s`$.  $``$$``$

More recently, Peter Høyer has shown the existence of a one query protocol for the same problem \[private communication\].

### 5.3 Query versus Time Complexity Issues

The above algorithm only reduces the *query complexity* to $`f_s`$. The *time complexity* of the protocol is another matter, as we did not explain how to perform the final measurement along the $`\psi `$ axes in a time-efficient way. This question, whether there exists a tractable implementation of the unitary mapping

$`|s`$ $``$ $`{\displaystyle \frac{1}{\sqrt{q}}}({\displaystyle \underset{x𝔽_q}{}}\chi (x+s)|x+|\text{dummy}),`$
is discussed and solved in an independent article.

## 6 Conclusion

We have established a connection between the construction of weighing matrices in combinatorics, and the design of new quantum algorithms. It was shown how every weighing matrix leads to a query problem that has a more efficient quantum solution than is possible classically. The earlier known results of Bernstein & Vazirani and Grover were shown to be specific instances of this more general problem.

Starting from Paley’s construction of Hadamard matrices, we used the structure of quadratic residues over finite fields to give a more explicit example of a Weighing Matrix Problem. This led to the definition of the Shifted Legendre Sequence Problem, which has a constant quantum query complexity, compared to a logarithmic classical query complexity.

Although the results in this article only concern the *query complexity* of black-box problems, it should be viewed as the first step towards the construction of quantum protocols that are also time-efficient and that deal with more realistic problems. Constructions of Hadamard matrices that are especially interesting in this context are, for example, the complex Hadamard matrices of Turyn and the Hadamard matrices of the dihedral group type. Also, the time-efficiency of the quantum solution of (a generalization of) the Shifted Legendre Sequence Problem was proven more recently in .

## Acknowledgments

Harry Buhrman, Peter Høyer, Paul Vitányi and Ronald de Wolf are thanked for several useful discussions. Mike Mosca and Alain Tapp are especially acknowledged for their valid criticism of an earlier version of this article, which was made possible by the hospitality of the CACR at the University of Waterloo.

This work has been supported by the Institute for Logic, Language and Computation in Amsterdam, the EU fifth framework project QAIP IST-1999-11234, and the TALENT grant S 62-552 of the Netherlands Organization for Scientific research (NWO).

## Appendix A Quadratic Residues of Finite Fields

This appendix describes some standard results about quadratic residues and Legendre symbols over finite fields. For more background information one can look up references like  or .

### A.1 Finite Field Factoids

Let $`q=p^k`$ denotes a power of an odd prime $`p`$. There always exists a generator $`\zeta `$ for the multiplicative group $`𝔽_q^{}=𝔽_q\{0\}`$. This means that the sequence $`\zeta ,\zeta ^2,\zeta ^3,\mathrm{}`$ will generate all non-zero elements of $`𝔽_q`$. As this is a set of size $`q1`$, it follows that $`\zeta ^q=\zeta `$, and hence $`\zeta ^{(q1)}=1`$. Hence we have the equivalence relation

$`\zeta ^i=\zeta ^j`$ if and only if $`i=jmod(q1)`$
for every integer $`i`$ and $`j`$.

We now turn our attention to the definition of the *generalized Legendre symbol* $`\chi :𝔽_q\{1,0,+1\}`$ which is defined by:

$`\chi (i)`$ $`:=`$ $`\{\begin{array}{cc}\hfill 0& \text{ if }i=0\hfill \\ \hfill +1& \text{ if }j0:j^2=i\hfill \\ \hfill 1& \text{ if }j:j^2i\text{.}\hfill \end{array}`$
By the above mentioned equivalence relation, the quadratic expression $`(\zeta ^j)^2=\zeta ^{2j}=\zeta ^i`$ is correct if and only if $`2j=imodq1`$. As $`p`$ is odd, $`q1`$ will be even, and hence there can only exists a $`j`$ with $`(\zeta ^j)^2=\zeta ^i`$ when $`i`$ is even. Obviously, if $`i`$ is even, then $`\zeta ^j`$ with $`j=\frac{i}{2}`$ gives a solution to our quadratic equation. This proves that $`50\%`$ of the elements of $`𝔽_q^{}`$ are a quadratic residue with $`\chi (x)=+1`$, while the other half has $`\chi (x)=1`$. In short: $`\chi (\zeta ^i)=(1)^i`$, and hence for the total sum of the function values: $`_x\chi (x)=0`$.

### A.2 Multiplicative Characters over Finite Fields

The rule $`\chi (\zeta ^i)\chi (\zeta ^j)=\chi (\zeta ^{i+j})`$, in combination with $`\chi (0)=0`$, shows that the Legendre symbol $`\chi `$ is a *multiplicative character* with $`\chi (x)\chi (y)=\chi (xy)`$ for all $`x,y𝔽_q`$.

###### Definition 6 (Multiplicative characters over finite fields)

The function $`\chi :𝔽_q`$ is a *multiplicative character* if and only if $`\chi (xy)=\chi (x)\chi (y)`$ for all $`x,y𝔽_q`$. The constant function $`\chi (x)=1`$ is called the trivial character. (We do not consider the other trivial function $`\chi (x)=0`$.)

See  for the usage of multiplicative characters in number theory. Some of the properties that we will use in this article are: $`\chi (1)=1`$, if $`\chi `$ is nontrivial, then $`\chi (0)=0`$, the inverse of nonzero $`x`$ obeys $`\chi (x^1)=\chi (x)^1=\overline{\chi (x)}`$, and $`_x\chi (x)=0`$ for nontrivial $`\chi `$.

With these properties we can prove the following fact that we use in the article.

###### Fact 6 (Near orthogonality of shifted characters)

Consider a nontrivial character $`\chi :𝔽_q`$. For the ‘complex inner product’ between two $`\chi `$-sequences that are shifted by $`s`$ and $`r𝔽_q`$ it holds that

$`{\displaystyle \underset{x𝔽_q}{}}\overline{\chi (x+r)}\chi (x+s)`$ $`=`$ $`\{\begin{array}{cc}\hfill q1& \text{if }s=r\text{,}\hfill \\ \hfill 1& \text{if }sr.\hfill \end{array}`$
Proof:  (For the quadratic character, these are simple instances of so-called *Jacobsthal sums*; see for example Section 6.1 in .) Rewrite

$`{\displaystyle \underset{x𝔽_q}{}}\overline{\chi (x+r)}\chi (x+s)`$ $`=`$ $`{\displaystyle \underset{x𝔽_q}{}}\overline{\chi (x)}\chi (x+\mathrm{\Delta })`$
with $`\mathrm{\Delta }:=sr`$. If $`s=r`$ this sum equals $`q1`$. Otherwise, we can use the fact that $`\overline{\chi (x)}\chi (x+\mathrm{\Delta })=\chi (1+x^1\mathrm{\Delta })=\chi (\mathrm{\Delta })\chi (\mathrm{\Delta }^1+x^1)`$ (for $`x0`$) to reach

$`{\displaystyle \underset{x𝔽_q}{}}\overline{\chi (x)}\chi (x+\mathrm{\Delta })`$ $`=`$ $`\chi (\mathrm{\Delta }){\displaystyle \underset{x𝔽_{q}^{}{}_{}{}^{}}{}}(\mathrm{\Delta }^1+x^1).`$
Earlier we noticed that $`_x\chi (x)=0`$, and therefore in the above summation (where the value $`x=0`$ is omitted) we have $`_x\chi (x^1+\mathrm{\Delta }^1)=\chi (\mathrm{\Delta }^1)`$.

This confirms that indeed

$`\chi (\mathrm{\Delta }){\displaystyle \underset{x𝔽_{q}^{}{}_{}{}^{}}{}}\chi (x^1+\mathrm{\Delta }^1)`$ $`=`$ $`1,`$
which finishes the proof.  $``$$``$

Note that the above property should not be confused with the orthogonality relation

$`{\displaystyle \underset{x𝔽_q}{}}\overline{\chi (x)}\chi ^{}(x)`$ $`=`$ $`\{\begin{array}{cc}\hfill q1& \text{if }\chi =\chi ^{}\hfill \\ \hfill 0& \text{if }\chi \chi ^{}\hfill \end{array}`$
between two (possibly different) characters $`\chi `$ and $`\chi ^{}`$.