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
@inproceedings{Rudolph_Gharibian_Nagaj_2025, title={Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation}, volume={325}, DOI={10.4230/LIPIcs.ITCS.2025.85}, number={85}, booktitle={16th Innovations in Theoretical Computer Science (ITCS)}, author={Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel}, year={2025}, pages={1–24} }
LibreCat
| DOI
| arXiv
2024 | Journal Article | LibreCat-ID: 48544 | 
@article{Gharibian_2024, title={Guest Column: The 7 faces of quantum NP}, volume={54}, number={4}, journal={ACM SIGACT News}, author={Gharibian, Sevag}, year={2024}, pages={54–91} }
LibreCat
| Files available
| Download (ext.)
2024 | Conference Paper | LibreCat-ID: 50406
@inproceedings{Gharibian_Kamminga_2024, title={BQP, meet NP: Search-to-decision reductions and approximate counting}, volume={297}, number={70}, booktitle={Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP)}, author={Gharibian, Sevag and Kamminga, Jonas}, year={2024}, pages={1–19} }
LibreCat
| arXiv
2024 | Preprint | LibreCat-ID: 55037
@article{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki_2024, title={Beating Grover search for low-energy estimation and state preparation}, journal={arXiv:2407.03073}, author={Buhrman, Harry and Gharibian, Sevag and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}, year={2024} }
LibreCat
| arXiv
2024 | Conference Paper | LibreCat-ID: 50273
@inproceedings{Agarwal_Gharibian_Koppula_Rudolph_2024, title={Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds}, volume={306}, DOI={10.4230/LIPIcs.MFCS.2024.7}, number={7}, booktitle={Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)}, author={Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian}, year={2024}, pages={7–17} }
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 32407
@inproceedings{Gharibian_Hayakawa_Gall_Morimae_2023, title={Improved Hardness Results for the Guided Local Hamiltonian Problem}, volume={261}, DOI={10.4230/LIPIcs.ICALP.2023.32}, number={32}, booktitle={Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP)}, author={Gharibian, Sevag and Hayakawa, Ryu and Gall, François Le and Morimae, Tomoyuki}, year={2023}, pages={1–19} }
LibreCat
| DOI
| arXiv
2023 | Journal Article | LibreCat-ID: 50271
@article{Gharibian_Le Gall_2023, title={Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}, volume={52}, DOI={10.1137/22m1513721}, number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Gharibian, Sevag and Le Gall, François}, year={2023}, pages={1009–1038} }
LibreCat
| DOI
2023 | Conference Paper | LibreCat-ID: 31872
@inproceedings{Gharibian_Rudolph_2023, title={Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement}, volume={251}, DOI={10.4230/LIPIcs.ITCS.2023.53}, booktitle={14th Innovations in Theoretical Computer Science (ITCS)}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2023}, pages={53:1-53:23} }
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 20841 |
@inproceedings{Gharibian_Watson_Bausch_2023, title={The Complexity of Translationally Invariant Problems beyond Ground State Energies}, volume={254}, DOI={https://doi.org/10.4230/LIPIcs.STACS.2023.54}, booktitle={Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS)}, author={Gharibian, Sevag and Watson, James and Bausch, Johannes}, year={2023}, pages={54:1-54:21} }
LibreCat
| DOI
| Download (ext.)
| arXiv
2023 | Conference Paper | LibreCat-ID: 34138
@inproceedings{Bittel_Gharibian_Kliesch_2023, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate}, volume={264}, DOI={10.4230/LIPIcs.CCC.2023.34}, number={34}, booktitle={Proceedings of the 38th Computational Complexity Conference (CCC)}, author={Bittel, Lennart and Gharibian, Sevag and Kliesch, Martin}, year={2023}, pages={34:1-34:24}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
LibreCat
| DOI
| arXiv
2022 | Conference Paper | LibreCat-ID: 27531 |
@inproceedings{Gharibian_Gall_2022, title={Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}, booktitle={Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)}, author={Gharibian, Sevag and Gall, François Le}, year={2022}, pages={19–32} }
LibreCat
| Download (ext.)
| arXiv
2022 | Journal Article | LibreCat-ID: 34700
@article{Gharibian_Santha_Sikora_Sundaram_Yirka_2022, title={Quantum generalizations of the polynomial hierarchy with applications to QMA(2)}, volume={31}, DOI={10.1007/s00037-022-00231-8}, number={213}, journal={Computational Complexity}, publisher={Springer Science and Business Media LLC}, author={Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin}, year={2022} }
LibreCat
| DOI
2022 | Conference Paper | LibreCat-ID: 27160 |
@inproceedings{Gharibian_Rudolph_2022, title={On polynomially many queries to NP or QMA oracles}, volume={215}, DOI={10.4230/LIPIcs.ITCS.2022.75}, number={75}, booktitle={13th Innovations in Theoretical Computer Science (ITCS 2022)}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2022}, pages={1–27} }
LibreCat
| DOI
| Download (ext.)
2021 | Journal Article | LibreCat-ID: 29780
@article{Broadbent_Gharibian_Zhou_2021, title={Towards Quantum One-Time Memories from Stateless Hardware}, volume={5}, DOI={10.22331/q-2021-04-08-429}, number={429}, journal={Quantum}, publisher={Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften}, author={Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng}, year={2021} }
LibreCat
| DOI
2020 | Conference Paper | LibreCat-ID: 13226 |
@inproceedings{Gharibian_Piddock_Yirka_2020, title={Oracle complexity classes and local measurements on physical Hamiltonians}, booktitle={Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, author={Gharibian, Sevag and Piddock, Stephen and Yirka, Justin}, year={2020}, pages={38} }
LibreCat
| Download (ext.)
| arXiv
2020 | Conference Paper | LibreCat-ID: 8426
@inproceedings{Broadbent_Gharibian_Zhou_2020, title={Towards Quantum One-Time Memories from Stateless Hardware}, volume={158}, booktitle={Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)}, publisher={Leibniz International Proceedings in Informatics (LIPIcs)}, author={Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng}, year={2020}, pages={6:1-6:25} }
LibreCat
| Download (ext.)
| arXiv
2020 | Journal Article | LibreCat-ID: 16927 |
@article{Gharibian_Aldi_de Beaudrap_Saeedi_2020, title={On efficiently solvable cases of Quantum k-SAT}, journal={Communications in Mathematical Physics}, author={Gharibian, Sevag and Aldi, Marco and de Beaudrap, Niel and Saeedi, Seyran}, year={2020} }
LibreCat
| Download (ext.)
| arXiv