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 | Preprint | LibreCat-ID: 50272
Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
D. Rudolph, S. Gharibian, D. Nagaj, ArXiv:2401.02368 (2024).
LibreCat
| arXiv
D. Rudolph, S. Gharibian, D. Nagaj, ArXiv:2401.02368 (2024).
2024 | Journal Article | LibreCat-ID: 48544 | 
Guest Column: The 7 faces of quantum NP
S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
LibreCat
| Files available
| Download (ext.)
S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
2024 | Preprint | LibreCat-ID: 50273
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, ArXiv:2401.01633 (2024).
LibreCat
| arXiv
A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, ArXiv:2401.01633 (2024).
2024 | Conference Paper | LibreCat-ID: 50406
BQP, meet NP: Search-to-decision reductions and approximate counting
S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), n.d.
LibreCat
| arXiv
S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), n.d.
2023 | Conference Paper | LibreCat-ID: 31872
Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
S. Gharibian, D. Rudolph, in: 14th Innovations in Theoretical Computer Science (ITCS), 2023, p. 53:1-53:23.
LibreCat
| DOI
| arXiv
S. Gharibian, D. Rudolph, in: 14th Innovations in Theoretical Computer Science (ITCS), 2023, p. 53:1-53:23.
2023 | Conference Paper | LibreCat-ID: 20841 |
The Complexity of Translationally Invariant Problems beyond Ground State Energies
S. Gharibian, J. Watson, J. Bausch, in: Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 2023, p. 54:1-54:21.
LibreCat
| DOI
| Download (ext.)
| arXiv
S. Gharibian, J. Watson, J. Bausch, in: Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 2023, p. 54:1-54:21.
2023 | Conference Paper | LibreCat-ID: 34138
The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate
L. Bittel, S. Gharibian, M. Kliesch, in: Proceedings of the 38th Computational Complexity Conference (CCC), 2023, p. 34:1-34:24.
LibreCat
| DOI
| arXiv
L. Bittel, S. Gharibian, M. Kliesch, in: Proceedings of the 38th Computational Complexity Conference (CCC), 2023, p. 34:1-34:24.
2023 | Conference Paper | LibreCat-ID: 32407
Improved Hardness Results for the Guided Local Hamiltonian Problem
S. Gharibian, R. Hayakawa, F.L. Gall, T. Morimae, in: Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2023, pp. 1–19.
LibreCat
| DOI
| arXiv
S. Gharibian, R. Hayakawa, F.L. Gall, T. Morimae, in: Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2023, pp. 1–19.
2023 | Journal Article | LibreCat-ID: 50271
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
S. Gharibian, F. Le Gall, SIAM Journal on Computing 52 (2023) 1009–1038.
LibreCat
| DOI
S. Gharibian, F. Le Gall, SIAM Journal on Computing 52 (2023) 1009–1038.
2022 | Journal Article | LibreCat-ID: 34700
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, Computational Complexity 31 (2022).
LibreCat
| DOI
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, Computational Complexity 31 (2022).