Dissertations / Theses on the topic 'Quantum computational complexity'

Kyoto University (京都大学)<br>0048<br>新制・課程博士<br>博士(情報学)<br>甲第11157号<br>情博第132号<br>新制||情||30(附属図書館)<br>22726<br>UT51-2004-R32<br>京都大学大学院情報学研究科通信情報システム専攻<br>(主査)教授 岩間 一雄, 教授 福嶋 雅夫, 教授 北野 正雄<br>学位規則第4条第1項該当

Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.<br>This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.<br>Cataloged from student-submitted PDF version of thesis.<br>Includes bibliographical references (pages 141-145).<br>While physical theories attempt to break down the observed structure and behavior of possibly large and complex systems to short descriptive axioms, the perspective of a computer scientist is to start with simple and believable set of rules to discover their large scale behaviors. Computer science and physics, however, can be combined into a new framework, wherein structures can be compared with each other according to scalar observables like mass and temperature, and also complexity at the same time. For example, similar to saying that one object is heavier than the other, we can discuss which system is more complex. According to this point of view, a more complex system can be interpreted as the one which can be programmed to encode and simulate the behavior of the others within its own degrees of freedom. Within this framework, at the most fundamental layer, physical systems are related to languages. In this thesis, I try to exemplify this point of view through an analysis of certain quantum theories in two dimensional space-time. In simple words, these models are the quantum analogues of elastic scattering of colored balls moving on a line. The models are closely related to each other in both relativistic and non-relativistic regimes. Physical examples that motivate this are the factorized scattering matrix of quantum field theory, and the repulsive delta interactions of quantum mechanics, in 1+1 dimensions. In classical mechanics, when two hard balls collide, they bounce off and remain in the same order. However, in the quantum setting, during a collision, either the balls bounce off, or otherwise they tunnel through each other, and exchange their configurations. Each event occurs with a certain probability. As a result, moving balls are put in a superposition of being in different color configurations. Thereby, if we consider n distinct balls, the state space is according to their n! possible arrangements, and their collisions act as quantum transpositions. Quantum transpositions can then be viewed as local quantum gates. I therefore consider the general Hilbert space of permutations, and study the space of unitary operators that can be generated by the local permuting gates. I first show that all of the discussed quantum theories can be programmed into an idealized model, the quantum ball permuting model, and then I will try to pin down the language of this model within the already known complexity classes. The main approach is to consider a series of models, as the variations of the ball scattering problem, and then to relate them to each other, using tools of computational complexity and quantum complexity theory. I find that the computational complexity of the ball permuting model depends on the initial superposition of the balls. More precisely, if the balls start out from the identity permutation, the model can be simulated in a one clean qubit, which is believed to be strictly weaker than the standard model of quantum computing. Given this upper-bound on the ball permuting model, the result is that the model of ball scatterings can be simulated within a one clean qubit, if they start out from an identity permutation. Furthermore, I will demonstrate that if special superpositions are allowed in the initial state, then the ball permuting model can efficiently simulate and sample from the output distribution of standard quantum computers. Next, I show how to use intermediate demolition ball detections to simulate the ball permuting model nondeterministically. According to this result, using post-selection on the outcome of these measurements, one obtains the original ball permuting model. Therefore, the post-selected analogue of ball scattering model can efficiently simulate standard quantum computers, when arbitrary initial superpositions are allowed. In the end, I formalize a quantum computer based on ball collisions and intermediate ball detections, and then I prove that the possibility of efficient simulation of this model on a classical computer is ruled out, unless the polynomial hierarchy collapses to its third level.<br>by Saeed Mehraban.<br>S.M.

