Sevag Gharibian

sevag.gharibian@uni-paderborn.de
ID
71541

43 Publications

Mark all

[43]
2025 | Conference Paper | LibreCat-ID: 50272
Rudolph, Dorian, Sevag Gharibian, and Daniel 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), 325:1–24, 2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.85.
LibreCat | DOI | arXiv
 
[42]
2024 | Journal Article | LibreCat-ID: 48544 | OA
Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” ACM SIGACT News 54, no. 4 (2024): 54–91.
LibreCat | Files available | Download (ext.)
 
[41]
2024 | Conference Paper | LibreCat-ID: 50406
Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision Reductions and Approximate Counting.” In Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 297:1–19, 2024.
LibreCat | arXiv
 
[40]
2024 | Preprint | LibreCat-ID: 55037
Buhrman, Harry, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, and Suguru Tamaki. “Beating Grover Search for Low-Energy Estimation and State Preparation.” ArXiv:2407.03073, 2024.
LibreCat | arXiv
 
[39]
2024 | Conference Paper | LibreCat-ID: 50273
Agarwal, Avantika, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph. “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower  Bounds.” In Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 306:7–17, 2024. https://doi.org/10.4230/LIPIcs.MFCS.2024.7.
LibreCat | DOI | arXiv
 
[38]
2024 | Preprint | LibreCat-ID: 56950
Gharibian, Sevag, and Carsten Hecht. “Hardness of Approximation for Ground State Problems.” ArXiv:2411.04874, 2024.
LibreCat | arXiv
 
[37]
2024 | Preprint | LibreCat-ID: 56944
Huber, Felix, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. “Second Order Cone Relaxations for Quantum Max Cut.” ArXiv:2411.04120, 2024.
LibreCat | arXiv
 
[36]
2024 | Preprint | LibreCat-ID: 57866
Aldi, Marco, Sevag Gharibian, and Dorian Rudolph. “An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum  Satisfiability Problem.” ArXiv:2412.19623, n.d.
LibreCat | arXiv
 
[35]
2023 | Conference Paper | LibreCat-ID: 32407
Gharibian, Sevag, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae. “Improved Hardness Results for the Guided Local Hamiltonian Problem.” In Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 261:1–19, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.32.
LibreCat | DOI | arXiv
 
[34]
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 52, no. 4 (2023): 1009–38. https://doi.org/10.1137/22m1513721.
LibreCat | DOI
 
[33]
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.” In 14th Innovations in Theoretical Computer Science (ITCS), 251:53:1-53:23, 2023. https://doi.org/10.4230/LIPIcs.ITCS.2023.53.
LibreCat | DOI | arXiv
 
[32]
2023 | Conference Paper | LibreCat-ID: 20841 | OA
Gharibian, Sevag, James Watson, and Johannes 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), 254:54:1-54:21, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.54.
LibreCat | DOI | Download (ext.) | arXiv
 
[31]
2023 | Conference Paper | LibreCat-ID: 34138
Bittel, Lennart, Sevag Gharibian, and Martin Kliesch. “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate.” In Proceedings of the 38th Computational Complexity Conference (CCC), 264:34:1-34:24. Leibniz International Proceedings in Informatics (LIPIcs), 2023. https://doi.org/10.4230/LIPIcs.CCC.2023.34.
LibreCat | DOI | arXiv
 
[30]
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.” In Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 19–32, 2022.
LibreCat | Download (ext.) | arXiv
 
[29]
2022 | Journal Article | LibreCat-ID: 34700
Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” Computational Complexity 31, no. 2 (2022). https://doi.org/10.1007/s00037-022-00231-8.
LibreCat | DOI
 
[28]
2022 | Conference Paper | LibreCat-ID: 27160 | OA
Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.” In 13th Innovations in Theoretical Computer Science (ITCS 2022), 215:1–27, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.75.
LibreCat | DOI | Download (ext.)
 
[27]
2021 | Journal Article | LibreCat-ID: 29780
Broadbent, Anne, Sevag Gharibian, and Hong-Sheng Zhou. “Towards Quantum One-Time Memories from Stateless Hardware.” Quantum 5 (2021). https://doi.org/10.22331/q-2021-04-08-429.
LibreCat | DOI
 
