Please note that LibreCat no longer supports Internet Explorer versions 8 or 9 (or earlier).

We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox.

39 Publications


2024 | Preprint | LibreCat-ID: 50272
Rudolph D, Gharibian S, Nagaj D. Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete:  Direct embeddings and black-box simulation. arXiv:240102368. Published online 2024.
LibreCat | arXiv
 

2024 | Journal Article | LibreCat-ID: 48544 | OA
Gharibian S. Guest Column: The 7 faces of quantum NP. ACM SIGACT News. 2024;54(4):54-91.
LibreCat | Files available | Download (ext.)
 

2024 | Preprint | LibreCat-ID: 50273
Agarwal A, Gharibian S, Koppula V, Rudolph D. Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds. arXiv:240101633. Published online 2024.
LibreCat | arXiv
 

2024 | Conference Paper | LibreCat-ID: 50406
Gharibian S, Kamminga J. BQP, meet NP: Search-to-decision reductions and approximate counting. In: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP).
LibreCat | arXiv
 

2023 | Conference Paper | LibreCat-ID: 31872
Gharibian S, Rudolph D. Quantum space, ground space traversal, and how to embed multi-prover  interactive proofs into unentanglement. In: 14th Innovations in Theoretical Computer Science (ITCS). Vol 251. ; 2023:53:1-53:23. doi:10.4230/LIPIcs.ITCS.2023.53
LibreCat | DOI | arXiv
 

2023 | Conference Paper | LibreCat-ID: 20841 | OA
Gharibian S, Watson J, Bausch J. The Complexity of Translationally Invariant Problems beyond Ground State Energies. In: Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS). Vol 254. ; 2023:54:1-54:21. doi:https://doi.org/10.4230/LIPIcs.STACS.2023.54
LibreCat | DOI | Download (ext.) | arXiv
 

2023 | Conference Paper | LibreCat-ID: 34138
Bittel L, Gharibian S, Kliesch M. The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. In: Proceedings of the 38th Computational Complexity Conference (CCC). Vol 264. Leibniz International Proceedings in Informatics (LIPIcs). ; 2023:34:1-34:24. doi:10.4230/LIPIcs.CCC.2023.34
LibreCat | DOI | arXiv
 

2023 | Conference Paper | LibreCat-ID: 32407
Gharibian S, Hayakawa R, Gall FL, Morimae T. Improved Hardness Results for the Guided Local Hamiltonian Problem. In: Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP). Vol 261. ; 2023:1-19. doi:10.4230/LIPIcs.ICALP.2023.32
LibreCat | DOI | arXiv
 

2023 | Journal Article | LibreCat-ID: 50271
Gharibian S, Le Gall F. Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. SIAM Journal on Computing. 2023;52(4):1009-1038. doi:10.1137/22m1513721
LibreCat | DOI
 

2022 | Journal Article | LibreCat-ID: 34700
Gharibian S, Santha M, Sikora J, Sundaram A, Yirka J. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Computational Complexity. 2022;31(2). doi:10.1007/s00037-022-00231-8
LibreCat | DOI
 

2022 | Conference Paper | LibreCat-ID: 27160 | OA
Gharibian S, Rudolph D. On polynomially many queries to NP or QMA oracles. In: 13th Innovations in Theoretical Computer Science (ITCS 2022). Vol 215. ; 2022:1-27. doi:10.4230/LIPIcs.ITCS.2022.75
LibreCat | DOI | Download (ext.)
 

2022 | Conference Paper | LibreCat-ID: 27531 | OA
Gharibian S, Gall FL. Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture. In: Proceedings of the 54th ACM Symposium on Theory of Computing (STOC). ; 2022:19-32.
LibreCat | Download (ext.) | arXiv
 

2021 | Journal Article | LibreCat-ID: 29780
Broadbent A, Gharibian S, Zhou H-S. Towards Quantum One-Time Memories from Stateless Hardware. Quantum. 2021;5. doi:10.22331/q-2021-04-08-429
LibreCat | DOI
 

2020 | Conference Paper | LibreCat-ID: 8426
Broadbent A, Gharibian S, Zhou H-S. Towards Quantum One-Time Memories from Stateless Hardware. In: Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC). Vol 158. Leibniz International Proceedings in Informatics (LIPIcs); 2020:6:1-6:25.
LibreCat | Download (ext.) | arXiv
 

