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
Rudolph, Dorian, et al. “Quantum 2-SAT on Low Dimensional Systems Is $\mathsf{QMA}_1$-Complete:  Direct Embeddings and Black-Box Simulation.” ArXiv:2401.02368, 2024.
LibreCat | arXiv
 

2024 | Journal Article | LibreCat-ID: 48544 | OA
Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” ACM SIGACT News, vol. 54, no. 4, 2024, pp. 54–91.
LibreCat | Files available | Download (ext.)
 

2024 | Preprint | LibreCat-ID: 50273
Agarwal, Avantika, et al. “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower  Bounds.” ArXiv:2401.01633, 2024.
LibreCat | arXiv
 

2024 | Conference Paper | LibreCat-ID: 50406
Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision Reductions and Approximate Counting.” Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP).
LibreCat | arXiv
 

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.” 14th Innovations in Theoretical Computer Science (ITCS), vol. 251, 2023, p. 53:1-53:23, doi:10.4230/LIPIcs.ITCS.2023.53.
LibreCat | DOI | arXiv
 

2023 | Conference Paper | LibreCat-ID: 20841 | OA
Gharibian, Sevag, et al. “The Complexity of Translationally Invariant Problems beyond Ground State Energies.” Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), vol. 254, 2023, p. 54:1-54:21, doi:https://doi.org/10.4230/LIPIcs.STACS.2023.54.
LibreCat | DOI | Download (ext.) | arXiv
 

2023 | Conference Paper | LibreCat-ID: 34138
Bittel, Lennart, et al. “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate.” Proceedings of the 38th Computational Complexity Conference (CCC), vol. 264, no. 34, 2023, p. 34:1-34:24, doi:10.4230/LIPIcs.CCC.2023.34.
LibreCat | DOI | arXiv
 

2023 | Conference Paper | LibreCat-ID: 32407
Gharibian, Sevag, et al. “Improved Hardness Results for the Guided Local Hamiltonian Problem.” Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), vol. 261, no. 32, 2023, pp. 1–19, doi: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, vol. 52, no. 4, Society for Industrial & Applied Mathematics (SIAM), 2023, pp. 1009–38, doi:10.1137/22m1513721.
LibreCat | DOI
 

2022 | Journal Article | LibreCat-ID: 34700
Gharibian, Sevag, et al. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” Computational Complexity, vol. 31, no. 2, 13, Springer Science and Business Media LLC, 2022, doi:10.1007/s00037-022-00231-8.
LibreCat | DOI
 

2022 | Conference Paper | LibreCat-ID: 27160 | OA
Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.” 13th Innovations in Theoretical Computer Science (ITCS 2022), vol. 215, no. 75, 2022, pp. 1–27, doi:10.4230/LIPIcs.ITCS.2022.75.
LibreCat | DOI | Download (ext.)
 

2022 | Conference Paper | LibreCat-ID: 27531 | OA
Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture.” Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 2022, pp. 19–32.
LibreCat | Download (ext.) | arXiv
 

2021 | Journal Article | LibreCat-ID: 29780
Broadbent, Anne, et al. “Towards Quantum One-Time Memories from Stateless Hardware.” Quantum, vol. 5, 429, Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften, 2021, doi:10.22331/q-2021-04-08-429.
LibreCat | DOI
 

2020 | Conference Paper | LibreCat-ID: 8426
Broadbent, Anne, et al. “Towards Quantum One-Time Memories from Stateless Hardware.” Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), vol. 158, Leibniz International Proceedings in Informatics (LIPIcs), 2020, p. 6:1-6:25.
LibreCat | Download (ext.) | arXiv
 

2020 | Journal Article | LibreCat-ID: 16927 | OA
Gharibian, Sevag, et al. “On Efficiently Solvable Cases of Quantum K-SAT.” Communications in Mathematical Physics, 2020.
LibreCat | Download (ext.) | arXiv
 

