format: text

text:
# Quantum Search on Bounded-Error Inputs

## 1 Introduction

One of the main successes of quantum computing is Grover’s algorithm . It can search an $`n`$-element space in $`O(\sqrt{n})`$ steps, which is quadratically faster than any classical algorithm. The algorithm assumes oracle access to the elements in the space, meaning that in unit time it can decide whether the $`i`$th element is a solution to its search problem or not. In some more realistic settings we can efficiently make such an oracle ourselves. For instance, if we want to decide satisfiability of an $`m`$-variable Boolean formula, the search space is the set of all $`n=2^m`$ truth assignments, and we can efficiently decide whether a given assignment satisfies the formula. However, in these cases the decision is made without any error probability. In this paper we study the complexity of quantum search if we only have bounded-error access to the elements in the space.

More precisely, suppose that among $`n`$ Boolean values $`f_1,\mathrm{},f_n`$ we want to find a solution (if one exists), i.e., an index $`j`$ such that $`f_j=1`$. For each $`i`$ we have at our disposal an algorithm $`F_i`$ that computes the bit $`f_i`$ with two-sided error: if $`f_i`$ is 1 then the algorithm outputs 1 with probability, say, at least $`9/10`$, and if $`f_i=0`$ then it outputs 0 with probability at least $`9/10`$. Grover’s algorithm is no longer applicable in this bounded-error setting, at least not directly, because the errors in each step will quickly add up to something uncontrollably large. Accordingly, we need to do something different to get a quantum search algorithm that works here. We will measure the complexity of our quantum search algorithms by the number of times they call the underlying algorithms $`F_i`$. Clearly, the $`\mathrm{\Omega }(\sqrt{n})`$ lower bound for the standard error-less search problem, due to Bennett, Bernstein, Brassard, and Vazirani , also applies to our more general setting. Our aim is to give a matching upper bound.

An obvious but sub-optimal quantum search algorithm is the following. By repeating $`F_i`$ $`k=O(\mathrm{log}n)`$ times and outputting the majority value of the $`k`$ outcomes, we can compute $`f_i`$ with error probability at most $`1/100n`$. If we then copy the answer to a safe place and reverse the computation to clean up (most of) the workspace, then we get something that is sufficiently “close” to perfect oracle access to the $`f_i`$ bits to just treat it as such. Now we can apply Grover’s algorithm on top of this, and because quantum computational errors add linearly , the overall difference with perfect oracle access will be negligibly small. This solves the bounded-error quantum search problem using $`O(\sqrt{n}\mathrm{log}n)`$ repetitions of the $`F_i`$’s, which is an $`O(\mathrm{log}n)`$-factor worse than the lower bound. Below we will refer to this algorithm as “the simple search algorithm”.

A relatively straightforward improvement over the simple search algorithm is the following. Partition the search space into $`n/\mathrm{log}^2n`$ blocks of size $`\mathrm{log}^2n`$ each. Pick one such block at random. We can find a potential solution (an index $`j`$ in the chosen block such that $`f_j=1`$, if there is such a $`j`$) in complexity $`O(\mathrm{log}n\mathrm{log}\mathrm{log}n)`$ using the simple search algorithm, and then verify that it is indeed 1 with error probability at most $`1/n`$ using another $`O(\mathrm{log}n)`$ invocations of $`F_j`$. Applying Grover search on the space of all $`n/\mathrm{log}^2n`$ blocks, we obtain an algorithm with complexity $`O(\sqrt{n/\mathrm{log}^2n})O(\mathrm{log}n\mathrm{log}\mathrm{log}n+\mathrm{log}n)=O(\sqrt{n}\mathrm{log}\mathrm{log}n)`$.

A further improvement comes from doing the splitting recursively: we can use the improved upper bound to do the computation of the “inner” blocks, instead of the simple search algorithm. Using $`T(n)`$ to denote the complexity on search space of size $`n`$, this gives us the recursion

$$T(n)d\left(T(\mathrm{log}^2n)\sqrt{\frac{n}{\mathrm{log}^2n}}+\mathrm{log}n\right)$$

for some constant $`d>0`$. This recursion resolves to complexity $`O(\sqrt{n}c^{\mathrm{log}^{}n})`$ for some constant $`c>0`$. It is similar to (and inspired by) the communication complexity protocol for the disjointness problem of Høyer and de Wolf .

Apart from being rather messy, this improved algorithm is still not optimal. The main result of this paper is to give a relatively clean algorithm that uses the optimal number $`O(\sqrt{n})`$ of repetitions to solve the bounded-error search problem. Our algorithm uses a kind of “carrot-and-stick” approach that may be of more general interest. Roughly speaking, it starts with a uniform superposition of all $`F_i`$. It then amplifies all branches of the computation that give answer 1. These branches include solutions, but they also include “false positives”: branches corresponding to the $`1/10`$ error probability of $`F_i`$’s where $`f_i=0`$. We then “push these back” by testing whether a 1-branch is a real positive or a false one (i.e., whether $`f_i=1`$ or not) and removing most of the false ones. Interleaving these amplify and push-back steps properly, we can amplify the weight of the solutions to a constant using $`O(\sqrt{n})`$ repetitions. At this point we just do a measurement, see a potential solution $`j`$, and verify it classically by running $`F_j`$ a few times.

As an application of our bounded-error quantum search algorithm, in Section 4 we give optimal quantum algorithms for constant-depth AND-OR trees in the query complexity setting. For any constant $`d`$, we need only $`O(\sqrt{N})`$ queries for the $`d`$-level AND-OR tree, improving upon the earlier $`O(\sqrt{N}(\mathrm{log}N)^{d1})`$ algorithms of Buhrman, Cleve, and Widgerson . Matching lower bounds of $`\mathrm{\Omega }(\sqrt{N})`$ were already shown for such AND-OR trees, using Ambainis’ quantum adversary method . Finally, in Section 5 we indicate how the ideas presented here can be cast more generally in terms of amplitude amplification.

## 2 Preliminaries

Here we briefly sketch the basics and notation of quantum computation, referring to the book by Nielsen and Chuang  for more detail. An $`m`$-qubit state is a linear combination of all classical $`m`$-bit states

$$|\varphi =\underset{i\{0,1\}^m}{}\alpha _i|i,$$

where $`|i`$ denotes the basis state $`i`$ (a classical $`m`$-bit string), the amplitude $`\alpha _i`$ is a complex number, and $`_i|\alpha _i|^2=1`$. We view $`|\varphi `$ as a $`2^m`$-dimensional column vector. A measurement of state $`|\varphi `$ will give $`|i`$ with probability $`|\alpha _i|^2`$, and the state will then collapse to the observed $`|i`$. A non-measuring quantum operation corresponds to applying a unitary $`(=`$ linear and norm-preserving$`)`$ transformation $`U`$ to the vector of amplitudes. If $`|\varphi `$ and $`|\psi `$ are quantum states on $`m`$ and $`m^{}`$ qubits, respectively, then the two-register state $`|\varphi |\psi =|\varphi |\psi `$ corresponds to the $`2^{m+m^{}}`$-dimensional vector that is the tensor product of $`|\varphi `$ and $`|\psi `$.

The setting of query complexity is as follows. For input $`x\{0,1\}^n`$, a query corresponds to the unitary transformation $`O`$ that maps $`|i,b,z|i,bx_i,z`$. Here $`i[n]`$ and $`b\{0,1\}`$; the $`z`$-part corresponds to the workspace, which is not affected by the query. A $`T`$-query quantum algorithm has the form $`A=U_TOU_{T1}\mathrm{}OU_1OU_0`$, where the $`U_k`$ are unitary transformations, independent of $`x`$. This $`A`$ depends on $`x`$ only via the $`T`$ applications of $`O`$. The algorithm starts in initial all-zero state $`|\stackrel{}{0}`$ and its output (which is a random variable) is obtained from observing some dedicated part of the final superposition $`A|\stackrel{}{0}`$.

## 3 Optimal Quantum Algorithm for Bounded-Error Search

In this section we describe our quantum algorithm for bounded-error search. The following two facts generalize, respectively, the Grover search and the error-reduction used in the algorithms we sketched in the introduction.

###### Fact 1 (Amplitude amplication )

Let $`S_0`$ be the unitary that puts a ‘-’ in front of the all-zero state $`|\stackrel{}{0}`$, and $`S_1`$ be the unitary that puts a ‘-’ in front of all basis states whose last qubit is $`|1`$. Let $`A|\stackrel{}{0}=\mathrm{sin}(\theta )|\varphi _1|1+\mathrm{cos}(\theta )|\varphi _0|0`$ where angle $`\theta `$ is such that $`0\theta \pi /2`$ and $`\mathrm{sin}^2(\theta )`$ equals the probability that a measurement of the last register of state $`A|\stackrel{}{0}`$ yields a ’1’. Set $`G=AS_0A^1S_1`$. Then $`GA|\stackrel{}{0}=\mathrm{sin}(3\theta )|\varphi _1|1+\mathrm{cos}(3\theta )|\varphi _0|0`$.

