Quantum algorithms & complexity theory
Roman Edenhofer
I am a PhD student at IRIF in Paris, supervised by Simon Apers and Frédéric Magniez. I started my PhD in March 2024.
I am interested in quantum algorithms and complexity theory, with a particular focus on space complexity.
I also organize the Algorithms and Complexity Seminar at IRIF.
Email edenhofer at irif dot fr
Publications
Papers & preprints
-
Robust subspace designs and the power of a unique small quantum witness
-
A Space-space Trade-off for Directed st-Connectivity
-
Dequantization and Hardness of Spectral Sum Estimation
29th Annual Quantum Information Processing Conference (QIP ’26)
-
Directed st-connectivity with few paths is in quantum logspace
20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC ’25)
Computational Complexity Conference (CCC ’25)
Research visits
During my PhD, I have been fortunate to be hosted by:
-
–
Michal Koucký
Charles University · Prague, Czech Republic
-
–
François Le Gall
Nagoya University · Nagoya, Japan
Education
-
– present
PhD in Quantum Complexity Theory
Institut de Recherche en Informatique Fondamentale (IRIF)
Paris, FranceDepartment: Algorithmes et complexité
Supervisors: Simon Apers and Frédéric Magniez -
–
Master of Science in Mathematics
Technische Universität Darmstadt · Darmstadt, Germany
Master's thesis: Quantum Space-Bounded Computation and Graph Connectivity PDF
Supervisors: Simon Apers and Kord Eickmeyer
-
–
Bachelor of Science in Mathematics
Technische Universität Darmstadt · Darmstadt, Germany
Bachelor's thesis: Abort-Strategies for Preemptive Online Dial-a-Ride PDF
Supervisor: Yann Disser