---
_id: '61922'
abstract:
- lang: eng
  text: "We present an extremely simple polynomial-space exponential-time\r\n$(1-\\varepsilon)$-approximation
    algorithm for MAX-k-SAT that is (slightly)\r\nfaster than the previous known polynomial-space
    $(1-\\varepsilon)$-approximation\r\nalgorithms by Hirsch (Discrete Applied Mathematics,
    2003) and Escoffier,\r\nPaschos and Tourniaire (Theoretical Computer Science,
    2014). Our algorithm\r\nrepeatedly samples an assignment uniformly at random until
    finding an\r\nassignment that satisfies a large enough fraction of clauses. Surprisingly,
    we\r\ncan show the efficiency of this simpler approach by proving that in any\r\ninstance
    of MAX-k-SAT (or more generally any instance of MAXCSP), an\r\nexponential number
    of assignments satisfy a fraction of clauses close to the\r\noptimal value."
author:
- first_name: Harry
  full_name: Buhrman, Harry
  last_name: Buhrman
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Zeph
  full_name: Landau, Zeph
  last_name: Landau
- first_name: François Le
  full_name: Gall, François Le
  last_name: Gall
- first_name: Norbert
  full_name: Schuch, Norbert
  last_name: Schuch
- first_name: Suguru
  full_name: Tamaki, Suguru
  last_name: Tamaki
citation:
  ama: 'Buhrman H, Gharibian S, Landau Z, Gall FL, Schuch N, Tamaki S. A Simpler Exponential-Time
    Approximation Algorithm for MAX-k-SAT. In: <i>SIAM Symposium on Simplicity in
    Algorithms (SOSA)</i>. ; :247-253.'
  apa: Buhrman, H., Gharibian, S., Landau, Z., Gall, F. L., Schuch, N., &#38; Tamaki,
    S. (n.d.). A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. <i>SIAM
    Symposium on Simplicity in Algorithms (SOSA)</i>, 247–253.
  bibtex: '@inproceedings{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki, title={A Simpler
    Exponential-Time Approximation Algorithm for MAX-k-SAT}, booktitle={SIAM Symposium
    on Simplicity in Algorithms (SOSA)}, author={Buhrman, Harry and Gharibian, Sevag
    and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru},
    pages={247–253} }'
  chicago: Buhrman, Harry, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert
    Schuch, and Suguru Tamaki. “A Simpler Exponential-Time Approximation Algorithm
    for MAX-k-SAT.” In <i>SIAM Symposium on Simplicity in Algorithms (SOSA)</i>, 247–53,
    n.d.
  ieee: H. Buhrman, S. Gharibian, Z. Landau, F. L. Gall, N. Schuch, and S. Tamaki,
    “A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT,” in <i>SIAM
    Symposium on Simplicity in Algorithms (SOSA)</i>, pp. 247–253.
  mla: Buhrman, Harry, et al. “A Simpler Exponential-Time Approximation Algorithm
    for MAX-k-SAT.” <i>SIAM Symposium on Simplicity in Algorithms (SOSA)</i>, pp.
    247–53.
  short: 'H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, in:
    SIAM Symposium on Simplicity in Algorithms (SOSA), n.d., pp. 247–253.'
date_created: 2025-10-22T09:33:22Z
date_updated: 2026-04-20T13:53:03Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2510.18164'
language:
- iso: eng
page: 247-253
publication: SIAM Symposium on Simplicity in Algorithms (SOSA)
publication_status: inpress
status: public
title: A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
type: conference
user_id: '71541'
year: '2026'
...
---
_id: '57866'
abstract:
- lang: eng
  text: "The theory of Total Function NP (TFNP) and its subclasses says that, even
    if\r\none is promised an efficiently verifiable proof exists for a problem, finding\r\nthis
    proof can be intractable. Despite the success of the theory at showing\r\nintractability
    of problems such as computing Brouwer fixed points and Nash\r\nequilibria, subclasses
    of TFNP remain arguably few and far between. In this\r\nwork, we define two new
    subclasses of TFNP borne of the study of complex\r\npolynomial systems: Multi-homogeneous
    Systems (MHS) and Sparse Fundamental\r\nTheorem of Algebra (SFTA). The first of
    these is based on B\\'ezout's theorem\r\nfrom algebraic geometry, marking the
    first TFNP subclass based on an algebraic\r\ngeometric principle. At the heart
    of our study is the computational problem\r\nknown as Quantum SAT (QSAT) with
    a System of Distinct Representatives (SDR),\r\nfirst studied by [Laumann, L\\\"auchli,
    Moessner, Scardicchio, and Sondhi 2010].\r\nAmong other results, we show that
    QSAT with SDR is MHS-complete, thus giving\r\nnot only the first link between
    quantum complexity theory and TFNP, but also\r\nthe first TFNP problem whose classical
    variant (SAT with SDR) is easy but whose\r\nquantum variant is hard. We also show
    how to embed the roots of a sparse,\r\nhigh-degree, univariate polynomial into
    QSAT with SDR, obtaining that SFTA is\r\ncontained in a zero-error version of
    MHS. We conjecture this construction also\r\nworks in the low-error setting, which
    would imply SFTA is contained in MHS."
author:
- first_name: Marco
  full_name: Aldi, Marco
  last_name: Aldi
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
citation:
  ama: 'Aldi M, Gharibian S, Rudolph D. An unholy trinity: TFNP, polynomial systems,
    and the quantum  satisfiability problem. In: <i>17th Innovations in Theoretical
    Computer Science Conference (ITCS 2026)</i>. Vol 362. ; 2026:7:1-7:24.'
  apa: 'Aldi, M., Gharibian, S., &#38; Rudolph, D. (2026). An unholy trinity: TFNP,
    polynomial systems, and the quantum  satisfiability problem. <i>17th Innovations
    in Theoretical Computer Science Conference (ITCS 2026)</i>, <i>362</i>, 7:1-7:24.'
  bibtex: '@inproceedings{Aldi_Gharibian_Rudolph_2026, title={An unholy trinity: TFNP,
    polynomial systems, and the quantum  satisfiability problem}, volume={362}, booktitle={17th
    Innovations in Theoretical Computer Science Conference (ITCS 2026)}, author={Aldi,
    Marco and Gharibian, Sevag and Rudolph, Dorian}, year={2026}, pages={7:1-7:24}
    }'
  chicago: 'Aldi, Marco, Sevag Gharibian, and Dorian Rudolph. “An Unholy Trinity:
    TFNP, Polynomial Systems, and the Quantum  Satisfiability Problem.” In <i>17th
    Innovations in Theoretical Computer Science Conference (ITCS 2026)</i>, 362:7:1-7:24,
    2026.'
  ieee: 'M. Aldi, S. Gharibian, and D. Rudolph, “An unholy trinity: TFNP, polynomial
    systems, and the quantum  satisfiability problem,” in <i>17th Innovations in Theoretical
    Computer Science Conference (ITCS 2026)</i>, 2026, vol. 362, p. 7:1-7:24.'
  mla: 'Aldi, Marco, et al. “An Unholy Trinity: TFNP, Polynomial Systems, and the
    Quantum  Satisfiability Problem.” <i>17th Innovations in Theoretical Computer
    Science Conference (ITCS 2026)</i>, vol. 362, 2026, p. 7:1-7:24.'
  short: 'M. Aldi, S. Gharibian, D. Rudolph, in: 17th Innovations in Theoretical Computer
    Science Conference (ITCS 2026), 2026, p. 7:1-7:24.'
date_created: 2024-12-30T13:55:27Z
date_updated: 2026-05-15T08:40:28Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2412.19623'
intvolume: '       362'
language:
- iso: eng
page: 7:1-7:24
publication: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)
publication_status: published
status: public
title: 'An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability
  problem'
