Sevag Gharibian

sevag.gharibian@uni-paderborn.de
ID
71541

43 Publications

Mark all

[43]
2025 | Conference Paper | LibreCat-ID: 50272
D. Rudolph, S. Gharibian, and D. Nagaj, “Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete:  Direct embeddings and black-box simulation,” in 16th Innovations in Theoretical Computer Science (ITCS), 2025, vol. 325, no. 85, pp. 1–24, doi: 10.4230/LIPIcs.ITCS.2025.85.
LibreCat | DOI | arXiv
 
[42]
2024 | Journal Article | LibreCat-ID: 48544 | OA
S. Gharibian, “Guest Column: The 7 faces of quantum NP,” ACM SIGACT News, vol. 54, no. 4, pp. 54–91, 2024.
LibreCat | Files available | Download (ext.)
 
[41]
2024 | Conference Paper | LibreCat-ID: 50406
S. Gharibian and J. Kamminga, “BQP, meet NP: Search-to-decision reductions and approximate counting,” in Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2024, vol. 297, no. 70, pp. 1–19.
LibreCat | arXiv
 
[40]
2024 | Preprint | LibreCat-ID: 55037
H. Buhrman, S. Gharibian, Z. Landau, F. L. Gall, N. Schuch, and S. Tamaki, “Beating Grover search for low-energy estimation and state preparation,” arXiv:2407.03073. 2024.
LibreCat | arXiv
 
[39]
2024 | Conference Paper | LibreCat-ID: 50273
A. Agarwal, S. Gharibian, V. Koppula, and D. Rudolph, “Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds,” in Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2024, vol. 306, no. 7, pp. 7–17, doi: 10.4230/LIPIcs.MFCS.2024.7.
LibreCat | DOI | arXiv
 
[38]
2024 | Preprint | LibreCat-ID: 56950
S. Gharibian and C. Hecht, “Hardness of approximation for ground state problems,” arXiv:2411.04874. 2024.
LibreCat | arXiv
 
[37]
2024 | Preprint | LibreCat-ID: 56944
F. Huber, K. Thompson, O. Parekh, and S. Gharibian, “Second order cone relaxations for quantum Max Cut,” arXiv:2411.04120. 2024.
LibreCat | arXiv
 
[36]
2024 | Preprint | LibreCat-ID: 57866
M. Aldi, S. Gharibian, and D. Rudolph, “An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem,” arXiv:2412.19623. .
LibreCat | arXiv
 
[35]
2023 | Conference Paper | LibreCat-ID: 32407
S. Gharibian, R. Hayakawa, F. L. Gall, and T. Morimae, “Improved Hardness Results for the Guided Local Hamiltonian Problem,” in Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2023, vol. 261, no. 32, pp. 1–19, doi: 10.4230/LIPIcs.ICALP.2023.32.
LibreCat | DOI | arXiv
 
[34]
2023 | Journal Article | LibreCat-ID: 50271
S. Gharibian and F. 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, pp. 1009–1038, 2023, doi: 10.1137/22m1513721.
LibreCat | DOI
 
[33]
2023 | Conference Paper | LibreCat-ID: 31872
S. Gharibian and D. Rudolph, “Quantum space, ground space traversal, and how to embed multi-prover  interactive proofs into unentanglement,” in 14th Innovations in Theoretical Computer Science (ITCS), 2023, vol. 251, p. 53:1-53:23, doi: 10.4230/LIPIcs.ITCS.2023.53.
LibreCat | DOI | arXiv
 
[32]
2023 | Conference Paper | LibreCat-ID: 20841 | OA
S. Gharibian, J. Watson, and J. Bausch, “The Complexity of Translationally Invariant Problems beyond Ground State Energies,” in Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 2023, vol. 254, p. 54:1-54:21, doi: https://doi.org/10.4230/LIPIcs.STACS.2023.54.
LibreCat | DOI | Download (ext.) | arXiv
 
