251 citations · 802 across the 40 of their papers we have counts for
4 papers · 1 filter
Quantum k-SAT Related Hypergraph Problems
Simon-Luca Kremer, Dorian Rudolph, Sevag Gharibian
The Quantum k-SAT problem is the quantum generalization of the k-SAT problem. It is the problem whether a given local Hamiltonian is frustration-free. Frustration-free means that t…
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
Avantika Agarwal, Sevag Gharibian, Venkata Koppula +1
The Polynomial-Time Hierarchy () is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum adv…
On polynomially many queries to NP or QMA oracles
Sevag Gharibian, Dorian Rudolph
We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as and , respective…
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
Sevag Gharibian, Miklos Santha, Jamie Sikora +2
The polynomial-time hierarchy () has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as $\m…