Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-22T13:41:27Z No. of bitstreams: 1 SUENE FERREIRA CAMPOS - DISSERTAÇÃO PPGMAT 2008..pdf: 741113 bytes, checksum: 7fc13ffd22412553f540977137401f24 (MD5) / Made available in DSpace on 2018-07-22T13:41:27Z (GMT). No. of bitstreams: 1 SUENE FERREIRA CAMPOS - DISSERTAÇÃO PPGMAT 2008..pdf: 741113 bytes, checksum: 7fc13ffd22412553f540977137401f24 (MD5) Previous issue date: 2008-12 / Neste trabalho apresentamos um estudo sobre o comportamento das identidades polinomiais dos produtos tensoriais de álgebras T-primas sobre corpos infinitos com diferentes características. Mais precisamente, apresentamos o Teorema sobre Produto Tensorial (TPT), descrito por Kemer para corpos de característica zero, e verificamos a sua validade sobre corpos infinitos com característica positiva. Incialmente, a partir de resultados apresentados por Azevedo e Koshlukov, estudamos os T-ideais das álgebras M1,1(G) eG⊗G, para corpos infinitos com característica zero e característicap > 2. Aqui, G = G0⊕G1 é a álgebra de Grassmann de dimensão infinita eM1,1(G) é a subálgebra de M2(G) que consiste das matrizes de ordem 2 que têm na diagonal principal entradas emG0 e na diagonal secundária entradas emG1. Em seguida, utilizando métodos introduzidos por Regev e desenvolvidos por Azevedo, Fidélis e Koshlukov, verificamos a validade do TPT para corpos de característica positiva, quando o mesmo é restrito a polinômios multilineares. Finalmente, apresentamos alguns resultados obtidos por Alves, Azevedo, Fidélis e Koshlukov, que comprovam que o TPT é falso quando o corpo base é infinito e tem característicap>2. / In this work we present a study about the behavior of polynomial identities of tensor products of T-prime T-ideals over infinite fields of different characteristics. More precisely, we present the Tensor Product Theorem (TPT), described by Kemer for fields of characteristic zero, and verify its validity over infinite fields with positive characteristic. First, based on results of Azevedo and Koshlukov, we study the Tideals of the algebrasM1,1(G) eG⊗G, for infinite fields of characteristic zero and characteristicp>2. Here,G=G0 ⊕G1 is the Grassmann algebra of infinite dimension andM1,1(G) is the subalgebras ofM2(G) consisting of matrices of order2 which main diagonal entries are inG0 and the secondary diagonal entries are inG1. Second, using methods introduced by Regev and developed by Azevedo, Fidélis and Koshlukov, we verify the validity of the TPT for fields of positive characteristic, when it is restricted to multilinear polynomials. Finally, we present some results of Alves, Azevedo, Fidelis and Koshlukov, which show that the TPT is false when the basis field is infinite and has characteristicp>2.

Dans le cadre discrétisé, la taille d'un ensemble à l'échelle δ est évaluée par son nombre de recouvrement par δ-boules (également connu sous le nom de l'entropie métrique). Dans cette thèse, nous étudions les propriétés combinatoires des ensembles discrétisés sous l'addition, la multiplication et les projections orthogonales. Il y a trois parties principales. Premièrement, nous démontrons un théorème somme-produit dans les algèbres de matrices, qui généralise un théorème somme-produit de Bourgain concernant l'anneau des réels. On améliore aussi des estimées somme-produit en dimension supérieure obtenues précédemment par Bougain et Gamburd. Deuxièmement, on étudie les projections orthogonales des sous-ensembles de l'espace euclidien et étend ainsi le théorème de projection discrétisé de Bourgain aux projections de rang supérieur. Enfin, dans un travail en commun avec Nicolas de Saxcé, nous démontrons un théorème produit dans les groupes de Lie parfaits. Ce dernier résultat généralise les travaux antérieurs de Bourgain-Gamburd et de Saxcé. / In the discretized setting, the size of a set is measured by its covering number by δ-balls (a.k.a. metric entropy), where δ is the scale. In this document, we investigate combinatorial properties of discretized sets under addition, multiplication and orthogonal projection. There are three parts. First, we prove sum-product estimates in matrix algebras, generalizing Bourgain's sum-product theorem in the ring of real numbers and improving higher dimensional sum-product estimates previously obtained by Bourgain-Gamburd. Then, we study orthogonal projections of subsets in the Euclidean space, generalizing Bourgain's discretized projection theorem to higher rank situations. Finally, in a joint work with Nicolas de Saxcé, we prove a product theorem for perfect Lie groups, generalizing previous results of Bourgain-Gamburd and Saxcé.

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.

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