To see the other types of publications on this topic, follow the link: Complexité du calcul quantique.
Dissertations / Theses on the topic 'Complexité du calcul quantique'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Complexité du calcul quantique.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Grospellier, Antoine. "Décodage des codes expanseurs quantiques et application au calcul quantique tolérant aux fautes." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS575.
Full textAbstract:
Le calcul quantique tolérant aux fautes est un ensemble de techniques dont le but est d'effectuer des calculs quantiques de manière fiable en utilisant des composants bruités. Dans ce contexte, l'utilisation de codes correcteurs quantiques maintient le nombre d'erreurs présentes dans le système en dessous d'un seuil tolérable. L'un des principaux problèmes de ce domaine est d'évaluer le coût minimum (en mémoire et en temps) nécessaire pour transformer un calcul quantique idéal en un calcul tolérant aux fautes. Dans cette thèse, nous montrons que la famille des codes expanseurs quantiques associée à l'algorithme de décodage small-set-flip peut être utilisée dans la construction de ref. [arXiv:1310.2984] pour réaliser du calcul quantique tolérant aux fautes avec coût constant en mémoire. La famille de codes correcteurs ainsi que le décodeur que nous étudions ont été introduits dans ref. [arXiv:1504.00822] où un modèle de bruit adverse est considéré. En nous appuyant sur les résultats de cet article, nous analysons le comportement des codes expanseurs quantiques face à un modèle de bruit stochastique qui est pertinent dans le cadre du calcul tolérant aux fautes [arXiv:1711.08351], [arXiv:1808.03821]. De plus, nous montrons que l'algorithme de décodage peut être parallélisé pour fonctionner en temps constant. Cette propriété est essentielle pour éviter que les erreurs ne s'accumulent pendant que l'algorithme est exécuté. Au-delà des résultats théoriques décrits ci-dessus, nous avons effectué une analyse numérique des codes expanseurs quantiques dans le but d'évaluer leurs performances en pratique [arXiv:1810.03681]. Le modèle de bruit choisi pour ces simulations consiste à générer des erreurs de types X et Z de manière indépendante et identiquement distribuée sur les qubits. Les résultats obtenus pour ces codes de rendement constant sont prometteurs puisque nos simulations montrent que leur seuil est décent et que leurs performances à taille finie sont bonnes<br>Fault tolerant quantum computation is a technique to perform reliable quantum computation using noisy components. In this context, quantum error correcting codes are used to keep the amount of errors under a sustainable threshold. One of the main problems of this field is to determine the minimum cost, in terms of memory and time, which is needed in order to transform an ideal quantum computation into a fault-tolerant one. In this PhD thesis, we show that the family of quantum expander codes and the small-set-flip decoder can be used in the construction of ref. [arXiv:1310.2984] to produce a fault-tolerant quantum circuit with constant space overhead. The error correcting code family and the decoder that we study has been introduced in ref. [arXiv:1504.00822] where an adversarial error model was examined. Based on the results of this article, we analyze quantum expander codes subjected to a stochastic error model which is relevant for fault-tolerant quantum computation [arXiv:1711.08351], [arXiv:1808.03821]. In addition, we show that the decoding algorithm can be parallelized to run in constant time. This is very relevant to prevent errors from accumulating while the decoding algorithm is running. Beyond the theoretical results described above, we perform a numerical analysis of quantum expander codes to measure their performance in practice [arXiv:1810.03681]. The error model used during these simulations generates X and Z type errors on the qubits with an independent and identically distributed probability distribution. Our results are promising because they reveal that these constant rate codes have a decent threshold and good finite length performance
2
Pégny, Maël. "Sur les limites empiriques du calcul : calculabilité, complexité et physique." Thesis, Paris 1, 2013. http://www.theses.fr/2013PA010673/document.
Full textAbstract:
Durant ces dernières décennies, la communauté informatique a montré un intérêt grandissant pour les modèles de calcul non-standard, inspirés par des phénomènes physiques, biologiques ou chimiques. Les propriétés exactes de ces modèles ont parfois été l'objet de controverses: que calculent-ils? Et à quelle vitesse? Les enjeux de ces questions sont renforcés par la possibilité que certains de ces modèles pourraient transgresser les limites acceptées du calcul, en violant soit la thèse de Church-Turing soit la thèse de Church-Turing étendue. La possibilité de réaliser physiquement ces modèles a notamment été au coeur des débats. Ainsi, des considérations empiriques semblent introduites dans les fondements même de la calculabilité et de la complexité computationnelle, deux théories qui auraient été précédemment considérées comme des parties purement a priori de la logique et de l'informatique. Par conséquent, ce travail est consacré à la question suivante : les limites du calcul reposent-elles sur des fondements empiriques? Et si oui, quels sont-ils? Pour ce faire, nous examinons tout d'abord la signification précise des limites du calcul, et articulons une conception épistémique du calcul, permettant la comparaison des modèles les plus variés. Nous répondrons à la première question par l'affirmative, grâce à un examen détaillé des débats entourant la faisabilité des modèles non-standard. Enfin, nous montrerons les incertitudes entourant la deuxième question dans l'état actuel de la recherche, en montrant les difficultés de la traduction des concepts computationnels en limites physiques<br>Recent years have seen a surge in the interest for non-standard computational models, inspired by physical, biological or chemical phenomena. The exact properties of some of these models have been a topic of somewhat heated discussion: what do they compute? And how fast do they compute? The stakes of these questions were heightened by the claim that these models would violate the accepted limits of computation, by violating the Church-Turing Thesis or the Extended Church-Turing Thesis. To answer these questions, the physical realizability of some of those models - or lack thereof - has often been put at the center of the argument. It thus seems that empirical considerations have been introduced into the very foundations of computability and computational complexity theory, both subjects that would have been previously considered purely a priori parts of logic and computer science. Consequently, this dissertation is dedicated to the following question: do computability and computational complexity theory rest on empirical foundations? If yes, what are these foundations? We will first examine the precise meaning of those limits of computation, and articulate a philosophical conception of computation able to make sense of this variety of models. We then answer the first question by the affirmative, through a careful examination of current debates around non-standard models. We show the various difficulties surrounding the second question, and study how they stem from the complex translation of computational concepts into physical limitations
3
Nesme, Vincent. "Complexité en requêtes et symétries." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2007. http://tel.archives-ouvertes.fr/tel-00156762.
Full textAbstract:
Ces travaux portent sur l'étude de la complexité en requêtes de <br />problèmes symétriques, dans les cadres du calcul probabiliste classique <br />et du calcul quantique.<br /><br />Il est montré, dans le cas quantique, une application de la méthode de <br />bornes inférieures dite "polynomiale" au calcul de la complexité en <br />requêtes des problèmes de sous-groupes cachés abéliens, via la technique de "symétrisation".<br /><br />Dans le cas du calcul probabiliste, sous une hypothèse de "symétrie <br />transitive" des problèmes, il est donné une formule combinatoire <br />permettant de calculer la complexité en requêtes exacte du meilleur <br />algorithme non-adaptatif. De plus, il est mis en évidence que sous <br />certaines hypothèses de symétrie, ce meilleur algorithme non-adaptatif <br />est optimal même parmi les algorithmes probabilistes plus généraux, ce qui donne pour la classe de problèmes correspondante une expression exacte de la complexité en requêtes.
4
Dang, Minh Dung. "Autour des primitifs quantiques pour le calcul sécurisé à deux parties." Paris, ENST, 2008. http://pastel.archives-ouvertes.fr/pastel-00005098.
Full textAbstract:
Dans cette thèse, nous sommes intéressés à la construction inconditionnelle du calcul sécurisé à deux parties dont Oblivious Transfer (OT) et Bit Commitment (BC) sont les primitifs fondamentaux. D'une part, mes oeuvres sont inspirées du framework de Crépeau et al. Pour la construction de OT à partir des canaux bruités. Le principe est de concevoir, à partir des canaux bruités, un modèle d'effacement intermédiaire qui est un variant de OT. Nous avons contribué à ce framework en proposant un modèle intermédiaire plus générique, le Binary Symmetric Multi-Error-Rate Channel, qui peut également être construit à partir des canaux bruités. Avec ce modèle intermédiaire, nous pouvons construire le protocole de OT de manière plus efficace. En outre, nous exposons quelques études de cas sur l'émulation des modèles bruités par un codage quantique nonorthogonal qui utilise deux états non-orthogonaux pour coder deux valeurs du bit classique. D'autre part, nous révisons le modèle quantique des protocoles quantiques à deux parties, couvrant les calculs et les communications classiques. Nous constatons que, dans le modèle général, un canal classique est inévitablement macroscopique et la decoherence est si forte que l'information quantique n'est pas acceptée d'être transférée sur ce canal. Ainsi, le modèle quantique des protocoles à deux parties consiste en trois parties, y compris l'environnement du canal. Avec cette fidèle interprétation, nous réaffirmons les théorèmes No-go de Mayers et Lo & Chau sur l'impossibilité de OT, BC quantiques. En addion, nous pouvons étendre ces résultats négatifs aux protocoles utilisant certains oracles quantiques, comme Coin-Flipping<br>In this thesis, we are interested in the theory of unconditional secure two-party computations of which Oblivious Transfer (OT) and Bit Commitment (BC) are the central primitives. On one hand, my works are inspired from Crépeau's et al. 's framework of building of OT protocol from noisy communication channels. The principle of this framework is to conceive, from noisy channels, an intermediate erasure model which is a variant of OT. We contributed to this framework by proposing a more general intermediate model, the Binary Symmetric Multi-Error-Rate Channel, which also can be built from noisy channels. With this intermediate model, we can build OT protocol from the noisy channels more effectively. In addition, we expose some case studies on emulating noisy models by a quantum nonorthogonal coding (QNOC) scheme which uses two non-orthogonal pure states for encoding two values of the classical bit. On the other hand, we revise the quantum model for general two-party protocols concerning classical and quantum computations and communications. We state that in the general model, a classical channel is inevitably macroscopic and its decoherence is so strong that quantum information is not accepted to be transfered on it. Thus, the quantum model for two-party protocols becomes three-party, including an environment of the channel. Indeed, with the faithful interpretation of general quantum two-party protocols in this three-party model, we reaffirm the no-go theorems of Mayers and Lo & Chau on the impossibilities of quantum OT, BC. In addion, we can go further to apply these negative results to protocols using some quantum trusted oracles, such as Coin-Flipping
5
Grunspan, Cyril. "Théorie de Toda discrète et espaces homogènes quantiques." Palaiseau, École polytechnique, 2000. http://www.theses.fr/2000EPXX0042.
Full text
6
Cattaneo, David. "Modélisation graphique et simulation en traitement d'information quantique." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM076/document.
Full textAbstract:
Le formalisme des états graphes consiste à modéliser des états quantiques par des graphes. Ce formalisme permet l'utilisation des notions et des outils de théorie des graphes (e.g. flot, domination, méthodes probabilistes) dans le domaine du traitement de l'information quantique. Ces dernières années, cette modélisation combinatoire a permis plusieurs avancées décisives, notamment (i) dans la compréhension des propriétés de l'intrication quantique (ii) dans l'étude des modèles de calcul particulièrement prometteurs en terme d'implémentation physique, et (iii) dans l'analyse et la construction de protocoles de cryptographie quantique. L'objectif de cette thèse est d'étudier les propriétés graphiques émergeant des problématiques d'informatique quantique, notamment pour la simulation quantique. En particulier, l'étude des propriétés de causalité et de localité des états graphes, en étendant par exemple la notion existante de flot de causalité à une notion intégrant des contraintes de localité, permettrait d'ouvrir de nouvelles perspectives pour la simulation de systèmes quantiques à l'aide d'états graphes. Des connections formelles avec les automates cellulaires quantiques bruités pourront également émerger de cette étude<br>Graph States formalism consist in using graphs to model quantum states. This formalism allows us to use notion and tools of graph theory (e.g. flow, domination, probabilistic methods) in quantum information processing. Last years, this combinatorial modelisation had lead to many decisiv breakthroughs, in particular (i) in the comprehension of the quantum entranglement properties (ii) in very promising in term of physical implementation quantum calculus model, and (iii) in the analysis and construction of quantum cryptography protocols. The goal of this thesis is to study the graphic properties emerging of those quantum information processing problematics, especially for quantum simulation. In particular, the properties of causality and locality in graph states, by extanding for exemple the existing notion of causality flows to a notion integring the locality constraints, would allow new perspectives for the quantum system simulation using graphs states. Formal connections with noisy quantum cellular automata would emerge from this study
7
Douce, Tom. "Realistic quantum information processing : from devices to computational models." Thesis, Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCC201/document.
Full textAbstract:
La théorie du calcul quantique se situe à la frontière de la physique quantique et de l’informatique. Par conséquent, les deux domaines contribuent à la rendre d’autant plus riche en apportant leurs propres méthodes et outils mathématiques. La présente thèse tente de mettre en évidence cette particularité en traitant des problématiques qui vont la physique expérimentale aux modèles de calcul. Le but est d’offrir de nouvelles possibilités pour démontrer un avantage quantique. Après une brève introduction aux notions de base de la mécanique quantique, certains aspects liés à l’informatique sont discutés. Le formalisme des classes de complexité quantiques ainsi que le concept du calcul quantique en variables continues sont décrits. Ensuite, le modèle connu comme instantaneous quantum computing est traduit en variables continues, le rendant attrayant d’un point de vue expérimental. Le chapitre conclut sur une discussion concernant un protocole hybride impliquant l’algorithme de Grover dans le cadre des communications quantiques. La dernière partie de la thèse s’intéresse à des problématiques issues de la physique expérimentale. Le lien entre l’effet Hong-Ou-Mandel et la fonction de Wigner d’un état à deux photons est mise en évidence, et un protocole expérimental est décrit en conséquence. La suite traite du domaine des circuits supraconducteurs et envisage de possibles expériences. Il est montré comment utiliser un qubit de flux pour manipuler un centre coloré du diamant. Il est également décrit comment sonder le modèle de Rabi dans le régime de couplage ultra fort en utilisant un qubit supplémentaire faiblement couplé<br>The theory of quantum computing lies at the very boundary between quantum physics and computer science. As such, both fields bring their own methods and mathematical tools to make quantum computing even richer. The present thesis attempts to reflect this specificity by addressing questions ranging from experimental physics to computational models. The goal is to provide novel ways of demonstrating quantum advantage. After a short introduction to basic notions of quantum mechanics, some computer science aspects are discussed. We describe the powerful formalism of quantum complexity classes and the concept of quantum computations based on continuous variables. We then translate the model of instantaneous quantum computing to continuous variables, which is experimentally appealing. The chapter concludes with a discussion on a hybrid protocol involving Grover’s algorithm in a quantum communication framework. The last part of the thesis is devoted to experimentally driven issues. A fundamental connection between the Hong-Ou-Mandel experiment and the Wigner function of two-photon states is derived and a verification protocol is designed accordingly. We then move to the field of superconducting circuits to discuss proposals for future experiments. We show how to use a flux qubit to manipulate a NV color center. We also describe how to use to probe the Rabi model in the ultra strong coupling regime using an additional weakly coupled qubit
8
Kaplan, Marc. "Méthodes Combinatoires et Algébriques en Complexité de la Communication." Phd thesis, Université Paris Sud - Paris XI, 2009. http://tel.archives-ouvertes.fr/tel-00439929.
Full textAbstract:
La complexité de la communication a été introduite en 1979 par Andrew Chi-Chi Yao. Elle est depuis devenue l'un des modèles de calcul les plus étudiés. L'objectif de celle-ci est d'étudier des problèmes dont les entrées sont distribuées entre plusieurs joueurs, en quantifiant la communication que ceux-ci doivent échanger. Nous utilisons d'abord la complexité de Kolmogorov, une caractérisation algorithmique de l'aléatoire, pour prouver des bornes inférieures sur la complexité de la communication. Notre méthode constitue une généralisation de la méthode d'incompressibilité. L'avantage de cette approche est de mettre en valeur la nature combinatoire des preuves. Nous étudions ensuite la simulation des distributions de probabilité causales avec de la communication. Ce modèle généralise la complexité de la communication traditionnelle et comprend en particulier les distributions quantiques. Nous montrons pour ce problème des bornes inférieures et supérieures. Dans le cas des fonctions booléennes, la borne inférieure que nous proposons est équivalente aux normes de factorisation, une puissante méthode introduite par Linial et Shraibman en 2006. Enfin, nous étudions la complexité en boîte non-locale. Cette ressource a été introduite par Popescu et Rohrlich pour étudier la non-localité. Le problème est de quantifier le nombre de boîtes nécessaire et suffisant pour calculer une fonction ou simuler une distributions. Nous donnons encore des bornes inférieures et supérieures pour ces problèmes, ainsi que des applications à l'évaluation sécurisée, un problème cryptographique très important.
9
Bredariol, Grilo Alex. "Quantum proofs, the local Hamiltonian problem and applications." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC051/document.
Full textAbstract:
Dans la classe de complexité QMA – la généralisation quantique de la classe NP – un état quantique est fourni comme preuve à un algorithme de vérification pour l’aider à résoudre un problème. Cette classe de complexité a un problème complet naturel, le problème des Hamiltoniens locaux. Inspiré par la Physique de la matière condensée, ce problème concerne l’énergie de l’état fondamental d’un système quantique. Dans le cadre de cette thèse, nous étudions quelques problèmes liés à la classe QMA et au problème des Hamiltoniens locaux. Premièrement, nous étudions la différence de puissance si au lieu d’une preuve quantique, l’algorithme de vérification quantique reçoit une preuve classique. Nous proposons un cadre intermédiaire à ces deux cas, où la preuve consiste en un état quantique “plus simple” et nous arrivons à démontrer que ces états plus simples sont suffisants pour résoudre tous les problèmes dans QMA. À partir de ce résultat, nous obtenons un nouveau problème QMA-complet et nous étudions aussi la version de notre nouvelle classe de complexité avec erreur unilatérale. Ensuite, nous proposons le premier schéma de délégation vérifiable relativiste de calcul quantique. Dans ce cadre, un client classique délègue son calcul quantique à deux serveurs quantiques intriqués. Ces serveurs peuvent communiquer entre eux en respectant l’hypothèse que l’information ne peut pas être propagé plus vite que la vitesse de la lumière. Ce protocole a été conçu à partir d’un jeu non-local pour le problème des Hamiltoniens locaux avec deux prouveurs et un tour de communication. Dans ce jeu, les prouveurs exécutent des calculs quantiques de temps polynomiaux sur des copies de l’état fondamental du Hamiltonien. Finalement, nous étudions la conjecture PCP quantique, où l’on demande si tous les problèmes dans la classe QMA acceptent un système de preuves où l’algorithme de vérification a accès à un nombre constant de qubits de la preuve quantique. Notre première contribution consiste à étendre le modèle QPCP avec une preuve auxiliaire classique. Pour attaquer le problème, nous avons proposé une version plus faible de la conjecture QPCP pour ce nouveau système de preuves. Nous avons alors montré que cette nouvelle conjecture peut également être exprimée dans le contexte des problèmes des Hamiltoniens locaux et ainsi que dans lecadre de la maximisation de la probabilité de acceptation des jeux quantiques. Notre résultat montre la première équivalence entre un jeu multi-prouveur et une conjecture QPCP<br>In QMA, the quantum generalization of the complexity class NP, a quantum state is provided as a proof of a mathematical statement, and this quantum proof can be verified by a quantum algorithm. This complexity class has a very natural complete problem, the Local Hamiltonian problem. Inspired by Condensed Matters Physics, this problem concerns the groundstate energy of quantum systems. In this thesis, we study some problems related to QMA and to the Local Hamiltonian problem. First, we study the difference of power when classical or quantum proofs are provided to quantum verification algorithms. We propose an intermediate setting where the proof is a “simpler” quantum state, and we manage to prove that these simpler states are enough to solve all problems in QMA. From this result, we are able to present a new QMA-complete problem and we also study the one-sided error version of our new complexity class. Secondly, we propose the first relativistic verifiable delegation scheme for quantum computation. In this setting, a classical client delegates her quantumcomputation to two entangled servers who are allowed to communicate, but respecting the assumption that information cannot be propagated faster than speed of light. This protocol is achieved through a one-round two-prover game for the Local Hamiltonian problem where provers only need polynomial time quantum computation and access to copies of the groundstate of the Hamiltonian. Finally, we study the quantumPCP conjecture, which asks if all problems in QMA accept aproof systemwhere only a fewqubits of the proof are checked. Our result consists in proposing an extension of QPCP proof systems where the verifier is also provided an auxiliary classical proof. Based on this proof system, we propose a weaker version of QPCP conjecture. We then show that this new conjecture can be formulated as a Local Hamiltonian problem and also as a problem involving the maximum acceptance probability of multi-prover games. This is the first equivalence of a multi-prover game and some QPCP statement
10
Javelle, Jérôme. "Cryptographie Quantique : Protocoles et Graphes." Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENM093/document.
Full textAbstract:
Je souhaite réaliser un modèle théorique optimal pour les protocoles de partage de secret quantique basé sur l'utilisation des états graphes. Le paramètre représentatif d'un partage de secret à seuil est, entre autres la taille du plus grand ensemble de joueurs qui ne peut pas accéder au secret. Je souhaite donc trouver un famille de protocoles pour laquelle ce paramètre est le plus petit possible. J'étudie également les liens entre les protocoles de partage de secret quantique et des familles de courbes en géométrie algébrique<br>I want to realize an optimal theoretical model for quantum secret sharing protocols based on graph states. The main parameter of a threshold quantum secret sharing scheme is the size of the largest set of players that can not access the secret. Thus, my goal is to find a collection of protocols for which the value of this parameter is the smallest possible. I also study the links between quantum secret sharing protocols and families of curves in algebraic geometry
11
David, Julien. "Génération aléatoire d'automates et analyse d'algorithmes de minimisation." Phd thesis, Université Paris-Est, 2010. http://tel.archives-ouvertes.fr/tel-00587637.
Full textAbstract:
Cette thèse porte sur la génération aléatoire uniforme des automates finis et l'analyse des algorithmes de minimisation qui s'y appliquent. La génération aléatoire permet de conduire une étude expérimentale sur les propriétésde l'objet engendré et sur les méthodes algorithmiques qui s'y appliquent. Il s'agit également d'un outil de recherche, qui permet de faciliter l'étude théorique du comportement moyen des algorithmes. L'analyse en moyenne des algorithmes s'inscrit dans la suite des travaux précurseurs de Donald Knuth. Le schéma classique en analyse d'algorithmes consiste à étudier le pire des cas, qui n'est souvent pas représentatif du comportement de l'algorithme en pratique. D'un point de vue théorique, on définit ce qui se produit "souvent'' en fixant une loi de probabilitésur les entrées de l'algorithme. L'analyse en moyenne consiste alors à estimer des ressources utiliséespour cette distribution de probabilité. Dans ce cadre, j'ai travaillé sur des algorithmes de génération aléatoire d'automatesdéterministes accessibles (complets ou non). Ces algorithmes sont basés sur de la combinatoirebijective, qui permet d'utiliser un procédé générique : les générateurs de Boltzmann. J'ai ensuite implanté ces méthodes dans deux logiciels : REGAL et PREGA. Je me suis intéressé à l'analyse en moyenne des algorithmes de minimisation d'automateset j'ai obtenu des résultats qui montrent le cas moyen des algorithmes de Moore et Hopcroft est bien meilleur que le pire des cas
12
Magnin, Loïck. "Two-player interaction in quantum computing : cryptographic primitives & query complexity." Thesis, Paris 11, 2011. http://www.theses.fr/2011PA112275/document.
Full textAbstract:
Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM<br>This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ``quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ``intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ``quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ``multiplicative adversary method'' is stronger than the ``additive adversary method''. We then show a reduction from the ``polynomial method'' to the multiplicative adversary method. Hence, we prove that the multiplicative adversary method is the strongest one. Adversary methods are usually difficult to use since they involve the computation of norms of matrices with very large size. We show how studying the symmetries of a problem can largely simplify these computations. Last, using these principles we prove the tight lower bound of the INDEX-ERASURE problem. This a quantum state generation problem that has links with the famous GRAPH-ISOMORPHISM problem
13
Mhalla, Mehdi. "Informatique quantique, algorithmes et complexité." Grenoble INPG, 2004. http://www.theses.fr/2004INPG0113.
Full textAbstract:
Nous présentons dans ce travail plusieurs résultats dans différents domaines de l'information quantique. Après une première partie où nous proposons une introduction au domaine, nous proposons des caractérisations simples et efficaces du phénomène de l'intrication des états purs. Les deux formes de séparabilité étudiées sont la séparabilité totale et la p-q séparabilité. Ces caractérisations nous ont permis de donner des algorithmes optimaux de détection de la séparabilité ayant un gain quadratrique par rapport aux méthodes connues. La troisième partie s'intéresse aux jeux quantiques. Nous présentons tout d'abord une analyse fine des jeux octaux classiques et donnons une stratégie optimale pour le jeu des dominos. Nous proposons ensuite une quantisation de certains jeux combinatoires, définissant ainsi la famille des jeux octaux quantiques. Nous présentons ainsi un modèle formel permettant de parler des jeux quantiques à information totale et proposons une approche qui utilise des pièges pour des jeux quantiques très étudiés, appelés jeux de dés à distance. La dernière partie étudie des problèmes d'optimisation, en développant pour cela des outils optimaux de recherche de minima. Ces outils nous ont permis d'analyser la complexité en requêtes de certains problèmes de graphes. Nous avons ainsi trouvé des algorithmes quantiques pour les problèmes de connectivité, forte connectivité, arbre couvrant de poids minimal et plus courts chemins à une source donnée. Puis, nous avons prouvé leur optimalité en utilisant des techniques de bornes inférieures, déterminant ainsi les limites du facteur de gain qu'offre l'informatique quantique pour résoudre ce problème<br>This work consists in several results in different domains of quantum computing. First, we propose an introduction to the quantum computing theory. Then we give efficient characterizations of entanglement for pure states. We define the full separability and the p-q separability, and give optimal algorithms that improve by a quadratic factor the detection of entanglement. The third part is dedicated to quantum game theory. We analyse some classical combinatorial games, and find an optimal strategy for the 0. 07 octal game. Then we propose a quantisation of the family of octal games, and of some other combinatorial games, defining by the way a formalism that permits to study such games. We also provide some new ideas for the study of the well know coin flip game. In the last part, we study optimisation problems, and give an optimal minima finding algorithm based on the quantum search. Then we apply this tool to design algorithms for some graph problems (connectivity, strong connectivity, minimum spanning tree and single source shortest paths. We prove the optimality of our algorithms by using the quantum adversary lower bound method, giving therefore a characherisation of the speed-up given by quantum computing for these problems
14
Jeandel, Emmanuel. "Techniques algébriques en calcul quantique." Lyon, École normale supérieure (sciences), 2005. http://www.theses.fr/2005ENSL0307.
Full textAbstract:
Le principal problème étudié est le calcul de l'adhérence de Zariski de groupes algébriques, et leurs applications en calcul quantique. On donne ici un algorithme en temps polynomial qui décide si un sous-groupe finiment engendré d'un groupe reductif est dense dans ce groupe. On donne également un algorithme qui calcule précisément l'adhérence d'un groupe. Ces résultats sont utilisés afin de résoudre plusieurs problèmes en calcul quantique, en particulier liés aux circuits quantiques. Ainsi divers algorithmes qui décident si des jeux de portes sont universels, ou qui permettent de séparer les différentes notions d'universalité, sont donnés. Nous nous intéressons aussi ici aux automates finis. Nous introduisons ici un nouvel modèle, les automates topologiques, qui permet de généraliser les modèles existants. Nous montrons ainsi, dans un contexte unifié, que tous les modèles d'automates finis classiques, quantiques ou probabilistes ne reconnaissent que des langages rationnels par seuil isolé<br>The main problem studied is the computation of the Zariski closure of algebraic groups and its applications on quantum computation. We give a polynomial time algorithm to decide whether a finitely generated subgroup of a given reductive group is Zariski-dense. A second algorithm, which computes precisely the Zariski-closure of a finitely generated group is given. These tools gives decidability results for several problems in quantum computing, mainly whether a set of gates is universal. We give also a separation between various models of quantum computing An other part of the thesis deals with finite automata. A new model of automata, topological automata, is defined. We then proved in a unified framework that all models of classical, probabilistic and quantum automata accept only regular languages with an isolated threshold
15
Madet, Antoine. "Complexité implicite dans des Lambda -calculs concurrents." Paris 7, 2012. http://www.theses.fr/2012PA077222.
Full textAbstract:
Contrôler la consommation en ressources des programmes informatiques est d'importance capitale, non seulement pour des raisons de performance, mais aussi pour des questions de sécurité quand par exemple certains systèmes mobiles ou embarqués disposent de quantités limitées de ressources. Dans cette thèse, nous développons des critères statiques pour contrôler la consommation en ressources de programmes concurrents d'ordre supérieur. Nous prenons comme point de départ le cadre des Logiques Light qui a été étudié afin de contrôler la complexité de programmes fonctionnels d'ordre supérieur au moyen de la correspondance preuves-programmes. La contribution de cette thèse est d'étendre ce cadre aux programmes concurrents d'ordre supérieur. Plus généralement, cette thèse s'inscrit dans le domaine de la complexité implicite qui cherche à caractériser des classes de complexité par des principes logiques ou des restrictions de langage. Les critères que nous proposons sont purement syntaxiques et sont développés graduellement afin de contrôler le temps de calcul des programmes de plus en plus finement: dans un premier temps nous montrons comment garantir la terminaison des programmes (temps fini), puis nous montrons comment garantir la terminaison des programmes en temps élémentaire, et enfin nous montrons comment garantir la terminaison des programmes en temps polynomial. Nous introduisons également des systèmes de types tels que les programmes bien typés terminent en temps borné et retournent des valeurs. Enfin, nous montrons que ces systèmes de types capturent des programmes concurrents intéressants qui itèrent des fonctions produisant des effets de bord sur des structures de données inductives. Dans la dernière partie, nous étudions une méthode sémantique alternative afin de contrôler la consommation en ressources de programmes impératifs d'ordre supérieur. Cette méthode est basée sur la réalisabilité quantitative de Dal Lago et Hofmann et permet d'obtenir plusieurs bornes de complexité de manière uniforme. Cette dernière partie est un travail en collaboration avec Aloïs Brunel<br>Controlling the resource consumption of programs is crucial: besides performance reasons, it has many applications in the field of computer security where e. G. Mobile or embedded Systems dispose of limited amounts of resources. In this thesis, we develop static criteria to control the resource consumption of higher-order concurrent programs. Our starting point is the framework of Light Logics which has been extensively studied to control the complexity of higher-order functional programs through the proofs-as-programs correspondent. The contribution of this thesis is to extend this framework to higher-order concurrent programs. More generally, this thesis fits in the research field of Implicit Computational Complexity which aims at characterizing complexity classes by logical principles or language restrictions. The criteria that we propose are purely syntactic and are developed gradually to control the computational time of programs in a finer and finer way: first, we show how to guarantee the termination of programs (finite time); then, we show how to guarantee the termination of programs in elementary time and last, we show how to guarantee the termination of programs in polynomial time. We also introduce type Systems so that well-typed programs are guaranteed to terminate in bounded time and to return values. Finally, we show that the type Systems capture some interesting concurrent programs that iterate functions producing side effects over inductive data structures. In the last part, we study an alternative semantic method to control the resource consumption of higher-order imperative programs. The method is based on Dal Lago and Hofmann's quantitative realizability framework and allows to obtain various complexity bounds in a uniform way. This last par is joint work with Aloïs Brunel
16
Tapp, Alain. "Informatique quantique, algorithmes et complexité de la communication." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0018/NQ51978.pdf.
Full text
17
Dürr, Christoph. "Tomographie discrète, calcul quantique et ordonnancement." Habilitation à diriger des recherches, Université Paris Sud - Paris XI, 2006. http://tel.archives-ouvertes.fr/tel-00111205.
Full text
18
Baboin, Anne-Céline. "Calcul quantique : algèbre et géométrie projective." Phd thesis, Université de Franche-Comté, 2011. http://tel.archives-ouvertes.fr/tel-00600387.
Full textAbstract:
Cette thèse a pour première vocation d'être un état de l'art sur le calcul quantique, sinon exhaustif, simple d'accès (chapitres 1, 2 et 3). La partie originale de cet essai consiste en deux approches mathématiques du calcul quantique concernant quelques systèmes quantiques : la première est de nature algébrique et fait intervenir des structures particulières : les corps et les anneaux de Galois (chapitre 4), la deuxième fait appel à la géométrie dite projective (chapitre 5). Cette étude a été motivée par le théorème de Kochen et Specker et par les travaux de Peres et Mermin qui en ont découlé
19
Blais, Alexandre. "Calcul quantique universel sur qubits supraconducteurs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape9/PQDD_0031/MQ67692.pdf.
Full text
20
Applencourt, Thomas. "Calcul haute performance & chimie quantique." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30162/document.
Full textAbstract:
L'objectif de ce travail de thèse est double : - Le développement et application de méthodes originales pour la chimie quantique ; - La mise au point de stratégies informatiques variées permettant la réalisation de simulations à grande échelle. Dans la première partie, les méthodes d'integration de configuration (IC) et monte carlo quantique (QMC) utilisées dans ce travail pour le calcul des propriétés quantiques sont présentées. Nous détaillerons en particulier la méthode d'\IC sélectionnée perturbativement (CISPI) que nous avons utilisée pour construire des fonctions d'onde d'essai pour le QMC. La première application concerne le calcul des énergies totales non-relativistes des atomes de transition de la série 3d ; ceci a nécessité l'implémentation de fonctions de base de type Slater et a permis d'obtenir les meilleures valeurs publiées à ce jour. La deuxième application concerne l'implémentation de pseudo-potentiels adaptés à notre approche QMC, avec pour application une étude concernant le calcul des énergies d'atomisation d'un ensemble de 55 molécules. La seconde partie traite des aspects calcule haute performance (HPC) avec pour objectif l'aide au déploiement des simulations à très grande échelle, aussi bien sous l'aspect informatique proprement dit - utilisation de paradigmes de programmation originaux, optimisation des processus monocœurs, calculs massivement parallèles sur grilles de calcul (supercalculateur et Cloud), outils d'aide au développement collaboratif \textit{et cætera} -, que sous l'aspect \emph{utilisateur} - installation, gestion des paramètres d'entrée et de sortie, interface graphique, interfaçage avec d'autres codes. L'implémentation de ces différents aspects dans nos codes-maison quantum pakcage et qmc=chem est également présentée<br>This thesis work has two main objectives: 1. To develop and apply original electronic structure methods for quantum chemistry 2. To implement several computational strategies to achieve efficient large-scale computer simulations. In the first part, both the Configuration Interaction (CI) and the Quantum Monte Carlo (QMC) methods used in this work for calculating quantum properties are presented. We then describe more specifically the selected CI approach (so-called CIPSI approach, Configuration Interaction using a Perturbative Selection done Iteratively) that we used for building trial wavefunctions for QMC simulations. As a first application, we present the QMC calculation of the total non-relativistic energies of transition metal atoms of the 3d series. This work, which has required the implementation of Slater type basis functions in our codes, has led to the best values ever published for these atoms. We then present our original implementation of the pseudo-potentials for QMC and discuss the calculation of atomization energies for a benchmark set of 55 organic molecules. The second part is devoted to the Hight Performance Computing (HPC) aspects. The objective is to make possible and/or facilitate the deployment of very large-scale simulations. From the point of view of the developer it includes: The use of original programming paradigms, single-core optimization process, massively parallel calculations on grids (supercomputer and Cloud), development of collaborative tools , etc - and from the user's point of view: Improved code installation, management of the input/output parameters, GUI, interfacing with other codes, etc
21
Ayad, Ali. "Complexité de résolution de systèmes algébriques paramétrés." Rennes 1, 2006. https://tel.archives-ouvertes.fr/tel-00127383.
Full textAbstract:
On présente trois algorithmes dans cette thèse. Le premier algorithme résout des systèmes polynomiaux homogènes et paramétrés zéro-dimensionnels avec un temps simplement exponentiel en le nombre n des inconnus. Cet algorithme décompose l'espace des paramètres en un nombre fini d'ensembles constructibles et calcule le nombre fini de solutions par des représentations rationnelles paramétriques uniformes sur chaque ensemble constructible. Le deuxième algorithme factorise absolument des polynômes multivariés paramétrés avec un temps simplement exponentiel en n et en la borne supérieure d de degrés de polynômes à factoriser. Le troisième algorithme décompose les variétés algébriques définies par des systèmes algébriques paramétrés de dimensions positives en composantes absolument irréductibles d'une manière uniforme sur les valeurs des paramètres. La complexité de cet algorithme est doublement exponentielle en n. D'autre part, la borne inférieure du problème de résolution de systèmes algébriques paramétrés est doublement exponentielle en n.
22
Pomeransky, Andrei. "Intrication et Imperfections dans le Calcul Quantique." Phd thesis, Université Paul Sabatier - Toulouse III, 2004. http://tel.archives-ouvertes.fr/tel-00007256.
Full textAbstract:
L'information quantique est un nouveau domaine de la physique, qui consiste à employer les systèmes quantiques dans le calcul et la transmission de l'information. Cette thèse est consacrée à l'étude de certains aspects théoriques de l'information quantique. Les ordinateurs quantiques utilisent les lois de la mécanique quantique pour exécuter des calculs d'une manière bien plus efficace que les ordinateurs existants. Les ordinateurs quantiques envisageables dans la pratique seraient influencés par des perturbations diverses. Parmi ces sources de perturbations, les interactions résiduelles statiques (indépendantes du temps) à l'intérieur de l'ordinateur sont connues pour être les plus dangereuses dans le sens où elles peuvent s'ajouter de façon cohérente, tandis que les autres perturbations ont la forme d'un bruit aléatoire avec une moyenne égale à zéro. Nous étudions, dans les cas de deux calculs quantiques très différents, l'efficacité des ordinateurs quantiques en présence d'imperfections statiques. Nous trouvons le domaine des paramètres dans lequel l'ordinateur quantique est robuste en présence des imperfections. Une des raisons fondamentales de l'efficacité extraordinaire de l'ordinateur quantique et de l'existence d'autres applications de l'information quantique est l'effet de l'intrication quantique. L'intrication consiste dans l'impossibilité de considérer un état pur générique d'un système quantique composé comme le simple produit des états purs de ses sous-systèmes. Dans cette thèse nous étudions certaines propriétés importantes d'une certaine mesure quantitative d'intrication largement utilisée. Nous considérons également l'entropie informationnelle moyenne des états quantiques, puis nous trouvons une expression explicite pour cette quantité et étudions ses propriétés les plus importantes.
23
Pomeransky, Andrei A. "Intrication et imperfections dans le calcul quantique." Toulouse 3, 2004. http://www.theses.fr/2004TOU30132.
Full textAbstract:
L'information quantique est un nouveau domaine de la physique, qui consiste à employer les systèmes quantiques dans le calcul et la transmission de l'information. Les ordinateurs quantiques utilisent les lois de la mécanique quantique pour exécuter des calculs d'une manière bien plus efficace que les ordinateurs existants. Les ordinateurs quantiques seraient influencés par des perturbations diverses. Nous étudions, dans les cas de deux calculs quantiques très différents, l'efficacité des ordinateurs quantiques en présence d'imperfections statiques. Une des raisons fondamentales de l'efficacité extraordinaire de l'ordinateur quantique est l'effet de l'intrication quantique. Dans cette thèse nous étudions certaines propriétés importantes d'une certaine mesure quantitative d'intrication largement utilisée. Nous considérons également l'entropie informationnelle moyenne des états quantiques, puis nous trouvons une expression explicite pour cette quantité et étudions ses propriétés les plus importantes<br>Quantum information is a new domain of physics, which studies the applications of quantum systems to the computation and to the information transmission. The quantum computers use the lows of quantum mechanics to perform the calculations much more efficiently than all currently existing computers can. The quantum computers will be influenced by all kinds of perturbations. We study, in the case of two very different quantum computations, the efficiency of the quantum computers in the presence of the static imperfections. One of the fundamental reasons of the extraordinary efficiency of the quantum computers is the effect of quantum entanglement. In the present thesis we study certain important properties of a widely used quantitative measure of entanglement. We consider also the average informational entropy of quantum states, find an explicit expression for this quantity and study some its most important properties
24
Duclos-Cianci, Guillaume. "Outils de calcul quantique tolérant aux fautes." Thèse, Université de Sherbrooke, 2015. http://hdl.handle.net/11143/6770.
Full textAbstract:
Le développement de qubits quantiques robustes représente un défi technologique de taille. Malgré plus d'une décennie de progrès et de percées, nous sommes toujours à la recherche du candidat idéal. La difficulté réside dans la nécessité de respecter une panoplie de critères stricts: on doit pouvoir préparer et mesurer les qubits rapidement et de manière fiable, préserver leur état pour de longs temps, appliquer avec précision un continuum de transformations, les coupler les uns aux autres, en entasser des milliers, voire des millions sur un seul dispositif, etc.
Parallèlement à ces recherches, un autre groupe de scientifiques travaillent plutôt à l'élaboration de l'architecture permettant d'opérer ces qubits. Cette architecture inclut une couche logicielle de base dont l'étude constitue le domaine du calcul tolérant aux fautes: en encodant l'information dans des qubits logiques à l'aide des qubits physiques disponibles, il est possible d'obtenir un dispositif quantique dont les propriétés effectives sont supérieures à celles des composantes physiques sous-jacentes. En contrepartie, une surcharge doit être payée. Celle-ci peut être interprétée comme une forme de redondance dans l'information. De plus, les portes logiques applicables aux qubits encodés sont souvent trop limitées pour être utiles. La recherche dans ce domaine vise souvent à limiter la surcharge et à étendre l'ensemble des opérations applicables.
Cette thèse présente les travaux que j'ai publiés avec mes collaborateurs durant mes études de doctorat. Ceux-ci touchent deux aspects importants du calcul tolérant aux fautes: l'élaboration de protocoles de calcul universel et la conception et l'étude d'algorithmes de décodage de codes topologiques stabilisateurs.
Concernant l'élaboration de protocoles de calcul universel, j'ai développé avec l'aide de Krysta Svore chez Microsoft Research une nouvelle famille d'états ressources (Chapitre 2). Celle-ci permet, par l'injection d'états, d'effectuer une opération unitaire arbitraire à un qubit à un coût plus faible que les méthodes existant à ce moment. Plus tard, j'ai poursuivi ces travaux avec David Poulin pour élaborer une autre famille d'états ressources qui diminuent encore davantage les coûts de compilation de diverses portes unitaires à un qubit (Chapitre 3). Finalement, Jonas Anderson, David Poulin et moi avons montré comment il est possible de passer de manière tolérante aux fautes d'un encodage à un autre (Chapitre 4). Cette approche est qualitativement différente, car elle fournit un ensemble universel de portes sans passer par l'injection d'états.
Durant mon doctorat, j'ai aussi généralisé de plusieurs manières la méthode de décodage par renormalisation du code topologique de Kitaev que j'ai développée au cours de ma maîtrise. Tout d'abord, j'ai collaboré avec Héctor Bombin et David Poulin dans le but de montrer que tous les codes topologiques stabilisateurs invariants sous translation sont équivalents, c'est-à-dire qu'ils appartiennent à la même phase topologique (Chapitre 5). Ce résultat m'a aussi permis d'adapter mon décodeur aux codes topologiques de couleurs stabilisateurs et à sous-systèmes. Puis, je l'ai adapté à une généralisation du code topologique de Kitaev sur des qudits (Chapitre 6). Ensuite, je l'ai généralisé au cas tolérant aux fautes, où les erreurs dans les mesures du syndrome sont prises en compte (Chapitre 7). Finalement, je l'ai appliqué à un nouveau code élaboré par Sergey Bravyi, le code de surface à sous-systèmes (Chapitre 8).
25
Senot, Maxime. "Modèle géométrique de calcul : fractales et barrières de complexité." Phd thesis, Université d'Orléans, 2013. http://tel.archives-ouvertes.fr/tel-00870600.
Full textAbstract:
Les modèles géométriques de calcul permettent d'effectuer des calculs à l'aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d'illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d'abord à travers l'étude de fractales que les machines à signaux sont capables d'une utilisation massive et parallèle de l'espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base -- les modules -- munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l'application de cette méthode et l'utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appelée profondeur de collisions, qui est polynomiale, illustrant ainsi l'efficacité et le pouvoir de calcul parallèle des machines à signaux.
26
Lafitte, Grégory. "Calculs et infinis." Lyon, École normale supérieure (sciences), 2002. http://www.theses.fr/2002ENSL0239.
Full textAbstract:
"Nous introduisons une hiérarchie de notions de calcul généralisé. L'idée est de regrouper en une notion tout ce que l'on pourrait qualifier de "calculabilité", de pouvoir étudier ces notions et en fin de compte d'établir des théorèmes de transfert entre elles. Ces notions correspondent certaines fois aussi à des modèles de calcul obtenues par le biais de machines concrètes. Nous avons ainsi un nouveau modèle de calcul avec les " automates cellulaires à temps infini " qui ont l'avantage sur les machines de Turing d'être plus homogènes (absence de tête). La notion de complexité de calcul (selon une certaine notion de calcul) est également généralisée et étudiée. Enfin, nous obtenons des notions de réels aléatoires plus fines que la notion classique de Martin-Löf (ou Kolmogorov) que l'on peut affiner de plus en plus. Tout ceci mène à la notion de complexité de Kolmogorov généralisée qui ouvre des perspectives intéressantes. "<br>We introduce a hierarchy of notions of generalized computation. The idea is to almagamate in one concept all that we could qualify of "computability", to study those notions and ultimately to have transfer theorems between those notions. Those notions correspond also in some cases to computation models obtained by means of concrete machines. We obtain in this way a new computation model, "infinite time cellular automata", which are more homogeneous than Turing machines (lack of head). The notion of computational complexity (according to a certain notion of computation) is also generalized and studied. Finally, we obtain notions of random reals that are finer than the classical notion of Martin-Löf (or Kolmogorov) and yet more and more refinable. All of this leads to a notion of generalized Kolmogorov complexity which opens up interesting prospects.
27
Kempe, Julia. "Calcul quantique : marches aléatoires et enchevêtrement, applications cryptographiques /." Paris : École nationale supérieure des télécommunications, 2001. http://catalogue.bnf.fr/ark:/12148/cb388211970.
Full text
28
Kempe, Julia. "Calcul quantique : marches aléatoires et enchevêtrement, applications cryptographiques." Paris, ENST, 2001. http://www.theses.fr/2001ENST0015.
Full textAbstract:
Depuis une dizaine d'années, le calcul quantique est un domaine de recherche très actif. Surtout depuis le fameux algorithme de factorisation de nombres en temps polynomial par un ordinateur quantique (shor 95) la recherche dans cette discipline à déclenche. Mon travail porte sur deux aspects du calcul quantique lies a l'algorithmique et à la cryptographie quantiques. Algorithmique : nous initions l'étude de la généralisation des marches aléatoires sur les graphes finis au monde quantique. La méthode des chaines de markov, basée sur l'échantillonnage rapide d'une distribution probabilistique a permis de résoudre efficacement une grande classe de problèmes en informatique classique. En quantique, de telles marches aléatoires ne convergent pas a priori vers une distribution stationnaire. Néanmoins en relaxant les définitions de façon appropriée, nous obtenons des mesures de vitesse pour lesquelles la marche quantique se disperse. Nous établissons des définitions (comme temps de mélange) donnant un sens théorique aux chaines de markov quantiques. Nous démontrons que sur le modèle du cercle, les mesures de vitesse de convergence sont quadratiquement plus rapides que dans le cas classique. Nous établissons des bornes inferieures de l'accélération quantique sur les graphes généraux. Cryptographie : nous étudions l'enchevêtrement quantique sous trois aspects : - nous analysons la possibilité de convertir des états quantiques enchevêtres par des moyens locaux ou encore par l'utilisation d'information stockée cachée : nous montrons que des états localement iso spectraux ne peuvent pas être convertis entre eux localement. Ceci donne lieu à un nouveau protocole du secret-sharing. - nous établissons un nouveau critère pour déterminer si un état quantique donne est enchevêtre (base sur la théorie de majoration probabiliste). - nous étudions le comportement d'un modèle physique pour le clonage quantique et démontrons son optimalité.
29
Lalire, Marie. "Développement d'une notation algorithmique pour le calcul quantique." Grenoble INPG, 2006. http://www.theses.fr/2006INPG0113.
Full textAbstract:
Partant du double constat que d'une part, aucun formalisme ou langage ne permettait d'exprimer complètement et rigoureusement les algorithmes quantiques, et que d'autre part, ces algorithmes et protocoles comportent nécessairement des parties classiques et des parties quantiques, nous avons choisi de concevoir une algèbre de processus qui intègre de façon cohérente les données et les opérations classiques et quantiques. Pour cette algèbre de processus, nous avons défini une sémantique formelle qui respecte les lois de la mécanique quantique et qui permet une coexistence harmonieuse entre les parties quantiques et les parties classiques d'un même processus. Cette sémantique a conduit à la définition d'une équivalence entre processus du langage<br>No formalism or language existed ta describe completely and rigorously quantum algorithms and protocols. 5ince these algorithms and protocols have necessarily quantum and classical parts, process algebras seemed a good candidate for such a language. 50, in this thesis, we developed a notation, based on process algebras, which provides a homogeneous style for formai descriptions of concurrent and distributed quantum computations comprising bath quantum and classical parts. Based upon an operational semantics that makes sure that quantum abjects, operations and communications operate according ta the postulates of quantum mechanics, an equivalence has been defined among process states considered as having the same behaviour
30
Darrigan, Clovis. "Calcul quantique de susceptibilités électriques dans les solides cristallins." Pau, 2001. http://www.theses.fr/2001PAUU3029.
Full textAbstract:
A la frontiere entre la chimie et la physique, ce travail s'inscrit dans l'etude theorique des proprietes electroniques et optiques de solides cristallins et la comprehension des phenomenes induits par une perturbation electrique exterieure. Notre approche theorique de la matiere est celle des chimistes quanticiens : bases atomiques localisees, orbitales cristallines (oc) construites selon la methode self consistent field (scf) par combinaison lineaire d'orbitales atomiques (lcao) en tenant compte de la symetrie translationnelle. La prevision des comportements de la matiere face a un champ electrique statique (frequence nulle) ou dynamique (frequence non-nulle) passe par l'elaboration de modeles theoriques conduisant aux susceptibilites electriques. Si la perturbation appliquee est faible, la reponse du cristal reste lineaire, nous parlons alors de susceptibilite lineaire (polarisabilite) et des proprietes connexes (constante dielectrique, indice de refraction, reflectivite, fonction de perte d'energie). Les termes d'ordres superieurs, appeles susceptibilites non-lineaires (hyperpolarisabilites), nous conduisent aux phenomenes non-lineaires : generation d'harmoniques, rectification optique, effets pockel, kerr. . . Deux methodes differentes ont ete developpees : 1. Methode couplee (cp), qui inclut analytiquement le potentiel electrique au sein meme du hamiltonien, ou les oc sont relaxees durant le processus scf. Le logiciel crystal98 a ete modifie en consequence. Deux systemes (mgo et lif) ont ete etudies, conduisant a de bonnes valeurs theoriques. 2. Methode non-couplee (uc) sum over states (sos), tenant compte de la frequence du champ perturbateur. Les expressions developpees et generales pour differents ordres sont explicitees. Nous l'appliquons au diamant pour le calcul de la constante dielectrique et la simulation de spectres eels. Des resultats tres encourageants sont obtenus sur le calcul d'effets non-lineaires (shg pour sic, thg pour lif).
31
De, Visme Marc. "Sémantique des Jeux Quantique." Thesis, Lyon, 2020. http://www.theses.fr/2020LYSEN056.
Full textAbstract:
Cette thèse porte sur la sémantique des langages de programmation quantiques, et en particulier sur celle du lambda-calcul quantique, un langage paradigmatique dû à Selinger et Valiron qui marrie flot de contrôle classique riche (fonctions d’ordre supérieur, récursion, etc) avec des données quantiques (création de qubits, mesure, application d’opérateurs unitaires). Pour donner un modèle du lambda-calcul quantique, il convient de trouver une alliance harmonieuse entre les modèles traditionnels de sémantique dénotationnelle (qui donnent du sens aux programmes en les interprétant dans des univers mathématiques adéquats) et les mathématiques du quantique (espaces de Hilbert, matrices de densité, etc). Cette thèse comporte trois contributions principales : Premièrement, nous étendons la sémantique des jeux, une approche dynamique à la sémantique dénotationnelle, au cas quantique. Nous obtenons le premier modèle dénotationnel du lambda-calcul quantique complet qui soit à la fois compositionnel et interactif, c’est à dire qu’il représente la dynamique de l’exécution. Notre modèle est une généralisation naturelle de développements récents pour le cas probabiliste.Deuxièmement, nous relions formellement notre modèle au seul modèle dénotationnel pré-existant du lambda-calcul quantique complet, le modèle relationnel quantique dû à Pagani, Selinger et Valiron. Finalement, nous montrons que notre modèle de jeux est pleinement adéquat, la correspondance idéale entre un langage de programmation et sa sémantique dénotationnelle. Nous en déduisons que le modèle relationnel quantique était lui-aussi pleinement adéquat, un problème que ses auteurs avaient laissé ouvert. Cette thèse se décompose en trois parties. La première partie présente des préliminaires de théorie des catégories, qui permettent de définir un cadre formel englobant à la fois notre modèle de jeux quantique et le modèle relationnel quantique, puis des préliminaires sur les mathématiques du quantique, et enfin des préliminaires sur la programmation quantique et ses modèles. La deuxième partie commence par des préliminaires de sémantique des jeux, et définit notre modèle de jeux quantique dans un cadre simplifié : le lambda-calcul linéaire quantique. Enfin, la troisième partie s'appuie sur la deuxième pour présenter le modèle de jeux quantique complet, prouver que ce modèle est pleinement adéquat, et en déduire que le modèle relationnel quantique est lui aussi pleinement adéquat<br>In this thesis, we study quantum programming languages, and focus on the quantum lambda-calculus, a paradigmatic language defined by Selinger and Valiron, which mixes a rich classical control flow (higher order functions, etc.) and quantum data (qubit creation, measure, and unitary operations). In this thesis, we search for a denotational semantics of this language, in other words, we extract the meaning and behaviour of programs by interpreting them in an adequately chosen mathematical universe. In order to model the quantum lambda-calculus, one must adapt the traditional denotational models to the mathematics of quantum computation (Hilbert spaces, density matrices, etc.). We have three main contributions:Firstly, we extend game semantics to the quantum case. Game semantics is a dynamic approach to denotational semantics, which focuses on the sequence of interactions between a program and its environment. We obtain the first denotational model of the full quantum lambda-calculus which is both compositional and interactive, meaning that it represents the dynamic of the execution. Our model generalise the recently developed model for the probabilistic case.Secondly, we formally link our model to the only pre-existing denotational model of the full lambda-calculus, the quantum relational model of Pagani, Selinger and Valiron.Lastly, we prove that our game model is fully abstract, the gold standard of denotational semantics, which ensures a total correspondence between the programming language and the model. We deduce that the quantum relational model was also fully abstract, which was an open problem.This thesis is constituted of three parts. The first part details some preliminaries on category theory, used for defining a formal framework including both the quantum game model and the quantum relational model, some preliminaries on the mathematics of quantum computation, and then some preliminaries on quantum programming and its models. The second part starts with some preliminaries on game semantics and defines our quantum game model in the simplified case of the linear quantum lambda-calculus. The third part builds on the second part to define the full quantum game model, prove its full abstraction, and deduce that the quantum relational model is fully abstract too
32
Henrio, Ludovic. "Asynchronous object calculus : confluence and determinacy." Nice, 2003. http://www.theses.fr/2003NICE4047.
Full textAbstract:
L'objectif de cette thèse est de concevoir un calcul d'objets permettant d'écrire des applications parallèles et distribuées, en particulier dans un cadre à grande échelle, tout en assurant de bonnes propriétés. Le calcul proposé s'intitule ASP : Asynchronous Sequential Processes. Les principales caractéristiques de ce calcul sont : des communications asynchrones, la présence de futurs et une exécution séquentielle dans chacun des processus. Ce calcul exhibe de fortes propriétés de confluence et de déterminisme. Cette thèse a donc aussi pour objectif de prouver de telles propriétés dans un cadre aussi général que possible. ASP est basé sur une répartition des objets en différentes activités disjointes. Une activité est un ensemble d'objets gérés par un unique processus. Les objets actifs sont des objets accessibles par des références globales/distantes. Ils communiquent à travers des appels de méthodes asynchrones avec un mécanisme de futurs. Un futur est une référence globale désignant un résultat qui n'est pas encore calculé. Cette thèse modélise ces différents aspects, leurs principales propriétés et les conséquences de ces mécanismes sur la notion de comportement déterministe des programmes. Le résultat principal consiste en une propriété de confluence et son application à l'identification d'un ensemble de programmes se comportant de façon déterministe. Du point de vue pratique, ASP peut aussi être considéré comme une modélisation de la librairie ProActive. Cette librairie fournit des outils pour développer des applications parallèles et distribuées en Java<br>The objective of this thesis is to design an object calculus that allows one to write parallel and distributed applications, particularly on wide range networks, while ensuring good properties. This calculus is named ASP : Asynchronous Sequential Processes. The main characteristics of ASP are: asynchronous communications, futures, and a sequential execution within each process. ASP presents strong confluence and determinism properties, proved in a context as general as possible within this thesis. A first design decision is the absence of sharing : objects live in disjoint activities. An activity is a set of objects managed by a unique process and a unique active object. Active objects are accessible through global/distant references. They communicate through asynchronous method calls with futures. A future is a global reference representing a result not yet computed. This thesis models those aspects, their main properties, and the consequences of these mechanisms on the deterministic behavior of programs. The main result consists in a confluence property and its application to the identification of a set of programs behaving deterministically. From a practical point of view, ASP can also be considered as a model of the ProActive library. This library provides tools for developing parallel and distributed applications in Java
33
Trystram, Denis. "Quelques résultats de complexité en algorithmique parallèle et systolique." Grenoble INPG, 1988. http://tel.archives-ouvertes.fr/tel-00009202.
Full textAbstract:
L'objet de cette thèse est l'étude de la parallélisation d'algorithmes du calcul scientifique et leur implémentation sur des ordinateurs parallèles à mémoire partagée et sur des réseaux systoliques. Un accent particulier est mis sur l'obtention de résultats de complexité. La thèse est organisée autour d'articles et textes de conférences qui sont analysés et discutés dans une première partie de façon à permettre de replacer les problèmes traités dans leur contexte. Dans le premier chapitre, nous présentons les principaux résultats théoriques concernant l'étude de complexité des algorithmes parallèles, ainsi qu'une description critique de l'architecture de référence, qui est une machine de type MIMD à mémoire partagée. Le chapitre suivant est dédie" à l'ensemble des résultats de complexité concernant les algorithmes de diagonalisation et l'élimination de Gauss, il a pour but d'illustrer la méthodologie. Il existe en tout dix écritures possibles de la méthode de Gauss, qui conduisent principalement à deux grandes classes de graphes de précédente, conceptuellement différents : les graphes de type "glouton" et ceux du type "2 pas". Ces types de graphes se rencontrent d'une manière plus générale dans d'autres problèmes d'algèbre linéaire et même dans certaines méthodes non numériques de la théorie des graphes. Nous développons les résultats de complexité concernant ces deux types de graphes sur les exemples les plus courant (versions kji et kij de Gauss en parallèle), puis nous montrons comment adapter l'étude en prenant en compte t'es temps de communication entre tes processeurs, ce qui rend le modèle théorique plus réaliste. Le chapitre 6 est consacré aux architectures systoliques. Le problème du chemin algébrique permet d'unifier plusieurs problèmes informatiques. Nous présentons un réseau résolvant ce problème en Sn-2 pas sur un réseau de taille n(n+l ). De plus, quelques modifications permettent de calculer des projections en filtrage adaptatif en vu d'obtenir une solution en temps réel pour le traitement numérique des signaux. Avant de conclure, nous présentons des résultats complémentaires de parallélisation effective sur d'autres types d'architectures : l'étude de l'algorithme du gradient conjugué sur des super calculateurs (CRAY-XMP et IBM 3090-VF).
34
Spaenlehauer, Pierre-Jean. "Résolution de systèmes multi-homogènes et déterminantiels algorithmes - complexité - applications." Paris 6, 2012. http://www.theses.fr/2012PA066467.
Full textAbstract:
De nombreux systèmes polynomiaux multivariés apparaissant en Sciences de l'Ingénieur possèdent une structure algébrique spécifique. En particulier, les structures multi-homogènes, déterminantielles et les systèmes booléens apparaissent dans une variété d'applications. Une méthode classique pour résoudre des systèmes polynomiaux passe par le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés. D'une part, ces outils permettent d'obtenir sousdes hypothèses de généricité des bornes de complexité du calcul debase de Gröbner de plusieurs familles de systèmes polynomiauxstructurés (systèmes bilinéaires, systèmes déterminantiels, systèmesdéfinissant des points critiques, systèmes booléens). Ceci permetd'identifier des familles de systèmes pour lequels la complexité arithmétique de résolution est polynomiale en le nombre de solutions. D'autre part, cette thèse propose de nouveaux algorithmequi exploitent ces structures algébriques pour améliorer l'efficacité du calcul de base de Gröbner et de la résolution (systèmes multi-homogènes, systèmes booléens). Ces résultats sontillustrés par des applications concrètes en cryptologie (cryptanalyse des systèmes MinRank et ASC), en optimisation et en géométrie réelle effective (calcul de points critiques)<br>Multivariate polynomial systems arising in Engineering Science often carryalgebraic structures related to the problems they stem from. Inparticular, multi-homogeneous, determinantal structures and booleansystems can be met in a wide range of applications. A classical method to solve polynomial systems is to compute a Gröbner basis ofthe ideal associated to the system. This thesis provides new tools forsolving such structured systems in the context of Gröbner basis algorithms. On the one hand, these tools bring forth new bounds on the complexity of thecomputation of Gröbner bases of several families of structured systems(bilinear systems, determinantal systems, critical point systems,boolean systems). In particular, it allows the identification of families ofsystems for which the complexity of the computation is polynomial inthe number of solutions. On the other hand, this thesis provides new algorithms which takeprofit of these algebraic structures for improving the efficiency ofthe Gröbner basis computation and of the whole solving process(multi-homogeneous systems, boolean systems). These results areillustrated by applications in cryptology (cryptanalysis of MinRank),in optimization and in effective real geometry (critical pointsystems)
35
Markey, Nicolas. "Logiques temporelles pour la vérification : expressivité, complexité, algorithmes." Orléans, 2003. http://www.theses.fr/2003ORLE2004.
Full textAbstract:
Ce travail s'inscrit dans le cadre de la vérification formelle de programmes: le model checking est une technique qui permet de s'assurer qu'une propriété, exprimée en logique temporelle, est vérifiée par le modèle d'un système. Cette thèse étudie plusieurs logiques temporelles, du point de vue de l'expressivité et de la complexité. Nous étudions trois grands types de logiques temporelles : - concernant la logique temporelle du temps linéaire, nous prouvons que l'ajout de modalités du passé permet de simplifier l'écriture des formules sans augmenter la complexité des problèmes de model checking. Nous étudions également l'impact de l'ajout de la modalité Now ; - concernant la logique temporelle du temps arborescent, nous établissons la complexité du model checking pour plusieurs extensions classiques de CTL ; - enfin, nous montrons qu'il est possible, sous certaines conditions, de vérifier efficacement des propriétés quantitatives sur la durée séparant deux évènements.
36
Iyer, Sridharan Pavithran. "Complexité du décodage des codes stabilisateurs quantiques." Mémoire, Université de Sherbrooke, 2014. http://hdl.handle.net/11143/5388.
Full textAbstract:
Résumé : Ce mémoire porte sur l’étude de la complexité du problème du décodage des codes stabilisateurs quantiques. Les trois premiers chapitres introduisent les notions nécessaires pour comprendre notre résultat principal. D’abord, nous rappelons les bases de la théorie de la complexité et illustrons les concepts qui s’y rattachent à l’aide d’exemples tirés de la physique. Ensuite, nous expliquons le problème du décodage des codes correcteurs classiques. Nous considérons les codes linéaires sur le canal binaire symétrique et nous discutons du célèbre résultat de McEliece et al. [1].
Dans le troisième chapitre, nous étudions le problème de la communication quantique
sur des canaux de Pauli. Dans ce chapitre, nous introduisons le formalisme des codes stabilisateurs pour étudier la correction d’erreur quantique et mettons en évidence le concept de dégénérescence. Le problème de décodage des codes stabilisateurs quantiques négligeant la dégénérescence est appelé «quantum maximum likelihood decoding»(QMLD). Il a été démontré que ce problème est NP-complet par Min Hseiu Heish et al., dans [2]. Nous nous concentrons sur la stratégie optimale de décodage, appelée «degenerate quantum maximum likelihood decoding »(DQMLD), qui prend en compte la présence de la dégénérescence et nous mettons en évidence quelques instances pour lesquelles les performances de ces deux méthodes
diffèrent drastiquement. La contribution principale de ce mémoire est de prouver que DQMLD est considérablement plus difficile que ce que les résultats précédents indiquaient. Dans le dernier chapitre, nous présentons notre résultat principal (Thm. 5.1.1), établissant que DQMLD est #P-complet. Pour le prouver, nous démontrons que le problème de l’évaluation de l’énumérateur de poids d’un code linéaire, qui est #P-complet, se réduit au problème DQMLD. Le résultat principal de ce mémoire est présenté sous forme d’article dans [3] et est présentement considéré pour publication dans IEEE Transactions on Information Theory. Nous montrons également que, sous certaines conditions, les résultats de QMLD et DQMLD coïncident. Il s’agit d’une amélioration par rapport aux résultats obtenus dans [4, 5]. // Abstract : This thesis deals with the study of computational complexity of decoding stabilizer codes. The first three chapters contain all the necessary background to understand the main result of this thesis. First, we explain the necessary notions in computational complexity, introducing P, NP, #P classes of problems, along with some examples intended for physicists. Then, we explain the decoding problem in classical error correction, for linear codes on the binary symmetric channel and discuss the celebrated result of Mcleicee et al., in [1]. In the third chapter, we study the problem of quantum communication, over Pauli channels. Here, using the stabilizer formalism, we discuss the concept of degenerate errors. The decoding problem for stabilizer codes, which simply neglects the presence of degenerate errors, is called quantum maximum likelihood decoding (QMLD) and it was shown to be NP-complete, by Min Hseiu Heish et al., in [2]. We focus on the problem of optimal decoding, called degenerate quantum maximum likelihood decoding (DQMLD), which accounts for the presence of degenerate errors. We will highlight some instances of stabilizer codes, where the presence of degenerate errors causes drastic variations between the performances of DQMLD and QMLD. The main contribution of this thesis is to demonstrate that the optimal decoding problem for stabilizer codes is much harder than what the previous results had anticipated. In the last chapter, we present our own result (in Thm. 5.1.1), establishing that the optimal decoding problem for stabilizer codes, is #P-complete. To prove this, we demonstrate that the problem of evaluating the weight enumerator of a binary linear code, which is #P-complete, can be reduced (in polynomial time) to the DQMLD problem, see (Sec. 5.1). Our principal result is also presented as an article in [3], which is currently under review for publication in IEEE Transactions on Information Theory. In addition to the main result, we also show that under certain conditions, the outputs of DQMLD and QMLD always agree. We consider the conditions developed by us to be an improvement over the ones in [4, 5].
37
Madet, Antoine. "Complexité Implicite de Lambda-Calculs Concurrents." Phd thesis, Université Paris-Diderot - Paris VII, 2012. http://tel.archives-ouvertes.fr/tel-00794977.
Full textAbstract:
Contrôler la consommation en ressources des programmes informatiques est d'importance capitale, non seulement pour des raisons de performance, mais aussi pour des questions de sécurité quand par exemple certains systèmes mobiles ou embarqués disposent de quantités limitées de ressources. Dans cette thèse, nous développons des critères statiques pour contrôler la consommation en ressources de programmes concurrents d'ordre supérieur. Nous prenons comme point de départ le cadre des Logiques Light qui a été étudié afin de contrôler la complexité de programmes fonctionnels d'ordre supérieur au moyen de la correspondance preuves-programmes. La contribution de cette thèse est d'étendre ce cadre aux programmes concurrents d'ordre supérieur. Plus généralement, cette thèse s'inscrit dans le domaine de la complexité implicite qui cherche à caractériser des classes de complexité par des principes logiques ou des restrictions de langage. Les critères que nous proposons sont purement syntaxiques et sont développés graduellement afin de contrôler le temps de calcul des programmes de plus en plus finement: dans un premier temps nous montrons comment garantir la terminaison des programmes (temps fini), puis nous montrons comment garantir la terminaison des programmes en temps élémentaire, et enfin nous montrons comment garantir la terminaison des programmes en temps polynomial. Nous introduisons également des systèmes de types tels que les programmes bien typés terminent en temps borné et retournent des valeurs. Enfin, nous montrons que ces systèmes de types capturent des programmes concurrents intéressants qui itèrent des fonctions produisant des effets de bord sur des structures de données inductives. Dans la dernière partie, nous étudions une méthode sémantique alternative afin de contrôler la consommation en ressources de programmes impératifs d'ordre supérieur. Cette méthode est basée sur la réalisabilité quantitative de Dal Lago et Hofmann et permet d'obtenir plusieurs bornes de complexité de manière uniforme. Cette dernière partie est un travail en collaboration avec Aloïs Brunel.
38
Bonfante, Guillaume. "Constructions d'ordres, analyse de la complexité." Vandoeuvre-les-Nancy, INPL, 2000. http://docnum.univ-lorraine.fr/public/INPL_T_2000_BONFANTE_G.pdf.
Full textAbstract:
Le thème de la thèse concerne l'étude des ordres, en termes de complexité en réécriture, mais aussi dans le cadre des termes ordinaux, des hiérarchies de fonctions sous-récursives. Nous avons cherché à extraire de la notion de preuve de terminaison des informations concernant la complexité des fonctions calculées par des systèmes de réécriture. Cela nous a permis d'établir de nombreuses caractérisations, en termes de complexité, des systèmes de réécriture. Ainsi, est-il possible de déterminer a priori la complexité d’un système, au seul vu de sa preuve de terminaison. Nous étudions plus spécifiquement le cas de l'ordre de Knuth-Bendix et celui de l'ordre par interprétation polynomiale. D'autre part, nous avons entamé une recherche plus fondamentale concernant la représentation de la notion d'ordre dans les λ-calculs typés. Cet intérêt provient de ce qu'une telle représentation est nécessaire dès lors que l'on veut représenter des structures définies par des opérateurs ω -aire, ce qui est le cas des termes ordinaux par exemple. Nous étudions d'un point de vue sémantique l'univers de travail, nous dégageons en particulier une notion de structure monoïdale fermée, mais aussi de manière syntaxique en proposant un calcul pour lequel un type représente un graphe plutôt qu'un (traditionnel) ensemble<br>Our concern in the thesis is in the study of orders, through the analysis of complexity within rewriting, but also through the construction of monotonous λ-calculi within the framework of ordinal terms, and subrecursivc hierarchies. We show how to extract some knowledge in terms of complexity from the proof of termination in rewriting theory. This allows us to establish some hierarchies of caracterisation of complexity classes in terms of rewriting. So, one has an a priori complexity measure of functions with respect to their proof of termination. We study more specifically the case of the Knuth-Bendix ordering and polynomial interpretations. Next to that, we engaged ourselves into an other challenge, a more fundamental approach. This concerns the notion of ordering within typed λ-calculi. The interest comes from the fact that such a representation is necessary when one has to represent a structure with an ω -ary operation: that is an operation that only applies to monotonous sequences (which is the case of ordinal terms). We develop semantical tools, in particular we present a mono id al close category on graphs, but also syntactical constructions, in particular a calcul us where types arc graphs in which the traditional approach would be in terms of sets
39
Duchemin, Ivan. "Calcul quantique Hamiltonien : théorie et application aux portes logiques mono-moléculaires." Toulouse 3, 2006. http://www.theses.fr/2006TOU30243.
Full text
40
Brault-Baron, Johann. "De la pertinence de l’énumération : complexité en logiques." Caen, 2013. http://www.theses.fr/2013CAEN2056.
Full textAbstract:
Au-delà de la décision de problèmes de satisfaisabilité, on s’intéresse à la génération exhaustive de leurs solutions, l’énumération. Nous interrogeons d’abord la pertinence du problème d’énumération dans le cadre très classique de la logique propositionnelle. La dichotomie de Creignou et Hébrard prouve déjà l’équivalence entre les classes polynomiales pour la décision non triviale et celles pour l’énumération. On donne des algorithmes d’énumération optimaux pour chacune de ces classes, qui généralisent tout algorithme de décision non triviale, suggérant que l’énumération est le problème pertinent dans ce cadre. Ensuite, nous complétons et simplifions des résultats de dichotomie de Bagan et al. Qui établissent un lien étroit entre la facilité d’une requête conjonctive et une notion d’acyclicité d’hypergraphe. On prouve alors, grâce à un nouvel d’algorithme, des résultats similaires pour la classe duale de celle des requêtes conjonctives. Finalement, en généralisant le résultat classique de combinatoire de Brouwer et Kolen, on unifie l’ensemble de ces résultats sous forme d’une dichotomie pour l’énumération des requêtes conjonctives dites signées, qui établit un lien fort entre facilité de l’énumération et facilité de la décision<br>Beyond the decision of satisfiability problems, we investigate the problem of enumerating all their solutions. In a first part, we consider the enumeration problem in the framework of the propositional satisfiability problem. Creignou and Hébrard proved that the polynomial classes for the non-trivial sat problem are exactly those for the enumeration problem. We give optimal enumeration algorithms for each of these classes, that generalize any non-trivial decision algorithm for this class. This suggests that enumeration is the relevant problem in this case, rather than the decision problem. Beyond the decision of satisfiability problems, we investigate the problem of enumerating all their solutions. In a first part, we consider the enumeration problem in the framework of the propositional satisfiability problem. Creignou and Hébrard proved that the polynomial classes for the non-trivial sat problem are exactly those for the enumeration problem. We give optimal enumeration algorithms for each of these classes, that generalize any non-trivial decision algorithm for this class. This suggests that enumeration is the relevant problem in this case, rather than the decision problem. In a second part, we simplify and complete some results of Bagan et al. That establish a strong connection between the tractability of a conjunctive query and a notion of hypergraph acyclicity. We establish similar results for the dual class of the class of conjunctive queries, thanks to a new algorithm. Finally, we generalize all these results through a single dichotomy for the enumeration problem of conjunctive signed queries, by generalizing some classical combinatorial result by Brouwer and Kolen. This dichotomy establishes a close connection between enumeration strong tractability and decision strong tractability. In a second part, we simplify and complete some results of Bagan et al. That establish a strong connection between the tractability of a conjunctive query and a notion of hypergraph acyclicity. We establish similar results for the dual class of the class of conjunctive queries, thanks to a new algorithm. Finally, we generalize all these results through a single dichotomy for the enumeration problem of conjunctive signed queries, by generalizing some classical combinatorial result by Brouwer and Kolen. This dichotomy establishes a close connection between enumeration strong tractability and decision strong tractability
41
Kachigar, Ghazal. "Questions de localisabilité pour le calcul distribué." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0339/document.
Full textAbstract:
Cette thèse suit un plan à deux parties. Le point de départ en est la notion de résistance à la localisation, qui est importante en calcul distribué quantique.Dans la première partie, qui est plutôt théorique, nous retraçons l’historique de certaines notions et résultats en information quantique et en calcul distribué, plus précisément le phénomène d’intrication et la condition non-signalling en information quantique et le modèle LOCAL et le problème de coloration en calcul distribué. Ensuite, nous évoquons le modèle φ-LOCAL, développé en 2009 comme adaptation de la condition non-signalling au modèle LOCAL dans le but d’étudier l’existence d’algorithmes distribués quantiques. Finalement, nous soulignons quelques limites du modèle φ-LOCAL à l’aide des notions de consistance globale et de consistance locale, et nous présentons une version plus adéquate de ce modèle.La deuxième partie comporte les principaux résultats techniques obtenus au cours de cette thèse dans le domaine de la théorie des probabilités. Nous introduisons la notion de k-localisabilité qui est une traduction probabiliste du modèle φ-LOCAL. Nous montrons en quoi cette notion est proche, mais plus faible, que la notion de k-dépendance, largement étudiée dans la littérature probabiliste. Nous évoquons des résultats récents autour de la coloration 1-dépendante du chemin qui permettent de conclure au sujet de la coloration 1-localisable du chemin : elle est possible dès qu’il y a plus de quatre couleurs. Dans la suite, nous traitons la question de la possibilité de la coloration 1-localisable du chemin à l’aide de trois couleurs : nous verrons qu’elle n’est pas possible. Pour répondre à cette question, nous avons eu recours à la programmation linéaire et à la combinatoire : en particulier, nous démontrons un théorème qui donne la solution explicite d’un programme linéaire ayant une forme particulière, ainsi qu’une formule pour les nombres de Catalan<br>This thesis is divided in two parts. Its starting point is the concept of resistance to localisation, an important concept in distributed quantum computing.In the first, theoretical part of this thesis, we go over the history of certain concepts and results in quantum information theory and distributed computing, such as the phenomenon of entanglement and the non-signalling condition in the first domain, and the LOCAL model and the colouring problem in the second domain. We then focus on the φ-LOCAL model, whose goal is to study the possibility of quantum distributed algorithms, and which was developedin 2009 by adapting the non-signalling condition to the LOCAL model. We introduce the concepts of global and local consistency in order to emphasise some shortcomings of this model. Finally, we present a more adequate version ofthe φ-LOCAL model.The second part of this thesis contains our major technical results in probability theory. We define the concept of k-localisability which is a probabilistic translation of the φ-LOCAL model. We show that this concept is close to but weaker than the concept of k-dependence which is well-studied in the probabilistic literature. We mention recent results concerning 1-dependent colouring of the path graph and the conclusion they allow us to reach with regards to 1-localisable colouring of the path graph : that it is possible with four or more colours. The rest of this part is dedicated to answering the question of the possibility of 1-localisable colouring of the path graph using three colours which we will show to be impossible. In answering this question we have made use of methods in linear programming and combinatorics. In particular, we prove a theorem on the explicit solution of a linear programming problem having a certain form, and a formula for the Catalan numbers
42
Chapdelaine, Philippe. "Contribution à la théorie de la complexité algorithmique : problèmes de contraintes, complétude et résultats de classification, complexité structurelle." Caen, 2004. http://www.theses.fr/2004CAEN2042.
Full textAbstract:
Cette thèse se divise en deux parties indépendantes ayant comme point commun la théorie de la complexité algorithmique. Dans la première partie, nous étudions la complexité des problèmes de satisfaction de contraintes. Nous montrons que celle-ci est fortement liée au pouvoir d'expression des contraintes, et que celui-ci peut être déterminé, grâce à une correspondance de Galois, par les propriétés de clôture de ces contraintes. Dans le cas booléen, la structure de ce système de clôture étant connue, nous en déduisons des classifications complètes de la complexité des problèmes de l'audit et du comptage pour les requêtes conjonctives. Nous donnons également, par une technique constructive, la classification de la complexité de la recherche locale pour la satisfaisabilité des contraintes booléennes. Dans la deuxième partie, nous nous intéressons à la classe de complexité du temps linéaire non déterministe, NLIN. Nous étudions des raffinements de celle-ci, notamment les classes obtenues en bornant l'espace. Nous montrons qu'elles contiennent de nombreux problèmes naturels, et nous donnons, pour ces classes, des caractérisations logiques et des problèmes complets. Dans un deuxième temps, nous détaillons la structure interne de NLIN. Nous établissons que, sous certaines hypothèses, il existe une infinité de niveaux de réductions linéaires incomparables entre le niveau du temps linéaire déterministe et celui des problèmes NLIN-complets. Nous développons également la notion d'isomorphie linéaire permettant de préciser la notion d'équivalence linéaire en montrant que des problèmes sont, non seulement de même complexité, mais également structurellement identiques.
43
Revol, Nathalie. "Complexité de l'évaluation parallèle de circuits arithmétiques." Grenoble INPG, 1994. http://tel.archives-ouvertes.fr/tel-00005109.
Full textAbstract:
Les algorithmes d'évaluation parallèle des expressions et des circuits arithmétiques peuvent être vus comme des extracteurs du parallélisme intrinsèque contenu dans les programmes séquentiels, parallélisme qui dépasse celui qui peut être lu sur le graphe de précédence et qui tient à la sémantique des opérateurs utilisés. La connaissance des propriétés algébriques, comme l'associativité ou la distributivité, permet une réorganisation des calculs qui n'affecte pas les résultats. Plus la structure algébrique utilisée sera riche en propriétés simples, plus il sera possible d'en tirer parti pour améliorer les algorithmes d'évaluation. Généralisant les algorithmes conçus pour les semi-anneaux, nous proposons un algorithme qui améliore les majorations précédemment connues pour la contraction de circuits arithmétiques dans un treillis. Des simulations de cet algorithme ont permis de mettre en évidence ses qualités de prédicteur automatique de complexité. Réorganiser explicitement les calculs à l'aide de ces algorithmes, c'est-à-dire réaliser un compilateur complet, permet de comparer la réalité des algorithmes parallèles sur machines à mémoire distribuée et la puissance des algorithmes théoriques. Un prototype a été réalisé, basé sur une simplification/extension du langage C. Enfin, l'intérêt de ces techniques dans le domaine de la parallélisation des nids de boucles, pour guider la recherche de réductions cachées dans ces nids, semble prometteuse, parce qu'elle est peu coûteuse à mettre en oeuvre et fournit des informations de qualité. En cela, les recherches en algorithmique parallèle théorique rejoignent les préoccupations de la parallelisation effective
44
Taveneaux, Antoine. "Puissance logique et calculatoire de l'aléa algorithmique." Paris 7, 2013. http://www.theses.fr/2013PA077217.
Full textAbstract:
La théorie de l'aléa effective étudie l'absence de structure qui caractérise l'aléa. La complexité de Kolmogorov est un outil fondamental de cette théorie et nous étudions les propriétés caractéristiques de cette fonctions. Dans un second temps noùs nous intéressons à la possibilité d'étendre l'étude de l'aléa aux suites de bits biaisés en nous demandant si la connaissance précise du biais ou non modifie la qualité de l'aléa que nous décrivons. Nous nous intéressons ensuite à la puissance logique de l'aléa: que peut on déduire du fait (non prouvable) qu'une suite est dénué de structure ? Enfin on s'intéresse a la possibilité de calculer une complétion de l'arithmétique à partir d'un algorithme utilisant de l'aléa<br>Theory of algorithmic randomness theory studies the Jack of structure that characterizes random objects Kolmogorov complexity is a fimdamental tool of this theory and we study the characteristic properties of this fonction. In a second step we investigate the possibility of extending the study of the biased random bit sequences wondering if precise knowledge of using or not changes the quality of randomness we describe, We then focus on the logic power of the random object: What can be inferred from the fact (non provable) that a sequence has no structure? Finally we look a the possibility of calculating a completion of arithmetic from an randomized algorithm
45
Bohuslavskyi, Heorhii. "Electronique cryogénique et réalisation de boîtes quantiques sur substrat SOI pour le calcul quantique." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAY080/document.
Full textAbstract:
Cette thèse étudie l’électronique cryogénique et la réalisation de boîtes quantiques (QD) sur substrat SOI pour le calcul quantique. Deux technologies sont proposées pour la démonstration de boîtes quantiques d’électrons/trous. La première s’appuie sur les dispositifs Trigate SOI développés au CEA-LETI et la seconde exploite la technologie FD-SOI 28nm développée par STMicroelectronics. Dans un premier temps, les dispositifs à double-grille du LETI sont mesurés à très basse température (60mK) pour mettre en avant le principe d’exclusion de Pauli pour les premiers trous confinés à l’intérieur des deux QD. Au travers de cette expérience réalisée sur un double QD nous étudions une brique élémentaire permettant à terme l’initialisation et la lecture d’un qubit. Cette expérience a par la suite été étendue à d’autres dispositifs possédant quatre grilles pour lesquels un protocole de mesure est proposé pour la démonstration de deux qubits de spin d’électron. Dans un second temps, nous avons adressé la question du contrôle, de la lecture et de la manipulation des qubits de spin par une électronique pouvant fonctionner à basse température. Les performances digitales et analogiques des transistors FD-SOI ont été étudiées sur une large gamme de température. La réduction de la température montre une nette amélioration de la mobilité des électrons et des trous mais également une plus faible pente sous le seuil (SS) qui s’accompagne également d’une augmentation de la tension de seuil (Vth). La saturation de la SS pour les faibles températures est expliquée à l’aide d’un modèle analytique développé dans le cadre de cette thèse. En modélisant une queue étroite de densité d'états près des bords des bandes de conduction et de valence et en utilisant la statistique de Fermi-Dirac, un excellent accord est obtenu entre les mesures et le modèle. L’ajout d’une variation exponentielle dans la densité de pièges d’interface permet de reproduire l’évolution de la SS sur plus de 6 décades de courant. Par ailleurs, nous montrons que l’effet d’une polarisation face arrière qui permet d’ajuster la Vth des transistors FD-SOI pour viser des applications haute performance ou basse consommation fonctionne parfaitement à basse température. La modulation de la Vth reste la même de 300K à 4K pour les grandes et petites longueurs de grille des transistors NMOS/PMOS. Afin de tirer avantage de la technologie FD-SOI et d’évaluer son intérêt pour l’électronique cryogénique, nous avons caractérisé plusieurs oscillateurs en anneaux (RO) jusqu’à 4K. L’étude a été réalisée en deux temps. Dans un premier temps, l’augmentation de la Vth à basse température n’a pas été corrigée. Puis, cette augmentation de la Vth a été corrigée grâce à la polarisation face arrière afin de conserver la même Vth que celle mesurée à 300K. Afin de conserver les avantages tirés des plus fortes mobilités des porteurs à basse température, nous montrons que la Vth doit être corrigée pour réduire significativement le délai de commutation d’une chaine d’inverseurs. Nous montrons qu’à 4K un régime de fonctionnement optimal alliant à la fois haute performance et basse consommation peut être obtenu avec une tension d’alimentation (VDD) de 0.3V contre 1V à 300K. Cela permet de réduire de façon significative la dissipation statique et dynamique des RO. Un produit Energie-Délai de 6.9fJ.ps avec un délai par étage de 37ps sont obtenus à VDD = 0.325V grâce à l’utilisation de la polarisation face arrière. Pour finir, nous discutons de la dualité des transistors FD-SOI canal court qui peuvent être utilisés soit comme MOSFET ou comme transistors à électron unique. La présence de QD dans les transistors FDSOI est démontrée avec des caractéristiques proches de celles obtenues avec d’autres architectures (type nanofil) offrant ainsi des perspectives intéressantes pour une future co-intégration d’une électronique cryogénique avec des qubits de spin réalisés à partir d’une même plateforme industrielle<br>This thesis studies cryogenic electronics and quantum dots on silicon-on-insulator (SOI) for quantum computing. Different types of electron and hole quantum dots are fabricated with Leti's SOI nanowire (NW) and planar 28nm FD-SOI technology. In the first part, Pauli Spin Blockade (PSB) is studied for the first holes down to 60mK. We show that it is governed by a strong spin orbit coupling (SOC). The intradot relaxation rate of 120kHz was found for the first holes. The access barriers tunability realized with additional gates was proven to be efficient regarding the isolation of qubit from source/drain metallic leads. Following the recent demonstration of electron-dipole spin resonance (EDSR) achieved in electron quantum dots confined in the corners of silicon nanowire (CDs), we deeply investigated quantum dots in several multi-gate samples under different body-biasing conditions. Based on preliminary cryogenic transport measurements, an operation protocol for a compact two electron spin qubit gate has been proposed.Regarding cryogenic electronics required for an efficient control, manipulation and read-out of a large number of qubits, the low temperature digital and analog performance of 28nm FD-SOI MOSFETs was analysed from room temperature down to 4K. Significant improvements in transistor performance are achieved with a clear enhancement of carrier mobility and a strong reduction of subthreshold swing (SS), even for short-channel devices with gate length down to 28nm. The saturation of the subthreshold swing at low temperature is explained with a new analytical model developed in this thesis. By introducing a narrow tail in the density of states at the edges of the conduction and valence bands and using the Fermi-Dirac statistics, an excellent agreement of SS is achieved between experiments and modelling. The analysis of the SS-IDS metric under different forward body-biasing (FBB) conditions has revealed that the increased density of interface traps cannot be responsible for the SS saturation at low temperature. By adding a slight exponential variation in the interface trap density, we show that the SS-IDS curve can be well reproduced over more than 6 decades, paving a way for an efficient cryogenic design of CryoCMOS.In a second time, cryogenic performance of Ring Oscillators (RO) down to 4K was investigated. We have shown that the optimal supply voltage can be reduced down to 0.3V. This allows to efficiently reduce the dynamic and static power dissipations. At the same time, a small Energy-Delay product of 6.9fJ.ps with a delay per stage of 37ps were achieved at VDD=0.325V under aggressive FBB.Finally, in the last chapter, the duality of short-channel FD-SOI transistors operation as FETs or SETs is demonstrated at 4K. By benchmarking the QDs with respect to the common silicon platforms, we show that 28nm FD-SOI technology has a great potential for both cryogenic electronics and qubits
46
Turuani, Mathieu. "Sécurité des protocoles cryptographiques : décidabilité et complexité." Nancy 1, 2003. http://www.theses.fr/2003NAN10223.
Full text
47
Ceroi, Stéphan. "Ordres et géométrie plane : application au nombre de sauts." Montpellier 2, 2000. http://www.theses.fr/2000MON20114.
Full textAbstract:
P etant un ordre, le nombre de sauts de p est le nombre minimum de comparaisons qu'il faut rajouter a p pour obtenir un ordre total. Ce parametre intervient dans certains problemes d'ordonnancement de taches, et son calcul est np-difficile en general. Par contre la complexite sur les ordres de dimension 2 (i. E. Les ordres qui sont l'intersection de 2 ordres totaux) est inconnue. Cette these presente des arguments de geometrie du plan qui permettent de resoudre certaines questions reliees au probleme du nombre de sauts sur les ordres de dimension 2. Nous montrons que ce probleme est equivalent au probleme suivant : etant donne un ensemble de rectangles ponderes du plan, quel est le poids maximum d'un sous-ensemble constitue de rectangles 2 a 2 disjoints ? grace a cette interpretation, nous montrons que le calcul est polynomial sur la classe des ordres de hauteur h (meme dans la version ponderee ou on attribue un poids a chaque couverture), alors que cette derniere version ponderee est np-difficile si la hauteur est quelconque, montrant que la complexite du probleme est dependante de la hauteur de l'ordre. D'autre part, nous nous interessons aux 2 ordres totaux dont un ordre p de dimension 2 est l'intersection, vis a vis du nombre de sauts, montrant entre autre que la somme des nombres de sauts produits par l'un et l'autre de ces ordres totaux ne depend que du graphe d'incomparabilite de p. Par ailleurs, nous nous interessons a certains problemes de representation des ordres de dimension 2 et 3. En montrant que les ordres de dimension 3 sont exactement les ordres d'inclusion de triangles isothetiques dans le plan, nous prouvons que la complexite de set packing passe de polynomial a np-complet lorsque le biparti d'adjacence sous-jacent passe de la dimension 2 a la dimension 3.
48
Leroy, Julien. "Contribution à la résolution de la conjecture S-adique." Amiens, 2012. http://www.theses.fr/2012AMIE0101.
Full textAbstract:
Cette thèse concerne la Conjecture S-adique qui stipule l'existence d'une version forte de S-adicité dans les suites qui serait équivalente à une complexité p (en facteurs) sous-linéaire. Une suite w à valeurs dans un alphabet fini A est dite S-adique si S est un ensemble de morphismes permettant de dé-substituer indéfiniment w. Sans condition supplémentaire, la complexité en facteurs d'une suite S-adique peut être arbitrairement grande. Cependant, de nombreuses familles de suites bien connues admettent des développements S-adiques avec S de cardinalité finie et sont également de complexité sous-linéaire. La conjecture S-adique apparaît alors naturellement comme une tentative de relier ces deux notions. Dans cette thèse, nous étudions en détails une méthode constructive basée sur les graphes de Rauzy et qui produit un développement S-adique des suites uniformément récurrentes de complexité sous-linéaire. Par ce biais, nous exhibons certaines propriétés nécessaires (mais pas suffisantes) du développement obtenu. Dans le cas particulier des suites uniformément récurrentes dont la différence première de complexité est majorée par deux, cette méthode est poussée à l'extrême, si bien que les conditions nécessaires obtenues en deviennent suffisantes<br>This thesis is about the S-adic conjecture which supposes the existence of a stronger notion of S-adicity that would be equivalent to having a sub-linear factor complexity. A sequence w over a finite alphabet A is said to be S-adic if S is a set of morphisms that allows to indefinitely de-substitute w. Without additional condition, the factor complexity of an S-adic sequence might be arbitrarily large. However, many well-known families of sequences have a sub-linear complexity and admit some S-adic expansions with a finite set S. The S-adic conjecture is therefore a natural attempt to link these two notions. In this thesis, we study in detail a method based on Rauzy graphs that provides an S-adic expansion of uniformly recurrent sequences with a sub-linear complexity. By this way we are able to determine some necessary (but not sufficient) conditions of these expansions. In the particular case of uniformly recurrent sequences with first difference of complexity bounded by two, the method is studied with even much more details, which makes the necessary conditions sufficient
49
Simoncini, David. "Sélection topologique dans les algorithmes évolutionnaires cellulaires : étude du compromis exploration exploitation." Nice, 2009. http://www.theses.fr/2009NICE4079.
Full textAbstract:
Les algorithmes évolutionnaires sont des méthodes d'optimisation approchées manipulant une population de solutions. Leur fonctionnement s'inspire de la théorie de l'évolution de Darwin. L'application combinée d'opérateurs stochastiques et de mécanismes de sélection permet de renouveler la population en explorant l'espace de recherche et en exploitant la qualité des solutions déjà découvertes. La vitesse de convergence d'un algorithme évolutionnaire dépend de sa capacité à générer de nouvelles solutions performantes en se dirigeant vers des régions prometteuses de l'espace de recherche et de celles des solutions à survivre en fonction de leur qualité déterminée par la pression de sélection. Celle-ci permet de contrôler le compromis entre exploration et exploitation et d'éviter une convergence prématurée vers un optimum local. Les algorithmes évolutionnaires cellulaires introduisent une notion de voisinage géographique en structurant spatialement les solutions sur une grille. Cela permet d'ajouter un niveau topologique entre les niveaux phénotypique et génotypique. Dans ce contexte, nous définissons de nouvelles méthodes de sélection permettant à l'aide d'un paramètre continu et borné de contrôler la topologie et ainsi d'obtenir des dynamiques plus complexes. Plutôt que de restreindre les solutions à évoluer sur une grille régulière où chaque cellule est indifférenciée, nous proposons d'enrichir la topologie en introduisant des notions d'anisotropie et de localité. Nous étudions l'influence de la sélection topologique sur la préservation de la diversité génotypique. Les expériences menées sur deux classes de problèmes NP-complets montrent que la prise en compte d'un point de vue topologique permet d'obtenir un bon équilibre entre exploration et exploitation. Dans le but d'étudier la dynamique de recherche et en particulier d'analyser l'efficacité des compromis observés, nous définissons un modèle théorique basé sur la notion d'équilibres ponctués. Enfin, nous proposons des algorithmes de contrôle utilisant la sélection topologique afin de réguler dynamiquement la pression de sélection et ainsi de gérer le rapport entre phases d'exploration et d'exploitation sans connaissance a priori sur les problèmes étudiés<br>Evolutionary algorithms are stochastic optimization methods manipulating a population of solutions. Their behaviour is inspired by Darwin's theory of evolution. The combined application of stochastic operators and selection mechanisms allow renewing the population by exploring the search space and exploiting the already found solutions. The convergence speed of an evolutionary algorithm relies on its ability to generate efficient solutions by leading the search toward promising regions of the search space, and the ability of solutions to survive according to their fitness defined by the selective pressure. The latter allows dealing with the exploration / exploitation trade-off and prevents the algorithm from converging prematurely toward a local optimum. Evolutionary cellular algorithms introduce a notion of geographical neighborhood by embedding the solution on a grid. This adds a topological level between the phenotypical and genotypical ones. In this context, we define new selection methods that allow controlling the topology and obtain complex dynamics thanks to a single continuous and bounded parameter. Instead of restricting solutions to evolve on a uniform grid, we propose to enhance the topology with notions of anisotropy and locality. We study the influence of the topological selection on the preservation of genotypic diversity. Experiences made on two classes of NP-complete problems show that taking into account the topological level leads to a fine equilibrium between exploration and exploitation. In order to study the search dynamic and especially to analyze the efficiency of the observed trade-offs, we define a model based on the notion of punctuated equilibria. Finally, we propose adaptive algorithms in the intent of dynamically controlling the selective pressure and thus dealing with the relation between exploration and exploitation phases without any knowledge on the studied problems
50
Afif, Mohammed. "Approches algorithmiques pour la résolution de certains problèmes NP-Complets." Paris 9, 1999. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1999PA090026.
Full textAbstract:
L'objet de cette thèse est de présenter de nouvelles approches de résolution de certains problèmes combinatoires de la classe NP-Complet. Ces approches sont représentées par des algorithmes efficaces basés sur des métaphores physiques ou sur des modèles qui se caractérisent par des solutions non combinatoires. Dans la première partie nous définirons les problèmes combinatoires traites, et les modèles mathématiques que nous avons défini pour les étudier. Nous avons aussi, pour chacun des problèmes étudiés, défini les algorithmes classiques de résolution optimale et approchée, ainsi que les méthodes et les heuristiques proposées. Dans la seconde partie, nous avons illustré par une étude expérimentale et comparative, les performances ainsi que les lacunes des différents algorithmes présentés