Amplitude amplification is a process that is used in many quantum algorithms to increase the success probability. Amplitude amplification effectively implements a rotation by an angle $`2\theta `$ in a two-dimensional space (a space different from the Hilbert space acted upon) spanned by $`|\varphi _1|1`$ and $`|\varphi _0|0`$. Note that we can always apply amplitude amplification regardless of whether the angle $`\theta `$ is known to us or not.

###### Fact 2 (Error-reduction)

Suppose $`A|\stackrel{}{0}=\sqrt{p}|\varphi _b|b+\sqrt{1p}|\varphi _{1b}|1b`$, where $`b\{0,1\}`$ and $`p9/10`$. Then using $`O(\mathrm{log}(1/\epsilon ))`$ applications of $`A`$ and majority-voting, we can build a unitary $`E`$ such that $`E|\stackrel{}{0}=\sqrt{q}|\psi _b|b+\sqrt{1q}|\psi _{1b}|1b`$ with $`q1\epsilon `$, and $`|\psi _{b/1b}`$ possibly of larger dimension than $`|\varphi _{b/1b}`$ (because of extra workspace).

We will recursively interleave these two facts to get a quantum search algorithm that searches the space $`f_1,\mathrm{},f_n\{0,1\}`$. We assume each $`f_i`$ is computed by unitary $`F_i`$ with success probability at least $`9/10`$. Let $`\mathrm{\Gamma }=\{j:f_j=1\}`$ be the set of solutions, and $`t=|\mathrm{\Gamma }|`$ its size (which is unknown to our algorithm). The goal is to find an element in $`\mathrm{\Gamma }`$ if $`t1`$, and to output ‘no solutions’ if $`t=0`$.

We will build an algorithm that has a superposition of all $`j[n]`$ in its first register, a growing second register that contains workspace and other junk, and a 1-qubit third register indicating whether something is deemed a solution or not. The algorithm will successively increase the weight of the basis states that simultaneously have a solution in the first register and a 1 in the third.

Consider an algorithm $`A`$ that runs all $`F_i`$ once in superposition, producing the state $`A|\stackrel{}{0}`$, which we rewrite as

$$\frac{1}{\sqrt{n}}\underset{i=1}{\overset{n}{}}|i\left(\sqrt{p_i}|\psi _{i,1}|1+\sqrt{1p_i}|\psi _{i,0}|0\right)=\mathrm{sin}(\theta )|\varphi _1|1+\mathrm{cos}(\theta )|\varphi _0|0,$$

where $`p_i`$ is the probability that $`F_i`$ outputs 1, the states $`|\psi _{i,b}`$ describe the workspace of the $`F_i`$, and $`\mathrm{sin}(\theta )^2=_{i=1}^np_i9t/10n`$.

The idea is to apply a round of amplitude amplification to $`A`$ to amplify the $`|1`$-part from $`\mathrm{sin}(\theta )`$ to $`\mathrm{sin}(3\theta )`$. This will amplify both the good states $`|j|1`$ for $`j\mathrm{\Gamma }`$ and the “false positives” $`|j|1`$ for $`j\mathrm{\Gamma }`$ by a factor of $`\mathrm{sin}(3\theta )/\mathrm{sin}(\theta )3`$ (here we didn’t write the second register). We then apply an error-reduction step to reduce the amplitude of the false positives, setting “most” of its third register to 0. These two steps together form a new algorithm that puts almost 3 times as much amplitude on the solutions as $`A`$ does, and that puts less amplitude on the false positives than $`A`$. We then repeat the amplify-reduce steps on this new algorithm to get an even better algorithm, and so on.

Let us be more precise. Our algorithm will consist of a number of rounds. In round $`k`$ we will have a unitary $`A_k`$ that produces

$$A_k|\stackrel{}{0}=\alpha _k|\mathrm{\Gamma }_k|1+\beta _k|\overline{\mathrm{\Gamma }}_k|1+\sqrt{1\alpha _k^2\beta _k^2}|H_k|0,$$

where $`\alpha _k,\beta _k`$ are non-negative reals, $`|\mathrm{\Gamma }_k`$ is a unit vector whose first register only contains $`j\mathrm{\Gamma }`$, $`|\overline{\mathrm{\Gamma }}_k`$ is a unit vector whose first register only contains $`j\mathrm{\Gamma }`$, and $`|H_k`$ is a unit vector. If we measure the first register of the above state, we will see a solution (i.e. some $`j\mathrm{\Gamma }`$) with probability at least $`\alpha _k^2`$. $`A_1`$ is the above algorithm $`A`$, which runs the $`F_i`$ in superposition. Initially, $`\alpha _1^29t/10n`$ since each solution contributes at least $`9/10n`$. We want to make the good amplitude $`\alpha _k`$ grow by a factor of almost 3 in each round.

Amplitude amplification step. For each round $`k`$, define $`\theta _k[0,\pi /2]`$ by $`\mathrm{sin}(\theta _k)^2=\alpha _k^2+\beta _k^2`$. Applying amplitude amplification ($`G_k=A_kS_0A_k^1S_1`$) gives us the state $`G_kA_k|\stackrel{}{0}`$, which we may write as

$$\frac{\mathrm{sin}(3\theta _k)}{\mathrm{sin}(\theta _k)}\alpha _k|\mathrm{\Gamma }_k|1+\frac{\mathrm{sin}(3\theta _k)}{\mathrm{sin}(\theta _k)}\beta _k|\overline{\mathrm{\Gamma }}_k|1+\sqrt{1\left(\frac{\mathrm{sin}(3\theta _k)}{\mathrm{sin}(\theta _k)}\right)^2(\alpha _k^2+\beta _k^2)}|H_k|0.$$

We applied $`A_k`$ twice and $`A_k^1`$ once, so the complexity goes up by a factor of 3.

Error-reduction step. Conditional on the qubit in the third register being 1, the error-reduction step $`E_k`$ now does majority voting on $`O(k)`$ runs of the $`F_j`$ (for all $`j`$ in superposition) to decide with error at most $`1/2^{k+5}`$ whether $`f_j=1`$. It adds one 0-qubit as the new third register and maps (ignoring its workspace, which is added to the second register)

$$\begin{array}{ccc}E_k|j|1|0\hfill & =& a_{jk}|j|1|1+\sqrt{1a_{jk}^2}|j|1|0\hfill \\ E_k|j|0|0\hfill & =& |j|0|0\hfill \end{array}$$

where $`a_{jk}^211/2^{k+5}`$ if $`f_j=1`$ and $`a_{jk}^21/2^{k+5}`$ if $`f_j=0`$. This way, $`E_k`$ removes most of the false positives.

Putting $`A_{k+1}=E_kG_kA_k`$ and defining $`\alpha _{k+1}`$, $`\beta _{k+1}`$, $`|\mathrm{\Gamma }_{k+1}`$, $`|\overline{\mathrm{\Gamma }}_{k+1}`$, and $`|H_{k+1}`$ appropriately, we now have

$$A_{k+1}|\stackrel{}{0}=\alpha _{k+1}|\mathrm{\Gamma }_{k+1}|1+\beta _{k+1}|\overline{\mathrm{\Gamma }}_{k+1}|1+\sqrt{1\alpha _{k+1}^2\beta _{k+1}^2}|H_{k+1}|0.$$

Here the second register has grown by the workspace used in the error-reduction step $`E_k`$, as well as by the qubit that previously was the third register. The good amplitude has grown in the process:

$$\alpha _{k+1}\alpha _k\frac{\mathrm{sin}(3\theta _k)}{\mathrm{sin}(\theta _k)}\sqrt{11/2^{k+5}}.$$

Since $`xx^3/6\mathrm{sin}(x)x`$, we have

$$\frac{\mathrm{sin}(3\theta _k)}{\mathrm{sin}(\theta _k)}39\theta _k^2/2.$$

Accordingly, as long as $`\theta _k`$ is small, $`\alpha _k`$ will grow by a factor of almost 3 in each round. On the other hand, the weight of the false positives goes down rapidly:

$$\beta _{k+1}\beta _k\frac{\mathrm{sin}(3\theta _k)}{\mathrm{sin}(\theta _k)}\frac{1}{\sqrt{2^{k+5}}}.$$

We now analyze the number $`m`$ of rounds that we need to make the good amplitude large. In general, we have $`\mathrm{sin}(\theta _k)^2=\alpha _k^2+\beta _k^2`$, hence $`\theta _k^22(\alpha _k^2+\beta _k^2)`$ for the domain we are interested in. Here $`\alpha _k^29^{k1}\alpha _1^2`$ and $`\beta _k^2\frac{1}{10}(9/2^6)^{k1}`$. Note

