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.
48 Publications
2025 | Conference Paper | 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. In: 16th Innovations in Theoretical Computer Science (ITCS). Vol 325. ; 2025:1-24. doi:10.4230/LIPIcs.ITCS.2025.85
LibreCat
| DOI
| arXiv
2025 | Journal Article | LibreCat-ID: 55037
Buhrman H, Gharibian S, Landau Z, Gall FL, Schuch N, Tamaki S. Beating Grover search for low-energy estimation and state preparation. Physical Review Letters. 2025;135:030601. doi:10.1103/29qw-bssx
LibreCat
| DOI
| arXiv
2024 | Conference Paper | LibreCat-ID: 50273
Agarwal A, Gharibian S, Koppula V, Rudolph D. Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. In: Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS). Vol 306. ; 2024:7-17. doi:10.4230/LIPIcs.MFCS.2024.7
LibreCat
| DOI
| arXiv
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: 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 | 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 | 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 | 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
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