Orientador: Arnaldo Vieira Moura<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação<br>Made available in DSpace on 2018-08-25T06:09:05Z (GMT). No. of bitstreams: 1 Grilo_AlexBredariol_M.pdf: 1279418 bytes, checksum: 80f0b105ffcfb57f6e43c530b32cb7a9 (MD5) Previous issue date: 2014<br>Resumo: A Computação Quântica é um tópico relativamente recente e pouco conhecido, principalmente no meio da Computação. Seu estudo surgiu na tentativa de físicos simularem sistemas regidos pela Mecânica Quântica por computadores clássicos, o que se conjecturou inviável. Portanto, um novo modelo computacional que utiliza a estrutura quântica da matéria para computar foi teorizado para suprir estas deficiências. Este trabalho tem como objetivo principal estudar as influências da Computação Quântica na Teoria da Computação. Para atingir tal objetivo, primeiramente são expostos os conhecimentos básicos da Mecânica Quântica através de uma linguagem voltada para Teóricos de Computação sem conhecimento prévio na área, de forma a remover a barreira inicial sobre o tema. Em seguida, serão apresentadas inovações na área da Teoria de Computação oriundas da Computação Quântica. Começaremos com os principais Algoritmos Quânticos desenvolvidos até hoje, que foram os primeiros passos para demonstrar a possível superioridade computacional do novo modelo. Dentre estes algoritmos, apresentaremos o famoso Algoritmo de Shor, que fatora números em tempo polinomial. Adicionalmente, neste trabalho foram estudados tópicos mais avançados e atuais em Computabilidade e Complexidade Quânticas. Sobre Autômatos Quânticos, foram estudados aspectos de um modelo que mistura estados clássicos e quânticos, focando na comparação do poder computacional em relação aos Autômatos Finitos Clássicos. Do ponto de vista de Classes de Complexidade, será abordada a questão se em linguagens da classe QMA, o análogo quântico da classe NP, consegue-se atingir probabilidade de erro nulo na aceitação de instâncias positivas<br>Abstract: Quantum Computing is a relatively new area and it is not well known, mainly among Computer Scientists. It has emerged while physicists tried to simulate Quantum Systems with classical computers efficiently, which has been conjectured impossible. Then, a new computational model that uses the quantum structure of matter to perform computations has been theorized in order to perform these operations. We intend in this work to study the influences of Quantum Computing in Theoretical Computer Science. In order to achieve this goal, we start by presenting the basics of Quantum Computing to Theoretical Computer Science readers with no previous knowledge in this area, removing any initial barriers for a clean understanding of the topic. We will then follow by showing innovations in Theoretical Computer Science introduced by Quantum Computation. We start by showing the main Quantum Algorithms, that exemplify advantages of the new computational model. Among these algorithms, we will present the Shor Algorithm that factors numbers in polynomial time. We follow with more advanced topics in Quantum Computability and Complexity. We study Quantum Finite Automata Models that work with quantum and classical states, focusing on comparing their computational power with Deterministic Finite Automata. In Complexity Theory, we study the question if for languages in QMA, the quantum analogue of NP, zero probability error can be achieved in yes-instances<br>Mestrado<br>Ciência da Computação<br>Mestre em Ciência da Computação

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 physiques<br>Recent 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

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2019<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 355-372).<br>Restricted models of quantum computation are mathematical models which describe quantum computers that have limited access to certain resources. Well-known examples of such models include the boson sampling model, extended Clifford circuits, and instantaneous quantum polynomial-time circuits. While unlikely to be universal for quantum computation, several of these models appear to be able to outperform classical computers at certain computational tasks, such as sampling from certain probability distributions. Understanding which of these models are capable of performing such tasks and characterizing the classical simulation complexity of these models--i.e. how hard it is to simulate these models on a classical computer--are some of the central questions we address in this thesis. Our first contribution is a classification of various extended Clifford circuits according to their classical simulation complexity.<br>Among these circuits are the conjugated Clifford circuits, which we prove cannot be efficiently classically simulated up to multiplicative or additive error, under certain plausible conjectures in computational complexity theory. Our second contribution is an estimate of the number of qubits needed in various restricted quantum computation models in order for them to be able to demonstrate quantum computational supremacy. Our estimate is obtained by fine-graining existing hardness results for these restricted models. Our third contribution is a new alternative proof of the Gottesman-Knill theorem, which states that Clifford circuits can be efficiently simulated by a classical computer. Our proof uses the sum-over-paths technique and establishes a correspondence between quantum circuits and a class of exponential sums. Our final contribution is a theorem characterizing the operations that can be efficiently simulated using a particular rebit simulator.<br>An application of this result is a generalization of the Gottesman-Knill theorem that allows for the efficient classical simulation of certain nonlinear operations.<br>"Funding support from the National Science Scholarship awarded by the Agency for Science, Technology and Research (A*STAR), Singapore, as well as the Enabling Practical-scale Quantum Computing (EPiQC) Expedition, an NSF expedition in computing"--Page 6.<br>by Dax Enshan Koh.<br>Ph. D.<br>Ph.D. Massachusetts Institute of Technology, Department of Mathematics

Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.

