Announcements

• July 1, 2026
  AQIS 2026 accepted paper:
  
  • G. Karaiskos, D. Rudolph, J. J. Meyer, J. Eisert, S. Gharibian. How hard is it to verify a classical shadow?, also at ICALP 2026.


• June 19, 2026
  MFCS 2026 accepted papers:
  
  • Towards a universal gateset for QMA1, D. Rudolph.
  
  
  • Hardness of approximation for ground state problems, S. Gharibian, C. Hecht, also at QIP 2025.


• June 8, 2026
  EU QuantERA proposal "Semidefinite foundations for quantum codes: convergence, bounds, and constructions (SDPCODE)" funded. Joint with Felix Huber (Gdansk, lead), Jens Eisert (FU Berlin), Victor Magron (LAAS CNRS Toulouse), Igor Klep (Primorska, Slovenia).


• May 15, 2026
  DFG proposal "Quantum proof systems with unentangled provers (QPUP)" funded.


• April 30, 2026
  New paper from our group: D. Miloschewsky, S. Podder, D. Rudolph. En Route to a Standard QMA1 vs. QCMA Oracle Separation, arXiv:2604.26921, 2026.


• April 20, 2026
  ICALP 2026 accepted papers:
  
  • G. Karaiskos, D. Rudolph, J. J. Meyer, J. Eisert, S. Gharibian. How hard is it to verify a classical shadow?, arXiv:2510.08515, 2025.
  
  
  • S. Grewal, D. Rudolph. On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity, 2025.


• April 13, 2026
  TQC 2026 news:
  
  • S. Gharibian is honored to be an invited speaker at TQC 2026.
  
  
  • Accepted paper: U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H. Reza Naeij, D. Rudolph, D. Sambrani. Energy, Bosons and Computational Complexity, 2025.
  
  
  • Accepted paper: S. Grewal, D. Rudolph. On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity, 2025.


• February 26, 2026
  Published in ITCS 2026:
  
  • J. Kamminga, D. Rudolph. The Pure-State Consistency of Local Density Matrices Problem: In PSPACE and Complete for a Class Between QMA and QMA(2), arXiv:2411.03096, 2024. QIP 2025, ITCS 2026.
  
  
  • M. Aldi, S. Gharibian, D. Rudolph. An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem, arXiv:2412.19623, 2024. TQC 2024, ITCS 2026.


• October 22, 2025
  New paper: H. Buhrman, S. Gharibian, Z. Landau, F. Le Gall, N. Schuch, S. Tamaki. A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT, arXiv:2510.18164, 2025. To appear in Proceedings of SOSA 2026.


• October 17, 2025
  Four preprints posted from our group (in chronological order):
  
  • U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H. Reza Naeij, D. Rudolph, D. Sambrani. Energy, Bosons and Computational Complexity, arXiv:2510.08545, 2025.
  
  
  • G. Karaiskos, D. Rudolph, J. J. Meyer, J. Eisert, S. Gharibian. How hard is it to verify a classical shadow?, arXiv:2510.08515, 2025.
  
  
  • S. Grewal, D. Rudolph. On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity, arXiv:2510.06522, 2025.
  
  
  • S. Gharibian, J. Kamminga. On the complexity of estimating ground state entanglement and free energy, arXiv:2510.06796, 2025.


• September 8, 2025
  Updated preprint posted with new author Dorian Rudolph: Bounding the computational power of bosonic systems, V. Upreti, D. Rudolph, U. Chabaud.


• July 25, 2025
  Our DFG proposal "Bridge-QS – Bridging finite dimensional and infinite dimensional quantum systems — simulations and computational power" has been funded (joint with Alessandro Ciani, Forschungszentrum Jülich). "


• July 16, 2025
  Our paper Beating Grover search for low-energy estimation and state preparation has been published in PRL.


• June 20, 2025
  New preprint posted based on undergraduate research assistant Simon-Luca Kremer's Bachelor's thesis: Quantum k-SAT Related Hypergraph Problems, S.-L. Kremer, D. Rudolph, S. Gharibian.


