Ein Vergleich von Varianten endlicher Quantenautomaten – Eine algorithmenorientierte Analyse. Sigg, S. VDM Verlag, 2008.
abstract   bibtex   
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.
@Book{ 4016,
	title = "Ein Vergleich von Varianten endlicher Quantenautomaten -- Eine algorithmenorientierte Analyse",
	author = "Stephan Sigg",
	publisher = "VDM Verlag",
	year = "2008",
	isbn = "978-3-639-03375-5",
	abstract = {Quantencomputer, die mit einer gr{\"o}sseren Anzahl Qubits rechnen, k{\"o}nnen heute praktisch nicht realisiert werden. Es ist zu erwarten, dass erste Quantencomputer zun{\"a}chst nur auf wenige Qubits bei Bedarf zugreifen. Wir untersuchen daher ein einfaches Rechnermodell, das wir mit den Gesetzm{\"a}ssigkeiten der Quantentheorie beschreiben k{\"o}nnen: Das Modell eines endlichen Quantenautomaten. Quantenautomaten, die ihren Kopf in zwei Richtungen bewegen k{\"o}nnen (2-QFAs) erkennen mehr Sprachen, als alle klassischen Automaten, 1-QFAs erkennen hingegen nur eine echte Teilmenge der regul{\"a}ren Sprachen. Allerdings ben{\"o}tigen 2-QFAs abh{\"a}ngig von der Wortl{\"a}nge unterschiedlich viele Qubits. Durch Modifikationen kann die M{\"a}chtigkeit des 1-QFAs erh{\"o}ht werden. Wir untersuchen Modifikationen von 1-QFAs und greifen weitere in der Literatur vorgeschlagene Aspekte auf, wodurch wir gr{\"o}ssere Freiheiten bei der Konstruktion erhalten. Wir stellen Sprachen vor, die von diesen Automaten erkannt werden k{\"o}nnen und geben, wenn m{\"o}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{\"o}tigt.},
group = {ambience}}
Downloads: 0