Academic CentreProject
Starting date: September 1, 2010
Duration: 36 months We plan research in three interrelated directions:
· Design of new quantum algorithms and communication protocols;
· The structure of quantum algorithms and communication protocols;
· Mathematical tools for quantum information science In more detail, our plans are as follows. 1. New quantum algorithms. We expect quantum computers to be uniquely useful because by now a multitude of computational problems is known for which quantum algorithms provide either an exponential advantage over the running time of the best available classical algorithm (most famously Shor’s factoring algorithm), or because of another, sometimes “only” polynomial, advantage in a more tightly controlled resource model (such as query complexity). The design of new, optimal quantum algorithms, and the quantum solution of hard classical problems, are thus of paramount importance. At the same time, we need to understand the inherent limitations of the quantum computational model. To achieve that, we propose a three-pronged strategy within this work package. First, we will investigate the potential of quantum walks for the development of new quantum algorithms, an area in which the consortium has demonstrated already great expertise. Second, we will explore entirely new approaches for designing new quantum algorithms. Third, we will explore the structural properties of quantum algorithms. Our goal is a deeper understanding of the frontier between classical and quantum computation. For instance, we will try to characterize the power of quantum computation with highly mixed states. We will also pursue mixed computational models which distinguish classical and quantum resources and study classical algorithms to simulate certain quantum evolutions, thus showing that some classes of quantum algorithms or quantum physical systems cannot be used to exploit any quantum advantage. 2. Algorithmic issues in quantum communication. At the heart of many results in quantum communication is quantum entanglement – non-classical correlations between two spatially separated quantum systems. Sharing entanglement allows remote parties to realize non-local correlations that are impossible to obtain classically, without imparting them with the ability to communicate instantaneously. Our first objective is to study non-local quantum games as a means to deepen our understanding of quantum entanglement. We would like to characterize the amount of entanglement required to play a non-local game optimally and find an algorithm to calculate, or even to approximate, the entangled value of non-local games. Our second objective is to study the connections between non-local games and interactive proofs. Interactive proofs are a classical concept that has recently found many applications in theoretical computer science (e.g. the PCP theorem, which implies that many problems are hard to approximate for classical computers). Our third objective is to use quantum games and other methods, to study the quantum version of another important computer science model, communication complexity. Communication complexity studies efficient communication protocols and has found many applications in computer science including data structures, automata, data streams, boolean circuits, VLSI design. Our fourth objective is to study the applications of quantum non-locality to cryptography. More specifically, we will study cryptographic algorithms whose security is based only on the existence of non-local correlations. Such algorithms may be able to achieve security even when the cryptographic devices that they use are produced by an untrusted party. 3. Over the past few decades, classical computer science has developed a flexible set of tools that allow us to work with randomness in all sorts of ways: to efficiently convert “rough” forms of randomness into more useful forms, to protect information against noise, against adversaries, etc. These tools have many applications in classical algorithms, complexity theory, information theory, and cryptography. We will work on analogues of these tools for quantum information and their applications, in particular to quantum cryptography. Apart from using quantum information tools for quantum purposes, one can also use them for classical purposes. We aim to extend and systematize the current list of applications of quantum information to other areas. Such applications show the usefulness of quantum information science beyond its own borders. Thus the study of quantum information can be useful even in the absence of an actual large-scale quantum computer.