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. (2024). Guest Column: The 7 faces of quantum NP. ACM SIGACT News, 54(4), 54–91.
LibreCat
| Files available
| Download (ext.)
2023 | Conference Paper | LibreCat-ID: 31872
Gharibian, S., & Rudolph, D. (2023). Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement. 14th Innovations in Theoretical Computer Science (ITCS), 251, 53:1-53:23. https://doi.org/10.4230/LIPIcs.ITCS.2023.53
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 20841 |
Gharibian, S., Watson, J., & Bausch, J. (2023). The Complexity of Translationally Invariant Problems beyond Ground State Energies. Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 254, 54:1-54:21. 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. (2023). The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. Proceedings of the 38th Computational Complexity Conference (CCC), 264(34), 34:1-34:24. https://doi.org/10.4230/LIPIcs.CCC.2023.34
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 32407
Gharibian, S., Hayakawa, R., Gall, F. L., & Morimae, T. (2023). Improved Hardness Results for the Guided Local Hamiltonian Problem. Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 261(32), 1–19. https://doi.org/10.4230/LIPIcs.ICALP.2023.32
LibreCat
| DOI
| arXiv
2023 | Journal Article | LibreCat-ID: 50271
Gharibian, S., & Le Gall, F. (2023). Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. SIAM Journal on Computing, 52(4), 1009–1038. https://doi.org/10.1137/22m1513721
LibreCat
| DOI
2022 | Journal Article | LibreCat-ID: 34700
Gharibian, S., Santha, M., Sikora, J., Sundaram, A., & Yirka, J. (2022). Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Computational Complexity, 31(2), Article 13. https://doi.org/10.1007/s00037-022-00231-8
LibreCat
| DOI
2022 | Conference Paper | LibreCat-ID: 27160 |
Gharibian, S., & Rudolph, D. (2022). On polynomially many queries to NP or QMA oracles. 13th Innovations in Theoretical Computer Science (ITCS 2022), 215(75), 1–27. https://doi.org/10.4230/LIPIcs.ITCS.2022.75
LibreCat
| DOI
| Download (ext.)
2022 | Conference Paper | LibreCat-ID: 27531 |
Gharibian, S., & Gall, F. L. (2022). Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 19–32.
LibreCat
| Download (ext.)
| arXiv
2021 | Journal Article | LibreCat-ID: 29780
Broadbent, A., Gharibian, S., & Zhou, H.-S. (2021). Towards Quantum One-Time Memories from Stateless Hardware. Quantum, 5, Article 429. https://doi.org/10.22331/q-2021-04-08-429
LibreCat
| DOI
2020 | Conference Paper | LibreCat-ID: 8426
Broadbent, A., Gharibian, S., & Zhou, H.-S. (2020). Towards Quantum One-Time Memories from Stateless Hardware. Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 158, 6:1-6:25.
LibreCat
| Download (ext.)
| arXiv
2020 | Journal Article | LibreCat-ID: 16927 |
Gharibian, S., Aldi, M., de Beaudrap, N., & Saeedi, S. (2020). On efficiently solvable cases of Quantum k-SAT. Communications in Mathematical Physics.
LibreCat
| Download (ext.)
| arXiv
2020 | Conference Paper | LibreCat-ID: 13226 |
Gharibian, S., Piddock, S., & Yirka, J. (2020). Oracle complexity classes and local measurements on physical Hamiltonians. Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 38.
LibreCat
| Download (ext.)
| arXiv
2019 | Conference Paper | LibreCat-ID: 13297 |
Gharibian, S., & Parekh, O. (2019). Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 145, 31:1-31:17. https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31
LibreCat
| DOI
| Download (ext.)
2019 | Journal Article | LibreCat-ID: 13558 |
Gharibian, S., & Yirka, J. (2019). The complexity of simulating local measurements on quantum systems. Quantum, 3, 189. https://doi.org/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. (2018). On Efficiently Solvable Cases of Quantum k-SAT. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) (Vol. 117, p. 38:1-38:16). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/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. (2018). Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) (Vol. 117, p. 58:1-58:16). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2018.58
LibreCat
| DOI
| Download (ext.)
| arXiv