[31]
2023 | Conference Paper | LibreCat-ID: 34138
L. Bittel, S. Gharibian, and M. Kliesch, “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate,” in Proceedings of the 38th Computational Complexity Conference (CCC), 2023, vol. 264, no. 34, p. 34:1-34:24, doi: 10.4230/LIPIcs.CCC.2023.34.
LibreCat | DOI | arXiv
 
[30]
2022 | Conference Paper | LibreCat-ID: 27531 | OA
S. Gharibian and F. L. Gall, “Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture,” 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
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka, “Quantum generalizations of the polynomial hierarchy with applications to QMA(2),” Computational Complexity, vol. 31, no. 2, Art. no. 13, 2022, doi: 10.1007/s00037-022-00231-8.
LibreCat | DOI
 
[28]
2022 | Conference Paper | LibreCat-ID: 27160 | OA
S. Gharibian and D. Rudolph, “On polynomially many queries to NP or QMA oracles,” in 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, vol. 215, no. 75, pp. 1–27, doi: 10.4230/LIPIcs.ITCS.2022.75.
LibreCat | DOI | Download (ext.)
 
[27]
2021 | Journal Article | LibreCat-ID: 29780
A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories from Stateless Hardware,” Quantum, vol. 5, Art. no. 429, 2021, doi: 10.22331/q-2021-04-08-429.
LibreCat | DOI
 
[26]
2020 | Conference Paper | LibreCat-ID: 13226 | OA
S. Gharibian, S. Piddock, and J. Yirka, “Oracle complexity classes and local measurements on physical  Hamiltonians,” 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
A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories from Stateless Hardware,” in Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 2020, vol. 158, p. 6:1-6:25.
LibreCat | Download (ext.) | arXiv
 
[24]
2020 | Journal Article | LibreCat-ID: 16927 | OA
S. Gharibian, M. Aldi, N. de Beaudrap, and S. Saeedi, “On efficiently solvable cases of Quantum k-SAT,” Communications in Mathematical Physics, 2020.
LibreCat | Download (ext.) | arXiv
 
[23]
2019 | Conference Paper | LibreCat-ID: 13297 | OA
S. Gharibian and O. Parekh, “Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut,” in Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2019, vol. 145, p. 31:1-31:17, doi: 10.4230/LIPICS.APPROX-RANDOM.2019.31.
LibreCat | DOI | Download (ext.)
 
[22]
2019 | Journal Article | LibreCat-ID: 13558 | OA
S. Gharibian and J. Yirka, “The complexity of simulating local measurements on quantum systems,” Quantum, vol. 3, p. 189, 2019, doi: 10.22331/q-2019-09-30-189.
LibreCat | DOI | Download (ext.)
 
[21]
2018 | Conference Paper | LibreCat-ID: 8162 | OA
M. Aldi, N. de Beaudrap, S. Gharibian, and S. Saeedi, “On Efficiently Solvable Cases of Quantum k-SAT,” in 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Liverpool, UK, 2018, vol. 117, p. 38:1-38:16, doi: 10.4230/LIPIcs.MFCS.2018.38.
LibreCat | DOI | Download (ext.) | arXiv
 
[20]
2018 | Conference Paper | LibreCat-ID: 8161 | OA
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka, “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2),” in 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Liverpool, UK, 2018, vol. 117, p. 58:1-58:16, doi: 10.4230/LIPIcs.MFCS.2018.58.
LibreCat | DOI | Download (ext.) | arXiv
 
[19]
2018 | Conference Paper | LibreCat-ID: 8160 | OA
S. Gharibian and J. Yirka, “The Complexity of Simulating Local Measurements on Quantum Systems,” in 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), Paris, France, 2018, vol. 73, p. 2:1-2:17, doi: 10.4230/LIPIcs.TQC.2017.2.
LibreCat | DOI | Download (ext.) | arXiv
 
[18]
2018 | Journal Article | LibreCat-ID: 8167 | OA
S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,” ACM Transactions on Computation Theory (TOCT), vol. 10, no. 2, p. 8:1-8:28, 2018, doi: 10.1145/3186587.
LibreCat | DOI | Download (ext.) | arXiv
 
