L'incertitude profonde pesant sur l'évolution future des systèmes hydriques représente un défi considérable pour leur modélisation et planification. En réponse à ce défi, plusieurs approches, qualifiées d'ascendantes, proposent une inversion de paradigme, en employant une démarche d'aide à la décision robuste plutôt que prédictive. Parmi ces approches, la surface de réponse est un outil fréquent permettant de comparer des décisions alternatives sous forte incertitude. Cette méthode consiste à modéliser la performance d'un système hydrique pour un grand nombre de conditions possibles, échantillonnées en fonction d'un nombre limité de variables, nommées stresseurs, afin d'identifier deux ensembles : l'espace des conditions acceptables et l'espace des conditions inacceptables, selon que la performance simulée du système y satisfait ou non un seuil d'acceptabilité. Pour comparer différentes options envisagées, ce type de méthode nécessite cependant de départager, dans l'espace des conditions possibles, les régions acceptables ou inacceptables en traçant un front net et unique. Les recommandations de l'analyse sont donc soumises à une incertitude normative pesant sur ce front d'acceptabilité : comment définir une performance acceptable ? Acceptable pour qui ? La présente thèse de doctorat intègre l'effet de cette incertitude normative sur une surface de réponse à travers deux axes : ambiguïté et équité. L'ambiguïté est une incertitude normative sur la capacité des acteurs d'un système hydrique à fournir un seuil précis. L'équité porte sur les conséquences des choix d'agrégation des acteurs entre lesquels la performance du système peut varier considérablement. L'ambiguïté du seuil est traduite en logique floue et intégrée à l'incertitude hydroclimatique propre à la surface de réponse. Une méthodologie est proposée pour combiner deux incertitudes de nature très différente, la stochasticité de la surface de réponse et l'ambiguïté de son évaluation, à travers une régression logistique agrégée et une mesure de possibilité. La méthode est illustrée à travers une modélisation du système de réservoirs du Haut Saint-François (Québec méridional, Canada), sous l'angle de la protection face aux inondations. L'équité est analysée en paramétrant des méthodes d'agrégation selon différentes priorités et appliquées à un grand nombre d'usagers. Cela permet d'identifier quels niveaux d'agrégation conduisent à recommander une politique ou une autre. Un modèle multi-agent du système hydrique Jordanien est utilisé pour simuler l'approvisionnement inégal en eau potable des ménages et l'effet de différentes politiques de développement d'infrastructures ou de restructuration de l'approvisionnement. Les résultats montrent comment ces incertitudes normatives peuvent modifier la recommandation d'une analyse de vulnérabilité et comment intégrer ces incertitudes à la surface de réponse. Dans le cas du système du Haut Saint-François, les surfaces de réponse illustrent comment les niveaux de possibilité sont modifiés par le seuil flou et sa fonction d'appartenance, affectant potentiellement la recommandation. Dans le cas Jordanien, le choix d'agrégation modifie fortement la surface de réponse, parfois plus que les politiques augmentant les ressources disponibles. Les résultats montrent aussi les effets non-linéaires que divers types de distribution statistique de l'approvisionnement en eau peuvent avoir sur les surfaces de réponse. Les niveaux d'agrégation menant à différentes préférences sont identifiables, permettant d'établir une relation entre les options disponibles, choix social et incertitude profonde afin d'expliciter les arbitrages et favoriser la délibération. En proposant des outils pour intégrer ces incertitudes normatives aux approches ascendantes d'analyse des systèmes hydriques, ce travail ouvre également des pistes de recherche futures telles que la combinaison de ces deux approches par agrégation de seuils flous, ou leur inclusion au sein de cadres plus vastes d'analyse de vulnérabilité hydrique.

