Learning Parity with Noise

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.

LPN circuit 2
Open in composer