[26]
2020 | Conference Paper | LibreCat-ID: 13226 | OA
Gharibian, Sevag, Stephen Piddock, and Justin Yirka. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” In Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 38, 2020.
LibreCat | Download (ext.) | arXiv
 
[25]
2020 | Conference Paper | LibreCat-ID: 8426
Broadbent, Anne, Sevag Gharibian, and Hong-Sheng 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), 158:6:1-6:25. Leibniz International Proceedings in Informatics (LIPIcs), 2020.
LibreCat | Download (ext.) | arXiv
 
[24]
2020 | Journal Article | LibreCat-ID: 16927 | OA
Gharibian, Sevag, Marco Aldi, Niel de Beaudrap, and Seyran 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
Gharibian, Sevag, and Ojas 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), 145:31:1-31:17. Leibniz International Proceedings in Informatics (LIPIcs), 2019. https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31.
LibreCat | DOI | Download (ext.)
 
[22]
2019 | Journal Article | LibreCat-ID: 13558 | OA
Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” Quantum 3 (2019): 189. https://doi.org/10.22331/q-2019-09-30-189.
LibreCat | DOI | Download (ext.)
 
[21]
2018 | Conference Paper | LibreCat-ID: 8162 | OA
Aldi, Marco, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi. “On Efficiently Solvable Cases of Quantum K-SAT.” In 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), edited by Igor Potapov, Paul Spirakis, and James Worrell, 117:38:1-38:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.38.
LibreCat | DOI | Download (ext.) | arXiv
 
[20]
2018 | Conference Paper | LibreCat-ID: 8161 | OA
Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” In 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), edited by Igor Potapov, Paul Spirakis, and James Worrell, 117:58:1-58:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.58.
LibreCat | DOI | Download (ext.) | arXiv
 
[19]
2018 | Conference Paper | LibreCat-ID: 8160 | OA
Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), edited by Mark Wilde, 73:2:1-2:17. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.TQC.2017.2.
LibreCat | DOI | Download (ext.) | arXiv
 
[18]
2018 | Journal Article | LibreCat-ID: 8167 | OA
Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” ACM Transactions on Computation Theory (TOCT) 10, no. 2 (2018): 8:1-8:28. https://doi.org/10.1145/3186587.
LibreCat | DOI | Download (ext.) | arXiv
 
[17]
2016 | Conference Paper | LibreCat-ID: 8159 | OA
Beaudrap, Niel de, and Sevag Gharibian. “A Linear Time Algorithm for Quantum 2-SAT.” In Proceedings of the 31st Conference on Computational Complexity (CCC 2016), edited by Ran Raz, 50:27:1-17:21. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. https://doi.org/10.4230/LIPIcs.CCC.2016.27.
LibreCat | DOI | Download (ext.) | arXiv
 
[16]
2015 | Conference Paper | LibreCat-ID: 8164 | OA
Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” In International Colloquium on Automata, Languages, and Programming (ICALP 2015), edited by Magn{\’u}s M. Halld{\’o}rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, 617–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. https://doi.org/10.1007/978-3-662-47672-7_50.
LibreCat | DOI | Download (ext.) | arXiv
 
[15]
2015 | Journal Article | LibreCat-ID: 8166 | OA
Gharibian, Sevag, Yichen Huang, Zeph Landau, and Seung Woo Shin. “Quantum Hamiltonian Complexity.” Foundations and Trends® in Theoretical Computer Science 10, no. 3 (2015): 159–282. https://doi.org/10.1561/0400000066.
LibreCat | DOI | Download (ext.) | arXiv
 
[14]
2015 | Journal Article | LibreCat-ID: 8168 | OA
Gharibian, Sevag, Zeph Landau, Seung Woo Shin, and Guoming Wang. “Tensor Network Non-Zero Testing.” Quantum Information & Computation 15, no. 9{\ & }10 (2015): 885–99.
LibreCat | Download (ext.) | arXiv
 
[13]
2014 | Journal Article | LibreCat-ID: 8171 | OA
Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” Quantum Information & Computation 14, no. 5–6 (2014): 517–40.
LibreCat | Download (ext.) | arXiv
 