De nombreux systèmes de communication sans fil ont adopté les codes turbo et les codes convolutifs comme schéma de codes correcteurs d'erreurs vers l'avant (FEC) pour les données et les canaux généraux. Toutefois, certaines versions proposent les codes LDPC pour la correction d'erreurs en raison de la complexité de l'implémentation des décodeurs turbo et le succès de certains codes LDPC irréguliers dans la réalisation des mêmes performances que les codes turbo les dépassent dans certains cas avec une complexité de décodage plus faible. En fait, les nouvelles versions des standards de ces systèmes travaillent côte à côte dans des dispositifs réels avec les plus anciennes qui sont basées sur les codes turbo et les codes convolutifs. En effet, ces deux familles de codes offrent toutes deux d'excellentes performances en termes de taux d'erreur binaire (TEB). Par conséquent, il semble être une bonne idée d'essayer de les relier de manière à améliorer le transfert de technologie et l'hybridation entre les deux méthodes. Ainsi, la conception efficace de décodeurs universels des codes convolutifs, turbo, et LDPC est critique pour l'avenir de l'implémentation des systèmes sans fil. En outre, un décodeur efficace pour les codes turbo et codes convolutifs est obligatoire pour la mise en oeuvre de ces systèmes sans fil. Cela pourrait se faire par l'élaboration d'un algorithme de décodage unifié des codes convolutifs, turbo et LDPC par des simulations et des études analytiques suivies d'une phase de mise en oeuvre. Pour introduire ce décodeur universel, il existe deux approches, soit sur la base de l'algorithme du maximum a posteriori (MAP) ou l'algorithme de propagation de croyance (BP). D'une part, nous étudions une nouvelle approche pour décoder les codes convolutifs et les turbo codes au moyen du décodeur par propagation de croyances (BP) décodeur utilisé pour les codes de parité à faible densité (codes LDPC). En outre, nous introduisons un système de représentation général pour les codes convolutifs par des matrices de contrôle de parité. De plus, les matrices de contrôle de parité des codes turbo sont obtenus en traitant les codes turbo parallèles comme des codes convolutifs concaténés. En effet, l'algorithme BP fournit une méthodologie très efficace pour la conception générale des algorithmes de décodage itératif de faible complexité pour toutes les classes des codes convolutifs ainsi que les turbo-codes. Alors qu'une petite perte de performance est observée lors du décodage de codes turbo avec BP au lieu du MAP, cela est compensé par la complexité moindre de l'algorithme BP et les avantages inhérents à une architecture unifiée de décodage. En outre, ce travail exploite la représentation tail-biting de la matrice de contrôle de parité des codes convolutifs et des codes turbo, ce qui permet le décodage par un algorithme de propagation de croyance unifiée (BP) pour les nouveaux systèmes de communication sans fils tels que le WiMAX (Worldwide Interoperability for Microwave Access) et le LTE (Long Term Evolution). D'autre part, comme solution alternative, une recherche est effectuée sur la façon de produire un décodeur combiné de ces deux familles de codes basé sur l'algorithme MAP. Malheureusement, cette seconde solution nécessite beaucoup de calculs et de capacité de stockage pour sa mise en oeuvre. En outre, ses récurrences en avant et en arrière résultent en de longs délais de décodage. Entre temps, l'algorithme MAP est basé sur le treillis et la structure en treillis du code LDPC est suffisamment compliquée en raison de la matrice de contrôle de parité de grande taille. En conséquence, cette approche peut être difficile à mettre en oeuvre efficacement car elle nécessite beaucoup de calculs et une grande capacité de stockage. Enfin, pour prédire le seuil de convergence des codes turbo, nous avons appliqué la méthode de transfert d'information extrinsèque (EXIT) pour le décodeur correspondant en le traitant comme une concaténation de noeuds de variable et de contrôle.