2020 | Conference Paper | LibreCat-ID: 13226 | OA
Gharibian, Sevag, et al. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.
LibreCat | Download (ext.) | arXiv
 

2019 | Conference Paper | LibreCat-ID: 13297 | OA
Gharibian, Sevag, and Ojas Parekh. “Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut.” Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), vol. 145, 2019, p. 31:1-31:17, doi:10.4230/LIPICS.APPROX-RANDOM.2019.31.
LibreCat | DOI | Download (ext.)
 

2019 | Journal Article | LibreCat-ID: 13558 | OA
Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” Quantum, vol. 3, 2019, p. 189, doi:10.22331/q-2019-09-30-189.
LibreCat | DOI | Download (ext.)
 

2018 | Conference Paper | LibreCat-ID: 8162 | OA
Aldi, Marco, et al. “On Efficiently Solvable Cases of Quantum K-SAT.” 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 38:1-38:16, doi:10.4230/LIPIcs.MFCS.2018.38.
LibreCat | DOI | Download (ext.) | arXiv
 

2018 | Conference Paper | LibreCat-ID: 8161 | OA
Gharibian, Sevag, et al. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 58:1-58:16, doi:10.4230/LIPIcs.MFCS.2018.58.
LibreCat | DOI | Download (ext.) | arXiv
 

2018 | Conference Paper | LibreCat-ID: 8160 | OA
Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), edited by Mark Wilde, vol. 73, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 2:1-2:17, doi:10.4230/LIPIcs.TQC.2017.2.
LibreCat | DOI | Download (ext.) | arXiv
 

2018 | Journal Article | LibreCat-ID: 8167 | OA
Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” ACM Transactions on Computation Theory (TOCT), vol. 10, no. 2, ACM, 2018, p. 8:1-8:28, doi:10.1145/3186587.
LibreCat | DOI | Download (ext.) | arXiv
 

2016 | Conference Paper | LibreCat-ID: 8159 | OA
de Beaudrap, Niel, and Sevag Gharibian. “A Linear Time Algorithm for Quantum 2-SAT.” Proceedings of the 31st Conference on Computational Complexity (CCC 2016), edited by Ran Raz, vol. 50, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, p. 27:1-17:21, doi:10.4230/LIPIcs.CCC.2016.27.
LibreCat | DOI | Download (ext.) | arXiv
 

2015 | Conference Paper | LibreCat-ID: 8164 | OA
Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” International Colloquium on Automata, Languages, and Programming (ICALP 2015), edited by Magn{\’u}s M. Halld{\’o}rsson et al., Springer Berlin Heidelberg, 2015, pp. 617–28, doi:10.1007/978-3-662-47672-7_50.
LibreCat | DOI | Download (ext.) | arXiv
 

2015 | Journal Article | LibreCat-ID: 8166 | OA
Gharibian, Sevag, et al. “Quantum Hamiltonian Complexity.” Foundations and Trends® in Theoretical Computer Science, vol. 10, no. 3, 2015, pp. 159–282, doi:10.1561/0400000066.
LibreCat | DOI | Download (ext.) | arXiv
 

2015 | Journal Article | LibreCat-ID: 8168 | OA
Gharibian, Sevag, et al. “Tensor Network Non-Zero Testing.” Quantum Information & Computation, vol. 15, no. 9{\ & }10, 2015, pp. 885–99.
LibreCat | Download (ext.) | arXiv
 

2014 | Journal Article | LibreCat-ID: 8171 | OA
Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” Quantum Information & Computation, vol. 14, no. 5–6, 2014, pp. 517–40.
LibreCat | Download (ext.) | arXiv
 

2014 | Journal Article | LibreCat-ID: 8172 | OA
W. Berry, Dominic, et al. “Gate-Efficient Discrete Simulations of Continuous-Time Quantum Query Algorithms.” Quantum Information & Computation, vol. 14, no. 1–2, 2014, pp. 1–30.
LibreCat | Download (ext.) | arXiv
 

