Von der Quantenmechanik zum Quantum Computation: Seit der Entdeckung quantenmechanischer Zusammenhänge, die sich zwar beobachten, aber nur schwer in das rationale Bewusstsein einfügen lassen, konnten in den letzten Jahren Eigenschaften dieser kontraintuitiven Wissenschaft zur Anwendung gebracht werden. Jedoch erst mit dem fächerübergreifenden Zusammenspiel von Physik, Mathematik und Informatik entwickelte sich der Begriff des Quantum Computation. Spin-Eigenschaften von Teilchen machen es physikalisch möglich, eine quantentheoretische Imitation der binären Computertechnik aus der Informatik einzuführen. Das führt zu der Idee, gewisse Strukturen, die sich in der Konstruktion von Quantenalgorithmen ergeben, mathematisch aufzugreifen und zu untersuchen, ob damit eine komplexitätserhaltende Berechnung auf einem klassischen Rechner möglich wäre. Komplexität und Informationsverlust: Ohne den Effizienzgewinn zu verlieren ist eine exakte Bestimmung des Ergebnisses, den der Quantenalgorithmus liefert, nicht möglich. Andererseits kann der Rechenaufwand nur unter immensem Informationsverlust auf das gewünschte Niveau gebracht werden. Eine ausreichend gute Annäherung an das exakte Ergebnis bei einer immer noch signifikanten Einsparung von Berechnungsschritten auf einem klassischen Rechner könnte einen interessanten Mittelweg darstellen. Eine signifikante Einsparung heißt dabei, möglichst in einer niedrigeren Ordnungsklasse der Komplexität zu landen, als dies im Falle einer exakten Berechnung auf einem Rechner möglich wäre. Das approximierte Ergebnis sollte dann bei einer mehrfach durchgeführten Simulation ein dem tatsächlichen Ergebnis sehr angenähertes Ergebnis liefern. Quantenalgorithmen als stochastische Algorithmen: Die aus der Physik stammenden Algorithmen weisen ein Verhalten auf, das von stochastischer Natur ist und zu einem Vergleich mit stochastischen Verfahren ermuntert. Deswegen wird ein auf einem stochastischen Algorithmus beruhendes (Branch&Bound-)Verfahren konstruiert, bei dem die Reduktion der Komplexität auf ein niedrigeres Niveau Ansatzpunkte für die klassische Umsetzung bringt. Das Niveau der Komplexität wird zunächst auf dieselbe Ordnung gebracht, die der Quantenalgorithmus bei der Ausführung auf einem Quantenrechner benötigt. Dies ist jedoch mit einem großen Informationsverlust verbunden. Wird nach und nach der Rechenaufwand erhöht, gewinnt man zusätzliche Information. Das Abwägen zwischen möglichst geringem Informationsverlust und einer tragbaren Ordnung der Komplexität ist das entscheidende Kriterium bei der klassischen Simulation von Quantenalgorithmen.