<p>La distribution quantique de clés est une technique cryptographique permettant l'échange de clés secrètes dont la confidentialité est garantie par les lois de la mécanique quantique. Le comportement particulier des particules élémentaires est exploité. En effet, en mécanique quantique, toute mesure sur l'état d'une particule modifie irrémédiablement cet état. En jouant sur cette propriété, deux parties, souvent appelées Alice et Bob, peuvent encoder une clé secrète dans des porteurs quantiques tels que des photons uniques. Toute tentative d'espionnage demande à l'espion, Eve, une mesure de l'état du photon qui transmet un bit de clé et donc se traduit par une perturbation de l'état. Alice et Bob peuvent alors se rendre compte de la présence d'Eve par un nombre inhabituel d'erreurs de transmission.</p> <p>L'information échangée par la distribution quantique n'est pas directement utilisable mais doit être d'abord traitée. Les erreurs de transmissions, qu'elles soient dues à un espion ou simplement à du bruit dans le canal de communication, doivent être corrigées grâce à une technique appelée réconciliation. Ensuite, la connaissance partielle d'un espion qui n'aurait perturbé qu'une partie des porteurs doit être supprimée de la clé finale grâce à une technique dite d'amplification de confidentialité.</p> <p>Cette thèse s'inscrit dans le contexte de la distribution quantique de clé où les porteurs sont des états continus de la lumière. En particulier, une partie importante de ce travail est consacrée au traitement de l'information continue échangée par un protocole particulier de distribution quantique de clés, où les porteurs sont des états cohérents de la lumière. La nature continue de cette information implique des aménagements particuliers des techniques de réconciliation, qui ont surtout été développées pour traiter l'information binaire. Nous proposons une technique dite de réconciliation en tranches qui permet de traiter efficacement l'information continue. L'ensemble des techniques développées a été utilisé en collaboration avec l'Institut d'Optique à Orsay, France, pour produire la première expérience de distribution quantique de clés au moyen d'états cohérents de la lumière modulés continuement.</p> <p>D'autres aspects importants sont également traités dans cette thèse, tels que la mise en perspective de la distribution quantique de clés dans un contexte cryptographique, la spécification d'un protocole complet, la création de nouvelles techniques d'amplification de confidentialité plus rapides à mettre en œuvre ou l'étude théorique et pratique d'algorithmes alternatifs de réconciliation.</p> <p>Enfin, nous étudions la sécurité du protocole à états cohérents en établissant son équivalence à un protocole de purification d'intrication. Sans entrer dans les détails, cette équivalence, formelle, permet de valider la robustesse du protocole contre tout type d'espionnage, même le plus compliqué possible, permis par les lois de la mécanique quantique. En particulier, nous généralisons l'algorithme de réconciliation en tranches pour le transformer en un protocole de purification et nous établissons ainsi un protocole de distribution quantique sûr contre toute stratégie d'espionnage.</p> <p>Quantum key distribution is a cryptographic technique, which allows to exchange secret keys whose confidentiality is guaranteed by the laws of quantum mechanics. The strange behavior of elementary particles is exploited. In quantum mechnics, any measurement of the state of a particle irreversibly modifies this state. By taking advantage of this property, two parties, often called Alice and bob, can encode a secret key into quatum information carriers such as single photons. Any attempt at eavesdropping requires the spy, Eve, to measure the state of the photon and thus to perturb this state. Alice and Bob can then be aware of Eve's presence by a unusually high number of transmission errors.</p> <p>The information exchanged by quantum key distribution is not directly usable but must first be processed. Transmission errors, whether they are caused by an eavesdropper or simply by noise in the transmission channel, must be corrected with a technique called reconciliation. Then, the partial knowledge of an eavesdropper, who would perturb only a fraction of the carriers, must be wiped out from the final key thanks to a technique called privacy amplification.</p> <p>The context of this thesis is the quantum key distribution with continuous states of light as carriers. An important part of this work deals with the processing of continuous information exchanged by a particular protocol, where the carriers are coherent states of light. The continuous nature of information in this case implies peculiar changes to the reconciliation techniques, which have mostly been developed to process binary information. We propose a technique called sliced error correction, which allows to efficiently process continuous information. The set of the developed techniques was used in collaboration with the Institut d'Optique, Orsay, France, to set up the first experiment of quantum key distribution with continuously-modulated coherent states of light.</p> <p>Other important aspects are also treated in this thesis, such as placing quantum key distribution in the context of a cryptosystem, the specification of a complete protocol, the creation of new techniques for faster privacy amplification or the theoretical and practical study of alternate reconciliation algorithms.</p> <p>Finally, we study the security of the coherent state protocol by analyzing its equivalence with an entanglement purification protocol. Without going into the details, this formal equivalence allows to validate the robustness of the protocol against any kind of eavesdropping, even the most intricate one allowed by the laws of quantum mechanics. In particular, we generalize the sliced error correction algorithm so as to transform it into a purification protocol and we thus establish a quantum key distribution protocol secure against any eavesdropping strategy.</p>

