Information is physical: it is something that must be encoded in the state
of a physical system. Therefore also the process of computation is 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
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 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 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
errors that rise from local interactions. The main idea is to encode the
qubits in topological properties of physical system 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 mutuated from
statistical and conformal field theories.