Séminaire LIAFA/Algorithmes et Complexité : Vendredi 7 Juin, 14h, salle 1E20– Umesh Vazirani (UC Berkeley)

Bonjour,

Dans la même lignée que le précédent séminaire de PPS, il y aura ce vendredi un séminaire quantique au LIAFA.
Merci de contacter Adi Rosen (en copie de ce mail), si vous souhaitez recevoir les futures annonces du séminaire de l'équipe Algorithmes et Complexité du LIAFA.

Frédéric


Date: 2012-06-07/2012-06-07 [14:00]
Auteur: Umesh Vazirani (UC Berkeley)
Titre: Certifiable Quantum Dice
Résumé:
[ The talk will take place at Chevaleret 1E20 ]

Is it possible to certify that the n-bit output of a random number generator is "really
random"? A possible approach to this question is via the theory of algorithmic
randomness due to Kolmogorov, Chaitin and Solomonoff, which identifies
randomness with uncompressibilityby any Turing Machine. Unfortunately this
definition does not result in an efficient test for randomness. Indeed, in the
classical World it seems impossible to provide such a test.
Quantum mechanics allows for a remarkable random number generator: its output is
certifiably random in the sense that if the output passes a simple statistical test,
and there is no information communicated between the two boxes in the
randomness generating device (based, say, on the speed of light limit imposed
by special relativity), then the output is certifiably random. Moreover, the proof
that the output is truly random does not even depend upon the correctness of
quantum mechanics!

Based on joint work with Thomas Vidick.



On May 29, 2012, at 13:28 , Jean Krivine wrote:

> Bonjour
>
> Le prochain séminaire PPS aura lieu jeudi prochain (31 Mai) à 11h en salle 1D23.
> Nous accueillerons Damian Markham (Telecom ParisTech) qui nous parlera Quantum Computing. Nous espérons vous voir nombreux-ses et dès 10.45 pour la collation café/thé/croissants traditionnelle.
>
> ---------------------
>
> Some quantum quirks for information processing
>
> We will briefly review some of the peculiar features of quantum mechanics which give rise to some of the advantages found in quantum information processing, including quantum key distribution, distributed computation, quantum games and blind quantum computation. We will then outline an intuitive link between measurement based quantum computation and phase transitions in many body physics.