## Reading:Impatient Learning and sub/sup Majority Problem

In this article I present some probabilities of 1-step learning optimized by Impatient Learning (http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/0309059) for the sub/sup Majority Learning.

## The (Sub/Sup) Majority Learning

Take a bitstring a, and an integer $$\theta$$. The oracle will respond 0 if $$d(a,x)\leq \theta$$  if queried with x and 1 otherwise. In other terms this oracle reply yes if two bitstrings agree on at least $$\theta$$ bit.

Here are the probability with a simple membership oracle (used with the usual phase kickback trick). Only even n gives an invertible matrix for the use of impatient learning.

 n \ theta 1 2 3 4 2 1 1 X X X 4 0.6875 0.875 0.875 0.6875 X 6 0.3671875 0.617188 0.75 0.75 0.6171875 8 0.1865234 0.361328 0.520508 0.6484 0.6484 10 0.0936279 0.199097 0.312499 0.448241 0.5703125

For all these value, the optimum is achieved when the phase kickback takes value in {-1 ; 1}.

<p>
<br class="_mce_marker" />
</p>