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].

La première partie aborde la conception et la mise en œuvre d'un outil d'analyse syntaxique capable de manipuler des informations syntaxiques et sémantiques. La problématique de l'analyse d'une langue naturelle est d'abord présentée: nous essayons de montrer quels sont les invariants de quelques formalismes récents et comment ces invariants ont motive nos choix. Nous décrivons ensuite le constructeur de structures de dépendances que nous proposons et les apports d'une hiérarchie de catégories a la souplesse et a la tolérance de l'analyse. Les arbres de dépendances produits sont décores grâce a un formalisme de représentation de la connaissance base sur des structures de traits intégrant un mécanisme d'héritage. Nous terminons en présentant le prototype d'analyseur que nous avons réalisé. La deuxième partie définit une architecture pour un système de détection et de correction qui exploite de manière cohérente tous les outils dont nous disposons. Les outils de niveau lexical comprennent un analyseur et un générateur morphologiques et des modules de correction lexicale utilisant trois techniques: phonétique, morphologie et clé squelette. Après avoir décrit les objectifs fixes pour le niveau syntaxique, nous donnons un aperçu du vérificateur syntaxique dont nous disposons et nous soulignons les apports des concepts et outils de la première partie a la robustesse des traitements. Enfin, nous proposons l'architecture d'un système complet de détection et correction d'erreurs dans un texte écrit en insistant sur sa portabilité et son adaptabilité.

L'encodage topologique de l'information quantique a attiré beaucoup d'attention, car c'est un modèle qui semble propice à résister aux erreurs locales. Tout d'abord, le modèle du calcul topologique est basé sur la statistique anyonique non-Abélienne universelle et sur son contrôle. Des anyons indésirables peuvent apparaître soudainement, en raison de fluctuations thermiques ou de processus virtuels. La présence de ces anyons peut corrompre l'information encodée, il est nécessaire de les éliminer: la correction consiste à fusionner les défauts tout en préservant la topologie du système. Ensuite, dans le cas des codes topologiques, on doit aussi protéger l'information encodée dans la topologie. En effet, dans ces systèmes, on n'a accès qu'à une fraction de l'information décrivant l'erreur. Elle est recueillie par des mesures et peut être interprétée en termes de particules. Ces défauts peuplent le code et doivent être annihilés adéquatement dans le but de préserver l'information encodée. Dans ce mémoire, nous proposons un algorithme efficace, appelé décodeur, pouvant être utilisé dans les deux contextes décrits ci-haut. Pour y parvenir, cet algorithme s'inspire de méthodes de renormalisation et de propagation de croyance. Il est exponentiellement plus rapide que les méthodes déjà existantes, étant de complexité [Caractères spéciaux omis] (l[indice supérieur 2] log l) en série et, si on parallélise, [Caractères spéciaux omis] (log l) en temps, contre [Caractères spéciaux omis] (l[indice supérieur]6) pour les autres décodeurs. Le temps étant le facteur limitant dans le problème du décodage, cette caractéristique est primordiale. De plus, il tolère une plus grande amplitude de bruit que les méthodes existantes; il possède un seuil de ~ 16.5% sur le canal dépolarisant surpassant le seuil déjà établi de ~ 15.5%. Finalement, il est plus versatile. En effet, en étant limité au code de Kitaev, on ne savait pas décoder les codes topologiques de manière générale (e.g. codes de couleur). Or, le décodeur proposé dans ce mémoire peut traiter la grande classe des codes topologiques stabiliseurs.

