@inproceedings{57866,
  abstract     = {{The theory of Total Function NP (TFNP) and its subclasses says that, even if
one is promised an efficiently verifiable proof exists for a problem, finding
this proof can be intractable. Despite the success of the theory at showing
intractability of problems such as computing Brouwer fixed points and Nash
equilibria, subclasses of TFNP remain arguably few and far between. In this
work, we define two new subclasses of TFNP borne of the study of complex
polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental
Theorem of Algebra (SFTA). The first of these is based on B\'ezout's theorem
from algebraic geometry, marking the first TFNP subclass based on an algebraic
geometric principle. At the heart of our study is the computational problem
known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR),
first studied by [Laumann, L\"auchli, Moessner, Scardicchio, and Sondhi 2010].
Among other results, we show that QSAT with SDR is MHS-complete, thus giving
not only the first link between quantum complexity theory and TFNP, but also
the first TFNP problem whose classical variant (SAT with SDR) is easy but whose
quantum variant is hard. We also show how to embed the roots of a sparse,
high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is
contained in a zero-error version of MHS. We conjecture this construction also
works in the low-error setting, which would imply SFTA is contained in MHS.}},
  author       = {{Aldi, Marco and Gharibian, Sevag and Rudolph, Dorian}},
  booktitle    = {{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)}},
  pages        = {{7:1--7:24}},
  title        = {{{An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem}}},
  volume       = {{362}},
  year         = {{2026}},
}