$`{\displaystyle \underset{k=1}{\overset{m1}{}}}\theta _k^2`$ $``$ $`2{\displaystyle \underset{k=1}{\overset{m1}{}}}\alpha _k^2+\beta _k^2`$
$``$ $`2{\displaystyle \underset{k=1}{\overset{m1}{}}}9^{k1}\alpha _1^2+2{\displaystyle \underset{k=1}{\overset{m1}{}}}{\displaystyle \frac{1}{10}}(9/2^6)^{k1}`$
$``$ $`29^{m1}\alpha _1^2+1/4.`$
Therefore, $`m`$ rounds of the above process amplifies the good amplitude $`\alpha _k`$ to

$`\alpha _m`$ $``$ $`\alpha _1{\displaystyle \underset{k=1}{\overset{m1}{}}}{\displaystyle \frac{\mathrm{sin}(3\theta _k)}{\mathrm{sin}(\theta _k)}}\sqrt{11/2^{k+5}}`$
$``$ $`\alpha _1{\displaystyle \underset{k=1}{\overset{m1}{}}}\left(39\theta _k^2/2\right)\left(11/2^{k+5}\right)`$
$`=`$ $`\alpha _13^{m1}{\displaystyle \underset{k=1}{\overset{m1}{}}}\left(13\theta _k^2/2\right)\left(11/2^{k+5}\right)`$
$``$ $`\alpha _13^{m1}\left(1{\displaystyle \frac{3}{2}}{\displaystyle \underset{k=1}{\overset{m1}{}}}\theta _k^2{\displaystyle \underset{k=1}{\overset{m1}{}}}{\displaystyle \frac{1}{2^{k+5}}}\right)`$
$``$ $`\alpha _13^{m1}\left(1{\displaystyle \frac{3}{2}}(29^{m1}\alpha _1^2+1/4)1/16\right)`$
$``$ $`\alpha _13^{m1}\left(1/239^{m1}\alpha _1^2\right).`$
In particular, whenever the (unknown) number $`t`$ of solutions lies in the interval $`[n/9^{m+1},n/9^m]`$, equivalently $`9^m[n/9t,n/t]`$, then we have

$$\frac{1}{3^m\sqrt{10}}\sqrt{\frac{9t}{10n}}\alpha _1\sqrt{\frac{t}{n}}\frac{1}{3^m}.$$

This implies

$$\alpha _m0.04,$$

so the probability of seeing a solution after $`m`$ rounds is at least $`0.0016`$. By repeating this classically a constant number of times, say 1000 times, we can bring the success probability close to 1 (note to avoid confusion: these 1000 repetitions are not part of the definition of $`A_m`$ itself).

The complexity $`C_k`$ of the operation $`A_k`$, in terms of number of repetitions of the $`F_i`$ algorithms, is given by the recursion

$$C_1=1\text{ and }C_{k+1}=3C_k+O(k),$$

where the $`3C_k`$ is the cost of amplitude amplification and $`O(k)`$ is the cost of error-reduction. This implies $`C_m=O(_{k=1}^{m1}k3^{mk1})=O(3^m).`$

We now give the full algorithm when the number of solutions is unknown:

* Algorithm: Quantum search on bounded-error inputs

1. for $`m=0`$ to $`\mathrm{log}_9(n)1`$ do:

    1. run $`A_m`$ 1000 times
        2. verify the 1000 measurement results, each by $`O(\mathrm{log}n)`$ runs of the corresponding $`F_j`$
        3. if a solution has been found, then output a solution and stop
    2. Output ‘no solutions’

This finds a solution with high probability if one exists. The complexity is

$$\underset{m=0}{\overset{\mathrm{log}_9(n)1}{}}1000O(3^m)+1000O(\mathrm{log}n)=O(3^{\mathrm{log}_9(n)})=O(\sqrt{n}).$$

If we know that there is at least one solution but we don’t know how many there are, then, using a modification of our algorithm as in , we can find a solution using an expected number of repetitions in $`O(\sqrt{N/t})`$, where $`t`$ is the (unknown) number of solutions. This is quadratically faster than classically, and optimal for any quantum algorithm.

## 4 Optimal Upper Bounds for AND-OR Trees

A $`d`$-level AND-OR tree on $`N`$ Boolean variables is a Boolean function that is described by a depth-$`d1`$ tree with interleaved ORs and ANDs on the nodes and the $`N`$ input variables as leaves. More precisely, a 0-level AND-OR tree is just an input variable, and if $`f_1,\mathrm{},f_n`$ all are $`d`$-level AND-OR trees on $`m`$ variables, each with an AND (resp. OR) as root, then OR$`(f_1,\mathrm{},f_n)`$ (resp. AND) is a $`(d+1)`$-level AND-OR tree on $`N=nm`$ variables. AND-OR trees can be converted easily into OR-AND trees and vice versa using De Morgan’s laws, if we allow negations to be added to the tree.

Consider the two-level tree on $`N=n^2`$ variables with an OR as root, ANDs as its children, and fanout $`n`$ in both levels. Each AND-subtree can be quantum computed by Grover’s algorithm with one-sided error using $`O(\sqrt{n})`$ queries (we let Grover search for a ‘0’, and output 1 if we don’t find any), and the value of the OR-AND tree is just the OR of those $`n`$ values. Accordingly, the construction of the previous section gives an $`O(\sqrt{n}\sqrt{n})=O(\sqrt{N})`$ algorithm with two-sided error. This is optimal up to a constant factor .

More generally, for $`d`$-level AND-OR trees we can apply the above algorithm recursively to obtain an algorithm with $`O(c^{d1}\sqrt{N})`$ queries. Here $`c`$ is the constant hidden in the $`O()`$ of the result of the previous section. For each fixed $`d`$, this complexity is $`O(\sqrt{N})`$, which is optimal up to a constant factor . It improves upon the $`O(\sqrt{N}(\mathrm{log}N)^{d1})`$ algorithm given in .

Our query complexity upper bound also implies that the minimal degree among $`N`$-variate polynomials approximating AND-OR is $`O(\sqrt{N})`$ . Whether this upper bound on the degree is optimal remains open. The best known lower bound for the 2-level case is $`\mathrm{\Omega }(N^{1/4}\sqrt{\mathrm{log}N})`$ .

## 5 Amplitude Amplification with Imperfect Verifier

In this section we view our construction in a more general light.

Suppose we are given some classical randomized algorithm $`A`$ that succeeds in solving some problem with probability $`p`$. In addition, we are given a Boolean function $`\chi `$ that takes as input an output from algorithm $`A`$, and outputs whether it is a solution or not. Then, we may find a solution to our problem by repetition. We first apply algorithm $`A`$, obtaining some candidate solution, which we then give as input to the verifier $`\chi `$. If $`\chi `$ outputs that the candidate indeed is a solution, we output it and stop, and otherwise we repeat the process by reapplying $`A`$. The probability that this process terminates by outputting a solution within the first $`\mathrm{\Theta }(\frac{1}{p})`$ iterations of the loop, is lower bounded by a constant.

A quantum analogue of boosting the probability of success is to boost the *amplitude* of being in a certain subspace of a Hilbert space. Thus far, amplitude amplification  has assumed that we are given a perfect verifier $`\chi `$: whenever a candidate solution is found, we can determine with certainty whether it is a solution or not. Formally, we model this by letting $`\chi `$ be computed by a deterministic classical subroutine or an exact quantum subroutine.

The main result of this paper may be viewed as an adaptation of amplitude amplification to the situation where the verifier is not perfect, but sometimes makes mistakes. Instead of a deterministic subroutine for computing $`\chi `$, we are given a bounded-error randomized subroutine, and instead of an exact quantum subroutine, we are given a bounded-error quantum subroutine. Previously, the only known technique for handling such cases has been by straightforward simulation of a perfect verifier: construct a subroutine for computing $`\chi `$ with error $`\frac{1}{2^k}`$ by repeating a given bounded-error subroutine of order $`\mathrm{\Theta }(k)`$ times and then use majority voting. Using such direct simulations, we may construct good but sub-optimal quantum algorithms, like the $`O(\sqrt{n}\mathrm{log}n)`$ query algorithm for quantum search of the introduction. Here, we have introduced a modification of the amplitude amplification process that allows us to efficiently deal with imperfect verifiers. Essentially, our result says that imperfect verifiers are as good as perfect verifiers (up to a constant multiplicative factor in the complexity).

### Acknowledgments

We thank Richard Cleve for useful discussions, as well as for hosting MM and RdW at the University of Calgary, where most of this work was done.


text:
# Dynamic scaling in spin glasses

## Abstract

