Sevag Gharibian

sevag.gharibian@uni-paderborn.de
ID
71541

52 Publications

Mark all

[52]
2026 | Conference Paper | LibreCat-ID: 61922
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, in: SIAM Symposium on Simplicity in Algorithms (SOSA), n.d., pp. 247–253.
LibreCat | arXiv
 
[51]
2026 | Conference Paper | LibreCat-ID: 57866
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
M. Aldi, S. Gharibian, D. Rudolph, in: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), 2026, p. 7:1-7:24.
LibreCat | arXiv
 
[50]
2026 | Preprint | LibreCat-ID: 67088
Semidefinite extension complexity of the separable set, with applications to approximate disentanglers
S. Gharibian, C. Hecht, D. Rudolph, ArXiv:2609.09033 (n.d.).
LibreCat | arXiv
 
[49]
2026 | Preprint | LibreCat-ID: 67292
Verification Complexity and Extension of Classical Shadows
G. Karaiskos, A. Raza, D. Rudolph, D.E. Koh, S. Gharibian, ArXiv:2609.40107 (2026).
LibreCat | arXiv
 
[48]
2026 | Preprint | LibreCat-ID: 67293
Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
S. Gharibian, F. Le Gall, R. Mataraarachchi, S. Tamaki, (2026).
LibreCat
 
[47]
2026 | Preprint | LibreCat-ID: 67291
A physical and universal model of bosonic computations with Solovay-Kitaev theorem
D. Rudolph, A. Motamedi, D. Sambrani, H. Reza Naeij, U. Chabaud, S. Gharibian, S. Mehraban, (n.d.).
LibreCat
 
[46]
2026 | Conference Paper | LibreCat-ID: 61777
How hard is it to verify a classical shadow?
G. Karaiskos, D. Rudolph, J.J. Meyer, J. Eisert, S. Gharibian, in: International Colloquium on Automata, Languages, and Programming (ICALP), 2026, pp. 1–23.
LibreCat | arXiv
 
[45]
2026 | Conference Paper | LibreCat-ID: 56950
Hardness of approximation for ground state problems
S. Gharibian, C. Hecht, in: 51st International Symposium on Mathematical Foundations of Computer Science (MFCS), n.d., pp. 1–19.
LibreCat | arXiv
 
[44]
2025 | Preprint | LibreCat-ID: 61778
On the complexity of estimating ground state entanglement and free energy
S. Gharibian, J. Kamminga, ArXiv:2510.06796 (2025).
LibreCat | arXiv
 
[43]
2025 | Conference Paper | 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, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 1–24.
LibreCat | DOI | arXiv
 
[42]
2025 | Journal Article | LibreCat-ID: 55037
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.
LibreCat | DOI | arXiv
 
[41]
2025 | Preprint | LibreCat-ID: 61776
Energy, Bosons and Computational Complexity
U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H.R. Naeij, D. Rudolph, D. Sambrani, ArXiv:2510.08545 (2025).
LibreCat | arXiv
 
[40]
2025 | Preprint | LibreCat-ID: 60432
Quantum k-SAT Related Hypergraph Problems
S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
LibreCat | arXiv
 
[39]
2024 | Conference Paper | LibreCat-ID: 50273
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.
LibreCat | DOI | arXiv
 
[38]
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), 2024, pp. 1–19.
LibreCat | arXiv
 
[37]
2024 | Preprint | LibreCat-ID: 56944
Second order cone relaxations for quantum Max Cut
F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).
LibreCat | arXiv
 
[36]
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.)
 
[35]
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
 
[34]
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
 
[33]
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
 
[32]
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
 
[31]
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
 
[30]
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
 
[29]
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
 
[28]
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.)
 
[27]
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
 
[26]
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
 
[25]
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
 
[24]
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
 
[23]
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.)
 
[22]
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.)
 
[21]
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
 
[20]
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
 
[19]
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
 
[18]
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
 
[17]
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
 
[16]
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
 
[15]
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
 
[14]
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
 
[13]
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
 
[12]
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
 
[11]
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
 
[10]
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
 
[9]
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
 
[8]
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
 
[7]
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
 
[6]
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
 
[5]
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
 
[4]
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
 
[3]
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
 
