25 Publications

Mark all

[25]
2020 | Conference Paper | LibreCat-ID: 13226
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), n.d., p. 38.
LibreCat | Download (ext.) | arXiv
 
[24]
2019 | Conference Paper | LibreCat-ID: 13297
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, pp. 31:1-31:17.
LibreCat | DOI | Download (ext.)
 
[23]
2019 | Journal Article | LibreCat-ID: 13558
The complexity of simulating local measurements on quantum systems
S. Gharibian, J. Yirka, Quantum 3 (2019) 189.
LibreCat | DOI | Download (ext.)
 
[22]
2018 | Conference Paper | LibreCat-ID: 8162
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, pp. 38:1-38:16.
LibreCat | DOI | Download (ext.) | arXiv
 
[21]
2018 | Journal Article | LibreCat-ID: 8167
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
 
[20]
2018 | Conference Paper | LibreCat-ID: 8160
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, pp. 2:1-2:17.
LibreCat | DOI | Download (ext.) | arXiv
 
[19]
2018 | Conference Paper | LibreCat-ID: 8161
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, pp. 58:1-58:16.
LibreCat | DOI | Download (ext.) | arXiv
 
[18]
2018 | Preprint | LibreCat-ID: 8426
Towards Quantum One-Time Memories from Stateless Hardware
A. Broadbent, S. Gharibian, H.-S. Zhou, (2018).
LibreCat | Download (ext.) | arXiv
 
[17]
2016 | Conference Paper | LibreCat-ID: 8159
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, pp. 27:1–17:21.
LibreCat | DOI | Download (ext.) | arXiv
 
[16]
2015 | Journal Article | LibreCat-ID: 8168
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
 
[15]
2015 | Conference Paper | LibreCat-ID: 8164
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
 
[14]
2015 | Journal Article | LibreCat-ID: 8166
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
 
[13]
2014 | Journal Article | LibreCat-ID: 8171
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
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
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
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 | Journal Article | LibreCat-ID: 8174
Quantifying nonclassicality with local unitary operations
S. Gharibian, Physical Review A 86 (2012) 042106.
LibreCat | DOI | Download (ext.) | arXiv
 
[8]
2012 | Journal Article | LibreCat-ID: 8175
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 | Conference Paper | LibreCat-ID: 8169
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
 
[6]
2011 | Conference Paper | LibreCat-ID: 8176
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
 
[5]
2011 | Journal Article | LibreCat-ID: 8177
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
 
[4]
2011 | Journal Article | LibreCat-ID: 8178
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
 
[3]
2010 | Journal Article | LibreCat-ID: 8179
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: 8181
Signatures of nonclassicality in mixed-state quantum computation
A. Datta, S. Gharibian, Physical Review A 79 (2009).
LibreCat | DOI | Download (ext.) | arXiv
 
[1]
2009 | Journal Article | LibreCat-ID: 8180
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
 

Search

Filter Publications

Display / Sort

Export / Embed

25 Publications

Mark all

[25]
2020 | Conference Paper | LibreCat-ID: 13226
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), n.d., p. 38.
LibreCat | Download (ext.) | arXiv
 
[24]
2019 | Conference Paper | LibreCat-ID: 13297
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, pp. 31:1-31:17.
LibreCat | DOI | Download (ext.)
 
[23]
2019 | Journal Article | LibreCat-ID: 13558
The complexity of simulating local measurements on quantum systems
S. Gharibian, J. Yirka, Quantum 3 (2019) 189.
LibreCat | DOI | Download (ext.)
 
[22]
2018 | Conference Paper | LibreCat-ID: 8162
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, pp. 38:1-38:16.
LibreCat | DOI | Download (ext.) | arXiv
 
[21]
2018 | Journal Article | LibreCat-ID: 8167
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
 
[20]
2018 | Conference Paper | LibreCat-ID: 8160
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, pp. 2:1-2:17.
LibreCat | DOI | Download (ext.) | arXiv
 
[19]
2018 | Conference Paper | LibreCat-ID: 8161
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, pp. 58:1-58:16.
LibreCat | DOI | Download (ext.) | arXiv
 
[18]
2018 | Preprint | LibreCat-ID: 8426
Towards Quantum One-Time Memories from Stateless Hardware
A. Broadbent, S. Gharibian, H.-S. Zhou, (2018).
LibreCat | Download (ext.) | arXiv
 
[17]
2016 | Conference Paper | LibreCat-ID: 8159
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, pp. 27:1–17:21.
LibreCat | DOI | Download (ext.) | arXiv
 
[16]
2015 | Journal Article | LibreCat-ID: 8168
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
 
[15]
2015 | Conference Paper | LibreCat-ID: 8164
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
 
[14]
2015 | Journal Article | LibreCat-ID: 8166
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
 
[13]
2014 | Journal Article | LibreCat-ID: 8171
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
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
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
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 | Journal Article | LibreCat-ID: 8174
Quantifying nonclassicality with local unitary operations
S. Gharibian, Physical Review A 86 (2012) 042106.
LibreCat | DOI | Download (ext.) | arXiv
 
[8]
2012 | Journal Article | LibreCat-ID: 8175
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 | Conference Paper | LibreCat-ID: 8169
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
 
[6]
2011 | Conference Paper | LibreCat-ID: 8176
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
 
[5]
2011 | Journal Article | LibreCat-ID: 8177
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
 
[4]
2011 | Journal Article | LibreCat-ID: 8178
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
 
[3]
2010 | Journal Article | LibreCat-ID: 8179
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: 8181
Signatures of nonclassicality in mixed-state quantum computation
A. Datta, S. Gharibian, Physical Review A 79 (2009).
LibreCat | DOI | Download (ext.) | arXiv
 
[1]
2009 | Journal Article | LibreCat-ID: 8180
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
 

Search

Filter Publications

Display / Sort

Export / Embed