@inproceedings{57866, abstract = {{The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash equilibria, subclasses of TFNP remain arguably few and far between. In this work, we define two new subclasses of TFNP borne of the study of complex polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental Theorem of Algebra (SFTA). The first of these is based on B\'ezout's theorem from algebraic geometry, marking the first TFNP subclass based on an algebraic geometric principle. At the heart of our study is the computational problem known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR), first studied by [Laumann, L\"auchli, Moessner, Scardicchio, and Sondhi 2010]. Among other results, we show that QSAT with SDR is MHS-complete, thus giving not only the first link between quantum complexity theory and TFNP, but also the first TFNP problem whose classical variant (SAT with SDR) is easy but whose quantum variant is hard. We also show how to embed the roots of a sparse, high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of MHS. We conjecture this construction also works in the low-error setting, which would imply SFTA is contained in MHS.}}, author = {{Aldi, Marco and Gharibian, Sevag and Rudolph, Dorian}}, booktitle = {{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)}}, pages = {{7:1--7:24}}, title = {{{An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem}}}, volume = {{362}}, year = {{2026}}, } @inproceedings{50272, abstract = {{Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSAT with each constraint acting on a $k$-dimensional and $l$-dimensional qudit pair, denoted $(k,l)$-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain $\mathsf{QMA}_1$-hard, in that $(2,5)$-QSAT is $\mathsf{QMA}_1$-complete. In contrast, $2$-SAT on qubits is well-known to be poly-time solvable [Bravyi, 2006]. Our second main result proves that $(3,d)$-QSAT on the 1D line with $d\in O(1)$ is also $\mathsf{QMA}_1$-hard. Finally, we initiate the study of 1D $(2,d)$-QSAT by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state. Our first result uses a direct embedding, combining a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset, Nagaj, 2013]. Of note is a new simplified and analytic proof for the latter (as opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection Lemma", allowing us to break low energy analyses into small patches of projectors, and to improve the soundness analysis of [GN13] from $\Omega(1/T^6)$ to $\Omega(1/T^2)$, for $T$ the number of gates. Our second result goes via black-box reduction: Given an arbitrary 1D Hamiltonian $H$ on $d'$-dimensional qudits, we show how to embed it into an effective null-space of a 1D $(3,d)$-QSAT instance, for $d\in O(1)$. Our approach may be viewed as a weaker notion of "simulation" (\`a la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based $\mathsf{QMA}_1$-hardness result, i.e. for frustration-free Hamiltonians.}}, author = {{Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel}}, booktitle = {{16th Innovations in Theoretical Computer Science (ITCS)}}, number = {{85}}, pages = {{1--24}}, title = {{{Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation}}}, doi = {{10.4230/LIPIcs.ITCS.2025.85}}, volume = {{325}}, year = {{2025}}, } @unpublished{60432, abstract = {{The Quantum k-SAT problem is the quantum generalization of the k-SAT problem. It is the problem whether a given local Hamiltonian is frustration-free. Frustration-free means that the ground state of the k-local Hamiltonian minimizes the energy of every local interaction term simultaneously. This is a central question in quantum physics and a canonical QMA_1-complete problem. The Quantum k-SAT problem is not as well studied as the classical k-SAT problem in terms of special tractable cases, approximation algorithms and parameterized complexity. In this paper, we will give a graph-theoretic study of the Quantum k-SAT problem with the structures core and radius. These hypergraph structures are important to solve the Quantum k-SAT problem. We can solve a Quantum k-SAT instance in polynomial time if the derived hypergraph has a core of size n-m+a, where a is a constant, and the radius is at most logarithmic. If it exists, we can find a core of size n-m+a with the best possible radius in polynomial time, whereas finding a general minimum core with minimal radius is NP-hard.}}, author = {{Kremer, Simon-Luca and Rudolph, Dorian and Gharibian, Sevag}}, booktitle = {{arXiv:2506.17066}}, title = {{{Quantum k-SAT Related Hypergraph Problems}}}, year = {{2025}}, } @article{55037, abstract = {{Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this work, we give quantum algorithms which, given any $k$-body Hamiltonian $H$, compute an estimate for the ground state energy and prepare a quantum state achieving said energy, respectively. Specifically, for any $\varepsilon>0$, our algorithms return, with high probability, an estimate of the ground state energy of $H$ within additive error $\varepsilon M$, or a quantum state with the corresponding energy. Here, $M$ is the total strength of all interaction terms, which in general is extensive in the system size. Our approach makes no assumptions about the geometry or spatial locality of interaction terms of the input Hamiltonian and thus handles even long-range or all-to-all interactions, such as in quantum chemistry, where lattice-based techniques break down. In this fully general setting, the runtime of our algorithms scales as $2^{cn/2}$ for $c<1$, yielding the first quantum algorithms for low-energy estimation breaking the natural bound based on Grover search. The core of our approach is remarkably simple, and relies on showing that any $k$-body Hamiltonian has a low-energy subspace of exponential dimension.}}, author = {{Buhrman, Harry and Gharibian, Sevag and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}}, journal = {{Physical Review Letters}}, pages = {{030601}}, title = {{{Beating Grover search for low-energy estimation and state preparation}}}, doi = {{10.1103/29qw-bssx}}, volume = {{135}}, year = {{2025}}, } @unpublished{61922, abstract = {{We present an extremely simple polynomial-space exponential-time $(1-\varepsilon)$-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space $(1-\varepsilon)$-approximation algorithms by Hirsch (Discrete Applied Mathematics, 2003) and Escoffier, Paschos and Tourniaire (Theoretical Computer Science, 2014). Our algorithm repeatedly samples an assignment uniformly at random until finding an assignment that satisfies a large enough fraction of clauses. Surprisingly, we can show the efficiency of this simpler approach by proving that in any instance of MAX-k-SAT (or more generally any instance of MAXCSP), an exponential number of assignments satisfy a fraction of clauses close to the optimal value.}}, author = {{Buhrman, Harry and Gharibian, Sevag and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}}, booktitle = {{SIAM Symposium on Simplicity in Algorithms (SOSA)}}, title = {{{A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT}}}, year = {{2025}}, } @article{48544, abstract = {{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.}}, author = {{Gharibian, Sevag}}, journal = {{ACM SIGACT News}}, number = {{4}}, pages = {{54--91}}, title = {{{Guest Column: The 7 faces of quantum NP}}}, volume = {{54}}, year = {{2024}}, } @inproceedings{50406, abstract = {{What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $\Theta(n)$ queries to an NP oracle to compute a witness to a given SAT formula, quantumly $\Theta(\log n)$ queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires $\Omega(\log n)$ queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires $\Omega(\log n)$ queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making $o(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.}}, author = {{Gharibian, Sevag and Kamminga, Jonas}}, booktitle = {{Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP)}}, number = {{70}}, pages = {{1--19}}, title = {{{BQP, meet NP: Search-to-decision reductions and approximate counting}}}, volume = {{297}}, year = {{2024}}, } @inproceedings{50273, abstract = {{The Polynomial-Time Hierarchy ($\mathsf{PH}$) is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum advantage'' analyses for near-term quantum computers. Quantumly, however, despite the fact that at least \emph{four} definitions of quantum $\mathsf{PH}$ exist, it has been challenging to prove analogues for these of even basic facts from $\mathsf{PH}$. This work studies three quantum-verifier based generalizations of $\mathsf{PH}$, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings ($\mathsf{QCPH}$) and quantum mixed states ($\mathsf{QPH}$) as proofs, and one of which is new to this work, utilizing quantum pure states ($\mathsf{pureQPH}$) as proofs. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for $\mathsf{QCPH}$. Then, for our new class $\mathsf{pureQPH}$, we show one-sided error reduction for $\mathsf{pureQPH}$, as well as the first bounds relating these quantum variants of $\mathsf{PH}$, namely $\mathsf{QCPH}\subseteq \mathsf{pureQPH} \subseteq \mathsf{EXP}^{\mathsf{PP}}$.}}, author = {{Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian}}, booktitle = {{Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)}}, number = {{7}}, pages = {{7--17}}, title = {{{Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds}}}, doi = {{10.4230/LIPIcs.MFCS.2024.7}}, volume = {{306}}, year = {{2024}}, } @unpublished{56950, abstract = {{After nearly two decades of research, the question of a quantum PCP theorem for quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a result, proving QMA-hardness of approximation for ground state energy estimation has remained elusive. Recently, it was shown [Bittel, Gharibian, Kliesch, CCC 2023] that a natural problem involving variational quantum circuits is QCMA-hard to approximate within ratio N^(1-eps) for any eps > 0 and N the input size. Unfortunately, this problem was not related to quantum CSPs, leaving the question of hardness of approximation for quantum CSPs open. In this work, we show that if instead of focusing on ground state energies, one considers computing properties of the ground space, QCMA-hardness of computing ground space properties can be shown. In particular, we show that it is (1) QCMA-complete within ratio N^(1-eps) to approximate the Ground State Connectivity problem (GSCON), and (2) QCMA-hard within the same ratio to estimate the amount of entanglement of a local Hamiltonian's ground state, denoted Ground State Entanglement (GSE). As a bonus, a simplification of our construction yields NP-completeness of approximation for a natural k-SAT reconfiguration problem, to be contrasted with the recent PCP-based PSPACE hardness of approximation results for a different definition of k-SAT reconfiguration [Karthik C.S. and Manurangsi, 2023, and Hirahara, Ohsaka, STOC 2024].}}, author = {{Gharibian, Sevag and Hecht, Carsten}}, booktitle = {{arXiv:2411.04874}}, title = {{{Hardness of approximation for ground state problems}}}, year = {{2024}}, } @unpublished{56944, abstract = {{Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic Heisenberg model, is a QMA-complete problem relevant to quantum many-body physics and computer science. Semidefinite programming relaxations have been fruitful in designing theoretical approximation algorithms for QMC, but are computationally expensive for systems beyond tens of qubits. We give a second order cone relaxation for QMC, which optimizes over the set of mutually consistent three-qubit reduced density matrices. In combination with Pauli level-$1$ of the quantum Lasserre hierarchy, the relaxation achieves an approximation ratio of $0.526$ to the ground state energy. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.}}, author = {{Huber, Felix and Thompson, Kevin and Parekh, Ojas and Gharibian, Sevag}}, booktitle = {{arXiv:2411.04120}}, title = {{{Second order cone relaxations for quantum Max Cut}}}, year = {{2024}}, } @inproceedings{32407, abstract = {{Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with $6$-local Hamiltonians when the guiding vector has overlap (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the overlap parameters: we show that this quantum advantage (BQP-completeness) persists even with 2-local Hamiltonians, and even when the guiding vector has overlap (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the quantum advantage also holds for 2-local physically motivated Hamiltonians on a 2D square lattice. This makes a further step towards establishing practical quantum advantage in quantum chemistry.}}, author = {{Gharibian, Sevag and Hayakawa, Ryu and Gall, François Le and Morimae, Tomoyuki}}, booktitle = {{Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP)}}, number = {{32}}, pages = {{1--19}}, title = {{{Improved Hardness Results for the Guided Local Hamiltonian Problem}}}, doi = {{10.4230/LIPIcs.ICALP.2023.32}}, volume = {{261}}, year = {{2023}}, } @article{50271, author = {{Gharibian, Sevag and Le Gall, François}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, keywords = {{General Mathematics, General Computer Science}}, number = {{4}}, pages = {{1009--1038}}, publisher = {{Society for Industrial & Applied Mathematics (SIAM)}}, title = {{{Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}}}, doi = {{10.1137/22m1513721}}, volume = {{52}}, year = {{2023}}, } @inproceedings{31872, abstract = {{Savitch's theorem states that NPSPACE computations can be simulated in PSPACE. We initiate the study of a quantum analogue of NPSPACE, denoted Streaming-QCMASPACE (SQCMASPACE), where an exponentially long classical proof is streamed to a poly-space quantum verifier. Besides two main results, we also show that a quantum analogue of Savitch's theorem is unlikely to hold, as SQCMASPACE=NEXP. For completeness, we introduce Streaming-QMASPACE (SQMASPACE) with an exponentially long streamed quantum proof, and show SQMASPACE=QMA_EXP (quantum analogue of NEXP). Our first main result shows, in contrast to the classical setting, the solution space of a quantum constraint satisfaction problem (i.e. a local Hamiltonian) is always connected when exponentially long proofs are permitted. For this, we show how to simulate any Lipschitz continuous path on the unit hypersphere via a sequence of local unitary gates, at the expense of blowing up the circuit size. This shows quantum error-correcting codes can be unable to detect one codeword erroneously evolving to another if the evolution happens sufficiently slowly, and answers an open question of [Gharibian, Sikora, ICALP 2015] regarding the Ground State Connectivity problem. Our second main result is that any SQCMASPACE computation can be embedded into "unentanglement", i.e. into a quantum constraint satisfaction problem with unentangled provers. Formally, we show how to embed SQCMASPACE into the Sparse Separable Hamiltonian problem of [Chailloux, Sattath, CCC 2012] (QMA(2)-complete for 1/poly promise gap), at the expense of scaling the promise gap with the streamed proof size. As a corollary, we obtain the first systematic construction for obtaining QMA(2)-type upper bounds on arbitrary multi-prover interactive proof systems, where the QMA(2) promise gap scales exponentially with the number of bits of communication in the interactive proof.}}, author = {{Gharibian, Sevag and Rudolph, Dorian}}, booktitle = {{14th Innovations in Theoretical Computer Science (ITCS)}}, pages = {{53:1--53:23}}, title = {{{Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement}}}, doi = {{10.4230/LIPIcs.ITCS.2023.53}}, volume = {{251}}, year = {{2023}}, } @inproceedings{20841, author = {{Gharibian, Sevag and Watson, James and Bausch, Johannes}}, booktitle = {{Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS)}}, pages = {{54:1--54:21}}, title = {{{The Complexity of Translationally Invariant Problems beyond Ground State Energies}}}, doi = {{https://doi.org/10.4230/LIPIcs.STACS.2023.54}}, volume = {{254}}, year = {{2023}}, } @inproceedings{34138, abstract = {{Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the depth of the variational ansatz used - the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. This potential for depth reduction has made VQAs a staple of Noisy Intermediate-Scale Quantum (NISQ)-era research. In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that for any constant $\epsilon>0$, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor $N^{1-\epsilon}$, for $N$ denoting the encoding size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP.) We then show that this hardness persists even in the "simpler" setting of QAOAs. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems. To achieve these results, we bypass the need for a PCP theorem for QCMA by appealing to the disperser-based NP-hardness of approximation construction of [Umans, FOCS 1999].}}, author = {{Bittel, Lennart and Gharibian, Sevag and Kliesch, Martin}}, booktitle = {{Proceedings of the 38th Computational Complexity Conference (CCC)}}, number = {{34}}, pages = {{34:1--34:24}}, title = {{{The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate}}}, doi = {{10.4230/LIPIcs.CCC.2023.34}}, volume = {{264}}, year = {{2023}}, } @inproceedings{27531, abstract = {{The Quantum Singular Value Transformation (QSVT) is a recent technique that gives a unified framework to describe most quantum algorithms discovered so far, and may lead to the development of novel quantum algorithms. In this paper we investigate the hardness of classically simulating the QSVT. A recent result by Chia, Gily\'en, Li, Lin, Tang and Wang (STOC 2020) showed that the QSVT can be efficiently "dequantized" for low-rank matrices, and discussed its implication to quantum machine learning. In this work, motivated by establishing the superiority of quantum algorithms for quantum chemistry and making progress on the quantum PCP conjecture, we focus on the other main class of matrices considered in applications of the QSVT, sparse matrices. We first show how to efficiently "dequantize", with arbitrarily small constant precision, the QSVT associated with a low-degree polynomial. We apply this technique to design classical algorithms that estimate, with constant precision, the singular values of a sparse matrix. We show in particular that a central computational problem considered by quantum algorithms for quantum chemistry (estimating the ground state energy of a local Hamiltonian when given, as an additional input, a state sufficiently close to the ground state) can be solved efficiently with constant precision on a classical computer. As a complementary result, we prove that with inverse-polynomial precision, the same problem becomes BQP-complete. This gives theoretical evidence for the superiority of quantum algorithms for chemistry, and strongly suggests that said superiority stems from the improved precision achievable in the quantum setting. We also discuss how this dequantization technique may help make progress on the central quantum PCP conjecture.}}, author = {{Gharibian, Sevag and Gall, François Le}}, booktitle = {{Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)}}, pages = {{19--32}}, title = {{{Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}}}, year = {{2022}}, } @article{34700, author = {{Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin}}, issn = {{1016-3328}}, journal = {{Computational Complexity}}, keywords = {{Computational Mathematics, Computational Theory and Mathematics, General Mathematics, Theoretical Computer Science}}, number = {{2}}, publisher = {{Springer Science and Business Media LLC}}, title = {{{Quantum generalizations of the polynomial hierarchy with applications to QMA(2)}}}, doi = {{10.1007/s00037-022-00231-8}}, volume = {{31}}, year = {{2022}}, } @inproceedings{27160, abstract = {{We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$ and $P^{QMA}$, respectively. The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate Simulation (APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by the classes $P^{NP[\log]}$ and $P^{QMA[\log]}$, defined identically to $P^{NP}$ and $P^{QMA}$, except that only logarithmically many oracle queries are allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by a $P^{NP}$ machine have a "query graph" which is a tree, then this computation can be simulated in $P^{NP[\log]}$. In this work, we first show that for any verification class $C\in\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\exp}\}$, any $P^C$ machine with a query graph of "separator number" $s$ can be simulated using deterministic time $\exp(s\log n)$ and $s\log n$ queries to a $C$-oracle. When $s\in O(1)$ (which includes the case of $O(1)$-treewidth, and thus also of trees), this gives an upper bound of $P^{C[\log]}$, and when $s\in O(\log^k(n))$, this yields bound $QP^{C[\log^{k+1}]}$ (QP meaning quasi-polynomial time). We next show how to combine Gottlob's "admissible-weighting function" framework with the "flag-qubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a unified approach for embedding $P^C$ computations directly into APX-SIM instances in a black-box fashion. Finally, we formalize a simple no-go statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear polynomial $p$ specified via an arithmetic circuit, if one can "weakly compress" $p$ so that its optimal value requires $m$ bits to represent, then $P^{NP}$ can be decided with only $m$ queries to an NP-oracle.}}, author = {{Gharibian, Sevag and Rudolph, Dorian}}, booktitle = {{13th Innovations in Theoretical Computer Science (ITCS 2022)}}, number = {{75}}, pages = {{1--27}}, title = {{{On polynomially many queries to NP or QMA oracles}}}, doi = {{10.4230/LIPIcs.ITCS.2022.75}}, volume = {{215}}, year = {{2022}}, } @article{29780, abstract = {{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 (i.e., 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.114n adaptive queries to the token (for n 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.}}, author = {{Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng}}, issn = {{2521-327X}}, journal = {{Quantum}}, keywords = {{Physics and Astronomy (miscellaneous), Atomic and Molecular Physics, and Optics}}, publisher = {{Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften}}, title = {{{Towards Quantum One-Time Memories from Stateless Hardware}}}, doi = {{10.22331/q-2021-04-08-429}}, volume = {{5}}, year = {{2021}}, } @inproceedings{13226, abstract = {{The canonical problem for the class Quantum Merlin-Arthur (QMA) is that of estimating ground state energies of local Hamiltonians. Perhaps surprisingly, [Ambainis, CCC 2014] showed that the related, but arguably more natural, problem of simulating local measurements on ground states of local Hamiltonians (APX-SIM) is likely harder than QMA. Indeed, [Ambainis, CCC 2014] showed that APX-SIM is P^QMA[log]-complete, for P^QMA[log] the class of languages decidable by a P machine making a logarithmic number of adaptive queries to a QMA oracle. In this work, we show that APX-SIM is P^QMA[log]-complete even when restricted to more physical Hamiltonians, obtaining as intermediate steps a variety of related complexity-theoretic results. We first give a sequence of results which together yield P^QMA[log]-hardness for APX-SIM on well-motivated Hamiltonians: (1) We show that for NP, StoqMA, and QMA oracles, a logarithmic number of adaptive queries is equivalent to polynomially many parallel queries. These equalities simplify the proofs of our subsequent results. (2) Next, we show that the hardness of APX-SIM is preserved under Hamiltonian simulations (a la [Cubitt, Montanaro, Piddock, 2017]). As a byproduct, we obtain a full complexity classification of APX-SIM, showing it is complete for P, P^||NP, P^||StoqMA, or P^||QMA depending on the Hamiltonians employed. (3) Leveraging the above, we show that APX-SIM is P^QMA[log]-complete for any family of Hamiltonians which can efficiently simulate spatially sparse Hamiltonians, including physically motivated models such as the 2D Heisenberg model. Our second focus considers 1D systems: We show that APX-SIM remains P^QMA[log]-complete even for local Hamiltonians on a 1D line of 8-dimensional qudits. This uses a number of ideas from above, along with replacing the "query Hamiltonian" of [Ambainis, CCC 2014] with a new "sifter" construction.}}, author = {{Gharibian, Sevag and Piddock, Stephen and Yirka, Justin}}, booktitle = {{Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)}}, pages = {{38}}, title = {{{Oracle complexity classes and local measurements on physical Hamiltonians}}}, year = {{2020}}, }