Sevag Gharibian
Algorithms & Complexity, Quantum Computation
Associate Professor (W2)
Department of Computer Science
Institute for Photonic Quantum Systems (PhoQS)
Paderborn University
Germany
Algorithms & Complexity, Quantum Computation
Associate Professor (W2)
Department of Computer Science
Institute for Photonic Quantum Systems (PhoQS)
Paderborn University
Germany
Announcements
- April 15, 2024Papers 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, 2024Paper "BQP, meet NP: Search-to-decision reductions and approximate counting" (joint work with J. Kamminga) accepted to ICALP 2024.
- January 17, 2024Welcome to new PhD candidate, Dhruva Sambrani!
- January 9, 2024Preprint "BQP, meet NP: Search-to-decision reductions and approximate counting" (joint work with J. Kamminga) posted.
- January 7, 2024Three 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, 2023Video 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, 2023Preprint "The 7 faces of quantum NP" posted.To appear in ACM SIGACT News as guest column. Had fun with this one.
- May 4, 2023Three 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, 2023An Endowed Full Professorship (W3) in Quantum Algorithms and Software is avaliable.
- December 19, 2022PhD position available in quantum algorithms/complexity theory/photonics! Deadline: January 10, 2023.
- December 14, 2022Our group welcomes new PhD Candidate Georgios Karaiskos! Click on People for details.
- December 5, 2022Two 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, 2022Papers 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, 2022Preprint "Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate" (joint work with L. Bittel, M. Kliesch) posted.
- November 13, 2022Video of STOC 2022 Workshop: The Multiple Facets of Quantum Proofs, Introduction to Quantum Proofs talk posted under Media.
- November 2, 2022ICALP 2023 will be hosted by Paderborn University from 10-14 July, 2023. The Call for Papers/Call for Workshops are now live.
- October 20, 2022Postdoc position available in project "Professional training for platform-independent and photonic quantum computing (qp-tech.edu)", deadline Nov 6, 2022.
- September 30, 2022Congratulations to Masters candidate Carsten Hecht for defending his Masters thesis on the recent breakthroughs in classical/quantum LDPC codes!
- September 6, 2022Our group welcomes new PhD candidate, Jonas Kamminga!
- August 22, 2022Lecture 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, 2022Preprint "Improved Hardness Results for the Guided Local Hamiltonian Problem" (joint work with R. Hayakawa, F. Le Gall, T. Morimae) posted.
- June 13, 2022Preprint "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, 2022Congrats to Daniel Warkentin for his Masters thesis defense!
- June 8, 2022Welcome to Avantika Agarwal, joining us for a 2-month summer research internship from IIT Delhi!
- May 12, 2022Video 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, 2022Postdoc position for "Professional training for platform-independent and photonic quantum computing (qp-tech.edu)" available, see Openings for details!
- April 5, 2022Videos of QIP 2022 talks now available, see Media for links. Thanks to Caltech for uploading these!
- February 28, 2022Two 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, 2022Paper 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, 2022Thank 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, 2022Two postdoc and two PhD positions now available in our group, see Openings for details!
- January 11, 2022Congratulations 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, 2021Papers 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")