We present new Neutron Spin Echo (NSE) results and a revisited analysis of historical data on spin glasses, which reveal a pure power-law time decay of the spin autocorrelation function $`s(Q,t)=S(Q,t)/S(Q)`$ at the glass temperature $`T_g`$, each power law exponent being in excellent agreement with that calculated from dynamic and static critical exponents deduced from macroscopic susceptibility measurements made on a quite different time scale. It is the first time that this scaling relation involving exponents of different physical quantities determined by completely independent experimental methods is stringently verified experimentally in a spin glass. As spin glasses are a subgroup of the vast family of glassy systems also comprising structural glasses and other non-crystalline systems the observed strict critical scaling behaviour is important. Above the phase transition the strikingly non-exponential relaxation, best fitted by the Ogielski (power-law times stretched exponential) function, appears as an intrinsic, homogeneous feature of spin glasses.

The glass transition, characterised by a dramatic slowing down of the dynamics without any noticeable change in the spatial order, is a generic phenomenon, seen in systems as different as disordered magnets, polymers and biological substances. In spite of its universality and of intense experimental and theoretical efforts it is still controversial whether the glass transition in structural glasses is a gradual freezing or a phase transition. The difficulty to identify the nature of the glass transition is due to the absence of an observable order parameter analagous to magnetization in the low temperature phase, usually a key quantity in the study of phase transitions. This is due to the absence of any static spacial fingerprint; instead, the order parameter appears in the dynamics parisi ; goetze . In fact, the ”snapshot” structure factor $`S(Q)=S(Q,t=0)`$, which reflects the short and medium range static correlations, shows no essential change when passing from the high temperature liquid (or paramagnet) to the low temperature frozen glass phase. In this situation the observation of dynamic scaling relations, which are the direct consequence of the homogeneity hypothesis in the vicinity of a critical instability widom  can reveal the crucial signature of a true phase transition.

In spin glasses, which are the simplest realisations of glassy systems from the experimental as well as from the theoretical point of view, a phase transition is well establishedfischer ; young . Low frequency dynamic susceptibility as well as the non linear part of the static susceptibility follow the scaling relations and the analysis leads to accurate determination of the static critical exponents $`\gamma `$, $`\beta `$, $`\delta `$ and of the dynamic exponent $`z`$ levy ; nadine ; paulsen ; mydosh . The verification of scaling relations between certain exponents, determined by completely independent experimental methods, however, was up to now impossible due to the absence of any obvious critical behaviour on other physical quantities, like the specific heat. Here we show that scaling relations can also be verified experimentally in spin glasses. New Neutron Spin Echo (NSE) results and also a revisited analysis of historical dataferi-murani ; feri ; eusrs  show a pure power-law time decay of the spin autocorrelation function $`s(Q,t)=S(Q,t)/S(Q,t=0)`$ at the glass temperature $`T_g`$, with a power law decay exponent which is in excellent agreement with that calculated from the dynamic and static critical exponents deduced from zero and low frequency susceptibility measurements. The interplay between neutron scattering, macroscopic magnetic, hyperfine field measurements, and simulations has always been decisive in understanding spin glasses and these results constitute the strongest experimental evidence yet for a true phase transition with a non-conventional order parameter; they also imply that the prominently non-exponential relaxation is an intrinsic, homogeneous feature of spin glasses.

