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.
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 textFault 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
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 textRecent 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
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 textproblèmes symétriques, dans les cadres du calcul probabiliste classique
et du calcul quantique.
Il est montré, dans le cas quantique, une application de la méthode de
bornes inférieures dite "polynomiale" au calcul de la complexité en
requêtes des problèmes de sous-groupes cachés abéliens, via la technique de "symétrisation".
Dans le cas du calcul probabiliste, sous une hypothèse de "symétrie
transitive" des problèmes, il est donné une formule combinatoire
permettant de calculer la complexité en requêtes exacte du meilleur
algorithme non-adaptatif. De plus, il est mis en évidence que sous
certaines hypothèses de symétrie, ce meilleur algorithme non-adaptatif
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.
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 textIn 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
Grunspan, Cyril. "Théorie de Toda discrète et espaces homogènes quantiques." Palaiseau, École polytechnique, 2000. http://www.theses.fr/2000EPXX0042.
Full textCattaneo, David. "Modélisation graphique et simulation en traitement d'information quantique." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM076/document.
Full textGraph 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
Douce, Tom. "Realistic quantum information processing : from devices to computational models." Thesis, Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCC201/document.
Full textThe 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
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 textBredariol, Grilo Alex. "Quantum proofs, the local Hamiltonian problem and applications." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC051/document.
Full textIn 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
Javelle, Jérôme. "Cryptographie Quantique : Protocoles et Graphes." Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENM093/document.
Full textI 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
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 textMagnin, Loïck. "Two-player interaction in quantum computing : cryptographic primitives & query complexity." Thesis, Paris 11, 2011. http://www.theses.fr/2011PA112275/document.
Full textThis 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
Mhalla, Mehdi. "Informatique quantique, algorithmes et complexité." Grenoble INPG, 2004. http://www.theses.fr/2004INPG0113.
Full textThis 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
Jeandel, Emmanuel. "Techniques algébriques en calcul quantique." Lyon, École normale supérieure (sciences), 2005. http://www.theses.fr/2005ENSL0307.
Full textThe 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
Madet, Antoine. "Complexité implicite dans des Lambda -calculs concurrents." Paris 7, 2012. http://www.theses.fr/2012PA077222.
Full textControlling 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
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 textDü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 textBaboin, 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 textBlais, 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 textApplencourt, Thomas. "Calcul haute performance & chimie quantique." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30162/document.
Full textThis 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
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 textPomeransky, Andrei. "Intrication et Imperfections dans le Calcul Quantique." Phd thesis, Université Paul Sabatier - Toulouse III, 2004. http://tel.archives-ouvertes.fr/tel-00007256.
Full textPomeransky, Andrei A. "Intrication et imperfections dans le calcul quantique." Toulouse 3, 2004. http://www.theses.fr/2004TOU30132.
Full textQuantum 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
Duclos-Cianci, Guillaume. "Outils de calcul quantique tolérant aux fautes." Thèse, Université de Sherbrooke, 2015. http://hdl.handle.net/11143/6770.
Full textSenot, 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 textLafitte, Grégory. "Calculs et infinis." Lyon, École normale supérieure (sciences), 2002. http://www.theses.fr/2002ENSL0239.
Full textWe 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.
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 textKempe, Julia. "Calcul quantique : marches aléatoires et enchevêtrement, applications cryptographiques." Paris, ENST, 2001. http://www.theses.fr/2001ENST0015.
Full textLalire, Marie. "Développement d'une notation algorithmique pour le calcul quantique." Grenoble INPG, 2006. http://www.theses.fr/2006INPG0113.
Full textNo 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
Darrigan, Clovis. "Calcul quantique de susceptibilités électriques dans les solides cristallins." Pau, 2001. http://www.theses.fr/2001PAUU3029.
Full textDe, Visme Marc. "Sémantique des Jeux Quantique." Thesis, Lyon, 2020. http://www.theses.fr/2020LYSEN056.
Full textIn 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
Henrio, Ludovic. "Asynchronous object calculus : confluence and determinacy." Nice, 2003. http://www.theses.fr/2003NICE4047.
Full textThe 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
Trystram, Denis. "Quelques résultats de complexité en algorithmique parallèle et systolique." Grenoble INPG, 1988. http://tel.archives-ouvertes.fr/tel-00009202.
Full textSpaenlehauer, 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 textMultivariate 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)
Markey, Nicolas. "Logiques temporelles pour la vérification : expressivité, complexité, algorithmes." Orléans, 2003. http://www.theses.fr/2003ORLE2004.
Full textIyer, Sridharan Pavithran. "Complexité du décodage des codes stabilisateurs quantiques." Mémoire, Université de Sherbrooke, 2014. http://hdl.handle.net/11143/5388.
Full textMadet, Antoine. "Complexité Implicite de Lambda-Calculs Concurrents." Phd thesis, Université Paris-Diderot - Paris VII, 2012. http://tel.archives-ouvertes.fr/tel-00794977.
Full textBonfante, 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 textOur 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
Duchemin, Ivan. "Calcul quantique Hamiltonien : théorie et application aux portes logiques mono-moléculaires." Toulouse 3, 2006. http://www.theses.fr/2006TOU30243.
Full textBrault-Baron, Johann. "De la pertinence de l’énumération : complexité en logiques." Caen, 2013. http://www.theses.fr/2013CAEN2056.
Full textBeyond 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
Kachigar, Ghazal. "Questions de localisabilité pour le calcul distribué." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0339/document.
Full textThis 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
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 textRevol, Nathalie. "Complexité de l'évaluation parallèle de circuits arithmétiques." Grenoble INPG, 1994. http://tel.archives-ouvertes.fr/tel-00005109.
Full textTaveneaux, Antoine. "Puissance logique et calculatoire de l'aléa algorithmique." Paris 7, 2013. http://www.theses.fr/2013PA077217.
Full textTheory 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
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 textThis 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
Turuani, Mathieu. "Sécurité des protocoles cryptographiques : décidabilité et complexité." Nancy 1, 2003. http://www.theses.fr/2003NAN10223.
Full textCeroi, Stéphan. "Ordres et géométrie plane : application au nombre de sauts." Montpellier 2, 2000. http://www.theses.fr/2000MON20114.
Full textLeroy, Julien. "Contribution à la résolution de la conjecture S-adique." Amiens, 2012. http://www.theses.fr/2012AMIE0101.
Full textThis 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
Simoncini, David. "Sélection topologique dans les algorithmes évolutionnaires cellulaires : étude du compromis exploration exploitation." Nice, 2009. http://www.theses.fr/2009NICE4079.
Full textEvolutionary 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
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 text