2013 | Dissertation | LibreCat-ID: 8425 | OA
Gharibian, Sevag. Approximation, Proof Systems, and Correlations in a Quantum World. 2013.
LibreCat | Files available | Download (ext.) | arXiv
 

2013 | Journal Article | LibreCat-ID: 8173 | OA
Gharibian, Sevag, et al. “QMA Variants with Polynomially Many Provers.” Quantum Information & Computation, vol. 13, no. 1–2, 2013, pp. 135–57.
LibreCat | Download (ext.) | arXiv
 

2012 | Conference Paper | LibreCat-ID: 8169 | OA
Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” International Colloquium on Automata, Languages, and Programming (ICALP 2012), edited by Artur Czumaj et al., Springer Berlin Heidelberg, 2012, pp. 387–98, doi:10.1007/978-3-642-31594-7_33.
LibreCat | DOI | Download (ext.) | arXiv
 

2012 | Journal Article | LibreCat-ID: 8175 | OA
Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” SIAM Journal on Computing, vol. 41, no. 4, Society for Industrial & Applied Mathematics (SIAM), 2012, pp. 1028–50, doi:10.1137/110842272.
LibreCat | DOI | Download (ext.) | arXiv
 

2012 | Journal Article | LibreCat-ID: 8174 | OA
Gharibian, Sevag. “Quantifying Nonclassicality with Local Unitary Operations.” Physical Review A, vol. 86, American Physical Society, 2012, p. 042106, doi:10.1103/PhysRevA.86.042106.
LibreCat | DOI | Download (ext.) | arXiv
 

2011 | Journal Article | LibreCat-ID: 8178 | OA
Gharibian, Sevag, et al. “Characterizing Quantumness via Entanglement Creation.” International Journal of Quantum Information, vol. 09, no. 07n08, World Scientific Pub Co Pte Lt, 2011, pp. 1701–13, doi:10.1142/s0219749911008258.
LibreCat | DOI | Download (ext.) | arXiv
 

2011 | Conference Paper | LibreCat-ID: 8176 | OA
Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” IEEE Annual Conference on Computational Complexity (CCC 2011), IEEE, 2011, doi:10.1109/ccc.2011.15.
LibreCat | DOI | Download (ext.) | arXiv
 

2011 | Journal Article | LibreCat-ID: 8177 | OA
Piani, Marco, et al. “All Nonclassical Correlations Can Be Activated into Distillable Entanglement.” Physical Review Letters, vol. 106, no. 22, American Physical Society (APS), 2011, doi:10.1103/physrevlett.106.220403.
LibreCat | DOI | Download (ext.) | arXiv
 

2010 | Journal Article | LibreCat-ID: 8179 | OA
Gharibian, Sevag. “Strong NP-Hardness of the Quantum Separability Problem.” Quantum Information & Computation, vol. 10, no. 3{\ & }4, 2010, pp. 343–60.
LibreCat | Download (ext.) | arXiv
 

2009 | Journal Article | LibreCat-ID: 8180 | OA
Gharibian, Sevag, et al. “On Global Effects Caused by Locally Noneffective Unitary Operations.” Quantum Information & Computation, vol. 9, no. 11, 2009, pp. 1013–29.
LibreCat | Download (ext.) | arXiv
 

2009 | Journal Article | LibreCat-ID: 8181 | OA
Datta, Animesh, and Sevag Gharibian. “Signatures of Nonclassicality in Mixed-State Quantum Computation.” Physical Review A, vol. 79, no. 4, American Physical Society (APS), 2009, doi:10.1103/physreva.79.042325.
LibreCat | DOI | Download (ext.) | arXiv
 

Filters and Search Terms

(person=71541)

status=public

Search

Filter Publications

Display / Sort

Citation Style: MLA

Export / Embed