Studienarbeit aus dem Jahr 2003 im Fachbereich Informatik - Theoretische Informatik, Note: 1,0, Ludwig-Maximilians-Universit t M nchen (Institut f r Informatik), Veranstaltung: Hauptseminar Quantencomputer, Sprache: Deutsch, Abstract: Im Jahr 1936 ver ffentlichten Church und Turing ihre ber hmte Church-Turing-Hypothese. Sie gilt als einer der Grundpfeiler der Berechenbarkeits- und Komplexit tstheorie, die in den vergangenen Jahrzehnten eine beachtliche Entwicklung vollzogen haben. Bis vor kurzem beschr nkte man sich in der Forschung in erster Linie auf die klassischen, abstrahierten Prinzipien der Informationstheorie und schenkte der physikalischen Natur von Information weniger Beachtung. Erst in den letzten Jahren kam der Gedanke auf, auch quantenmechanische Ph nomene bei der Konstruktion von Computern auszunutzen. Einer der Vorreiter auf diesem Gebiet ist David Deutsch 1], der bei seinem Versuch, die Church-Turing-Hypothese zu beweisen, als erster (Quanten-)Physik als Grundlage benutzte. Dabei stellte er fest, dass die klassische Komplexit tstheorie nicht ohne weiteres mit der (physikalischen) Realit t vereinbar ist. Sie bedurfte einer Erweiterung. Die daraus entstandene Quantenkomplexit tstheorie setzt sich zum Ziel, eine weitgreifendere Definition von "Komplexit t" und "Wissen" in einem physikalischem System zu geben. Dabei mu nicht zuletzt auch die Church-Turing-Hypothese erweitert und pr zisiert werden. Auf dieser Grundlage ist es letztendlich m glich, eine universelle Quanten-Turing-Maschine zu konstruieren. Im ersten Teil dieser Arbeit werde ich die Ideen von David Deutsch skizzieren und mich dann im zweiten Teil der Quantenturingmaschine (QTM) widmen, die im letzten Kapitel zu einer universellen Quantenturingmaschine ausgebaut werden soll.