Preprints
Quantum k-SAT Related Hypergraph Problems
S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
Hardness of approximation for ground state problems
S. Gharibian, C. Hecht, ArXiv:2411.04874 (2024).
Second order cone relaxations for quantum Max Cut
F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
M. Aldi, S. Gharibian, D. Rudolph, ArXiv:2412.19623 (n.d.).
Show all publications
Publications
2025
Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 1–24.
Beating Grover search for low-energy estimation and state preparation
H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, Physical Review Letters 135 (2025) 030601.
2024
Guest Column: The 7 faces of quantum NP
S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
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), 2024, pp. 1–19.
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, in: Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2024, pp. 7–17.
2023
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.
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.
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.
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.
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.
2022
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.
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).
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.
2021
Towards Quantum One-Time Memories from Stateless Hardware
A. Broadbent, S. Gharibian, H.-S. Zhou, Quantum 5 (2021).
2020
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.
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.
On efficiently solvable cases of Quantum k-SAT
S. Gharibian, M. Aldi, N. de Beaudrap, S. Saeedi, Communications in Mathematical Physics (2020).
2019
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.
The complexity of simulating local measurements on quantum systems
S. Gharibian, J. Yirka, Quantum 3 (2019) 189.
2018
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.
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.
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.
Ground State Connectivity of Local Hamiltonians
S. Gharibian, J. Sikora, ACM Transactions on Computation Theory (TOCT) 10 (2018) 8:1-8:28.
2016
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.
2015
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.
Quantum Hamiltonian Complexity
S. Gharibian, Y. Huang, Z. Landau, S. Woo Shin, Foundations and Trends® in Theoretical Computer Science 10 (2015) 159–282.
Tensor network non-zero testing
S. Gharibian, Z. Landau, S. Woo Shin, G. Wang, Quantum Information & Computation 15 (2015) 885–899.
2014
Hardness of approximation for quantum problems
S. Gharibian, J. Kempe, Quantum Information & Computation 14 (2014) 517–540.
Gate-efficient discrete simulations of continuous-time quantum query algorithms
D. W. Berry, R. Cleve, S. Gharibian, Quantum Information & Computation 14 (2014) 1–30.
2013
Approximation, Proof Systems, and Correlations in a Quantum World
S. Gharibian, Approximation, Proof Systems, and Correlations in a Quantum World, 2013.
QMA variants with polynomially many provers
S. Gharibian, J. Sikora, S. Upadhyay, Quantum Information & Computation 13 (2013) 135–157.
2012
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.
Approximation Algorithms for QMA-Complete Problems
S. Gharibian, J. Kempe, SIAM Journal on Computing 41 (2012) 1028–1050.
Quantifying nonclassicality with local unitary operations
S. Gharibian, Physical Review A 86 (2012) 042106.
2011
Characterizing Quantumness via Entanglement Creation
S. Gharibian, M. PIANI, G. ADESSO, J. CALSAMIGLIA, P. HORODECKI, International Journal of Quantum Information 09 (2011) 1701–1713.
Approximation Algorithms for QMA-Complete Problems
S. Gharibian, J. Kempe, in: IEEE Annual Conference on Computational Complexity (CCC 2011), IEEE, 2011.
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).
2010
Strong NP-hardness of the quantum separability problem
S. Gharibian, Quantum Information & Computation 10 (2010) 343–360.
2009
On global effects caused by locally noneffective unitary operations
S. Gharibian, H. Kampermann, D. Bru{\ss}, Quantum Information & Computation 9 (2009) 1013–1029.
Signatures of nonclassicality in mixed-state quantum computation
A. Datta, S. Gharibian, Physical Review A 79 (2009).
Show all publications