[{"abstract":[{"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.","lang":"eng"}],"publication":"17th Innovations in Theoretical Computer Science Conference (ITCS 2026)","citation":{"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} }","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.","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.","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.","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."},"type":"conference","department":[{"_id":"7"},{"_id":"623"}],"external_id":{"arxiv":["2412.19623"]},"date_created":"2024-12-30T13:55:27Z","publication_status":"published","date_updated":"2026-05-15T08:40:28Z","intvolume":"       362","year":"2026","status":"public","title":"An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem","author":[{"last_name":"Aldi","first_name":"Marco","full_name":"Aldi, Marco"},{"full_name":"Gharibian, Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","first_name":"Sevag","id":"71541"},{"full_name":"Rudolph, Dorian","last_name":"Rudolph","first_name":"Dorian","id":"57863"}],"user_id":"71541","volume":362,"page":"7:1-7:24","_id":"57866","language":[{"iso":"eng"}]},{"abstract":[{"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.","lang":"eng"}],"citation":{"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} }","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.","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.","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.","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."},"issue":"123","publication":"International Colloquium on Automata, Languages, and Programming (ICALP)","department":[{"_id":"7"},{"_id":"623"}],"type":"conference","date_created":"2025-10-10T13:45:07Z","external_id":{"arxiv":["2510.08515"]},"intvolume":"       374","date_updated":"2026-07-01T15:30:26Z","publication_status":"published","author":[{"full_name":"Karaiskos, Georgios","first_name":"Georgios","last_name":"Karaiskos"},{"full_name":"Rudolph, Dorian","last_name":"Rudolph","first_name":"Dorian","id":"57863"},{"full_name":"Meyer, Johannes Jakob","last_name":"Meyer","first_name":"Johannes Jakob"},{"full_name":"Eisert, Jens","last_name":"Eisert","first_name":"Jens"},{"full_name":"Gharibian, Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","first_name":"Sevag","id":"71541"}],"title":"How hard is it to verify a classical shadow?","status":"public","year":"2026","volume":374,"user_id":"71541","language":[{"iso":"eng"}],"_id":"61777","page":"1-23"},{"user_id":"71541","volume":325,"page":"1-24","_id":"50272","status":"public","external_id":{"arxiv":["2401.02368"]},"citation":{"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>.","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} }","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>","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>.","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>","short":"D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 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>."},"doi":"10.4230/LIPIcs.ITCS.2025.85","language":[{"iso":"eng"}],"publication_status":"published","date_updated":"2026-05-15T08:38:31Z","intvolume":"       325","title":"Quantum 2-SAT on low dimensional systems is $\\mathsf{QMA}_1$-complete:  Direct embeddings and black-box simulation","year":"2025","author":[{"full_name":"Rudolph, Dorian","last_name":"Rudolph","first_name":"Dorian","id":"57863"},{"last_name":"Gharibian","orcid":"0000-0002-9992-3379","first_name":"Sevag","full_name":"Gharibian, Sevag","id":"71541"},{"last_name":"Nagaj","first_name":"Daniel","full_name":"Nagaj, Daniel"}],"type":"conference","department":[{"_id":"7"},{"_id":"623"}],"date_created":"2024-01-07T20:09:13Z","abstract":[{"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.","lang":"eng"}],"issue":"85","publication":"16th Innovations in Theoretical Computer Science (ITCS)"},{"user_id":"71541","language":[{"iso":"eng"}],"_id":"61776","date_updated":"2026-05-15T08:39:50Z","status":"public","year":"2025","title":"Energy, Bosons and Computational Complexity","author":[{"first_name":"Ulysse","last_name":"Chabaud","full_name":"Chabaud, Ulysse"},{"full_name":"Gharibian, Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","first_name":"Sevag","id":"71541"},{"full_name":"Mehraban, Saeed","first_name":"Saeed","last_name":"Mehraban"},{"full_name":"Motamedi, Arsalan","first_name":"Arsalan","last_name":"Motamedi"},{"full_name":"Naeij, Hamid Reza","last_name":"Naeij","first_name":"Hamid Reza"},{"id":"57863","first_name":"Dorian","last_name":"Rudolph","full_name":"Rudolph, Dorian"},{"full_name":"Sambrani, Dhruva","last_name":"Sambrani","first_name":"Dhruva"}],"type":"preprint","department":[{"_id":"7"},{"_id":"623"}],"external_id":{"arxiv":["2510.08545"]},"date_created":"2025-10-10T13:44:52Z","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."}],"publication":"arXiv:2510.08545","citation":{"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.","short":"U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H.R. Naeij, D. Rudolph, D. Sambrani, ArXiv:2510.08545 (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>.","ieee":"U. Chabaud <i>et al.</i>, “Energy, Bosons and Computational Complexity,” <i>arXiv:2510.08545</i>. 2025.","ama":"Chabaud U, Gharibian S, Mehraban S, et al. Energy, Bosons and Computational Complexity. <i>arXiv:251008545</i>. Published online 2025.","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} }","mla":"Chabaud, Ulysse, et al. “Energy, Bosons and Computational Complexity.” <i>ArXiv:2510.08545</i>, 2025."}},{"citation":{"short":"S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).","chicago":"Kremer, Simon-Luca, Dorian Rudolph, and Sevag Gharibian. “Quantum K-SAT Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>, 2025.","apa":"Kremer, S.-L., Rudolph, D., &#38; Gharibian, S. (2025). Quantum k-SAT Related Hypergraph Problems. In <i>arXiv:2506.17066</i>.","ieee":"S.-L. Kremer, D. Rudolph, and S. Gharibian, “Quantum k-SAT Related Hypergraph Problems,” <i>arXiv:2506.17066</i>. 2025.","ama":"Kremer S-L, Rudolph D, Gharibian S. Quantum k-SAT Related Hypergraph Problems. <i>arXiv:250617066</i>. Published online 2025.","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} }","mla":"Kremer, Simon-Luca, et al. “Quantum K-SAT Related Hypergraph Problems.” <i>ArXiv:2506.17066</i>, 2025."},"publication":"arXiv:2506.17066","abstract":[{"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.","lang":"eng"}],"date_created":"2025-06-27T06:56:35Z","external_id":{"arxiv":["2506.17066"]},"department":[{"_id":"7"},{"_id":"623"}],"type":"preprint","author":[{"first_name":"Simon-Luca","last_name":"Kremer","full_name":"Kremer, Simon-Luca"},{"full_name":"Rudolph, Dorian","last_name":"Rudolph","first_name":"Dorian","id":"57863"},{"id":"71541","full_name":"Gharibian, Sevag","first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian"}],"year":"2025","status":"public","title":"Quantum k-SAT Related Hypergraph Problems","date_updated":"2026-05-15T08:41:01Z","_id":"60432","language":[{"iso":"eng"}],"user_id":"71541"},{"_id":"50273","page":"7-17","volume":306,"user_id":"71541","status":"public","external_id":{"arxiv":["2401.01633"]},"citation":{"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>.","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} }","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>","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>.","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>","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.","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>."},"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.MFCS.2024.7","author":[{"full_name":"Agarwal, Avantika","last_name":"Agarwal","first_name":"Avantika"},{"full_name":"Gharibian, Sevag","first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","id":"71541"},{"full_name":"Koppula, Venkata","last_name":"Koppula","first_name":"Venkata"},{"full_name":"Rudolph, Dorian","first_name":"Dorian","last_name":"Rudolph","id":"57863"}],"title":"Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds","year":"2024","intvolume":"       306","publication_status":"published","date_updated":"2026-05-15T08:39:23Z","date_created":"2024-01-07T20:09:32Z","department":[{"_id":"7"},{"_id":"623"}],"type":"conference","publication":"Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)","issue":"7","abstract":[{"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}}$.","lang":"eng"}]},{"status":"public","_id":"27160","page":"1-27","volume":215,"user_id":"71541","citation":{"mla":"Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.” <i>13th Innovations in Theoretical Computer Science (ITCS 2022)</i>, vol. 215, no. 75, 2022, pp. 1–27, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">10.4230/LIPIcs.ITCS.2022.75</a>.","ama":"Gharibian S, Rudolph D. On polynomially many queries to NP or QMA oracles. In: <i>13th Innovations in Theoretical Computer Science (ITCS 2022)</i>. Vol 215. ; 2022:1-27. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">10.4230/LIPIcs.ITCS.2022.75</a>","bibtex":"@inproceedings{Gharibian_Rudolph_2022, title={On polynomially many queries to NP or QMA oracles}, volume={215}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">10.4230/LIPIcs.ITCS.2022.75</a>}, number={75}, booktitle={13th Innovations in Theoretical Computer Science (ITCS 2022)}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2022}, pages={1–27} }","apa":"Gharibian, S., &#38; Rudolph, D. (2022). On polynomially many queries to NP or QMA oracles. <i>13th Innovations in Theoretical Computer Science (ITCS 2022)</i>, <i>215</i>(75), 1–27. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">https://doi.org/10.4230/LIPIcs.ITCS.2022.75</a>","ieee":"S. Gharibian and D. Rudolph, “On polynomially many queries to NP or QMA oracles,” in <i>13th Innovations in Theoretical Computer Science (ITCS 2022)</i>, 2022, vol. 215, no. 75, pp. 1–27, doi: <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">10.4230/LIPIcs.ITCS.2022.75</a>.","chicago":"Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.” In <i>13th Innovations in Theoretical Computer Science (ITCS 2022)</i>, 215:1–27, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">https://doi.org/10.4230/LIPIcs.ITCS.2022.75</a>.","short":"S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, pp. 1–27."},"oa":"1","author":[{"id":"71541","full_name":"Gharibian, Sevag","first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian"},{"full_name":"Rudolph, Dorian","first_name":"Dorian","last_name":"Rudolph","id":"57863"}],"year":"2022","title":"On polynomially many queries to NP or QMA oracles","intvolume":"       215","date_updated":"2026-04-30T14:11:00Z","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15671"}],"doi":"10.4230/LIPIcs.ITCS.2022.75","issue":"75","publication":"13th Innovations in Theoretical Computer Science (ITCS 2022)","abstract":[{"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.","lang":"eng"}],"date_created":"2021-11-05T08:08:29Z","department":[{"_id":"623"},{"_id":"7"}],"type":"conference"}]