Sevag Gharibian

According to our database, Sevag Gharibian authored at least 38 papers between 2009 and 2025.

Collaborative distances:

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

2025

Quantum k-SAT Related Hypergraph Problems.

Simon-Luca Kremer, Dorian Rudolph, Sevag Gharibian

CoRR, June, 2025

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem.

Marco Aldi, Sevag Gharibian, Dorian Rudolph

Electron. Colloquium Comput. Complex., 2025

Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript{1}-Complete: Direct Embeddings and Black-Box Simulation.

Dorian Rudolph, Sevag Gharibian, Daniel Nagaj

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

Hardness of approximation for ground state problems.

Sevag Gharibian, Carsten Hecht

CoRR, 2024

Beating Grover search for low-energy estimation and state preparation.

Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki

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

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting.

Sevag Gharibian, Jonas Kamminga

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Guest Column: The 7 faces of quantum NP.

Sevag Gharibian

SIGACT News, December, 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

Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture.

Sevag Gharibian, François Le Gall

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

On Polynomially Many Queries to NP or QMA Oracles.

Sevag Gharibian, Dorian Rudolph

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

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

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

Dagstuhl Reports, 2021

2020

Towards Quantum One-Time Memories from Stateless Hardware.

Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou

Proceedings of the 15th Conference on the Theory of Quantum Computation, 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

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

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

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 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

Ground State Connectivity of Local Hamiltonians.

Sevag Gharibian, Jamie Sikora

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

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

Hardness of Approximation for Quantum Problems.

Sevag Gharibian, Julia Kempe

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Approximation Algorithms for QMA-Complete Problems.

Sevag Gharibian, Julia Kempe

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

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