Imagine you discover an alien artifact. It has a single button on it which you can push. Every time you push the button the artifact emits \(n+1\) qubits. A scientist who does not know any quantum mechanics determines that the (to him) bits emitted have a specific form. The first \(n\) bits are completely random.

The final bit is determined by \(\langle a,x\rangle\) where \(a\) is
an \(n\)-bit string which he does not yet know. \(a \cdot x\) means
the inner product between \(a\) and \(x\) defined as \(\sum_{j=1}^n
a_jx_j \mod 2\) where \(a_j\) and \(x_j\) are the \(j`th bits of
:math:`a\) and \(x\). We say that the artifact is an *example oracle for
the parity function*.

The goal in this example is to learn the value of \(a\). The classical
scientist can do this by obtaining just a few more than \(n\) examples
from the oracle. To see this, imagine the scientist got lucky and read
out a string like \(0000100000|1\). The bit to the right of the
\(|\) is the special “last” bit. This then immediately tells him that
the 5th bit of \(a\) is 1. If the last bit had been 0, you would know
that the 5th bit of \(a\) was 0. Now, because the whole problem is
*linear*, any example yields one bit of information about \(a\). Each
additional example will yield another bit of information about \(a\),
provided it is linearly independent of the previous examples. For
instance, if you get the same bitstring out of the oracle that you
have seen before, it obviously doesn’t teach you anything new.
Actually calculating \(a\) can be done efficiently from the \(O(n)\)
examples using Gaussian
elimination.

Unlike the classical scientist, we know quantum mechanics. The state
that actually emerges from the oracle is \(\sum_x |x,a\cdot
x\rangle\). If we were to measure in the computation basis, this
would result in the distribution seen classically. But if we simply
apply the Hadamard gate to all the qubits, the resulting state is
\(\frac{1}{\sqrt{2}}(|0^n,0\rangle + |a,1\rangle)\). Thus, if we
measure the first \(n\) bits, we can just read out the value of \(a\)
half the time! Furthermore, the state of the last bit tells us
whether to expect to read out \(0^n\) or \(a\). So we need only
\(O(2)\) queries and no special Gaussian elimination classical
computation at the end!

That’s already a pretty stark difference between the classical and
quantum case. In fact, this is the example oracle version of the
Bernstein-Vazirani algorithm, itself a refinement of the Deutsch-Jozsa
algorithm found earlier in the tutorial. But when the oracle is noisy,
as all practical systems are, the difference becomes even stranger.
Usually, noise makes things worse for quantum computers much more than
for their classical counterparts. In this problem, the noise makes
things much worse for the classical scientist, but not so much for us
quantum scientists.

The problem for the classical scientist is that when some of the bits
are wrong, the Gaussian elimination algorithm no longer works. The
problem becomes equivalent to the problem of decoding a random linear
code, which is believed to be outside of P. The best known algorithm
becomes computationally intractable for a few hundred bits. This is
true even for relatively tiny amounts of noise.

The quantum scientist can just carry on as before, needing just a few
more examples from the oracle. Provided the noise isn’t too large,
each bit of the output is still correct more than half the time. By
keeping track of the results for each bit separately and using
whichever result (0 or 1) is most common for each bit, the correct
answer can be determined in a straightforward manner.

Implementing this algorithm is simple. Making a parity oracle on our
quantum computer is very easy, requiring only CNOT gates, and the
learning algorithm requires only Hadamards and measurements. See if
you can determine the hidden value of \(a\) in the following circuit.
Note that the special “last” bit is in the middle due to the
limitations of our current actual architecture. The example oracle is
everything up to the final set of Hadamard gates, which themselves are
the quantum algorithm.