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
Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
D. Rudolph, S. Gharibian, D. Nagaj, ArXiv:2401.02368 (2024).
LibreCat | arXiv
 

2024 | Journal Article | LibreCat-ID: 48544 | OA
Guest Column: The 7 faces of quantum NP
S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
LibreCat | Files available | Download (ext.)
 

2024 | Preprint | LibreCat-ID: 50273
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, ArXiv:2401.01633 (2024).
LibreCat | arXiv
 

2024 | Conference Paper | LibreCat-ID: 50406
BQP, meet NP: Search-to-decision reductions and approximate counting
S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), n.d.
LibreCat | arXiv
 

2023 | Conference Paper | LibreCat-ID: 31872
Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
S. Gharibian, D. Rudolph, in: 14th Innovations in Theoretical Computer Science (ITCS), 2023, p. 53:1-53:23.
LibreCat | DOI | arXiv
 

2023 | Conference Paper | LibreCat-ID: 20841 | OA
The Complexity of Translationally Invariant Problems beyond Ground State Energies
S. Gharibian, J. Watson, J. Bausch, in: Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 2023, p. 54:1-54:21.
LibreCat | DOI | Download (ext.) | arXiv
 

2023 | Conference Paper | LibreCat-ID: 34138
The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate
L. Bittel, S. Gharibian, M. Kliesch, in: Proceedings of the 38th Computational Complexity Conference (CCC), 2023, p. 34:1-34:24.
LibreCat | DOI | arXiv
 

2023 | Conference Paper | LibreCat-ID: 32407
Improved Hardness Results for the Guided Local Hamiltonian Problem
S. Gharibian, R. Hayakawa, F.L. Gall, T. Morimae, in: Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2023, pp. 1–19.
LibreCat | DOI | arXiv
 

2023 | Journal Article | LibreCat-ID: 50271
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
S. Gharibian, F. Le Gall, SIAM Journal on Computing 52 (2023) 1009–1038.
LibreCat | DOI
 

2022 | Journal Article | LibreCat-ID: 34700
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, Computational Complexity 31 (2022).
LibreCat | DOI
 

2022 | Conference Paper | LibreCat-ID: 27160 | OA
On polynomially many queries to NP or QMA oracles
S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, pp. 1–27.
LibreCat | DOI | Download (ext.)
 

2022 | Conference Paper | LibreCat-ID: 27531 | OA
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
S. Gharibian, F.L. Gall, in: 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
Towards Quantum One-Time Memories from Stateless Hardware
A. Broadbent, S. Gharibian, H.-S. Zhou, Quantum 5 (2021).
LibreCat | DOI
 

2020 | Conference Paper | LibreCat-ID: 8426
Towards Quantum One-Time Memories from Stateless Hardware
A. Broadbent, S. Gharibian, H.-S. Zhou, in: Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), Leibniz International Proceedings in Informatics (LIPIcs), 2020, p. 6:1-6:25.
LibreCat | Download (ext.) | arXiv
 

2020 | Journal Article | LibreCat-ID: 16927 | OA
On efficiently solvable cases of Quantum k-SAT
S. Gharibian, M. Aldi, N. de Beaudrap, S. Saeedi, Communications in Mathematical Physics (2020).
LibreCat | Download (ext.) | arXiv
 

2020 | Conference Paper | LibreCat-ID: 13226 | OA
Oracle complexity classes and local measurements on physical Hamiltonians
S. Gharibian, S. Piddock, J. Yirka, in: 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
Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut
S. Gharibian, O. Parekh, in: Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2019, p. 31:1-31:17.
LibreCat | DOI | Download (ext.)
 

2019 | Journal Article | LibreCat-ID: 13558 | OA
The complexity of simulating local measurements on quantum systems
S. Gharibian, J. Yirka, Quantum 3 (2019) 189.
LibreCat | DOI | Download (ext.)
 

2018 | Conference Paper | LibreCat-ID: 8162 | OA
On Efficiently Solvable Cases of Quantum k-SAT
M. Aldi, N. de Beaudrap, S. Gharibian, S. Saeedi, in: I. Potapov, P. Spirakis, J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 38:1-38:16.
LibreCat | DOI | Download (ext.) | arXiv
 

2018 | Conference Paper | LibreCat-ID: 8161 | OA
Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, in: I. Potapov, P. Spirakis, J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 58:1-58:16.
LibreCat | DOI | Download (ext.) | arXiv
 

2018 | Conference Paper | LibreCat-ID: 8160 | OA
The Complexity of Simulating Local Measurements on Quantum Systems
S. Gharibian, J. Yirka, in: M. Wilde (Ed.), 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 2:1-2:17.
LibreCat | DOI | Download (ext.) | arXiv
 

2018 | Journal Article | LibreCat-ID: 8167 | OA
Ground State Connectivity of Local Hamiltonians
S. Gharibian, J. Sikora, ACM Transactions on Computation Theory (TOCT) 10 (2018) 8:1-8:28.
LibreCat | DOI | Download (ext.) | arXiv
 

