Quantum Computation

Information is physical. It is something that must be encoded in the state of a physical system. Therefore, the process of computation is also a task that has to be performed with a physical device. Since the physical world is fundamentally quantum mechanical, the foundations of information theory and computer science can be analyzed under the point of view of quantum mechanics.

In fact, quantum information (information stored in qubits described by linear superpositions of quantum states) has peculiar properties that contrast sharply with the familiar properties of “classical” information. And a quantum computer — a new type of machine that exploits these quantum properties — should be capable of performing tasks that would be very difficult (if not impossible) with digital computers, such as finding the prime factors of large numbers, searching large databases, and simulating quantum systems.

Much interest has naturally been focused on algorithms that outperform their classical counterparts. However, the development of a complexity theory for quantum computers suggests that we already know problems (those shown to be QMA-complete) whose worst case solutions will take even for quantum computers a time exponential in the problem size. These appropriately generalize to quantum computers the class of NP-complete problems: those which are easy to check but (believed to be) hard to solve on classical computers.

Moreover, the study of the typical complexity of QMA-complete problems shows interesting links with the statistical mechanics of disordered quantum system and this analogy is one of the research topics currently active in our group.

The potential power of quantum computers motivates the intense effort currently in progress to understand and — eventually — build them. However, enormous scientific and engineering challenges must be overcome for scalable and universal quantum computers to be realized. The main problems are represented by the interactions of the quantum system storing the information with the outside world: these interactions, usually of thermal origin, are capable of destroying the quantum phases that are essential to encode qubits.

Topological quantum computation is one of the best proposal to overcome these errors arising from local interactions. The main idea is to encode the qubits in topological properties of physical systems such as fractional quantum Hall fluids or ultracold atoms. Exploiting the exotic braiding statistics of certain quasiparticle excitations of these systems, called anyons, it is possible to build qubits that are robust to all kinds of local errors. The study of the main features of these anyonic excitations, which is one of our research activities, can be achieved using techniques borrowed from statistical and conformal field theories.