Sevag Gharibian

sevag.gharibian@uni-paderborn.de
ID
71541

39 Publications

Mark all

[39]
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
 
[38]
2024 | Journal Article | LibreCat-ID: 48544 | OA
@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.)
 
[37]
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
 
[36]
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
 
[35]
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
 
[34]
2023 | Conference Paper | LibreCat-ID: 20841 | OA
@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
 
[33]
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
 
[32]
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
 
[31]
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
 
[30]
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
 
[29]
2022 | Conference Paper | LibreCat-ID: 27160 | OA
@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.)
 
[28]
2022 | Conference Paper | LibreCat-ID: 27531 | OA
@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
 
[27]
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
 
[26]
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
 
[25]
2020 | Journal Article | LibreCat-ID: 16927 | OA
@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
 
[24]
2020 | Conference Paper | LibreCat-ID: 13226 | OA
@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
 
[23]
2019 | Conference Paper | LibreCat-ID: 13297 | OA
@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.)
 
[22]
2019 | Journal Article | LibreCat-ID: 13558 | OA
@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.)
 
[21]
2018 | Conference Paper | LibreCat-ID: 8162 | OA
@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
 
[20]
2018 | Conference Paper | LibreCat-ID: 8161 | OA
@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
 
[19]
2018 | Conference Paper | LibreCat-ID: 8160 | OA
@inproceedings{Gharibian_Yirka_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={The Complexity of Simulating Local Measurements on Quantum Systems}, volume={73}, DOI={10.4230/LIPIcs.TQC.2017.2}, booktitle={12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={Gharibian, Sevag and Yirka, Justin}, editor={Wilde, Mark}, year={2018}, pages={2:1-2:17}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
LibreCat | DOI | Download (ext.) | arXiv
 
[18]
2018 | Journal Article | LibreCat-ID: 8167 | OA
@article{Gharibian_Sikora_2018, title={Ground State Connectivity of Local Hamiltonians}, volume={10}, DOI={10.1145/3186587}, number={2}, journal={ACM Transactions on Computation Theory (TOCT)}, publisher={ACM}, author={Gharibian, Sevag and Sikora, Jamie}, year={2018}, pages={8:1-8:28} }
LibreCat | DOI | Download (ext.) | arXiv
 
[17]
2016 | Conference Paper | LibreCat-ID: 8159 | OA
@inproceedings{de Beaudrap_Gharibian_2016, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={A Linear Time Algorithm for Quantum 2-SAT}, volume={50}, DOI={10.4230/LIPIcs.CCC.2016.27}, booktitle={Proceedings of the 31st Conference on Computational Complexity (CCC 2016)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={de Beaudrap, Niel and Gharibian, Sevag}, editor={Raz, Ran}, year={2016}, pages={27:1–17:21}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
LibreCat | DOI | Download (ext.) | arXiv
 
[16]
2015 | Conference Paper | LibreCat-ID: 8164 | OA
@inproceedings{Gharibian_Sikora_2015, place={Berlin, Heidelberg}, title={Ground State Connectivity of Local Hamiltonians}, DOI={10.1007/978-3-662-47672-7_50}, booktitle={International Colloquium on Automata, Languages, and Programming (ICALP 2015)}, publisher={Springer Berlin Heidelberg}, author={Gharibian, Sevag and Sikora, Jamie}, editor={Halld{\’o}rsson, Magn{\’u}s M. and Iwama, Kazuo and Kobayashi, Naoki and Speckmann, Bettina}, year={2015}, pages={617–628} }
LibreCat | DOI | Download (ext.) | arXiv
 
[15]
2015 | Journal Article | LibreCat-ID: 8166 | OA
@article{Gharibian_Huang_Landau_Woo Shin_2015, title={Quantum Hamiltonian Complexity}, volume={10}, DOI={10.1561/0400000066}, number={3}, journal={Foundations and Trends® in Theoretical Computer Science}, author={Gharibian, Sevag and Huang, Yichen and Landau, Zeph and Woo Shin, Seung}, year={2015}, pages={159–282} }
LibreCat | DOI | Download (ext.) | arXiv
 
[14]
2015 | Journal Article | LibreCat-ID: 8168 | OA
@article{Gharibian_Landau_Woo Shin_Wang_2015, title={Tensor network non-zero testing}, volume={15}, number={9{\ & }10}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Landau, Zeph and Woo Shin, Seung and Wang, Guoming}, year={2015}, pages={885–899} }
LibreCat | Download (ext.) | arXiv
 
[13]
2014 | Journal Article | LibreCat-ID: 8171 | OA
@article{Gharibian_Kempe_2014, title={Hardness of approximation for quantum problems}, volume={14}, number={5–6}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Kempe, Julia}, year={2014}, pages={517–540} }
LibreCat | Download (ext.) | arXiv
 
[12]
2014 | Journal Article | LibreCat-ID: 8172 | OA
@article{W. Berry_Cleve_Gharibian_2014, title={Gate-efficient discrete simulations of continuous-time quantum query algorithms}, volume={14}, number={1–2}, journal={Quantum Information & Computation}, author={W. Berry, Dominic and Cleve, Richard and Gharibian, Sevag}, year={2014}, pages={1–30} }
LibreCat | Download (ext.) | arXiv
 
[11]
2013 | Dissertation | LibreCat-ID: 8425 | OA
@book{Gharibian_2013, title={Approximation, Proof Systems, and Correlations in a Quantum World}, author={Gharibian, Sevag}, year={2013} }
LibreCat | Files available | Download (ext.) | arXiv
 
[10]
2013 | Journal Article | LibreCat-ID: 8173 | OA
@article{Gharibian_Sikora_Upadhyay_2013, title={QMA variants with polynomially many provers}, volume={13}, number={1–2}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Sikora, Jamie and Upadhyay, Sarvagya}, year={2013}, pages={135–157} }
LibreCat | Download (ext.) | arXiv
 
[9]
2012 | Conference Paper | LibreCat-ID: 8169 | OA
@inproceedings{Gharibian_Kempe_2012, place={Berlin, Heidelberg}, title={Hardness of Approximation for Quantum Problems}, DOI={10.1007/978-3-642-31594-7_33}, booktitle={International Colloquium on Automata, Languages, and Programming (ICALP 2012)}, publisher={Springer Berlin Heidelberg}, author={Gharibian, Sevag and Kempe, Julia}, editor={Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger}, year={2012}, pages={387–398} }
LibreCat | DOI | Download (ext.) | arXiv
 
[8]
2012 | Journal Article | LibreCat-ID: 8175 | OA
@article{Gharibian_Kempe_2012, title={Approximation Algorithms for QMA-Complete Problems}, volume={41}, DOI={10.1137/110842272}, number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Gharibian, Sevag and Kempe, Julia}, year={2012}, pages={1028–1050} }
LibreCat | DOI | Download (ext.) | arXiv
 
