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