Reading:Impatient Learning and sub/sup Majority Problem

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.6171875 0.75 0.75 0.6171875
8 0.1865234 0.36132812 0.520508 0.6484 0.6484
10 0.0936279 0.1990967 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>