[12]
2014 | Journal Article | LibreCat-ID: 8172 | OA
W. Berry, Dominic, Richard Cleve, and Sevag Gharibian. “Gate-Efficient Discrete Simulations of Continuous-Time Quantum Query Algorithms.” Quantum Information & Computation 14, no. 1–2 (2014): 1–30.
LibreCat | Download (ext.) | arXiv
 
[11]
2013 | Dissertation | LibreCat-ID: 8425 | OA
Gharibian, Sevag. Approximation, Proof Systems, and Correlations in a Quantum World, 2013.
LibreCat | Files available | Download (ext.) | arXiv
 
[10]
2013 | Journal Article | LibreCat-ID: 8173 | OA
Gharibian, Sevag, Jamie Sikora, and Sarvagya Upadhyay. “QMA Variants with Polynomially Many Provers.” Quantum Information & Computation 13, no. 1–2 (2013): 135–57.
LibreCat | Download (ext.) | arXiv
 
[9]
2012 | Conference Paper | LibreCat-ID: 8169 | OA
Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” In International Colloquium on Automata, Languages, and Programming (ICALP 2012), edited by Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, 387–98. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. https://doi.org/10.1007/978-3-642-31594-7_33.
LibreCat | DOI | Download (ext.) | arXiv
 
[8]
2012 | Journal Article | LibreCat-ID: 8175 | OA
Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” SIAM Journal on Computing 41, no. 4 (2012): 1028–50. https://doi.org/10.1137/110842272.
LibreCat | DOI | Download (ext.) | arXiv
 
[7]
2012 | Journal Article | LibreCat-ID: 8174 | OA
Gharibian, Sevag. “Quantifying Nonclassicality with Local Unitary Operations.” Physical Review A 86 (2012): 042106. https://doi.org/10.1103/PhysRevA.86.042106.
LibreCat | DOI | Download (ext.) | arXiv
 
[6]
2011 | Journal Article | LibreCat-ID: 8178 | OA
Gharibian, Sevag, MARCO PIANI, GERARDO ADESSO, JOHN CALSAMIGLIA, and PAWEŁ HORODECKI. “Characterizing Quantumness via Entanglement Creation.” International Journal of Quantum Information 09, no. 07n08 (2011): 1701–13. https://doi.org/10.1142/s0219749911008258.
LibreCat | DOI | Download (ext.) | arXiv
 
[5]
2011 | Conference Paper | LibreCat-ID: 8176 | OA
Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” In IEEE Annual Conference on Computational Complexity (CCC 2011). IEEE, 2011. https://doi.org/10.1109/ccc.2011.15.
LibreCat | DOI | Download (ext.) | arXiv
 
[4]
2011 | Journal Article | LibreCat-ID: 8177 | OA
Piani, Marco, Sevag Gharibian, Gerardo Adesso, John Calsamiglia, Paweł Horodecki, and Andreas Winter. “All Nonclassical Correlations Can Be Activated into Distillable Entanglement.” Physical Review Letters 106, no. 22 (2011). https://doi.org/10.1103/physrevlett.106.220403.
LibreCat | DOI | Download (ext.) | arXiv
 
[3]
2010 | Journal Article | LibreCat-ID: 8179 | OA
Gharibian, Sevag. “Strong NP-Hardness of the Quantum Separability Problem.” Quantum Information & Computation 10, no. 3{\ & }4 (2010): 343–60.
LibreCat | Download (ext.) | arXiv
 
[2]
2009 | Journal Article | LibreCat-ID: 8180 | OA
Gharibian, Sevag, Hermann Kampermann, and Dagmar Bru{\ss}. “On Global Effects Caused by Locally Noneffective Unitary Operations.” Quantum Information & Computation 9, no. 11 (2009): 1013–29.
LibreCat | Download (ext.) | arXiv
 
[1]
2009 | Journal Article | LibreCat-ID: 8181 | OA
Datta, Animesh, and Sevag Gharibian. “Signatures of Nonclassicality in Mixed-State Quantum Computation.” Physical Review A 79, no. 4 (2009). https://doi.org/10.1103/physreva.79.042325.
LibreCat | DOI | Download (ext.) | arXiv
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Citation Style: Chicago

