List of preprints and publications - Quantum Computation

Preprints

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

D. Rudolph, S. Gharibian, D. Nagaj, ArXiv:2401.02368 (2024).

arXiv

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).

arXiv

Show all publications

Publications

2024

Guest Column: The 7 faces of quantum NP

S. Gharibian, ACM SIGACT News 54 (2024) 54–91.

https://dl.acm.org/doi/abs/10.1145/3639528.3639535

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), n.d.

arXiv

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.

arXiv

2023

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.

DOI arXiv

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.

DOI arXiv

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.

DOI arXiv

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.

DOI arXiv

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.

DOI

2022

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).

DOI

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.

DOI

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.

arXiv

2021

Towards Quantum One-Time Memories from Stateless Hardware

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

DOI

2020

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.

arXiv

On efficiently solvable cases of Quantum k-SAT

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

arXiv

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.

arXiv

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.

DOI

The complexity of simulating local measurements on quantum systems

S. Gharibian, J. Yirka, Quantum 3 (2019) 189.

DOI

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.

DOI arXiv

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.

DOI arXiv

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.

DOI arXiv

Ground State Connectivity of Local Hamiltonians

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

DOI arXiv

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.

DOI arXiv

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.

DOI arXiv

Quantum Hamiltonian Complexity

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

DOI arXiv

Tensor network non-zero testing

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

arXiv

2014

Hardness of approximation for quantum problems

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

arXiv

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

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

arXiv

2013

Approximation, Proof Systems, and Correlations in a Quantum World

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

https://arxiv.org/abs/1301.2632 arXiv

QMA variants with polynomially many provers

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

arXiv

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.

DOI arXiv

Approximation Algorithms for QMA-Complete Problems

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

DOI arXiv

Quantifying nonclassicality with local unitary operations

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

DOI arXiv