What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.
What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.
This thesis explores the interplay between structure and randomness in quantum computation, with the goal being to characterise the types of structure that give quantum computers an advantage over classical computation. The thesis begins by giving a necessary and sufficient condition for one notion of a quantum walk to be defined on a directed graph, and goes on to derive conditions on the structure of graphs that allow a quantum advantage in a non-local graph colouring game. A lower bound on entanglement-assisted quantum communication complexity based on information-theoretic ideas is given, and applied to the communication complexity of random functions. New lower bounds on the probability of success of quantum state discrimination are derived, and are applied to the problem of distinguishing random quantum states. This result is used to show a quantum advantage in almost all instances of a bounded-error single-query oracle identification problem. Lower bounds, and almost optimal algorithms, are given for two models of quantum search of partially ordered sets. This leads to the development of an optimal quantum algorithm to find the intersection of two sorted lists.
Quantum computing is the study of what we can and cannot do with quantum computers: computers operating based on the laws of quantum mechanics. This thesis is a collection of seven papers, dealing with three aspects of quantum computing: non-locality, cryptography and complexity.
Nonlocality. Quantum nonlocality refers to the fact that, using a resource called quantum entanglement, two participants who are physically separated and unable to communicate can exhibit correlations that cannot be produced without entanglement. This gives rise to nonlocal games, which are multi-player cooperative games for which quantum players (who share entanglement) have an advantage over classical players (who share only classical information). A pseudo-telepathy game is a special case of a nonlocal game for which quantum players have a perfect winning strategy. The first paper in this thesis, On the power of non-local boxes, is a study of quantum correlations (which are non-signalling, i.e. they do not allow faster-than-light communication), as well as superquantum correlations (which are also non-signalling, but stronger than those predicted by quantum mechanics). We consider the simulation of pseudo-telepathy winning strategies with the nonlocal box (which can be seen as the most basic superquantum correlation), revealing that nonlocality and entanglement are different resources. Before our work, it was common to equate these two notions. The second paper, Classical, quantum and non-signalling resources in bipartite games, shows that the problem of deciding if a fixed game has a perfect classical winning strategy is NP-complete, while deciding if a perfect strategy exists with superquantum correlations is in P. We also establish links with the Bell-Kochen-Specker theorem, orthogonality graphs and two-prover interactive proofs.
Quantum nonlocality is a phenomenon that we can, in theory, witness in the laboratory. Many experiments have been performed, but none so far have simultaneously closed all experimental loopholes. There is currently a substantial scientific effort to achieve the perfect laboratory experiment. Yet not all experimental setups are created equally: the third and fourth paper of this thesis, Entanglement swapping, light cones and elements of reality and On the logical structure of Bell theorems, show that recent proposals have classical explanations, and thus do nothing to aid in our comprehension of the quantum world. This work is scientifically valuable, since it tells us that we should not invest in the proposed lines of research.
Classical and quantum cryptography. The groundbreaking work of Peter Shor in 1995 established that quantum computers can efficiently factor large integers, thus rendering most modern cryptographic systems insecure. But what quantum computers break, they also fix: Bennett and Brassard had already given in 1984 a protocol for key distribution whose security is based only on the laws of quantum mechanics.
In a world with quantum computers, it seems like the only way to ensure perfect security in cryptographic tasks is to do away with computational assumptions (such as the apparent difficulty of factoring): this is the realm of information-theoretic security. In the fifth paper of this thesis, Information-theoretic security without an honest majority we give protocols to accomplish a series of six private distributed tasks (in particular, vote and anonymous message transmission), while ensuring information-theoretic security. Then, in Anonymous quantum communication, we give a protocol which, within a group, allows a sender to transfer a quantum message to a receiver ofhis choosing. The protocol ensures information-theoretic anonymity for the sender and the receiver as well as information-theoretic privacy for the message.
Complexity in the measurement-based model. Finally, in Parallelizing quantum circuits, we study the depth complexity of quantum circuits, giving an automated technique for the parrallelization of quantum circuits. The development of parallel (low-depth) quantum circuits seems almost essential if we wish to implement quantum algorithms in the near future with available technology. Quantum information is usually unstable, hence we can only operate on it for a very short period of time. Parallel circuits maximize the use of this fragile quantum information. Our method is based on the recent paradigm for quantum computing called the measurement-based model.
Key words: quantum information processing, pseudo-telepathy, nonlocal boxes, Bell's theorem, multi-party computation, information-theoretic security, anonymity, quantum depth complexity, measurement-based quantum computing, measurement calculus.
We study quantum entanglement and some of its applications in graph theory and zero-error information theory. In Chapter 1 we introduce entanglement and other fundamental concepts of quantum theory. In Chapter 2 we address the question of how much quantum correlations generated by entanglement can deviate from classical predictions. We focus on non-local games: experiments in which two players are separated and forbidden to communicate, and have to collaborate to accomplish a task. We give two games exhibiting quantum-classical separations close to optimal. Remarkably, our results in theoretical physics are inspired by theoretical computer science. Chapter 3 is dedicated to the study of quantum graph parameters. Well-known quantities such as the chromatic number and the independence number of a graph can be interpreted as parameters for non-local games. A definition of quantum graph parameters follows from this fact. We contribute to the field in a number of ways. Among other results, we find a surprising characterization of the quantum chromatic number that relates to the Kochen-Specker theorem, a result in the foundations of quantum mechanics. In Chapter 4, we move to zero-error information theory. We study the zero error capacity of a classical noisy channel when the sender and the receiver can use quantum entanglement. We initiate the study of the source problem and source-channel problem with entanglement and we find channels and sources that exhibit a strong divergence in quantum and classical behaviours. To do that, we use results in combinatorics, linear algebra, optimization and number theory.
In this PhD thesis we study the effects of quantum entanglement, one of quantum mechanics most peculiar features, in nonlocal games and communication problems in zero-error information theory. A nonlocal game is a thought experiment in which two cooperating players, who are forbidden to communicate, want to perform a certain task. Zero-error information theory is the mathematical field that studies communication problems where no error is tolerated. The unifying link among the various scenarios we consider is their combinatorial nature and in particular their reformulations as graph theoretical problems, mainly concerning the chromatic and stability numbers and some quantum generalizations thereof. In this thesis we propose a novel approach to the study of these quantum graph parameters using the paradigm of conic optimization. For that, we introduce and study the completely positive semidefinite cone, a new matrix cone consisting of all symmetric matrices that admit a Gram representation by positive semidefinite matrices. Furthermore, we investigate whether entanglement allows for better-than-classical communication schemes in some well-known problems from zero-error information theory. For example we study the channel coding problem, which asks a sender to transmit data reliably to a receiver in the presence of noise, as well as some of its generalizations.
This dissertation contains results on three quite different topics. First, I investigate the entanglement resources required for two parties to jointly implement a unitary operation using local operations and classical communication (LOCC). If this resource is of smallest feasible Schmidt rank then it must be maximally entangled. If the Schmidt rank is higher, less entanglement may suffice. Second, I investigate the source of the “quantum speedup”. I quantify quantum interference and show that in order for a quantum computer to be significantly faster than a classical computer, it must make use of operations capable of producing large amounts of interference (or a large number of operations that can produce small amounts of interference). A quantum computer not making use of such a resource can be efficiently simulated by a classical computer. Third, I investigate zero-error source-channel coding. In this scenario, Alice wishes to convey a message to Bob through a noisy channel, with zero chance of error, in the case where Bob already has some prior knowledge regarding the message that is to be sent. For classical messages and classical channels, it was known that three graph invariants of Lovász, Szegedy, and Schrijver provide necessary conditions for this task. We show that this applies also when Alice and Bob make use of an entangled state, unifying and extending a series of previous results. Finally, I introduce a fully quantum version of source-channel coding where the message to be sent, the channel, and the side information are all quantum. Whereas the classical case makes use of graphs, the quantum case makes use of non-commutative graphs. I generalize the concept of graph homomorphism, as well as the Szegedy and Schrijver numbers, to non-commutative graphs and show that the necessary conditions for the classical case generalize to the quantum case. Using this theory, I construct a quantum channel whose one-shot zero-error entanglement assisted capacity can only be unlocked using a non-maximally entangled state, showing that in this case less is more when it comes to entanglement resources.
Entanglement is at the heart of quantum mechanics. The nonlocal correlations that can be obtained from space-time separated measurements on an entangled state are a central feature which provably distinguish it from local theories. This dissertation studies entanglement through a computational viewpoint. We develop new insights into the complex nature of entanglement by studying its role in multiplayer games, in which cooperating, but non-communicating, players interact with a referee in an attempt to win a pre-specified game. On the one hand, the nonlocal correlations that entanglement allows may enable players using it to develop new colluding strategies, defeating previously secure protocols. On the other, the richness of this new resource may also be exploited in order to design new protocols, providing solutions to problems previously deemed impossible. We explore both aspects of this dual nature of entanglement, putting limits on its strength while at the same time showing how it can be put to profit to solve new computational problems. A major unresolved question on the computational complexity of multiplayer entangled games is the power of MIP*, the class of languages having entangled multi-prover interactive proofs: how does it relate to its purely classical analogue MIP, which was completely characterized through the fundamental equation MIP=NEXP? Since the players may use entanglement to increase their odds at colluding against the verifier, MIP* could potentially be a much weaker class than MIP. Indeed, for a long time it has been an open question whether two entangled provers are more useful than a single prover. In this thesis we resolve this question by showing that the class of languages having multiprover interactive proofs with entangled provers is at least as large as its classical counterpart: NEXP is included in MIP*. At the heart of this result is an analysis of the multilinearity test of Babai, Fortnow, and Lund in the presence of entanglement. The fact that this test remains sound gives a systematic way for a verifier to impose strong limits on the ability of entangled provers to collude against the verifier.Gap amplification is a fundamental primitive in the study of classical multiplayer games. While sequential repetition of a game always decreases the prover's maximum success probability at an exponential rate, the fact that parallel repetition also achieves a gap amplification is a highly non-trivial fact. We show that gap amplification can be performed in parallel even in the presence of entanglement between the provers. We adapt a technique which was originally introduced by Feige and Kilian and results in a polynomial rate of amplification.The phenomenon of monogamy of entanglement states, in first approximation, that if two parties are maximally entangled then they cannot simultaneously be entangled with a third party. We use this phenomenon in two distinct results. In the first, we show that the bits generated in our randomness-expansion protocol are certifiably random even from the point of view of a quantum adversary who may share prior entanglement with the provers. In addition, we prove the security against quantum adversaries of a randomness-efficient extractor construction originally due to Trevisan. This lets us transform the high-entropy bits that are generated in our protocol into ones that are almost indistinguishable from uniform by any adversary. More generally, we show how the monogamy of entanglement can be exploited to design multi-prover interactive proof systems that are partially entanglement-resistant. Quantitative bounds on the monogamy of entanglement have generally been elusive, and the analysis of our protocol demonstrates such a bound in a new context. The nonlocal correlations that can be created by entangled players provide a statistical means of differentiating them from classical, unentangled players. This is the main idea behind Bell inequalities, the violation of which demonstrates the nonlocality of quantum mechanics. We show how this phenomenon may be exploited to design a protocol in which the bits produced by successful players necessarily contain a large quantity of fresh randomness. The presence of randomness is guaranteed irrespective of the provers' actual strategy, as long as the sole constraint of no signaling is respected. Hence a statistical certification for the presence of randomness, a feat easily seen to be impossible to achieve classically. In order to manipulate the random bits produced in our protocol, and make them useful in cryptography, we give the first proof of security of a poly-logarithmic seed extractor secure against quantum adversaries. To achieve this we adapt the reconstruction paradigm originally introduced by Trevisan to the quantum setting. We study other ways in which entanglement may be used in interactive proof systems by also allowing a quantum interaction between the referee and the players. We show that, using entanglement, the class of QMIP* proof systems can be parallelized to only three rounds of interaction, and made public-coin, a property that does not hold in the absence of entanglement between the provers.