@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}},
}

@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)}},
  title        = {{{How hard is it to verify a classical shadow?}}},
  year         = {{2026}},
}

@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{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}},
}

@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}},
}