[17]
2016 | Conference Paper | LibreCat-ID: 8159 | OA
N. de Beaudrap and S. Gharibian, “A Linear Time Algorithm for Quantum 2-SAT,” in Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Tokyo, Japan, 2016, vol. 50, p. 27:1–17:21, doi: 10.4230/LIPIcs.CCC.2016.27.
LibreCat | DOI | Download (ext.) | arXiv
 
[16]
2015 | Conference Paper | LibreCat-ID: 8164 | OA
S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,” in International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015, pp. 617–628, doi: 10.1007/978-3-662-47672-7_50.
LibreCat | DOI | Download (ext.) | arXiv
 
[15]
2015 | Journal Article | LibreCat-ID: 8166 | OA
S. Gharibian, Y. Huang, Z. Landau, and S. Woo Shin, “Quantum Hamiltonian Complexity,” Foundations and Trends® in Theoretical Computer Science, vol. 10, no. 3, pp. 159–282, 2015, doi: 10.1561/0400000066.
LibreCat | DOI | Download (ext.) | arXiv
 
[14]
2015 | Journal Article | LibreCat-ID: 8168 | OA
S. Gharibian, Z. Landau, S. Woo Shin, and G. Wang, “Tensor network non-zero testing,” Quantum Information & Computation, vol. 15, no. 9{\ & }10, pp. 885–899, 2015.
LibreCat | Download (ext.) | arXiv
 
[13]
2014 | Journal Article | LibreCat-ID: 8171 | OA
S. Gharibian and J. Kempe, “Hardness of approximation for quantum problems,” Quantum Information & Computation, vol. 14, no. 5–6, pp. 517–540, 2014.
LibreCat | Download (ext.) | arXiv
 
[12]
2014 | Journal Article | LibreCat-ID: 8172 | OA
D. W. Berry, R. Cleve, and S. Gharibian, “Gate-efficient discrete simulations of continuous-time quantum query algorithms,” Quantum Information & Computation, vol. 14, no. 1–2, pp. 1–30, 2014.
LibreCat | Download (ext.) | arXiv
 
[11]
2013 | Dissertation | LibreCat-ID: 8425 | OA
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
S. Gharibian, J. Sikora, and S. Upadhyay, “QMA variants with polynomially many provers,” Quantum Information & Computation, vol. 13, no. 1–2, pp. 135–157, 2013.
LibreCat | Download (ext.) | arXiv
 
[9]
2012 | Conference Paper | LibreCat-ID: 8169 | OA
S. Gharibian and J. Kempe, “Hardness of Approximation for Quantum Problems,” in International Colloquium on Automata, Languages, and Programming (ICALP 2012), Warwick, UK, 2012, pp. 387–398, doi: 10.1007/978-3-642-31594-7_33.
LibreCat | DOI | Download (ext.) | arXiv
 
[8]
2012 | Journal Article | LibreCat-ID: 8175 | OA
S. Gharibian and J. Kempe, “Approximation Algorithms for QMA-Complete Problems,” SIAM Journal on Computing, vol. 41, no. 4, pp. 1028–1050, 2012, doi: 10.1137/110842272.
LibreCat | DOI | Download (ext.) | arXiv
 
[7]
2012 | Journal Article | LibreCat-ID: 8174 | OA
S. Gharibian, “Quantifying nonclassicality with local unitary operations,” Physical Review A, vol. 86, p. 042106, 2012, doi: 10.1103/PhysRevA.86.042106.
LibreCat | DOI | Download (ext.) | arXiv
 
[6]
2011 | Journal Article | LibreCat-ID: 8178 | OA
S. Gharibian, M. PIANI, G. ADESSO, J. CALSAMIGLIA, and P. HORODECKI, “Characterizing Quantumness via Entanglement Creation,” International Journal of Quantum Information, vol. 09, no. 07n08, pp. 1701–1713, 2011, doi: 10.1142/s0219749911008258.
LibreCat | DOI | Download (ext.) | arXiv
 
