Diese Dissertation beschäftigt sich mit der Frage, wie viel Rechenkraft Quantencomputer bieten können. Diese Frage geht in ihrer allgemeinsten Form weit über die aktuellen Möglichkeiten und Methoden der Komplexitätstheorie hinaus. Dennoch liefert die Komplexitätstheorie Beispiele von Problemen, die sogar für Quantencomputer als nicht effizient lösbar gelten. Andererseits können Quantencomputer vermutlich nicht effizient von klassischen Computern simuliert werden. Wir wollen mit dieser Arbeit zum Verständnis des dazwischen liegenden Bereichs von Problemen, die effizient auf Quantencomputern, aber nicht effizient auf klassischen Computern berechnet werden können, beitragen. Um besseren Einblick in die Fragestellung zu erlagen, entwickeln wir in dieser Dissertation klassische und quantenmechanische Algorithmen zur Lösung von Problemen, die unter einschränkenden Annahmen a priori als nicht effizient lösbar geltende Probleme dennoch effizient lösen. Wir erforschen in diesem Sinne also die Grenzen des auf Quantencomputern und klassischen Computern Machbaren, in dem wir Annahmen identifizieren, die dazu geeignet sind grundsätzlich als schwer geltende Probleme in den Bereich des Machbaren zu bringen. Im Speziellen entwickeln wir einen Quantenalgorithmus, der sogenannte Projective Entangled-Pair States (PEPS) effizient herstellen kann, sobald Injektivität und Wohlkonditierung des PEPS gegeben ist. In einem zweiten Schritt erweitern wir diesen Algorithmus auf sogenannte G-injektive PEPS, einer wesentlich allgemeineren Klasse von Quantenzuständen, die auch die exotische Eigenschaft der topologischen Ordnung besitzen können. Weiters entwickeln wir einen Quantenalgorithmus, der das im Allgemeinen für Quantencomputer als schwer geltende Problem den Grundzustand von lokalen Hamiltonoperatoren zu erzeugen löst, sofern diese die Voraussetzungen des (nicht-konstruktiven) Quanten-Lovász-Local-Lemma erfüllen und die Operatoren kommutieren. Unser Quantenalgorithmus kann in diesem Fall auch als unabhängiger, konstruktiver Beweis des Quanten-Lovász-Local-Lemmas betrachtet werden. Um die Grenze zu klassischen Computern zu erforschen, entwickeln wir einen klassischen Algorithmus, der das sehr allgemeine Problem Quantenschaltkreise zu simulieren unter gewissen Annahmen effizient lösen kann. Wäre es in voller Allgemeinheit lösbar, würden Quantencomputer keinen Vorteil bieten. Unser Algorithmus kann Quantenschaltkreise simulieren, die in ihrer Struktur jener des Quantenalgorithmus von Shor zur Faktorisierung ganzer Zahlen, der als exponentiell schneller als der schnellste bekannte klassische Faktorisierungsalgorithmus gilt, sehr ähnlich sind. Weiters treffen wir die Annahme, dass die erzeugte Wahrscheinlichkeitsverteilung annähernd dünn-besetzt ist. Unser Ergebnis impliziert daher, dass die von Algorithmen dieser Struktur erzeugte Wahrscheinlichkeitsverteilung notwendigerweise dicht-besetzt sein muss, um einen exponentiellen Geschwindigkeitsvorteil erzielen zu können.
Diese Dissertation beschäftigt sich mit der Frage, wie viel Rechenkraft Quantencomputer bieten können. Diese Frage geht in ihrer allgemeinsten Form weit über die aktuellen Möglichkeiten und Methoden der Komplexitätstheorie hinaus. Dennoch liefert die Komplexitätstheorie Beispiele von Problemen, die sogar für Quantencomputer als nicht effizient lösbar gelten. Andererseits können Quantencomputer vermutlich nicht effizient von klassischen Computern simuliert werden. Wir wollen mit dieser Arbeit zum Verständnis des dazwischen liegenden Bereichs von Problemen, die effizient auf Quantencomputern, aber nicht effizient auf klassischen Computern berechnet werden können, beitragen. Um besseren Einblick in die Fragestellung zu erlagen, entwickeln wir in dieser Dissertation klassische und quantenmechanische Algorithmen zur Lösung von Problemen, die unter einschränkenden Annahmen a priori als nicht effizient lösbar geltende Probleme dennoch effizient lösen. Wir erforschen in diesem Sinne also die Grenzen des auf Quantencomputern und klassischen Computern Machbaren, in dem wir Annahmen identifizieren, die dazu geeignet sind grundsätzlich als schwer geltende Probleme in den Bereich des Machbaren zu bringen. Im Speziellen entwickeln wir einen Quantenalgorithmus, der sogenannte Projective Entangled-Pair States (PEPS) effizient herstellen kann, sobald Injektivität und Wohlkonditierung des PEPS gegeben ist. In einem zweiten Schritt erweitern wir diesen Algorithmus auf sogenannte G-injektive PEPS, einer wesentlich allgemeineren Klasse von Quantenzuständen, die auch die exotische Eigenschaft der topologischen Ordnung besitzen können. Weiters entwickeln wir einen Quantenalgorithmus, der das im Allgemeinen für Quantencomputer als schwer geltende Problem den Grundzustand von lokalen Hamiltonoperatoren zu erzeugen löst, sofern diese die Voraussetzungen des (nicht-konstruktiven) Quanten-Lovász-Local-Lemma erfüllen und die Operatoren kommutieren. Unser Quantenalgorithmus kann in diesem Fall auch als unabhängiger, konstruktiver Beweis des Quanten-Lovász-Local-Lemmas betrachtet werden. Um die Grenze zu klassischen Computern zu erforschen, entwickeln wir einen klassischen Algorithmus, der das sehr allgemeine Problem Quantenschaltkreise zu simulieren unter gewissen Annahmen effizient lösen kann. Wäre es in voller Allgemeinheit lösbar, würden Quantencomputer keinen Vorteil bieten. Unser Algorithmus kann Quantenschaltkreise simulieren, die in ihrer Struktur jener des Quantenalgorithmus von Shor zur Faktorisierung ganzer Zahlen, der als exponentiell schneller als der schnellste bekannte klassische Faktorisierungsalgorithmus gilt, sehr ähnlich sind. Weiters treffen wir die Annahme, dass die erzeugte Wahrscheinlichkeitsverteilung annähernd dünn-besetzt ist. Unser Ergebnis impliziert daher, dass die von Algorithmen dieser Struktur erzeugte Wahrscheinlichkeitsverteilung notwendigerweise dicht-besetzt sein muss, um einen exponentiellen Geschwindigkeitsvorteil erzielen zu können.
Quantencomputer besitzen das Potenzial, um in naher Zukunft Probleme, die mit herkömmlichen Computern und Supercomputern nicht bewältigbar sind, zu lösen. Bisher ist die Umsetzung dieser Technologie in der Industrie noch in der Anfangsphase, wodurch der Einsatz von Quantencomputern bisher nur für Forschungsprojekte möglich ist. Dennoch ermöglichen es große IT-Unternehmen, interessierten Personen einen indirekten Zugang zu Quantencomputern über deren Services. Da die Technologien und Konzepte, auf denen Quantencomputern basieren, sehr umfangreich und komplex sind, ist es für interessierte Personen, die sich in diese neue Materie vertiefen wollen, oft schwierig, die Hauptkonzepte, die benötigt werden, um Quantencomputern zu verstehen, zu identifizieren und somit ein Grundverständnis von Quantencomputern zu erlangen. Aus diesem Grund besteht der Hauptzweck dieser Arbeit darin, die benötigten Grundkonzepte und Themen auf denen Quantencomputer aufbauen, zu identifizieren und auszuarbeiten. Hierfür werden die Konzepte von bekannten Lehrbüchern im Bereich Quantencomputer herangezogen und systematisch nach deren Wichtigkeit für das Verständnis von Quantencomputern gegliedert, aufgelistet und ausgearbeitet. Für den praktischen Teil der Arbeit werden zwei Quantenbeispiele anhand des zuvor erarbeiteten Wissens beschrieben und erweitert. Die zuvor identifizierten und beschriebenen Grundkonzepte werden anschließend grafisch mittels einer Concept-Map dargestellt, diese bietet einen systematischen Überblick über die einzelnen Konzepte und deren Abhängigkeiten zueinander. Der Vorteil in der Darstellung von Wissen mittels einer Concept-Map besteht darin, dass die Visualisierung der Verbindungen zwischen den einzelnen Konzepten hervorgehoben wird. Zusätzlich wird auf Basis des erarbeiteten Wissens ein Beispiel-Curriculum für eine Lehrveranstaltung, die das Ziel hat, die Grundkonzepte von Quantencomputern zu vermitteln, erstellt. Das Ergebnis dieser Arbeit zeigt, dass die Konzepte, auf denen Quantencomputer aufbauen, in drei Grundkompetenzen unterteilt werden können. Zum einen die Kompetenz der linearen Algebra, in dem die meisten Konzepte und Themen bereits in einem vorangegangenen Studium behandelt wurden. Zum anderen die der Informatik-Konzepte, wobei hier wie bei der linearen Algebra das Verständnis im Bereich der Programmierung angenommen werden kann. Die Kompetenz der Quantenmechanik stützt sich auf die Konzepte, die von Quantencomputern genutzt wird und auf die Kompetenzen und das Wissen der beiden anderen Kompetenzen. Zusammenfassend zeigt diese Arbeit, dass für das reine Verständnis von Quantencomputern und dem Replizieren von bereits erstellten Quantenalgorithmen eine große Anzahl an unterschiedlichen Konzepten benötigt wird. Für die Fähigkeit der Entwicklung von eigenen Quantenalgorithmen reicht das erarbeitet Wissen nicht aus, sondern wird als Grundwissen angesehen.
Diese Bachelorarbeit erläutert die Grundlagen von Quantencomputern und ihr Potential sowie die Vorteile, die eine Auseinandersetzung mit diesem Thema mit sich bringt. Sie richtet sich an Leser ohne Vorwissen auf diesem Gebiet und stellt die Konzepte auf eine Art vor, die für jede Person mit einem Grundwissen im Softwarebereich zugänglich ist. Es werden dabei die Unterschiede zwischen klassischen Computern und Quantencomputern besprochen, sowie die grundlegende Funktionsweise, wie die Basiseinheiten (Qubits) und die Gatter, die auf diese angewendet werden. Um diese Grundbausteine und Funktionsweise zu veranschaulichen sowie die Potentiale von Quantencomputern nachzuvollziehen, werden drei Algorithmen näher besprochen. Der Deutsch-Algorithmus zeigt, dass Quantencomputer manche Probleme schneller als klassische Computer lösen können. Der Shor-Algorithmus kann RSA verschlüsselte Nachrichten schnell entschlüsseln. Der Grover-Algorithmus bietet eine schnelle Methode eine bestimmte Information in unsortierten Daten zu suchen. Die drei Algorithmen decken bereits ein recht breites Spektrum von Anwendungsmöglichkeiten von Quantencomputern ab. Dieses Potential sowie die Wichtigkeit der Auseinandersetzung mit der Mächtigkeit von Quantencomputern und ein kurzer Einblick in mögliche zukünftige Entwicklungen schießen die Arbeit ab. Diese Bachelorarbeit erläutert die Grundlagen von Quantencomputern und ihr Potential sowie die Vorteile, die eine Auseinandersetzung mit diesem Thema mit sich bringt. Sie richtet sich an Leser ohne Vorwissen auf diesem Gebiet und stellt die Konzepte auf eine Art vor, die für jede Person mit einem Grundwissen im Softwarebereich zugänglich ist. Es werden dabei die Unterschiede zwischen klassischen Computern und Quantencomputern besprochen, sowie die grundlegende Funktionsweise, wie die Basiseinheiten (Qubits) und die Gatter, die auf diese angewendet werden. Um diese Grundbausteine und Funktionsweise zu veranschaulichen sowie die Potentiale von Quantencomputern nachzuvollziehen, werden drei Algorithmen näher besprochen. Der Deutsch-Algorithmus zeigt, dass Quantencomputer manche Probleme schneller als klassische Computer lösen können. Der Shor-Algorithmus kann RSA verschlüsselte Nachrichten schnell entschlüsseln. Der Grover-Algorithmus bietet eine schnelle Methode eine bestimmte Information in unsortierten Daten zu suchen. Die drei Algorithmen decken bereits ein recht breites Spektrum von Anwendungsmöglichkeiten von Quantencomputern ab. Dieses Potential sowie die Wichtigkeit der Auseinandersetzung mit der Mächtigkeit von Quantencomputern und ein kurzer Einblick in mögliche zukünftige Entwicklungen schießen die Arbeit ab. Diese Bachelorarbeit erläutert die Grundlagen von Quantencomputern und ihr Potential sowie die Vorteile, die eine Auseinandersetzung mit diesem Thema mit sich bringt. Sie richtet sich an Leser ohne Vorwissen auf diesem Gebiet und stellt die Konzepte auf eine Art vor, die für jede Person mit einem Grundwissen im Softwarebereich zugänglich ist. Es werden dabei die Unterschiede zwischen klassischen Computern und Quantencomputern besprochen, sowie die grundlegende Funktionsweise, wie die Basiseinheiten (Qubits) und die Gatter, die auf diese angewendet werden. Um diese Grundbausteine und Funktionsweise zu veranschaulichen sowie die Potentiale von Quantencomputern nachzuvollziehen, werden drei Algorithmen näher besprochen. Der Deutsch-Algorithmus zeigt, dass Quantencomputer manche Probleme schneller als klassische Computer lösen können. Der Shor-Algorithmus kann RSA verschlüsselte Nachrichten schnell entschlüsseln. Der Grover-Algorithmus bietet eine schnelle Methode eine bestimmte Information in unsortierten Daten zu suchen. Die drei Algorithmen decken bereits ein recht breites Spektrum von Anwendungsmöglichkeiten von Quantencomputern ab. Dieses Potential sowie die Wichtigkeit der Auseinandersetzung mit der Mächtigkeit von Quantencomputern und ein kurzer Einblick in mögliche zukünftige Entwicklungen schießen die Arbeit ab. Diese Bachelorarbeit erläutert die Grundlagen von Quantencomputern und ihr Potential sowie die Vorteile, die eine Auseinandersetzung mit diesem Thema mit sich bringt. Sie richtet sich an Leser ohne Vorwissen auf diesem Gebiet und stellt die Konzepte auf eine Art vor, die für jede Person mit einem Grundwissen im Softwarebereich zugänglich ist. Es werden dabei die Unterschiede zwischen klassischen Computern und Quantencomputern besprochen, sowie die grundlegende Funktionsweise, wie die Basiseinheiten (Qubits) und die Gatter, die auf diese angewendet werden. Um diese Grundbausteine und Funktionsweise zu veranschaulichen sowie die Potentiale von Quantencomputern nachzuvollziehen, werden drei Algorithmen näher besprochen. Der Deutsch-Algorithmus zeigt, dass Quantencomputer manche Probleme schneller als klassische Computer lösen können. Der Shor-Algorithmus kann RSA verschlüsselte Nachrichten schnell entschlüsseln. Der Grover-Algorithmus bietet eine schnelle Methode eine bestimmte Information in unsortierten Daten zu suchen. Die drei Algorithmen decken bereits ein recht breites Spektrum von Anwendungsmöglichkeiten von Quantencomputern ab. Dieses Potential sowie die Wichtigkeit der Auseinandersetzung mit der Mächtigkeit von Quantencomputern und ein kurzer Einblick in mögliche zukünftige Entwicklungen schießen die Arbeit ab.
Die Quantenphysik hat unser heutiges Verstandnis der Informationsverarbeitung revolutioniert. Unter Ausnutzung von Quanteneffekten ermoglichen Quantencomputer deutlich schnellere, fur klassische Computern unerreichbare Rechengeschwindigkeiten. Diese Arbeit prasentiert eine Reihe von Experimenten auf dem Gebiet photonischer Quantencomputer, die einerseits technische Fortschritte in der Entwicklung eines skalierbaren Quantencomputers zeigen und andererseits neue, fundamentale Konzepte im Bereich der Quanteninformationsverarbeitung demonstrieren. Alle vorgestellten Experimente beruhen auf der Verwendung von Techniken der linearen Optik und der Anwendung dieser auf durch spontane parametrische Fluoreszenz erzeugte Multi-Photonen Zustande.
Das erste in dieser Arbeit prasentierte Experiment realisiert die angekundigte Erzeugung polarisationsverschrankter Photonenpaare. Bisher war die praktische Einsetzbarkeit von optischen Quantencomputerexperimenten aufgrund der probabilistischen Erzeugungsweise verschrankter Photonenpaare stark limitiert. Das hier vorgestellte Experiment ermoglicht den Nachweis eines verschrankten Zustandes ohne diesen zu messen und uberwindet damit diese begrenzte Anwendbarkeit photonischer Systeme in der Quanteninformationsverarbeitung. Diese angekundigte Erzeugung von verschrankten Zustanden ist daher ein erster Schritt zu auf linearer Optik basierenden Quantennetzwerken und zu skalierbaren photonischen Quantencomputern.
In einem zweiten Experiment wurde das neue Konzept eines blinden Quantencomputers implementiert. Neben den auf Quanteneffekten beruhenden schnelleren Rechnungen, ermoglichen Quantencomputer einen weiteren wesentlichen Vorteil gegenuber klassischen Computern: Sie ermoglichen absolut sichere Rechnungen. Dabei ist es moglich, dass ein Quantencomputer Rechnungen durchfuhrt, aber selbst nicht herausfinden kann, welche es sind. Mit diesem Konzept kann ein nahezu klassischer Nutzer eine Rechnung an einen Quantenserver auslagern, ohne dass dieser die Eingabe, die Ausgabe und die Rechnung kennt. Im Zuge dieser Arbeit wurde die erste experimentelle Umsetzung eines blinden Quantencomputers basierend polarisationsverschrankten Photonen realisiert und blinde Quantenrechnungen, darunter zahlreiche 1- und 2-Qubit Gatter sowie Quantenalgorithmen, demonstriert. Diese Demonstration eines blinden Quantencomputers zeigt, dass unter Ausnutzung von Quanteneffekten absolut sicheres Cloud Computing moglich ist. Aufgrund der naheliegenden Annahme, dass Quantencomputer aufgrund ihrer technischen Komplexitat zunachst nur in wenigen spezialisierten Rechenzentren zur Verfugung stehen konnten und Nutzer von auserhalb mit diesen interagieren, ist dieses Experiment daher ein wichtiger Beitrag fur praktische Anwendungen.
In einem weiteren Experiment wurde dieses Konzept des blinden Quantencomputers auf Fragestellungen im Gebiet der Komplexitatstheorie und der Verifikation angewendet. Dazu wurde eine neue Theorie entwickelt und experimentell demonstriert, mit derer ein nahezu klassischer Nutzer testen kann, ob ein Computer Quantenressourcen hat. Mittels eines blinden Bell Tests kann der Nutzer dabei verifizieren, ob der Quantencomputer Verschrankungsoperationen durchfuhren kann. Diese elementare Methode ist ein erster Schritt zur Verifikation von Quantencomputern und zur Beantwortung der Frage, ob ein klassischer Nutzer Quantenrechnungen uberprufen kann, ohne diese selbst durchfuhren zu konnen.
Verschränkung ist eine faszinierende Eigenart der Quantenphysik, die diese beträchtlich von klassischen Konzepten unterscheidet. Einerseits impliziert Verschränkung überraschende philosophische Aspekte, wie die Unvereinbarkeit von lokal-realistischen Theorien mit der Quantenphysik, andererseits kann sie erfolgreich für Aufgaben der Quanteninformation und Quantenkommunikation verwendet werden, um Protokolle im Hinblick auf klassische Prozeduren zu verbessern. Es ist noch immer ein offenes mathematisches Problem, herauszufinden, ob ein Quantenzustand verschränkt ist oder nicht; für einen allgemeinen Zustand auf einem beliebig dimensionalen Hilbertraum gibt es keine operationelle Vorgangsweise. Für reine Zustände und niedrig dimensionale Zweiteilchen-Systeme, z.B. für zwei Qubits, ist dieses Problem gelöst, da berechenbare notwendige und hinreichende Bedingungen für Separabilität (d.h. für Nicht-Verschränktheit) gefunden wurden. Außerdem kann die Verschränkung für ein Zwei-Qubit-System leicht quantifiziert werden. Für höher dimensionale und/oder Mehrteilchen-Systeme wurde in Bezug auf die Bestimmung und Quantifizierung von Verschränkung schon einiges erreicht, allerdings kann das Problem noch nicht als gelöst angesehen werden, vieles ist noch zu erforschen. In dieser Dissertation werden neue Methoden zur Bestimmung und Quantifizierung von Verschränkung für Systeme, die über Zwei-Qubit-Systeme hinausgehen, präsentiert. Zustände solcher Systeme werden üblicherweise durch Dichteoperatoren beschrieben und in Matrix-Schreibweise verwendet. Für hochdimensionale und/oder Mehrteilchen-Systeme können diese Dichtematrizen allerdings sehr unpraktisch werden. Mit Hilfe von Bloch-Zerlegungen können Dichteoperatoren kompakter und einfacher dargestellt werden. In dieser Schreibweise werden Dichteoperatoren in eine vollständige und orthogonale Operatorenbasis des Operatorenraums zerlegt. Für Qubits ist diese Schreibweise geläufig und üblicherweise werden die Pauli-Spin-1/2 Operatoren für die Operatorenbasis verwendet. Für Qudits, das sind Zustände allgemein dimensionaler Systeme, gibt es allerdings keine eindeutige Verallgemeinerung der Pauli-Operatorenbasis. Daher untersuchen wir drei mögliche Operatorenbasen: Die verallgemeinerte Gell-Mann-Operatorenbasis, die Polarisationsoperatorenbasis, sowie die Weyloperatorenbasis. Weiters wird eine Methode präsentiert, mit welcher die Zerlegung eines beliebigen Operators in eine der drei Operatorenbasen mit Hilfe der Zerlegung von sogenannten Standardoperatoren gefunden werden kann. Als Beispiel zur Anwendung dieser Methode betrachten wir den maximal verschränkten Zwei-Qudit Zustand und zerlegen diesen in jede der Operatorenbasen. Im Zusammenhang mit der Bestimmung von Verschränkung sind „Entanglement Witnesses'“ ein wichtiges und oft verwendetes Hilfsmittel. Diese sind Observablen und detektieren die Verschränkung eines Zustandes, sofern sie für diesen einen negativen Erwartungswert aufweisen, und wenn gleichzeitig bekannt ist, dass der Erwartungswert für alle separablen Zustände nicht negativ werden kann. Diese letztere Bedingung ist allerdings im Allgemeinen nicht leicht zu zeigen. In diesem Zusammenhang bietet sich die Verwendung von Bloch-Zerlegungen für vereinfachte Relationen an, und somit kann die Bedingung in vielen Fällen bewiesen werden. Eine besondere Klasse von Entanglement Witnesses sind geometrische Entanglement Witnesses, welche eine direkte euklidisch-geometrische Darstellung des Operatorenraumes erlauben. Die Wichtigkeit dieser Witnesses wird durch „Shift“-Methoden verdeutlicht, welche verschränkte und im Speziellen „bound entangled“ Zustände detektieren können, und außerdem helfen, die Menge der separablen Zustände von konvexen Untermengen von Zuständen zu bestimmen. Als Beispiel betrachten wir eine Drei-Parameter-Familie von Zwei-Qutrit Zuständen. Weiters können geometrische Entanglement Witnesses auch zur geometrischen Quantifizierung von Verschränkung verwendet werden, insbesondere zur Bestimmung des Hilbert-Schmidt Verschränkungsmaßes. Dies wird an den Beispielen der isotropen Zwei-Qudit Zustände und Zwei-Parameter Familien von Zwei-Qubit und Zwei-Qutrit Zuständen gezeigt. Zuletzt widmen wir uns dem Problem der Bestimmung von Verschränkung in Mehr-Qubit Systemen. In diesem Zusammenhang bieten wir eine allgemeine Konstruktion von Entanglement Witnesses unter Verwendung von statischen Strukturfaktoren an. In der Festkörperphysik beschreiben Strukturfaktoren dynamische Eigenschaften von Festkörpern in Streuexperimenten. Die strukturellen Entanglement Witnesses detektieren echte Mehrteilchen-Verschränkung, wie z.B. Dicke-Zustände und Dicke-ähnliche Zustände mit geänderten Phasen der vorkommenden Terme. Sie beinhalten außerdem nur Zwei-Punkt-Korrelationen und sind für die experimentelle Anwendung in verschieden physikalischen Systemen geeignet.
In den vergangenen Jahren hat das relative neue Feld der Quanteninformationsverarbeitung (QIP) das Interesse vieler Wissenschafter geweckt, da es schnellere Rechenleistung von Computern, absolute sichere Kommunikation sowie ein Potential zum Simulieren von komplexen quantenmechanischen Systemen verspricht. Die Essenz dieser neuen Quanteninformationstechnologie sind zwei Grundkonzepte der Quantenmechanik, nämlich die der Superposition und der Verschränkung. Diese Dissertation enthält die Resultate von vier verschiedenen Experimenten die alle die Demonstration eines neuen Quantencomputer-Models mit linearer Optik, des sogenannten "Einweg-Quantencomputers", zum Ziel hatten. Zu diesem Zweck wurde ein multiphotonen-verschränkter Zustand mit Hilfe des Prozesses der spontanen parametrischen Down-Konversion in einem interferometrischen Setup erzeugt. Dieser verschränkte Zustand agiert als eine Art Ressource, die für Demonstrationen von neuen Quantenalgorithmen und anderen relevanten experimentellen Techniken genutzt wurde. In dieser Dissertation wird über neue Fortschritte in der Theorie und im Experiment berichtet, unter anderem wurde zum ersten Mal eine schnelle, aktive Vorwärtskopplung implementiert, die eine Realisation eines deterministischen Quantencomputer mit einer noch nicht dagewesenen Geschwindigkeit erlaubt. Weiters wurde der sogenannte Deutsch-Algorithmus mit unserem Quantencomputer implementiert. Der Quantenalgorithmus erlaubt es mit nur einer Evaluation zu erkennen, ob eine mathematische Funktion konstant oder balanciert ist, während ein klassischer Algorithmus mindestens 2N−1+1 Evaluationen benötigt. In einem anderen Experiment wurde ein Quantenspiel, das sogenannte Gefangenen-Dilemma, realisiert. Ein solches Spiel ist im Prinzip die Ausführung eines Quantenalgorithmus der aus einer bestimmten Folge aus Ein- und Zwei-qubit Quantengattern aufgebaut ist. Dieses Spiel erlaubt den individuellen Spielern ihren Strategieraum zu vergrößern, da sie auch Superpositionen von klassischen Strategien wählen und diese miteinander verschränken können. Die Erfolgsfunktion des Spieles wurde für verschiedene Strategiesets evaluiert und es konnte experimentell gezeigt werden, dass das sogenannte "Dilemma", welches in der klassischen Version des Spieles auftritt, in der Quantenwelt beseitigt werden kann. Unglücklicherweise ist Dekohärenz, der ungewollte Verlust von in Quantensystemen kodierter Information durch unkontrollierte Wechselwirkung mit der Umgebung, eines der Haupthindernisse für die Realisierung eines Quantencomputers im großen Rahmen. Ein möglicher Lösungsansatz ist die Rechnung in einem sogenannten dekohärenzfreien Unterraum (DFS) durchzuführen. Auf früheren Arbeiten aufbauend gelang es diese theoretischen Konzepte auf unser Einweg-Quantencomputermodel zu übertragen und zum ersten Mal die dekohärenzfreie Durchführung einer Rechnung zu zeigen, während die Photonen starkem Phasenrauschen ausgesetzt waren. Beachtenswerter Schutz der Information konnte erreich werden, der annähernd die idealen Ergebnisse lieferte. Obwohl die Experimente in dieser Dissertation nur einen "proof-of-principle" Charakter aufweisen haben sie trotzdem große Bedeutung für das Feld der QIP und werden hoffentlich den Weg für weitere und aufregende Erfindungen und experimentellen Demonstrationen in der Zukunft ebnen.
In dieser Arbeit werden Algorithmen zur Lösung zahlentheoretischer Probleme für klassische Computer und Quantencomputer entwickelt und analysiert sowie ihre Auswirkungen auf Public-Key-Kryptosysteme untersucht. Im Jahr 1994 veröffentliche Shor einen Quantenalgorithmus [Shor, 1994], der das Periodengitter einer gegebenen Funktion in Quanten-Polynomzeit bestimmt. Mit diesem Algorithmus läßt sich das Faktorisierungs- und das Diskreter-Logarithmus-Problems in endlichen abelschen Gruppen in Quanten-Polynomzeit lösen. Dadurch werden die meisten heutzutage verwendeten Public-Key-Kryptoverfahren unsicher, sollten hinreichend große Quantencomputer eines Tages gebaut werden können. Der erste Quantencomputer wurde 1998 gebaut [Chuang/Vandersypen/Zhou/Leung/Lloyd, 1998]. Er bestand aus zwei Qubits. Der größte Quantencomputer, der bis heute gebaut wurde, besteht aus nur sieben Qubits [Vandersypen/Steffen/Breyta/Yannoni/Sherwood/Chuang, 2001]. Es hat sich herausgestellt, daß das Bauen von großen Quantencomputern ein extrem schwieriges Problem ist. Aus diesem Grund kann davon ausgegangen werden, daß die Größe der Quantencomputer, d.h. die Anzahl der Qubits, aus denen ein Quantencomputer besteht, nur langsam wachsen wird. Deshalb ist es von Interesse, Shors Quantenalgorithmus an verschiedene abelsche Gruppen sowie gruppenähnliche Strukturen zu adaptieren und ihre genaue Komplexität zu untersuchen, um daraus die Bedrohungen für die betroffenen Kryptosysteme genau zu bestimmen. In dieser Arbeit werden Quantenalgorithmen zur Lösung des Ordnungsproblems und des DL-Problems in der Klassengruppe der Ideale eines imaginär-quadratischen Zahlkörpers angegeben und ihre Komplexität, d.h. die Anzahl der Qubits und der elementaren Quantenoperationen, bestimmt. Darüberhinaus werden Algorithmen zur Bestimmung des Regulators und zur Lösung des Hauptidealproblems und des erweiterten Diskreter-Logarithmus-Problems in reell-quadratischen Zahlkörpern präsentiert. Shors Algorithmus wird dabei auf Funktionen angewendet, die nicht injektiv innerhalb einer Periode sind. Auch in diesem Fall wird die Komplexität der Algorithmen genau bestimmt. Im Falle von Zahlkörpern eines beliebigen Grades wird eine weitere Modifikation von Shors Algorithmus entwickelt: Es wird das Periodengitter einer Funktion bestimmt, deren Periodengitter irrational ist. Dieser Algorithmus wird benutzt, um die Einheitengruppe eines beliebigen endlich-dimensionalen Zahlkörpers zu berechnen. Als nächstes werden die Auswirkungen von Quantenalgorithmen auf die Sicherheit von Public-Key-Kryptosystemen untersucht. Es wird ein neuer Sicherheitsbegriff eingeführt. Die Sicherheit zweier Kryptosysteme wird als gleich definiert, wenn die Anzahl der Qubits zum Brechen dieser Kryptosysteme gleich ist. Basierend auf der neuen Sicherheitsdefinition wird die Geschwindigkeit und die Schlüsselgröße von einigen Kryptosystemen verglichen. Im letzten Kapitel wird ein deterministischer klassischer Algorithmus zur Berechnung der Struktur einer endlichen abelschen Gruppe aus einem Erzeugendensystem präsentiert, dessen Laufzeit nur linear von der Anzahl der gegebenen Erzeuger abhängt und dessen Speicherplatzkomplexität unabhängig von der Anzahl der gegebenen Erzeuger ist. Das stellt eine exponentielle Verbesserung zu früheren Algorithmen dar, bei denen sowohl die Laufzeit als auch die Speicherplatzkomplexität exponentiell von der Anzahl der Erzeuger im gegebenen Erzeugendensystem abhängt [Buchmann/Jacobson/Teske, 1997].