[{"external_id":{"arxiv":["2510.06796"]},"date_created":"2025-10-10T13:45:28Z","type":"preprint","department":[{"_id":"7"},{"_id":"623"}],"publication":"arXiv:2510.06796","citation":{"mla":"Gharibian, Sevag, and Jonas Kamminga. “On the Complexity of Estimating Ground State Entanglement and Free  Energy.” <i>ArXiv:2510.06796</i>, 2025.","bibtex":"@article{Gharibian_Kamminga_2025, title={On the complexity of estimating ground state entanglement and free  energy}, journal={arXiv:2510.06796}, author={Gharibian, Sevag and Kamminga, Jonas}, year={2025} }","ama":"Gharibian S, Kamminga J. On the complexity of estimating ground state entanglement and free  energy. <i>arXiv:251006796</i>. Published online 2025.","ieee":"S. Gharibian and J. Kamminga, “On the complexity of estimating ground state entanglement and free  energy,” <i>arXiv:2510.06796</i>. 2025.","apa":"Gharibian, S., &#38; Kamminga, J. (2025). On the complexity of estimating ground state entanglement and free  energy. In <i>arXiv:2510.06796</i>.","short":"S. Gharibian, J. Kamminga, ArXiv:2510.06796 (2025).","chicago":"Gharibian, Sevag, and Jonas Kamminga. “On the Complexity of Estimating Ground State Entanglement and Free  Energy.” <i>ArXiv:2510.06796</i>, 2025."},"abstract":[{"lang":"eng","text":"Understanding the entanglement structure of local Hamiltonian ground spaces\r\nis a physically motivated problem, with applications ranging from tensor\r\nnetwork design to quantum error-correcting codes. To this end, we study the\r\ncomplexity of estimating ground state entanglement, and more generally entropy\r\nestimation for low energy states and Gibbs states. We find, in particular, that\r\nthe classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum\r\nanalogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a\r\ncrucial role for such problems, showing: (1) Detecting a high-entanglement\r\nground state is qq-QAM-complete, (2) computing an additive error approximation\r\nto the Helmholtz free energy (equivalently, a multiplicative error\r\napproximation to the partition function) is in qq-QAM, (3) detecting a\r\nlow-entanglement ground state is QMA(2)-hard, and (4) detecting low energy\r\nstates which are close to product states can range from QMA-complete to\r\nQMA(2)-complete. Our results make progress on an open question of [Bravyi,\r\nChowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield\r\nthe first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the\r\nsparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012])."}],"language":[{"iso":"eng"}],"_id":"61778","user_id":"71541","year":"2025","title":"On the complexity of estimating ground state entanglement and free  energy","status":"public","author":[{"id":"71541","last_name":"Gharibian","orcid":"0000-0002-9992-3379","first_name":"Sevag","full_name":"Gharibian, Sevag"},{"full_name":"Kamminga, Jonas","first_name":"Jonas","last_name":"Kamminga"}],"date_updated":"2026-04-30T14:08:44Z"},{"type":"preprint","department":[{"_id":"7"},{"_id":"623"}],"external_id":{"arxiv":["2510.08545"]},"date_created":"2025-10-10T13:44:52Z","abstract":[{"text":"We investigate the role of energy, i.e. average photon number, as a resource\r\nin the computational complexity of bosonic systems. We show three sets of\r\nresults: (1. Energy growth rates) There exist bosonic gate sets which increase\r\nenergy incredibly rapidly, obtaining e.g. infinite energy in finite/constant\r\ntime. We prove these high energies can make computing properties of bosonic\r\ncomputations, such as deciding whether a given computation will attain infinite\r\nenergy, extremely difficult, formally undecidable. (2. Lower bounds on\r\ncomputational power) More energy ``='' more computational power. For example,\r\ncertain gate sets allow poly-time bosonic computations to simulate PTOWER, the\r\nset of deterministic computations whose runtime scales as a tower of\r\nexponentials with polynomial height. Even just exponential energy and $O(1)$\r\nmodes suffice to simulate NP, which, importantly, is a setup similar to that of\r\nthe recent bosonic factoring algorithm of [Brenner, Caha, Coiteux-Roy and\r\nKoenig (2024)]. For simpler gate sets, we show an energy hierarchy theorem. (3.\r\nUpper bounds on computational power) Bosonic computations with polynomial\r\nenergy can be simulated in BQP, ``physical'' bosonic computations with\r\narbitrary finite energy are decidable, and the gate set consisting of Gaussian\r\ngates and the cubic phase gate can be simulated in PP, with exponential bound\r\non energy, improving upon the previous PSPACE upper bound. Finally, combining\r\nupper and lower bounds yields no-go theorems for a continuous-variable\r\nSolovay--Kitaev theorem for gate sets such as the Gaussian and cubic phase\r\ngates.","lang":"eng"}],"publication":"arXiv:2510.08545","citation":{"ama":"Chabaud U, Gharibian S, Mehraban S, et al. Energy, Bosons and Computational Complexity. <i>arXiv:251008545</i>. Published online 2025.","bibtex":"@article{Chabaud_Gharibian_Mehraban_Motamedi_Naeij_Rudolph_Sambrani_2025, title={Energy, Bosons and Computational Complexity}, journal={arXiv:2510.08545}, author={Chabaud, Ulysse and Gharibian, Sevag and Mehraban, Saeed and Motamedi, Arsalan and Naeij, Hamid Reza and Rudolph, Dorian and Sambrani, Dhruva}, year={2025} }","mla":"Chabaud, Ulysse, et al. “Energy, Bosons and Computational Complexity.” <i>ArXiv:2510.08545</i>, 2025.","short":"U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H.R. Naeij, D. Rudolph, D. Sambrani, ArXiv:2510.08545 (2025).","chicago":"Chabaud, Ulysse, Sevag Gharibian, Saeed Mehraban, Arsalan Motamedi, Hamid Reza Naeij, Dorian Rudolph, and Dhruva Sambrani. “Energy, Bosons and Computational Complexity.” <i>ArXiv:2510.08545</i>, 2025.","apa":"Chabaud, U., Gharibian, S., Mehraban, S., Motamedi, A., Naeij, H. R., Rudolph, D., &#38; Sambrani, D. (2025). Energy, Bosons and Computational Complexity. In <i>arXiv:2510.08545</i>.","ieee":"U. Chabaud <i>et al.</i>, “Energy, Bosons and Computational Complexity,” <i>arXiv:2510.08545</i>. 2025."},"user_id":"71541","language":[{"iso":"eng"}],"_id":"61776","date_updated":"2026-05-15T08:39:50Z","status":"public","title":"Energy, Bosons and Computational Complexity","year":"2025","author":[{"last_name":"Chabaud","first_name":"Ulysse","full_name":"Chabaud, Ulysse"},{"full_name":"Gharibian, Sevag","first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","id":"71541"},{"first_name":"Saeed","last_name":"Mehraban","full_name":"Mehraban, Saeed"},{"last_name":"Motamedi","first_name":"Arsalan","full_name":"Motamedi, Arsalan"},{"last_name":"Naeij","first_name":"Hamid Reza","full_name":"Naeij, Hamid Reza"},{"id":"57863","full_name":"Rudolph, Dorian","last_name":"Rudolph","first_name":"Dorian"},{"last_name":"Sambrani","first_name":"Dhruva","full_name":"Sambrani, Dhruva"}]},{"user_id":"71541","_id":"60432","language":[{"iso":"eng"}],"date_updated":"2026-05-15T08:41:01Z","author":[{"first_name":"Simon-Luca","last_name":"Kremer","full_name":"Kremer, Simon-Luca"},{"id":"57863","last_name":"Rudolph","first_name":"Dorian","full_name":"Rudolph, Dorian"},{"full_name":"Gharibian, Sevag","orcid":"0000-0002-9992-3379","first_name":"Sevag","last_name":"Gharibian","id":"71541"}],"title":"Quantum k-SAT Related Hypergraph Problems","year":"2025","status":"public","department":[{"_id":"7"},{"_id":"623"}],"type":"preprint","date_created":"2025-06-27T06:56:35Z","external_id":{"arxiv":["2506.17066"]},"abstract":[{"text":"The Quantum k-SAT problem is the quantum generalization of the k-SAT problem.\r\nIt is the problem whether a given local Hamiltonian is frustration-free.\r\nFrustration-free means that the ground state of the k-local Hamiltonian\r\nminimizes the energy of every local interaction term simultaneously. This is a\r\ncentral question in quantum physics and a canonical QMA_1-complete problem. The\r\nQuantum k-SAT problem is not as well studied as the classical k-SAT problem in\r\nterms of special tractable cases, approximation algorithms and parameterized\r\ncomplexity. In this paper, we will give a graph-theoretic study of the Quantum\r\nk-SAT problem with the structures core and radius. These hypergraph structures\r\nare important to solve the Quantum k-SAT problem. We can solve a Quantum k-SAT\r\ninstance in polynomial time if the derived hypergraph has a core of size n-m+a,\r\nwhere a is a constant, and the radius is at most logarithmic. If it exists, we\r\ncan find a core of size n-m+a with the best possible radius in polynomial time,\r\nwhereas finding a general minimum core with minimal radius is NP-hard.","lang":"eng"}],"citation":{"mla":"Kremer, Simon-Luca, et al. “Quantum K-SAT Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>, 2025.","ama":"Kremer S-L, Rudolph D, Gharibian S. Quantum k-SAT Related Hypergraph Problems. <i>arXiv:250617066</i>. Published online 2025.","bibtex":"@article{Kremer_Rudolph_Gharibian_2025, title={Quantum k-SAT Related Hypergraph Problems}, journal={arXiv:2506.17066}, author={Kremer, Simon-Luca and Rudolph, Dorian and Gharibian, Sevag}, year={2025} }","apa":"Kremer, S.-L., Rudolph, D., &#38; Gharibian, S. (2025). Quantum k-SAT Related Hypergraph Problems. In <i>arXiv:2506.17066</i>.","ieee":"S.-L. Kremer, D. Rudolph, and S. Gharibian, “Quantum k-SAT Related Hypergraph Problems,” <i>arXiv:2506.17066</i>. 2025.","short":"S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).","chicago":"Kremer, Simon-Luca, Dorian Rudolph, and Sevag Gharibian. “Quantum K-SAT Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>, 2025."},"publication":"arXiv:2506.17066"},{"publication":"arXiv:2411.04120","citation":{"mla":"Huber, Felix, et al. “Second Order Cone Relaxations for Quantum Max Cut.” <i>ArXiv:2411.04120</i>, 2024.","bibtex":"@article{Huber_Thompson_Parekh_Gharibian_2024, title={Second order cone relaxations for quantum Max Cut}, journal={arXiv:2411.04120}, author={Huber, Felix and Thompson, Kevin and Parekh, Ojas and Gharibian, Sevag}, year={2024} }","ama":"Huber F, Thompson K, Parekh O, Gharibian S. Second order cone relaxations for quantum Max Cut. <i>arXiv:241104120</i>. Published online 2024.","ieee":"F. Huber, K. Thompson, O. Parekh, and S. Gharibian, “Second order cone relaxations for quantum Max Cut,” <i>arXiv:2411.04120</i>. 2024.","apa":"Huber, F., Thompson, K., Parekh, O., &#38; Gharibian, S. (2024). Second order cone relaxations for quantum Max Cut. In <i>arXiv:2411.04120</i>.","short":"F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).","chicago":"Huber, Felix, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. “Second Order Cone Relaxations for Quantum Max Cut.” <i>ArXiv:2411.04120</i>, 2024."},"abstract":[{"lang":"eng","text":"Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic\r\nHeisenberg model, is a QMA-complete problem relevant to quantum many-body\r\nphysics and computer science. Semidefinite programming relaxations have been\r\nfruitful in designing theoretical approximation algorithms for QMC, but are\r\ncomputationally expensive for systems beyond tens of qubits. We give a second\r\norder cone relaxation for QMC, which optimizes over the set of mutually\r\nconsistent three-qubit reduced density matrices. In combination with Pauli\r\nlevel-$1$ of the quantum Lasserre hierarchy, the relaxation achieves an\r\napproximation ratio of $0.526$ to the ground state energy. Our relaxation is\r\nsolvable on systems with hundreds of qubits and paves the way to\r\ncomputationally efficient lower and upper bounds on the ground state energy of\r\nlarge-scale quantum spin systems."}],"external_id":{"arxiv":["2411.04120"]},"date_created":"2024-11-07T12:09:37Z","type":"preprint","department":[{"_id":"7"},{"_id":"623"}],"status":"public","title":"Second order cone relaxations for quantum Max Cut","year":"2024","author":[{"first_name":"Felix","last_name":"Huber","full_name":"Huber, Felix"},{"full_name":"Thompson, Kevin","first_name":"Kevin","last_name":"Thompson"},{"first_name":"Ojas","last_name":"Parekh","full_name":"Parekh, Ojas"},{"id":"71541","orcid":"0000-0002-9992-3379","last_name":"Gharibian","first_name":"Sevag","full_name":"Gharibian, Sevag"}],"date_updated":"2026-05-15T08:41:38Z","_id":"56944","language":[{"iso":"eng"}],"user_id":"71541"}]