Cette thèse aborde le problème de la reconnaissance d'activités. Elle est fortement motivée par la recherche dans le domaine de la reconnaissance des activités vidéo appliquée au domaine de la surveillance de personnes âgées. Dans ce travail, nous proposons deux contributions principales. La première contribution consiste en une approche pour la reconnaissance d'activité vidéo avec gestion de l'incertitude pour une détection précise d'événements. La deuxième contribution consiste à définir une ontologie et une base de connaissances pour la surveillance dans le domaine de la santé et en particulier la surveillance à l'hôpital de patients atteints de la maladie d'Alzheimer. L'approche de reconnaissance d'activité proposée combine une modélisation sémantique avec un raisonnement probabiliste pour faire face aux erreurs des détecteurs de bas niveau et pour gérer l'incertitude de la reconnaissance d'activité. La reconnaissance probabiliste des activités est basée sur la théorie des probabilités bayésienne qui fournit un cadre cohérent pour traiter les connaissances incertaines. L'approche proposée pour la vérification probabiliste des contraintes spatiale et temporelle des activités est basée sur le modèle de probabilité gaussienne. Nous avons travaillé en étroite collaboration avec les cliniciens pour définir une ontologie et une base de connaissances pour la surveillance à l'hôpital de patients atteints de la maladie d'Alzheimer. L'ontologie définie contient plusieurs concepts utiles dans le domaine de la santé. Nous avons également défini un certain nombre de critères qui peuvent être observés par les caméras pour permettre la détection des premiers symptômes de la maladie d'Alzheimer. Nous avons validé l'algorithme proposé sur des vidéos réelles. Les résultats expérimentaux montrent que l'algorithme de reconnaissance d'activité proposé a réussi à reconnaitre les activités avec un taux élevé de reconnaissance. Les résultats obtenus pour la surveillance de patients atteints de la maladie d'Alzheimer mettent en évidence les avantages de l'utilisation de l'approche proposée comme une plate-forme de soutien pour les cliniciens pour mesurer objectivement les performances des patients et obtenir une évaluation quantifiable des activités de la vie quotidienne.

Durant ces dernières années, un grand intérêt a été accordé aux systèmes de communication sans fil ayant plusieurs antennes en émission et en réception. Les codes espace-temps permettent d'exploiter tous les degrés de liberté de tels systèmes. Toutefois, le décodage de ces codes présente une grande complexité qui croit en fonction du nombre d'antennes déployées et de la taille de la constellation utilisée. Nous proposons un nouveau décodeur, appelé SB-Stack (Spherical Bound-Stack decoder) basé sur un algorithme de recherche dans l'arbre. Ce décodeur combine la stratégie de recherche du décodeur séquentiel Stack (dit également décodeur à pile) et la région de recherche du décodeur par sphères. Nous montrons que ce décodeur présente une complexité moindre par rapport à tous les décodeurs existants tout en offrant des performances optimales. Une version paramétrée de ce décodeur est aussi proposée, offrant une multitude de performances allant du ZF-DFE au ML avec des complexités croissantes, ainsi plusieurs compromis performances-complexités sont obtenus. Comme pour tous les systèmes de communication, les codes espace-temps pour les systèmes à antennes multiples peuvent être concaténés avec des codes correcteurs d'erreurs. Généralement, ces derniers sont décodés par des décodeurs à entrées et sorties souples. Ainsi, nous avons besoin de sorties souples fournies par le décodeur espace-temps qui seront utilisées comme entrées par les premiers décodeurs. Nous proposons alors une version modifiée du décodeur SB-Stack délivrant des sorties souples sous forme de taux de vraisemblance logarithmiques (Log-Likelihood Ratio - LLR). Pour la mise en oeuvre pratique des décodeurs, il est important d'avoir une complexité faible mais avoir également une complexité constante est indispensable dans certaines applications. Nous proposons alors un décodeur adaptatif qui permet de sélectionner, parmi plusieurs algorithmes de décodage, celui qui est le plus adéquat selon la qualité du canal de transmission et la qualité de service souhaitée. Nous présentons une implémentation pratique du décodage adaptatif utilisant le décodeur SB-Stack paramétré. Le décodage des codes espace-temps peut être amélioré en le précédant par une phase de pré-traitement. En sortie de cette phase, la matrice du canal équivalente est mieux conditionnée ce qui permet de réduire la complexité d'un décodeur optimal et d'améliorer les performances d'un décodeur sous-optimal. Nous présentons et nous étudions alors les performances d'une chaine complète de décodage utilisant diverses techniques de pré-traitement combinées avec les décodeurs espace-temps étudiés précédemment.