type: conference
user_id: '71541'
volume: 362
year: '2026'
...
---
_id: '67088'
abstract:
- lang: eng
  text: We prove quantitative lower bounds on the semidefinite extension complexity
    of the set of separable quantum states on $\mathbb{C}^d\otimes\mathbb{C}^d$. We
    consider semidefinite programs (SDPs) that approximate the maximum acceptance
    probability of a measurement over separable states, the optimization problem underlying
    QMA(2). In the extended-formulation model of Harrow, Natarajan, and Wu (HNW),
    all measurements share a common feasible region and an objective-independent embedding
    of product states that exactly reproduces their acceptance probabilities. For
    every $0<θ<2/7$, there are constants $c_θ,a_θ>0$ such that, for sufficiently large
    $d$, any such SDP with uniform additive error $0<a\le a_θ$ has size at least $d^{c_θ\min\{a^{-1/3},d^θ\}}$.
    The bound applies at sufficiently small constant error, is superpolynomial in
    $d$ whenever $a=o(1)$, and becomes $d^{Ω(d^θ)}$ when $a\le d^{-3θ}$, improving
    HNW's quasipolynomial bound at inverse- square error. The same bound holds for
    any SDP-representable convex set of states that contains all separable states
    and lies within trace distance $a$ of them, giving a quantitative counterpart
    to Fawzi's theorem that the separable set has no exact semidefinite representation.
    Our proof combines the quantitative pseudo-density theorem of Lee, Raghavendra,
    and Steurer with explicit block-positive operators and Chebyshev amplification.
    Our main results are supported by Lean proofs.
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Carsten
  full_name: Hecht, Carsten
  last_name: Hecht
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
citation:
  ama: Gharibian S, Hecht C, Rudolph D. Semidefinite extension complexity of the separable
    set, with applications to approximate disentanglers. <i>arXiv:260909033</i>.
  apa: Gharibian, S., Hecht, C., &#38; Rudolph, D. (n.d.). Semidefinite extension
    complexity of the separable set, with applications to approximate disentanglers.
    In <i>arXiv:2609.09033</i>.
  bibtex: '@article{Gharibian_Hecht_Rudolph, title={Semidefinite extension complexity
    of the separable set, with applications to approximate disentanglers}, journal={arXiv:2609.09033},
    author={Gharibian, Sevag and Hecht, Carsten and Rudolph, Dorian} }'
  chicago: Gharibian, Sevag, Carsten Hecht, and Dorian Rudolph. “Semidefinite Extension
    Complexity of the Separable Set, with Applications to Approximate Disentanglers.”
    <i>ArXiv:2609.09033</i>, n.d.
  ieee: S. Gharibian, C. Hecht, and D. Rudolph, “Semidefinite extension complexity
    of the separable set, with applications to approximate disentanglers,” <i>arXiv:2609.09033</i>.
    .
  mla: Gharibian, Sevag, et al. “Semidefinite Extension Complexity of the Separable
    Set, with Applications to Approximate Disentanglers.” <i>ArXiv:2609.09033</i>.
  short: S. Gharibian, C. Hecht, D. Rudolph, ArXiv:2609.09033 (n.d.).
date_created: 2026-09-09T12:06:36Z
date_updated: 2026-09-09T12:07:31Z
external_id:
  arxiv:
  - '2609.09033'
language:
- iso: eng
publication: arXiv:2609.09033
publication_status: unpublished
status: public
title: Semidefinite extension complexity of the separable set, with applications to
  approximate disentanglers
type: preprint
user_id: '71541'
year: '2026'
...
---
_id: '67292'
abstract:
- lang: eng
  text: 'Classical shadows are an influential framework for compressing copies of
    a given quantum state $ρ$ into classical data $S$, enabling many properties of
    $ρ$ to be predicted from relatively few copies. In this work, we study two natural
    questions involving shadows: (1) Given $S$, when can one efficiently verify that
    $S$ came from a genuine $n$-qubit state? This is called the Classical Shadow Validity
    (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian
    [ICALP 2026]. (2) Given $S$ that allows one to capture 2-local properties of $ρ$,
    can one fake or spoof a shadow $S''$ which predicts 3-local properties of some
    state? For (1), we show CSV is efficiently solvable for permutation-invariant
    shadows, QMA-hard for real, fermionic, and bosonic shadows, and both coNP-hard
    and QMA-hard when the observable family consists of all $n$-qubit Pauli strings.
    A result of independent interest along the way is a new upper bound qc-$Σ_2$ $\subseteq$
    $\mathrm{P}^{\mathrm{PP}}$, where qc-$Σ_2$ is a quantum analogue of the second
    level of the polynomial hierarchy in which the first proof is quantum. For (2),
    we show intractability: Given the 2-local marginals $S$ of a quantum state $ρ$,
    estimating the 3-local marginals of $ρ$ is intractable unless QCMA $\subseteq$
    BPP, even if the state $ρ$ is the unique state consistent with $S$.'
author:
- first_name: Georgios
  full_name: Karaiskos, Georgios
  last_name: Karaiskos
- first_name: Asad
  full_name: Raza, Asad
  last_name: Raza
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
- first_name: Dax Enshan
  full_name: Koh, Dax Enshan
  last_name: Koh
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
citation:
  ama: Karaiskos G, Raza A, Rudolph D, Koh DE, Gharibian S. Verification Complexity
    and Extension of Classical Shadows. <i>arXiv:260940107</i>. Published online 2026.
  apa: Karaiskos, G., Raza, A., Rudolph, D., Koh, D. E., &#38; Gharibian, S. (2026).
    Verification Complexity and Extension of Classical Shadows. In <i>arXiv:2609.40107</i>.
  bibtex: '@article{Karaiskos_Raza_Rudolph_Koh_Gharibian_2026, title={Verification
    Complexity and Extension of Classical Shadows}, journal={arXiv:2609.40107}, author={Karaiskos,
    Georgios and Raza, Asad and Rudolph, Dorian and Koh, Dax Enshan and Gharibian,
    Sevag}, year={2026} }'
  chicago: Karaiskos, Georgios, Asad Raza, Dorian Rudolph, Dax Enshan Koh, and Sevag
    Gharibian. “Verification Complexity and Extension of Classical Shadows.” <i>ArXiv:2609.40107</i>,
    2026.
  ieee: G. Karaiskos, A. Raza, D. Rudolph, D. E. Koh, and S. Gharibian, “Verification
    Complexity and Extension of Classical Shadows,” <i>arXiv:2609.40107</i>. 2026.
  mla: Karaiskos, Georgios, et al. “Verification Complexity and Extension of Classical
    Shadows.” <i>ArXiv:2609.40107</i>, 2026.
  short: G. Karaiskos, A. Raza, D. Rudolph, D.E. Koh, S. Gharibian, ArXiv:2609.40107
    (2026).
date_created: 2026-10-01T07:32:45Z
date_updated: 2026-10-01T07:33:38Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2609.40107'
language:
- iso: eng
publication: arXiv:2609.40107
status: public
title: Verification Complexity and Extension of Classical Shadows
type: preprint
user_id: '71541'
year: '2026'
...
---
_id: '67293'
abstract:
- lang: eng
  text: Low-energy estimation and state preparation for general $k$-local Hamiltonians
    are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST,
    PRL 2025] recently broke the natural Grover bound $O^\ast(2^{n/2})$ for both problems,
    with the improvement depending on the relative accuracy $\varepsilon$ and the
    locality $k$. In this work, we present faster exponential quantum algorithms for
    these problems, where the binary entropy function governs the runtime exponent.
    For sufficiently small $\varepsilon/k$, our algorithms improve the exponent by
    a factor of $\log(k/\varepsilon)$ over [BGLGST, PRL 2025]. Our main technical
    result is an entropy-governed lower bound on the dimension of the Hamiltonian's
    low-energy subspace, obtained by depolarizing its ground state. For fixed $k$,
    this bound is optimal up to constant factors in the exponent. The same framework
    yields tighter bounds for Heisenberg, $XY$, and Ising models on arbitrary interaction
    graphs.
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Francois
  full_name: Le Gall, Francois
  last_name: Le Gall
- first_name: Ranitha
  full_name: Mataraarachchi, Ranitha
  last_name: Mataraarachchi
- first_name: Suguru
  full_name: Tamaki, Suguru
  last_name: Tamaki
