Academic literature on the topic 'Complexité du calcul quantique'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.
Journal articles on the topic "Complexité du calcul quantique"
1
Amanti, Maria, Florent Baboux, and Sara Ducci. "Les sources intégrées de photons intriqués au coeur des technologies quantiques." Photoniques, no. 91 (May 2018): 25–28. http://dx.doi.org/10.1051/photon/20189125.
Full textAbstract:
L’intrication est un des aspects les plus fascinants et contre-intuitifs des systèmes quantiques, devenue une ressource clé dans tous les domaines de l’information quantique, des communications à la métrologie, des simulations au calcul. La photonique quantique intégrée est en train de jouer un rôle moteur pour le développement de sources de photons intriqués de plus en plus performantes et leur insertion dans des circuits quantiques complexes.
2
Romero, Clara. "Comment le sens peut-il être complexe ? L’exemple des comparaisons d’intensité." Nouvelles perspectives en sciences sociales 9, no. 1 (March 27, 2014): 171–98. http://dx.doi.org/10.7202/1024041ar.
Full textAbstract:
À partir de phénomènes sémantiques qui semblent complexes (au sens courant), et de ce que l’on appelle complexité là où, en linguistique, cette notion est mieux établie, une définition générale de la complexité sémantique est proposée. La complexité de certains faits est susceptible d’expliquer les différences entre les idiolectes, laissant prévoir un rapport avec la notion de difficulté. Un phénomène correspondant à un certain type de complexité sémantique – les comparaisons d’intensité – est ensuite analysé. Les paramètres qui allongent le calcul du sens de ces comparaisons et qui permettent de les hiérarchiser en fonction de leur complexité sont mis au jour.
3
Alibart, Olivier, Virginia D’Auria, Grégory Sauder, Laurent Labonte, and Sébastien Tanzilli. "Comprendre. Le comptage de photons corrélés en temps." Photoniques, no. 91 (May 2018): 38–42. http://dx.doi.org/10.1051/photon/20189138.
Full textAbstract:
L’analyse des corrélations temporelles entre des photons se trouve au cœur des protocoles de traitement de l’information quantique (communication, métrologie et calcul) présentés dans ce dossier. Ces mesures de corrélation sont issues de techniques d’optique quantique fondamentale formalisées par R. Glauber en 1963 [Phys. Rev. 130, 2529] qui permettent de mesurer les propriétés des champs électromagnétiques et d’en détecter des régularités, des signatures dans un signal bruité. D’une façon plus générale, elles sont le résultat d’interférences d’ordre supérieur et sont, dans certains cas, directement reliées à la cohérence « classique » des champs optiques.
4
-MUKHARSKY, Dr Yury. "Les Qubits et le calcul quantique : le silicium d'après demain ?" Revue de l'Electricité et de l'Electronique -, no. 09 (2004): 99. http://dx.doi.org/10.3845/ree.2004.098.
Full text
5
Bermejo, Isabel, and Monique Lejeune-Jalabert. "Sur la complexité du calcul des projections d'une courbe projective." Communications in Algebra 27, no. 7 (January 1999): 3211–20. http://dx.doi.org/10.1080/00927879908826623.
Full text
6
Labhalla, S. "Complexité du calcul du développement d'un nombre réel en fractions continues." Theoretical Computer Science 83, no. 2 (June 1991): 219–35. http://dx.doi.org/10.1016/0304-3975(91)90275-7.
Full text
7
Rérat, M., M. Mérawa, and C. Pouchan. "Choix de la jauge dans le calcul quantique de propriétés électromagnétiques des molécules." Journal de Chimie Physique 90 (1993): 477–89. http://dx.doi.org/10.1051/jcp/1993900477.
Full text
8
Lestienne, Rémy. "Whitehead, la Mécanique Quantique et les relations esprit-matière." Lato Sensu: Revue de la Société de philosophie des sciences 8, no. 1 (March 9, 2021): 1–11. http://dx.doi.org/10.20416/lsrsps.v8i1.1.
Full textAbstract:
La philosophie de la Nature et du Temps chez Alfred North Whitehead (1861-1947) n’a peut-être pas assez retenu l’attention des scientifiques, en particulier en France. On sait que ce mathématicien-philosophe collaborant avec Bertrand Russell pour l’écriture des Principia Mathematica (1910-1913) a insisté sur le caractère abstrait des points d’espace dans la fondation de la géométrie. A partir de 1911, il étend cette observation aux instants de temps, et développe progressivement, à partir de là, une vision de l’ontologie du monde comme une succession de « concrescences d’entités actuelles » dont chacune apporte avec elle une brique de temps finie. Ces concrescences ne sont pas sans rappeler les réductions du paquet d’ondes dans les opérations de mesure en mécanique quantique ; en fait, Whitehead a suivi de près le développement de cette théorie, comme il a suivi de près le développement de la relativité. Par ailleurs, sa philosophie de la Nature, ou comme il le dit sa philosophie de l’organisme, prévoit une solidarité globale des entités actuelles qui par certains côtés rappelle l’intrication quantique. On examine plus en profondeur cette similarité et ses limites, et aborde les relations esprit-matière chez cet auteur. Malgré ses défauts, la métaphysique de Whitehead, en en particulier la négation de l’instant a mis en lumière, à mon sens, la complexité du temps de la nature (chez Whitehead le process), bien au-delà de la variable continue t des physiciens. Une large part de cet article est basée sur mon livre Whitehead, Philosophe du Temps (auteur, 2020, à paraître).
9
Poizat, Bruno. "A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant." Journal of Symbolic Logic 73, no. 4 (December 2008): 1179–201. http://dx.doi.org/10.2178/jsl/1230396913.
Full textAbstract:
RésuméNous définissons une classe de suites de polynômes, calculés par des circuits de complexité polynomiale comprenant des additions, des soustractions. des multiplications et des sommations de Valiant. Nous montrons que cette classe est close pour la prise de la fonction-coefficient. définie au paragraphe 3 de cet article; nous en déduisons l'existence d'un circuit de complexité 72.n2, calculant le coefficient binomial de deux nombres de n chiffres, donnés en base 2. Il est par ailleurs facile de construire un circuit de complexité 17.n + 2 calculant la factorielle d'un nombre de n chiffres. La présence de 2.n sommations d'effet exponentiel dans chacun de ces circuits en affecte gravement l'intérêt pratique. II est peu probable, ou du moins peu souhaitable. qu'on puisse éliminer ces sommations sans explosion, car cela provoquerait la catastrophe cryptographique que redoutent tous les banquiers; néanmoins, nous ne savons pas séparer la classe définie ici de celle des suites de polynômes calculables en un nombre polynomial d'opérations arithmétiques. Cela n'a rien de surprenant, vu la très grande affinité qu'elle a avec la classe PSPACE: nous montrons en effet que cette classe est identique à la classe VPSPACE, définie antérieurement par Koiran et Perifel, qui apparaît ici sous une forme bien plus maniable que l'originale.
10
Devictor, Vincent. "Dossier : La fabrique de la compensation écologique : controverses et pratiques – La compensation écologique : fondements épistémiques et reconfigurations technoscientifiques." Natures Sciences Sociétés 26, no. 2 (April 2018): 136–49. http://dx.doi.org/10.1051/nss/2018032.
Full textAbstract:
La compensation écologique s’appuie sur des hypothèses scientifiques dont les fondements épistémologiques demeurent souvent implicites. Le but de cet article est d’expliciter la manière dont l’écologie scientifique et les politiques d’aménagement posent le problème de la compensation des entités écologiques. Le bien-fondé de deux enjeux fondamentaux est analysé : la question de l’équivalence entre deux entités écologiques et celle du référentiel spatio-temporel pour mesurer la dynamique de ces entités. L’analyse d’un cas d’étude mobilisant le calcul d’une équivalence entre des pertes et des gains de biodiversité est proposée. Nous montrons comment le calcul des équivalences impose un espace-temps étranger aux dynamiques écologiques. Cet article propose de comprendre la compensation comme une prise en charge technoscientifique des problèmes écologiques. Cette approche facilite l’intégration des enjeux de biodiversité dans une politique d’aménagement en contournant la spécificité et la complexité des dynamiques écologiques.
Dissertations / Theses on the topic "Complexité du calcul quantique"
1
Grospellier, Antoine. "Décodage des codes expanseurs quantiques et application au calcul quantique tolérant aux fautes." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS575.
Full textAbstract:
Le calcul quantique tolérant aux fautes est un ensemble de techniques dont le but est d'effectuer des calculs quantiques de manière fiable en utilisant des composants bruités. Dans ce contexte, l'utilisation de codes correcteurs quantiques maintient le nombre d'erreurs présentes dans le système en dessous d'un seuil tolérable. L'un des principaux problèmes de ce domaine est d'évaluer le coût minimum (en mémoire et en temps) nécessaire pour transformer un calcul quantique idéal en un calcul tolérant aux fautes. Dans cette thèse, nous montrons que la famille des codes expanseurs quantiques associée à l'algorithme de décodage small-set-flip peut être utilisée dans la construction de ref. [arXiv:1310.2984] pour réaliser du calcul quantique tolérant aux fautes avec coût constant en mémoire. La famille de codes correcteurs ainsi que le décodeur que nous étudions ont été introduits dans ref. [arXiv:1504.00822] où un modèle de bruit adverse est considéré. En nous appuyant sur les résultats de cet article, nous analysons le comportement des codes expanseurs quantiques face à un modèle de bruit stochastique qui est pertinent dans le cadre du calcul tolérant aux fautes [arXiv:1711.08351], [arXiv:1808.03821]. De plus, nous montrons que l'algorithme de décodage peut être parallélisé pour fonctionner en temps constant. Cette propriété est essentielle pour éviter que les erreurs ne s'accumulent pendant que l'algorithme est exécuté. Au-delà des résultats théoriques décrits ci-dessus, nous avons effectué une analyse numérique des codes expanseurs quantiques dans le but d'évaluer leurs performances en pratique [arXiv:1810.03681]. Le modèle de bruit choisi pour ces simulations consiste à générer des erreurs de types X et Z de manière indépendante et identiquement distribuée sur les qubits. Les résultats obtenus pour ces codes de rendement constant sont prometteurs puisque nos simulations montrent que leur seuil est décent et que leurs performances à taille finie sont bonnesFault tolerant quantum computation is a technique to perform reliable quantum computation using noisy components. In this context, quantum error correcting codes are used to keep the amount of errors under a sustainable threshold. One of the main problems of this field is to determine the minimum cost, in terms of memory and time, which is needed in order to transform an ideal quantum computation into a fault-tolerant one. In this PhD thesis, we show that the family of quantum expander codes and the small-set-flip decoder can be used in the construction of ref. [arXiv:1310.2984] to produce a fault-tolerant quantum circuit with constant space overhead. The error correcting code family and the decoder that we study has been introduced in ref. [arXiv:1504.00822] where an adversarial error model was examined. Based on the results of this article, we analyze quantum expander codes subjected to a stochastic error model which is relevant for fault-tolerant quantum computation [arXiv:1711.08351], [arXiv:1808.03821]. In addition, we show that the decoding algorithm can be parallelized to run in constant time. This is very relevant to prevent errors from accumulating while the decoding algorithm is running. Beyond the theoretical results described above, we perform a numerical analysis of quantum expander codes to measure their performance in practice [arXiv:1810.03681]. The error model used during these simulations generates X and Z type errors on the qubits with an independent and identically distributed probability distribution. Our results are promising because they reveal that these constant rate codes have a decent threshold and good finite length performance
2
Pégny, Maël. "Sur les limites empiriques du calcul : calculabilité, complexité et physique." Thesis, Paris 1, 2013. http://www.theses.fr/2013PA010673/document.
Full textAbstract:
Durant ces dernières décennies, la communauté informatique a montré un intérêt grandissant pour les modèles de calcul non-standard, inspirés par des phénomènes physiques, biologiques ou chimiques. Les propriétés exactes de ces modèles ont parfois été l'objet de controverses: que calculent-ils? Et à quelle vitesse? Les enjeux de ces questions sont renforcés par la possibilité que certains de ces modèles pourraient transgresser les limites acceptées du calcul, en violant soit la thèse de Church-Turing soit la thèse de Church-Turing étendue. La possibilité de réaliser physiquement ces modèles a notamment été au coeur des débats. Ainsi, des considérations empiriques semblent introduites dans les fondements même de la calculabilité et de la complexité computationnelle, deux théories qui auraient été précédemment considérées comme des parties purement a priori de la logique et de l'informatique. Par conséquent, ce travail est consacré à la question suivante : les limites du calcul reposent-elles sur des fondements empiriques? Et si oui, quels sont-ils? Pour ce faire, nous examinons tout d'abord la signification précise des limites du calcul, et articulons une conception épistémique du calcul, permettant la comparaison des modèles les plus variés. Nous répondrons à la première question par l'affirmative, grâce à un examen détaillé des débats entourant la faisabilité des modèles non-standard. Enfin, nous montrerons les incertitudes entourant la deuxième question dans l'état actuel de la recherche, en montrant les difficultés de la traduction des concepts computationnels en limites physiquesRecent years have seen a surge in the interest for non-standard computational models, inspired by physical, biological or chemical phenomena. The exact properties of some of these models have been a topic of somewhat heated discussion: what do they compute? And how fast do they compute? The stakes of these questions were heightened by the claim that these models would violate the accepted limits of computation, by violating the Church-Turing Thesis or the Extended Church-Turing Thesis. To answer these questions, the physical realizability of some of those models - or lack thereof - has often been put at the center of the argument. It thus seems that empirical considerations have been introduced into the very foundations of computability and computational complexity theory, both subjects that would have been previously considered purely a priori parts of logic and computer science. Consequently, this dissertation is dedicated to the following question: do computability and computational complexity theory rest on empirical foundations? If yes, what are these foundations? We will first examine the precise meaning of those limits of computation, and articulate a philosophical conception of computation able to make sense of this variety of models. We then answer the first question by the affirmative, through a careful examination of current debates around non-standard models. We show the various difficulties surrounding the second question, and study how they stem from the complex translation of computational concepts into physical limitations
3
Nesme, Vincent. "Complexité en requêtes et symétries." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2007. http://tel.archives-ouvertes.fr/tel-00156762.
Full textAbstract:
Ces travaux portent sur l'étude de la complexité en requêtes de problè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.
4
Dang, Minh Dung. "Autour des primitifs quantiques pour le calcul sécurisé à deux parties." Paris, ENST, 2008. http://pastel.archives-ouvertes.fr/pastel-00005098.
Full textAbstract:
Dans cette thèse, nous sommes intéressés à la construction inconditionnelle du calcul sécurisé à deux parties dont Oblivious Transfer (OT) et Bit Commitment (BC) sont les primitifs fondamentaux. D'une part, mes oeuvres sont inspirées du framework de Crépeau et al. Pour la construction de OT à partir des canaux bruités. Le principe est de concevoir, à partir des canaux bruités, un modèle d'effacement intermédiaire qui est un variant de OT. Nous avons contribué à ce framework en proposant un modèle intermédiaire plus générique, le Binary Symmetric Multi-Error-Rate Channel, qui peut également être construit à partir des canaux bruités. Avec ce modèle intermédiaire, nous pouvons construire le protocole de OT de manière plus efficace. En outre, nous exposons quelques études de cas sur l'émulation des modèles bruités par un codage quantique nonorthogonal qui utilise deux états non-orthogonaux pour coder deux valeurs du bit classique. D'autre part, nous révisons le modèle quantique des protocoles quantiques à deux parties, couvrant les calculs et les communications classiques. Nous constatons que, dans le modèle général, un canal classique est inévitablement macroscopique et la decoherence est si forte que l'information quantique n'est pas acceptée d'être transférée sur ce canal. Ainsi, le modèle quantique des protocoles à deux parties consiste en trois parties, y compris l'environnement du canal. Avec cette fidèle interprétation, nous réaffirmons les théorèmes No-go de Mayers et Lo & Chau sur l'impossibilité de OT, BC quantiques. En addion, nous pouvons étendre ces résultats négatifs aux protocoles utilisant certains oracles quantiques, comme Coin-FlippingIn this thesis, we are interested in the theory of unconditional secure two-party computations of which Oblivious Transfer (OT) and Bit Commitment (BC) are the central primitives. On one hand, my works are inspired from Crépeau's et al. 's framework of building of OT protocol from noisy communication channels. The principle of this framework is to conceive, from noisy channels, an intermediate erasure model which is a variant of OT. We contributed to this framework by proposing a more general intermediate model, the Binary Symmetric Multi-Error-Rate Channel, which also can be built from noisy channels. With this intermediate model, we can build OT protocol from the noisy channels more effectively. In addition, we expose some case studies on emulating noisy models by a quantum nonorthogonal coding (QNOC) scheme which uses two non-orthogonal pure states for encoding two values of the classical bit. On the other hand, we revise the quantum model for general two-party protocols concerning classical and quantum computations and communications. We state that in the general model, a classical channel is inevitably macroscopic and its decoherence is so strong that quantum information is not accepted to be transfered on it. Thus, the quantum model for two-party protocols becomes three-party, including an environment of the channel. Indeed, with the faithful interpretation of general quantum two-party protocols in this three-party model, we reaffirm the no-go theorems of Mayers and Lo & Chau on the impossibilities of quantum OT, BC. In addion, we can go further to apply these negative results to protocols using some quantum trusted oracles, such as Coin-Flipping
5
Grunspan, Cyril. "Théorie de Toda discrète et espaces homogènes quantiques." Palaiseau, École polytechnique, 2000. http://www.theses.fr/2000EPXX0042.
Full text
6
Cattaneo, David. "Modélisation graphique et simulation en traitement d'information quantique." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM076/document.
Full textAbstract:
Le formalisme des états graphes consiste à modéliser des états quantiques par des graphes. Ce formalisme permet l'utilisation des notions et des outils de théorie des graphes (e.g. flot, domination, méthodes probabilistes) dans le domaine du traitement de l'information quantique. Ces dernières années, cette modélisation combinatoire a permis plusieurs avancées décisives, notamment (i) dans la compréhension des propriétés de l'intrication quantique (ii) dans l'étude des modèles de calcul particulièrement prometteurs en terme d'implémentation physique, et (iii) dans l'analyse et la construction de protocoles de cryptographie quantique. L'objectif de cette thèse est d'étudier les propriétés graphiques émergeant des problématiques d'informatique quantique, notamment pour la simulation quantique. En particulier, l'étude des propriétés de causalité et de localité des états graphes, en étendant par exemple la notion existante de flot de causalité à une notion intégrant des contraintes de localité, permettrait d'ouvrir de nouvelles perspectives pour la simulation de systèmes quantiques à l'aide d'états graphes. Des connections formelles avec les automates cellulaires quantiques bruités pourront également émerger de cette étudeGraph States formalism consist in using graphs to model quantum states. This formalism allows us to use notion and tools of graph theory (e.g. flow, domination, probabilistic methods) in quantum information processing. Last years, this combinatorial modelisation had lead to many decisiv breakthroughs, in particular (i) in the comprehension of the quantum entranglement properties (ii) in very promising in term of physical implementation quantum calculus model, and (iii) in the analysis and construction of quantum cryptography protocols. The goal of this thesis is to study the graphic properties emerging of those quantum information processing problematics, especially for quantum simulation. In particular, the properties of causality and locality in graph states, by extanding for exemple the existing notion of causality flows to a notion integring the locality constraints, would allow new perspectives for the quantum system simulation using graphs states. Formal connections with noisy quantum cellular automata would emerge from this study
7
Douce, Tom. "Realistic quantum information processing : from devices to computational models." Thesis, Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCC201/document.
Full textAbstract:
La théorie du calcul quantique se situe à la frontière de la physique quantique et de l’informatique. Par conséquent, les deux domaines contribuent à la rendre d’autant plus riche en apportant leurs propres méthodes et outils mathématiques. La présente thèse tente de mettre en évidence cette particularité en traitant des problématiques qui vont la physique expérimentale aux modèles de calcul. Le but est d’offrir de nouvelles possibilités pour démontrer un avantage quantique. Après une brève introduction aux notions de base de la mécanique quantique, certains aspects liés à l’informatique sont discutés. Le formalisme des classes de complexité quantiques ainsi que le concept du calcul quantique en variables continues sont décrits. Ensuite, le modèle connu comme instantaneous quantum computing est traduit en variables continues, le rendant attrayant d’un point de vue expérimental. Le chapitre conclut sur une discussion concernant un protocole hybride impliquant l’algorithme de Grover dans le cadre des communications quantiques. La dernière partie de la thèse s’intéresse à des problématiques issues de la physique expérimentale. Le lien entre l’effet Hong-Ou-Mandel et la fonction de Wigner d’un état à deux photons est mise en évidence, et un protocole expérimental est décrit en conséquence. La suite traite du domaine des circuits supraconducteurs et envisage de possibles expériences. Il est montré comment utiliser un qubit de flux pour manipuler un centre coloré du diamant. Il est également décrit comment sonder le modèle de Rabi dans le régime de couplage ultra fort en utilisant un qubit supplémentaire faiblement coupléThe theory of quantum computing lies at the very boundary between quantum physics and computer science. As such, both fields bring their own methods and mathematical tools to make quantum computing even richer. The present thesis attempts to reflect this specificity by addressing questions ranging from experimental physics to computational models. The goal is to provide novel ways of demonstrating quantum advantage. After a short introduction to basic notions of quantum mechanics, some computer science aspects are discussed. We describe the powerful formalism of quantum complexity classes and the concept of quantum computations based on continuous variables. We then translate the model of instantaneous quantum computing to continuous variables, which is experimentally appealing. The chapter concludes with a discussion on a hybrid protocol involving Grover’s algorithm in a quantum communication framework. The last part of the thesis is devoted to experimentally driven issues. A fundamental connection between the Hong-Ou-Mandel experiment and the Wigner function of two-photon states is derived and a verification protocol is designed accordingly. We then move to the field of superconducting circuits to discuss proposals for future experiments. We show how to use a flux qubit to manipulate a NV color center. We also describe how to use to probe the Rabi model in the ultra strong coupling regime using an additional weakly coupled qubit
8
Kaplan, Marc. "Méthodes Combinatoires et Algébriques en Complexité de la Communication." Phd thesis, Université Paris Sud - Paris XI, 2009. http://tel.archives-ouvertes.fr/tel-00439929.
Full textAbstract:
La complexité de la communication a été introduite en 1979 par Andrew Chi-Chi Yao. Elle est depuis devenue l'un des modèles de calcul les plus étudiés. L'objectif de celle-ci est d'étudier des problèmes dont les entrées sont distribuées entre plusieurs joueurs, en quantifiant la communication que ceux-ci doivent échanger. Nous utilisons d'abord la complexité de Kolmogorov, une caractérisation algorithmique de l'aléatoire, pour prouver des bornes inférieures sur la complexité de la communication. Notre méthode constitue une généralisation de la méthode d'incompressibilité. L'avantage de cette approche est de mettre en valeur la nature combinatoire des preuves. Nous étudions ensuite la simulation des distributions de probabilité causales avec de la communication. Ce modèle généralise la complexité de la communication traditionnelle et comprend en particulier les distributions quantiques. Nous montrons pour ce problème des bornes inférieures et supérieures. Dans le cas des fonctions booléennes, la borne inférieure que nous proposons est équivalente aux normes de factorisation, une puissante méthode introduite par Linial et Shraibman en 2006. Enfin, nous étudions la complexité en boîte non-locale. Cette ressource a été introduite par Popescu et Rohrlich pour étudier la non-localité. Le problème est de quantifier le nombre de boîtes nécessaire et suffisant pour calculer une fonction ou simuler une distributions. Nous donnons encore des bornes inférieures et supérieures pour ces problèmes, ainsi que des applications à l'évaluation sécurisée, un problème cryptographique très important.
9
Bredariol, Grilo Alex. "Quantum proofs, the local Hamiltonian problem and applications." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC051/document.
Full textAbstract:
Dans la classe de complexité QMA – la généralisation quantique de la classe NP – un état quantique est fourni comme preuve à un algorithme de vérification pour l’aider à résoudre un problème. Cette classe de complexité a un problème complet naturel, le problème des Hamiltoniens locaux. Inspiré par la Physique de la matière condensée, ce problème concerne l’énergie de l’état fondamental d’un système quantique. Dans le cadre de cette thèse, nous étudions quelques problèmes liés à la classe QMA et au problème des Hamiltoniens locaux. Premièrement, nous étudions la différence de puissance si au lieu d’une preuve quantique, l’algorithme de vérification quantique reçoit une preuve classique. Nous proposons un cadre intermédiaire à ces deux cas, où la preuve consiste en un état quantique “plus simple” et nous arrivons à démontrer que ces états plus simples sont suffisants pour résoudre tous les problèmes dans QMA. À partir de ce résultat, nous obtenons un nouveau problème QMA-complet et nous étudions aussi la version de notre nouvelle classe de complexité avec erreur unilatérale. Ensuite, nous proposons le premier schéma de délégation vérifiable relativiste de calcul quantique. Dans ce cadre, un client classique délègue son calcul quantique à deux serveurs quantiques intriqués. Ces serveurs peuvent communiquer entre eux en respectant l’hypothèse que l’information ne peut pas être propagé plus vite que la vitesse de la lumière. Ce protocole a été conçu à partir d’un jeu non-local pour le problème des Hamiltoniens locaux avec deux prouveurs et un tour de communication. Dans ce jeu, les prouveurs exécutent des calculs quantiques de temps polynomiaux sur des copies de l’état fondamental du Hamiltonien. Finalement, nous étudions la conjecture PCP quantique, où l’on demande si tous les problèmes dans la classe QMA acceptent un système de preuves où l’algorithme de vérification a accès à un nombre constant de qubits de la preuve quantique. Notre première contribution consiste à étendre le modèle QPCP avec une preuve auxiliaire classique. Pour attaquer le problème, nous avons proposé une version plus faible de la conjecture QPCP pour ce nouveau système de preuves. Nous avons alors montré que cette nouvelle conjecture peut également être exprimée dans le contexte des problèmes des Hamiltoniens locaux et ainsi que dans lecadre de la maximisation de la probabilité de acceptation des jeux quantiques. Notre résultat montre la première équivalence entre un jeu multi-prouveur et une conjecture QPCPIn QMA, the quantum generalization of the complexity class NP, a quantum state is provided as a proof of a mathematical statement, and this quantum proof can be verified by a quantum algorithm. This complexity class has a very natural complete problem, the Local Hamiltonian problem. Inspired by Condensed Matters Physics, this problem concerns the groundstate energy of quantum systems. In this thesis, we study some problems related to QMA and to the Local Hamiltonian problem. First, we study the difference of power when classical or quantum proofs are provided to quantum verification algorithms. We propose an intermediate setting where the proof is a “simpler” quantum state, and we manage to prove that these simpler states are enough to solve all problems in QMA. From this result, we are able to present a new QMA-complete problem and we also study the one-sided error version of our new complexity class. Secondly, we propose the first relativistic verifiable delegation scheme for quantum computation. In this setting, a classical client delegates her quantumcomputation to two entangled servers who are allowed to communicate, but respecting the assumption that information cannot be propagated faster than speed of light. This protocol is achieved through a one-round two-prover game for the Local Hamiltonian problem where provers only need polynomial time quantum computation and access to copies of the groundstate of the Hamiltonian. Finally, we study the quantumPCP conjecture, which asks if all problems in QMA accept aproof systemwhere only a fewqubits of the proof are checked. Our result consists in proposing an extension of QPCP proof systems where the verifier is also provided an auxiliary classical proof. Based on this proof system, we propose a weaker version of QPCP conjecture. We then show that this new conjecture can be formulated as a Local Hamiltonian problem and also as a problem involving the maximum acceptance probability of multi-prover games. This is the first equivalence of a multi-prover game and some QPCP statement
10
Javelle, Jérôme. "Cryptographie Quantique : Protocoles et Graphes." Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENM093/document.
Full textAbstract:
Je souhaite réaliser un modèle théorique optimal pour les protocoles de partage de secret quantique basé sur l'utilisation des états graphes. Le paramètre représentatif d'un partage de secret à seuil est, entre autres la taille du plus grand ensemble de joueurs qui ne peut pas accéder au secret. Je souhaite donc trouver un famille de protocoles pour laquelle ce paramètre est le plus petit possible. J'étudie également les liens entre les protocoles de partage de secret quantique et des familles de courbes en géométrie algébriqueI 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
Books on the topic "Complexité du calcul quantique"
2
Scandinavian Workshop on Algorithm Theory (7th 2000 Bergen, Norway). Algorithm theory - SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, July 5-7, 2000 ; proceedings. Berlin: Springer, 2000.
Find full text
3
Scandinavian Workshop on Algorithm Theory (7th 2000 Bergen, Norway). Algorithm theory-- SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000 : proceedings. Berlin: Springer, 2000.
Find full text
5
International Meeting of Young Computer Scientists (5th 1988 Smolenice, Slovakia). Machines, languages, and complexity. Berlin: Springer-Verlag, 1989.
Find full text
6
C, Berwick Robert, and Ristad Eric Sven, eds. Computational complexity and natural language. Cambridge, Mass: MIT Press, 1987.
Find full text
7
Kearns, Michael J. The computational complexity of machine learning. Cambridge, Mass: MIT Press, 1990.
Find full text
9
Complexity theory and cryptology: An introduction to cryptocomplexity. Berlin: Springer, 2005.
Find full text
10
Meinel, Christoph. Modified branching programs and their computational power. Berlin: Springer-Verlag, 1989.
Find full textBook chapters on the topic "Complexité du calcul quantique"
1
"Chapitre 3 Calculabilité et complexité." In Physique quantique, information et calcul, 85–134. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7-007.
Full text
2
"Chapitre 3 Calculabilité et complexité." In Physique quantique, information et calcul, 85–134. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7.c007.
Full text
3
"Chapitre 1 Théorie quantique." In Physique quantique, information et calcul, 9–48. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7-005.
Full text
4
"Chapitre 1 Théorie quantique." In Physique quantique, information et calcul, 9–48. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7.c005.
Full text
5
"Chapitre 11 Caractériser les corrélations quantiques." In Physique quantique, information et calcul, 449–68. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7-015.
Full text
6
"Chapitre 7 Communiquer en utilisant des qubits." In Physique quantique, information et calcul, 227–92. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7-011.
Full text
7
"Chapitre 8 Calculer en utilisant des qubits." In Physique quantique, information et calcul, 293–364. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7-012.
Full text
8
"Chapitre 10 Vers une ingénierie quantique." In Physique quantique, information et calcul, 395–448. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7-014.
Full text
9
"Chapitre 9 Dynamique des systèmes quantiques ouverts." In Physique quantique, information et calcul, 365–94. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7-013.
Full text
10
"Introduction." In Physique quantique, information et calcul, 1–4. EDP Sciences, 2020. http://dx.doi.org/10.1051/978-2-7598-2413-7-003.
Full text