VDM Sigg, S: Ein Vergleich von Varianten endlicher Quantenautoma

Quantencomputer, die mit einer grösseren 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ässigkeiten 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össere 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. ...