[5]
2011 | Conference Paper | LibreCat-ID: 8176 | OA
S. Gharibian and J. Kempe, “Approximation Algorithms for QMA-Complete Problems,” presented at the 2011 IEEE 26th Annual Conference on Computational Complexity (CCC), San Jose, USA, 2011, doi: 10.1109/ccc.2011.15.
LibreCat | DOI | Download (ext.) | arXiv
 
[4]
2011 | Journal Article | LibreCat-ID: 8177 | OA
M. Piani, S. Gharibian, G. Adesso, J. Calsamiglia, P. Horodecki, and A. Winter, “All Nonclassical Correlations Can Be Activated into Distillable Entanglement,” Physical Review Letters, vol. 106, no. 22, 2011, doi: 10.1103/physrevlett.106.220403.
LibreCat | DOI | Download (ext.) | arXiv
 
[3]
2010 | Journal Article | LibreCat-ID: 8179 | OA
S. Gharibian, “Strong NP-hardness of the quantum separability problem,” Quantum Information & Computation, vol. 10, no. 3{\ & }4, pp. 343–360, 2010.
LibreCat | Download (ext.) | arXiv
 
[2]
2009 | Journal Article | LibreCat-ID: 8180 | OA
S. Gharibian, H. Kampermann, and D. Bru{\ss}, “On global effects caused by locally noneffective unitary operations,” Quantum Information & Computation, vol. 9, no. 11, pp. 1013–1029, 2009.
LibreCat | Download (ext.) | arXiv
 
[1]
2009 | Journal Article | LibreCat-ID: 8181 | OA
A. Datta and S. Gharibian, “Signatures of nonclassicality in mixed-state quantum computation,” Physical Review A, vol. 79, no. 4, 2009, doi: 10.1103/physreva.79.042325.
LibreCat | DOI | Download (ext.) | arXiv
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Citation Style: IEEE

Export / Embed

43 Publications

Mark all

[43]
2025 | Conference Paper | LibreCat-ID: 50272
D. Rudolph, S. Gharibian, and D. Nagaj, “Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete:  Direct embeddings and black-box simulation,” in 16th Innovations in Theoretical Computer Science (ITCS), 2025, vol. 325, no. 85, pp. 1–24, doi: 10.4230/LIPIcs.ITCS.2025.85.
LibreCat | DOI | arXiv
 
[42]
2024 | Journal Article | LibreCat-ID: 48544 | OA
S. Gharibian, “Guest Column: The 7 faces of quantum NP,” ACM SIGACT News, vol. 54, no. 4, pp. 54–91, 2024.
LibreCat | Files available | Download (ext.)
 
[41]
2024 | Conference Paper | LibreCat-ID: 50406
S. Gharibian and J. Kamminga, “BQP, meet NP: Search-to-decision reductions and approximate counting,” in Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2024, vol. 297, no. 70, pp. 1–19.
LibreCat | arXiv
 
[40]
2024 | Preprint | LibreCat-ID: 55037
H. Buhrman, S. Gharibian, Z. Landau, F. L. Gall, N. Schuch, and S. Tamaki, “Beating Grover search for low-energy estimation and state preparation,” arXiv:2407.03073. 2024.
LibreCat | arXiv
 
[39]
2024 | Conference Paper | LibreCat-ID: 50273
A. Agarwal, S. Gharibian, V. Koppula, and D. Rudolph, “Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds,” in Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2024, vol. 306, no. 7, pp. 7–17, doi: 10.4230/LIPIcs.MFCS.2024.7.
LibreCat | DOI | arXiv
 
[38]
2024 | Preprint | LibreCat-ID: 56950
S. Gharibian and C. Hecht, “Hardness of approximation for ground state problems,” arXiv:2411.04874. 2024.
LibreCat | arXiv
 
