Publications

Preprints

• M. Aldi, N. de Beaudrap, S. Gharibian and S. Saeedi. On efficiently solvable cases of Quantum 3-SAT. Available at arXiv.org e-Print quant-ph/1712.09617, 2017.
• A. Broadbent, S. Gharibian and H.-S. Zhou. Quantum one-time memories from stateless hardware. Available at arXiv.org e-Print quant-ph/1511.01363, 2015.

Refereed Publications

• S. Gharibian and J. Yirka. The complexity of estimating local physical quantities. To appear in Proceedings of the Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Presented as poster by Justin Yirka at QIP 2017. Available at quant-ph/1606.05626, 2016. 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 preprint 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 preprint 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. Open access preprint 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 preprint 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 preprint 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 preprint 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 preprint 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 preprint 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 preprint 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 preprint 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 preprint 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 preprint 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 preprint here.
• A. Datta and S. Gharibian. Signatures of non-classicality in mixed-state quantum computation, Physical Review A 79:042325, 2009. Open access preprint here.

Recent Seminars

• S. Gharibian and J. Yirka. The complexity of estimating local physical quantities, quant-ph/1606.05626, 2016.
  • Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 2017.
  • Leibniz Universität Hannover, 2016. Video available here.
  • University of Oxford, UK, 2016.
  • Virginia Commonwealth University, USA, 2016. Presented by J. Yirka.
  • University of Virginia, USA, 2015.
• N. de Beaudrap and S. Gharibian. A linear time algorithm for quantum 2-SAT, 2016.
  • Conference on Computational Complexity (CCC), 2016. Presented by N. de Beaudrap.
  • University of Oxford, UK, 2016. Presented by N. de Beaudrap.
  • California Institute of Technology, USA, 2016.
  • 19th Conference on Quantum Information Processing (QIP), 2016. Merged talk with I. Arad, M. Santha, A. Sundaram, S. Zhang. Presented by A. Sundaram.
  • University of Maryland, College Park, USA, 2015.
• S. Gharibian and Y.-K. Liu. Classical approximation algorithms for quantum constraint satisfaction problems.
  • (Invited) Canadian Mathematical Society (CMS) Winter Meeting, Niagara Falls, Canada, 2016.
  • Department of Mathematics, Virginia Commonwealth University, USA, 2016.
  • (Invited) Semidefinite and Matrix Methods for Optimization and Communication, National University of Singapore, Singapore, 2016.
  • University of California, Berkeley, USA, 2014.
• A. Broadbent, S. Gharibian and H.-S. Zhou. Quantum one-time memories from stateless hardware, quant-ph/1511.01363, 2015.
  • California Institute of Technology, USA, 2016. Presented by A. Broadbent.
  • Virginia Commonwealth University, USA, 2015.
• S. Gharibian, J. Sikora. Ground state connectivity of local Hamiltonians, 2015.
  • (Invited) Workshop around BQP, Tokyo Institute of Technology (Tamachi Campus), Japan, 2015. Presented by J. Sikora.
  • Freie Universitaet Berlin, Germany, 2015.
  • RWTH Aachen University, Germany, 2015.
  • (Invited) Quantum Hamiltonian Complexity Reunion Workshop, Simons Institute for the Theory of Computing, University of California, Berkeley, 2015.
  • 42nd International Colloquium on Automata, Languages, and Programming (ICALP), 2015. Presented by J. Sikora.
  • University of Maryland, College Park, USA, 2014.
  • University of Waterloo, Canada, 2014.