<p>The effects of open system evolution on single particle interferometry, quantum computation, and the adiabatic approximation are investigated.</p><p>Single particle interferometry: Three concepts concerning completely positive maps (CPMs) and trace preserving CPMs (channels), named subspace preserving (SP) CPMs, subspace local channels, and gluing of CPMs, are introduced. SP channels preserve probability weights on given orthogonal sum decompositions of the Hilbert space of a quantum system. Subspace locality determines what channels act locally with respect to such decompositions. Gluings are the possible total channels obtainable if two evolution devices, characterized by channels, act jointly on a superposition of a particle in their inputs. It is shown that gluings are not uniquely determined by the two channels. We determine all possible interference patterns in single particle interferometry for given channels acting in the interferometer paths. It is shown that the standard interferometric setup cannot distinguish all gluings, but a generalized setup can.</p><p>Quantum computing: The robustness of local and global adiabatic quantum search subject to decoherence in the instantaneous eigenbasis of the search Hamiltonian, is examined. In both the global and local search case the asymptotic time-complexity of the ideal closed case is preserved, as long as the Hamiltonian dynamics is present. In the case of pure decoherence, where the environment monitors the search Hamiltonian, it is shown that the local adiabatic quantum search performs as the classical search with scaling N, and that the global search scales like N^3/2 , where N is the list length. We consider success probabilities p<1 and prove bounds on the run-time with the same scaling as in the conditions for the p → 1 limit.</p><p>Adiabatic evolution: We generalize the adiabatic approximation to the case of open quantum systems in the joint limit of slow change and weak open system disturbances. </p>

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é<br>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

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 QPCP<br>In 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

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 bonnes<br>Fault 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

The computational problem of distinguishing two quantum channels is central to quantum computing. It is a generalization of the well-known satisfiability problem from classical to quantum computation. This problem is shown to be surprisingly hard: it is complete for the class QIP of problems that have quantum interactive proof systems, which implies that it is hard for the class PSPACE of problems solvable by a classical computation in polynomial space. Several restrictions of distinguishability are also shown to be hard. It is no easier when restricted to quantum computations of logarithmic depth, to mixed-unitary channels, to degradable channels, or to antidegradable channels. These hardness results are demonstrated by finding reductions between these classes of quantum channels. These techniques have applications outside the distinguishability problem, as the construction for mixed-unitary channels is used to prove that the additivity problem for the classical capacity of quantum channels can be equivalently restricted to the mixed unitary channels.

Keywords: entanglement, complexity, entropy, measurement In chapter 1 the basic principles of communication complexity are introduced. Two-party communication is described explicitly, and multi-party communication complexity is described in terms of the two-party communication complexity model. The relation to entropy is described for the classical communication model. Important concepts from quantum mechanics are introduced. More advanced concepts, for example the generalized measurement, are then presented in detail. In chapter 2 the di erent measures of entanglement are described in detail, and concrete examples are provided. Measures for both pure states and mixed states are described in detail. Some results for the Schmidt decomposition are derived for applications in communication complexity. The Schmidt decomposition is fundamental in quantum communication and computation, and thus is presented in considerable detail. Important concepts such as positive maps and entanglement witnesses are discussed with examples. Finally, in chapter 3, the communication complexity model for quantum communication is described. A number of examples are presented to illustrate the advantages of quantum communication in the communication complexity scenario. This includes communication by teleportation, and dense coding using entanglement. A few problems, such as the Deutsch-Jozsa problem, are worked out in detail to illustrate the advantages of quantum communication. The communication complexity of sampling establishes some relationships between communication complexity, the Schmidt rank and entropy. The last topic is coherent communication complexity, which places communication complexity completely in the domain of quantum computation. An important lower bound for the coherent communication complexity in terms of the Schmidt rank is dervived. This result is the quantum analogue to the log rank lower bound in classical communication complexity.<br>Prof. W.H. Steeb

