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>