[2]
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
 
[1]
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
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Export / Embed

52 Publications

Mark all

[52]
2026 | Conference Paper | LibreCat-ID: 61922
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, in: SIAM Symposium on Simplicity in Algorithms (SOSA), n.d., pp. 247–253.
LibreCat | arXiv
 
[51]
2026 | Conference Paper | LibreCat-ID: 57866
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
M. Aldi, S. Gharibian, D. Rudolph, in: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), 2026, p. 7:1-7:24.
LibreCat | arXiv
 
[50]
2026 | Preprint | LibreCat-ID: 67088
Semidefinite extension complexity of the separable set, with applications to approximate disentanglers
S. Gharibian, C. Hecht, D. Rudolph, ArXiv:2609.09033 (n.d.).
LibreCat | arXiv
 
[49]
2026 | Preprint | LibreCat-ID: 67292
Verification Complexity and Extension of Classical Shadows
G. Karaiskos, A. Raza, D. Rudolph, D.E. Koh, S. Gharibian, ArXiv:2609.40107 (2026).
LibreCat | arXiv
 
[48]
2026 | Preprint | LibreCat-ID: 67293
Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
S. Gharibian, F. Le Gall, R. Mataraarachchi, S. Tamaki, (2026).
LibreCat
 
[47]
2026 | Preprint | LibreCat-ID: 67291
A physical and universal model of bosonic computations with Solovay-Kitaev theorem
D. Rudolph, A. Motamedi, D. Sambrani, H. Reza Naeij, U. Chabaud, S. Gharibian, S. Mehraban, (n.d.).
LibreCat
 
[46]
2026 | Conference Paper | LibreCat-ID: 61777
How hard is it to verify a classical shadow?
G. Karaiskos, D. Rudolph, J.J. Meyer, J. Eisert, S. Gharibian, in: International Colloquium on Automata, Languages, and Programming (ICALP), 2026, pp. 1–23.
LibreCat | arXiv
 
[45]
2026 | Conference Paper | LibreCat-ID: 56950
Hardness of approximation for ground state problems
S. Gharibian, C. Hecht, in: 51st International Symposium on Mathematical Foundations of Computer Science (MFCS), n.d., pp. 1–19.
LibreCat | arXiv
 
[44]
2025 | Preprint | LibreCat-ID: 61778
On the complexity of estimating ground state entanglement and free energy
S. Gharibian, J. Kamminga, ArXiv:2510.06796 (2025).
LibreCat | arXiv
 
[43]
2025 | Conference Paper | 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, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 1–24.
LibreCat | DOI | arXiv
 
[42]
2025 | Journal Article | LibreCat-ID: 55037
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.
LibreCat | DOI | arXiv
 
[41]
2025 | Preprint | LibreCat-ID: 61776
Energy, Bosons and Computational Complexity
U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H.R. Naeij, D. Rudolph, D. Sambrani, ArXiv:2510.08545 (2025).
LibreCat | arXiv
 
[40]
2025 | Preprint | LibreCat-ID: 60432
Quantum k-SAT Related Hypergraph Problems
S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
LibreCat | arXiv
 
[39]
2024 | Conference Paper | LibreCat-ID: 50273
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.
LibreCat | DOI | arXiv
 
[38]
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), 2024, pp. 1–19.
LibreCat | arXiv
 
[37]
2024 | Preprint | LibreCat-ID: 56944
Second order cone relaxations for quantum Max Cut
F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).
LibreCat | arXiv
 
[36]
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.)
 
[35]
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
 
[34]
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
 
[33]
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
 
[32]
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
 
[31]
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
 
[30]
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
 
[29]
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
 
[28]
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.)
 
[27]
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
 
[26]
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
 
[25]
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
 
[24]
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
 
[23]
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.)
 
[22]
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.)
 
[21]
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
 
[20]
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
 
[19]
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
 
[18]
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
 
[17]
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
 
[16]
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
 
[15]
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
 
[14]
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
 
[13]
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
 
[12]
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
 
[11]
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
 
[10]
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
 
[9]
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
 
[8]
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
 
[7]
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
 
[6]
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
 
[5]
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
 
[4]
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
 
[3]
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
 
[2]
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
 
[1]
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
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Export / Embed