[{"type":"conference","publication":"17th Innovations in Theoretical Computer Science Conference (ITCS 2026)","status":"public","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"}],"user_id":"71541","_id":"57866","external_id":{"arxiv":["2412.19623"]},"language":[{"iso":"eng"}],"publication_status":"published","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} }","short":"M. Aldi, S. Gharibian, D. Rudolph, in: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), 2026, 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.","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.","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.","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."},"page":"7:1-7:24","intvolume":"       362","year":"2026","date_created":"2024-12-30T13:55:27Z","author":[{"first_name":"Marco","last_name":"Aldi","full_name":"Aldi, Marco"},{"first_name":"Sevag","full_name":"Gharibian, Sevag","id":"71541","orcid":"0000-0002-9992-3379","last_name":"Gharibian"},{"first_name":"Dorian","last_name":"Rudolph","full_name":"Rudolph, Dorian","id":"57863"}],"volume":362,"date_updated":"2026-01-23T07:53:03Z","title":"An unholy trinity: TFNP, polynomial systems, and the quantum  satisfiability problem"},{"user_id":"71541","_id":"50272","external_id":{"arxiv":["2401.02368"]},"language":[{"iso":"eng"}],"type":"conference","publication":"16th Innovations in Theoretical Computer Science (ITCS)","status":"public","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"}],"date_created":"2024-01-07T20:09:13Z","author":[{"last_name":"Rudolph","full_name":"Rudolph, Dorian","first_name":"Dorian"},{"id":"71541","full_name":"Gharibian, Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","first_name":"Sevag"},{"first_name":"Daniel","full_name":"Nagaj, Daniel","last_name":"Nagaj"}],"volume":325,"date_updated":"2025-02-11T07:21:23Z","doi":"10.4230/LIPIcs.ITCS.2025.85","title":"Quantum 2-SAT on low dimensional systems is $\\mathsf{QMA}_1$-complete:  Direct embeddings and black-box simulation","issue":"85","publication_status":"published","citation":{"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>.","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>.","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>","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} }","short":"D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 1–24.","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>.","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>"},"page":"1-24","intvolume":"       325","year":"2025"},{"citation":{"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.","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} }","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)."},"year":"2025","title":"Quantum k-SAT Related Hypergraph Problems","date_created":"2025-06-27T06:56:35Z","author":[{"last_name":"Kremer","full_name":"Kremer, Simon-Luca","first_name":"Simon-Luca"},{"first_name":"Dorian","last_name":"Rudolph","full_name":"Rudolph, Dorian","id":"57863"},{"first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","id":"71541","full_name":"Gharibian, Sevag"}],"date_updated":"2025-06-27T06:57:03Z","status":"public","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"}],"type":"preprint","publication":"arXiv:2506.17066","language":[{"iso":"eng"}],"user_id":"71541","external_id":{"arxiv":["2506.17066"]},"_id":"60432"},{"intvolume":"       135","page":"030601","citation":{"short":"H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, Physical Review Letters 135 (2025) 030601.","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} }","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>.","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>","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>.","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>"},"year":"2025","publication_status":"published","doi":"10.1103/29qw-bssx","title":"Beating Grover search for low-energy estimation and state preparation","volume":135,"author":[{"last_name":"Buhrman","full_name":"Buhrman, Harry","first_name":"Harry"},{"orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541","first_name":"Sevag"},{"last_name":"Landau","full_name":"Landau, Zeph","first_name":"Zeph"},{"last_name":"Gall","full_name":"Gall, François Le","first_name":"François Le"},{"first_name":"Norbert","last_name":"Schuch","full_name":"Schuch, Norbert"},{"full_name":"Tamaki, Suguru","last_name":"Tamaki","first_name":"Suguru"}],"date_created":"2024-07-04T09:02:42Z","date_updated":"2025-07-16T10:25:43Z","status":"public","abstract":[{"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.","lang":"eng"}],"publication":"Physical Review Letters","type":"journal_article","language":[{"iso":"eng"}],"user_id":"71541","external_id":{"arxiv":["2407.03073"]},"_id":"55037"},{"user_id":"71541","department":[{"_id":"7"},{"_id":"623"}],"external_id":{"arxiv":["2510.18164"]},"_id":"61922","language":[{"iso":"eng"}],"type":"preprint","publication":"SIAM Symposium on Simplicity in Algorithms (SOSA)","status":"public","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":[{"full_name":"Buhrman, Harry","last_name":"Buhrman","first_name":"Harry"},{"first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541"},{"first_name":"Zeph","last_name":"Landau","full_name":"Landau, Zeph"},{"first_name":"François Le","last_name":"Gall","full_name":"Gall, François Le"},{"first_name":"Norbert","full_name":"Schuch, Norbert","last_name":"Schuch"},{"first_name":"Suguru","last_name":"Tamaki","full_name":"Tamaki, Suguru"}],"date_created":"2025-10-22T09:33:22Z","date_updated":"2026-01-07T14:26:56Z","title":"A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT","publication_status":"inpress","citation":{"mla":"Buhrman, Harry, et al. “A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT.” <i>SIAM Symposium on Simplicity in Algorithms (SOSA)</i>.","short":"H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, SIAM Symposium on Simplicity in Algorithms (SOSA) (n.d.).","bibtex":"@article{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki, title={A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT}, journal={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} }","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. In <i>SIAM Symposium on Simplicity in Algorithms (SOSA)</i>.","ama":"Buhrman H, Gharibian S, Landau Z, Gall FL, Schuch N, Tamaki S. A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. <i>SIAM Symposium on Simplicity in Algorithms (SOSA)</i>.","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,” <i>SIAM Symposium on Simplicity in Algorithms (SOSA)</i>. .","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.” <i>SIAM Symposium on Simplicity in Algorithms (SOSA)</i>, n.d."},"year":"2025"},{"language":[{"iso":"eng"}],"publication":"ACM SIGACT News","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."}],"date_created":"2023-10-30T12:19:11Z","title":"Guest Column: The 7 faces of quantum NP","issue":"4","year":"2024","user_id":"71541","_id":"48544","article_type":"review","type":"journal_article","status":"public","volume":54,"author":[{"orcid":"0000-0002-9992-3379","last_name":"Gharibian","id":"71541","full_name":"Gharibian, Sevag","first_name":"Sevag"}],"oa":"1","date_updated":"2024-01-07T18:16:36Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2310.18010"}],"related_material":{"link":[{"url":"https://dl.acm.org/doi/abs/10.1145/3639528.3639535","relation":"confirmation"}]},"publication_status":"published","intvolume":"        54","page":"54-91","citation":{"ieee":"S. Gharibian, “Guest Column: The 7 faces of quantum NP,” <i>ACM SIGACT News</i>, vol. 54, no. 4, pp. 54–91, 2024.","chicago":"Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” <i>ACM SIGACT News</i> 54, no. 4 (2024): 54–91.","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.","mla":"Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” <i>ACM SIGACT News</i>, vol. 54, no. 4, 2024, pp. 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} }","short":"S. Gharibian, ACM SIGACT News 54 (2024) 54–91."}},{"language":[{"iso":"eng"}],"user_id":"71541","_id":"50406","external_id":{"arxiv":["2401.03943"]},"status":"public","abstract":[{"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.","lang":"eng"}],"type":"conference","publication":"Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP)","title":"BQP, meet NP: Search-to-decision reductions and approximate counting","date_created":"2024-01-09T13:59:44Z","author":[{"first_name":"Sevag","id":"71541","full_name":"Gharibian, Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian"},{"full_name":"Kamminga, Jonas","last_name":"Kamminga","first_name":"Jonas"}],"volume":297,"date_updated":"2024-07-02T13:16:48Z","citation":{"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} }","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.","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.","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.","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."},"page":"1-19","intvolume":"       297","year":"2024","issue":"70","publication_status":"published"},{"publication_status":"published","issue":"7","year":"2024","page":"7-17","intvolume":"       306","citation":{"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>.","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>.","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>","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.","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} }","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>."},"date_updated":"2024-08-23T06:18:02Z","volume":306,"author":[{"full_name":"Agarwal, Avantika","last_name":"Agarwal","first_name":"Avantika"},{"first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","full_name":"Gharibian, Sevag","id":"71541"},{"last_name":"Koppula","full_name":"Koppula, Venkata","first_name":"Venkata"},{"last_name":"Rudolph","full_name":"Rudolph, Dorian","first_name":"Dorian"}],"date_created":"2024-01-07T20:09:32Z","title":"Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds","doi":"10.4230/LIPIcs.MFCS.2024.7","publication":"Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)","type":"conference","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","external_id":{"arxiv":["2401.01633"]},"_id":"50273","user_id":"71541","language":[{"iso":"eng"}]},{"publication":"arXiv:2411.04874","type":"preprint","status":"public","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]."}],"user_id":"71541","external_id":{"arxiv":["2411.04874"]},"_id":"56950","language":[{"iso":"eng"}],"citation":{"bibtex":"@article{Gharibian_Hecht_2024, title={Hardness of approximation for ground state problems}, journal={arXiv:2411.04874}, author={Gharibian, Sevag and Hecht, Carsten}, year={2024} }","short":"S. Gharibian, C. Hecht, ArXiv:2411.04874 (2024).","mla":"Gharibian, Sevag, and Carsten Hecht. “Hardness of Approximation for Ground State Problems.” <i>ArXiv:2411.04874</i>, 2024.","apa":"Gharibian, S., &#38; Hecht, C. (2024). Hardness of approximation for ground state problems. In <i>arXiv:2411.04874</i>.","ama":"Gharibian S, Hecht C. Hardness of approximation for ground state problems. <i>arXiv:241104874</i>. Published online 2024.","ieee":"S. Gharibian and C. Hecht, “Hardness of approximation for ground state problems,” <i>arXiv:2411.04874</i>. 2024.","chicago":"Gharibian, Sevag, and Carsten Hecht. “Hardness of Approximation for Ground State Problems.” <i>ArXiv:2411.04874</i>, 2024."},"year":"2024","date_created":"2024-11-08T07:58:24Z","author":[{"first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","full_name":"Gharibian, Sevag","id":"71541"},{"full_name":"Hecht, Carsten","last_name":"Hecht","first_name":"Carsten"}],"date_updated":"2024-11-08T07:58:44Z","title":"Hardness of approximation for ground state problems"},{"language":[{"iso":"eng"}],"_id":"56944","external_id":{"arxiv":["2411.04120"]},"user_id":"71541","abstract":[{"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.","lang":"eng"}],"status":"public","type":"preprint","publication":"arXiv:2411.04120","title":"Second order cone relaxations for quantum Max Cut","date_updated":"2024-11-07T12:10:28Z","author":[{"full_name":"Huber, Felix","last_name":"Huber","first_name":"Felix"},{"last_name":"Thompson","full_name":"Thompson, Kevin","first_name":"Kevin"},{"first_name":"Ojas","full_name":"Parekh, Ojas","last_name":"Parekh"},{"first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","id":"71541","full_name":"Gharibian, Sevag"}],"date_created":"2024-11-07T12:09:37Z","year":"2024","citation":{"ieee":"F. Huber, K. Thompson, O. Parekh, and S. Gharibian, “Second order cone relaxations for quantum Max Cut,” <i>arXiv:2411.04120</i>. 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.","ama":"Huber F, Thompson K, Parekh O, Gharibian S. Second order cone relaxations for quantum Max Cut. <i>arXiv:241104120</i>. Published online 2024.","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} }","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).","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>."}},{"user_id":"71541","department":[{"_id":"623"},{"_id":"7"}],"_id":"32407","type":"conference","status":"public","author":[{"first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","full_name":"Gharibian, Sevag","id":"71541"},{"first_name":"Ryu","full_name":"Hayakawa, Ryu","last_name":"Hayakawa"},{"first_name":"François Le","full_name":"Gall, François Le","last_name":"Gall"},{"last_name":"Morimae","full_name":"Morimae, Tomoyuki","first_name":"Tomoyuki"}],"volume":261,"date_updated":"2023-10-09T04:17:10Z","doi":"10.4230/LIPIcs.ICALP.2023.32","publication_status":"published","citation":{"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.","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} }","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>.","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>","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>","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>."},"intvolume":"       261","page":"1-19","external_id":{"arxiv":["2207.10250"]},"language":[{"iso":"eng"}],"publication":"Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP)","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."}],"date_created":"2022-07-22T12:32:40Z","title":"Improved Hardness Results for the Guided Local Hamiltonian Problem","issue":"32","year":"2023"},{"title":"Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture","doi":"10.1137/22m1513721","publisher":"Society for Industrial & Applied Mathematics (SIAM)","date_updated":"2024-01-07T18:20:37Z","volume":52,"date_created":"2024-01-07T18:19:42Z","author":[{"first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541"},{"full_name":"Le Gall, François","last_name":"Le Gall","first_name":"François"}],"year":"2023","intvolume":"        52","page":"1009-1038","citation":{"ama":"Gharibian S, Le Gall F. Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. <i>SIAM Journal on Computing</i>. 2023;52(4):1009-1038. doi:<a href=\"https://doi.org/10.1137/22m1513721\">10.1137/22m1513721</a>","ieee":"S. Gharibian and F. Le Gall, “Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture,” <i>SIAM Journal on Computing</i>, vol. 52, no. 4, pp. 1009–1038, 2023, doi: <a href=\"https://doi.org/10.1137/22m1513721\">10.1137/22m1513721</a>.","chicago":"Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.” <i>SIAM Journal on Computing</i> 52, no. 4 (2023): 1009–38. <a href=\"https://doi.org/10.1137/22m1513721\">https://doi.org/10.1137/22m1513721</a>.","apa":"Gharibian, S., &#38; Le Gall, F. (2023). Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. <i>SIAM Journal on Computing</i>, <i>52</i>(4), 1009–1038. <a href=\"https://doi.org/10.1137/22m1513721\">https://doi.org/10.1137/22m1513721</a>","short":"S. Gharibian, F. Le Gall, SIAM Journal on Computing 52 (2023) 1009–1038.","bibtex":"@article{Gharibian_Le Gall_2023, title={Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}, volume={52}, DOI={<a href=\"https://doi.org/10.1137/22m1513721\">10.1137/22m1513721</a>}, number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial &#38; Applied Mathematics (SIAM)}, author={Gharibian, Sevag and Le Gall, François}, year={2023}, pages={1009–1038} }","mla":"Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.” <i>SIAM Journal on Computing</i>, vol. 52, no. 4, Society for Industrial &#38; Applied Mathematics (SIAM), 2023, pp. 1009–38, doi:<a href=\"https://doi.org/10.1137/22m1513721\">10.1137/22m1513721</a>."},"publication_identifier":{"issn":["0097-5397","1095-7111"]},"publication_status":"published","issue":"4","keyword":["General Mathematics","General Computer Science"],"language":[{"iso":"eng"}],"_id":"50271","user_id":"71541","status":"public","publication":"SIAM Journal on Computing","type":"journal_article"},{"year":"2023","title":"Quantum space, ground space traversal, and how to embed multi-prover  interactive proofs into unentanglement","date_created":"2022-06-13T14:40:46Z","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."}],"publication":"14th Innovations in Theoretical Computer Science (ITCS)","language":[{"iso":"eng"}],"external_id":{"arxiv":["2206.05243"]},"page":"53:1-53:23","intvolume":"       251","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>","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>.","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>.","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>","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>.","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} }","short":"S. Gharibian, D. Rudolph, in: 14th Innovations in Theoretical Computer Science (ITCS), 2023, p. 53:1-53:23."},"publication_status":"published","doi":"10.4230/LIPIcs.ITCS.2023.53","volume":251,"author":[{"full_name":"Gharibian, Sevag","id":"71541","orcid":"0000-0002-9992-3379","last_name":"Gharibian","first_name":"Sevag"},{"full_name":"Rudolph, Dorian","last_name":"Rudolph","first_name":"Dorian"}],"date_updated":"2023-02-28T11:06:55Z","status":"public","type":"conference","department":[{"_id":"623"},{"_id":"7"}],"user_id":"71541","_id":"31872"},{"year":"2023","title":"The Complexity of Translationally Invariant Problems beyond Ground State Energies","date_created":"2020-12-24T14:15:09Z","publication":"Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS)","language":[{"iso":"eng"}],"external_id":{"arxiv":["2012.12717"]},"intvolume":"       254","page":"54:1-54:21","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>","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>.","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>","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>.","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} }","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."},"publication_status":"published","doi":"https://doi.org/10.4230/LIPIcs.STACS.2023.54","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2012.12717"}],"volume":254,"author":[{"first_name":"Sevag","full_name":"Gharibian, Sevag","id":"71541","orcid":"0000-0002-9992-3379","last_name":"Gharibian"},{"last_name":"Watson","full_name":"Watson, James","first_name":"James"},{"first_name":"Johannes","full_name":"Bausch, Johannes","last_name":"Bausch"}],"oa":"1","date_updated":"2023-05-04T17:51:23Z","status":"public","type":"conference","department":[{"_id":"623"},{"_id":"7"}],"user_id":"71541","_id":"20841"},{"citation":{"ama":"Bittel L, Gharibian S, Kliesch M. The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. In: <i>Proceedings of the 38th Computational Complexity Conference (CCC)</i>. Vol 264. Leibniz International Proceedings in Informatics (LIPIcs). ; 2023:34:1-34:24. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CCC.2023.34\">10.4230/LIPIcs.CCC.2023.34</a>","ieee":"L. Bittel, S. Gharibian, and M. Kliesch, “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate,” in <i>Proceedings of the 38th Computational Complexity Conference (CCC)</i>, 2023, vol. 264, no. 34, p. 34:1-34:24, doi: <a href=\"https://doi.org/10.4230/LIPIcs.CCC.2023.34\">10.4230/LIPIcs.CCC.2023.34</a>.","chicago":"Bittel, Lennart, Sevag Gharibian, and Martin Kliesch. “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate.” In <i>Proceedings of the 38th Computational Complexity Conference (CCC)</i>, 264:34:1-34:24. Leibniz International Proceedings in Informatics (LIPIcs), 2023. <a href=\"https://doi.org/10.4230/LIPIcs.CCC.2023.34\">https://doi.org/10.4230/LIPIcs.CCC.2023.34</a>.","apa":"Bittel, L., Gharibian, S., &#38; Kliesch, M. (2023). The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. <i>Proceedings of the 38th Computational Complexity Conference (CCC)</i>, <i>264</i>(34), 34:1-34:24. <a href=\"https://doi.org/10.4230/LIPIcs.CCC.2023.34\">https://doi.org/10.4230/LIPIcs.CCC.2023.34</a>","mla":"Bittel, Lennart, et al. “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate.” <i>Proceedings of the 38th Computational Complexity Conference (CCC)</i>, vol. 264, no. 34, 2023, p. 34:1-34:24, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CCC.2023.34\">10.4230/LIPIcs.CCC.2023.34</a>.","bibtex":"@inproceedings{Bittel_Gharibian_Kliesch_2023, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate}, volume={264}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.CCC.2023.34\">10.4230/LIPIcs.CCC.2023.34</a>}, number={34}, booktitle={Proceedings of the 38th Computational Complexity Conference (CCC)}, author={Bittel, Lennart and Gharibian, Sevag and Kliesch, Martin}, year={2023}, pages={34:1-34:24}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","short":"L. Bittel, S. Gharibian, M. Kliesch, in: Proceedings of the 38th Computational Complexity Conference (CCC), 2023, p. 34:1-34:24."},"intvolume":"       264","page":"34:1-34:24","publication_status":"published","doi":"10.4230/LIPIcs.CCC.2023.34","date_updated":"2023-07-10T14:33:00Z","author":[{"full_name":"Bittel, Lennart","last_name":"Bittel","first_name":"Lennart"},{"orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541","first_name":"Sevag"},{"full_name":"Kliesch, Martin","last_name":"Kliesch","first_name":"Martin"}],"volume":264,"status":"public","type":"conference","_id":"34138","user_id":"71541","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","department":[{"_id":"623"},{"_id":"7"}],"year":"2023","issue":"34","title":"The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate","date_created":"2022-11-24T08:07:56Z","abstract":[{"lang":"eng","text":"Variational Quantum Algorithms (VQAs), such as the Quantum Approximate\r\nOptimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen\r\nintense study towards near-term applications on quantum hardware. A crucial\r\nparameter for VQAs is the depth of the variational ansatz used - the smaller\r\nthe depth, the more amenable the ansatz is to near-term quantum hardware in\r\nthat it gives the circuit a chance to be fully executed before the system\r\ndecoheres. This potential for depth reduction has made VQAs a staple of Noisy\r\nIntermediate-Scale Quantum (NISQ)-era research.\r\n  In this work, we show that approximating the optimal depth for a given VQA\r\nansatz is intractable. Formally, we show that for any constant $\\epsilon>0$, it\r\nis QCMA-hard to approximate the optimal depth of a VQA ansatz within\r\nmultiplicative factor $N^{1-\\epsilon}$, for $N$ denoting the encoding size of\r\nthe VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum\r\ngeneralization of NP.) We then show that this hardness persists even in the\r\n\"simpler\" setting of QAOAs. To our knowledge, this yields the first natural\r\nQCMA-hard-to-approximate problems. To achieve these results, we bypass the need\r\nfor a PCP theorem for QCMA by appealing to the disperser-based NP-hardness of\r\napproximation construction of [Umans, FOCS 1999]."}],"publication":"Proceedings of the 38th Computational Complexity Conference (CCC)","language":[{"iso":"eng"}],"external_id":{"arxiv":["2211.12519"]}},{"publication_status":"published","year":"2022","citation":{"short":"S. Gharibian, F.L. Gall, in: Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 2022, pp. 19–32.","bibtex":"@inproceedings{Gharibian_Gall_2022, title={Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture}, booktitle={Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)}, author={Gharibian, Sevag and Gall, François Le}, year={2022}, pages={19–32} }","mla":"Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture.” <i>Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)</i>, 2022, pp. 19–32.","apa":"Gharibian, S., &#38; Gall, F. L. (2022). Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture. <i>Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)</i>, 19–32.","ama":"Gharibian S, Gall FL. Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture. In: <i>Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)</i>. ; 2022:19-32.","chicago":"Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture.” In <i>Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)</i>, 19–32, 2022.","ieee":"S. Gharibian and F. L. Gall, “Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture,” in <i>Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)</i>, 2022, pp. 19–32."},"page":"19-32","oa":"1","date_updated":"2023-10-09T04:17:29Z","date_created":"2021-11-18T07:32:56Z","author":[{"first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","id":"71541","full_name":"Gharibian, Sevag"},{"first_name":"François Le","last_name":"Gall","full_name":"Gall, François Le"}],"title":"Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture","main_file_link":[{"url":"https://arxiv.org/abs/2111.09079","open_access":"1"}],"type":"conference","publication":"Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)","abstract":[{"lang":"eng","text":"The Quantum Singular Value Transformation (QSVT) is a recent technique that\r\ngives a unified framework to describe most quantum algorithms discovered so\r\nfar, and may lead to the development of novel quantum algorithms. In this paper\r\nwe investigate the hardness of classically simulating the QSVT. A recent result\r\nby Chia, Gily\\'en, Li, Lin, Tang and Wang (STOC 2020) showed that the QSVT can\r\nbe efficiently \"dequantized\" for low-rank matrices, and discussed its\r\nimplication to quantum machine learning. In this work, motivated by\r\nestablishing the superiority of quantum algorithms for quantum chemistry and\r\nmaking progress on the quantum PCP conjecture, we focus on the other main class\r\nof matrices considered in applications of the QSVT, sparse matrices.\r\n  We first show how to efficiently \"dequantize\", with arbitrarily small\r\nconstant precision, the QSVT associated with a low-degree polynomial. We apply\r\nthis technique to design classical algorithms that estimate, with constant\r\nprecision, the singular values of a sparse matrix. We show in particular that a\r\ncentral computational problem considered by quantum algorithms for quantum\r\nchemistry (estimating the ground state energy of a local Hamiltonian when\r\ngiven, as an additional input, a state sufficiently close to the ground state)\r\ncan be solved efficiently with constant precision on a classical computer. As a\r\ncomplementary result, we prove that with inverse-polynomial precision, the same\r\nproblem becomes BQP-complete. This gives theoretical evidence for the\r\nsuperiority of quantum algorithms for chemistry, and strongly suggests that\r\nsaid superiority stems from the improved precision achievable in the quantum\r\nsetting. We also discuss how this dequantization technique may help make\r\nprogress on the central quantum PCP conjecture."}],"status":"public","_id":"27531","external_id":{"arxiv":["2111.09079"]},"user_id":"71541","department":[{"_id":"623"},{"_id":"7"}],"language":[{"iso":"eng"}]},{"publication":"Computational Complexity","language":[{"iso":"eng"}],"keyword":["Computational Mathematics","Computational Theory and Mathematics","General Mathematics","Theoretical Computer Science"],"issue":"2","year":"2022","date_created":"2022-12-21T10:53:52Z","publisher":"Springer Science and Business Media LLC","title":"Quantum generalizations of the polynomial hierarchy with applications to QMA(2)","type":"journal_article","status":"public","department":[{"_id":"623"},{"_id":"7"}],"user_id":"71541","_id":"34700","article_number":"13","publication_identifier":{"issn":["1016-3328","1420-8954"]},"publication_status":"published","intvolume":"        31","citation":{"apa":"Gharibian, S., Santha, M., Sikora, J., Sundaram, A., &#38; Yirka, J. (2022). Quantum generalizations of the polynomial hierarchy with applications to QMA(2). <i>Computational Complexity</i>, <i>31</i>(2), Article 13. <a href=\"https://doi.org/10.1007/s00037-022-00231-8\">https://doi.org/10.1007/s00037-022-00231-8</a>","bibtex":"@article{Gharibian_Santha_Sikora_Sundaram_Yirka_2022, title={Quantum generalizations of the polynomial hierarchy with applications to QMA(2)}, volume={31}, DOI={<a href=\"https://doi.org/10.1007/s00037-022-00231-8\">10.1007/s00037-022-00231-8</a>}, number={213}, journal={Computational Complexity}, publisher={Springer Science and Business Media LLC}, author={Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin}, year={2022} }","mla":"Gharibian, Sevag, et al. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” <i>Computational Complexity</i>, vol. 31, no. 2, 13, Springer Science and Business Media LLC, 2022, doi:<a href=\"https://doi.org/10.1007/s00037-022-00231-8\">10.1007/s00037-022-00231-8</a>.","short":"S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, Computational Complexity 31 (2022).","ieee":"S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka, “Quantum generalizations of the polynomial hierarchy with applications to QMA(2),” <i>Computational Complexity</i>, vol. 31, no. 2, Art. no. 13, 2022, doi: <a href=\"https://doi.org/10.1007/s00037-022-00231-8\">10.1007/s00037-022-00231-8</a>.","chicago":"Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” <i>Computational Complexity</i> 31, no. 2 (2022). <a href=\"https://doi.org/10.1007/s00037-022-00231-8\">https://doi.org/10.1007/s00037-022-00231-8</a>.","ama":"Gharibian S, Santha M, Sikora J, Sundaram A, Yirka J. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). <i>Computational Complexity</i>. 2022;31(2). doi:<a href=\"https://doi.org/10.1007/s00037-022-00231-8\">10.1007/s00037-022-00231-8</a>"},"volume":31,"author":[{"first_name":"Sevag","full_name":"Gharibian, Sevag","id":"71541","orcid":"0000-0002-9992-3379","last_name":"Gharibian"},{"full_name":"Santha, Miklos","last_name":"Santha","first_name":"Miklos"},{"last_name":"Sikora","full_name":"Sikora, Jamie","first_name":"Jamie"},{"full_name":"Sundaram, Aarthi","last_name":"Sundaram","first_name":"Aarthi"},{"full_name":"Yirka, Justin","last_name":"Yirka","first_name":"Justin"}],"date_updated":"2023-02-28T11:07:02Z","doi":"10.1007/s00037-022-00231-8"},{"status":"public","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."}],"type":"conference","publication":"13th Innovations in Theoretical Computer Science (ITCS 2022)","language":[{"iso":"eng"}],"user_id":"71541","department":[{"_id":"623"},{"_id":"7"}],"_id":"27160","citation":{"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>","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>.","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>.","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} }","short":"S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, pp. 1–27.","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>.","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>"},"intvolume":"       215","page":"1-27","year":"2022","issue":"75","main_file_link":[{"url":"https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15671","open_access":"1"}],"doi":"10.4230/LIPIcs.ITCS.2022.75","title":"On polynomially many queries to NP or QMA oracles","date_created":"2021-11-05T08:08:29Z","author":[{"first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","full_name":"Gharibian, Sevag","id":"71541"},{"full_name":"Rudolph, Dorian","last_name":"Rudolph","first_name":"Dorian"}],"volume":215,"oa":"1","date_updated":"2023-02-28T11:07:56Z"},{"title":"Towards Quantum One-Time Memories from Stateless Hardware","doi":"10.22331/q-2021-04-08-429","date_updated":"2023-02-28T11:07:47Z","publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","volume":5,"author":[{"last_name":"Broadbent","full_name":"Broadbent, Anne","first_name":"Anne"},{"first_name":"Sevag","id":"71541","full_name":"Gharibian, Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379"},{"first_name":"Hong-Sheng","full_name":"Zhou, Hong-Sheng","last_name":"Zhou"}],"date_created":"2022-02-08T10:59:00Z","year":"2021","intvolume":"         5","citation":{"ama":"Broadbent A, Gharibian S, Zhou H-S. Towards Quantum One-Time Memories from Stateless Hardware. <i>Quantum</i>. 2021;5. doi:<a href=\"https://doi.org/10.22331/q-2021-04-08-429\">10.22331/q-2021-04-08-429</a>","chicago":"Broadbent, Anne, Sevag Gharibian, and Hong-Sheng Zhou. “Towards Quantum One-Time Memories from Stateless Hardware.” <i>Quantum</i> 5 (2021). <a href=\"https://doi.org/10.22331/q-2021-04-08-429\">https://doi.org/10.22331/q-2021-04-08-429</a>.","ieee":"A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories from Stateless Hardware,” <i>Quantum</i>, vol. 5, Art. no. 429, 2021, doi: <a href=\"https://doi.org/10.22331/q-2021-04-08-429\">10.22331/q-2021-04-08-429</a>.","apa":"Broadbent, A., Gharibian, S., &#38; Zhou, H.-S. (2021). Towards Quantum One-Time Memories from Stateless Hardware. <i>Quantum</i>, <i>5</i>, Article 429. <a href=\"https://doi.org/10.22331/q-2021-04-08-429\">https://doi.org/10.22331/q-2021-04-08-429</a>","mla":"Broadbent, Anne, et al. “Towards Quantum One-Time Memories from Stateless Hardware.” <i>Quantum</i>, vol. 5, 429, Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften, 2021, doi:<a href=\"https://doi.org/10.22331/q-2021-04-08-429\">10.22331/q-2021-04-08-429</a>.","bibtex":"@article{Broadbent_Gharibian_Zhou_2021, title={Towards Quantum One-Time Memories from Stateless Hardware}, volume={5}, DOI={<a href=\"https://doi.org/10.22331/q-2021-04-08-429\">10.22331/q-2021-04-08-429</a>}, number={429}, journal={Quantum}, publisher={Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften}, author={Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng}, year={2021} }","short":"A. Broadbent, S. Gharibian, H.-S. Zhou, Quantum 5 (2021)."},"publication_identifier":{"issn":["2521-327X"]},"publication_status":"published","keyword":["Physics and Astronomy (miscellaneous)","Atomic and Molecular Physics","and Optics"],"article_number":"429","language":[{"iso":"eng"}],"_id":"29780","department":[{"_id":"623"},{"_id":"7"}],"user_id":"71541","abstract":[{"lang":"eng","text":"<jats:p>A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless (<mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\"><mml:mi>i</mml:mi><mml:mo>.</mml:mo><mml:mi>e</mml:mi><mml:mo>.</mml:mo></mml:math>, reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver making at most 0.114<mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\"><mml:mi>n</mml:mi></mml:math> adaptive queries to the token (for <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\"><mml:mi>n</mml:mi></mml:math> the key size), in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the \"prepare-and-measure\" type. We also give two impossibility results showing certain assumptions in our scheme cannot be relaxed.</jats:p>"}],"status":"public","publication":"Quantum","type":"journal_article"},{"title":"Oracle complexity classes and local measurements on physical  Hamiltonians","main_file_link":[{"url":"https://arxiv.org/abs/1909.05981","open_access":"1"}],"oa":"1","date_updated":"2023-10-09T04:17:41Z","date_created":"2019-09-16T07:41:31Z","author":[{"first_name":"Sevag","full_name":"Gharibian, Sevag","id":"71541","last_name":"Gharibian","orcid":"0000-0002-9992-3379"},{"first_name":"Stephen","last_name":"Piddock","full_name":"Piddock, Stephen"},{"last_name":"Yirka","full_name":"Yirka, Justin","first_name":"Justin"}],"year":"2020","citation":{"apa":"Gharibian, S., Piddock, S., &#38; Yirka, J. (2020). Oracle complexity classes and local measurements on physical  Hamiltonians. <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>, 38.","bibtex":"@inproceedings{Gharibian_Piddock_Yirka_2020, title={Oracle complexity classes and local measurements on physical  Hamiltonians}, booktitle={Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, author={Gharibian, Sevag and Piddock, Stephen and Yirka, Justin}, year={2020}, pages={38} }","mla":"Gharibian, Sevag, et al. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>, 2020, p. 38.","short":"S. Gharibian, S. Piddock, J. Yirka, in: Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.","ieee":"S. Gharibian, S. Piddock, and J. Yirka, “Oracle complexity classes and local measurements on physical  Hamiltonians,” in <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>, 2020, p. 38.","chicago":"Gharibian, Sevag, Stephen Piddock, and Justin Yirka. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” In <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>, 38, 2020.","ama":"Gharibian S, Piddock S, Yirka J. Oracle complexity classes and local measurements on physical  Hamiltonians. In: <i>Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)</i>. ; 2020:38."},"page":"38","publication_status":"published","language":[{"iso":"eng"}],"_id":"13226","external_id":{"arxiv":["1909.05981"]},"user_id":"71541","department":[{"_id":"623"},{"_id":"7"}],"abstract":[{"lang":"eng","text":"The canonical problem for the class Quantum Merlin-Arthur (QMA) is that of\r\nestimating ground state energies of local Hamiltonians. Perhaps surprisingly,\r\n[Ambainis, CCC 2014] showed that the related, but arguably more natural,\r\nproblem of simulating local measurements on ground states of local Hamiltonians\r\n(APX-SIM) is likely harder than QMA. Indeed, [Ambainis, CCC 2014] showed that\r\nAPX-SIM is P^QMA[log]-complete, for P^QMA[log] the class of languages decidable\r\nby a P machine making a logarithmic number of adaptive queries to a QMA oracle.\r\nIn this work, we show that APX-SIM is P^QMA[log]-complete even when restricted\r\nto more physical Hamiltonians, obtaining as intermediate steps a variety of\r\nrelated complexity-theoretic results.\r\n  We first give a sequence of results which together yield P^QMA[log]-hardness\r\nfor APX-SIM on well-motivated Hamiltonians: (1) We show that for NP, StoqMA,\r\nand QMA oracles, a logarithmic number of adaptive queries is equivalent to\r\npolynomially many parallel queries. These equalities simplify the proofs of our\r\nsubsequent results. (2) Next, we show that the hardness of APX-SIM is preserved\r\nunder Hamiltonian simulations (a la [Cubitt, Montanaro, Piddock, 2017]). As a\r\nbyproduct, we obtain a full complexity classification of APX-SIM, showing it is\r\ncomplete for P, P^||NP, P^||StoqMA, or P^||QMA depending on the Hamiltonians\r\nemployed. (3) Leveraging the above, we show that APX-SIM is P^QMA[log]-complete\r\nfor any family of Hamiltonians which can efficiently simulate spatially sparse\r\nHamiltonians, including physically motivated models such as the 2D Heisenberg\r\nmodel.\r\n  Our second focus considers 1D systems: We show that APX-SIM remains\r\nP^QMA[log]-complete even for local Hamiltonians on a 1D line of 8-dimensional\r\nqudits. This uses a number of ideas from above, along with replacing the \"query\r\nHamiltonian\" of [Ambainis, CCC 2014] with a new \"sifter\" construction."}],"status":"public","type":"conference","publication":"Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)"}]