Sevag Gharibian

Publication Activity (10 Years)

Years Active: 2009-2024
Publications (10 Years): 43

Top Topics

Quantum Computing

Content Addressable

Error Reduction

Top Venues

Quantum Inf. Comput.

Publications

Sevag Gharibian, Jonas Kamminga
BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting. ICALP (2024)
Dorian Rudolph, Sevag Gharibian, Daniel Nagaj
-complete: Direct embeddings and black-box simulation. CoRR (2024)
Sevag Gharibian, Jonas Kamminga
BQP, meet NP: Search-to-decision reductions and approximate counting. CoRR (2024)
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
Beating Grover search for low-energy estimation and state preparation. CoRR (2024)
Avantika Agarwal, Sevag Gharibian, Venkata Koppula, Dorian Rudolph
Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds. MFCS (2024)
Avantika Agarwal, Sevag Gharibian, Venkata Koppula, Dorian Rudolph
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. CoRR (2024)
Sevag Gharibian, Dorian Rudolph
Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement. ITCS (2023)
Sevag Gharibian
Guest Column: The 7 faces of quantum NP. SIGACT News 54 (4) (2023)
Sevag Gharibian
The 7 faces of quantum NP. CoRR (2023)
Sevag Gharibian, François Le Gall
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. SIAM J. Comput. 52 (4) (2023)
Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans
Improved Hardness Results for the Guided Local Hamiltonian Problem. ICALP (2023)
Lennart Bittel, Sevag Gharibian, Martin Kliesch
The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. CCC (2023)
James D. Watson, Johannes Bausch, Sevag Gharibian
The Complexity of Translationally Invariant Problems Beyond Ground State Energies. STACS (2023)
Sevag Gharibian, François Le Gall
Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture. STOC (2022)
Sevag Gharibian, Dorian Rudolph
Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement. CoRR (2022)
Lennart Bittel, Sevag Gharibian, Martin Kliesch
Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate. CoRR (2022)
Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Comput. Complex. 31 (2) (2022)
Sevag Gharibian, Dorian Rudolph
On Polynomially Many Queries to NP or QMA Oracles. ITCS (2022)
Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae
Improved Hardness Results for the Guided Local Hamiltonian Problem. CoRR (2022)
Sevag Gharibian, Dorian Rudolph
On polynomially many queries to NP or QMA oracles. CoRR (2021)
Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou
Towards Quantum One-Time Memories from Stateless Hardware. Quantum 5 (2021)
Sevag Gharibian, Dorian Rudolph
On polynomially many queries to NP or QMA oracles. Electron. Colloquium Comput. Complex. 28 (2021)
Sevag Gharibian, François Le Gall
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. CoRR (2021)
Bill Fefferman, Sevag Gharibian, Norbert Schuch, Barbara M. Terhal
Quantum Complexity: Theory and Application (Dagstuhl Seminar 21261). Dagstuhl Reports 11 (5) (2021)
Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou
Towards Quantum One-Time Memories from Stateless Hardware. TQC (2020)
James D. Watson, Johannes Bausch, Sevag Gharibian
The Complexity of Translationally Invariant Problems beyond Ground State Energies. CoRR (2020)
Sevag Gharibian, Stephen Piddock, Justin Yirka
Oracle Complexity Classes and Local Measurements on Physical Hamiltonians. STACS (2020)
Sevag Gharibian, Ojas Parekh
Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut. CoRR (2019)
Sevag Gharibian, Ojas Parekh
Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. APPROX-RANDOM (2019)
Sevag Gharibian, Stephen Piddock, Justin Yirka
Oracle complexity classes and local measurements on physical Hamiltonians. CoRR (2019)
Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). MFCS (2018)
Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou
Towards Quantum One-Time Memories from Stateless Hardware. IACR Cryptol. ePrint Arch. 2018 (2018)
Sevag Gharibian, Jamie Sikora
Ground State Connectivity of Local Hamiltonians. ACM Trans. Comput. Theory 10 (2) (2018)
Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
Quantum generalizations of the polynomial hierarchy with applications to QMA(2). CoRR (2018)
Marco Aldi, Niel de Beaudrap, Sevag Gharibian, Seyran Saeedi
On Efficiently Solvable Cases of Quantum k-SAT. MFCS (2018)
Sevag Gharibian, Justin Yirka
The Complexity of Simulating Local Measurements on Quantum Systems. TQC (2017)
Marco Aldi, Niel de Beaudrap, Sevag Gharibian, Seyran Saeedi
On efficiently solvable cases of Quantum k-SAT. CoRR (2017)
J. Niel de Beaudrap, Sevag Gharibian
A Linear Time Algorithm for Quantum 2-SAT. Computational Complexity Conference (2016)
Sevag Gharibian, Justin Yirka
The complexity of estimating local physical quantities. CoRR (2016)
Niel de Beaudrap, Sevag Gharibian
A linear time algorithm for quantum 2-SAT. CoRR (2015)
Sevag Gharibian, Yichen Huang, Zeph Landau, Seung Woo Shin
Quantum Hamiltonian Complexity. Found. Trends Theor. Comput. Sci. 10 (3) (2015)
Sevag Gharibian, Zeph Landau, Seung Woo Shin, Guoming Wang
Tensor network non-zero testing. Quantum Inf. Comput. 15 (9&10) (2015)
Sevag Gharibian, Jamie Sikora
Ground State Connectivity of Local Hamiltonians. ICALP (1) (2015)
Sevag Gharibian, Julia Kempe
Hardness of approximation for quantum problems. Quantum Inf. Comput. 14 (5-6) (2014)
Sevag Gharibian, Zeph Landau, Seung Woo Shin, Guoming Wang
Tensor network non-zero testing. CoRR (2014)
Sevag Gharibian, Jamie Sikora
Ground state connectivity of local Hamiltonians. CoRR (2014)
Dominic W. Berry, Richard Cleve, Sevag Gharibian
Gate-efficient discrete simulations of continuous-time quantum query algorithms. Quantum Inf. Comput. 14 (1-2) (2014)
Sevag Gharibian, Yichen Huang, Zeph Landau
Quantum Hamiltonian Complexity. CoRR (2014)
Sevag Gharibian, Jamie Sikora, Sarvagya Upadhyay
QMA variants with polynomially many provers. Quantum Inf. Comput. 13 (1-2) (2013)
Sevag Gharibian, Julia Kempe
Hardness of Approximation for Quantum Problems. ICALP (1) (2012)
Sevag Gharibian, Julia Kempe
Approximation Algorithms for QMA-Complete Problems. SIAM J. Comput. 41 (4) (2012)
Sevag Gharibian, Julia Kempe
Hardness of approximation for quantum problems CoRR (2012)
Sevag Gharibian, Julia Kempe
Approximation algorithms for QMA-complete problems CoRR (2011)
Sevag Gharibian, Julia Kempe
Approximation Algorithms for QMA-Complete Problems. Computational Complexity Conference (2011)
Sevag Gharibian, Jamie Sikora, Sarvagya Upadhyay
QMA variants with polynomially many provers CoRR (2011)
Sevag Gharibian
Strong NP-hardness of the quantum separability problem. Quantum Inf. Comput. 10 (3&4) (2010)
Sevag Gharibian, Hermann Kampermann, Dagmar Bruß
On global effects caused by locally noneffective unitary operations. Quantum Inf. Comput. 9 (11&12) (2009)
Dagmar Bruß, Sevag Gharibian, Hermann Kampermann
Revealing Quantum Entanglement via Locally Noneffective Operations. QI (2009)