Ein Vergleich von Varianten endlicher Quantenautomaten

Quantencomputer, die mit einer größeren Anzahl Qubits rechnen, können heute praktisch nicht realisiert werden. Es ist zu erwarten, dass erste Quantencomputer zunächst nur auf wenige Qubits bei Bedarf zugreifen. Wir untersuchen daher ein einfaches Rechnermodell, das wir mit den Gesetzmäßigkeiten der Quantentheorie beschreiben können: Das Modell eines endlichen Quantenautomaten. Quantenautomaten, die ihren Kopf in zwei Richtungen bewegen können (2-QFAs) erkennen mehr Sprachen, als alle klassischen Automaten, 1-QFAs erkennen hingegen nur eine echte Teilmenge der regulären Sprachen. Allerdings benötigen 2-QFAs abhängig von der Wortlänge unterschiedlich viele Qubits. Durch Modifikationen kann die Mächtigkeit des 1-QFAs erhöht werden. Wir untersuchen Modifikationen von 1-QFAs und greifen weitere in der Literatur vorgeschlagene Aspekte auf, wodurch wir größere Freiheiten bei der Konstruktion erhalten. Wir stellen Sprachen vor, die von diesen Automaten erkannt werden können und geben, wenn möglich, die Menge der erkannten Sprachen an. Dabei versuchen wir ein Modell zu finden, das mehr Sprachen erkennen kann als alle klassischen Automaten, das jedoch nur konstant viele Qubits benötigt.

Stephan Sigg hat seine Dissertation an der Uni Kassel mit Auszeichnung beendet und ist seit 2008 in der Gruppe verteilte und ubiquitäre Systeme der TU-BS. Seine Interessen umfassen den Entwurf effizienter Algorithmen, kollaboratives Senden in Sensornetzen, Verfahren zur UMTS-Lastoptimierung und die Analyse evolutionärer, mehrkriterieller Verfahren.