2016 | Conference Paper | LibreCat-ID: 8159 | OA
A Linear Time Algorithm for Quantum 2-SAT
N. de Beaudrap, S. Gharibian, in: R. Raz (Ed.), Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016, p. 27:1–17:21.
LibreCat | DOI | Download (ext.) | arXiv
 

2015 | Conference Paper | LibreCat-ID: 8164 | OA
Ground State Connectivity of Local Hamiltonians
S. Gharibian, J. Sikora, in: M.M. Halld{\’o}rsson, K. Iwama, N. Kobayashi, B. Speckmann (Eds.), International Colloquium on Automata, Languages, and Programming (ICALP 2015), Springer Berlin Heidelberg, Berlin, Heidelberg, 2015, pp. 617–628.
LibreCat | DOI | Download (ext.) | arXiv
 

2015 | Journal Article | LibreCat-ID: 8166 | OA
Quantum Hamiltonian Complexity
S. Gharibian, Y. Huang, Z. Landau, S. Woo Shin, Foundations and Trends® in Theoretical Computer Science 10 (2015) 159–282.
LibreCat | DOI | Download (ext.) | arXiv
 

2015 | Journal Article | LibreCat-ID: 8168 | OA
Tensor network non-zero testing
S. Gharibian, Z. Landau, S. Woo Shin, G. Wang, Quantum Information & Computation 15 (2015) 885–899.
LibreCat | Download (ext.) | arXiv
 

2014 | Journal Article | LibreCat-ID: 8171 | OA
Hardness of approximation for quantum problems
S. Gharibian, J. Kempe, Quantum Information & Computation 14 (2014) 517–540.
LibreCat | Download (ext.) | arXiv
 

2014 | Journal Article | LibreCat-ID: 8172 | OA
Gate-efficient discrete simulations of continuous-time quantum query algorithms
D. W. Berry, R. Cleve, S. Gharibian, Quantum Information & Computation 14 (2014) 1–30.
LibreCat | Download (ext.) | arXiv
 

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

2013 | Journal Article | LibreCat-ID: 8173 | OA
QMA variants with polynomially many provers
S. Gharibian, J. Sikora, S. Upadhyay, Quantum Information & Computation 13 (2013) 135–157.
LibreCat | Download (ext.) | arXiv
 

2012 | Conference Paper | LibreCat-ID: 8169 | OA
Hardness of Approximation for Quantum Problems
S. Gharibian, J. Kempe, in: A. Czumaj, K. Mehlhorn, A. Pitts, R. Wattenhofer (Eds.), International Colloquium on Automata, Languages, and Programming (ICALP 2012), Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 387–398.
LibreCat | DOI | Download (ext.) | arXiv
 

2012 | Journal Article | LibreCat-ID: 8175 | OA
Approximation Algorithms for QMA-Complete Problems
S. Gharibian, J. Kempe, SIAM Journal on Computing 41 (2012) 1028–1050.
LibreCat | DOI | Download (ext.) | arXiv
 

2012 | Journal Article | LibreCat-ID: 8174 | OA
Quantifying nonclassicality with local unitary operations
S. Gharibian, Physical Review A 86 (2012) 042106.
LibreCat | DOI | Download (ext.) | arXiv
 

2011 | Journal Article | LibreCat-ID: 8178 | OA
Characterizing Quantumness via Entanglement Creation
S. Gharibian, M. PIANI, G. ADESSO, J. CALSAMIGLIA, P. HORODECKI, International Journal of Quantum Information 09 (2011) 1701–1713.
LibreCat | DOI | Download (ext.) | arXiv
 

2011 | Conference Paper | LibreCat-ID: 8176 | OA
Approximation Algorithms for QMA-Complete Problems
S. Gharibian, J. Kempe, in: IEEE Annual Conference on Computational Complexity (CCC 2011), IEEE, 2011.
LibreCat | DOI | Download (ext.) | arXiv
 

2011 | Journal Article | LibreCat-ID: 8177 | OA
All Nonclassical Correlations Can Be Activated into Distillable Entanglement
M. Piani, S. Gharibian, G. Adesso, J. Calsamiglia, P. Horodecki, A. Winter, Physical Review Letters 106 (2011).
LibreCat | DOI | Download (ext.) | arXiv
 

2010 | Journal Article | LibreCat-ID: 8179 | OA
Strong NP-hardness of the quantum separability problem
S. Gharibian, Quantum Information & Computation 10 (2010) 343–360.
LibreCat | Download (ext.) | arXiv
 

2009 | Journal Article | LibreCat-ID: 8180 | OA
On global effects caused by locally noneffective unitary operations
S. Gharibian, H. Kampermann, D. Bru{\ss}, Quantum Information & Computation 9 (2009) 1013–1029.
LibreCat | Download (ext.) | arXiv
 

2009 | Journal Article | LibreCat-ID: 8181 | OA
Signatures of nonclassicality in mixed-state quantum computation
A. Datta, S. Gharibian, Physical Review A 79 (2009).
LibreCat | DOI | Download (ext.) | arXiv
 

Filters and Search Terms

(person=71541)

status=public

Search

Filter Publications

Display / Sort

Export / Embed