L'un des principaux obstacles pour construire un ordinateur quantique est la décohérence, laquelle limite grandement le temps alloué pour un calcul ainsi que la taille du système. Pour combattre la décohérence dans un système quantique, des protocoles de correction d'erreurs ont été proposés et semblent apporter une bonne solution à ce problème. Ces protocoles consistent à confiner l'information que contiennent les qubits dans un sous-espace nommé espace code. Après un certain temps d'évolution, on pose un diagnostic sur l'erreur qui s'est produite sur le système en effectuant des mesures indiquant s'il est toujours dans l'espace code où s'il a évolué vers un autre sous-espace. Pour que de tels protocoles soient efficaces, les mesures effectuées doivent en principe être rapides et projectives. Cependant, pour plusieurs architectures de qubits existantes, les mesures sont faibles et se font de façon continue. De plus, elles peuvent introduire elles-mêmes des erreurs dans le système. Ces caractéristiques de mesure rendent difficile le diagnostic de l'erreur tel qu'il est effectué traditionnellement. Aussi comme les mesures peuvent introduire des erreurs, il n'est pas certain que les protocoles de diagnostic d'erreur traditionnels soient utiles. Dans ce travail, on étudie l'utilité d'une mesure faible et continue dans un processus de correction d'erreurs. Cette étude s'est réalisée en deux volets. D'abord, on présente un protocole de correction d'erreur adapté aux architectures de qubits dont la mesure est faible et se fait de façon continue. On montre que ce protocole permet d'évaluer sous quelles conditions une mesure présentant ces caractéristiques peut aider à corriger des erreurs. Ensuite, on teste ce protocole de correction dans le cas particulier des qubits supraconducteurs. On établit sous quelles conditions la mesure sur ces qubits peut aider à diagnostiquer les erreurs et on étudie l'effet de différents paramètres expérimentaux dans ce contexte.

Le système d'identification automatique (ou système AIS pour automatic identification system) est un système qui permet aux navires et aux stations côtières de s'échanger certaines informations par radio VHF. Ces informations comprennent l'identifiant, le statut, la position, la direction et la vitesse de l'émetteur. L'objectif de cette thèse est de permettre la réception des messages AIS par un satellite en orbite basse sans modifier le matériel existant équipant les navires. Par l'intermédiaire du système AIS, il devient possible de connaitre la position de tous les navires à travers le monde. Plusieurs nouveaux services sont possibles, comme le contrôle maritime global ou, pour les armateurs, la connaissance constante de la position de leurs bateaux. La réception par satellite des signaux AIS est sujette à un niveau de bruit bien plus élevé que lors de la réception de ces signaux au niveau du sol. Ce niveau de bruit rend les méthodes classiques de réception de ces signaux difficilement utilisables. Une première contribution de cette thèse est le développement de nouveaux démodulateurs utilisant des méthodes de correction d'erreurs. Ceux-ci tirent parti de la présence d'un bloc de contrôle de redondance cyclique (CRC) dans les messages ainsi que de certaines informations connues sur la structure des messages et des données. Des adaptations du récepteur proposé ont également été étudiées afin d'intégrer la poursuite de la phase des signaux reçus et de prendre en compte les collisions des messages envoyés simultanément par plusieurs navires. La dernière partie de cette thèse est consacrée à l'étude des méthodes de localisation des navires ne diffusant pas leur position dans leurs messages AIS. Cette localisation tire parti des paramètres des messages reçus tels que le délai de propagation et le décalage en fréquence de la porteuse dû à l'effet Doppler, et d'un modèle de déplacement des navires. / The automatic identification system (AIS) is a system allowing ships and coast stations to exchange some information by VHF radio. This information includes the identifier, status, location, direction and speed of the emitter. The aim of this thesis is to allow the reception of AIS messages by low Earth orbit satellites without modifying the existing ship equipments. With this system, it becomes possible to know the position of all ships over the Earth. As a consequence, several new services become available, such as global traffic monitoring or determining boat location (for ship-owners). Satellite reception of AIS signals is subjected to a higher noise level when compared to ground level reception. This noise makes classical demodulation and decoding methods unusable. A first contribution of this thesis is to develop new demodulators using error correction methods. These demodulators take advantage of the presence of a cyclic redundancy check (CRC) block in the messages as well as known information about the structure of messages and data. Generalizations of the proposed receiver have also been studied in order to take into account the phase noise of the received signals and the possible collision of messages sent simultaneously by several vessels. The last part of this thesis is devoted to the study of localization methods for ships that do not transmit their location in AIS messages. This localization takes advantage of information contained in the received messages such as the propagation delay and the carrier frequency shift due to the Doppler effect, and a ship movement model.

