Dorian Rudolph

About

I'm a PhD student in quantum computation at Paderborn University, supervised by Sevag Gharibian.

Research

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

1. U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H. R. Naeij, D. Rudolph, D. Sambrani. Energy, Bosons and Computational Complexity. arXiv:2510.08545, 2025.
2. S. Grewal, D. Rudolph. On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity. arXiv:2510.06522, 2025.
3. G. Karaiskos, D. Rudolph, J. J. Meyer, J. Eisert, S. Gharibian. How hard is it to verify a classical shadow? arXiv:2510.08515, 2025.

4. D. Rudolph. Towards a universal gateset for QMA₁. arXiv:2411.02681, 2024.
   • Poster at QIP 2025.
   • Talk at AQIS 2025.
5. J. Kamminga, D. Rudolph. On the Complexity of Pure-State Consistency of Local Density Matrices. arXiv:2411.03096, 2024.
   • Talk at QIP 2025.
   • To appear in the Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS 2026).
6. 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).
   • To appear in the Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS 2026).
7. 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.
   • Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), DOI:10.4230/LIPIcs.ITCS.2025.85.
   • Talk at TQC 2024.
   • Poster at QIP 2024.
8. 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.
9. 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.
10. 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.

11. 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.
12. D. Rudolph. Approximating the Sweepwidth of Polygons with Holes.
    • Talk at 35th European Workshop on Computational Geometry (EuroCG) (ext. abstract), 2019.
13. 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.
14. 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)