citation:
  ama: Gharibian S, Le Gall F, Mataraarachchi R, Tamaki S. Near-Optimal Bounds on
    the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum
    Algorithms. Published online 2026.
  apa: Gharibian, S., Le Gall, F., Mataraarachchi, R., &#38; Tamaki, S. (2026). <i>Near-Optimal
    Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster
    Quantum Algorithms</i>.
  bibtex: '@article{Gharibian_Le Gall_Mataraarachchi_Tamaki_2026, title={Near-Optimal
    Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster
    Quantum Algorithms}, author={Gharibian, Sevag and Le Gall, Francois and Mataraarachchi,
    Ranitha and Tamaki, Suguru}, year={2026} }'
  chicago: Gharibian, Sevag, Francois Le Gall, Ranitha Mataraarachchi, and Suguru
    Tamaki. “Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local
    Hamiltonians and Faster Quantum Algorithms,” 2026.
  ieee: S. Gharibian, F. Le Gall, R. Mataraarachchi, and S. Tamaki, “Near-Optimal
    Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster
    Quantum Algorithms.” 2026.
  mla: Gharibian, Sevag, et al. <i>Near-Optimal Bounds on the Density of Low-Energy
    States of $k$-Local Hamiltonians and Faster Quantum Algorithms</i>. 2026.
  short: S. Gharibian, F. Le Gall, R. Mataraarachchi, S. Tamaki, (2026).
date_created: 2026-10-01T07:35:41Z
date_updated: 2026-10-01T08:21:44Z
department:
- _id: '7'
- _id: '623'
language:
- iso: eng
status: public
title: Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians
  and Faster Quantum Algorithms
type: preprint
user_id: '71541'
year: '2026'
...
---
_id: '67291'
author:
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
- first_name: Arsalan
  full_name: Motamedi, Arsalan
  last_name: Motamedi
- first_name: Dhruva
  full_name: Sambrani, Dhruva
  id: '103068'
  last_name: Sambrani
- first_name: Hamid
  full_name: Reza Naeij, Hamid
  last_name: Reza Naeij
- 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
citation:
  ama: Rudolph D, Motamedi A, Sambrani D, et al. A physical and universal model of
    bosonic computations with Solovay-Kitaev theorem.
  apa: Rudolph, D., Motamedi, A., Sambrani, D., Reza Naeij, H., Chabaud, U., Gharibian,
    S., &#38; Mehraban, S. (n.d.). <i>A physical and universal model of bosonic computations
    with Solovay-Kitaev theorem</i>.
  bibtex: '@article{Rudolph_Motamedi_Sambrani_Reza Naeij_Chabaud_Gharibian_Mehraban,
    title={A physical and universal model of bosonic computations with Solovay-Kitaev
    theorem}, author={Rudolph, Dorian and Motamedi, Arsalan and Sambrani, Dhruva and
    Reza Naeij, Hamid and Chabaud, Ulysse and Gharibian, Sevag and Mehraban, Saeed}
    }'
  chicago: Rudolph, Dorian, Arsalan Motamedi, Dhruva Sambrani, Hamid Reza Naeij, Ulysse
    Chabaud, Sevag Gharibian, and Saeed Mehraban. “A Physical and Universal Model
    of Bosonic Computations with Solovay-Kitaev Theorem,” n.d.
  ieee: D. Rudolph <i>et al.</i>, “A physical and universal model of bosonic computations
    with Solovay-Kitaev theorem.” .
  mla: Rudolph, Dorian, et al. <i>A Physical and Universal Model of Bosonic Computations
    with Solovay-Kitaev Theorem</i>.
  short: D. Rudolph, A. Motamedi, D. Sambrani, H. Reza Naeij, U. Chabaud, S. Gharibian,
    S. Mehraban, (n.d.).
date_created: 2026-10-01T07:24:03Z
date_updated: 2026-10-01T07:32:01Z
department:
- _id: '7'
- _id: '623'
language:
- iso: eng
publication_status: unpublished
status: public
title: A physical and universal model of bosonic computations with Solovay-Kitaev
  theorem
type: preprint
user_id: '71541'
year: '2026'
...
---
_id: '61777'
abstract:
- lang: eng
  text: "Classical shadows are succinct classical representations of quantum states\r\nwhich
    allow one to encode a set of properties P of a quantum state rho, while\r\nonly
    requiring measurements on logarithmically many copies of rho in the size\r\nof
    P. In this work, we initiate the study of verification of classical shadows,\r\ndenoted
    classical shadow validity (CSV), from the perspective of computational\r\ncomplexity,
    which asks: Given a classical shadow S, how hard is it to verify\r\nthat S predicts
    the measurement statistics of a quantum state? We show that\r\neven for the elegantly
    simple classical shadow protocol of [Huang, Kueng,\r\nPreskill, Nature Physics
    2020] utilizing local Clifford measurements, CSV is\r\nQMA-complete. This hardness
    continues to hold for the high-dimensional\r\nextension of said protocol due to
    [Mao, Yi, and Zhu, PRL 2025]. Among other\r\nresults, we also show that CSV for
    exponentially many observables is complete\r\nfor a quantum generalization of
    the second level of the polynomial hierarchy,\r\nyielding the first natural complete
    problem for such a class."
author:
- first_name: Georgios
  full_name: Karaiskos, Georgios
  last_name: Karaiskos
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
- first_name: Johannes Jakob
  full_name: Meyer, Johannes Jakob
  last_name: Meyer
- first_name: Jens
  full_name: Eisert, Jens
  last_name: Eisert
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
citation:
  ama: 'Karaiskos G, Rudolph D, Meyer JJ, Eisert J, Gharibian S. How hard is it to
    verify a classical shadow? In: <i>International Colloquium on Automata, Languages,
    and Programming (ICALP)</i>. Vol 374. ; 2026:1-23.'
  apa: Karaiskos, G., Rudolph, D., Meyer, J. J., Eisert, J., &#38; Gharibian, S. (2026).
    How hard is it to verify a classical shadow? <i>International Colloquium on Automata,
    Languages, and Programming (ICALP)</i>, <i>374</i>(123), 1–23.
  bibtex: '@inproceedings{Karaiskos_Rudolph_Meyer_Eisert_Gharibian_2026, title={How
    hard is it to verify a classical shadow?}, volume={374}, number={123}, booktitle={International
    Colloquium on Automata, Languages, and Programming (ICALP)}, author={Karaiskos,
    Georgios and Rudolph, Dorian and Meyer, Johannes Jakob and Eisert, Jens and Gharibian,
    Sevag}, year={2026}, pages={1–23} }'
  chicago: Karaiskos, Georgios, Dorian Rudolph, Johannes Jakob Meyer, Jens Eisert,
    and Sevag Gharibian. “How Hard Is It to Verify a Classical Shadow?” In <i>International
    Colloquium on Automata, Languages, and Programming (ICALP)</i>, 374:1–23, 2026.
  ieee: G. Karaiskos, D. Rudolph, J. J. Meyer, J. Eisert, and S. Gharibian, “How hard
    is it to verify a classical shadow?,” in <i>International Colloquium on Automata,
    Languages, and Programming (ICALP)</i>, 2026, vol. 374, no. 123, pp. 1–23.
  mla: Karaiskos, Georgios, et al. “How Hard Is It to Verify a Classical Shadow?”
    <i>International Colloquium on Automata, Languages, and Programming (ICALP)</i>,
    vol. 374, no. 123, 2026, pp. 1–23.
  short: 'G. Karaiskos, D. Rudolph, J.J. Meyer, J. Eisert, S. Gharibian, in: International
    Colloquium on Automata, Languages, and Programming (ICALP), 2026, pp. 1–23.'