Most of the modern wireless communication systems as WiMAX, DVB-NGH, WiFi, HSPA+ and 4G have adopted the use of multiple antennas at the transmitter and the receiver, called multiple-input multiple-output (MIMO). Space time coding for MIMO systems is a promising technology to increase the data rate and enhance the reliability of wireless communications. Space-time block codes (STBCs) are commonly designed according to the rank-determinant criteria suitable at high signal to noise ratios (SNRs). In contrast, wireless communication standards employ MIMO technology with capacity-approaching forward-error correcting (FEC) codes like turbo codes and low-density parity-check (LDPC) codes, ensuring low error rates even at low SNRs. In this thesis, we investigate the design of STBCs for MIMO systems with capacity-approaching FEC codes. We start by proposing a non-asymptotic STBC design criterion based on the bitwise mutual information (BMI) maximization between transmitted and soft estimated bits at a specific target SNR. According to the BMI criterion, we optimize several conventional STBCs. Their design parameters are shown to be SNR-dependent leading to the proposal of adaptive STBCs. Proposed adaptive STBCs offer identical or better performance than standard WiMAX profiles for all coding rates, without increasing the detection complexity. Among them, the proposed adaptive trace-orthonormal STBC can pass continuously from spatial multiplexing, suitable at low SNRs and therefore at low coding rates, to the Golden code, optimal at high SNRs. Uncorrelated, correlated channels and transmit antenna selection are considered. We design adaptive STBCs for these cases offering identical or better performance than conventional non-adaptive STBCs. In addition, conventional STBCs are designed in a way achieving the asymptotic DMT frontier. Recently, the finite-SNR DMT has been proposed to characterize the DMT at finite SNRs. Our last contribution consists of the derivation of the exact finite-SNR DMT for MIMO channels with dual antennas at the transmitter and/or the receiver. Both uncorrelated and correlated Rayleigh fading channels are considered. It is shown that at realistic SNRs, achievable diversity gains are significantly lower than asymptotic values. This finite-SNR could provide new insights on the design of STBCs at operational SNRs.

Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed-Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. This algorithm directly outputs the linearized evaluation polynomial of the estimated codeword by means of the (fast) linearized Euclidean algorithm. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. This algorithm decodes most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed-Solomon codes and block codes in Hamming metric, respectively. The bounds imply, amongst others, that there exists no polynomial upper bound on the list size in rank metric as the Johnson bound in Hamming metric, which depends only on the length and the minimum rank distance of the code. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes. This structure is crucial in the decoding process since we exploit the efficient decoders of the underlying block codes in order to decode the convolutional code.