Most of the information about glass transitions comes from the high temperature unfrozen phase, where thermodynamic equilibrium is easily reached without any long-time drifts and aging phenomena. In spin glasses, where the magnetization is always zero, the fundamental parameter is the mean spin autocorrelation function $`q(tt^{^{}})=<𝐒_𝐢(𝐭).𝐒_𝐢(𝐭^{^{}})>`$ where $`𝐒_𝐢`$ is the spin at a site $`i`$ and the average runs over all sites and configurations of the sample. Critical behaviour in the paramagnetic phase is seen in the non-linear susceptibility (or ”spin glass susceptibility”). levy ; nadine ; paulsen ; mydosh  Below $`T_g`$ the Edwards Anderson order parameter q(t$`\mathrm{})=\text{<}𝐒_𝐢(𝐭=\mathrm{𝟎})𝐒_𝐢(𝐭\mathrm{})\text{>}`$, becomes non-zero.edwards-anderson ; parisi  Neutron Spin Echo spectroscopy measures the scattering function $`S(Q,t)`$ and after normalization by $`S(Q,0)`$ delivers a direct determination of the autocorrelation function $`q(t)=s(Q0,t)`$. NSE covers a time domain ranging from 10-12 s to some 10-8 s, i.e. from characteristic microscopic times up to times, which already belong to the ”long” time relaxation domain. The first NSE experiment ever performed on a glassy system was made on the reference spin glass CuMn 5% in 1979 feri-murani  and the results strongly influenced subsequent thinking on (spin)glass dynamics. For the first time is was shown that non-conventional dynamics is not limited to the spin glass phase but also extends into the paramagnetic phase well above Tg. Non-exponential and Q-independent relaxation occurs in a large temperature range up to 2-3 Tg, which can arguably be identified with the Griffiths phase griffiths . For about T$`>`$1.2 Tg the relaxation can be described by a broad distribution of Arrhenius activation energies. Closer to Tg, however, a more dramatic slowing down sets in, which can be interpreted as the footprint of a phase transition with a critical region of usual extent. Here we report on the first detailed analysis of $`s(Q,t)`$ around Tg in spin glasses, based on enhanced quality data obtained by using new generation NSE spectrometers.

For an accurate determination of the NSE spectra we chose Au0.86Fe0.14. AuFe is a classical metallic Heisenberg spin glass with significant local anisotropy dorothee  and with strong ferromagnetic correlations which amplify the magnetic scattering in the forward direction so improving the ratio between the magnetic signal and all non-magnetic (structural) contributions, i.e. the signal to noise ratio. The sample was a polycrystalline disc 0.5 mm thick with a diameter of 37 mm prepared by arc melting of the constituents. It was subsequently cold worked, homogenised at 900oC, annealed at 550oC and then quenched and kept in liquid Nitrogen. aufe\_prep  Given the vicinity to the percolation threshold xc ($``$15.5% at. Fe), above which ferromagnetism sets in,coles  the annealing and quenching procedure was repeated before every series of measurements. The NSE data were collected at the high resolution spectrometer IN15 of ILL in15  at an incoming wavelength of 0.8 nm for Q = 0.4 and 0.8 nm-1 respectively. These results were supplemented by measurements at the wide angle NSE spectrometer SPAN of BENSC span  at an incoming wavelength of 0.45 nm for 0.6 nm$`{}_{}{}^{1}`$Q $``$ 2.6 nm-1. We used the paramagnetic NSE set-up, which directly delivers the magnetic part of the NSE signal and for this reason no background correction was required. All NSE spectra were normalized against the resolution function of the spectrometers, determined with the sample well below Tg, at 2 K, where the spin dynamics is completely frozen. A small part of the sample was taken out for dc susceptibility measurements with a commercial SQUID magnetometer at the HMI and for ac susceptibility measurements, which were made from 10 Hz up to 10 KHz with the MAGLAB setup at the Physics and Astronomy Department, University of Leeds. The spin glass temperature of $`T_g=41.0\pm 0.3`$ K was determined from the maximum of the static susceptibility.

The normalised intermediate scattering function s(Q,t) of Au0.86Fe0.14 at Q = 0.4 nm-1 is shown in Fig. 1 plotted in a log-log scale. The spectra span a dynamic range of three orders of magnitude and by combining spectra collected at two wavelengths on IN15 and SPAN the time domain of the observation is extended up to almost 4 decades (Fig.2). The time dependence of the experimental $`s(Q,t)`$ is impressively similar to that of the numerical $`q(t)`$ found in large scale Ising spin glass simulations, which revealed the existence of a phase transition in three-dimensional Ising spin glasses.ogielski  From quite general scaling arguments,HH  at a continuous phase transition relaxation must be of the form $`t^xf(t/\tau (T))`$ where $`\tau (T)`$ diverges as $`(TT_g)^z`$, and $`f`$ is a non-universal function to be determined for each system. For a spin glass the power law exponent $`x`$ is related to the standard critical exponents through $`x=(d2+\eta )/2z`$ ogielski . Here $`\eta `$ is the Fisher or ”anomalous dimension” exponent and $`z`$ is again the dynamical exponent. The Ising simulations showed that, as Tg is approached from above, $`q(t)`$ is strongly non-exponential. Ogielski chose to represent $`f`$ by the stretched exponential or KWW function, familiar in fragile glass dynamics. Excellent fits were obtained with $`q(t)t^xexp((t/\tau (T))^\beta )`$ and $`T`$ dependent $`\tau `$ and $`\beta `$. (The KWW $`\beta `$ is not to be confused with the critical exponent $`\beta `$). He and others found a temperature dependent $`\beta `$ tending to near 1/3 at $`T_g`$ and increasing with $`T`$. ogielski ; coniglio ; ian ; goetze  The most important point for our data analysis is that precisely at $`T_g`$ dynamic scaling predicts a pure power law decay for the autocorrelation function : $`q(t)t^x`$. This rule is quite general; its functional form does not depend on details such as the Ising character of the spins but the value of $`x`$ depends on the exponents for the particular system under study. Scaling therefore gives a unique opportunity for describing the NSE spectra at $`T_g`$ in terms of exponents determined by completely independent dynamic and non-linear macroscopic susceptibility measurements.

As seen on Fig. 1, for T$``$Tg we found s(Q,t) $``$ t-x and the lines represent the best fits to the data with x=0.116$`\pm `$0.007 and 0.025$`\pm `$0.005 at T=40.6($``$Tg) and 30.7 K respectively. Above Tg the relaxation is also strongly non-exponential. As shown in Figure 2, pure exponential as well as stretched exponential decay (without the power-law prefactor) can be definitively ruled out at all T in the range studied. In fact at 45.6 K, the fit with the Ogielski function leads to $`\chi ^2`$ = 0.28, which is significantly lower than $`\chi ^2`$ = 0.55, the value obtained for the stretched exponential and $`\chi ^2`$ = 1.67 for the simple exponential respectively. The power law part of the Ogielski function, which holds at short times, describes the main part of the relaxation above Tg and the spectra of Figure 1 lead to an accurate determination of the effective power law exponent x as function of T . On the other hand, the stretched exponential only influences the tail of the relaxation so the parameters $`\tau (T)`$ and $`\beta `$ are obtained here to low accuracy: $`\tau (T)`$ 0.3 ns and $`\beta `$1 at 55.8 and 50.8 K whereas $`\tau (T)`$22 ns and $`\beta `$0.66 at 45.7 K. In similar systems, muon spin depolarisation measurements which are sensitive to the time range from 10 ns up to about 50 $`\mu `$s (i.e. in the range where the relaxation above Tg is mainly described by the stretched exponential) showed that in fact $`\beta `$ approaches about 1/3 at Tg bob ; amit  as expected by the simulations. Susceptibility measurements very close to $`T_g`$ in an Ising spin glass show a similar limiting value of $`\beta `$.gunnarsson  Furthermore, recent magnetic-field dependent muon spin depolarisation measurements on several AgMn spin glasses, analysed assuming an Ogielski-like decay of the correlations, lead to values of $`x`$ tending to $``$0.15 at Tg in agreement with our results.amit

The large dynamic range covered by our data and their accuracy allow us to distinguish between a simple stretched exponential decay, the Ogielski function with $`\beta =1`$ (power law times simple exponential), and the full Ogielski function; the full function is needed to give an acceptable fit of the data over the whole time and temperature range.

In spin glasses the normalized $`s(Q,t)`$ does not vary with $`Q`$, in dramatic contrast to the strong Q-dependence of the dynamics in ferromagnets. This remarkable Q-independence of the relaxation in spin glasses feri-murani  implies that the NSE s(Q,t) can be identified with q(t) and analysed in the frame of dynamic scaling. The NSE spectra of Au0.86Fe0.14 collected on IN15 for $`Q=0.4`$ and $`0.8`$ nm-1 and on SPAN for 0.6 nm$`{}_{}{}^{1}`$Q$``$2.6 nm-1 confirmed this behaviour. Fig. 3 compares, in a lin-log plot, spectra collected at 45.6 and 40.6 K for Q= 0.04 Å-1 and 0.08 Å-1 respectively. The data almost overlap although the Q-values differ by a factor of two and the magnetic intensity decreases by almost a factor of 3, which explains the larger error bars of the data set at 0.08 Å-1. The Q-independence of s(Q,t) was an important check of the high quality of our samples in a concentration range close to ferromagnetism. It also implies that s(Q,t) can be directly related to the macroscopic ac susceptibility $`\chi `$(Q=0, $`\omega `$) = S(Q=0)\[1-s(Q=0,t)\]/kT.feri  The meaning of this equation is quite simple: $`s(Q,t)`$ is the fraction of the total magnetic response S(Q) which does not relax before the time t, in other words $`s(Q,t)`$ is the part of S(Q) which cannot respond to a driving field of frequency $`1/t`$. Figure 4 shows the NSE spectra for $`TT_g`$ combined with $`s(Q,t)`$ values deduced from macroscopic dynamic (a.c.) susceptibility measurements on the same sample. The data follow the power law decay over an impressively large range of at least 9 orders of magnitude in time.

The impressive similarity between the experimental s(Q,t) and the decay of q(t) found in large scale simulations and more particularly the simple power law decay found at and below Tg incited us to revisit the historical CuMn 5% data. Below Tg, the spectra of CuMn 5% were combined with macroscopic dynamic (ac) susceptibility measurements and thus covered more than 9 orders of magnitude in time down to the microscopic time scale.feri  These data, plotted now on a log-log scale, also reveal a power law decay below Tg over an impressively large range of at least 9 orders of magnitude in time as shown in Fig. 5. Above Tg, which is at 27.5 K, the power law holds only at short times and the decay can be described by the Ogielski function with $`\beta `$1 just as in AuFe 14%.

The values of the exponent x, plotted versus the reduced temperature T/Tg in Fig. 6, are similar for both metallic systems. This confirms the similarity of the dynamic behaviour of AuFe, AgMn and CuMn systems around Tg, pointed out by Uemura after comparing the NSE spectra of CuMn 5% with $`\mu `$SR spectra of AgMn and AuFe.uemura  As already mentioned, dynamic scaling relates the value of x at Tg to the static and dynamic critical exponents, which can be determined completely independently from non-linear and ac macroscopic susceptibility measurements. Well established values of these exponents are available for a AgMn spin glass levy  and for CuMn and AgMn spin glasses doped with Au,nadine  in agreement with more recent data on AuFe 14%. The static exponents lead to $`\eta `$= 2-$`\gamma /\nu `$ = 0.23$`\pm `$0.3 and the dynamic exponent z=5.3$`\pm `$0.8 was determined by low frequency susceptibility measurements. From these values we calculate x=0.116$`\pm `$0.026 in excellent agreement with x=0.116$`\pm `$0.007, the value we have observed on Au0.86Fe0.14 at Tg. It is important to note that the value of $`x`$ in these basically Heisenberg spin glasses is considerably larger than that seen numerically ogielski  or experimentally gunnarsson  in Ising spin glasses where $`x0.07`$.

Our results represent the first verification of scaling in spin glasses relating quantities of very different nature and measured by different methods on very different time scales, namely the microscopic time dependence of the autocorrelation function at times between the microscopic time and $`10^7`$ seconds on the one hand, and the macroscopic a.c. susceptibility at time scales greater than $`10^3`$ seconds together with the static non-linear susceptibility on the other. This agreement constitutes a most compelling evidence for a true phase transition in spin glasses at Tg. In addition, this demonstration of critical relaxation characterisic of a phase transition also implies that the entire non-exponential temporal relaxation in these spin glasses is an intrinsic, homogeneous feature, as already evidenced by Uemura after comparing $`\mu `$sR, NSE and dynamic susceptibility data.uemura  This conclusion is in obvious contrast to the clear evidence for the heterogeneous origin of the non-exponential relaxation in some structural glasses, where also no clear signature of a phase transition could be found.glasses  The clear evidence for a phase transition with a non-conventional order parameter and intrinsic, homogeneous non-exponential relaxation in spin glasses, a member of the large family of glassy systems, which also include structural glasses, other non-crystalline systems and living matter, is of particular importance in view of the unsolved central question of the nature of the glass transition in general.

ACKNOWLEDGMENTS

C. Pappas would like to acknowledge fruitful discussions with R. Cywinski and S. Kilcoyne, who also made possible the susceptibility measurements at the Physics & Astronomy Department of the University of Leeds. P Manuel would like to acknowledge postdoctoral support from EPSRC Research Grant GR/M77260.


text:
# NEUTRINO ANOMALIES

## 1 Introduction

Solar and atmospheric neutrino data show that lepton flavour is violated, and give the two established evidences for physics beyond the SM that we have today (the SM and its first flaw both appeared in 1968). Atmospheric, solar, reactor and $`\nu `$ beam data can be fully explained by neutrino oscillations with?)

$$\begin{array}{cc}|\mathrm{\Delta }m_{23}^2|=(2.7\pm 0.4)10^3\mathrm{eV}^2,& \mathrm{sin}^22\theta _{23}=1.00\pm 0.04,\\ \mathrm{\Delta }m_{12}^2=(7.1\pm 0.6)10^5\mathrm{eV}^2,& \mathrm{tan}^2\theta _{12}=0.45\pm 0.06.\end{array}$$
(1)
Although the specific dependence on neutrino path-length and energy predicted by oscillations has not yet been fully tested, present data exclude all alternative interpretations which have been proposed.

