Komplexität und Entropie

Sascha Delitzscher  (TU Berlin)
Saturday, October 13, 2007
Ein zentrales Ergebnis der Komplexitätstheorie ist ein Theorem, das von A.A. Brudno 1983 zuerst bewiesen wurde. Es besagt, dass die Entropierate eines ergodischen Prozesses fast sicher gleich der Kolmogorov Komplexität pro Symbol seiner Trajektorien ist.
Betrachtet man einen aus zwei Systemen zusammengesetzten ergodischen Prozess, so lässt sich diese Aussage auf die zugehörigen bedingten Größen erweitern.
Der Vortrag stellt die beiden Theoreme vor und zeigt Wege auf, diese zu verallgemeinern: Es wird eine leicht modifizierte Version der bedingten Kolmogorov Komplexität vorgestellt. Bei dieser hat die unterliegende Rechenmaschine die Möglichkeit aus einer gegebenen Menge von Daten die zur Berechnung eines Objektes passendsten auszuwählen.
Desweiteren wird der Begriff der Komplexität eines klassischen Ensembles, d.h. eines klassischen physikalischen Systems in einer unbekannten Konfiguration, eingeführt. Dabei wird eine Variante, Ensembles als Ausgaben von Turing Maschinen zu 'berechnen', diskutiert und eine Formel zur Berechnung der Komplexität angegeben.

Exponential families and linear codes

Thomas Kahle  (MPI MiS, Leipzig)
Friday, October 12, 2007
In this talk we establish a connection between exponential families of k-interactions, 0/1 polytopes and linear codes. We will see how we can map exponential families in a "face"-preserving way, and study a nice convex polytope instead of the closure of a twisted exponential family. Furthermore the coordinates of vertices of this polytopes turn out to form a so called linear code, which is a subspace of the finite vector space .

Quanten-Sanov-Theorem im mehrdimensionalen Fall

Guido Montúfar  (TU Berlin)
Saturday, October 13, 2007

Um das Resultat [Bjelakovic et. al. 2007] auf mehrdimensionale Gittersysteme zu erweitern, wird ein analoger Beweis vorgeschlagen. Die dort eingeführte HP-Bedingung ist im mehrdimensionalen Fall auch equivalent zum Quanten-Sanov-Theorem. Um dieses zu zeigen muss insbesondere die Existenz von universelltypischen Projektoren in dem mehrdimensionalen Fall gezeigt werden.

Equiquantisierung von Signalen

Ruedi Seiler  (TU Berlin)
Saturday, October 13, 2007
Die Quantisierung von Signalen hat eine weit ber 100 Jahre alte Geschichte. Eine vollstndige Herleitung der zentralen Formel gelang erst krzlich. Sie stammt von Volker Bach.

Quantum broadcasting problem in low-power signal processing

Bastian Steudel  (MPI MiS, Leipzig)
Friday, October 12, 2007
We assume that discussions on fundamental bounds in classical low-power computing require a quantum theoretical description and that further some kind of synchronization through a 'timing signal' is needed during the computation process. More explicitly, since any closed quantum system with non-trivial evolution contains some information about the time at which it has been initialized, it can be viewed as a 'quantum clock'. We quantify the timing information that it contains using Holevo-Information and discuss limitations that occur if one wants to broadcast this information as well as thermodynamic implications of these limitations. Mainly this is work by Dominik Janzing to which I contributed through my master thesis.

Asymptotic error rates in quantum hypothesis testing

Arleta Szkoła  (MPI MiS Leipzig)
Saturday, October 13, 2007
We give an overview of some recent results in quantum hypothesis testing mostly presented in [1]. Using both a new trace inequality for pairs of density operators due to Audenaert et al. [2] and a special mapping from pairs of density operators to pairs of probability distributions [3] we derive quantum extensions of the Chernoff distance and the Hoeffding bound. As a byproduct we demonstrate how one part of the quantum Stein's Lemma -the achievability of the quantum relative entropy as the best rate of the probability of error of the type-II- arises from these quantities. Moreover, we discuss the properties of the quantum Chernoff distance as a distance measure on the quantum state space of finite-dimensional complex Hilbert spaces.
[1] K.M.R. Audenaert, M. Nussbaum, A. Szkola, F. Verstraete, "Asymptotic Error Rates in Quantum Hypothesis Testing", Preprint No. 84/2007, MPG MiS Leipzig
[2] K.M.R. Audenaert, J. Calsamiglia, R. Munoz-Tapia, E. bagan, Li. masanes, A. Acin and F. Verstraete, " Discriminating States: The Quantum Chernoff Bound" , quant-ph/0607216
[3] M. Nussbaum, A. Szkola, "The Chernoff lower bound in quantum hypothesis testing", Preprint No. 69/2006, MPG MiS Leipzig