2020 | Journal Article | LibreCat-ID: 16927 | OA
Gharibian S, Aldi M, de Beaudrap N, Saeedi S. On efficiently solvable cases of Quantum k-SAT. Communications in Mathematical Physics. Published online 2020.
LibreCat | Download (ext.) | arXiv
 

2020 | Conference Paper | LibreCat-ID: 13226 | OA
Gharibian S, Piddock S, Yirka J. Oracle complexity classes and local measurements on physical  Hamiltonians. In: Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020). ; 2020:38.
LibreCat | Download (ext.) | arXiv
 

2019 | Conference Paper | LibreCat-ID: 13297 | OA
Gharibian S, Parekh O. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. In: Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Vol 145. Leibniz International Proceedings in Informatics (LIPIcs). ; 2019:31:1-31:17. doi:10.4230/LIPICS.APPROX-RANDOM.2019.31
LibreCat | DOI | Download (ext.)
 

2019 | Journal Article | LibreCat-ID: 13558 | OA
Gharibian S, Yirka J. The complexity of simulating local measurements on quantum systems. Quantum. 2019;3:189. doi:10.22331/q-2019-09-30-189
LibreCat | DOI | Download (ext.)
 

2018 | Conference Paper | LibreCat-ID: 8162 | OA
Aldi M, de Beaudrap N, Gharibian S, Saeedi S. On Efficiently Solvable Cases of Quantum k-SAT. In: Potapov I, Spirakis P, Worrell J, eds. 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018). Vol 117. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:38:1-38:16. doi:10.4230/LIPIcs.MFCS.2018.38
LibreCat | DOI | Download (ext.) | arXiv
 

2018 | Conference Paper | LibreCat-ID: 8161 | OA
Gharibian S, Santha M, Sikora J, Sundaram A, Yirka J. Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In: Potapov I, Spirakis P, Worrell J, eds. 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018). Vol 117. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:58:1-58:16. doi:10.4230/LIPIcs.MFCS.2018.58
LibreCat | DOI | Download (ext.) | arXiv
 

2018 | Conference Paper | LibreCat-ID: 8160 | OA
Gharibian S, Yirka J. The Complexity of Simulating Local Measurements on Quantum Systems. In: Wilde M, ed. 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Vol 73. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:2:1-2:17. doi:10.4230/LIPIcs.TQC.2017.2
LibreCat | DOI | Download (ext.) | arXiv
 

2018 | Journal Article | LibreCat-ID: 8167 | OA
Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. ACM Transactions on Computation Theory (TOCT). 2018;10(2):8:1-8:28. doi:10.1145/3186587
LibreCat | DOI | Download (ext.) | arXiv
 

2016 | Conference Paper | LibreCat-ID: 8159 | OA
de Beaudrap N, Gharibian S. A Linear Time Algorithm for Quantum 2-SAT. In: Raz R, ed. Proceedings of the 31st Conference on Computational Complexity (CCC 2016). Vol 50. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2016:27:1-17:21. doi:10.4230/LIPIcs.CCC.2016.27
LibreCat | DOI | Download (ext.) | arXiv
 

2015 | Conference Paper | LibreCat-ID: 8164 | OA
Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. In: Halld{\’o}rsson MM, Iwama K, Kobayashi N, Speckmann B, eds. International Colloquium on Automata, Languages, and Programming (ICALP 2015). Springer Berlin Heidelberg; 2015:617-628. doi:10.1007/978-3-662-47672-7_50
LibreCat | DOI | Download (ext.) | arXiv
 

2015 | Journal Article | LibreCat-ID: 8166 | OA
Gharibian S, Huang Y, Landau Z, Woo Shin S. Quantum Hamiltonian Complexity. Foundations and Trends® in Theoretical Computer Science. 2015;10(3):159-282. doi:10.1561/0400000066
LibreCat | DOI | Download (ext.) | arXiv
 

2015 | Journal Article | LibreCat-ID: 8168 | OA
Gharibian S, Landau Z, Woo Shin S, Wang G. Tensor network non-zero testing. Quantum Information & Computation. 2015;15(9{\ & }10):885-899.
LibreCat | Download (ext.) | arXiv
 

