Pre­prints

Beating Grover search for low-energy estimation and state preparation

H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, ArXiv:2407.03073 (2024).


Hardness of approximation for ground state problems

S. Gharibian, C. Hecht, ArXiv:2411.04874 (2024).


Second order cone relaxations for quantum Max Cut

F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).


Alle Publikationen anzeigen

Ver­öf­fent­li­chun­gen

2025

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation

D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical Computer Science (ITCS), n.d.


2024


BQP, meet NP: Search-to-decision reductions and approximate counting

S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2024, pp. 1–19.


Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds

A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, in: Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2024, pp. 7–17.


2023

Improved Hardness Results for the Guided Local Hamiltonian Problem

S. Gharibian, R. Hayakawa, F.L. Gall, T. Morimae, in: Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2023, pp. 1–19.



Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement

S. Gharibian, D. Rudolph, in: 14th Innovations in Theoretical Computer Science (ITCS), 2023, p. 53:1-53:23.


The Complexity of Translationally Invariant Problems beyond Ground State Energies

S. Gharibian, J. Watson, J. Bausch, in: Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 2023, p. 54:1-54:21.


The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate

L. Bittel, S. Gharibian, M. Kliesch, in: Proceedings of the 38th Computational Complexity Conference (CCC), 2023, p. 34:1-34:24.


2022

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture

S. Gharibian, F.L. Gall, in: Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 2022, pp. 19–32.


Quantum generalizations of the polynomial hierarchy with applications to QMA(2)

S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, Computational Complexity 31 (2022).


On polynomially many queries to NP or QMA oracles

S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, pp. 1–27.


2021

Towards Quantum One-Time Memories from Stateless Hardware

A. Broadbent, S. Gharibian, H.-S. Zhou, Quantum 5 (2021).


2020

Oracle complexity classes and local measurements on physical Hamiltonians

S. Gharibian, S. Piddock, J. Yirka, in: Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.


Towards Quantum One-Time Memories from Stateless Hardware

A. Broadbent, S. Gharibian, H.-S. Zhou, in: Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), Leibniz International Proceedings in Informatics (LIPIcs), 2020, p. 6:1-6:25.


On efficiently solvable cases of Quantum k-SAT

S. Gharibian, M. Aldi, N. de Beaudrap, S. Saeedi, Communications in Mathematical Physics (2020).


2019

Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut

S. Gharibian, O. Parekh, in: Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2019, p. 31:1-31:17.



2018

On Efficiently Solvable Cases of Quantum k-SAT

M. Aldi, N. de Beaudrap, S. Gharibian, S. Saeedi, in: I. Potapov, P. Spirakis, J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 38:1-38:16.


Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)

S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, in: I. Potapov, P. Spirakis, J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 58:1-58:16.


The Complexity of Simulating Local Measurements on Quantum Systems

S. Gharibian, J. Yirka, in: M. Wilde (Ed.), 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 2:1-2:17.


Ground State Connectivity of Local Hamiltonians

S. Gharibian, J. Sikora, ACM Transactions on Computation Theory (TOCT) 10 (2018) 8:1-8:28.


2016

A Linear Time Algorithm for Quantum 2-SAT

N. de Beaudrap, S. Gharibian, in: R. Raz (Ed.), Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016, p. 27:1–17:21.


2015

Ground State Connectivity of Local Hamiltonians

S. Gharibian, J. Sikora, in: M.M. Halld{\’o}rsson, K. Iwama, N. Kobayashi, B. Speckmann (Eds.), International Colloquium on Automata, Languages, and Programming (ICALP 2015), Springer Berlin Heidelberg, Berlin, Heidelberg, 2015, pp. 617–628.


Quantum Hamiltonian Complexity

S. Gharibian, Y. Huang, Z. Landau, S. Woo Shin, Foundations and Trends® in Theoretical Computer Science 10 (2015) 159–282.


Tensor network non-zero testing

S. Gharibian, Z. Landau, S. Woo Shin, G. Wang, Quantum Information & Computation 15 (2015) 885–899.


2014

Hardness of approximation for quantum problems

S. Gharibian, J. Kempe, Quantum Information & Computation 14 (2014) 517–540.


Gate-efficient discrete simulations of continuous-time quantum query algorithms

D. W. Berry, R. Cleve, S. Gharibian, Quantum Information & Computation 14 (2014) 1–30.


2013

Approximation, Proof Systems, and Correlations in a Quantum World

S. Gharibian, Approximation, Proof Systems, and Correlations in a Quantum World, 2013.


QMA variants with polynomially many provers

S. Gharibian, J. Sikora, S. Upadhyay, Quantum Information & Computation 13 (2013) 135–157.


2012

Hardness of Approximation for Quantum Problems

S. Gharibian, J. Kempe, in: A. Czumaj, K. Mehlhorn, A. Pitts, R. Wattenhofer (Eds.), International Colloquium on Automata, Languages, and Programming (ICALP 2012), Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 387–398.


Approximation Algorithms for QMA-Complete Problems

S. Gharibian, J. Kempe, SIAM Journal on Computing 41 (2012) 1028–1050.


Quantifying nonclassicality with local unitary operations

S. Gharibian, Physical Review A 86 (2012) 042106.


2011

Characterizing Quantumness via Entanglement Creation

S. Gharibian, M. PIANI, G. ADESSO, J. CALSAMIGLIA, P. HORODECKI, International Journal of Quantum Information 09 (2011) 1701–1713.


Approximation Algorithms for QMA-Complete Problems

S. Gharibian, J. Kempe, in: IEEE Annual Conference on Computational Complexity (CCC 2011), IEEE, 2011.


All Nonclassical Correlations Can Be Activated into Distillable Entanglement

M. Piani, S. Gharibian, G. Adesso, J. Calsamiglia, P. Horodecki, A. Winter, Physical Review Letters 106 (2011).


2010

Strong NP-hardness of the quantum separability problem

S. Gharibian, Quantum Information & Computation 10 (2010) 343–360.


2009

On global effects caused by locally noneffective unitary operations

S. Gharibian, H. Kampermann, D. Bru{\ss}, Quantum Information & Computation 9 (2009) 1013–1029.



Alle Publikationen anzeigen