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 
. The oracle will respond 0 if 
if queried with x and 1 otherwise. In other terms this oracle reply yes if two bitstrings agree on at least 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 | 0 | 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}.
Leave a Reply
232 views, 3 so far
today |
This blog is about random stuff from my daily cyber life. Most of the time articles will be about the Web , often they will be relating to Science ... and for the others, there is no rule. Enjoy, and comment articles! 
