@unpublished{61778,
  abstract     = {{Understanding the entanglement structure of local Hamiltonian ground spaces
is a physically motivated problem, with applications ranging from tensor
network design to quantum error-correcting codes. To this end, we study the
complexity of estimating ground state entanglement, and more generally entropy
estimation for low energy states and Gibbs states. We find, in particular, that
the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum
analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a
crucial role for such problems, showing: (1) Detecting a high-entanglement
ground state is qq-QAM-complete, (2) computing an additive error approximation
to the Helmholtz free energy (equivalently, a multiplicative error
approximation to the partition function) is in qq-QAM, (3) detecting a
low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy
states which are close to product states can range from QMA-complete to
QMA(2)-complete. Our results make progress on an open question of [Bravyi,
Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield
the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the
sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).}},
  author       = {{Gharibian, Sevag and Kamminga, Jonas}},
  booktitle    = {{arXiv:2510.06796}},
  title        = {{{On the complexity of estimating ground state entanglement and free  energy}}},
  year         = {{2025}},
}

@unpublished{61776,
  abstract     = {{We investigate the role of energy, i.e. average photon number, as a resource
in the computational complexity of bosonic systems. We show three sets of
results: (1. Energy growth rates) There exist bosonic gate sets which increase
energy incredibly rapidly, obtaining e.g. infinite energy in finite/constant
time. We prove these high energies can make computing properties of bosonic
computations, such as deciding whether a given computation will attain infinite
energy, extremely difficult, formally undecidable. (2. Lower bounds on
computational power) More energy ``='' more computational power. For example,
certain gate sets allow poly-time bosonic computations to simulate PTOWER, the
set of deterministic computations whose runtime scales as a tower of
exponentials with polynomial height. Even just exponential energy and $O(1)$
modes suffice to simulate NP, which, importantly, is a setup similar to that of
the recent bosonic factoring algorithm of [Brenner, Caha, Coiteux-Roy and
Koenig (2024)]. For simpler gate sets, we show an energy hierarchy theorem. (3.
Upper bounds on computational power) Bosonic computations with polynomial
energy can be simulated in BQP, ``physical'' bosonic computations with
arbitrary finite energy are decidable, and the gate set consisting of Gaussian
gates and the cubic phase gate can be simulated in PP, with exponential bound
on energy, improving upon the previous PSPACE upper bound. Finally, combining
upper and lower bounds yields no-go theorems for a continuous-variable
Solovay--Kitaev theorem for gate sets such as the Gaussian and cubic phase
gates.}},
  author       = {{Chabaud, Ulysse and Gharibian, Sevag and Mehraban, Saeed and Motamedi, Arsalan and Naeij, Hamid Reza and Rudolph, Dorian and Sambrani, Dhruva}},
  booktitle    = {{arXiv:2510.08545}},
  title        = {{{Energy, Bosons and Computational Complexity}}},
  year         = {{2025}},
}

@unpublished{60432,
  abstract     = {{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 the ground state of the k-local Hamiltonian
minimizes the energy of every local interaction term simultaneously. This is a
central question in quantum physics and a canonical QMA_1-complete problem. The
Quantum k-SAT problem is not as well studied as the classical k-SAT problem in
terms of special tractable cases, approximation algorithms and parameterized
complexity. In this paper, we will give a graph-theoretic study of the Quantum
k-SAT problem with the structures core and radius. These hypergraph structures
are important to solve the Quantum k-SAT problem. We can solve a Quantum k-SAT
instance in polynomial time if the derived hypergraph has a core of size n-m+a,
where a is a constant, and the radius is at most logarithmic. If it exists, we
can find a core of size n-m+a with the best possible radius in polynomial time,
whereas finding a general minimum core with minimal radius is NP-hard.}},
  author       = {{Kremer, Simon-Luca and Rudolph, Dorian and Gharibian, Sevag}},
  booktitle    = {{arXiv:2506.17066}},
  title        = {{{Quantum k-SAT Related Hypergraph Problems}}},
  year         = {{2025}},
}

@unpublished{56944,
  abstract     = {{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 theoretical approximation algorithms for QMC, but are
computationally expensive for systems beyond tens of qubits. We give a second
order cone relaxation for QMC, which optimizes over the set of mutually
consistent three-qubit reduced density matrices. In combination with Pauli
level-$1$ of the quantum Lasserre hierarchy, the relaxation achieves an
approximation ratio of $0.526$ to the ground state energy. Our relaxation is
solvable on systems with hundreds of qubits and paves the way to
computationally efficient lower and upper bounds on the ground state energy of
large-scale quantum spin systems.}},
  author       = {{Huber, Felix and Thompson, Kevin and Parekh, Ojas and Gharibian, Sevag}},
  booktitle    = {{arXiv:2411.04120}},
  title        = {{{Second order cone relaxations for quantum Max Cut}}},
  year         = {{2024}},
}