Blog de Jean-Christophe Lavocat

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 Read More

As you may have read in some previous post I am actually working on a modified version of the Grover's Algorithm. For those who don't know the principles of Grover's Algorithm, here is a quick explanation. We have a function that is True for only one . We also have a quantum oracle that returns the value of the function f. Classicaly, finding the value of will take n-1 steps. With the quantum version (Grover's Algorithm) it takes only steps. The idea (without explanations) is to take an equally distributed weights vector as input , and to iterate a sequence of unitary operations during a certain amount of time.  After this given number of steps a measurement on the input Read More

Qui est donc ce fameux Hadamard dont tout le monde parle en informatique quantique? Jacques Hadamard est un mathématicien français (1865-1963) à qui l'on doit les célèbres matrices (encore un normalien). Je vous conseille la biographie suivante sur Jacques Hadamard : Jacques Hadamard un mathématicien universel Ainsi que ce site regroupant les propriétés des-dites matrices : http://chaos.if.uj.edu.pl/~karol/hadamard/index.php

Presentation of the problem : The majority problem is equivalent to the perceptron learning. For each define a function : Where wt is the weight of a bit-string (number of 1). Alternatively we can write : . The problem is : determine a given an access to answers from . We saw in the presentation (link available soon) that the classical complexity was while the quantum complexity was . In the following we show the classical bound. The classical algorithm For the classical case we will use a dichotomic process as in the binary chop. Here is the algorithm : At the first step you look the result for 0...0. If it's 1 you take all the possible weights that Read More

There is a bunch of interesting papers dealing with Oracle Identification. Here is a list of the ones I found interesting to read :

WordPress permet d'inclure du Latex dans ses pages grace a un script hébergé sur ses propres serveur. Voila qui va me rendre heureux tout ca :