Export / Embed

43 Publications

Mark all

[43]
2025 | Conference Paper | LibreCat-ID: 50272
Rudolph, Dorian, Sevag Gharibian, and Daniel 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), 325:1–24, 2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.85.
LibreCat | DOI | arXiv
 
[42]
2024 | Journal Article | LibreCat-ID: 48544 | OA
Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” ACM SIGACT News 54, no. 4 (2024): 54–91.
LibreCat | Files available | Download (ext.)
 
[41]
2024 | Conference Paper | LibreCat-ID: 50406
Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision Reductions and Approximate Counting.” In Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 297:1–19, 2024.
LibreCat | arXiv
 
[40]
2024 | Preprint | LibreCat-ID: 55037
Buhrman, Harry, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, and Suguru Tamaki. “Beating Grover Search for Low-Energy Estimation and State Preparation.” ArXiv:2407.03073, 2024.
LibreCat | arXiv
 
[39]
2024 | Conference Paper | LibreCat-ID: 50273
Agarwal, Avantika, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph. “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower  Bounds.” In Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 306:7–17, 2024. https://doi.org/10.4230/LIPIcs.MFCS.2024.7.
LibreCat | DOI | arXiv
 
[38]
2024 | Preprint | LibreCat-ID: 56950
Gharibian, Sevag, and Carsten Hecht. “Hardness of Approximation for Ground State Problems.” ArXiv:2411.04874, 2024.
LibreCat | arXiv
 
[37]
2024 | Preprint | LibreCat-ID: 56944
Huber, Felix, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. “Second Order Cone Relaxations for Quantum Max Cut.” ArXiv:2411.04120, 2024.
LibreCat | arXiv
 
[36]
2024 | Preprint | LibreCat-ID: 57866
Aldi, Marco, Sevag Gharibian, and Dorian Rudolph. “An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum  Satisfiability Problem.” ArXiv:2412.19623, n.d.
LibreCat | arXiv
 
[35]
2023 | Conference Paper | LibreCat-ID: 32407
Gharibian, Sevag, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae. “Improved Hardness Results for the Guided Local Hamiltonian Problem.” In Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 261:1–19, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.32.
LibreCat | DOI | arXiv
 
[34]
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 52, no. 4 (2023): 1009–38. https://doi.org/10.1137/22m1513721.
LibreCat | DOI
 
[33]
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.” In 14th Innovations in Theoretical Computer Science (ITCS), 251:53:1-53:23, 2023. https://doi.org/10.4230/LIPIcs.ITCS.2023.53.
LibreCat | DOI | arXiv
 
[32]
2023 | Conference Paper | LibreCat-ID: 20841 | OA
Gharibian, Sevag, James Watson, and Johannes 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), 254:54:1-54:21, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.54.
LibreCat | DOI | Download (ext.) | arXiv
 
[31]
2023 | Conference Paper | LibreCat-ID: 34138
Bittel, Lennart, Sevag Gharibian, and Martin Kliesch. “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate.” In Proceedings of the 38th Computational Complexity Conference (CCC), 264:34:1-34:24. Leibniz International Proceedings in Informatics (LIPIcs), 2023. https://doi.org/10.4230/LIPIcs.CCC.2023.34.
LibreCat | DOI | arXiv
 
[30]
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.” In Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 19–32, 2022.
LibreCat | Download (ext.) | arXiv
 
[29]
2022 | Journal Article | LibreCat-ID: 34700
Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” Computational Complexity 31, no. 2 (2022). https://doi.org/10.1007/s00037-022-00231-8.
LibreCat | DOI
 
[28]
2022 | Conference Paper | LibreCat-ID: 27160 | OA
Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.” In 13th Innovations in Theoretical Computer Science (ITCS 2022), 215:1–27, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.75.
LibreCat | DOI | Download (ext.)
 
[27]
2021 | Journal Article | LibreCat-ID: 29780
Broadbent, Anne, Sevag Gharibian, and Hong-Sheng Zhou. “Towards Quantum One-Time Memories from Stateless Hardware.” Quantum 5 (2021). https://doi.org/10.22331/q-2021-04-08-429.
LibreCat | DOI
 