@unpublished{67088,
  abstract     = {{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       = {{Gharibian, Sevag and Hecht, Carsten and Rudolph, Dorian}},
  booktitle    = {{arXiv:2609.09033}},
  title        = {{{Semidefinite extension complexity of the separable set, with applications to approximate disentanglers}}},
  year         = {{2026}},
}

@unpublished{67292,
  abstract     = {{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       = {{Karaiskos, Georgios and Raza, Asad and Rudolph, Dorian and Koh, Dax Enshan and Gharibian, Sevag}},
  booktitle    = {{arXiv:2609.40107}},
  title        = {{{Verification Complexity and Extension of Classical Shadows}}},
  year         = {{2026}},
}

@unpublished{67291,
  author       = {{Rudolph, Dorian and Motamedi, Arsalan and Sambrani, Dhruva and Reza Naeij, Hamid and Chabaud, Ulysse and Gharibian, Sevag and Mehraban, Saeed}},
  title        = {{{A physical and universal model of bosonic computations with Solovay-Kitaev theorem}}},
  year         = {{2026}},
}

@inproceedings{61777,
  abstract     = {{Classical shadows are succinct classical representations of quantum states
which allow one to encode a set of properties P of a quantum state rho, while
only requiring measurements on logarithmically many copies of rho in the size
of P. In this work, we initiate the study of verification of classical shadows,
denoted classical shadow validity (CSV), from the perspective of computational
complexity, which asks: Given a classical shadow S, how hard is it to verify
that S predicts the measurement statistics of a quantum state? We show that
even for the elegantly simple classical shadow protocol of [Huang, Kueng,
Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is
QMA-complete. This hardness continues to hold for the high-dimensional
extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. Among other
results, we also show that CSV for exponentially many observables is complete
for a quantum generalization of the second level of the polynomial hierarchy,
yielding the first natural complete problem for such a class.}},
  author       = {{Karaiskos, Georgios and Rudolph, Dorian and Meyer, Johannes Jakob and Eisert, Jens and Gharibian, Sevag}},
  booktitle    = {{International Colloquium on Automata, Languages, and Programming (ICALP)}},
  number       = {{123}},
  pages        = {{1--23}},
  title        = {{{How hard is it to verify a classical shadow?}}},
  volume       = {{374}},
  year         = {{2026}},
}

@inproceedings{50272,
  abstract     = {{Despite the fundamental role the Quantum Satisfiability (QSAT) problem has
played in quantum complexity theory, a central question remains open: At which
local dimension does the complexity of QSAT transition from "easy" to "hard"?
Here, we study QSAT with each constraint acting on a $k$-dimensional and
$l$-dimensional qudit pair, denoted $(k,l)$-QSAT. Our first main result shows
that, surprisingly, QSAT on qubits can remain $\mathsf{QMA}_1$-hard, in that
$(2,5)$-QSAT is $\mathsf{QMA}_1$-complete. In contrast, $2$-SAT on qubits is
well-known to be poly-time solvable [Bravyi, 2006]. Our second main result
proves that $(3,d)$-QSAT on the 1D line with $d\in O(1)$ is also
$\mathsf{QMA}_1$-hard. Finally, we initiate the study of 1D $(2,d)$-QSAT by
giving a frustration-free 1D Hamiltonian with a unique, entangled ground state.
  Our first result uses a direct embedding, combining a novel clock
construction with the 2D circuit-to-Hamiltonian construction of [Gosset, Nagaj,
2013]. Of note is a new simplified and analytic proof for the latter (as
opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled
Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection
Lemma", allowing us to break low energy analyses into small patches of
projectors, and to improve the soundness analysis of [GN13] from
$\Omega(1/T^6)$ to $\Omega(1/T^2)$, for $T$ the number of gates. Our second
result goes via black-box reduction: Given an arbitrary 1D Hamiltonian $H$ on
$d'$-dimensional qudits, we show how to embed it into an effective null-space
of a 1D $(3,d)$-QSAT instance, for $d\in O(1)$. Our approach may be viewed as a
weaker notion of "simulation" (\`a la [Bravyi, Hastings 2017], [Cubitt,
Montanaro, Piddock 2018]). As far as we are aware, this gives the first
"black-box simulation"-based $\mathsf{QMA}_1$-hardness result, i.e. for
frustration-free Hamiltonians.}},
  author       = {{Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel}},
  booktitle    = {{16th Innovations in Theoretical Computer Science (ITCS)}},
  number       = {{85}},
  pages        = {{1--24}},
  title        = {{{Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete:  Direct embeddings and black-box simulation}}},
  doi          = {{10.4230/LIPIcs.ITCS.2025.85}},
  volume       = {{325}},
  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}},
}

@inproceedings{50273,
  abstract     = {{The Polynomial-Time Hierarchy ($\mathsf{PH}$) is a staple of classical
complexity theory, with applications spanning randomized computation to circuit
lower bounds to ''quantum advantage'' analyses for near-term quantum computers.
Quantumly, however, despite the fact that at least \emph{four} definitions of
quantum $\mathsf{PH}$ exist, it has been challenging to prove analogues for
these of even basic facts from $\mathsf{PH}$. This work studies three
quantum-verifier based generalizations of $\mathsf{PH}$, two of which are from
[Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings
($\mathsf{QCPH}$) and quantum mixed states ($\mathsf{QPH}$) as proofs, and one
of which is new to this work, utilizing quantum pure states
($\mathsf{pureQPH}$) as proofs. We first resolve several open problems from
[GSSSY22], including a collapse theorem and a Karp-Lipton theorem for
$\mathsf{QCPH}$. Then, for our new class $\mathsf{pureQPH}$, we show one-sided
error reduction for $\mathsf{pureQPH}$, as well as the first bounds relating
these quantum variants of $\mathsf{PH}$, namely $\mathsf{QCPH}\subseteq
\mathsf{pureQPH} \subseteq \mathsf{EXP}^{\mathsf{PP}}$.}},
  author       = {{Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian}},
  booktitle    = {{Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)}},
  number       = {{7}},
  pages        = {{7--17}},
  title        = {{{Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds}}},
  doi          = {{10.4230/LIPIcs.MFCS.2024.7}},
  volume       = {{306}},
  year         = {{2024}},
}

@inproceedings{27160,
  abstract     = {{We study the complexity of problems solvable in deterministic polynomial time
with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$
and $P^{QMA}$, respectively. The former allows one to classify problems more
finely than the Polynomial-Time Hierarchy (PH), whereas the latter
characterizes physically motivated problems such as Approximate Simulation
(APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by
the classes $P^{NP[\log]}$ and $P^{QMA[\log]}$, defined identically to $P^{NP}$
and $P^{QMA}$, except that only logarithmically many oracle queries are
allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by
a $P^{NP}$ machine have a "query graph" which is a tree, then this computation
can be simulated in $P^{NP[\log]}$.
  In this work, we first show that for any verification class
$C\in\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\exp}\}$, any $P^C$ machine with a query
graph of "separator number" $s$ can be simulated using deterministic time
$\exp(s\log n)$ and $s\log n$ queries to a $C$-oracle. When $s\in O(1)$ (which
includes the case of $O(1)$-treewidth, and thus also of trees), this gives an
upper bound of $P^{C[\log]}$, and when $s\in O(\log^k(n))$, this yields bound
$QP^{C[\log^{k+1}]}$ (QP meaning quasi-polynomial time). We next show how to
combine Gottlob's "admissible-weighting function" framework with the
"flag-qubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a
unified approach for embedding $P^C$ computations directly into APX-SIM
instances in a black-box fashion. Finally, we formalize a simple no-go
statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear
polynomial $p$ specified via an arithmetic circuit, if one can "weakly
compress" $p$ so that its optimal value requires $m$ bits to represent, then
$P^{NP}$ can be decided with only $m$ queries to an NP-oracle.}},
  author       = {{Gharibian, Sevag and Rudolph, Dorian}},
  booktitle    = {{13th Innovations in Theoretical Computer Science (ITCS 2022)}},
  number       = {{75}},
  pages        = {{1--27}},
  title        = {{{On polynomially many queries to NP or QMA oracles}}},
  doi          = {{10.4230/LIPIcs.ITCS.2022.75}},
  volume       = {{215}},
  year         = {{2022}},
}