date_created: 2025-10-10T13:45:07Z
date_updated: 2026-07-01T15:30:26Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2510.08515'
intvolume: '       374'
issue: '123'
language:
- iso: eng
page: 1-23
publication: International Colloquium on Automata, Languages, and Programming (ICALP)
publication_status: published
status: public
title: How hard is it to verify a classical shadow?
type: conference
user_id: '71541'
volume: 374
year: '2026'
...
---
_id: '56950'
abstract:
- lang: eng
  text: "After nearly two decades of research, the question of a quantum PCP theorem\r\nfor
    quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a\r\nresult,
    proving QMA-hardness of approximation for ground state energy\r\nestimation has
    remained elusive. Recently, it was shown [Bittel, Gharibian,\r\nKliesch, CCC 2023]
    that a natural problem involving variational quantum\r\ncircuits is QCMA-hard
    to approximate within ratio N^(1-eps) for any eps > 0 and\r\nN the input size.
    Unfortunately, this problem was not related to quantum CSPs,\r\nleaving the question
    of hardness of approximation for quantum CSPs open. In\r\nthis work, we show that
    if instead of focusing on ground state energies, one\r\nconsiders computing properties
    of the ground space, QCMA-hardness of computing\r\nground space properties can
    be shown. In particular, we show that it is (1)\r\nQCMA-complete within ratio
    N^(1-eps) to approximate the Ground State\r\nConnectivity problem (GSCON), and
    (2) QCMA-hard within the same ratio to\r\nestimate the amount of entanglement
    of a local Hamiltonian's ground state,\r\ndenoted Ground State Entanglement (GSE).
    As a bonus, a simplification of our\r\nconstruction yields NP-completeness of
    approximation for a natural k-SAT\r\nreconfiguration problem, to be contrasted
    with the recent PCP-based PSPACE\r\nhardness of approximation results for a different
    definition of k-SAT\r\nreconfiguration [Karthik C.S. and Manurangsi, 2023, and
    Hirahara, Ohsaka, STOC\r\n2024]."
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Carsten
  full_name: Hecht, Carsten
  last_name: Hecht
citation:
  ama: 'Gharibian S, Hecht C. Hardness of approximation for ground state problems.
    In: <i>51st International Symposium on Mathematical Foundations of Computer Science
    (MFCS)</i>. Vol 386. ; :1-19.'
  apa: Gharibian, S., &#38; Hecht, C. (n.d.). Hardness of approximation for ground
    state problems. <i>51st International Symposium on Mathematical Foundations of
    Computer Science (MFCS)</i>, <i>386</i>(48), 1–19.
  bibtex: '@inproceedings{Gharibian_Hecht, title={Hardness of approximation for ground
    state problems}, volume={386}, number={48}, booktitle={51st International Symposium
    on Mathematical Foundations of Computer Science (MFCS)}, author={Gharibian, Sevag
    and Hecht, Carsten}, pages={1–19} }'
  chicago: Gharibian, Sevag, and Carsten Hecht. “Hardness of Approximation for Ground
    State Problems.” In <i>51st International Symposium on Mathematical Foundations
    of Computer Science (MFCS)</i>, 386:1–19, n.d.
  ieee: S. Gharibian and C. Hecht, “Hardness of approximation for ground state problems,”
    in <i>51st International Symposium on Mathematical Foundations of Computer Science
    (MFCS)</i>, vol. 386, no. 48, pp. 1–19.
  mla: Gharibian, Sevag, and Carsten Hecht. “Hardness of Approximation for Ground
    State Problems.” <i>51st International Symposium on Mathematical Foundations of
    Computer Science (MFCS)</i>, vol. 386, no. 48, pp. 1–19.
  short: 'S. Gharibian, C. Hecht, in: 51st International Symposium on Mathematical
    Foundations of Computer Science (MFCS), n.d., pp. 1–19.'
date_created: 2024-11-08T07:58:24Z
date_updated: 2026-09-08T20:37:14Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2411.04874'
intvolume: '       386'
issue: '48'
language:
- iso: eng
page: 1-19
publication: 51st International Symposium on Mathematical Foundations of Computer
  Science (MFCS)
publication_status: accepted
status: public
title: Hardness of approximation for ground state problems
type: conference
user_id: '71541'
volume: 386
year: '2026'
...
---
_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: '50272'
abstract:
- lang: eng
  text: "Despite the fundamental role the Quantum Satisfiability (QSAT) problem has\r\nplayed
    in quantum complexity theory, a central question remains open: At which\r\nlocal
    dimension does the complexity of QSAT transition from \"easy\" to \"hard\"?\r\nHere,
    we study QSAT with each constraint acting on a $k$-dimensional and\r\n$l$-dimensional
    qudit pair, denoted $(k,l)$-QSAT. Our first main result shows\r\nthat, surprisingly,
    QSAT on qubits can remain $\\mathsf{QMA}_1$-hard, in that\r\n$(2,5)$-QSAT is $\\mathsf{QMA}_1$-complete.
    In contrast, $2$-SAT on qubits is\r\nwell-known to be poly-time solvable [Bravyi,
    2006]. Our second main result\r\nproves that $(3,d)$-QSAT on the 1D line with
    $d\\in O(1)$ is also\r\n$\\mathsf{QMA}_1$-hard. Finally, we initiate the study
    of 1D $(2,d)$-QSAT by\r\ngiving a frustration-free 1D Hamiltonian with a unique,
    entangled ground state.\r\n  Our first result uses a direct embedding, combining
    a novel clock\r\nconstruction with the 2D circuit-to-Hamiltonian construction
    of [Gosset, Nagaj,\r\n2013]. Of note is a new simplified and analytic proof for
    the latter (as\r\nopposed to a partially numeric proof in [GN13]). This exploits
    Unitary Labelled\r\nGraphs [Bausch, Cubitt, Ozols, 2017] together with a new \"Nullspace
    Connection\r\nLemma\", allowing us to break low energy analyses into small patches
    of\r\nprojectors, and to improve the soundness analysis of [GN13] from\r\n$\\Omega(1/T^6)$
    to $\\Omega(1/T^2)$, for $T$ the number of gates. Our second\r\nresult goes via
    black-box reduction: Given an arbitrary 1D Hamiltonian $H$ on\r\n$d'$-dimensional
    qudits, we show how to embed it into an effective null-space\r\nof a 1D $(3,d)$-QSAT
    instance, for $d\\in O(1)$. Our approach may be viewed as a\r\nweaker notion of
    \"simulation\" (\\`a la [Bravyi, Hastings 2017], [Cubitt,\r\nMontanaro, Piddock
    2018]). As far as we are aware, this gives the first\r\n\"black-box simulation\"-based
    $\\mathsf{QMA}_1$-hardness result, i.e. for\r\nfrustration-free Hamiltonians."
author:
- 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
- first_name: Daniel
  full_name: Nagaj, Daniel
  last_name: Nagaj
citation:
  ama: 'Rudolph D, Gharibian S, Nagaj D. Quantum 2-SAT on low dimensional systems
    is $\mathsf{QMA}_1$-complete:  Direct embeddings and black-box simulation. In:
    <i>16th Innovations in Theoretical Computer Science (ITCS)</i>. Vol 325. ; 2025:1-24.
    doi:<a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">10.4230/LIPIcs.ITCS.2025.85</a>'
  apa: Rudolph, D., Gharibian, S., &#38; Nagaj, D. (2025). Quantum 2-SAT on low dimensional
    systems is $\mathsf{QMA}_1$-complete:  Direct embeddings and black-box simulation.
    <i>16th Innovations in Theoretical Computer Science (ITCS)</i>, <i>325</i>(85),
    1–24. <a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">https://doi.org/10.4230/LIPIcs.ITCS.2025.85</a>
  bibtex: '@inproceedings{Rudolph_Gharibian_Nagaj_2025, title={Quantum 2-SAT on low
    dimensional systems is $\mathsf{QMA}_1$-complete:  Direct embeddings and black-box
    simulation}, volume={325}, DOI={<a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">10.4230/LIPIcs.ITCS.2025.85</a>},
    number={85}, booktitle={16th Innovations in Theoretical Computer Science (ITCS)},
    author={Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel}, year={2025},
    pages={1–24} }'
  chicago: Rudolph, Dorian, Sevag Gharibian, and Daniel Nagaj. “Quantum 2-SAT on Low
    Dimensional Systems Is $\mathsf{QMA}_1$-Complete:  Direct Embeddings and Black-Box
    Simulation.” In <i>16th Innovations in Theoretical Computer Science (ITCS)</i>,
    325:1–24, 2025. <a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">https://doi.org/10.4230/LIPIcs.ITCS.2025.85</a>.
  ieee: 'D. Rudolph, S. Gharibian, and D. Nagaj, “Quantum 2-SAT on low dimensional
    systems is $\mathsf{QMA}_1$-complete:  Direct embeddings and black-box simulation,”
    in <i>16th Innovations in Theoretical Computer Science (ITCS)</i>, 2025, vol.
    325, no. 85, pp. 1–24, doi: <a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">10.4230/LIPIcs.ITCS.2025.85</a>.'
  mla: Rudolph, Dorian, et al. “Quantum 2-SAT on Low Dimensional Systems Is $\mathsf{QMA}_1$-Complete: 
    Direct Embeddings and Black-Box Simulation.” <i>16th Innovations in Theoretical
    Computer Science (ITCS)</i>, vol. 325, no. 85, 2025, pp. 1–24, doi:<a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">10.4230/LIPIcs.ITCS.2025.85</a>.
  short: 'D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical
    Computer Science (ITCS), 2025, pp. 1–24.'
