|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
In computer science, it is commonplace to study both what computers can do and what they cannot do. We show an upper bound by exhibiting an algorithm that solves a given computational problem within given resources. In contrast, a lower bound states that no matter how ingenious we may be, we cannot find an algorithm that solves a given computational problem within certain resources, since no such algorithm exists. Lower bounds provide a way of quantifying the intrinsic difficulty of a problem that is independent on any particular approach to solve it. In this talk, we give two methods for proving lower bounds on quantum computations. Both methods are developed in the so-called adversarial model and based on information-theoretic arguments. Our first method generalizes and strengthens past lower bound methods. Our second method allows to show exact lower bounds. Our second method yields in particular a very elementary proof that Grovers algorithm is not only asymptotically optimal, but exactly optimal. Grovers algorithm is one of the most important quantum algorithms ever developed and is used in all areas of quantum information processing, including quantum random walks, quantum communication complexity, quantum learning theory and quantum zero-knowledge. This talk is based on joint work with Catalin Dohotaru, Troy Lee, and Robert Spalek, and assumes no prior knowledge of quantum computing. Host: Lene Favrholdt SDU HOME | IMADA HOME | Previous Page Daniel Merkle |