[7]
2012 | Journal Article | LibreCat-ID: 8174 | OA
@article{Gharibian_2012, title={Quantifying nonclassicality with local unitary operations}, volume={86}, DOI={10.1103/PhysRevA.86.042106}, journal={Physical Review A}, publisher={American Physical Society}, author={Gharibian, Sevag}, year={2012}, pages={042106} }
LibreCat | DOI | Download (ext.) | arXiv
 
[6]
2011 | Journal Article | LibreCat-ID: 8178 | OA
@article{Gharibian_PIANI_ADESSO_CALSAMIGLIA_HORODECKI_2011, title={Characterizing Quantumness via Entanglement Creation}, volume={09}, DOI={10.1142/s0219749911008258}, number={07n08}, journal={International Journal of Quantum Information}, publisher={World Scientific Pub Co Pte Lt}, author={Gharibian, Sevag and PIANI, MARCO and ADESSO, GERARDO and CALSAMIGLIA, JOHN and HORODECKI, PAWEŁ}, year={2011}, pages={1701–1713} }
LibreCat | DOI | Download (ext.) | arXiv
 
[5]
2011 | Conference Paper | LibreCat-ID: 8176 | OA
@inproceedings{Gharibian_Kempe_2011, title={Approximation Algorithms for QMA-Complete Problems}, DOI={10.1109/ccc.2011.15}, booktitle={IEEE Annual Conference on Computational Complexity (CCC 2011)}, publisher={IEEE}, author={Gharibian, Sevag and Kempe, Julia}, year={2011} }
LibreCat | DOI | Download (ext.) | arXiv
 