Le codage de canal est une opération mathématique qui améliore la qualité des transmissions numériques en corrigeant les bits erronés en réception. Les contraintes des usages comme la qualité de réception, les débits d'utilisation, la latence de calcul, la surface ou encore la consommation électrique favorisent l'usage de différents codes dans la standardisation des protocoles de communication. La tendance industrielle est à la convergence des réseaux de communication pour des usages variés. Ce large choix de codage devient un handicap pour la conception de transmetteurs à bas coûts. Les réseaux médias favorisent des codes correcteurs d'erreurs avancés comme les turbocodes et les codes LDPC pour répondre aux contraintes de qualité de réception. Or ces procédés ont un coût de décodage important sur les récepteurs finaux. Une architecture adaptée à plusieurs types de codes capable d'évoluer en fonction d'une modification du protocole d'accès devient inévitable pour élaborer de nouveaux scénarios d'usages. Ce mémoire présente le principe du codage de canal et la plupart des codes correcteurs d'erreurs avancés sélectionnés dans les standards de communication courants. Les caractéristiques communes des codes QC-LDPC et des turbocodes sont soulignées. Les principaux algorithmes ainsi que certaines architectures de décodage sont présentés. La complexité matérielle des principaux algorithmes de décodage est évaluée. Ils sont comparés pour un même code et à un niveau de correction équivalent pour les codes QC-LDPC. Une étude similaire est réalisée sur les turbocodes. Les algorithmes de décodage sont appliqués sur des codes de tailles et de rendements proches et dimensionnés pour atteindre une correction similaire afin de sélectionner un algorithme de décodage conjoint aux deux familles de code. Les codes QC-LDPC et les turbocodes se structurent à l'aide d'une représentation en treillis commune. La technique de fenêtrage couramment appliquée au décodage des turbocodes est étudiée pour le décodage d'un code QC-LDPC. Enfin, l'entrelacement des codes QC-LDPC est mis en évidence et reconsidéré en fonction des contraintes matérielles. Un coeur de décodage de treillis compatible avec les standards 3GPP LTE et IEEE 802.11n est proposé. Plusieurs structures de décodage sont ensuite introduites incorporant un ou plusieurs de ces coeurs. L'intégration sur cible FPGA est détaillée. Un scénario d'utilisation avec un contexte de décodage évoluant à chaque message reçu est proposé ce qui souligne l'impact de la reconfiguration sur les débits de décodage. La structure multistandard nécessite 4,2 % (respectivement 5,3 %) de ressources matérielles supplémentaires à une structure compatible avec le standard 3GPP LTE (resp. IEEE 802.11n) seul. La dégradation du débit maximal due à la reconfiguration entre le décodage des mots de code est d'au plus 1 %. Une architecture à plusieurs coeurs est également portée sur une cible ASIC de 65 nm. Cette architecture fonctionne à une fréquence de 500 Mhz sur une surface de 2,1 mm2 décodant les mots de code 3GPP LTE et IEEE 802.11n, et acceptant une reconfiguration dynamique entre deux mots de code consécutifs.

Cette thèse porte sur la distribution quantique de clés, qui est une primitive cryptographique permettant à deux correspondants éloignés, Alice et Bob, d'établir une clé secrète commune malgré la présence potentielle d'un espion. On s'intéresse notamment aux protocoles " à variables continues " où Alice et Bob encodent l'information dans l'espace des phases. L'intérêt majeur de ces protocoles est qu'ils sont faciles à mettre en œuvre car ils ne requièrent que des composants télécom standards. La sécurité de ces protocoles repose sur les lois de la physique quantique : acquérir de l'information sur les données échangées par Alice et Bob induit nécessairement un bruit qui révèle la présence de l'espion. Une étape particulièrement délicate pour les protocoles à variables continues est la " réconciliation " durant laquelle Alice et Bob utilisent leurs résultats de mesure classiques pour se mettre d'accord sur une chaîne de bits identiques. Nous proposons d'abord un algorithme de réconciliation optimal pour le protocole initial, puis introduisons un nouveau protocole qui résout automatiquement le problème de la réconciliation grâce à l'emploi d'une modulation discrète. Parce que les protocoles à variables continues sont formellement décrits dans un espace de Hilbert de dimension infinie, prouver leur sécurité pose des problèmes mathématiques originaux. Nous nous intéressons d'abord à des symétries spécifiques de ces protocoles dans l'espace des phases. Ces symétries permettent de simplifier considérablement l'analyse de sécurité. Enfin, nous étudions l'influence des effets de tailles finies, tels que l'estimation du canal quantique, sur les performances des protocoles.

Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.<p><p>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.<p><p>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 est possible d'avoir une sécurité lorsque les deux parties sont soumises à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opérations 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.<p><p>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.<p><p>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 qu'en effectuant des requêtes sur chacune des variables 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.<p><p>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.<p><p>Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessitent 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.<p><p>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 Isomorphisme-de-Graphes. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished