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
Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 1–24.
LibreCat
| DOI
| arXiv
D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 1–24.
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 | 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), 2024, pp. 1–19.
LibreCat
| arXiv
S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2024, pp. 1–19.
2024 | Preprint | LibreCat-ID: 55037
Beating Grover search for low-energy estimation and state preparation
H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, ArXiv:2407.03073 (2024).
LibreCat
| arXiv
H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, ArXiv:2407.03073 (2024).
2024 | Conference Paper | LibreCat-ID: 50273
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, in: Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2024, pp. 7–17.
LibreCat
| DOI
| arXiv
A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, in: Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2024, pp. 7–17.
2024 | Preprint | LibreCat-ID: 56950
Hardness of approximation for ground state problems
S. Gharibian, C. Hecht, ArXiv:2411.04874 (2024).
LibreCat
| arXiv
S. Gharibian, C. Hecht, ArXiv:2411.04874 (2024).
2024 | Preprint | LibreCat-ID: 56944
Second order cone relaxations for quantum Max Cut
F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).
LibreCat
| arXiv
F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).
2024 | Preprint | LibreCat-ID: 57866
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
M. Aldi, S. Gharibian, D. Rudolph, ArXiv:2412.19623 (n.d.).
LibreCat
| arXiv
M. Aldi, S. Gharibian, D. Rudolph, ArXiv:2412.19623 (n.d.).
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.
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.
2022 | Conference Paper | LibreCat-ID: 27531 |
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
S. Gharibian, F.L. Gall, in: Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 2022, pp. 19–32.
LibreCat
| Download (ext.)
| arXiv
S. Gharibian, F.L. Gall, in: Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 2022, pp. 19–32.
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).
2022 | Conference Paper | LibreCat-ID: 27160 |
On polynomially many queries to NP or QMA oracles
S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, pp. 1–27.
LibreCat
| DOI
| Download (ext.)
S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, pp. 1–27.
2021 | Journal Article | LibreCat-ID: 29780
Towards Quantum One-Time Memories from Stateless Hardware
A. Broadbent, S. Gharibian, H.-S. Zhou, Quantum 5 (2021).
LibreCat
| DOI
A. Broadbent, S. Gharibian, H.-S. Zhou, Quantum 5 (2021).
2020 | Conference Paper | LibreCat-ID: 13226 |
Oracle complexity classes and local measurements on physical Hamiltonians
S. Gharibian, S. Piddock, J. Yirka, in: Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.
LibreCat
| Download (ext.)
| arXiv
S. Gharibian, S. Piddock, J. Yirka, in: Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.
2020 | Conference Paper | LibreCat-ID: 8426
Towards Quantum One-Time Memories from Stateless Hardware
A. Broadbent, S. Gharibian, H.-S. Zhou, in: Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), Leibniz International Proceedings in Informatics (LIPIcs), 2020, p. 6:1-6:25.
LibreCat
| Download (ext.)
| arXiv
A. Broadbent, S. Gharibian, H.-S. Zhou, in: Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), Leibniz International Proceedings in Informatics (LIPIcs), 2020, p. 6:1-6:25.
2020 | Journal Article | LibreCat-ID: 16927 |
On efficiently solvable cases of Quantum k-SAT
S. Gharibian, M. Aldi, N. de Beaudrap, S. Saeedi, Communications in Mathematical Physics (2020).
LibreCat
| Download (ext.)
| arXiv
S. Gharibian, M. Aldi, N. de Beaudrap, S. Saeedi, Communications in Mathematical Physics (2020).