[4]
2011 | Journal Article | LibreCat-ID: 8177 | OA
@article{Piani_Gharibian_Adesso_Calsamiglia_Horodecki_Winter_2011, title={All Nonclassical Correlations Can Be Activated into Distillable Entanglement}, volume={106}, DOI={10.1103/physrevlett.106.220403}, number={22}, journal={Physical Review Letters}, publisher={American Physical Society (APS)}, author={Piani, Marco and Gharibian, Sevag and Adesso, Gerardo and Calsamiglia, John and Horodecki, Paweł and Winter, Andreas}, year={2011} }
LibreCat | DOI | Download (ext.) | arXiv
 
[3]
2010 | Journal Article | LibreCat-ID: 8179 | OA
@article{Gharibian_2010, title={Strong NP-hardness of the quantum separability problem}, volume={10}, number={3{\ & }4}, journal={Quantum Information & Computation}, author={Gharibian, Sevag}, year={2010}, pages={343–360} }
LibreCat | Download (ext.) | arXiv
 
[2]
2009 | Journal Article | LibreCat-ID: 8180 | OA
@article{Gharibian_Kampermann_Bru{\ss}_2009, title={On global effects caused by locally noneffective unitary operations}, volume={9}, number={11}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Kampermann, Hermann and Bru{\ss}, Dagmar}, year={2009}, pages={1013–1029} }
LibreCat | Download (ext.) | arXiv
 
[1]
2009 | Journal Article | LibreCat-ID: 8181 | OA
@article{Datta_Gharibian_2009, title={Signatures of nonclassicality in mixed-state quantum computation}, volume={79}, DOI={10.1103/physreva.79.042325}, number={4}, journal={Physical Review A}, publisher={American Physical Society (APS)}, author={Datta, Animesh and Gharibian, Sevag}, year={2009} }
LibreCat | DOI | Download (ext.) | arXiv
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Citation Style: BibTeX

Export / Embed

39 Publications

Mark all

[39]
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
 
[38]
2024 | Journal Article | LibreCat-ID: 48544 | OA
@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.)
 
[37]
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
 
[36]
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
 
[35]
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
 
[34]
2023 | Conference Paper | LibreCat-ID: 20841 | OA
@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
 
[33]
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
 
[32]
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
 
[31]
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
 
[30]
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
 
[29]
2022 | Conference Paper | LibreCat-ID: 27160 | OA
@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.)
 
[28]
2022 | Conference Paper | LibreCat-ID: 27531 | OA
@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
 
[27]
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
 
[26]
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
 
[25]
2020 | Journal Article | LibreCat-ID: 16927 | OA
@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
 
[24]
2020 | Conference Paper | LibreCat-ID: 13226 | OA
@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
 
[23]
2019 | Conference Paper | LibreCat-ID: 13297 | OA
@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.)
 
[22]
2019 | Journal Article | LibreCat-ID: 13558 | OA
@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.)
 
[21]
2018 | Conference Paper | LibreCat-ID: 8162 | OA
@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
 
[20]
2018 | Conference Paper | LibreCat-ID: 8161 | OA
@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
 