[26]
2020 | Conference Paper | LibreCat-ID: 13226 | OA
Gharibian, Sevag, Stephen Piddock, and Justin Yirka. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” In Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 38, 2020.
LibreCat | Download (ext.) | arXiv
 
[25]
2020 | Conference Paper | LibreCat-ID: 8426
Broadbent, Anne, Sevag Gharibian, and Hong-Sheng 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), 158:6:1-6:25. Leibniz International Proceedings in Informatics (LIPIcs), 2020.
LibreCat | Download (ext.) | arXiv
 
[24]
2020 | Journal Article | LibreCat-ID: 16927 | OA
Gharibian, Sevag, Marco Aldi, Niel de Beaudrap, and Seyran 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
Gharibian, Sevag, and Ojas 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), 145:31:1-31:17. Leibniz International Proceedings in Informatics (LIPIcs), 2019. https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31.
LibreCat | DOI | Download (ext.)
 
[22]
2019 | Journal Article | LibreCat-ID: 13558 | OA
Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” Quantum 3 (2019): 189. https://doi.org/10.22331/q-2019-09-30-189.
LibreCat | DOI | Download (ext.)
 
[21]
2018 | Conference Paper | LibreCat-ID: 8162 | OA
Aldi, Marco, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi. “On Efficiently Solvable Cases of Quantum K-SAT.” In 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), edited by Igor Potapov, Paul Spirakis, and James Worrell, 117:38:1-38:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.38.
LibreCat | DOI | Download (ext.) | arXiv
 
[20]
2018 | Conference Paper | LibreCat-ID: 8161 | OA
Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” In 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), edited by Igor Potapov, Paul Spirakis, and James Worrell, 117:58:1-58:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.58.
LibreCat | DOI | Download (ext.) | arXiv
 
[19]
2018 | Conference Paper | LibreCat-ID: 8160 | OA
Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), edited by Mark Wilde, 73:2:1-2:17. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.TQC.2017.2.
LibreCat | DOI | Download (ext.) | arXiv
 
[18]
2018 | Journal Article | LibreCat-ID: 8167 | OA
Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” ACM Transactions on Computation Theory (TOCT) 10, no. 2 (2018): 8:1-8:28. https://doi.org/10.1145/3186587.
LibreCat | DOI | Download (ext.) | arXiv
 
[17]
2016 | Conference Paper | LibreCat-ID: 8159 | OA
Beaudrap, Niel de, and Sevag Gharibian. “A Linear Time Algorithm for Quantum 2-SAT.” In Proceedings of the 31st Conference on Computational Complexity (CCC 2016), edited by Ran Raz, 50:27:1-17:21. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. https://doi.org/10.4230/LIPIcs.CCC.2016.27.
LibreCat | DOI | Download (ext.) | arXiv
 
[16]
2015 | Conference Paper | LibreCat-ID: 8164 | OA
Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” In International Colloquium on Automata, Languages, and Programming (ICALP 2015), edited by Magn{\’u}s M. Halld{\’o}rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, 617–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. https://doi.org/10.1007/978-3-662-47672-7_50.
LibreCat | DOI | Download (ext.) | arXiv
 
[15]
2015 | Journal Article | LibreCat-ID: 8166 | OA
Gharibian, Sevag, Yichen Huang, Zeph Landau, and Seung Woo Shin. “Quantum Hamiltonian Complexity.” Foundations and Trends® in Theoretical Computer Science 10, no. 3 (2015): 159–282. https://doi.org/10.1561/0400000066.
LibreCat | DOI | Download (ext.) | arXiv
 
[14]
2015 | Journal Article | LibreCat-ID: 8168 | OA
Gharibian, Sevag, Zeph Landau, Seung Woo Shin, and Guoming Wang. “Tensor Network Non-Zero Testing.” Quantum Information & Computation 15, no. 9{\ & }10 (2015): 885–99.
LibreCat | Download (ext.) | arXiv
 
[13]
2014 | Journal Article | LibreCat-ID: 8171 | OA
Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” Quantum Information & Computation 14, no. 5–6 (2014): 517–40.
LibreCat | Download (ext.) | arXiv
 
