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
@article{Rudolph_Gharibian_Nagaj_2024, title={Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation}, journal={arXiv:2401.02368}, author={Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel}, year={2024} }
LibreCat
| 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 | Preprint | LibreCat-ID: 50273
@article{Agarwal_Gharibian_Koppula_Rudolph_2024, title={Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds}, journal={arXiv:2401.01633}, author={Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian}, year={2024} }
LibreCat
| arXiv
2024 | Conference Paper | LibreCat-ID: 50406
@inproceedings{Gharibian_Kamminga, title={BQP, meet NP: Search-to-decision reductions and approximate counting}, booktitle={Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP)}, author={Gharibian, Sevag and Kamminga, Jonas} }
LibreCat
| arXiv
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
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
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.)
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
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: 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
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
2019 | Conference Paper | LibreCat-ID: 13297 |
@inproceedings{Gharibian_Parekh_2019, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut}, volume={145}, DOI={10.4230/LIPICS.APPROX-RANDOM.2019.31}, booktitle={Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, author={Gharibian, Sevag and Parekh, Ojas}, year={2019}, pages={31:1-31:17}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
LibreCat
| DOI
| Download (ext.)
2019 | Journal Article | LibreCat-ID: 13558 |
@article{Gharibian_Yirka_2019, title={The complexity of simulating local measurements on quantum systems}, volume={3}, DOI={10.22331/q-2019-09-30-189}, journal={Quantum}, author={Gharibian, Sevag and Yirka, Justin }, year={2019}, pages={189} }
LibreCat
| DOI
| Download (ext.)
2018 | Conference Paper | LibreCat-ID: 8162 |
@inproceedings{Aldi_de Beaudrap_Gharibian_Saeedi_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={On Efficiently Solvable Cases of Quantum k-SAT}, volume={117}, DOI={10.4230/LIPIcs.MFCS.2018.38}, booktitle={43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran}, editor={Potapov, Igor and Spirakis, Paul and Worrell, James}, year={2018}, pages={38:1-38:16}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
LibreCat
| DOI
| Download (ext.)
| arXiv
2018 | Conference Paper | LibreCat-ID: 8161 |
@inproceedings{Gharibian_Santha_Sikora_Sundaram_Yirka_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)}, volume={117}, DOI={10.4230/LIPIcs.MFCS.2018.58}, booktitle={43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin}, editor={Potapov, Igor and Spirakis, Paul and Worrell, James}, year={2018}, pages={58:1-58:16}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
LibreCat
| DOI
| Download (ext.)
| arXiv