Externally funded projects

In progress

• Bundesministerium für Bildung und Forschung (BMBF) - Project 13N16224
  Professional training for platform-independent and photonic quantum computing,
  Lead PI at UPB (multi-institution grant, led by University of Jena).
• Bundesministerium für Bildung und Forschung (BMBF)
  Photonic Quantum Computers (PhoQuant), co-P.I. at UPB (multi-institution grant).
• State of North Rhein-Westphalia
  Photonic Quantum Computing (PhoQC), co-P.I.
• Deutsche Forschungsgemeinschaft (DFG) - Project 450041824
  Characterizing the complexity of physical quantum problems with oracle complexity classes, P.I.

Completed

• Deutsche Forschungsgemeinschaft (DFG) - Project 432788384
  The Quantum Satisfiability Problem: Algorithms and Complexity-Theoretic Hardness, P.I.
• National Science Foundation (NSF), CCF-1617710
  AF: Small: Approximation algorithms for the quantum mechanical problems, P.I.
• National Science Foundation (NSF), CCF-1526189
  AF: Small: Exact algorithms for the quantum satisfiability problem, P.I.

Papers from our research group

Preprints

M. Aldi, S. Gharibian, D. Rudolph. An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem, arXiv:2412.19623, 2024. TQC 2024.


S. Gharibian, C. Hecht. Hardness of approximation for ground state problems, arXiv:2411.04874, 2024. QIP 2025.


• F. Huber, K. Thompson, O. Parekh, S. Gharibian. Second order cone relaxations for quantum Max Cut, arXiv:2411.04120, 2024.


• J. Kamminga, D. Rudolph. On the Complexity of Pure-State Consistency of Local Density Matrices, arXiv:2411.03096, 2024. QIP 2025.


• D. Rudolph. Towards a universal gateset for QMA1, arXiv:2411.02681, 2024.


• H. Buhrman, S. Gharibian, Z. Landau, F. Le Gall, N. Schuch, S. Tamaki. Beating Grover search for low-energy estimation and state preparation, arXiv:2407.03073, 2024. QIP 2025.

Publications

• D. Rudolph, S. Gharibian, D. Nagaj. Quantum 2-SAT on low dimensional systems is QMA1-complete: Direct embeddings and black-box simulation, ITCS 2025, TQC 2024.


• A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph. Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. MFCS 2024.


• S. Gharibian, J. Kamminga. BQP, meet NP: Search-to-decision reductions and approximate counting. ICALP 2024.


• (Invited) S. Gharibian. Guest Column: The 7 faces of quantum NP. ACM SIGACT News, 54(4):54-91, 2024.


• L. Bittel, S. Gharibian, M. Kliesch. Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate. CCC 2023, QIP 2023.


• S. Gharibian, R. Hayakawa, F. Le Gall, T. Morimae. Improved Hardness Results for the Guided Local Hamiltonian Problem. ICALP 2023, QIP 2023.


• S. Gharibian, D. Rudolph. Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement. ITCS 2023, QIP 2022.


• J. D. Watson, J. Bausch, S. Gharibian. The complexity of translationally invariant problems beyond ground state energies. STACS 2023, TQC 2021, Workshop on Combinatorial Reconfiguration (CORE 2021, affiliated with ICALP 2021).


• S. Gharibian, F. le Gall. Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. STOC 2022, QIP 2022.


• S. Gharibian and D. Rudolph. On polynomially many queries to NP or QMA oracles.  ITCS 2022, TQC 2022.
• A. Broadbent, S. Gharibian and H.-S. Zhou. Towards quantum one-time memories from stateless hardware.  TQC 2020. Invited talk at AQIS 2018 Satellite Workshop on Quantum Computing.  Journal version in Quantum, 5:429, 2021.
• S. Gharibian, S. Piddock and J. Yirka. Oracle complexity classes and local measurements on physical Hamiltonians. QIP 2020, STACS 2020. Preliminary version at AQIS 2018.
• S. Gharibian, O. Parekh.  Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut.  QIP 2020, APPROX 2019.
• S. Gharibian, M. Santha, J. Sikora, A. Sundaram and J. Yirka. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Plenary talk at AQIS 2018, MFCS 2018. Journal version in Computational Complexity, 31(13), 2022.
• M. Aldi, N. de Beaudrap, S. Gharibian and S. Saeedi. On efficiently solvable cases of Quantum k-SAT. Plenary talk at AQIS 2018, MFCS 2018. Journal version in Communications in Mathematical Physics, 381: 209-256, 2020.
• S. Gharibian and J. Yirka. The complexity of simulating local measurements on quantum systems. TQC 2017. Journal version in Quantum,3:189, 2019.
• N. de Beaudrap and S. Gharibian. A linear time algorithm for quantum 2-SAT. QIP 2016, CCC 2016. arXiv:1508.07338.
• S. Gharibian, Y. Huang, and Z. Landau, S. W. Shin. Quantum Hamiltonian Complexity. Foundations and Trends in Theoretical Computer Science, 10(3):159-282, 2015. .
• S. Gharibian, J. Sikora. Ground state connectivity of local Hamiltonians. ICALP 2015. Journal version in ACM Transactions on Computation Theory, 10(2), 2018. .
• S. Gharibian, Z. Landau, S. W. Shin, and G. Wang. Tensor network non-zero testing. Long talk at AQIS 2014. Quantum Information & Computation 15 (9 & 10):885-899, 2015. .
• S. Gharibian and J. Kempe. Hardness of approximation for quantum problems. Quantum Information & Computation 14 (5 & 6), 2014. QIP 2012, ICALP 2012. Open access full version here.
• D. Berry, R. Cleve and S. Gharibian. Gate-efficient discrete simulations of continuous-time quantum query algorithms. QIP 2012, AQIS 2012. Journal version in Quantum Information & Computation 14 (1 & 2): 0001-0030, 2014. Open access full version here.
• S. Gharibian, J. Sikora, and S. Upadhyay. QMA variants with polynomially many provers. Quantum Information & Computation 13(1 & 2):0135-0157, 2013. Open access full version here.
• S. Gharibian. Quantifying non-classicality with local unitary operations, Physical Review A 86:042106, 2012.
• S. Gharibian and J. Kempe. Approximation algorithms for QMA-complete problems. CCC 2011. Journal version in SIAM Journal on Computing 41(4): 1028-1050, 2012. Winner of Best Poster Award at QIP 2011. .
• M. Piani, S. Gharibian, G. Adesso, J. Calsamiglia, P. Horodecki and A. Winter. All non-classical correlations can be activated into distillable entanglement, Physical Review Letters 106: 220403, 2011. arXiv:1103.4032.
• S. Gharibian, M. Piani, G. Adesso, J. Calsamiglia, P. Horodecki. Characterizing quantumness via entanglement creation, International Journal of Quantum Information 9(7 & 8):1701-1713, 2011. arXiv:1105.3419.
• S. Gharibian. Strong NP-hardness of the quantum separability problem, Quantum Information & Computation 10(3 & 4): 343-360, 2010. SqUInT 2009, 2nd Place for Best Speaker Award at CQISC 2008. arXiv:0810.4507.
• S. Gharibian, H. Kampermann, and D. Bruß. On global effects caused by locally noneffective unitary operations, Quantum Information & Computation 9(11 & 12): 1013-1029, 2009. arXiv:0809.4469.
• A. Datta and S. Gharibian. Signatures of non-classicality in mixed-state quantum computation, Physical Review A 79:042325, 2009. arXiv:0811.4003.