date_created: 2024-01-07T20:09:13Z
date_updated: 2026-05-15T08:38:31Z
department:
- _id: '7'
- _id: '623'
doi: 10.4230/LIPIcs.ITCS.2025.85
external_id:
  arxiv:
  - '2401.02368'
intvolume: '       325'
issue: '85'
language:
- iso: eng
page: 1-24
publication: 16th Innovations in Theoretical Computer Science (ITCS)
publication_status: published
status: public
title: 'Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete:  Direct
  embeddings and black-box simulation'
type: conference
user_id: '71541'
volume: 325
year: '2025'
...
---
_id: '55037'
abstract:
- lang: eng
  text: "Estimating ground state energies of many-body Hamiltonians is a central task\r\nin
    many areas of quantum physics. In this work, we give quantum algorithms\r\nwhich,
    given any $k$-body Hamiltonian $H$, compute an estimate for the ground\r\nstate
    energy and prepare a quantum state achieving said energy, respectively.\r\nSpecifically,
    for any $\\varepsilon>0$, our algorithms return, with high\r\nprobability, an
    estimate of the ground state energy of $H$ within additive\r\nerror $\\varepsilon
    M$, or a quantum state with the corresponding energy. Here,\r\n$M$ is the total
    strength of all interaction terms, which in general is\r\nextensive in the system
    size. Our approach makes no assumptions about the\r\ngeometry or spatial locality
    of interaction terms of the input Hamiltonian and\r\nthus handles even long-range
    or all-to-all interactions, such as in quantum\r\nchemistry, where lattice-based
    techniques break down. In this fully general\r\nsetting, the runtime of our algorithms
    scales as $2^{cn/2}$ for $c<1$, yielding\r\nthe first quantum algorithms for low-energy
    estimation breaking the natural\r\nbound based on Grover search. The core of our
    approach is remarkably simple,\r\nand relies on showing that any $k$-body Hamiltonian
    has a low-energy subspace\r\nof exponential dimension."
author:
- first_name: Harry
  full_name: Buhrman, Harry
  last_name: Buhrman
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Zeph
  full_name: Landau, Zeph
  last_name: Landau
- first_name: François Le
  full_name: Gall, François Le
  last_name: Gall
- first_name: Norbert
  full_name: Schuch, Norbert
  last_name: Schuch
- first_name: Suguru
  full_name: Tamaki, Suguru
  last_name: Tamaki
citation:
  ama: Buhrman H, Gharibian S, Landau Z, Gall FL, Schuch N, Tamaki S. Beating Grover
    search for low-energy estimation and state preparation. <i>Physical Review Letters</i>.
    2025;135:030601. doi:<a href="https://doi.org/10.1103/29qw-bssx">10.1103/29qw-bssx</a>
  apa: Buhrman, H., Gharibian, S., Landau, Z., Gall, F. L., Schuch, N., &#38; Tamaki,
    S. (2025). Beating Grover search for low-energy estimation and state preparation.
    <i>Physical Review Letters</i>, <i>135</i>, 030601. <a href="https://doi.org/10.1103/29qw-bssx">https://doi.org/10.1103/29qw-bssx</a>
  bibtex: '@article{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki_2025, title={Beating
    Grover search for low-energy estimation and state preparation}, volume={135},
    DOI={<a href="https://doi.org/10.1103/29qw-bssx">10.1103/29qw-bssx</a>}, journal={Physical
    Review Letters}, author={Buhrman, Harry and Gharibian, Sevag and Landau, Zeph
    and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}, year={2025}, pages={030601}
    }'
  chicago: 'Buhrman, Harry, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert
    Schuch, and Suguru Tamaki. “Beating Grover Search for Low-Energy Estimation and
    State Preparation.” <i>Physical Review Letters</i> 135 (2025): 030601. <a href="https://doi.org/10.1103/29qw-bssx">https://doi.org/10.1103/29qw-bssx</a>.'
  ieee: 'H. Buhrman, S. Gharibian, Z. Landau, F. L. Gall, N. Schuch, and S. Tamaki,
    “Beating Grover search for low-energy estimation and state preparation,” <i>Physical
    Review Letters</i>, vol. 135, p. 030601, 2025, doi: <a href="https://doi.org/10.1103/29qw-bssx">10.1103/29qw-bssx</a>.'
  mla: Buhrman, Harry, et al. “Beating Grover Search for Low-Energy Estimation and
    State Preparation.” <i>Physical Review Letters</i>, vol. 135, 2025, p. 030601,
    doi:<a href="https://doi.org/10.1103/29qw-bssx">10.1103/29qw-bssx</a>.
  short: H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, Physical
    Review Letters 135 (2025) 030601.
date_created: 2024-07-04T09:02:42Z
date_updated: 2026-05-15T08:40:45Z
department:
- _id: '7'
- _id: '623'
doi: 10.1103/29qw-bssx
external_id:
  arxiv:
  - '2407.03073'