It is plausible that the physics behind present discoveries is a $`3\times 3`$ Majorana neutrino mass matrix. This is in fact what one gets adding to the SM Lagrangian higher dimensional operators (which parameterize the low-energy effects of new physics too heavy to be directly probed):

$$=_{\mathrm{SM}}+\frac{m_{ij}}{v^2}\frac{(L_iH)(L_jH)}{2\mathrm{\Lambda }_L}+\mathrm{}$$

Maybe we are observing the first manifestation of a new scale of nature, $`\mathrm{\Lambda }_L10^{14}\mathrm{GeV}`$, similarly to what happened in 1896, when operators suppressed by the electroweak scale $`v=174\mathrm{GeV}`$ were first seen as radioactivity by Becquerel. LHC will directly explore physics at the electroweak scale in $``$2008.

Accessing the neutrino scale could be not so fast. If the theoretical scheme outlined above is true we have seen 4 of the 9 Majorana parameters contained in $`m_{ij}`$. Planned oscillation experiments seem capable of measuring all 6 Majorana parameters which affect oscillations; neutrino-less double-beta ($`0\nu 2\beta `$) experiments could discover violation of total lepton number and measure one more parameter.

Alternatively, neutrino experiments might discover something else which does not fit well in the above scheme. Present neutrino data show a few unconfirmed anomalies:

1. A reanalysis?) of Heidelberg-Moscow?) $`0\nu 2\beta `$ data claims $`|m_{ee}|\mathrm{eV}`$.
2. LSND?) claims $`\overline{\nu }_\mu \overline{\nu }_e`$ with small $`\theta `$ and $`\mathrm{\Delta }m^2\mathrm{eV}^2`$.
3. NuTeV?) claims $`\nu _\mu /`$iron couplings $`1\%`$ away from the SM.
4. The apparent observation of cosmic rays above the GZK cut-off might be related to neutrino masses ($`\nu _{\mathrm{UHE}}\nu _{\mathrm{CMB}}Z`$ with $`m_\nu \mathrm{eV}`$) or to problems with energy calibration.

We discuss possible interpretations of the first three hints (within the SM and beyond) and their signals. Since this is not established physics, we unavoidably touch controversial issues: I try to present what seems true to me without hiding problems and signalling the most controversial points. Hopefully future data will lead to a definite conclusion, maybe confirming one or more of these anomalies.

## 2 Heidelberg-Moscow

Neutrino masses distort the end-point spectrum of $`\beta `$ decays. From studies of $`{}_{}{}^{3}\mathrm{H}{}_{}{}^{3}\mathrm{He}e\overline{\nu }_e`$ the Mainz experiment sets the 95% CL bound $`m_\nu <2.2\mathrm{eV}`$ (Troitsk has a similar sensitivity)?).

Some nuclei cannot $`\beta `$-decay. For example $`{}_{32}{}^{76}\mathrm{Ge}`$ cannot $`\beta `$-decay to $`{}_{33}{}^{76}\mathrm{As}`$ that is heavier, so it $`\beta \beta `$ decays as $`{}_{32}{}^{76}\mathrm{Ge}{}_{34}{}^{76}\mathrm{Se}ee\overline{\nu }_e\overline{\nu }_e`$ $`(Q=2038.6\text{keV})`$. Various experiments have observed this and other analogously rare SM processes. If neutrinos have Majorana masses, the $`L`$-violating decay $`{}_{32}{}^{76}\mathrm{Ge}{}_{34}{}^{76}\mathrm{Se}ee`$ has a non zero amplitude proportional to $`m_{ee}`$, the $`ee`$ entry of the Majorana neutrino mass matrix. The experimental signal is two electrons with total kinetic energy equal to the $`Q`$ value of the decay. A reanalysis?) of the Heidelberg-Moscow (HM) data?) shown in fig. 1 claimed a $`(2.2÷3.1)\sigma `$ evidence for $`0\nu 2\beta `$. To properly understand HM data one needs to know that the $`0\nu 2\beta `$ signal is a peak at $`Q=2038.6\text{keV}`$ with known width, $`\sigma _E1.6\text{keV}`$ given by the energy resolution, emerging over the $`\beta \beta `$ and other backgrounds, which are not well known. The evidence in?) was claimed assuming

$$\text{data}=\text{(flat background)}+\text{(}0\nu 2\beta \text{ peak)}$$

and distinguishing the two components trough a spectral analysis, restricted to data in a small search window around $`Q`$ with few $`\sigma _E`$ size. The continuous line in fig. 1 shows the resulting best-fit: we obtain a $`2.0\sigma `$ evidence. The evidence depends on the choice of the window size: we have chosen the window where data mostly look like a peak, maximizing the evidence for peakaaaThe authors of?) claim that the restriction in the window search is not a critical arbitrary choice, in apparent disagreement with?). The claim in?) refers to a fit of an average sample of simulated data (generated under some assumption), while ref.?) finds that the restriction in the window search turns out to be a critical arbitrary choice when analyzing the real data.. Employing a large window (which would be the right choice, if the background were really flat) the evidence decreases to $`0.8\sigma `$.

Furthermore, the HM spectrum contains a few other apparent peaks, some around the energies of faint $`\gamma `$ lines of $`{}_{}{}^{214}\text{Bi}`$ (a radioactive impurity present in the apparatus). Fitting all data using all the information we have

$$\text{data}=\text{(Bi peaks)}+\text{(cte background)}+\text{(}0\nu 2\beta \text{ peak)}$$

we find a $`1.2\sigma `$ evidencebbbThe tentative identification of some of the spurious peaks in the HM spectrum with faint 214Bi $`\gamma `$ lines proposed in?) had been criticized in?,?), because their intensity appeared incompatible with the intense 214Bi $`\gamma `$ lines, clearly present in HM data. This issue has been clarified and the relative intensities are now compatible within $`2\sigma `$. The initial estimate has been corrected by a factor of 6 (as first noticed in footnote 9 of a revised version of?), there is a trivial normalization error in the published HM data?)) times another $`𝒪(\text{few})`$ factor related to pile-up effects (computed assuming that $`{}_{}{}^{214}\text{Bi}`$ is located in the copper part of the detector)?). as illustrated by the dashed line in fig. 1. Other reanalyses performed along similar lines and precisely described by their authors find $`1.1\sigma `$?), $`1.46\sigma `$?), less than $`1\sigma `$?) (these authors combine HM?) and IGEX?) data. Both experiments use 76Ge with a similar energy resolution and background level. IGEX has about 5 times less statistic and finds a slight deficit of events around the $`0\nu 2\beta `$ $`Q`$ value, where HM finds a slight excess). In conclusion, the hint for $`0\nu 2\beta `$ is not statistically significant. HM data would contain an evidence for $`0\nu 2\beta `$ if one could show that the background around $`Q`$ is lower than what fig. 1 seems to indicate.

We now shift topic and study what oscillation data imply on $`m_{ee}`$, assuming $`3`$ neutrinos with Majorana masses. Therefore we rewrite $`|m_{ee}|`$ in terms of mixing angles $`\theta _{ij}`$, neutrino masses $`m_{1,2,3}`$ and Majorana phases $`\alpha ,\beta `$

$$|m_{ee}|=\left|\underset{i}{}V_{ei}^2m_i\right|=\left|\mathrm{cos}^2\theta _{13}(m_1\mathrm{cos}^2\theta _{12}+m_2e^{i\alpha }\mathrm{sin}^2\theta _{12})+m_3e^{i\beta }\mathrm{sin}^2\theta _{13}\right|.$$

Using a global fit of all oscillation data?), we plot in fig. 2 the $`|m_{ee}|`$ range at $`90\%`$ CL as function of the lightest neutrino mass?). The darker regions in fig. 2 show the remaining uncertainty in $`|m_{ee}|`$ due to the Majorana phases that we would achieve if the present best-fit values of oscillation parameters in eq. (1) were confirmed with infinite precision (we are assuming $`\theta _{13}=0`$).

Combining the HM?) bound on $`|m_{ee}|`$ with solar data which point to less than maximal mixing $`\theta _{12}`$ one can derive an interesting bound on the mass $`m_\nu `$ of almost-degenerate neutrinos?)

$$m_\nu <1.0(1.5)h\mathrm{eV}\text{ at 90 (}99\%\text{) CL.}$$
(2)
The factor $`h1`$ parameterizes the uncertainty in the $`0\nu 2\beta `$ nuclear matrix element (see sect. 2.1 of ref.?)). Our bound holds under the untested assumption that neutrinos are Majorana particles, and can be evaded adding e.g. Dirac neutrino masses. Cosmology gives a tighter limit?,?), $`m_\nu <0.23\text{eV}`$ at $`95\%`$ CL, under the untested assumption that a minimal inflationary model describes structure formation and can be evaded by e.g. compensating $`\nu `$ free-streaming with a primordial tilt in the power spectrum.