In this thesis, we investigate the optimization of Raptor codes for various channels of interest in practical wireless systems. First, we present an analytical asymptotic analy- sis of jointly decoded Raptor codes over a BIAWGN channel. Based on the analysis, we derive an optimization method for the design of efficient output degree distributions. We show that even though Raptor codes are not universal on other channels than the BEC, Raptor code optimized for a given channel capacity also perform well on a wide range of channel capacities when joint decoding is considered. Then, we propose a rate splitting strategy that is efficient for the design of finite length Raptor codes. We next investigate the extension of the analysis to the uncorrelated Rayleigh-fading chan- nel with perfect channel state information (CSI) at the receiver, and optimize Raptor codes for quasi-static fading channels when CSI is available at the receiver but not at the transmitter. Finally, we show that in presence of imperfect CSI at the receiver, it is possible to improve the performance with no additional complexity, by using an appropriate metric for the computation of the LLR at the output of the channel. In the second part of this thesis, we investigate the construction of efficient finite length LDPC codes. In particular, we present some improvements for the Progressive Edge- Growth algorithm that allow to construct minimal graphs. The proposed algorithm is used to construct protographs with large girth that perform well under iterative decoding. Moreover, we propose an efficient structured search procedure for the design of quasi-cyclic LDPC codes.

Dans cette thèse, nous développons des méthodes de contrôle pour stabiliser des systèmes quantiques en temps continu sous mesures quantiques non-destructives. En boucle ouverte, ces systèmes convergent vers un état propre de l'opérateur de mesure, mais l'état résultant est aléatoire. Le rôle du contrôle est de préparer un état prescrit avec une probabilité de un. Le nouvel élément pour atteindre cet objectif est l'utilisation d'un mouvement Brownien pour piloter les actions de contrôle. En utilisant la théorie stochastique de Lyapunov, nous montrons stabilité exponentielle globale du système en boucle fermés. Nous explorons aussi la syntèse du contrôle pour stabiliser un code correcteur d'erreurs quantiques en temps continu. Un autre sujet d'intérêt est l'implementation de contrôles efficacement calculables dans un contexte expérimental. Dans cette direction, nous proposons l'utilisation de contrôles et filtres qui calculent seulement les characteristiques classiques du système, correspondant a la base propre de l'opérateur de mesure. La formulation de dites filtres est importante pour adresser les problèmes de scalabilité du filtre posées par l'avancement des technologies quantiques. / In this thesis, we develop control methods to stabilize quantum systems in continuous-time subject to quantum nondemolition measurements. In open-loop such quantum systems converge towards a random eigenstate of the measurement operator. The role of feedback is to prepare a prescribed eigenstate with unit probability. The novel element to achieve this is the introduction of an exogenous Brownian motion to drive the control actions. By using standard stochastic Lyapunov techniques, we show global exponential stability of the closed-loop dynamics. We explore as well the design of the control layer for a quantum error correction scheme in continuous-time. Another theme of interest is towards the implementation of efficiently computable control laws in experimental settings. In this direction, we propose the use control laws and of reduced-order filters which only track classical characteristics of the system, corresponding to the populations on the measurement eigenbasis. The formulation of these reduced filters is important to address the scalability issues of the filter posed by the advancement of quantum technologies.

