Dorian Rudolph

About

I'm a PhD student in quantum computation at Paderborn University, supervised by Sevag Gharibian. I expect to graduate in late 2025 and am looking for a postdoc position!

Research

My work is mainly in quantum complexity theory. I am also interested in quantum algorithms, cryptography, boson sampling and theoretical computer science in general.

1. D. Rudolph. Towards a universal gateset for QMA₁. arXiv:2411.02681, 2024.
   • Poster at QIP 2025.

2. J. Kamminga, D. Rudolph. On the Complexity of Pure-State Consistency of Local Density Matrices. arXiv:2411.03096, 2024.
   • Talk at QIP 2025.
3. M. Aldi, S. Gharibian, D. Rudolph. An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem. arXiv:2412.19623, 2024.
   • Talk at TQC 2024 (Theory of Quantum Computation, Communication and Cryptography).
   • Poster at QIP 2024 (Quantum Information Processing).
4. D. Rudolph, S. Gharibian, D. Nagaj. Quantum 2-SAT on low dimensional systems is QMA₁-complete: Direct embeddings and black-box simulation. arXiv:2401.02368, 2024.
   • Talk at TQC 2024.
   • Poster at QIP 2024.
5. A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph. Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. arXiv:2401.01633, 2024.
   • Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), DOI:10.4230/LIPIcs.MFCS.2024.7 (slides).
   • Poster at QIP 2024.
6. S. Gharibian, D. Rudolph. Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement. arXiv:2206.05243, 2022.
   • Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), DOI:10.4230/LIPIcs.ITCS.2023.53, 2023.
   • Talk at QIP 2022.
7. S. Gharibian, D. Rudolph. On polynomially many queries to NP or QMA oracles. arXiv:2111.02296, 2021.
   • Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), DOI:10.4230/LIPIcs.ITCS.2022.75.
   • Talk at TQC 2022.
   • Poster at QIP 2022.

8. K. Hinnenthal, D. Rudolph, C. Scheideler. Shape Formation in a Three-dimensional Model for Hybrid Programmable Matter.
   • Talk at 36th European Workshop on Computational Geometry (ext. abstract), 2020.
9. D. Rudolph. Approximating the Sweepwidth of Polygons with Holes.
   • Talk at 35th European Workshop on Computational Geometry (EuroCG) (ext. abstract), 2019.
10. R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, C. Scheideler. Shape Recognition by a Finite Automaton Robot.
    • Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), DOI:10.4230/LIPIcs.MFCS.2018.52.
11. R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, C. Scheideler, T. Strothmann. Forming tile shapes with simple robots.
    • Natural Computing 19, DOI:10.1007/s11047-019-09774-2, 2020.
    • Proceedings of DNA Computing and Molecular Programming (DNA 2018), DOI:10.1007/978-3-030-00030-1_8.

Theses

1. Master thesis: On the Power of P with Access to a QMA Oracle.
   (Supervisor: Sevag Gharibian)
2. Bachelor thesis: Decontaminating Planar Regions With Finite Automaton Robots and Tiles.
   (Supervisor: Christian Scheideler)