@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}}, } @inproceedings{8426, 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, against a linear number of adaptive queries to the token, in the quantum universal composability framework. We prove stand-alone security against a malicious sender, but leave open the question of composable security against a malicious sender, as well as security against a malicious receiver making a polynomial number of adaptive 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 show our scheme is "tight" according to two scenarios.}}, author = {{Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng}}, booktitle = {{Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)}}, pages = {{6:1--6:25}}, publisher = {{Leibniz International Proceedings in Informatics (LIPIcs)}}, title = {{{Towards Quantum One-Time Memories from Stateless Hardware}}}, volume = {{158}}, year = {{2020}}, } @article{16927, author = {{Gharibian, Sevag and Aldi, Marco and de Beaudrap, Niel and Saeedi, Seyran}}, journal = {{Communications in Mathematical Physics}}, title = {{{On efficiently solvable cases of Quantum k-SAT}}}, year = {{2020}}, } @inproceedings{13297, author = {{Gharibian, Sevag and Parekh, Ojas}}, booktitle = {{Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}}, pages = {{31:1--31:17}}, title = {{{Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut}}}, doi = {{10.4230/LIPICS.APPROX-RANDOM.2019.31}}, volume = {{145}}, year = {{2019}}, } @article{13558, author = {{Gharibian, Sevag and Yirka, Justin }}, journal = {{Quantum}}, pages = {{189}}, title = {{{The complexity of simulating local measurements on quantum systems}}}, doi = {{10.22331/q-2019-09-30-189}}, volume = {{3}}, year = {{2019}}, } @inproceedings{8162, abstract = {{The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere.}}, author = {{Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran}}, booktitle = {{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}}, editor = {{Potapov, Igor and Spirakis, Paul and Worrell, James}}, keywords = {{search complexity, local Hamiltonian, Quantum SAT, algebraic geometry}}, location = {{Liverpool, UK}}, pages = {{38:1--38:16}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}}, title = {{{On Efficiently Solvable Cases of Quantum k-SAT}}}, doi = {{10.4230/LIPIcs.MFCS.2018.38}}, volume = {{117}}, year = {{2018}}, } @inproceedings{8161, abstract = {{The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH does not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, QCPH, uses classical proofs, and the second, QPH, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, Q Sigma_3, into NEXP using the Ellipsoid Method for efficiently solving semidefinite programs. These results yield two implications for QMA(2), the variant of Quantum Merlin-Arthur (QMA) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs "equivalent"), then QMA(2) is in the Counting Hierarchy (specifically, in P^{PP^{PP}}). Second, unless QMA(2)= Q Sigma_3 (i.e., alternating quantifiers do not help in the presence of "unentanglement"), QMA(2) is strictly contained in NEXP.}}, author = {{Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin}}, booktitle = {{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}}, editor = {{Potapov, Igor and Spirakis, Paul and Worrell, James}}, keywords = {{Complexity Theory, Quantum Computing, Polynomial Hierarchy, Semidefinite Programming, QMA(2), Quantum Complexity}}, location = {{Liverpool, UK}}, pages = {{58:1--58:16}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}}, title = {{{Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)}}}, doi = {{10.4230/LIPIcs.MFCS.2018.58}}, volume = {{117}}, year = {{2018}}, } @inproceedings{8160, abstract = {{An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, Ambainis defined the complexity class P^QMA[log], and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the study of P^QMA[log], obtaining the following results. The P^QMA[log]-completeness result of Ambainis requires O(log n)-local observ- ables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete, resolving an open question of Ambainis. We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly P^QMA[log]-complete. P^QMA[log] is thought of as "slightly harder" than QMA. We justify this formally by exploiting the hierarchical voting technique of Beigel, Hemachandra, and Wechsung to show P^QMA[log] \subseteq PP. This improves the containment QMA \subseteq PP from Kitaev and Watrous. A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, we identify a flaw in Ambainis' prior work regarding a P^UQMA[log]-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a "query validation" technique, we build on his prior work to obtain P^UQMA[log]-hardness for estimating spectral gaps under polynomial-time Turing reductions.}}, author = {{Gharibian, Sevag and Yirka, Justin}}, booktitle = {{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)}}, editor = {{Wilde, Mark}}, keywords = {{Complexity theory, Quantum Merlin Arthur (QMA), local Hamiltonian, local measurement, spectral gap}}, location = {{Paris, France}}, pages = {{2:1--2:17}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}}, title = {{{The Complexity of Simulating Local Measurements on Quantum Systems}}}, doi = {{10.4230/LIPIcs.TQC.2017.2}}, volume = {{73}}, year = {{2018}}, } @article{8167, author = {{Gharibian, Sevag and Sikora, Jamie}}, issn = {{1942-3454}}, journal = {{ACM Transactions on Computation Theory (TOCT)}}, keywords = {{Local Hamiltonian, ground state connectivity, quantum Hamiltonian complexity, reconfiguration problem}}, number = {{2}}, pages = {{8:1--8:28}}, publisher = {{ACM}}, title = {{{Ground State Connectivity of Local Hamiltonians}}}, doi = {{10.1145/3186587}}, volume = {{10}}, year = {{2018}}, } @inproceedings{8159, abstract = {{The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].}}, author = {{de Beaudrap, Niel and Gharibian, Sevag}}, booktitle = {{Proceedings of the 31st Conference on Computational Complexity (CCC 2016)}}, editor = {{Raz, Ran}}, isbn = {{978-3-95977-008-8}}, keywords = {{quantum 2-SAT, transfer matrix, strongly connected components, limited backtracking, local Hamiltonian}}, location = {{Tokyo, Japan}}, pages = {{27:1--17:21}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}}, title = {{{A Linear Time Algorithm for Quantum 2-SAT}}}, doi = {{10.4230/LIPIcs.CCC.2016.27}}, volume = {{50}}, year = {{2016}}, } @inproceedings{8164, abstract = {{The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this paper, we take a new direction by introducing the physically motivated notion of ``ground state connectivity'' of local Hamiltonians, which captures problems in areas ranging from quantum stabilizer codes to quantum memories. We show that determining how ``connected'' the ground space of a local Hamiltonian is can range from QCMA-complete to PSPACE-complete, as well as NEXP-complete for an appropriately defined ``succinct'' version of the problem. As a result, we obtain a natural QCMA-complete problem, a goal which has generally proven difficult since the conception of QCMA over a decade ago. Our proofs rely on a new technical tool, the Traversal Lemma, which analyzes the Hilbert space a local unitary evolution must traverse under certain conditions. We show that this lemma is essentially tight with respect to the length of the unitary evolution in question.}}, author = {{Gharibian, Sevag and Sikora, Jamie}}, booktitle = {{International Colloquium on Automata, Languages, and Programming (ICALP 2015)}}, editor = {{Halld{\'o}rsson, Magn{\'u}s M. and Iwama, Kazuo and Kobayashi, Naoki and Speckmann, Bettina}}, isbn = {{978-3-662-47672-7}}, location = {{Kyoto, Japan}}, pages = {{617--628}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{Ground State Connectivity of Local Hamiltonians}}}, doi = {{10.1007/978-3-662-47672-7_50}}, year = {{2015}}, } @article{8166, abstract = {{Constraint satisfaction problems are a central pillar of modern computational complexity theory. This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint satisfaction problems. Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a “Quantum Cook-Levin Theorem” to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws. Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field. As such, we include the following in this survey: (1) The motivations and history of the field, (2) a glossary of condensed matter physics terms explained in computer-science friendly language, (3) overviews of central ideas from condensed matter physics, such as indistinguishable particles, mean field theory, tensor networks, and area laws, and (4) brief expositions of selected computer science-based results in the area. For example, as part of the latter, we provide a novel information theoretic presentation of Bravyi’s polynomial time algorithm for Quantum 2-SAT.}}, author = {{Gharibian, Sevag and Huang, Yichen and Landau, Zeph and Woo Shin, Seung}}, issn = {{1551-305X}}, journal = {{Foundations and Trends® in Theoretical Computer Science}}, number = {{3}}, pages = {{159--282}}, title = {{{Quantum Hamiltonian Complexity}}}, doi = {{10.1561/0400000066}}, volume = {{10}}, year = {{2015}}, } @article{8168, abstract = {{Tensor networks are a central tool in condensed matter physics. In this paper, we initiate the study of tensor network non-zero testing (TNZ): Given a tensor network T, does T represent a non-zero vector? We show that TNZ is not in the Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among other results) that the special cases of TNZ on non-negative and injective tensor networks are in NP. Using this, we make a simple observation: The commuting variant of the MA-complete stoquastic k-SAT problem on D-dimensional qudits is in NP for logarithmic k and constant D. This reveals the first class of quantum Hamiltonians whose commuting variant is known to be in NP for all (1) logarithmic k, (2) constant D, and (3) for arbitrary interaction graphs. }}, author = {{Gharibian, Sevag and Landau, Zeph and Woo Shin, Seung and Wang, Guoming}}, journal = {{Quantum Information & Computation}}, number = {{9{\&}10}}, pages = {{885--899}}, title = {{{Tensor network non-zero testing}}}, volume = {{15}}, year = {{2015}}, } @article{8171, abstract = {{The polynomial hierarchy plays a central role in classical complexity theory. Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999]. The problems for which we prove hardness of approximation for include, among others, a quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian problem with hybrid classical-quantum ground states.}}, author = {{Gharibian, Sevag and Kempe, Julia}}, journal = {{Quantum Information & Computation}}, keywords = {{Hardness of approximation, polynomial time hierarchy, succinct set cover, quantum complexity}}, number = {{5-6}}, pages = {{517--540}}, title = {{{Hardness of approximation for quantum problems}}}, volume = {{14}}, year = {{2014}}, } @article{8172, abstract = {{We show how to efficiently simulate continuous-time quantum query algorithms that run in time T in a manner that preserves the query complexity (within a polylogarithmic factor) while also incurring a small overhead cost in the total number of gates between queries. By small overhead, we mean T within a factor that is polylogarithmic in terms of T and a cost measure that reflects the cost of computing the driving Hamiltonian. This permits any continuous-time quantum algorithm based on an efficiently computable driving Hamiltonian to be converted into a gate-efficient algorithm with similar running time.}}, author = {{W. Berry, Dominic and Cleve, Richard and Gharibian, Sevag}}, journal = {{Quantum Information & Computation}}, number = {{1-2}}, pages = {{1--30}}, title = {{{Gate-efficient discrete simulations of continuous-time quantum query algorithms}}}, volume = {{14}}, year = {{2014}}, } @phdthesis{8425, abstract = {{This thesis studies three topics in quantum computation and information: The approximability of quantum problems, quantum proof systems, and non-classical correlations in quantum systems. In the first area, we demonstrate a polynomial-time (classical) approximation algorithm for dense instances of the canonical QMA-complete quantum constraint satisfaction problem, the local Hamiltonian problem. In the opposite direction, we next introduce a quantum generalization of the polynomial-time hierarchy, and define problems which we prove are not only complete for the second level of this hierarchy, but are in fact hard to approximate. In the second area, we study variants of the interesting and stubbornly open question of whether a quantum proof system with multiple unentangled quantum provers is equal in expressive power to a proof system with a single quantum prover. Our results concern classes such as BellQMA(poly), and include a novel proof of perfect parallel repetition for SepQMA(m) based on cone programming duality. In the third area, we study non-classical quantum correlations beyond entanglement, often dubbed "non-classicality". Among our results are two novel schemes for quantifying non-classicality: The first proposes the new paradigm of exploiting local unitary operations to study non-classical correlations, and the second introduces a protocol through which non-classical correlations in a starting system can be "activated" into distillable entanglement with an ancilla system. An introduction to all required linear algebra and quantum mechanics is included.}}, author = {{Gharibian, Sevag}}, pages = {{240}}, title = {{{Approximation, Proof Systems, and Correlations in a Quantum World}}}, year = {{2013}}, } @article{8173, abstract = {{We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly MQA (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class BellQMA(poly), characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly QMA. Finally, we study a class equivalent to QMA(m), denoted SepQMA(m), where the verifier's measurement operator corresponding to outcome "accept" is a fully separable operator across the m quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for SepQMA(m) for any m.}}, author = {{Gharibian, Sevag and Sikora, Jamie and Upadhyay, Sarvagya}}, journal = {{Quantum Information & Computation}}, number = {{1-2}}, pages = {{135--157}}, title = {{{QMA variants with polynomially many provers}}}, volume = {{13}}, year = {{2013}}, } @inproceedings{8169, abstract = {{The polynomial hierarchy plays a central role in classical complexity theory. Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Our work thus yields the first known hardness of approximation results for a quantum complexity class. Using these techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy (Umans 1999). We close by showing that a variant of the local Hamiltonian problem with hybrid classical-quantum ground states is complete for the second level of our quantum hierarchy.}}, author = {{Gharibian, Sevag and Kempe, Julia}}, booktitle = {{International Colloquium on Automata, Languages, and Programming (ICALP 2012)}}, editor = {{Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger}}, isbn = {{978-3-642-31594-7}}, location = {{Warwick, UK}}, pages = {{387--398}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{Hardness of Approximation for Quantum Problems}}}, doi = {{10.1007/978-3-642-31594-7_33}}, year = {{2012}}, }