A. Broadbent, S. Gharibian and H.-S. Zhou. Quantum one-time memories from stateless hardware. Available at arXiv.org e-Print quant-ph/1810.05226, 2018. Invited talk at AQIS2018 Kyoto Satellite Workshop on Quantum Computing, Japan.
Refereed Publications
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. 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. To appear in Quantum, 2019. Also presented as poster by Justin Yirka at QIP 2017. Video from talk at Leibniz Universität Hannover is available here. Open access full version 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.
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.
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.