[37]
2024 | Preprint | LibreCat-ID: 56944
F. Huber, K. Thompson, O. Parekh, and S. Gharibian, “Second order cone relaxations for quantum Max Cut,” arXiv:2411.04120. 2024.
LibreCat | arXiv
 
[36]
2024 | Preprint | LibreCat-ID: 57866
M. Aldi, S. Gharibian, and D. Rudolph, “An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem,” arXiv:2412.19623. .
LibreCat | arXiv
 
[35]
2023 | Conference Paper | LibreCat-ID: 32407
S. Gharibian, R. Hayakawa, F. L. Gall, and T. Morimae, “Improved Hardness Results for the Guided Local Hamiltonian Problem,” in Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2023, vol. 261, no. 32, pp. 1–19, doi: 10.4230/LIPIcs.ICALP.2023.32.
LibreCat | DOI | arXiv
 
[34]
2023 | Journal Article | LibreCat-ID: 50271
S. Gharibian and F. 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, pp. 1009–1038, 2023, doi: 10.1137/22m1513721.
LibreCat | DOI
 
[33]
2023 | Conference Paper | LibreCat-ID: 31872
S. Gharibian and D. Rudolph, “Quantum space, ground space traversal, and how to embed multi-prover  interactive proofs into unentanglement,” in 14th Innovations in Theoretical Computer Science (ITCS), 2023, vol. 251, p. 53:1-53:23, doi: 10.4230/LIPIcs.ITCS.2023.53.
LibreCat | DOI | arXiv
 
[32]
2023 | Conference Paper | LibreCat-ID: 20841 | OA
S. Gharibian, J. Watson, and J. Bausch, “The Complexity of Translationally Invariant Problems beyond Ground State Energies,” in Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 2023, vol. 254, p. 54:1-54:21, doi: https://doi.org/10.4230/LIPIcs.STACS.2023.54.
LibreCat | DOI | Download (ext.) | arXiv
 
[31]
2023 | Conference Paper | LibreCat-ID: 34138
L. Bittel, S. Gharibian, and M. Kliesch, “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate,” in Proceedings of the 38th Computational Complexity Conference (CCC), 2023, vol. 264, no. 34, p. 34:1-34:24, doi: 10.4230/LIPIcs.CCC.2023.34.
LibreCat | DOI | arXiv
 
[30]
2022 | Conference Paper | LibreCat-ID: 27531 | OA
S. Gharibian and F. L. Gall, “Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture,” 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
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka, “Quantum generalizations of the polynomial hierarchy with applications to QMA(2),” Computational Complexity, vol. 31, no. 2, Art. no. 13, 2022, doi: 10.1007/s00037-022-00231-8.
LibreCat | DOI
 
[28]
2022 | Conference Paper | LibreCat-ID: 27160 | OA
S. Gharibian and D. Rudolph, “On polynomially many queries to NP or QMA oracles,” in 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, vol. 215, no. 75, pp. 1–27, doi: 10.4230/LIPIcs.ITCS.2022.75.
LibreCat | DOI | Download (ext.)
 
[27]
2021 | Journal Article | LibreCat-ID: 29780
A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories from Stateless Hardware,” Quantum, vol. 5, Art. no. 429, 2021, doi: 10.22331/q-2021-04-08-429.
LibreCat | DOI
 
[26]
2020 | Conference Paper | LibreCat-ID: 13226 | OA
S. Gharibian, S. Piddock, and J. Yirka, “Oracle complexity classes and local measurements on physical  Hamiltonians,” 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
A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories from Stateless Hardware,” in Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 2020, vol. 158, p. 6:1-6:25.
LibreCat | Download (ext.) | arXiv
 
[24]
2020 | Journal Article | LibreCat-ID: 16927 | OA
S. Gharibian, M. Aldi, N. de Beaudrap, and S. Saeedi, “On efficiently solvable cases of Quantum k-SAT,” Communications in Mathematical Physics, 2020.
LibreCat | Download (ext.) | arXiv
 
