Zobrazeno 1 - 10
of 116
pro vyhledávání: '"Gharibian, Sevag"'
Autor:
Gharibian, Sevag, Hecht, Carsten
After nearly two decades of research, the question of a quantum PCP theorem for quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a result, proving QMA-hardness of approximation for ground state energy estimation has remained elus
Externí odkaz:
http://arxiv.org/abs/2411.04874
Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic Heisenberg model, is a QMA-complete problem relevant to quantum many-body physics and computer science. Semidefinite programming relaxations have been fruitful in designing theoretic
Externí odkaz:
http://arxiv.org/abs/2411.04120
Autor:
Buhrman, Harry, Gharibian, Sevag, Landau, Zeph, Gall, François Le, Schuch, Norbert, Tamaki, Suguru
Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this work, we give quantum algorithms which, given any $k$-body Hamiltonian $H$, compute an estimate for the ground state energy and pre
Externí odkaz:
http://arxiv.org/abs/2407.03073
Autor:
Gharibian, Sevag, Kamminga, Jonas
Publikováno v:
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Volume 297, pp. 70:1-70:19
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We
Externí odkaz:
http://arxiv.org/abs/2401.03943
Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSA
Externí odkaz:
http://arxiv.org/abs/2401.02368
Publikováno v:
49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
The Polynomial-Time Hierarchy ($\mathsf{PH}$) is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum advantage'' analyses for near-term quantum computers. Quantumly, however,
Externí odkaz:
http://arxiv.org/abs/2401.01633
Autor:
Gharibian, Sevag
Publikováno v:
ACM SIGACT News, 54(4):54-91, 2024
When it comes to NP, its natural definition, its wide applicability across scientific disciplines, and its timeless relevance, the writing is on the wall: There can be only one. Quantum NP, on the other hand, is clearly the apple that fell far from t
Externí odkaz:
http://arxiv.org/abs/2310.18010
Publikováno v:
38th Computational Complexity Conference (CCC 2023), 34:1--34:24
Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the
Externí odkaz:
http://arxiv.org/abs/2211.12519
Autor:
Cade, Chris, Folkertsma, Marten, Gharibian, Sevag, Hayakawa, Ryu, Gall, François Le, Morimae, Tomoyuki, Weggemans, Jordi
Publikováno v:
Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), pp. 32:1-32.19, 2023
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recen
Externí odkaz:
http://arxiv.org/abs/2207.10250