Academic Centre
Our project consists of 4 scientific workpackages:
WP1 “New Ideas for Quantum Algorithms”
In order to identify new problems where quantum computers could be useful, it seems of particular importance to develop new tools for designing quantum algorithms. In this aspect, the groups involved in this proposal have been at the forefront of the development of techniques which have recently led to new quantum algorithms. In particular, we have been the leaders in the development of different quantum walk based search algorithms, as well as a very recent quantum computing model which we called learning graphs.
The general objective of this work package will be to exploit the full potential of these techniques to design new quantum algorithms. In particular, we will formalize the connection between quantum walks and learning graphs, in order to facilitate their application. We will then use these techniques to solve different computational problems, in particular problems of algebraic and combinatorial nature. Another objective of this workpackage will be to design new quantum algorithms for property testing.
WP2 “General properties of quantum algorithms”
While the development of new quantum algorithms is an important pursuit, it is also of great fundamental interest to identify and study, in more generic terms, the essential novel features of quantum physics that are responsible for various kinds of supra-classical computational benefits.
In addition to the purely pragmatic goal of assisting the discovery of new algorithmic techniques, this kind of investigation has potentially very deep and long term significance in providing a fertile novel perspective on fundamental physics itself. In this work package, we will study the following fundamental aspects of the quantum computational model. First, we will explore the role of entanglement and resources beyond entanglement in quantum computing.
Second, we will investigate the role of structure in quantum computational speed-up. Finally, we will develop new quantum lower bound techniques in order to better understand the inherent limitations of the model. WP3 “Algorithms in Quantum Communication” In the last two decades, there has been unprecedented growth in the area of communication systems and networks. Distributed computational tasks now encompass many of the activities occurring in today's computer and communications world. In this workpackage, we will study the power and limitations of quantum algorithms for solving problems that involve several parties communicating over a quantum network. Our first goal is to design quantum protocols for distributed communication tasks that are more efficient (use less communication) than any classical protocol. We will work on efficient quantum protocols in two different settings:
• Communication complexity setting where the task is to carry out a
computation on input data that are distributed among two or more parties, which follow a given protocol;
• Distributed computing setting where the task is to coordinate actions
between a number of parties, some of which can be faulty or malicious (and not following the protocol).
We will also investigate the methods for proving lower bounds on the amount of communication that is necessary for quantum protocols to solve a given problem. Our second goal is to investigate the growing connections between quantum communication and quantum non-locality. We are particularly interested in how the communication complexity of a task characterises the robustness of the corresponding Bell inequality. Our third goal is to study quantum agents in a game-theoretic setting, with each agent is acting to maximize their own benefit. We are particularly interested in mechanisms to impose an honest behaviour on quantum agents in a network. WP4 “Quantum information in computer science and physical systems” While the first three workpackages aim to further the state of the art within the area of quantum computing proper, this fourth workpackage aims at applying the many tools and techniques that have been built up here to other areas, specifically to questions in classical computer science and the study of physical systems. First, there is a growing list of applications of tools from quantum information theory in classical computer science, including breakthrough results about locally decodable error-correcting codes and the extension complexity of the Travelling Salesman Problem. We want to find more such applications. Second, quantum information allows a fresh, more rigorous and more algorithmic perspective on many problems in physics. Specifically we want to study the quantum and classical complexity of systems of (partially interacting) fermions, and the problem of finding ground states of Hamiltonians that are constrained in certain ways.
In addition to the purely pragmatic goal of assisting the discovery of new algorithmic techniques, this kind of investigation has potentially very deep and long term significance in providing a fertile novel perspective on fundamental physics itself. In this work package, we will study the following fundamental aspects of the quantum computational model. First, we will explore the role of entanglement and resources beyond entanglement in quantum computing.
Second, we will investigate the role of structure in quantum computational speed-up. Finally, we will develop new quantum lower bound techniques in order to better understand the inherent limitations of the model. WP3 “Algorithms in Quantum Communication” In the last two decades, there has been unprecedented growth in the area of communication systems and networks. Distributed computational tasks now encompass many of the activities occurring in today's computer and communications world. In this workpackage, we will study the power and limitations of quantum algorithms for solving problems that involve several parties communicating over a quantum network. Our first goal is to design quantum protocols for distributed communication tasks that are more efficient (use less communication) than any classical protocol. We will work on efficient quantum protocols in two different settings:
• Communication complexity setting where the task is to carry out a
computation on input data that are distributed among two or more parties, which follow a given protocol;
• Distributed computing setting where the task is to coordinate actions
between a number of parties, some of which can be faulty or malicious (and not following the protocol).
We will also investigate the methods for proving lower bounds on the amount of communication that is necessary for quantum protocols to solve a given problem. Our second goal is to investigate the growing connections between quantum communication and quantum non-locality. We are particularly interested in how the communication complexity of a task characterises the robustness of the corresponding Bell inequality. Our third goal is to study quantum agents in a game-theoretic setting, with each agent is acting to maximize their own benefit. We are particularly interested in mechanisms to impose an honest behaviour on quantum agents in a network. WP4 “Quantum information in computer science and physical systems” While the first three workpackages aim to further the state of the art within the area of quantum computing proper, this fourth workpackage aims at applying the many tools and techniques that have been built up here to other areas, specifically to questions in classical computer science and the study of physical systems. First, there is a growing list of applications of tools from quantum information theory in classical computer science, including breakthrough results about locally decodable error-correcting codes and the extension complexity of the Travelling Salesman Problem. We want to find more such applications. Second, quantum information allows a fresh, more rigorous and more algorithmic perspective on many problems in physics. Specifically we want to study the quantum and classical complexity of systems of (partially interacting) fermions, and the problem of finding ground states of Hamiltonians that are constrained in certain ways.