2014 | Journal Article | LibreCat-ID: 8171 | OA
Gharibian S, Kempe J. Hardness of approximation for quantum problems. Quantum Information & Computation. 2014;14(5-6):517-540.
LibreCat | Download (ext.) | arXiv
 

2014 | Journal Article | LibreCat-ID: 8172 | OA
W. Berry D, Cleve R, Gharibian S. Gate-efficient discrete simulations of continuous-time quantum query algorithms. Quantum Information & Computation. 2014;14(1-2):1-30.
LibreCat | Download (ext.) | arXiv
 

2013 | Dissertation | LibreCat-ID: 8425 | OA
Gharibian S. Approximation, Proof Systems, and Correlations in a Quantum World.; 2013.
LibreCat | Files available | Download (ext.) | arXiv
 

2013 | Journal Article | LibreCat-ID: 8173 | OA
Gharibian S, Sikora J, Upadhyay S. QMA variants with polynomially many provers. Quantum Information & Computation. 2013;13(1-2):135-157.
LibreCat | Download (ext.) | arXiv
 

2012 | Conference Paper | LibreCat-ID: 8169 | OA
Gharibian S, Kempe J. Hardness of Approximation for Quantum Problems. In: Czumaj A, Mehlhorn K, Pitts A, Wattenhofer R, eds. International Colloquium on Automata, Languages, and Programming (ICALP 2012). Springer Berlin Heidelberg; 2012:387-398. doi:10.1007/978-3-642-31594-7_33
LibreCat | DOI | Download (ext.) | arXiv
 

2012 | Journal Article | LibreCat-ID: 8175 | OA
Gharibian S, Kempe J. Approximation Algorithms for QMA-Complete Problems. SIAM Journal on Computing. 2012;41(4):1028-1050. doi:10.1137/110842272
LibreCat | DOI | Download (ext.) | arXiv
 

2012 | Journal Article | LibreCat-ID: 8174 | OA
Gharibian S. Quantifying nonclassicality with local unitary operations. Physical Review A. 2012;86:042106. doi:10.1103/PhysRevA.86.042106
LibreCat | DOI | Download (ext.) | arXiv
 

2011 | Journal Article | LibreCat-ID: 8178 | OA
Gharibian S, PIANI M, ADESSO G, CALSAMIGLIA J, HORODECKI P. Characterizing Quantumness via Entanglement Creation. International Journal of Quantum Information. 2011;09(07n08):1701-1713. doi:10.1142/s0219749911008258
LibreCat | DOI | Download (ext.) | arXiv
 

2011 | Conference Paper | LibreCat-ID: 8176 | OA
Gharibian S, Kempe J. Approximation Algorithms for QMA-Complete Problems. In: IEEE Annual Conference on Computational Complexity (CCC 2011). IEEE; 2011. doi:10.1109/ccc.2011.15
LibreCat | DOI | Download (ext.) | arXiv
 

2011 | Journal Article | LibreCat-ID: 8177 | OA
Piani M, Gharibian S, Adesso G, Calsamiglia J, Horodecki P, Winter A. All Nonclassical Correlations Can Be Activated into Distillable Entanglement. Physical Review Letters. 2011;106(22). doi:10.1103/physrevlett.106.220403
LibreCat | DOI | Download (ext.) | arXiv
 

2010 | Journal Article | LibreCat-ID: 8179 | OA
Gharibian S. Strong NP-hardness of the quantum separability problem. Quantum Information & Computation. 2010;10(3{\ & }4):343-360.
LibreCat | Download (ext.) | arXiv
 

2009 | Journal Article | LibreCat-ID: 8180 | OA
Gharibian S, Kampermann H, Bru{\ss} D. On global effects caused by locally noneffective unitary operations. Quantum Information & Computation. 2009;9(11):1013-1029.
LibreCat | Download (ext.) | arXiv
 

2009 | Journal Article | LibreCat-ID: 8181 | OA
Datta A, Gharibian S. Signatures of nonclassicality in mixed-state quantum computation. Physical Review A. 2009;79(4). doi:10.1103/physreva.79.042325
LibreCat | DOI | Download (ext.) | arXiv
 

Filters and Search Terms

(person=71541)

status=public

Search

Filter Publications

Display / Sort

Citation Style: AMA

Export / Embed