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.

<td>
</td>

<td>
  1
</td>

<td>
  2
</td>

<td>
  3
</td>

<td>
  4
</td>

<td style="text-align: center;">
  1
</td>

<td style="text-align: center;">
  <strong>1</strong>
</td>

<td style="text-align: center;">
  X
</td>

<td>
  X
</td>

<td>
  X
</td>

<td style="text-align: center;">
  0.6875
</td>

<td>
  0.875
</td>

<td>
  <strong>0.875</strong>
</td>

<td>
  0.6875
</td>

<td>
  X
</td>

<td>
  0.3671875
</td>

<td>
  0.6171875
</td>

<td>
  0.75
</td>

<td>
  <strong>0.75</strong>
</td>

<td>
  0.6171875
</td>

<td>
  0.1865234
</td>

<td>
  0.36132812
</td>

<td>
  0.520508
</td>

<td>
  0.6484
</td>

<td>
  <strong>0.6484</strong>
</td>

<td>
  0.0936279
</td>

<td>
  0.1990967
</td>

<td>
  0.312499
</td>

<td>
  0.448241
</td>

<td>
  0.5703125
</td>

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

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