[23]
2019 | Conference Paper | LibreCat-ID: 13297 | OA
S. Gharibian and O. Parekh, “Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut,” in Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2019, vol. 145, p. 31:1-31:17, doi: 10.4230/LIPICS.APPROX-RANDOM.2019.31.
LibreCat | DOI | Download (ext.)
 
[22]
2019 | Journal Article | LibreCat-ID: 13558 | OA
S. Gharibian and J. Yirka, “The complexity of simulating local measurements on quantum systems,” Quantum, vol. 3, p. 189, 2019, doi: 10.22331/q-2019-09-30-189.
LibreCat | DOI | Download (ext.)
 
[21]
2018 | Conference Paper | LibreCat-ID: 8162 | OA
M. Aldi, N. de Beaudrap, S. Gharibian, and S. Saeedi, “On Efficiently Solvable Cases of Quantum k-SAT,” in 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Liverpool, UK, 2018, vol. 117, p. 38:1-38:16, doi: 10.4230/LIPIcs.MFCS.2018.38.
LibreCat | DOI | Download (ext.) | arXiv
 
[20]
2018 | Conference Paper | LibreCat-ID: 8161 | OA
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka, “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2),” in 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Liverpool, UK, 2018, vol. 117, p. 58:1-58:16, doi: 10.4230/LIPIcs.MFCS.2018.58.
LibreCat | DOI | Download (ext.) | arXiv
 
[19]
2018 | Conference Paper | LibreCat-ID: 8160 | OA
S. Gharibian and J. Yirka, “The Complexity of Simulating Local Measurements on Quantum Systems,” in 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), Paris, France, 2018, vol. 73, p. 2:1-2:17, doi: 10.4230/LIPIcs.TQC.2017.2.
LibreCat | DOI | Download (ext.) | arXiv
 
[18]
2018 | Journal Article | LibreCat-ID: 8167 | OA
S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,” ACM Transactions on Computation Theory (TOCT), vol. 10, no. 2, p. 8:1-8:28, 2018, doi: 10.1145/3186587.
LibreCat | DOI | Download (ext.) | arXiv
 
[17]
2016 | Conference Paper | LibreCat-ID: 8159 | OA
N. de Beaudrap and S. Gharibian, “A Linear Time Algorithm for Quantum 2-SAT,” in Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Tokyo, Japan, 2016, vol. 50, p. 27:1–17:21, doi: 10.4230/LIPIcs.CCC.2016.27.
LibreCat | DOI | Download (ext.) | arXiv
 
[16]
2015 | Conference Paper | LibreCat-ID: 8164 | OA
S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,” in International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015, pp. 617–628, doi: 10.1007/978-3-662-47672-7_50.
LibreCat | DOI | Download (ext.) | arXiv
 
[15]
2015 | Journal Article | LibreCat-ID: 8166 | OA
S. Gharibian, Y. Huang, Z. Landau, and S. Woo Shin, “Quantum Hamiltonian Complexity,” Foundations and Trends® in Theoretical Computer Science, vol. 10, no. 3, pp. 159–282, 2015, doi: 10.1561/0400000066.
LibreCat | DOI | Download (ext.) | arXiv
 
[14]
2015 | Journal Article | LibreCat-ID: 8168 | OA
S. Gharibian, Z. Landau, S. Woo Shin, and G. Wang, “Tensor network non-zero testing,” Quantum Information & Computation, vol. 15, no. 9{\ & }10, pp. 885–899, 2015.
LibreCat | Download (ext.) | arXiv
 
[13]
2014 | Journal Article | LibreCat-ID: 8171 | OA
S. Gharibian and J. Kempe, “Hardness of approximation for quantum problems,” Quantum Information & Computation, vol. 14, no. 5–6, pp. 517–540, 2014.
LibreCat | Download (ext.) | arXiv
 