In the future, the sensitivity of $`0\nu 2\beta `$ experiments to neutrino masses should improve more significantly than cosmology and $`\beta `$-decay. Fig. 2 shows that planned $`0\nu 2\beta `$ experiments, which could reach a sensitivity in $`|m_{ee}|`$ of few meV, should see a signal if the spectrum of neutrinos is ‘inverted’ (i.e. $`\mathrm{\Delta }m_{23}^2<0`$) or ‘quasi degenerate’ (i.e. $`\mathrm{min}m_i>\mathrm{\hspace{0.17em}0.05}\mathrm{eV}`$).

## 3 LSND

Both the LSND?) and Karmen?) experiments study $`\overline{\nu }_\mu `$ obtained from $`\mu ^+`$ decay at rest, that therefore have a well known energy spectrum up to $`52.8\mathrm{MeV}`$. The search for $`\overline{\nu }_\mu \overline{\nu }_e`$ is performed using the detection reaction $`\overline{\nu }_epne^+`$, that has a large cross section. The detectors try to identify both the $`e^+`$ and the $`n`$ (via the $`2.2\mathrm{MeV}`$ $`\gamma `$ emitted when the neutron is captured by a proton). The neutrinos travel for $`L30\mathrm{m}`$ in LSND and $`L17.5\mathrm{m}`$ in Karmen.

LSND finds an evidence for $`\overline{\nu }_\mu \overline{\nu }_e`$, that ranges between 3 to $`7\sigma `$ depending on how data are analyzed. This happens because LSND has a poor signal/background ratio: choosing the selection cuts as in?) the LSND sample contains 1000 background events and less than 100 signal events, distinguished only on a statistical basis. The statistical significance of the LSND signal depends on how cuts are chosen, and it is crucial that all sources of background have been correctly computed. The main backgrounds are cosmic rays and $`\nu _e`$ misidentification. The final LSND result $`P(\overline{\nu }_\mu \overline{\nu }_e)=(2.6\pm 0.8)\mathrm{\hspace{0.17em}10}^3`$ can be explained by oscillations with $`\mathrm{\Delta }m^2>\mathrm{\hspace{0.17em}0.1}\mathrm{eV}^2`$ (see?,?) for the precise range).

Karmen is cleaner than LSND but has a few times less statistics and shorter base-line. Karmen finds $`15`$ events versus an expected background of $`15.8`$ events, excluding the part of the ($`\mathrm{\Delta }m^2,\theta `$) range suggested by LSND with larger $`\mathrm{\Delta }m^2>\mathrm{\hspace{0.17em}2}\mathrm{eV}^2`$, while at smaller $`\mathrm{\Delta }m^2`$ the longer path-length makes LSND more sensitive than Karmen. The LSND anomaly is being tested as $`\nu _\mu \nu _e`$ by the MiniBoone experiment, which has quite different systematics.

If confirmed, the LSND anomaly will require a significant revision of the standard picture. In fact, oscillations between the three SM neutrinos are described by two independent squared neutrino mass differences, allowing to explain only two of the three atmospheric, solar and LSND neutrino anomalies as oscillations.

One possible global explanation of the three anomalies is that an extra sterile neutrino generates one of them. The sterile neutrino can be used to generate either the LSND or the solar or the atmospheric anomaly, or some combination of them. Only the first possibility is now compatible with data?,?)cccThe other possibilities would remain strongly disfavoured even if possible reasons for being more cautious would apply. R. Foot, hep-ph/0210393 suggests that theoretical errors might have been underestimated in analyses of NC enriched SK data which disfavour atmospheric sterile oscillations. Furthermore, bounds on the sterile component involved in solar oscillations would be weakened if solar models underestimate the 8B flux. H. Pas et al., hep-ph/0209373  suggest that adjusting all the small mixing angles allowed by a $`4\nu `$ framework might weaken the bounds. R. Foot, hep-ph/0210393 suggests that scanarios with $`\nu _\mu \nu _s`$ atmospheric oscillations provide a global fit of all neutrino data with $`\chi ^2/\mathrm{dof}291/276`$, which is acceptable. This is true, but the goodness-of-fit (gof) test based on the value of the total $`\chi ^2`$ is inefficient when $`\mathrm{dof}1`$: it may assign an acceptable gof probability to a solution which is already excluded. This issue was discussed in the context of analyses of solar data in?) and can be exemplified by recalling that, according to global fits of solar and KamLAND data?), the LOW solution has been excluded but its naïve gof is still acceptable (presently it has $`\chi ^2/\mathrm{dof}=89/91`$).. According to this possibility, named ‘3+1’ oscillations in the jargon, $`\nu _\mu \nu _e`$ oscillations at the LSND frequency proceed trough $`\nu _\mu \nu _s\nu _e`$, so that the effective $`\nu _e\nu _\mu `$ mixing angle at the LSND frequency is $`\theta _{\mathrm{LSND}}\theta _{es}\theta _{\mu s}`$. Due to this ‘product rule’?) the LSND anomaly somewhat conflicts with bounds on $`\theta _{es}`$ and $`\theta _{\mu s}`$ from $`\nu _e`$ and $`\nu _\mu `$ disappearance experiments. The situation is quantitatively summarized in table 1 and fig. 4. The part of the LSND region still marginally compatible with other oscillation experiments has $`\mathrm{\Delta }m_{\mathrm{LSND}}^2\mathrm{eV}^2`$ and $`\mathrm{sin}^22\theta _{\mu s}0.2`$ (for more details see?,?)).

Furthermore, cosmology disfavours such 3+1 interpretation of the LSND anomaly for two different reasons: because 3+1 oscillations thermalize a fourth sterile neutrino, and because it is heavy. Since both issues are still controversial, we now try to summarize what cosmology is really telling.

Massive neutrinos make galaxies less clustered: recent global fits of cosmological data find $`m_\nu <\mathrm{\hspace{0.17em}1}\mathrm{eV}`$ (the analysis performed by the WMAP team gives the strongest bound?), criticized by?) who find appropriate a more conservative treatment of data at small scale and of bias). The bound on $`m_\nu `$ gets slightly relaxed if there are $`N_\nu =4`$ thermalized neutrinos?). 3+1 oscillations indeed thermalize $`N_\nu =4`$ neutrinos before the big-bang nucleosynthesis (BBN) epoch, and $`N_\nu =4`$ seems not compatible with BBN. Assuming standard cosmology, the dominant bound on $`N_\nu `$ comes from the BBN prediction for the 4He primordial abundancy, using as input the baryon asymmetry extracted from CMB data. A global fit of cosmological data gives $`N_\nu =2.6\pm 0.2`$?), which apparently excludes $`N_\nu =4`$ and even disfavours $`N_\nu =3`$. One can avoid these conclusions by enlarging the error on the 4He primordial abundancy, since its determination is still controversial. In table 1 we tried to make a quantitative statement, which can be criticized telling either that it underestimates or that it overestimates the impact of cosmology.

When data started disfavouring interpretations of the LSND anomaly based on sterile neutrinos, other more exotic solutions were proposed. None of them can fully reconcile of data.

Since solar and atmospheric oscillations have been established in neutrinos but not yet in anti-neutrinos, one can try to explain all anomalies assuming a CPT-violating neutrino spectrum. The larger $`\mathrm{\Delta }m^2`$ between $`\overline{\nu }_{e,\mu ,\tau }`$ is used to explain the LSND anomaly, and the smaller $`\mathrm{\Delta }m^2`$ could be in the atmospheric or in the solar range, at the price of sacrificing some solar?) or atmospheric?,?) anti-neutrino data. These CPT-violating spectra are now somewhat disfavoured, as quantitatively summarized in table 1. KamLAND will soon precisely probe CPT in the solar sector. Doing the same in the atmospheric sector would require a dedicated $`\overline{\nu }_\mu `$ long-baseline (LBL) experiment or a dedicated atmospheric experiment such as Monolith.

The LSND anomaly might be produced by a non standard ($`\mathrm{\Delta }L=2`$!) decay mode $`\overline{\mu }\overline{\nu }_e\overline{e}\overline{\nu }`$?). It affects electroweak precision data and the $`\overline{e}`$ spectrum in $`\overline{\mu }`$ decays. The latter signal is under test at TWIST. This $`\overline{\mu }`$ decay interpretation of the LSND anomaly is disfavoured by Karmen, since unlike oscillations it does not exploit the fact that LSND has a longer path-length?); a more precise quantitative statement than the one in table 1 will be possible if LSND will analyze their data in this context.

In conclusion, the recent experimental progress has disfavoured all proposed interpretations of the LSND anomaly. Some of them are not yet excluded, and will be tested by future experiments, as summarized in table 1.

## 4 NuTeV

