Sevag Gharibian

According to our database, Sevag Gharibian authored at least 33 papers between 2009 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

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

Sevag Gharibian, Jonas Kamminga

CoRR, 2024

Quantum 2-SAT on low dimensional systems is QMA₁-complete: Direct embeddings and black-box simulation.

Dorian Rudolph, Sevag Gharibian, Daniel Nagaj

CoRR, 2024

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

Avantika Agarwal, Sevag Gharibian, Venkata Koppula, Dorian Rudolph

CoRR, 2024

2023

Guest Column: The 7 faces of quantum NP.

Sevag Gharibian

SIGACT News, December, 2023

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

Sevag Gharibian, François Le Gall

SIAM J. Comput., August, 2023

The 7 faces of quantum NP.

Sevag Gharibian

CoRR, 2023

The Complexity of Translationally Invariant Problems Beyond Ground State Energies.

James D. Watson, Johannes Bausch, Sevag Gharibian

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement.

Sevag Gharibian, Dorian Rudolph

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Improved Hardness Results for the Guided Local Hamiltonian Problem.

Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

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

Lennart Bittel, Sevag Gharibian, Martin Kliesch

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate.

Lennart Bittel, Sevag Gharibian, Martin Kliesch

CoRR, 2022

Improved Hardness Results for the Guided Local Hamiltonian Problem.

Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae

CoRR, 2022

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

Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka

Comput. Complex., 2022

2021

Towards Quantum One-Time Memories from Stateless Hardware.

Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou

Quantum, 2021

On polynomially many queries to NP or QMA oracles.

Sevag Gharibian, Dorian Rudolph

Electron. Colloquium Comput. Complex., 2021

Quantum Complexity: Theory and Application (Dagstuhl Seminar 21261).

Bill Fefferman, Sevag Gharibian, Norbert Schuch, Barbara M. Terhal

Dagstuhl Reports, 2021

2020

Oracle Complexity Classes and Local Measurements on Physical Hamiltonians.

Sevag Gharibian, Stephen Piddock, Justin Yirka

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

2019

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

Sevag Gharibian, Ojas Parekh

Proceedings of the Approximation, 2019

2018

Ground State Connectivity of Local Hamiltonians.

Sevag Gharibian, Jamie Sikora

ACM Trans. Comput. Theory, 2018

On Efficiently Solvable Cases of Quantum k-SAT.

Marco Aldi, Niel de Beaudrap, Sevag Gharibian, Seyran Saeedi

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2017

The Complexity of Simulating Local Measurements on Quantum Systems.

Sevag Gharibian, Justin Yirka

Proceedings of the 12th Conference on the Theory of Quantum Computation, 2017

2016

The complexity of estimating local physical quantities.

Sevag Gharibian, Justin Yirka

CoRR, 2016

A Linear Time Algorithm for Quantum 2-SAT.

J. Niel de Beaudrap, Sevag Gharibian

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Tensor network non-zero testing.

Sevag Gharibian, Zeph Landau, Seung Woo Shin, Guoming Wang

Quantum Inf. Comput., 2015

Quantum Hamiltonian Complexity.

Sevag Gharibian, Yichen Huang, Zeph Landau, Seung Woo Shin

Found. Trends Theor. Comput. Sci., 2015

2014

Hardness of approximation for quantum problems.

Sevag Gharibian, Julia Kempe

Quantum Inf. Comput., 2014

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

Dominic W. Berry, Richard Cleve, Sevag Gharibian

Quantum Inf. Comput., 2014

Quantum Hamiltonian Complexity.

Sevag Gharibian, Yichen Huang, Zeph Landau

CoRR, 2014

2013

QMA variants with polynomially many provers.

Sevag Gharibian, Jamie Sikora, Sarvagya Upadhyay

Quantum Inf. Comput., 2013

2012

Approximation Algorithms for QMA-Complete Problems.

Sevag Gharibian, Julia Kempe

SIAM J. Comput., 2012

2010

Strong NP-hardness of the quantum separability problem.

Sevag Gharibian

Quantum Inf. Comput., 2010

2009

On global effects caused by locally noneffective unitary operations.

Sevag Gharibian, Hermann Kampermann, Dagmar Bruß

Quantum Inf. Comput., 2009

Revealing Quantum Entanglement via Locally Noneffective Operations.

Dagmar Bruß, Sevag Gharibian, Hermann Kampermann

Proceedings of the Quantum Interaction, Third International Symposium, 2009