= Solution
First use the allowed one-query algorithm to learn $p=x_1\mathbin\oplus x_2$ exactly. This restricted two-index <Boolean quantum oracle> is realized by relabelling indices $1,2$ in a single query to the original input. Measure its output and choose the second query classically.
If $p=0$, the first two bits agree and their common value is the majority, irrespective of $x_3$. Query $x_1$ and output it. If $p=1$, the first two bits cancel in the vote, so query $x_3$ and output it. Thus
$$
\boxed{\operatorname{MAJ}(x)=\begin{cases}x_1,&x_1\oplus x_2=0,\\x_3,&x_1\oplus x_2=1.\end{cases}}
$$
The <exact two-query majority algorithm> uses one parity query and one ordinary bit query on every branch, and is correct on all eight inputs. Together with the lower bound this proves \b[$Q_E(\operatorname{MAJ})=2$].
Back to article page
