Externally funded projects

In progress

• Deutsche Forschungsgemeinschaft (DFG) - Project 432788384
  The Quantum Satisfiability Problem: Algorithms and Complexity-Theoretic Hardness, P.I.

Completed

• 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

Preprints

• J. D. Watson, J. Bausch, S. Gharibian. The complexity of translationally invariant problems beyond ground state energies. arXiv:2012.12717, 2020.

Refereed Publications

• A. Broadbent, S. Gharibian and H.-S. Zhou. Towards quantum one-time memories from stateless hardware.  Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:25, 2020. Invited talk at 18th Asian Quantum Information Science Conference (AQIS 2018) Satellite Workshop on Quantum Computing, Kyoto University, Japan, 2018.  Open access full version here.
• S. Gharibian, S. Piddock and J. Yirka. Oracle complexity classes and local measurements on physical Hamiltonians. Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), volume 154 of Leibniz International Proceedings in Informatics (LIPIcs), 20:1--20:37, 2020. Also presented at 23rd Annual Conference on Quantum Information Processing (QIP 2020). Preliminary version presented at 18th Asian Quantum Information Science Conference (AQIS), 2018, by J. Yirka. Open access full version here.
• S. Gharibian, O. Parekh.  Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut.  Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:17, 2019.  Also presented at 23rd Annual Conference on Quantum Information Processing (QIP 2020). Open access full version here.
• S. Gharibian, M. Santha, J. Sikora, A. Sundaram and J. Yirka. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1-58:16, 2018. Also presented as plenary talk (top 7% of submissions) at the 18th Asian Quantum Information Science Conference (AQIS 2018), and as invited talk by A. Sundaram at Quantum Innovators Workshop, IQC, University of Waterloo. Open access full version here.
• M. Aldi, N. de Beaudrap, S. Gharibian and S. Saeedi. On efficiently solvable cases of Quantum k-SAT. Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:16, 2018. Journal version in Communications in Mathematical Physics, 2020, https://doi.org/10.1007/s00220-020-03843-9. Presented as plenary talk (top 7% of submissions) at the 18th Asian Quantum Information Science Conference (AQIS 2018). Open access full version here.
• S. Gharibian and J. Yirka. The complexity of simulating local measurements on quantum systems. Proceedings of the 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), volume 73 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1-2:17, 2018. Journal version in Quantum, 3:189, 2019. Also presented as poster by Justin Yirka at QIP 2017. Video from talk at Leibniz Universität Hannover is available here.
• N. de Beaudrap and S. Gharibian. A linear time algorithm for quantum 2-SAT. In Proceedings of the 31st Conference on Computational Complexity (CCC), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:21, 2016. Also presented at the 19th Conference on Quantum Information Processing (QIP), 2016. Open access full version here.
• 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. Open access full version here.
• S. Gharibian, J. Sikora. Ground state connectivity of local Hamiltonians. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), volume 9134 of Lecture Notes in Computer Science, pages 617 – 628, 2015. Full version in ACM Transactions on Computation Theory, volume 10, issue 2, 2018. Open access full version here.
• S. Gharibian, Z. Landau, S. W. Shin, and G. Wang. Tensor network non-zero testing. Quantum Information & Computation 15 (9 & 10):885-899, 2015. Presented by S. W. Shin as long talk at AQIS 2014. Open access full version here.
• S. Gharibian and J. Kempe. Hardness of approximation for quantum problems. Quantum Information & Computation 14 (5 & 6), 2014. Invited talk at ELC Workshop on Inapproximability, University of Electro-Communications, Japan. Also presented at 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. Quantum Information & Computation 14 (1 & 2): 0001-0030, 2014. Presented by R. Cleve at QIP 2012 and D. Berry at AQIS 2012. 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. Invited talk at Mini-Workshop on the General Quantumness of Correlations, University of Waterloo, 2012. Open access full version here.
• S. Gharibian and J. Kempe. Approximation algorithms for QMA-complete problems, SIAM Journal on Computing 41(4): 1028-1050, 2012. Presented at CCC 2011. Winner of Best Poster Award at QIP 2011. Open access full version here.
• 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. Open access full version here.
• 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. Open access full version here.
• S. Gharibian. Strong NP-hardness of the quantum separability problem, Quantum Information & Computation 10(3 & 4): 343-360, 2010. Winner of 2nd Place for Best Speaker Award, CQISC 2008. Also presented at SQuInT 2009. Open access full version here.
• 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. Invited talk by D. Bruß at QI 2009. Open access full version here.
• A. Datta and S. Gharibian. Signatures of non-classicality in mixed-state quantum computation, Physical Review A 79:042325, 2009. Open access full version here.