Quantum Computing and Communication Complexity Ronald de Wolf Abstract: %Nr: DS-2001-06 %Author: Ronald de Wolf %Title: Quantum Computing and Communication Complexity Computers are physical objects and hence should follow the laws of physics. Somewhat surprisingly, today's computers (theoretical Turing machines as well as desk-top PCs) are developed on the model of classical physics rather than on the model of its 20th century successor quantum mechanics. The new field of quantum computing tries to make up for this deficit by studying the properties of computers that follow the laws of quantum mechanics. One of the striking properties of a quantum computer is that it can be in a superposition of many classical states at the same time, which can exhibit interference patterns. One of the main goals of the field of quantum computing is to find quantum algorithms that solve certain problems much faster than the best classical algorithms. Its two main successes so far are Shor's 1994 efficient quantum algorithm for finding the prime factors of large integers (which can break most of modern cryptography) and Grover's 1996 algorithm that can search an $n$-element space in about $\sqrt{n}$ steps. Part I: Query Complexity ------------------------ The starting point of part I of this thesis is the observation that virtually all known quantum algorithms (including Shor's and Grover's) can be described in terms of query complexity: they require far fewer queries to input bits than classical algorithms do. It thus appears that the model of query complexity captures a lot of the power of quantum computing. Accordingly, in part I of the thesis we make a detailed and general comparison of quantum query complexity versus classical query complexity for various kinds of computational problems. Our main tool in this comparison is algebraic: we prove that the quantum query complexity of a computational problem is lower bounded by the degree of a certain polynomial that in some sense represents that problem. This means that we can prove lower bounds on the quantum query complexity of various problems by analyzing polynomials for those problems. One of the main consequences of this technique is the result that quantum query complexity can be at most polynomially smaller than classical query complexity when we consider total computational problems (which are defined on all possible inputs). In other words, any exponential quantum speed-up in this model will have to be based on some promise on the input, some property that the input is known in advance to have. For example, for Shor's algorithm this promise is the periodicity of a certain function to which the factoring problem can be reduced. Apart from these general results that hold for all total problems, we also consider in more detail the quantum complexities of various specific computational problems. For example, we prove that the error probability in Grover's search algorithm can be reduced slightly better if we do this in a quantum way than if we do it in the usual classical way (which would just repeat Grover's algorithm many times). We also derive an algorithm for the element distinctness problem (which is: are the numbers on a list of $n$ elements all distinct?) that takes about $n^{3/4}$ steps. This shows that for a quantum computer the problem of element distinctness is significantly easier than the problem of sorting, in contrast to the classical world, where both problems require about $n\log n$ steps. Finally, we show that the negative result for standard query complexity (at most a polynomial quantum speed-up for all total problems) does not hold in two other versions of query complexity: average-case complexity and non-deterministic complexity. For both models we exhibit total problems and quantum algorithms for solving those problems that are exponentially better than the best classical algorithms. Part II: Communication and Complexity ------------------------------------- It has been known since the early 1970s that quantum communication cannot improve upon classical communication when it comes to information transmission: if Alice wants to send Bob $k$ bits of information, then she has to send him at least $k$ quantum bits (Holevo's theorem). However, Cleve and Buhrman discovered that if the goal of Alice and Bob is not to communicate information but to solve some distributed computational problem (Alice gets $x$, Bob gets $y$, and together they want to compute some function $f(x,y)$ with minimal communication between them), then sometimes the amount of communication can be reduced drastically by allowing quantum communication. For example, a result of Buhrman, Cleve, and Wigderson says that if Alice and Bob each have an $n$-slot agenda and they want to find a slot where they are both free, then they can do this with roughly $\sqrt{n}$ quantum bits of communication, whereas in the classical world about $n$ bits of communication would be needed. In part II of the thesis we look at this model of quantum communication complexity from various angles. We first discuss the main examples known where quantum communication complexity is significantly less than classical communication complexity. Then we consider the other side and develop techniques to show lower bounds on quantum communication complexity, again using algebraic techniques. These techniques imply, for example, that quantum communication cannot improve significantly upon classical communication complexity for almost all distributed problems. However, we also exhibit a new example where quantum communication complexity does improve upon classical complexity: in a specific 3-party model (Alice and Bob each send a message to a referee, who should then compute $f(x,y)$), the problem of testing equality between Alice and Bob's input can be solved with exponentially less communication when we allow quantum communication, using a new technique called quantum fingerprinting. In the final chapter we address an issue of security. Suppose Alice and Bob care not only about minimizing the amount of their communication, but also about keeping it secret: if some third party Eve is tapping the communication channel, then she should learn nothing about the actual messages. Classically, it is known that a shared secret $n$-bit key is necessary and sufficient to send a classical $n$-bit message from Alice to Bob in a way that gives no information to Eve (Shannon's theorem). We prove the quantum analogue of this: $2n$ bits of shared secret key are necessary and sufficient to securely send a message of $n$ quantum bits.