Many quantum computation algorithms, and processes like measurement based quantum computing, require the initial state of the quantum computer to be an eigenstate of a specific unitary operator. Here we study how quantum states that are eigenstates of finite dimensional irreducible representations of the special unitary (SU(d)) and the permutation (S_n) groups can be efficiently constructed in the computational basis formed by tensor products of the qudit states. The procedure is a unitary transform, which first uses Schur-Weyl duality to map every eigenstate to a unique Schur basis state, and then recursively uses the Clebsch - Gordan transform to rotate the Schur basis state to the computational basis. We explicitly provide an efficient quantum algorithm, and the corresponding quantum logic circuit, to generate any desired eigenstate of SU(2) and SU(3) irreducible representations in the computational basis.

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.<br>Since the introduction of quantum mechanics, many mysteries of nature have found explanations. Many quantum-mechanical concepts have merged with the field of computational complexity theory. New ideas and solutions have been put forward to solve computational problems. In particular, quantum mechanics has struck down many security proofs of classical protocols. In this thesis, we survey recent results regarding the implication of quantum mechanics to computational complexity and more precisely to classes with interaction. We present the work done in the framework of cooperative games with imperfect information. We give some differences between classical, quantum and no-signaling theories and apply them to the specific example of Odd Cycle Games. We center our attention on two different themes: the effect on a game of adding more players and of parallel repetition. We observe that depending of the physical theory considered, the consequences of these changes is very different.

La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive.<br>Quantum information theory has developed tremendously over the past two decades, with analogues and extensions of the source coding and channel coding theorems for unidirectional communication. Meanwhile, for interactive communication, a quantum analogue of communication complexity has been developed, for which quantum protocols can provide exponential savings over the best possible classical protocols for some classical tasks. However, quantum information is much more sensitive to noise than classical information. It is therefore essential to make the best use possible of quantum resources. In this thesis, we take an information-theoretic point of view on interactive quantum protocols and study the interactive analogues of source compression and noisy channel coding. The setting we consider is that of quantum communication complexity: Alice and Bob want to perform some joint quantum computation while minimizing the required amount of communication. Local computation is deemed free. Our results are split into three distinct chapters, and these are organized in such a way that each can be read independently. Given its central role in the context of interactive compression, we devote a chapter to the task of quantum state redistribution. In particular, we prove lower bounds on its communication cost that are robust in the context of interactive communication. We also prove one-shot, one-message achievability bounds. In a subsequent chapter, we define a new, fully quantum notion of information cost for interactive protocols and a corresponding notion of information complexity for bipartite tasks. It characterizes how much quantum information, rather than quantum communication, Alice and Bob must exchange in order to implement a given bipartite task. We prove many structural properties for these quantities, and provide an operational interpretation for quantum information complexity as the amortized quantum communication complexity. In the special case of classical inputs, we provide an alternate characterization of information cost that provides an answer to the following question about quantum protocols: what is the cost of forgetting classical information? Two applications are presented: the first general multi-round direct-sum theorem for quantum protocols, and a tight lower bound, up to polylogarithmic terms, for the bounded-round quantum communication complexity of the disjointness function. In a final chapter, we initiate the study of the interactive quantum capacity of noisy channels. Since techniques to distribute entanglement are well-studied, we focus on a model with perfect pre-shared entanglement and noisy classical communication. We show that even in the harder setting of adversarial errors, we can tolerate a provably maximal error rate of one half minus epsilon, for an arbitrarily small epsilon greater than zero, at positive communication rates. It then follows that random noise channels with positive capacity for unidirectional transmission also have positive interactive quantum capacity. We conclude with a discussion of our results and further research directions in interactive quantum information theory.