Bestimmung unterer Schranken für Quanten- und klassische Algorithmen
| Talking persons: |
| Dirk Winkler |
| Abstract: |
| Im Zuge der Betrachtung von Quantenalgorithmen stellt sich die Frage, welche Verbesserungen gegenüber klassischen (nicht quantenbasierten) Ansätzen erreichbar sind und wo die Grenzen liegen. Zu diesem Zweck wurde in den vergangenen Jahren erforscht, wie man untere Schranken für die Abfragekomplexität solcher Systeme in Bezug auf gegebene Problemstellungen nachweist. Dies führte zur Quantum-Adversary-Methode, welche die Abweichung zweier Rechenwege mit unterschiedlichem Ausgang analysiert. Die Idee wird im Rahmen der Relational-Adversary-Methode aufgegriffen und an klassische Verfahren angepasst: Man untersucht die Menge an Information, die ein randomisierter Algorithmus nach einer bestimmten Anzahl T an Abfragen einzelner Bits der Eingabe besitzt, und zeigt, dass er nur dann mit hoher Wahrscheinlichkeit korrekt antworten kann, wenn T eine Mindestgröße erreicht hat. Thema des Vortrags ist, welche Ideen und Konzepte den beiden Methoden zugrunde liegen und welche unteren Schranken sich aus ihnen ergeben. |
| Times: |
| Tuesday 8th November 2005, 3.30 pm - 5.00 pm, room 1/208A |