[19]
2018 | Conference Paper | LibreCat-ID: 8160 | OA
@inproceedings{Gharibian_Yirka_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={The Complexity of Simulating Local Measurements on Quantum Systems}, volume={73}, DOI={10.4230/LIPIcs.TQC.2017.2}, booktitle={12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={Gharibian, Sevag and Yirka, Justin}, editor={Wilde, Mark}, year={2018}, pages={2:1-2:17}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
LibreCat | DOI | Download (ext.) | arXiv
 
[18]
2018 | Journal Article | LibreCat-ID: 8167 | OA
@article{Gharibian_Sikora_2018, title={Ground State Connectivity of Local Hamiltonians}, volume={10}, DOI={10.1145/3186587}, number={2}, journal={ACM Transactions on Computation Theory (TOCT)}, publisher={ACM}, author={Gharibian, Sevag and Sikora, Jamie}, year={2018}, pages={8:1-8:28} }
LibreCat | DOI | Download (ext.) | arXiv
 
[17]
2016 | Conference Paper | LibreCat-ID: 8159 | OA
@inproceedings{de Beaudrap_Gharibian_2016, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={A Linear Time Algorithm for Quantum 2-SAT}, volume={50}, DOI={10.4230/LIPIcs.CCC.2016.27}, booktitle={Proceedings of the 31st Conference on Computational Complexity (CCC 2016)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={de Beaudrap, Niel and Gharibian, Sevag}, editor={Raz, Ran}, year={2016}, pages={27:1–17:21}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
LibreCat | DOI | Download (ext.) | arXiv
 
[16]
2015 | Conference Paper | LibreCat-ID: 8164 | OA
@inproceedings{Gharibian_Sikora_2015, place={Berlin, Heidelberg}, title={Ground State Connectivity of Local Hamiltonians}, DOI={10.1007/978-3-662-47672-7_50}, booktitle={International Colloquium on Automata, Languages, and Programming (ICALP 2015)}, publisher={Springer Berlin Heidelberg}, author={Gharibian, Sevag and Sikora, Jamie}, editor={Halld{\’o}rsson, Magn{\’u}s M. and Iwama, Kazuo and Kobayashi, Naoki and Speckmann, Bettina}, year={2015}, pages={617–628} }
LibreCat | DOI | Download (ext.) | arXiv
 
[15]
2015 | Journal Article | LibreCat-ID: 8166 | OA
@article{Gharibian_Huang_Landau_Woo Shin_2015, title={Quantum Hamiltonian Complexity}, volume={10}, DOI={10.1561/0400000066}, number={3}, journal={Foundations and Trends® in Theoretical Computer Science}, author={Gharibian, Sevag and Huang, Yichen and Landau, Zeph and Woo Shin, Seung}, year={2015}, pages={159–282} }
LibreCat | DOI | Download (ext.) | arXiv
 
[14]
2015 | Journal Article | LibreCat-ID: 8168 | OA
@article{Gharibian_Landau_Woo Shin_Wang_2015, title={Tensor network non-zero testing}, volume={15}, number={9{\ & }10}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Landau, Zeph and Woo Shin, Seung and Wang, Guoming}, year={2015}, pages={885–899} }
LibreCat | Download (ext.) | arXiv
 
[13]
2014 | Journal Article | LibreCat-ID: 8171 | OA
@article{Gharibian_Kempe_2014, title={Hardness of approximation for quantum problems}, volume={14}, number={5–6}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Kempe, Julia}, year={2014}, pages={517–540} }
LibreCat | Download (ext.) | arXiv
 
[12]
2014 | Journal Article | LibreCat-ID: 8172 | OA
@article{W. Berry_Cleve_Gharibian_2014, title={Gate-efficient discrete simulations of continuous-time quantum query algorithms}, volume={14}, number={1–2}, journal={Quantum Information & Computation}, author={W. Berry, Dominic and Cleve, Richard and Gharibian, Sevag}, year={2014}, pages={1–30} }
LibreCat | Download (ext.) | arXiv
 
[11]
2013 | Dissertation | LibreCat-ID: 8425 | OA
@book{Gharibian_2013, title={Approximation, Proof Systems, and Correlations in a Quantum World}, author={Gharibian, Sevag}, year={2013} }
LibreCat | Files available | Download (ext.) | arXiv
 
[10]
2013 | Journal Article | LibreCat-ID: 8173 | OA
@article{Gharibian_Sikora_Upadhyay_2013, title={QMA variants with polynomially many provers}, volume={13}, number={1–2}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Sikora, Jamie and Upadhyay, Sarvagya}, year={2013}, pages={135–157} }
LibreCat | Download (ext.) | arXiv
 
[9]
2012 | Conference Paper | LibreCat-ID: 8169 | OA
@inproceedings{Gharibian_Kempe_2012, place={Berlin, Heidelberg}, title={Hardness of Approximation for Quantum Problems}, DOI={10.1007/978-3-642-31594-7_33}, booktitle={International Colloquium on Automata, Languages, and Programming (ICALP 2012)}, publisher={Springer Berlin Heidelberg}, author={Gharibian, Sevag and Kempe, Julia}, editor={Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger}, year={2012}, pages={387–398} }
LibreCat | DOI | Download (ext.) | arXiv
 
[8]
2012 | Journal Article | LibreCat-ID: 8175 | OA
@article{Gharibian_Kempe_2012, title={Approximation Algorithms for QMA-Complete Problems}, volume={41}, DOI={10.1137/110842272}, number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Gharibian, Sevag and Kempe, Julia}, year={2012}, pages={1028–1050} }
LibreCat | DOI | Download (ext.) | arXiv
 
