---
_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: 17th Innovations in Theoretical
Computer Science Conference (ITCS 2026). Vol 362. ; 2026:7:1-7:24.'
apa: 'Aldi, M., Gharibian, S., & Rudolph, D. (2026). An unholy trinity: TFNP,
polynomial systems, and the quantum satisfiability problem. 17th Innovations
in Theoretical Computer Science Conference (ITCS 2026), 362, 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 17th
Innovations in Theoretical Computer Science Conference (ITCS 2026), 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 17th Innovations in Theoretical
Computer Science Conference (ITCS 2026), 2026, vol. 362, p. 7:1-7:24.'
mla: 'Aldi, Marco, et al. “An Unholy Trinity: TFNP, Polynomial Systems, and the
Quantum Satisfiability Problem.” 17th Innovations in Theoretical Computer
Science Conference (ITCS 2026), 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-01-23T07:53:03Z
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: '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: International Colloquium on Automata, Languages,
and Programming (ICALP). ; 2026.'
apa: Karaiskos, G., Rudolph, D., Meyer, J. J., Eisert, J., & Gharibian, S. (2026).
How hard is it to verify a classical shadow? International Colloquium on Automata,
Languages, and Programming (ICALP).
bibtex: '@inproceedings{Karaiskos_Rudolph_Meyer_Eisert_Gharibian_2026, title={How
hard is it to verify a classical shadow?}, 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} }'
chicago: Karaiskos, Georgios, Dorian Rudolph, Johannes Jakob Meyer, Jens Eisert,
and Sevag Gharibian. “How Hard Is It to Verify a Classical Shadow?” In International
Colloquium on Automata, Languages, and Programming (ICALP), 2026.
ieee: G. Karaiskos, D. Rudolph, J. J. Meyer, J. Eisert, and S. Gharibian, “How hard
is it to verify a classical shadow?,” 2026.
mla: Karaiskos, Georgios, et al. “How Hard Is It to Verify a Classical Shadow?”
International Colloquium on Automata, Languages, and Programming (ICALP),
2026.
short: 'G. Karaiskos, D. Rudolph, J.J. Meyer, J. Eisert, S. Gharibian, in: International
Colloquium on Automata, Languages, and Programming (ICALP), 2026.'
date_created: 2025-10-10T13:45:07Z
date_updated: 2026-04-30T14:04:33Z
external_id:
arxiv:
- '2510.08515'
language:
- iso: eng
publication: International Colloquium on Automata, Languages, and Programming (ICALP)
status: public
title: How hard is it to verify a classical shadow?
type: conference
user_id: '71541'
year: '2026'
...
---
_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.
arXiv:250617066. Published online 2025.
apa: Kremer, S.-L., Rudolph, D., & Gharibian, S. (2025). Quantum k-SAT Related
Hypergraph Problems. In arXiv:2506.17066.
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.” ArXiv:2506.17066, 2025.
ieee: S.-L. Kremer, D. Rudolph, and S. Gharibian, “Quantum k-SAT Related Hypergraph
Problems,” arXiv:2506.17066. 2025.
mla: Kremer, Simon-Luca, et al. “Quantum K-SAT Related Hypergraph Problems.” ArXiv:2506.17066,
2025.
short: S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
date_created: 2025-06-27T06:56:35Z
date_updated: 2025-06-27T06:57:03Z
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: '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:
16th Innovations in Theoretical Computer Science (ITCS). Vol 325. ; 2025:1-24.
doi:10.4230/LIPIcs.ITCS.2025.85'
apa: Rudolph, D., Gharibian, S., & Nagaj, D. (2025). Quantum 2-SAT on low dimensional
systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation.
16th Innovations in Theoretical Computer Science (ITCS), 325(85),
1–24. https://doi.org/10.4230/LIPIcs.ITCS.2025.85
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={10.4230/LIPIcs.ITCS.2025.85},
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 16th Innovations in Theoretical Computer Science (ITCS),
325:1–24, 2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.85.
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 16th Innovations in Theoretical Computer Science (ITCS), 2025, vol.
325, no. 85, pp. 1–24, doi: 10.4230/LIPIcs.ITCS.2025.85.'
mla: Rudolph, Dorian, et al. “Quantum 2-SAT on Low Dimensional Systems Is $\mathsf{QMA}_1$-Complete:
Direct Embeddings and Black-Box Simulation.” 16th Innovations in Theoretical
Computer Science (ITCS), vol. 325, no. 85, 2025, pp. 1–24, doi:10.4230/LIPIcs.ITCS.2025.85.
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-04-30T14:10:03Z
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: '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. arXiv:251008545. Published online 2025.
apa: Chabaud, U., Gharibian, S., Mehraban, S., Motamedi, A., Naeij, H. R., Rudolph,
D., & Sambrani, D. (2025). Energy, Bosons and Computational Complexity. In
arXiv:2510.08545.
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.” ArXiv:2510.08545, 2025.
ieee: U. Chabaud et al., “Energy, Bosons and Computational Complexity,” arXiv:2510.08545.
2025.
mla: Chabaud, Ulysse, et al. “Energy, Bosons and Computational Complexity.” ArXiv:2510.08545,
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-04-30T14:08:24Z
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: '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: Proceedings of 49th International
Symposium on Mathematical Foundations of Computer Science (MFCS). Vol 306.
; 2024:7-17. doi:10.4230/LIPIcs.MFCS.2024.7'
apa: 'Agarwal, A., Gharibian, S., Koppula, V., & Rudolph, D. (2024). Quantum
Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. Proceedings
of 49th International Symposium on Mathematical Foundations of Computer Science
(MFCS), 306(7), 7–17. https://doi.org/10.4230/LIPIcs.MFCS.2024.7'
bibtex: '@inproceedings{Agarwal_Gharibian_Koppula_Rudolph_2024, title={Quantum Polynomial
Hierarchies: Karp-Lipton, error reduction, and lower bounds}, volume={306}, DOI={10.4230/LIPIcs.MFCS.2024.7},
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 Proceedings of 49th International Symposium on Mathematical Foundations
of Computer Science (MFCS), 306:7–17, 2024. https://doi.org/10.4230/LIPIcs.MFCS.2024.7.'
ieee: 'A. Agarwal, S. Gharibian, V. Koppula, and D. Rudolph, “Quantum Polynomial
Hierarchies: Karp-Lipton, error reduction, and lower bounds,” in Proceedings
of 49th International Symposium on Mathematical Foundations of Computer Science
(MFCS), 2024, vol. 306, no. 7, pp. 7–17, doi: 10.4230/LIPIcs.MFCS.2024.7.'
mla: 'Agarwal, Avantika, et al. “Quantum Polynomial Hierarchies: Karp-Lipton, Error
Reduction, and Lower Bounds.” Proceedings of 49th International Symposium
on Mathematical Foundations of Computer Science (MFCS), vol. 306, no. 7, 2024,
pp. 7–17, doi:10.4230/LIPIcs.MFCS.2024.7.'
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-04-30T14:10:19Z
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: '27160'
abstract:
- lang: eng
text: "We study the complexity of problems solvable in deterministic polynomial
time\r\nwith access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$\r\nand
$P^{QMA}$, respectively. The former allows one to classify problems more\r\nfinely
than the Polynomial-Time Hierarchy (PH), whereas the latter\r\ncharacterizes physically
motivated problems such as Approximate Simulation\r\n(APX-SIM) [Ambainis, CCC
2014]. In this area, a central role has been played by\r\nthe classes $P^{NP[\\log]}$
and $P^{QMA[\\log]}$, defined identically to $P^{NP}$\r\nand $P^{QMA}$, except
that only logarithmically many oracle queries are\r\nallowed. Here, [Gottlob,
FOCS 1993] showed that if the adaptive queries made by\r\na $P^{NP}$ machine have
a \"query graph\" which is a tree, then this computation\r\ncan be simulated in
$P^{NP[\\log]}$.\r\n In this work, we first show that for any verification class\r\n$C\\in\\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\\exp}\\}$,
any $P^C$ machine with a query\r\ngraph of \"separator number\" $s$ can be simulated
using deterministic time\r\n$\\exp(s\\log n)$ and $s\\log n$ queries to a $C$-oracle.
When $s\\in O(1)$ (which\r\nincludes the case of $O(1)$-treewidth, and thus also
of trees), this gives an\r\nupper bound of $P^{C[\\log]}$, and when $s\\in O(\\log^k(n))$,
this yields bound\r\n$QP^{C[\\log^{k+1}]}$ (QP meaning quasi-polynomial time).
We next show how to\r\ncombine Gottlob's \"admissible-weighting function\" framework
with the\r\n\"flag-qubit\" framework of [Watson, Bausch, Gharibian, 2020], obtaining
a\r\nunified approach for embedding $P^C$ computations directly into APX-SIM\r\ninstances
in a black-box fashion. Finally, we formalize a simple no-go\r\nstatement about
polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear\r\npolynomial $p$
specified via an arithmetic circuit, if one can \"weakly\r\ncompress\" $p$ so
that its optimal value requires $m$ bits to represent, then\r\n$P^{NP}$ can be
decided with only $m$ queries to an NP-oracle."
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
id: '57863'
last_name: Rudolph
citation:
ama: 'Gharibian S, Rudolph D. On polynomially many queries to NP or QMA oracles.
In: 13th Innovations in Theoretical Computer Science (ITCS 2022). Vol 215.
; 2022:1-27. doi:10.4230/LIPIcs.ITCS.2022.75'
apa: Gharibian, S., & Rudolph, D. (2022). On polynomially many queries to NP
or QMA oracles. 13th Innovations in Theoretical Computer Science (ITCS 2022),
215(75), 1–27. https://doi.org/10.4230/LIPIcs.ITCS.2022.75
bibtex: '@inproceedings{Gharibian_Rudolph_2022, title={On polynomially many queries
to NP or QMA oracles}, volume={215}, DOI={10.4230/LIPIcs.ITCS.2022.75},
number={75}, booktitle={13th Innovations in Theoretical Computer Science (ITCS
2022)}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2022}, pages={1–27}
}'
chicago: Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to
NP or QMA Oracles.” In 13th Innovations in Theoretical Computer Science (ITCS
2022), 215:1–27, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.75.
ieee: 'S. Gharibian and D. Rudolph, “On polynomially many queries to NP or QMA oracles,”
in 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022,
vol. 215, no. 75, pp. 1–27, doi: 10.4230/LIPIcs.ITCS.2022.75.'
mla: Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or
QMA Oracles.” 13th Innovations in Theoretical Computer Science (ITCS 2022),
vol. 215, no. 75, 2022, pp. 1–27, doi:10.4230/LIPIcs.ITCS.2022.75.
short: 'S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science
(ITCS 2022), 2022, pp. 1–27.'
date_created: 2021-11-05T08:08:29Z
date_updated: 2026-04-30T14:11:00Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.ITCS.2022.75
intvolume: ' 215'
issue: '75'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15671
oa: '1'
page: 1-27
publication: 13th Innovations in Theoretical Computer Science (ITCS 2022)
status: public
title: On polynomially many queries to NP or QMA oracles
type: conference
user_id: '71541'
volume: 215
year: '2022'
...