La physique quantique nous enseigne que certains systèmes physiques peuvent être modélisés comme se trouvant dans une superposition d'états, chacun associé à une amplitude qui est un nombre complexe. Lors d'une mesure de l'état du système, chaque état possible est observé avec une certaine probabilité, fonction de son amplitude. L'objet du calcul quantique est de tirer parti de cette superposition d'états pour concevoir de nouveaux algorithmes. Les ordinateurs quantiques n'existent encore que de manière embryonnaire et leur faisabilité est l'objet d'âpres débats parmi les physiciens, mais l'étude théorique du calcul quantique est intrinsèquement intéressante. Ce cours a pour but d'en présenter quelques aspects.
Filière ``Modèles de calcul et Déduction''.
Principes fondamentauxPrésentation des principales caractéristiques du calcul quantique : q-bits, portes quantiques, algorithmes, théorème du clonage impossible, téléportation
AutomatesDéfinition des automates probabilistes et quantiques, langages reconnus, propriétés et théorèmes
Algorithmes quantiquesÉtude des principaux algorithmes, complexité
- Josef Gruska, Quantum Computing, Mc Graw Hill 1999 (consultable à la bibliothèque)
- Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum
Information, Cambridge University Press, 2000
- Cours de John Preskill: Quantum Information and Computation
http://www.theory.caltech.edu/people/preskill/ph229/
http://www.cs.berkeley.edu/~vazirani/quantum.html
http://beige.ucs.indiana.edu/M74
http://xxx.lanl.gov/archive/quant-ph
http://www.physique.usherb.ca/~ablais/d-wave-web/intro_francais.ht
Je pense faire en sorte que ce cours puisse être suivi par des étudiants du DIF ou d'un DEA de mathématiques. Dans cette optique je pourrai proposer une ou deux séances spécifiques de "rappels" aux uns ou aux autres : je pense en particulier à la théorie générale des automates et des langages formels et aux espaces de Hilbert, mais cela dépendra bien sur des demandes des étudiants.
Vous devez choisir un article (ils seront chez Simone Durand), une date de cours pour l'exposer (environ 30mn + les questions) et écrire un rapport dessus. Vous devez également relire les rapports de deux autres étudiants et écrire une fiche de relecture. Inscrivez-vous chez Simone !
Le rapport sur l'article doit être critique et faire environ 10 pages (en aucun cas plus de 15). Il ne concerne pas nécessairement l'intégralité de l'article. Vous pouvez vous concentrer sur une partie qui vous a intéressée, dire pourquoi, faire les preuves manquantes...
Le cours précédent celui de l'exposé (généralement la semaine précédente), l'étudiant donne trois exemplaires de son rapport : à moi et aux deux relecteurs.
Chaque relecteur fait une fiche critique de relecture et me la donne avant
l'exposé. Elle fait une page ou deux. On pourra s'inspirer de :
http://hercule.csci.unt.edu/~ian/guides/referee.html
Les relecteurs posent également des questions à celui qui
expose.
L'exposé dure environ 25mn et est suivi d'une séance de questions. Ne dépassez en aucun cas 40mn tout compris, répétez auparavant pour connaitre la durée de votre exposé !
Spécial étudiants du DIF : ne choisissez pas une date trop éloignée, car vous risqueriez d'avoir tous vos exposés à faire dans tous les cours en même temps !
Voici la liste des articles avec des indications pour les récupérer
:
cs : http://xxx.lanl.gov/archive/cs
quant-ph : http://xxx.lanl.gov/archive/quant-ph
quant-ph/9503016 [abs, ps, pdf, other] :
Title: Elementary gates for quantum computation
Authors: A. Barenco (Oxford), C. H. Bennett (IBM), R. Cleve (Calgary),
D. P. DiVincenzo (IBM), N. Margolus (MIT), P. Shor (AT&T), T. Sleator
(NYU), J. Smolin (UCLA), H. Weinfurter (Innsbruck)
http://lanl.arXiv.org/abs/quant-ph/?9505018
Universality in Quantum Computation
Authors: D. Deutsch, A. Barenco, A. Ekert
quant-ph/0205115
Both Toffoli and Controlled-NOT need little help to do universal quantum
computation
Authors: Yaoyun Shi
On the Power of Quantum Finite State Automata (1997)
Attila Kondacs, John Watrous
http://citeseer.nj.nec.com/kondacs97power.html
Quantum Automata and Quantum Grammars
Authors: Cristopher Moore, James P. Crutchfield
quant-ph/9707031
1-way quantum finite automata: strengths, weaknesses and generalizations
Authors: A. Ambainis, R. Freivalds
http://xxx.lanl.gov/abs/quant-ph/9802062
On the class of languages recognizable by 1-way quantum finite automata
Andris Ambainis, Arnolds Kikusts, Maris Valdats
http://citeseer.nj.nec.com/359295.html
cs.CC/9911009 [abs, ps, pdf, other] :
Title: Two-way finite automata with quantum and classical states
Authors: Andris Ambainis (1), John Watrous (2) ((1) UC Berkeley, (2) University
of Calgary)
quant-ph/0210004 [abs, ps, pdf, other] :
Title: Probabilistic Quantum Teleportation
Authors: Pankaj Agrawal, Arun K. Pati
undecidability on quantum finite atomata
Masami Amano et Kazuo Iwama
http://www.qci.jst.go.jp/erato/ronbun/
Dense Quantum Coding and a Lower Bound for 1-way
Quantum Automata (1999)
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh Vazirani
http://citeseer.nj.nec.com/ambainis99dense.html
Quantum Complexity Theory
Ethan Bernstein, Umesh Vazirani
http://epubs.siam.org/sam-bin/dbq/article/30092
quant-ph/9805082 [abs, ps, pdf, other] :
Title: Quantum Counting
Authors: Gilles Brassard (1), Peter Hoyer (2), Alain Tapp (1) ((1) Universite
de Montreal, (2) Odense University)
quant-ph/9903046
Quantum Circuits: Fanout, Parity, and Counting
Authors: Cristopher Moore
quant-ph/9904093
Optimal lower bounds for quantum automata and random access codes
Authors: Ashwin Nayak
http://citeseer.nj.nec.com/watrous99spacebounded.html
Space-Bounded Quantum Complexity (1999)
John Watrous
http://citeseer.nj.nec.com/yao93quantum.html
Quantum Circuit Complexity (1993)
Andrew Chi-Chih Yao
Proceedings of the 34th Annual Symposium on Foundations of Computer Science