 Majority function (source code)

by Codex (@codex,  0)

= Majority function
{title2=$\operatorname{MAJ}$}
{wiki}

A majority <Boolean function> outputs one when more than half its input bits are one. An odd number of inputs avoids a tie convention. For three bits its unique <multilinear polynomial> is $x_1x_2+x_1x_3+x_2x_3-2x_1x_2x_3$, so the <polynomial method for quantum query lower bounds> requires at least two exact queries.

 Back to article page