• December 30, 2024
  New preprint posted: An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem, M. Aldi, S. Gharibian, D. Rudolph.


• December 9, 2024
  Three papers accepted to QIP 2025 from our group (in chronological order):
  
  • Hardness of approximation for ground state problems, S. Gharibian, C. Hecht.
  
  
  • On the Complexity of Pure-State Consistency of Local Density Matrices, J. Kamminga, D. Rudolph. Congrats on this student-authored paper!
  
  
  • Beating Grover search for low-energy estimation and state preparation, H. Buhrman, S. Gharibian, Z. Landau, F. Le Gall, N. Schuch, S. Tamaki.


• December 4, 2024
  2nd NRW Quantum Theoretical Computer Science Workshop to be held at UPB on December 18, 2024.


• November 7, 2024
  Two new preprints posted:
  • Hardness of approximation for ground state problems, S. Gharibian, C. Hecht.
  
  
  • Second order cone relaxations for quantum Max Cut, F. Huber, K. Thompson, O. Parekh, S. Gharibian.


• November 6, 2024
  Two student-authored preprints from our group posted today. Congrats!
  • 
    On the Complexity of Pure-State Consistency of Local Density Matrices, J. Kamminga, D. Rudolph.
  
  
  • Towards a universal gateset for QMA1, D. Rudolph.


• November 5, 2024
  Paper "Quantum 2-SAT on low dimensional systems is QMA1-complete: Direct embeddings and black-box simulation" (joint work with D. Rudolph, D. Nagaj) accepted to ITCS 2025.


• July 4, 2024
  Preprint "Beating Grover search for low-energy estimation and state preparation" (joint work with H. Buhrman, Z. Landau, F. Le Gall, N. Schuch, and S. Tamaki) posted.


• June 26, 2024
  Paper Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds (joint work with A. Agarwal, V. Koppula, D. Rudolph) accepted to MFCS 2024.


• April 15, 2024
  Papers accepted to TQC 2024:
  • D. Rudolph, S. Gharibian, D. Nagaj. Quantum 2-SAT on low dimensional systems is QMA1-complete: Direct embeddings and black-box simulation, arXiv:2401.02368.
  • M. Aldi, S. Gharibian, D. Rudolph. Quantum complexity theory meets TFNP: Product Quantum Satisfiability on qudits, in preparation.


• April 14, 2024
  Paper "BQP, meet NP: Search-to-decision reductions and approximate counting" (joint work with J. Kamminga) accepted to ICALP 2024.


• January 17, 2024
  Welcome to new PhD candidate, Dhruva Sambrani!


• January 9, 2024
  Preprint "BQP, meet NP: Search-to-decision reductions and approximate counting" (joint work with J. Kamminga) posted.


• January 7, 2024
  Three announcements:
  • Preprint "Quantum 2-SAT on low dimensional systems is QMA1-complete: Direct embeddings and black-box simulation" (joint work with D. Rudolph, D. Nagaj) posted.
  
  
  • Preprint "Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds" (joint work with A. Agarwal, V. Koppula, D. Rudolph) posted.
  
  
  • Invited paper "Guest Column: The 7 faces of quantum NP" published in Sigact News.
  
  


• November 28, 2023
  Video of Quantum Information Workshop at Ruhr University Bochum, The optimal depth of variational quantum algorithms is QCMA-hard to approximate talk posted under Media.


• October 30, 2023
  Preprint "The 7 faces of quantum NP" posted.To appear in ACM SIGACT News as guest column. Had fun with this one.


• May 4, 2023
  Three announcements:
  • Paper accepted to CCC 2023: "Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate" (joint with L. Bittel, M. Kliesch).
  
  
  • Paper accepted to ICALP 2023: "Improved Hardness Results for the Guided Local Hamiltonian Problem" (merged submission with R. Hayakawa, J. Weggemans, T. Morimae, C. Cade, M. Folkertsma, F. Le Gall.).
  
  
  • The accepted papers list for ICALP 2023 is out, early registration deadline is May 15, 2023. See you in Paderborn!
  
  


• February 16, 2023
  An Endowed Full Professorship (W3) in Quantum Algorithms and Software is avaliable.