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.
43 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
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.)
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
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
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
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
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.)
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: 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
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