Announcements

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


• April 22, 2022
  Postdoc position for "Professional training for platform-independent and photonic quantum computing (qp-tech.edu)" available, see Openings for details!


• April 5, 2022
  Videos of QIP 2022 talks now available, see Media for links. Thanks to Caltech for uploading these!


• February 28, 2022
  Two announcements:
  • The CS Department at Uni Paderborn is looking to hire a Junior Research Group Leader in Quantum Computing.
  • There will be a Quantum Computing School for graduate students and postdocs at Bad Honnef in August 2022, details and registration info here.


• February 18, 2022
  Paper accepted to STOC 2022: Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture (joint work with Francois Le Gall).


• February 10, 2022
  Thank you to the Bundesministerium für Bildung und Forschung (BMBF) for funding proposal "Professional training for platform-independent and photonic quantum computing", project number 13N16224, UPB's part of a multi-institution grant led by the University of Jena.


• January 18, 2022
  Two postdoc and two PhD positions now available in our group, see Openings for details!


• January 11, 2022
  Congratulations to Dorian Rudolph, who was awarded an UPB Outstanding Thesis prize for his Masters thesis titled "On the power of P with access to a QMA oracle"!


• December 21, 2021
  Papers accepted to QIP 2022:
  • Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture (joint work with Francois Le Gall)
  • Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement (joint work with Dorian Rudolph, to be posted on arXiv "soon")