Announcements

• 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.


• December 19, 2022
  PhD position available in quantum algorithms/complexity theory/photonics! Deadline: January 10, 2023.


• December 14, 2022
  Our group welcomes new PhD Candidate Georgios Karaiskos! Click on People for details.


• December 5, 2022
  Two announcements:
  • Paper accepted to STACS 2023: "The complexity of translationally invariant problems beyond ground state energies" (joint with J. D. Watson, J. Bausch).
  
  
  • Postdoc position available in quantum algorithms/complexity theory/photonics! Deadline: December 16, 2022.


• November 25, 2022
  Papers accepted to QIP 2023:
  • "Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate" (joint work with L. Bittel, M. Kliesch)
  • "Improved Hardness Results for the Guided Local Hamiltonian Problem" (joint work with R. Hayakawa, F. Le Gall, T. Morimae)


• November 24, 2022
  Preprint "Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate" (joint work with L. Bittel, M. Kliesch) posted.


• November 13, 2022
  Video of STOC 2022 Workshop: The Multiple Facets of Quantum Proofs, Introduction to Quantum Proofs talk posted under Media.


• November 2, 2022
  ICALP 2023 will be hosted by Paderborn University from 10-14 July, 2023. The Call for Papers/Call for Workshops are now live.


• October 20, 2022
  Postdoc position available in project "Professional training for platform-independent and photonic quantum computing (qp-tech.edu)", deadline Nov 6, 2022.


• September 30, 2022
  Congratulations to Masters candidate Carsten Hecht for defending his Masters thesis on the recent breakthroughs in classical/quantum LDPC codes!


• September 6, 2022
  Our group welcomes new PhD candidate, Jonas Kamminga!


• August 22, 2022
  Lecture videos and slides from 2022 Bad Honnef Summer School on Quantum Computing posted! Great lineup of speakers/topics. Direct links to quantum complexity lectures posted to Media above.


• July 21, 2022
  Preprint "Improved Hardness Results for the Guided Local Hamiltonian Problem" (joint work with R. Hayakawa, F. Le Gall, T. Morimae) posted.


• June 13, 2022
  Preprint "Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement" (joint work with Dorian Rudolph, presented at QIP 2022) posted.


• June 9, 2022
  Congrats to Daniel Warkentin for his Masters thesis defense!


• June 8, 2022
  Welcome to Avantika Agarwal, joining us for a 2-month summer research internship from IIT Delhi!


• May 12, 2022
  Video of talk at Banff International Research Station Workshop on Combinatorial Reconfiguration on "Reconfiguration in the quantum setting" now available, see Media for links.


• April 29, 2022
  • Video of UC Berkeley/MIT Quantum CS seminar on "Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement" (joint work with Dorian Rudolph) now available, see Media for links.
  • Senior researcher position in quantum algorithms (focus: Gaussian Boson Sampling, Universal photonic quantum computing) available, see Openings for details.