---
_id: '61778'
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])."
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Jonas
  full_name: Kamminga, Jonas
  last_name: Kamminga
citation:
  ama: Gharibian S, Kamminga J. On the complexity of estimating ground state entanglement
    and free  energy. <i>arXiv:251006796</i>. Published online 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>.
  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} }'
  chicago: Gharibian, Sevag, and Jonas Kamminga. “On the Complexity of Estimating
    Ground State Entanglement and Free  Energy.” <i>ArXiv:2510.06796</i>, 2025.
  ieee: S. Gharibian and J. Kamminga, “On the complexity of estimating ground state
    entanglement and free  energy,” <i>arXiv:2510.06796</i>. 2025.
  mla: Gharibian, Sevag, and Jonas Kamminga. “On the Complexity of Estimating Ground
    State Entanglement and Free  Energy.” <i>ArXiv:2510.06796</i>, 2025.
  short: S. Gharibian, J. Kamminga, ArXiv:2510.06796 (2025).
date_created: 2025-10-10T13:45:28Z
date_updated: 2026-04-30T14:08:44Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2510.06796'
language:
- iso: eng
publication: arXiv:2510.06796
status: public
title: On the complexity of estimating ground state entanglement and free  energy
type: preprint
user_id: '71541'
year: '2025'
...
---
_id: '61776'
abstract:
- lang: eng
  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."
author:
- first_name: Ulysse
  full_name: Chabaud, Ulysse
  last_name: Chabaud
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Saeed
  full_name: Mehraban, Saeed
  last_name: Mehraban
- first_name: Arsalan
  full_name: Motamedi, Arsalan
  last_name: Motamedi
- first_name: Hamid Reza
  full_name: Naeij, Hamid Reza
  last_name: Naeij
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
- first_name: Dhruva
  full_name: Sambrani, Dhruva
  last_name: Sambrani
citation:
  ama: Chabaud U, Gharibian S, Mehraban S, et al. Energy, Bosons and Computational
    Complexity. <i>arXiv:251008545</i>. Published online 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>.
  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}
    }'
  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.
  ieee: U. Chabaud <i>et al.</i>, “Energy, Bosons and Computational Complexity,” <i>arXiv:2510.08545</i>.
    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).
date_created: 2025-10-10T13:44:52Z
date_updated: 2026-05-15T08:39:50Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2510.08545'
language:
- iso: eng
publication: arXiv:2510.08545
status: public
title: Energy, Bosons and Computational Complexity
type: preprint
user_id: '71541'
year: '2025'
...
---
_id: '60432'
abstract:
- lang: eng
  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."
author:
- first_name: Simon-Luca
  full_name: Kremer, Simon-Luca
  last_name: Kremer
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
citation:
  ama: Kremer S-L, Rudolph D, Gharibian S. Quantum k-SAT Related Hypergraph Problems.
    <i>arXiv:250617066</i>. Published online 2025.
  apa: Kremer, S.-L., Rudolph, D., &#38; Gharibian, S. (2025). Quantum k-SAT Related
    Hypergraph Problems. In <i>arXiv:2506.17066</i>.
  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} }'
  chicago: Kremer, Simon-Luca, Dorian Rudolph, and Sevag Gharibian. “Quantum K-SAT
    Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>, 2025.
  ieee: S.-L. Kremer, D. Rudolph, and S. Gharibian, “Quantum k-SAT Related Hypergraph
    Problems,” <i>arXiv:2506.17066</i>. 2025.
  mla: Kremer, Simon-Luca, et al. “Quantum K-SAT Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>,
    2025.
  short: S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
date_created: 2025-06-27T06:56:35Z
date_updated: 2026-05-15T08:41:01Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2506.17066'
language:
- iso: eng
publication: arXiv:2506.17066
status: public
title: Quantum k-SAT Related Hypergraph Problems
type: preprint
user_id: '71541'
year: '2025'
...
---
_id: '56944'
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."
author:
- first_name: Felix
  full_name: Huber, Felix
  last_name: Huber
- first_name: Kevin
  full_name: Thompson, Kevin
  last_name: Thompson
- first_name: Ojas
  full_name: Parekh, Ojas
  last_name: Parekh
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
citation:
  ama: Huber F, Thompson K, Parekh O, Gharibian S. Second order cone relaxations for
    quantum Max Cut. <i>arXiv:241104120</i>. Published online 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>.
  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} }'
  chicago: Huber, Felix, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. “Second
    Order Cone Relaxations for Quantum Max Cut.” <i>ArXiv:2411.04120</i>, 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.
  mla: Huber, Felix, et al. “Second Order Cone Relaxations for Quantum Max Cut.” <i>ArXiv:2411.04120</i>,
    2024.
  short: F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).
date_created: 2024-11-07T12:09:37Z
date_updated: 2026-05-15T08:41:38Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2411.04120'
language:
- iso: eng
publication: arXiv:2411.04120
status: public
title: Second order cone relaxations for quantum Max Cut
type: preprint
user_id: '71541'
year: '2024'
...