intvolume: '       135'
language:
- iso: eng
page: '030601'
publication: Physical Review Letters
publication_status: published
status: public
title: Beating Grover search for low-energy estimation and state preparation
type: journal_article
user_id: '71541'
volume: 135
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: '50273'
abstract:
- lang: eng
  text: "The Polynomial-Time Hierarchy ($\\mathsf{PH}$) is a staple of classical\r\ncomplexity
    theory, with applications spanning randomized computation to circuit\r\nlower
    bounds to ''quantum advantage'' analyses for near-term quantum computers.\r\nQuantumly,
    however, despite the fact that at least \\emph{four} definitions of\r\nquantum
    $\\mathsf{PH}$ exist, it has been challenging to prove analogues for\r\nthese
    of even basic facts from $\\mathsf{PH}$. This work studies three\r\nquantum-verifier
    based generalizations of $\\mathsf{PH}$, two of which are from\r\n[Gharibian,
    Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings\r\n($\\mathsf{QCPH}$)
    and quantum mixed states ($\\mathsf{QPH}$) as proofs, and one\r\nof which is new
    to this work, utilizing quantum pure states\r\n($\\mathsf{pureQPH}$) as proofs.
    We first resolve several open problems from\r\n[GSSSY22], including a collapse
    theorem and a Karp-Lipton theorem for\r\n$\\mathsf{QCPH}$. Then, for our new class
    $\\mathsf{pureQPH}$, we show one-sided\r\nerror reduction for $\\mathsf{pureQPH}$,
    as well as the first bounds relating\r\nthese quantum variants of $\\mathsf{PH}$,
    namely $\\mathsf{QCPH}\\subseteq\r\n\\mathsf{pureQPH} \\subseteq \\mathsf{EXP}^{\\mathsf{PP}}$."
author:
- first_name: Avantika
  full_name: Agarwal, Avantika
  last_name: Agarwal
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Venkata
  full_name: Koppula, Venkata
  last_name: Koppula
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
citation:
  ama: 'Agarwal A, Gharibian S, Koppula V, Rudolph D. Quantum Polynomial Hierarchies:
    Karp-Lipton, error reduction, and lower  bounds. In: <i>Proceedings of 49th International
    Symposium on Mathematical Foundations of Computer Science (MFCS)</i>. Vol 306.
    ; 2024:7-17. doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">10.4230/LIPIcs.MFCS.2024.7</a>'
  apa: 'Agarwal, A., Gharibian, S., Koppula, V., &#38; Rudolph, D. (2024). Quantum
    Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds. <i>Proceedings
    of 49th International Symposium on Mathematical Foundations of Computer Science
    (MFCS)</i>, <i>306</i>(7), 7–17. <a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">https://doi.org/10.4230/LIPIcs.MFCS.2024.7</a>'
  bibtex: '@inproceedings{Agarwal_Gharibian_Koppula_Rudolph_2024, title={Quantum Polynomial
    Hierarchies: Karp-Lipton, error reduction, and lower  bounds}, volume={306}, DOI={<a
    href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">10.4230/LIPIcs.MFCS.2024.7</a>},
    number={7}, booktitle={Proceedings of 49th International Symposium on Mathematical
    Foundations of Computer Science (MFCS)}, author={Agarwal, Avantika and Gharibian,
    Sevag and Koppula, Venkata and Rudolph, Dorian}, year={2024}, pages={7–17} }'
  chicago: 'Agarwal, Avantika, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph.
    “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower  Bounds.”
    In <i>Proceedings of 49th International Symposium on Mathematical Foundations
    of Computer Science (MFCS)</i>, 306:7–17, 2024. <a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">https://doi.org/10.4230/LIPIcs.MFCS.2024.7</a>.'
  ieee: 'A. Agarwal, S. Gharibian, V. Koppula, and D. Rudolph, “Quantum Polynomial
    Hierarchies: Karp-Lipton, error reduction, and lower  bounds,” in <i>Proceedings
    of 49th International Symposium on Mathematical Foundations of Computer Science
    (MFCS)</i>, 2024, vol. 306, no. 7, pp. 7–17, doi: <a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">10.4230/LIPIcs.MFCS.2024.7</a>.'
  mla: 'Agarwal, Avantika, et al. “Quantum Polynomial Hierarchies: Karp-Lipton, Error
    Reduction, and Lower  Bounds.” <i>Proceedings of 49th International Symposium
    on Mathematical Foundations of Computer Science (MFCS)</i>, vol. 306, no. 7, 2024,
    pp. 7–17, doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">10.4230/LIPIcs.MFCS.2024.7</a>.'
  short: 'A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, in: Proceedings of 49th
    International Symposium on Mathematical Foundations of Computer Science (MFCS),
    2024, pp. 7–17.'
date_created: 2024-01-07T20:09:32Z
date_updated: 2026-05-15T08:39:23Z
department:
- _id: '7'
- _id: '623'
doi: 10.4230/LIPIcs.MFCS.2024.7
external_id:
  arxiv:
  - '2401.01633'
intvolume: '       306'
issue: '7'
language:
- iso: eng
page: 7-17
publication: Proceedings of 49th International Symposium on Mathematical Foundations
  of Computer Science (MFCS)
publication_status: published
status: public
title: 'Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds'
type: conference
user_id: '71541'
volume: 306
year: '2024'
...
---
_id: '50406'
abstract:
- lang: eng
  text: "What is the power of polynomial-time quantum computation with access to an
    NP\r\noracle? In this work, we focus on two fundamental tasks from the study of\r\nBoolean
    satisfiability (SAT) problems: search-to-decision reductions, and\r\napproximate
    counting. We first show that, in strong contrast to the classical\r\nsetting where
    a poly-time Turing machine requires $\\Theta(n)$ queries to an NP\r\noracle to
    compute a witness to a given SAT formula, quantumly $\\Theta(\\log n)$\r\nqueries
    suffice. We then show this is tight in the black-box model - any\r\nquantum algorithm
    with \"NP-like\" query access to a formula requires\r\n$\\Omega(\\log n)$ queries
    to extract a solution with constant probability.\r\nMoving to approximate counting
    of SAT solutions, by exploiting a quantum link\r\nbetween search-to-decision reductions
    and approximate counting, we show that\r\nexisting classical approximate counting
    algorithms are likely optimal. First,\r\nwe give a lower bound in the \"NP-like\"
    black-box query setting: Approximate\r\ncounting requires $\\Omega(\\log n)$ queries,
    even on a quantum computer. We then\r\ngive a \"white-box\" lower bound (i.e.
    where the input formula is not hidden in\r\nthe oracle) - if there exists a randomized
    poly-time classical or quantum\r\nalgorithm for approximate counting making $o(log
    n)$ NP queries, then\r\n$\\text{BPP}^{\\text{NP}[o(n)]}$ contains a $\\text{P}^{\\text{NP}}$-complete\r\nproblem
    if the algorithm is classical and $\\text{FBQP}^{\\text{NP}[o(n)]}$\r\ncontains
    an $\\text{FP}^{\\text{NP}}$-complete problem if the algorithm is\r\nquantum."
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. BQP, meet NP: Search-to-decision reductions and approximate
    counting. In: <i>Proceedings of 51st EATCS International Colloquium on Automata,
    Languages and Programming (ICALP)</i>. Vol 297. ; 2024:1-19.'
  apa: 'Gharibian, S., &#38; Kamminga, J. (2024). BQP, meet NP: Search-to-decision
    reductions and approximate counting. <i>Proceedings of 51st EATCS International
    Colloquium on Automata, Languages and Programming (ICALP)</i>, <i>297</i>(70),
    1–19.'
  bibtex: '@inproceedings{Gharibian_Kamminga_2024, title={BQP, meet NP: Search-to-decision
    reductions and approximate counting}, volume={297}, number={70}, booktitle={Proceedings
    of 51st EATCS International Colloquium on Automata, Languages and Programming
    (ICALP)}, author={Gharibian, Sevag and Kamminga, Jonas}, year={2024}, pages={1–19}
    }'
  chicago: 'Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision
    Reductions and Approximate Counting.” In <i>Proceedings of 51st EATCS International
    Colloquium on Automata, Languages and Programming (ICALP)</i>, 297:1–19, 2024.'
  ieee: 'S. Gharibian and J. Kamminga, “BQP, meet NP: Search-to-decision reductions
    and approximate counting,” in <i>Proceedings of 51st EATCS International Colloquium
    on Automata, Languages and Programming (ICALP)</i>, 2024, vol. 297, no. 70, pp.
    1–19.'
  mla: 'Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision Reductions
    and Approximate Counting.” <i>Proceedings of 51st EATCS International Colloquium
    on Automata, Languages and Programming (ICALP)</i>, vol. 297, no. 70, 2024, pp.
    1–19.'
  short: 'S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium
    on Automata, Languages and Programming (ICALP), 2024, pp. 1–19.'
date_created: 2024-01-09T13:59:44Z
date_updated: 2026-05-15T08:41:59Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2401.03943'
intvolume: '       297'
issue: '70'
language:
- iso: eng
page: 1-19
publication: Proceedings of 51st EATCS International Colloquium on Automata, Languages
  and Programming (ICALP)
publication_status: published
status: public
title: 'BQP, meet NP: Search-to-decision reductions and approximate counting'
type: conference
user_id: '71541'
volume: 297
year: '2024'
...
---
_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'
...
---
_id: '48544'
abstract:
- lang: eng
  text: '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 the tree of NP. Two decades since the first definitions of quantum
    NP started rolling in, quantum complexity theorists face a stark reality: There''s
    QMA, QCMA, QMA1, QMA(2), StoqMA, and NQP. In this article aimed at a general theoretical
    computer science audience, I survey these various definitions of quantum NP, their
    strengths and weaknesses, and why most of them, for better or worse, actually
    appear to fit naturally into the complexity zoo.'