The NuTeV collaboration?) reported a $`3\sigma `$ anomaly in the NC/CC ratio of deep-inelastic muon-neutrino/nucleon scattering. The effective $`\nu _\mu `$ coupling to left-handed quarks is found to be about $`1\%`$ lower than the best fit SM prediction.

The NuTeV collaboration sent both a $`\nu _\mu `$ and a $`\overline{\nu }_\mu `$ beam on an iron target. Scattering events were detected by a calorimeter. The muon produced in CC events gives a long track, while the hadrons in NC events give a short track. NuTeV statistically distinguishes NC from CC events putting a cut on the track length. The ratios of neutral–current (NC) to charged–current (CC) deep-inelastic neutrino–nucleon scattering total cross–sections, $`R_\nu `$ and $`R_{\overline{\nu }}`$, are free from the uncertainties on the neutrino fluxes and contain the most interesting information. We recall the tree-level SM prediction for these quantities. Including only first generation quarks, for an isoscalar target, and to leading order, $`R_\nu `$ and $`R_{\overline{\nu }}`$ are given by

$$R_\nu =\frac{\sigma (\nu 𝒩\nu X)}{\sigma (\nu 𝒩\mu X)}=g_L^2+rg_R^2R_{\overline{\nu }}=\frac{\sigma (\overline{\nu }𝒩\overline{\nu }X)}{\sigma (\overline{\nu }𝒩\overline{\mu }X)}=g_L^2+\frac{1}{r}g_R^2,$$

where

$$r\frac{\sigma (\overline{\nu }𝒩\overline{\mu }X)}{\sigma (\nu 𝒩\mu X)}=\frac{3\overline{q}+q}{3q+\overline{q}}\frac{1}{2}$$

and $`q=(u+d)/2`$ and $`\overline{q}`$ denote the fraction of the nucleon momentum carried by quarks and antiquarks, respectively. In this approximation the single parameter $`r`$ accounts for the uncertain QCD dynamics and, after including various significant but ‘trivial’ correctionsdddCuts, QED and electroweak corrections, iron contains more neutrons than protons, the charm threshold,… In principle, only a careful job is needed to include all these effects correctly., the NuTeV data can be presented as a measurement of $`g_L^2`$ and $`g_R^2`$, the NC/CC ratio of effective $`\nu _\mu q_L`$ and $`\nu _\mu q_R`$ couplings, predicted by the SM to be

$$g_L^2=\frac{1}{2}\mathrm{sin}^2\theta _\mathrm{W}+\frac{5}{9}\mathrm{sin}^4\theta _\mathrm{W},g_R^2=\frac{5}{9}\mathrm{sin}^4\theta _\mathrm{W}.$$

The big ellipse in fig. 4 is the NuTeV result, obtained summing in quadrature statistical and systematic uncertainties. $`g_L`$ is found to be $`3\sigma `$ below its SM prediction.

The difference of the effective couplings $`g_L^2g_R^2`$ (‘Paschos–Wolfenstein ratio’?)) does not depend on $`r`$

$$R_{\mathrm{PW}}\frac{R_\nu rR_{\overline{\nu }}}{1r}=\frac{\sigma (\nu 𝒩\nu X)\sigma (\overline{\nu }𝒩\overline{\nu }X)}{\sigma (\nu 𝒩\mathrm{}X)\sigma (\overline{\nu }𝒩\overline{\mathrm{}}X)}=g_L^2g_R^2=\frac{1}{2}\mathrm{sin}^2\theta _\mathrm{W}.$$
(3)
The value of $`R_\nu `$ measured at NuTeV is consistent with previous experiments, such as CCFR?). Unlike CCFR, NuTeV has two separate $`\nu _\mu `$ and $`\overline{\nu }_\mu `$ beams: this is the main improvement because, under the above assumptions, allows to get rid of the unprecisely known partonic structure of the nucleon using $`R_{\mathrm{PW}}`$. The NuTeV value of $`R_{\mathrm{PW}}`$ is $`3\sigma `$ below its SM prediction.

Doing precision physics with iron is a delicate task. NLO QCD corrections have not taken into account by the NuTeV collaboration. They cancel out in the ideal $`R_{\mathrm{PW}}`$ observable?) and therefore probably cannot explain the NuTeV anomaly (caution is needed because what NuTeV really measures is a few $`10\%`$ different from the total cross sections which appear in the ideal PW observable).

Parton distributions $`q(x)`$ are extracted from global fits, usually performed under two simplifying assumptions: $`s(x)=\overline{s}(x)`$ and $`u^p(x)=d^n(x)`$. These approximation could fail, at the level of precision reached by NuTeV. In presence of a momentum asymmetry $`q^{}=_0^1x[q(x)\overline{q}(x)]𝑑x`$ the ideal PW observable shifts as

$$R_{\mathrm{PW}}=\frac{1}{2}\mathrm{sin}^2\theta _\mathrm{W}+\text{(EW corrections)}+(1.3+\text{QCD corrections})(u^{}d^{}s^{}).$$

Both $`u^{}d^{}`$ (isospin violation) and $`s^{}`$ (strange momentum asymmetry) might produce the NuTeV anomaly compatibly with other data.

Isospin violating effects of order $`u^{}d^{}(m_um_d)/\mathrm{\Lambda }_{\mathrm{QCD}}`$ could reconcile NuTeV with the SM compatibly with all other available data. Some detailed computations performed replacing QCD with more tractable phenomenological models suggest that, due to cancellations, isospin-violating effects are somewhat too small?). It is not clear if a QCD computation would lead to the same conclusion.

The theoretical situation concerning $`s^{}`$ is similar. Since a nucleon contains 3 quarks (rather than three antiquarks) one expects that $`s`$ and $`\overline{s}`$ carry comparable (but not equal) fractions of the total nucleon momentum. Non perturbative fluctuations like $`pK\mathrm{\Lambda }`$ are expected to give $`s`$ harder than $`\overline{s}`$ since $`K`$ is lighter than $`\mathrm{\Lambda }`$. Indeed $`s^{}>0`$ could explain the NuTeV anomaly. Some model computations suggest that $`s^{}`$ is too small?), but again it is not clear how reliable they are. The $`s^{}`$ issue can also be addressed relying on experimental data. The global parton fit in?) found a hint for a $`s^{}`$ of the desired sign and magnitude. However, a $`s^{}`$ with the opposite sign was suggested by an analysis of charm production data, obtained and analyzed by the NuTeV collaboration?). This analysis is unreliable for various reasons listed in a note added to?). Charm production data probe the strange content of the nucleon in a powerful way, but we are not able of reliably guessing what they imply for $`s^{}`$. It seems worth performing a professional analysis, even if this not an easy task.

Finally, nuclear effects?) could affect $`R_\nu `$ and $`R_{\overline{\nu }}`$, but only at low momentum transfer and apparently not in a way that allows to reconcile NuTeV data with the SM?). In part, nuclear effects are automatically included in the NuTeV analysis, based on their own parton distributions obtained fitting only iron data.

In conclusion, testing and eventually excluding such SM ‘systematic effects’ which can produce the NuTeV anomaly seems to be a difficult jobeeeUsing a different terminology, this means that in the meantime in view of ‘additional uncertainties’ NuTeV is not inconsistent with the SM.. Therefore, it is useful to speculate about possible new physics interpretations which might have cleaner signatures. Unfortunately, no particularly compelling new physics with distinctive signatures has been found. The problem is that charged lepton couplings agree with the SM and have been measured about 10 times more accurately than neutrino couplings. Proposals which overcome this problem look exotic, while more plausible possibilities work only if one deals with constraints in a ‘generous’ way or introduces and fine-tunes enough free parameters. For example, mixing the $`Z`$ boson with an extra $`Z^{}`$ boson modifies NC neutrino couplings, but also NC couplings of charged leptons ($`\mathrm{}_L`$ and $`\nu `$ are unified in the same $`\mathrm{SU}(2)_L`$ doublet). New physics that only affects the gauge boson propagators cannot fit the NuTeV anomaly due to the same constraints. Neutrino oscillations do not work. A reduction of neutrino couplings due to a $`1\%`$ mixing with sterile singlets does not work, because CC neutrino couplings have been too precisely tested by $`\mu `$ decay together with precision data. Combinations of the above effects with enough unknown parameters can workfffFor example, mixing with a sterile singlet together with a heavy higgs fits all data if one also assumes that some extra unspecified new physics affects $`M_W`$ and therefore ignores this measurement?). A failure of the SM fit of electroweak data would support the case for new physics, but at the moment we do not see any convincing problem.. The new physics could either be heavy with sizable couplings (so that future colliders should see it) or light with small couplings (e.g. a $`Z^{}`$ with few GeV mass and negligible mixing with the $`Z`$).

## 5 Acknowledgements

I learnt most of the topics discussed here thanks to collaborations with S. Davidson, S. Forte, P. Gambino, N. Rius and F. Vissani.