Algorithmen und Komplexität im Quantum Computing: Möglichkeiten und Grenzen quantenmechanischer Berechnungen

• Antragsteller: Dr. Hartmut Klauck
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2004 bis 2009
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5424260

Quantum Computing ist ein interdisziplinäres Gebiet zwischen Informatik, Physik und Mathematik. Es wurde von Feynman und Deutsch in den 80er Jahren begründet, und erhält massive Aufmerksamkeit weltweit, seit in Arbeiten von Shor und Grover überraschend schnelle Algorithmen für Quantencomputer beschrieben wurden. Im Quantum Computing werden Berechnungsmodelle betrachtet, die den Regeln der Quantenmechanik folgen. Dabei werden sowohl neue Algorithmen gesucht als auch die Grenzen solcher Modelle erforscht. Im Projekt sollen Untersuchungen zu Quantenalgorithmen und zur Komplexitätstheorie für Quantencomputer angestellt werden. Ein geplanter Schwerpunkt sind Quantencomputer mit beschränktem Speicherplatz mit den Themen Tradeoffs zwischen Speicherplatz und anderen Ressourcen, Computer mit gemischt klassischem/quantenmechanischem Speicher, und Quantum-Data-Stream Algorithmen. Desweiteren soll das Quanten-Kommunikationsmodell mit und ohne Speicherrestriktion untersucht werden, wobei nach neuen Techniken zum Beweis unterer Schranken gesucht werden soll. Als weiterer Schwerpunkt sollen Quantenalgorithmen für Graph- und Matrixprobleme erforscht werden.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen (Aktionsplan Informatik)