Project Details
Projekt
Novel quantum algorithms via classical cryptography
Subject Area
Software Engineering and Programming Languages
Optics, Quantum Optics and Physics of Atoms, Molecules and Plasmas
Optics, Quantum Optics and Physics of Atoms, Molecules and Plasmas
Term
since 2025
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 563143113
Quantum computing promises advantages in important computational tasks, yet, too few quantum algorithms are known that relate to practically and industrially relevant applications. This project suggests a concerted program of identifying the close links between notions of quantum advantages for classical optimization and of quantum and classical computational complexity for harvesting them in a development and rigorous analysis of quantum algorithms and their run-times. By leveraging insights from cryptography (TU Berlin) and quantum information theory (FU Berlin), we aim to pinpoint the specific structures and problem instances where quantum software outperforms classical methods. Crucially, our focus is not on abstract or purely academic scenarios, but on identifying tangible, real-world advantages that make quantum solutions viable for meaningful applications, addressing one of the most important questions in practically minded quantum computing. In particular, we focus in this research proposal on satisfiability problems: At the end of this research stands an answer to a make-or-break question and clear understanding of the sense in which quantum computers can precisely help when addressing problems of combinatorial optimization. Building on this research, we establish further connections between cryptography and quantum information theory in quantum error correction and quantum simulation.
DFG Programme
Priority Programmes
