Vorlesung Quantenalgorithmen vom 10.12.02

Themen

• Das Simon Problem als promise problem: Gegeben ist eine black-box Funktion f, die einen verborgenen String s besitzt.
• Ein polynomialer Quantenalgorithmus für das Simon Problem:
  • Die Hadamard-Transformation
  • Zustände der Form |x>+|x+s> für festes s und zufällig (gleichverteilt) gezogenes x.
  • Bestimmung des Hadamard-Spektrums solcher Zustände.
  • Rekonstruktion aus Vektoren, die orthogonal zum verborgenen String s sind durch Lösen eines linearen Gleichungssystems.
• Untere Schranke für probabilistische Algorithmen für das Simon Problem
  • Untersuchung eines optimalen klassischen Algorithmus, untere Schranke von 2^(n/2) für dessen Laufzeit.
  • Allgemeine Methode für untere Schranken für probabilistische Algorithmen: Yao's MinMax Prinzip (vgl. Literatur).
  • Korollar: Trennung der Komplexitätsklassen BPP und BQP durch Orakel, d.h. es gibt black-box Probleme, die ein Quantencomputer in polynomialer Zeit lösen kann, während ein klassischer Rechner exponentielle Zeit benötigt.

Literatur zur Vorlesung

Das Simon Problem:

• D. Simon, On the power of quantum computation, In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS'94), pp. 124-134, 1994.
• G. Brassard, P. Hoyer, On the power of exact quantum polynomial time, quant-ph/9612017.
• Section 3.1.3, pp. 109-111 in: Josef Gruska, Quantum Computing, MacGraw-Hill, 1999.

Das MinMax Prinzip/Untere Schranken für probabilistische Algorithmen:

• Section 2.2, pp. 31-35 in: Rajeev Motwani und Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.