article_type: review
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
citation:
  ama: 'Gharibian S. Guest Column: The 7 faces of quantum NP. <i>ACM SIGACT News</i>.
    2024;54(4):54-91.'
  apa: 'Gharibian, S. (2024). Guest Column: The 7 faces of quantum NP. <i>ACM SIGACT
    News</i>, <i>54</i>(4), 54–91.'
  bibtex: '@article{Gharibian_2024, title={Guest Column: The 7 faces of quantum NP},
    volume={54}, number={4}, journal={ACM SIGACT News}, author={Gharibian, Sevag},
    year={2024}, pages={54–91} }'
  chicago: 'Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” <i>ACM SIGACT
    News</i> 54, no. 4 (2024): 54–91.'
  ieee: 'S. Gharibian, “Guest Column: The 7 faces of quantum NP,” <i>ACM SIGACT News</i>,
    vol. 54, no. 4, pp. 54–91, 2024.'
  mla: 'Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” <i>ACM SIGACT
    News</i>, vol. 54, no. 4, 2024, pp. 54–91.'
  short: S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
date_created: 2023-10-30T12:19:11Z
date_updated: 2026-05-15T08:42:54Z
department:
- _id: '7'
- _id: '623'
intvolume: '        54'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2310.18010
oa: '1'
page: 54-91
publication: ACM SIGACT News
publication_status: published
related_material:
  link:
  - relation: confirmation
    url: https://dl.acm.org/doi/abs/10.1145/3639528.3639535
status: public
title: 'Guest Column: The 7 faces of quantum NP'
type: journal_article
user_id: '71541'
volume: 54
year: '2024'
...
---
_id: '32407'
abstract:
- lang: eng
  text: "Estimating the ground state energy of a local Hamiltonian is a central\r\nproblem
    in quantum chemistry. In order to further investigate its complexity\r\nand the
    potential of quantum algorithms for quantum chemistry, Gharibian and Le\r\nGall
    (STOC 2022) recently introduced the guided local Hamiltonian problem\r\n(GLH),
    which is a variant of the local Hamiltonian problem where an\r\napproximation
    of a ground state is given as an additional input. Gharibian and\r\nLe Gall showed
    quantum advantage (more precisely, BQP-completeness) for GLH\r\nwith $6$-local
    Hamiltonians when the guiding vector has overlap\r\n(inverse-polynomially) close
    to 1/2 with a ground state. In this paper, we\r\noptimally improve both the locality
    and the overlap parameters: we show that\r\nthis quantum advantage (BQP-completeness)
    persists even with 2-local\r\nHamiltonians, and even when the guiding vector has
    overlap\r\n(inverse-polynomially) close to 1 with a ground state. Moreover, we
    show that\r\nthe quantum advantage also holds for 2-local physically motivated
    Hamiltonians\r\non a 2D square lattice. This makes a further step towards establishing\r\npractical
    quantum advantage in quantum chemistry."
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Ryu
  full_name: Hayakawa, Ryu
  last_name: Hayakawa
- first_name: François Le
  full_name: Gall, François Le
  last_name: Gall
- first_name: Tomoyuki
  full_name: Morimae, Tomoyuki
  last_name: Morimae
citation:
  ama: 'Gharibian S, Hayakawa R, Gall FL, Morimae T. Improved Hardness Results for
    the Guided Local Hamiltonian Problem. In: <i>Proceedings of the 50th EATCS International
    Colloquium on Automata, Languages and Programming (ICALP)</i>. Vol 261. ; 2023:1-19.
    doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.32">10.4230/LIPIcs.ICALP.2023.32</a>'
  apa: Gharibian, S., Hayakawa, R., Gall, F. L., &#38; Morimae, T. (2023). Improved
    Hardness Results for the Guided Local Hamiltonian Problem. <i>Proceedings of the
    50th EATCS International Colloquium on Automata, Languages and Programming (ICALP)</i>,
    <i>261</i>(32), 1–19. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.32">https://doi.org/10.4230/LIPIcs.ICALP.2023.32</a>
  bibtex: '@inproceedings{Gharibian_Hayakawa_Gall_Morimae_2023, title={Improved Hardness
    Results for the Guided Local Hamiltonian Problem}, volume={261}, DOI={<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.32">10.4230/LIPIcs.ICALP.2023.32</a>},
    number={32}, booktitle={Proceedings of the 50th EATCS International Colloquium
    on Automata, Languages and Programming (ICALP)}, author={Gharibian, Sevag and
    Hayakawa, Ryu and Gall, François Le and Morimae, Tomoyuki}, year={2023}, pages={1–19}
    }'
  chicago: Gharibian, Sevag, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae.
    “Improved Hardness Results for the Guided Local Hamiltonian Problem.” In <i>Proceedings
    of the 50th EATCS International Colloquium on Automata, Languages and Programming
    (ICALP)</i>, 261:1–19, 2023. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.32">https://doi.org/10.4230/LIPIcs.ICALP.2023.32</a>.
  ieee: 'S. Gharibian, R. Hayakawa, F. L. Gall, and T. Morimae, “Improved Hardness
    Results for the Guided Local Hamiltonian Problem,” in <i>Proceedings of the 50th
    EATCS International Colloquium on Automata, Languages and Programming (ICALP)</i>,
    2023, vol. 261, no. 32, pp. 1–19, doi: <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.32">10.4230/LIPIcs.ICALP.2023.32</a>.'
  mla: Gharibian, Sevag, et al. “Improved Hardness Results for the Guided Local Hamiltonian
    Problem.” <i>Proceedings of the 50th EATCS International Colloquium on Automata,
    Languages and Programming (ICALP)</i>, vol. 261, no. 32, 2023, pp. 1–19, doi:<a
    href="https://doi.org/10.4230/LIPIcs.ICALP.2023.32">10.4230/LIPIcs.ICALP.2023.32</a>.
  short: 'S. Gharibian, R. Hayakawa, F.L. Gall, T. Morimae, in: Proceedings of the
    50th EATCS International Colloquium on Automata, Languages and Programming (ICALP),
    2023, pp. 1–19.'
date_created: 2022-07-22T12:32:40Z
date_updated: 2023-10-09T04:17:10Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.ICALP.2023.32
external_id:
  arxiv:
  - '2207.10250'
intvolume: '       261'
issue: '32'
language:
- iso: eng
page: 1-19
publication: Proceedings of the 50th EATCS International Colloquium on Automata, Languages
  and Programming (ICALP)
publication_status: published
status: public
title: Improved Hardness Results for the Guided Local Hamiltonian Problem
type: conference
user_id: '71541'
volume: 261
year: '2023'
...
---
_id: '31872'
abstract:
- lang: eng
  text: "Savitch's theorem states that NPSPACE computations can be simulated in\r\nPSPACE.
    We initiate the study of a quantum analogue of NPSPACE, denoted\r\nStreaming-QCMASPACE
    (SQCMASPACE), where an exponentially long classical proof\r\nis streamed to a
    poly-space quantum verifier. Besides two main results, we also\r\nshow that a
    quantum analogue of Savitch's theorem is unlikely to hold, as\r\nSQCMASPACE=NEXP.
    For completeness, we introduce Streaming-QMASPACE (SQMASPACE)\r\nwith an exponentially
    long streamed quantum proof, and show SQMASPACE=QMA_EXP\r\n(quantum analogue of
    NEXP). Our first main result shows, in contrast to the\r\nclassical setting, the
    solution space of a quantum constraint satisfaction\r\nproblem (i.e. a local Hamiltonian)
    is always connected when exponentially long\r\nproofs are permitted. For this,
    we show how to simulate any Lipschitz\r\ncontinuous path on the unit hypersphere
    via a sequence of local unitary gates,\r\nat the expense of blowing up the circuit
    size. This shows quantum\r\nerror-correcting codes can be unable to detect one
    codeword erroneously\r\nevolving to another if the evolution happens sufficiently
    slowly, and answers\r\nan open question of [Gharibian, Sikora, ICALP 2015] regarding
    the Ground State\r\nConnectivity problem. Our second main result is that any SQCMASPACE
    computation\r\ncan be embedded into \"unentanglement\", i.e. into a quantum constraint\r\nsatisfaction
    problem with unentangled provers. Formally, we show how to embed\r\nSQCMASPACE
    into the Sparse Separable Hamiltonian problem of [Chailloux,\r\nSattath, CCC 2012]
    (QMA(2)-complete for 1/poly promise gap), at the expense of\r\nscaling the promise
    gap with the streamed proof size. As a corollary, we obtain\r\nthe first systematic
    construction for obtaining QMA(2)-type upper bounds on\r\narbitrary multi-prover
    interactive proof systems, where the QMA(2) promise gap\r\nscales exponentially
    with the number of bits of communication in the\r\ninteractive proof."
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Dorian
  full_name: Rudolph, Dorian
  last_name: Rudolph