[12]
2014 | Journal Article | LibreCat-ID: 8172 | OA
W. Berry, Dominic, Richard Cleve, and Sevag Gharibian. “Gate-Efficient Discrete Simulations of Continuous-Time Quantum Query Algorithms.” Quantum Information & Computation 14, no. 1–2 (2014): 1–30.
LibreCat | Download (ext.) | arXiv
 
[11]
2013 | Dissertation | LibreCat-ID: 8425 | OA
Gharibian, Sevag. Approximation, Proof Systems, and Correlations in a Quantum World, 2013.
LibreCat | Files available | Download (ext.) | arXiv
 
[10]
2013 | Journal Article | LibreCat-ID: 8173 | OA
Gharibian, Sevag, Jamie Sikora, and Sarvagya Upadhyay. “QMA Variants with Polynomially Many Provers.” Quantum Information & Computation 13, no. 1–2 (2013): 135–57.
LibreCat | Download (ext.) | arXiv
 
[9]
2012 | Conference Paper | LibreCat-ID: 8169 | OA
Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” In International Colloquium on Automata, Languages, and Programming (ICALP 2012), edited by Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, 387–98. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. https://doi.org/10.1007/978-3-642-31594-7_33.
LibreCat | DOI | Download (ext.) | arXiv
 
[8]
2012 | Journal Article | LibreCat-ID: 8175 | OA
Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” SIAM Journal on Computing 41, no. 4 (2012): 1028–50. https://doi.org/10.1137/110842272.
LibreCat | DOI | Download (ext.) | arXiv
 
[7]
2012 | Journal Article | LibreCat-ID: 8174 | OA
Gharibian, Sevag. “Quantifying Nonclassicality with Local Unitary Operations.” Physical Review A 86 (2012): 042106. https://doi.org/10.1103/PhysRevA.86.042106.
LibreCat | DOI | Download (ext.) | arXiv
 
[6]
2011 | Journal Article | LibreCat-ID: 8178 | OA
Gharibian, Sevag, MARCO PIANI, GERARDO ADESSO, JOHN CALSAMIGLIA, and PAWEŁ HORODECKI. “Characterizing Quantumness via Entanglement Creation.” International Journal of Quantum Information 09, no. 07n08 (2011): 1701–13. https://doi.org/10.1142/s0219749911008258.
LibreCat | DOI | Download (ext.) | arXiv
 
[5]
2011 | Conference Paper | LibreCat-ID: 8176 | OA
Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” In IEEE Annual Conference on Computational Complexity (CCC 2011). IEEE, 2011. https://doi.org/10.1109/ccc.2011.15.
LibreCat | DOI | Download (ext.) | arXiv
 
[4]
2011 | Journal Article | LibreCat-ID: 8177 | OA
Piani, Marco, Sevag Gharibian, Gerardo Adesso, John Calsamiglia, Paweł Horodecki, and Andreas Winter. “All Nonclassical Correlations Can Be Activated into Distillable Entanglement.” Physical Review Letters 106, no. 22 (2011). https://doi.org/10.1103/physrevlett.106.220403.
LibreCat | DOI | Download (ext.) | arXiv
 
[3]
2010 | Journal Article | LibreCat-ID: 8179 | OA
Gharibian, Sevag. “Strong NP-Hardness of the Quantum Separability Problem.” Quantum Information & Computation 10, no. 3{\ & }4 (2010): 343–60.
LibreCat | Download (ext.) | arXiv
 
[2]
2009 | Journal Article | LibreCat-ID: 8180 | OA
Gharibian, Sevag, Hermann Kampermann, and Dagmar Bru{\ss}. “On Global Effects Caused by Locally Noneffective Unitary Operations.” Quantum Information & Computation 9, no. 11 (2009): 1013–29.
LibreCat | Download (ext.) | arXiv
 
[1]
2009 | Journal Article | LibreCat-ID: 8181 | OA
Datta, Animesh, and Sevag Gharibian. “Signatures of Nonclassicality in Mixed-State Quantum Computation.” Physical Review A 79, no. 4 (2009). https://doi.org/10.1103/physreva.79.042325.
LibreCat | DOI | Download (ext.) | arXiv
 
Marked Publication(s)

Search

Filter Publications

Display / Sort

Citation Style: Chicago

Export / Embed