Cette thèse étudie les déterminants de l’épargne des ménages, à la fois dans leur dimension microéconomique et macroéconomique, en coupe et en panel. L’étude de ces déterminants ne se limite pas au cas français, mais est également étendue à la zone euro, au Royaume-Uni et aux États-Unis. Le premier chapitre introductif rappelle les principaux modèles et théories de l’épargne développés depuis les années 1930, et compare les approches macroéconomique et microéconomique de l’épargne des ménages. Les principales différences entre ces deux approches sont mises en exergue, ainsi que les hypothèses qui sous-tendent le passage du niveau micro au niveau agrégé. Dans un deuxième chapitre, on teste d'abord l’homogénéité des comportements d'épargne en étudiant les liens entre taux d’épargne et revenu (courant et permanent) des ménages français, à partir des données de l'enquête INSEE Budget de famille 2011. On met ensuite empiriquement en évidence et on quantifie une épargne de précaution liée au risque sur le revenu. Dans un troisième chapitre, on s’attache à décrire et à expliquer l’hétérogénéité des comportements d’épargne à l’intérieur et entre les pays européens, à partir des déterminants socio-économiques et des variables de protection sociale. On cherche ainsi à mettre en évidence un effet d'éviction entre épargne publique et épargne privée. Le dernier chapitre exploite la dimension macroéconomique de l'épargne et de la consommation : on passe en revue les principaux déterminants de la consommation (donc de l’épargne), avec une analyse particulière de l’effet de richesse, c’est à dire l’impact du patrimoine financier et immobilier sur le comportement d’épargne. / This PhD dissertation investigates the determinants of households’ savings, both in theirmicro- and macroeconomic dimensions, on cross section and panel data. This analysis is notrestricted to the French case, but also examines the euro area, the United Kingdom and theUnited States. The introduction recalls main models and theories of savings which were developed in the 1930s, and compares the macroeconomic and microeconomic approaches of households’ savings. The main discrepancies between these two approaches are highlighted, as well as the hypotheses which underpin the aggregation of data. In the second chapter, I investigate the relationship between savings rates and (current and permanent) income to test the homogeneity of French households’ behaviours. Then I highlight and measure precautionary savings related to the income risk. In the third chapter, I describe the heterogeneity of savings behaviours within and between European countries, by analyzing social and economic determinants and social protection variables. I try to highlight a crowding-out effect between public and private savings. The last chapter is on the macroeconomic side: the main determinants of consumption (and savings) are scanned, with an emphasis on wealth effect – i.e. the effect of financial wealth and real estate wealth on savings rate.

Dans cette thèse, nous proposons des modèles pour évaluer les performances des applications multimédias temps-réel. De plus, nous proposons un modèle pour les protocoles de type AIMD. Le premier sujet étudié est un mécanisme de correction d'erreurs (FEC). Premièrement, nous utilisons une file d attente M/M/1/K pour modéliser le réseau. Nous considérons que la qualité de la voix varie linéairement par rapport au taux de redondance de la FEC. La redondance du i-ème paquet est portée dans le paquet i+f. Notre analyse montre que, même pour le cas f->inf, ce mécanisme n'améliore pas la qualité de l'audio. Deuxièmement, nous modélisons notre système par une file M/G/1/K. Nous considérons deux aspects qui peuvent contribuer à améliorer la qualité de l'audio: (a) multiplexer l'audio avec un flux exogène, et (b) des fonctions d'utilité non-linéaires. Sous ces contraintes, on montre qu il est possible d'améliorer la qualité de l'audio avec la méthode FEC étudiée. Le deuxième sujet traité concerne les mécanismes de contrôle du délai de diffusion. Nous proposons un ensemble d'algorithmes de moyenne mobile permettant de contrôler le taux de pertes dans une session audio. Les performances de nos algorithmes ont été évaluées et comparées grâce à des traces réelles. Le troisième sujet abordé concerne les protocoles de type AIMD. Nous proposons un modèle analytique, prenant en compte la variabilité du délai. Notre modèle utilise des équations de différences stochastiques. Il fournit une expression close pour le débit et pour la taille de la fenêtre. Nous montrons, par analyse et par simulation, qu'une augmentation de la variabilité du délai améliore les performances d'un protocole AIMD.

Le contrôle quantique constitue un enjeu majeur de la Physique contemporaine. Après un bref tour d'horizon du domaine, nous présentons une méthode, appelée contrôle non holonôme, qui permet d'imposer à système quantique quelconque une évolution unitaire arbitrairement choisie. Dans le contexte de l'Informatique Quantique, cette technique peut être utilisée pour réaliser n'importe quelle porte quantique : à titre d'exemple, nous montrons comment appliquer une porte CNOT à un système de deux atomes de Césium froids en interaction.<br />L'interaction de l'ordinateur avec son environnement risque de compromettre sa fiabilité. Le développement récent de la correction d'erreurs quantiques, inspirée des techniques classiques, suggère néanmoins que ce danger peut être évité. Après une présentation succincte du cadre général de la correction d'erreurs, nous proposons une méthode de protection de l'information fondée sur l'effet Zénon. Cette méthode est ensuite appliquée à un atome de Rubidium.