[12]
2014 | Journal Article | LibreCat-ID: 8172 | OA
D. W. Berry, R. Cleve, and S. Gharibian, “Gate-efficient discrete simulations of continuous-time quantum query algorithms,” Quantum Information & Computation, vol. 14, no. 1–2, pp. 1–30, 2014.
LibreCat | Download (ext.) | arXiv
 
[11]
2013 | Dissertation | LibreCat-ID: 8425 | OA
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
S. Gharibian, J. Sikora, and S. Upadhyay, “QMA variants with polynomially many provers,” Quantum Information & Computation, vol. 13, no. 1–2, pp. 135–157, 2013.
LibreCat | Download (ext.) | arXiv
 
[9]
2012 | Conference Paper | LibreCat-ID: 8169 | OA
S. Gharibian and J. Kempe, “Hardness of Approximation for Quantum Problems,” in International Colloquium on Automata, Languages, and Programming (ICALP 2012), Warwick, UK, 2012, pp. 387–398, doi: 10.1007/978-3-642-31594-7_33.
LibreCat | DOI | Download (ext.) | arXiv
 
[8]
2012 | Journal Article | LibreCat-ID: 8175 | OA
S. Gharibian and J. Kempe, “Approximation Algorithms for QMA-Complete Problems,” SIAM Journal on Computing, vol. 41, no. 4, pp. 1028–1050, 2012, doi: 10.1137/110842272.
LibreCat | DOI | Download (ext.) | arXiv
 
[7]
2012 | Journal Article | LibreCat-ID: 8174 | OA
S. Gharibian, “Quantifying nonclassicality with local unitary operations,” Physical Review A, vol. 86, p. 042106, 2012, doi: 10.1103/PhysRevA.86.042106.
LibreCat | DOI | Download (ext.) | arXiv
 
[6]
2011 | Journal Article | LibreCat-ID: 8178 | OA
S. Gharibian, M. PIANI, G. ADESSO, J. CALSAMIGLIA, and P. HORODECKI, “Characterizing Quantumness via Entanglement Creation,” International Journal of Quantum Information, vol. 09, no. 07n08, pp. 1701–1713, 2011, doi: 10.1142/s0219749911008258.
LibreCat | DOI | Download (ext.) | arXiv
 
[5]
2011 | Conference Paper | LibreCat-ID: 8176 | OA
S. Gharibian and J. Kempe, “Approximation Algorithms for QMA-Complete Problems,” presented at the 2011 IEEE 26th Annual Conference on Computational Complexity (CCC), San Jose, USA, 2011, doi: 10.1109/ccc.2011.15.
LibreCat | DOI | Download (ext.) | arXiv
 
[4]
2011 | Journal Article | LibreCat-ID: 8177 | OA
M. Piani, S. Gharibian, G. Adesso, J. Calsamiglia, P. Horodecki, and A. Winter, “All Nonclassical Correlations Can Be Activated into Distillable Entanglement,” Physical Review Letters, vol. 106, no. 22, 2011, doi: 10.1103/physrevlett.106.220403.
LibreCat | DOI | Download (ext.) | arXiv
 
[3]
2010 | Journal Article | LibreCat-ID: 8179 | OA
S. Gharibian, “Strong NP-hardness of the quantum separability problem,” Quantum Information & Computation, vol. 10, no. 3{\ & }4, pp. 343–360, 2010.
LibreCat | Download (ext.) | arXiv
 
[2]
2009 | Journal Article | LibreCat-ID: 8180 | OA
S. Gharibian, H. Kampermann, and D. Bru{\ss}, “On global effects caused by locally noneffective unitary operations,” Quantum Information & Computation, vol. 9, no. 11, pp. 1013–1029, 2009.
LibreCat | Download (ext.) | arXiv
 
[1]
2009 | Journal Article | LibreCat-ID: 8181 | OA
A. Datta and S. Gharibian, “Signatures of nonclassicality in mixed-state quantum computation,” Physical Review A, vol. 79, no. 4, 2009, doi: 10.1103/physreva.79.042325.
LibreCat | DOI | Download (ext.) | arXiv
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Citation Style: IEEE

Export / Embed