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, Sevag. “Guest Column: The 7 Faces of Quantum NP.” ACM SIGACT News 54, no. 4 (2024): 54–91.
LibreCat
| Files available
| Download (ext.)
2023 | Conference Paper | LibreCat-ID: 31872
Gharibian, Sevag, and Dorian Rudolph. “Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement.” In 14th Innovations in Theoretical Computer Science (ITCS), 251:53:1-53:23, 2023. https://doi.org/10.4230/LIPIcs.ITCS.2023.53.
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 20841 |
Gharibian, Sevag, James Watson, and Johannes 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), 254:54:1-54:21, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.54.
LibreCat
| DOI
| Download (ext.)
| arXiv
2023 | Conference Paper | LibreCat-ID: 34138
Bittel, Lennart, Sevag Gharibian, and Martin Kliesch. “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate.” In Proceedings of the 38th Computational Complexity Conference (CCC), 264:34:1-34:24. Leibniz International Proceedings in Informatics (LIPIcs), 2023. https://doi.org/10.4230/LIPIcs.CCC.2023.34.
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 32407
Gharibian, Sevag, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae. “Improved Hardness Results for the Guided Local Hamiltonian Problem.” In Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 261:1–19, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.32.
LibreCat
| DOI
| arXiv
2023 | Journal Article | LibreCat-ID: 50271
Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.” SIAM Journal on Computing 52, no. 4 (2023): 1009–38. https://doi.org/10.1137/22m1513721.
LibreCat
| DOI
2022 | Journal Article | LibreCat-ID: 34700
Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” Computational Complexity 31, no. 2 (2022). https://doi.org/10.1007/s00037-022-00231-8.
LibreCat
| DOI
2022 | Conference Paper | LibreCat-ID: 27160 |
Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.” In 13th Innovations in Theoretical Computer Science (ITCS 2022), 215:1–27, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.75.
LibreCat
| DOI
| Download (ext.)
2022 | Conference Paper | LibreCat-ID: 27531 |
Gharibian, Sevag, and François Le 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), 19–32, 2022.
LibreCat
| Download (ext.)
| arXiv
2021 | Journal Article | LibreCat-ID: 29780
Broadbent, Anne, Sevag Gharibian, and Hong-Sheng Zhou. “Towards Quantum One-Time Memories from Stateless Hardware.” Quantum 5 (2021). https://doi.org/10.22331/q-2021-04-08-429.
LibreCat
| DOI
2020 | Conference Paper | LibreCat-ID: 8426
Broadbent, Anne, Sevag Gharibian, and Hong-Sheng 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), 158:6:1-6:25. Leibniz International Proceedings in Informatics (LIPIcs), 2020.
LibreCat
| Download (ext.)
| arXiv
2020 | Journal Article | LibreCat-ID: 16927 |
Gharibian, Sevag, Marco Aldi, Niel de Beaudrap, and Seyran Saeedi. “On Efficiently Solvable Cases of Quantum K-SAT.” Communications in Mathematical Physics, 2020.
LibreCat
| Download (ext.)
| arXiv
2020 | Conference Paper | LibreCat-ID: 13226 |
Gharibian, Sevag, Stephen Piddock, and Justin Yirka. “Oracle Complexity Classes and Local Measurements on Physical Hamiltonians.” In Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 38, 2020.
LibreCat
| Download (ext.)
| arXiv
2019 | Conference Paper | LibreCat-ID: 13297 |
Gharibian, Sevag, and Ojas Parekh. “Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut.” In Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 145:31:1-31:17. Leibniz International Proceedings in Informatics (LIPIcs), 2019. https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31.
LibreCat
| DOI
| Download (ext.)
2019 | Journal Article | LibreCat-ID: 13558 |
Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” Quantum 3 (2019): 189. https://doi.org/10.22331/q-2019-09-30-189.
LibreCat
| DOI
| Download (ext.)
2018 | Conference Paper | LibreCat-ID: 8162 |
Aldi, Marco, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi. “On Efficiently Solvable Cases of Quantum K-SAT.” In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), edited by Igor Potapov, Paul Spirakis, and James Worrell, 117:38:1-38:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.38.
LibreCat
| DOI
| Download (ext.)
| arXiv
2018 | Conference Paper | LibreCat-ID: 8161 |
Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), edited by Igor Potapov, Paul Spirakis, and James Worrell, 117:58:1-58:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.58.
LibreCat
| DOI
| Download (ext.)
| arXiv