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
D. Rudolph, S. Gharibian, and D. Nagaj, “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), 2025, vol. 325, no. 85, pp. 1–24, doi: 10.4230/LIPIcs.ITCS.2025.85.
LibreCat
| DOI
| arXiv
2024 | Journal Article | LibreCat-ID: 48544 | 
S. Gharibian, “Guest Column: The 7 faces of quantum NP,” ACM SIGACT News, vol. 54, no. 4, pp. 54–91, 2024.
LibreCat
| Files available
| Download (ext.)
2024 | Conference Paper | LibreCat-ID: 50273
A. Agarwal, S. Gharibian, V. Koppula, and D. Rudolph, “Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds,” in Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2024, vol. 306, no. 7, pp. 7–17, doi: 10.4230/LIPIcs.MFCS.2024.7.
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 32407
S. Gharibian, R. Hayakawa, F. L. Gall, and T. Morimae, “Improved Hardness Results for the Guided Local Hamiltonian Problem,” in Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2023, vol. 261, no. 32, pp. 1–19, doi: 10.4230/LIPIcs.ICALP.2023.32.
LibreCat
| DOI
| arXiv
2023 | Journal Article | LibreCat-ID: 50271
S. Gharibian and F. Le Gall, “Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture,” SIAM Journal on Computing, vol. 52, no. 4, pp. 1009–1038, 2023, doi: 10.1137/22m1513721.
LibreCat
| DOI
2023 | Conference Paper | LibreCat-ID: 31872
S. Gharibian and D. Rudolph, “Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement,” in 14th Innovations in Theoretical Computer Science (ITCS), 2023, vol. 251, p. 53:1-53:23, doi: 10.4230/LIPIcs.ITCS.2023.53.
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 20841 |
S. Gharibian, J. Watson, and J. Bausch, “The Complexity of Translationally Invariant Problems beyond Ground State Energies,” in Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 2023, vol. 254, p. 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
L. Bittel, S. Gharibian, and M. Kliesch, “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate,” in Proceedings of the 38th Computational Complexity Conference (CCC), 2023, vol. 264, no. 34, p. 34:1-34:24, doi: 10.4230/LIPIcs.CCC.2023.34.
LibreCat
| DOI
| arXiv
2022 | Conference Paper | LibreCat-ID: 27531 |
S. Gharibian and F. L. Gall, “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, pp. 19–32.
LibreCat
| Download (ext.)
| arXiv
2022 | Journal Article | LibreCat-ID: 34700
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka, “Quantum generalizations of the polynomial hierarchy with applications to QMA(2),” Computational Complexity, vol. 31, no. 2, Art. no. 13, 2022, doi: 10.1007/s00037-022-00231-8.
LibreCat
| DOI
2022 | Conference Paper | LibreCat-ID: 27160 |
S. Gharibian and D. Rudolph, “On polynomially many queries to NP or QMA oracles,” in 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, vol. 215, no. 75, pp. 1–27, doi: 10.4230/LIPIcs.ITCS.2022.75.
LibreCat
| DOI
| Download (ext.)
2021 | Journal Article | LibreCat-ID: 29780
A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories from Stateless Hardware,” Quantum, vol. 5, Art. no. 429, 2021, doi: 10.22331/q-2021-04-08-429.
LibreCat
| DOI
2020 | Conference Paper | LibreCat-ID: 13226 |
S. Gharibian, S. Piddock, and J. Yirka, “Oracle complexity classes and local measurements on physical Hamiltonians,” in Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.
LibreCat
| Download (ext.)
| arXiv
2020 | Conference Paper | LibreCat-ID: 8426
A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories from Stateless Hardware,” in Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 2020, vol. 158, p. 6:1-6:25.
LibreCat
| Download (ext.)
| arXiv
2020 | Journal Article | LibreCat-ID: 16927 |
S. Gharibian, M. Aldi, N. de Beaudrap, and S. Saeedi, “On efficiently solvable cases of Quantum k-SAT,” Communications in Mathematical Physics, 2020.
LibreCat
| Download (ext.)
| arXiv