[7]
2012 | Journal Article | LibreCat-ID: 8174 | OA
@article{Gharibian_2012, title={Quantifying nonclassicality with local unitary operations}, volume={86}, DOI={10.1103/PhysRevA.86.042106}, journal={Physical Review A}, publisher={American Physical Society}, author={Gharibian, Sevag}, year={2012}, pages={042106} }
LibreCat | DOI | Download (ext.) | arXiv
 
[6]
2011 | Journal Article | LibreCat-ID: 8178 | OA
@article{Gharibian_PIANI_ADESSO_CALSAMIGLIA_HORODECKI_2011, title={Characterizing Quantumness via Entanglement Creation}, volume={09}, DOI={10.1142/s0219749911008258}, number={07n08}, journal={International Journal of Quantum Information}, publisher={World Scientific Pub Co Pte Lt}, author={Gharibian, Sevag and PIANI, MARCO and ADESSO, GERARDO and CALSAMIGLIA, JOHN and HORODECKI, PAWEŁ}, year={2011}, pages={1701–1713} }
LibreCat | DOI | Download (ext.) | arXiv
 
[5]
2011 | Conference Paper | LibreCat-ID: 8176 | OA
@inproceedings{Gharibian_Kempe_2011, title={Approximation Algorithms for QMA-Complete Problems}, DOI={10.1109/ccc.2011.15}, booktitle={IEEE Annual Conference on Computational Complexity (CCC 2011)}, publisher={IEEE}, author={Gharibian, Sevag and Kempe, Julia}, year={2011} }
LibreCat | DOI | Download (ext.) | arXiv
 
[4]
2011 | Journal Article | LibreCat-ID: 8177 | OA
@article{Piani_Gharibian_Adesso_Calsamiglia_Horodecki_Winter_2011, title={All Nonclassical Correlations Can Be Activated into Distillable Entanglement}, volume={106}, DOI={10.1103/physrevlett.106.220403}, number={22}, journal={Physical Review Letters}, publisher={American Physical Society (APS)}, author={Piani, Marco and Gharibian, Sevag and Adesso, Gerardo and Calsamiglia, John and Horodecki, Paweł and Winter, Andreas}, year={2011} }
LibreCat | DOI | Download (ext.) | arXiv
 
[3]
2010 | Journal Article | LibreCat-ID: 8179 | OA
@article{Gharibian_2010, title={Strong NP-hardness of the quantum separability problem}, volume={10}, number={3{\ & }4}, journal={Quantum Information & Computation}, author={Gharibian, Sevag}, year={2010}, pages={343–360} }
LibreCat | Download (ext.) | arXiv
 
[2]
2009 | Journal Article | LibreCat-ID: 8180 | OA
@article{Gharibian_Kampermann_Bru{\ss}_2009, title={On global effects caused by locally noneffective unitary operations}, volume={9}, number={11}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Kampermann, Hermann and Bru{\ss}, Dagmar}, year={2009}, pages={1013–1029} }
LibreCat | Download (ext.) | arXiv
 
[1]
2009 | Journal Article | LibreCat-ID: 8181 | OA
@article{Datta_Gharibian_2009, title={Signatures of nonclassicality in mixed-state quantum computation}, volume={79}, DOI={10.1103/physreva.79.042325}, number={4}, journal={Physical Review A}, publisher={American Physical Society (APS)}, author={Datta, Animesh and Gharibian, Sevag}, year={2009} }
LibreCat | DOI | Download (ext.) | arXiv
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Citation Style: BibTeX

Export / Embed