What are the difficult problems for a quantum computer?

by Prof. Antonello Scardicchio (Research Scientist,Condensed Matter and Statistical Physics, Abdus Salam ICTP)

Tuesday 19 Oct 2010, 16:00 → 18:00 Europe/Rome

Aula Conversi (Dip. di Fisica - Edificio G. Marconi)

As the efforts for building a quantum computer continue, the question of what problems it can solve efficiently and what will instead be fundamentally difficult arises. These considerations can be used to define a notion of quantum glassiness, or fundamentally slow quantum dynamics, which are independent of the analogous classical notions. As an example, I will consider an ensemble of decision problems (called QSAT) which are difficult for a quantum computer, in their worst case, and show that the ensemble parameters can be tuned to generate problems of a different degree of difficulty.