citation:
  ama: 'Gharibian S, Rudolph D. Quantum space, ground space traversal, and how to
    embed multi-prover  interactive proofs into unentanglement. In: <i>14th Innovations
    in Theoretical Computer Science (ITCS)</i>. Vol 251. ; 2023:53:1-53:23. doi:<a
    href="https://doi.org/10.4230/LIPIcs.ITCS.2023.53">10.4230/LIPIcs.ITCS.2023.53</a>'
  apa: Gharibian, S., &#38; Rudolph, D. (2023). Quantum space, ground space traversal,
    and how to embed multi-prover  interactive proofs into unentanglement. <i>14th
    Innovations in Theoretical Computer Science (ITCS)</i>, <i>251</i>, 53:1-53:23.
    <a href="https://doi.org/10.4230/LIPIcs.ITCS.2023.53">https://doi.org/10.4230/LIPIcs.ITCS.2023.53</a>
  bibtex: '@inproceedings{Gharibian_Rudolph_2023, title={Quantum space, ground space
    traversal, and how to embed multi-prover  interactive proofs into unentanglement},
    volume={251}, DOI={<a href="https://doi.org/10.4230/LIPIcs.ITCS.2023.53">10.4230/LIPIcs.ITCS.2023.53</a>},
    booktitle={14th Innovations in Theoretical Computer Science (ITCS)}, author={Gharibian,
    Sevag and Rudolph, Dorian}, year={2023}, pages={53:1-53:23} }'
  chicago: Gharibian, Sevag, and Dorian Rudolph. “Quantum Space, Ground Space Traversal,
    and How to Embed Multi-Prover  Interactive Proofs into Unentanglement.” In <i>14th
    Innovations in Theoretical Computer Science (ITCS)</i>, 251:53:1-53:23, 2023.
    <a href="https://doi.org/10.4230/LIPIcs.ITCS.2023.53">https://doi.org/10.4230/LIPIcs.ITCS.2023.53</a>.
  ieee: 'S. Gharibian and D. Rudolph, “Quantum space, ground space traversal, and
    how to embed multi-prover  interactive proofs into unentanglement,” in <i>14th
    Innovations in Theoretical Computer Science (ITCS)</i>, 2023, vol. 251, p. 53:1-53:23,
    doi: <a href="https://doi.org/10.4230/LIPIcs.ITCS.2023.53">10.4230/LIPIcs.ITCS.2023.53</a>.'
  mla: Gharibian, Sevag, and Dorian Rudolph. “Quantum Space, Ground Space Traversal,
    and How to Embed Multi-Prover  Interactive Proofs into Unentanglement.” <i>14th
    Innovations in Theoretical Computer Science (ITCS)</i>, vol. 251, 2023, p. 53:1-53:23,
    doi:<a href="https://doi.org/10.4230/LIPIcs.ITCS.2023.53">10.4230/LIPIcs.ITCS.2023.53</a>.
  short: 'S. Gharibian, D. Rudolph, in: 14th Innovations in Theoretical Computer Science
    (ITCS), 2023, p. 53:1-53:23.'
date_created: 2022-06-13T14:40:46Z
date_updated: 2023-02-28T11:06:55Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.ITCS.2023.53
external_id:
  arxiv:
  - '2206.05243'
intvolume: '       251'
language:
- iso: eng
page: 53:1-53:23
publication: 14th Innovations in Theoretical Computer Science (ITCS)
publication_status: published
status: public
title: Quantum space, ground space traversal, and how to embed multi-prover  interactive
  proofs into unentanglement
type: conference
user_id: '71541'
volume: 251
year: '2023'
...
---
_id: '20841'
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: James
  full_name: Watson, James
  last_name: Watson
- first_name: Johannes
  full_name: Bausch, Johannes
  last_name: Bausch
citation:
  ama: 'Gharibian S, Watson J, Bausch J. The Complexity of Translationally Invariant
    Problems beyond Ground State Energies. In: <i>Proceedings of the 40th International
    Symposium on Theoretical Aspects of Computer Science (STACS)</i>. Vol 254. ; 2023:54:1-54:21.
    doi:<a href="https://doi.org/10.4230/LIPIcs.STACS.2023.54">https://doi.org/10.4230/LIPIcs.STACS.2023.54</a>'
  apa: Gharibian, S., Watson, J., &#38; Bausch, J. (2023). The Complexity of Translationally
    Invariant Problems beyond Ground State Energies. <i>Proceedings of the 40th International
    Symposium on Theoretical Aspects of Computer Science (STACS)</i>, <i>254</i>,
    54:1-54:21. <a href="https://doi.org/10.4230/LIPIcs.STACS.2023.54">https://doi.org/10.4230/LIPIcs.STACS.2023.54</a>
  bibtex: '@inproceedings{Gharibian_Watson_Bausch_2023, title={The Complexity of Translationally
    Invariant Problems beyond Ground State Energies}, volume={254}, DOI={<a href="https://doi.org/10.4230/LIPIcs.STACS.2023.54">https://doi.org/10.4230/LIPIcs.STACS.2023.54</a>},
    booktitle={Proceedings of the 40th International Symposium on Theoretical Aspects
    of Computer Science (STACS)}, author={Gharibian, Sevag and Watson, James and Bausch,
    Johannes}, year={2023}, pages={54:1-54:21} }'
  chicago: Gharibian, Sevag, James Watson, and Johannes Bausch. “The Complexity of
    Translationally Invariant Problems beyond Ground State Energies.” In <i>Proceedings
    of the 40th International Symposium on Theoretical Aspects of Computer Science
    (STACS)</i>, 254:54:1-54:21, 2023. <a href="https://doi.org/10.4230/LIPIcs.STACS.2023.54">https://doi.org/10.4230/LIPIcs.STACS.2023.54</a>.
  ieee: 'S. Gharibian, J. Watson, and J. Bausch, “The Complexity of Translationally
    Invariant Problems beyond Ground State Energies,” in <i>Proceedings of the 40th
    International Symposium on Theoretical Aspects of Computer Science (STACS)</i>,
    2023, vol. 254, p. 54:1-54:21, doi: <a href="https://doi.org/10.4230/LIPIcs.STACS.2023.54">https://doi.org/10.4230/LIPIcs.STACS.2023.54</a>.'
  mla: Gharibian, Sevag, et al. “The Complexity of Translationally Invariant Problems
    beyond Ground State Energies.” <i>Proceedings of the 40th International Symposium
    on Theoretical Aspects of Computer Science (STACS)</i>, vol. 254, 2023, p. 54:1-54:21,
    doi:<a href="https://doi.org/10.4230/LIPIcs.STACS.2023.54">https://doi.org/10.4230/LIPIcs.STACS.2023.54</a>.
  short: 'S. Gharibian, J. Watson, J. Bausch, in: Proceedings of the 40th International
    Symposium on Theoretical Aspects of Computer Science (STACS), 2023, p. 54:1-54:21.'
date_created: 2020-12-24T14:15:09Z
date_updated: 2023-05-04T17:51:23Z
department:
- _id: '623'
- _id: '7'
doi: https://doi.org/10.4230/LIPIcs.STACS.2023.54
external_id:
  arxiv:
  - '2012.12717'
intvolume: '       254'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2012.12717
oa: '1'
page: 54:1-54:21
publication: Proceedings of the 40th International Symposium on Theoretical Aspects
  of Computer Science (STACS)
publication_status: published
status: public
title: The Complexity of Translationally Invariant Problems beyond Ground State Energies
type: conference
user_id: '71541'
volume: 254
year: '2023'
...