[{"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."}],"publication":"13th Innovations in Theoretical Computer Science (ITCS 2022)","issue":"75","type":"conference","department":[{"_id":"623"},{"_id":"7"}],"date_created":"2021-11-05T08:08:29Z","date_updated":"2026-04-30T14:11:00Z","intvolume":"       215","title":"On polynomially many queries to NP or QMA oracles","year":"2022","author":[{"first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541"},{"id":"57863","full_name":"Rudolph, Dorian","last_name":"Rudolph","first_name":"Dorian"}],"doi":"10.4230/LIPIcs.ITCS.2022.75","main_file_link":[{"open_access":"1","url":"https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15671"}],"language":[{"iso":"eng"}],"citation":{"mla":"Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.” <i>13th Innovations in Theoretical Computer Science (ITCS 2022)</i>, vol. 215, no. 75, 2022, pp. 1–27, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">10.4230/LIPIcs.ITCS.2022.75</a>.","ama":"Gharibian S, Rudolph D. On polynomially many queries to NP or QMA oracles. In: <i>13th Innovations in Theoretical Computer Science (ITCS 2022)</i>. Vol 215. ; 2022:1-27. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">10.4230/LIPIcs.ITCS.2022.75</a>","bibtex":"@inproceedings{Gharibian_Rudolph_2022, title={On polynomially many queries to NP or QMA oracles}, volume={215}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">10.4230/LIPIcs.ITCS.2022.75</a>}, number={75}, booktitle={13th Innovations in Theoretical Computer Science (ITCS 2022)}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2022}, pages={1–27} }","apa":"Gharibian, S., &#38; Rudolph, D. (2022). On polynomially many queries to NP or QMA oracles. <i>13th Innovations in Theoretical Computer Science (ITCS 2022)</i>, <i>215</i>(75), 1–27. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">https://doi.org/10.4230/LIPIcs.ITCS.2022.75</a>","ieee":"S. Gharibian and D. Rudolph, “On polynomially many queries to NP or QMA oracles,” in <i>13th Innovations in Theoretical Computer Science (ITCS 2022)</i>, 2022, vol. 215, no. 75, pp. 1–27, doi: <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2022.75\">10.4230/LIPIcs.ITCS.2022.75</a>.","short":"S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science (ITCS 2022), 2022, pp. 1–27.","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>."},"oa":"1","status":"public","user_id":"71541","volume":215,"page":"1-27","_id":"27160"},{"citation":{"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>","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>.","short":"A. Broadbent, S. Gharibian, H.-S. Zhou, Quantum 5 (2021).","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} }","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>"},"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","_id":"29780","volume":5,"user_id":"71541","status":"public","date_created":"2022-02-08T10:59:00Z","department":[{"_id":"623"},{"_id":"7"}],"type":"journal_article","keyword":["Physics and Astronomy (miscellaneous)","Atomic and Molecular Physics","and Optics"],"publication":"Quantum","abstract":[{"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>","lang":"eng"}],"language":[{"iso":"eng"}],"article_number":"429","doi":"10.22331/q-2021-04-08-429","author":[{"full_name":"Broadbent, Anne","last_name":"Broadbent","first_name":"Anne"},{"orcid":"0000-0002-9992-3379","first_name":"Sevag","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541"},{"full_name":"Zhou, Hong-Sheng","first_name":"Hong-Sheng","last_name":"Zhou"}],"publication_identifier":{"issn":["2521-327X"]},"title":"Towards Quantum One-Time Memories from Stateless Hardware","year":"2021","intvolume":"         5","publication_status":"published","date_updated":"2023-02-28T11:07:47Z"},{"oa":"1","department":[{"_id":"623"},{"_id":"7"}],"type":"conference","date_created":"2019-09-16T07:41:31Z","external_id":{"arxiv":["1909.05981"]},"abstract":[{"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.","lang":"eng"}],"citation":{"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} }","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.","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.","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.","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."},"publication":"Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)","user_id":"71541","_id":"13226","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1909.05981","open_access":"1"}],"page":"38","date_updated":"2023-10-09T04:17:41Z","publication_status":"published","author":[{"id":"71541","full_name":"Gharibian, Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","first_name":"Sevag"},{"full_name":"Piddock, Stephen","first_name":"Stephen","last_name":"Piddock"},{"full_name":"Yirka, Justin","first_name":"Justin","last_name":"Yirka"}],"status":"public","title":"Oracle complexity classes and local measurements on physical  Hamiltonians","year":"2020"},{"author":[{"last_name":"Broadbent","first_name":"Anne","full_name":"Broadbent, Anne"},{"id":"71541","full_name":"Gharibian, Sevag","last_name":"Gharibian","first_name":"Sevag","orcid":"0000-0002-9992-3379"},{"first_name":"Hong-Sheng","last_name":"Zhou","full_name":"Zhou, Hong-Sheng"}],"year":"2020","title":"Towards Quantum One-Time Memories from Stateless Hardware","intvolume":"       158","date_updated":"2023-02-28T10:59:55Z","publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1810.05226"}],"publication":"Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)","abstract":[{"text":"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. \r\n\r\nHere, 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.","lang":"eng"}],"date_created":"2019-03-06T14:37:09Z","department":[{"_id":"623"},{"_id":"7"}],"type":"conference","status":"public","_id":"8426","publisher":"Leibniz International Proceedings in Informatics (LIPIcs)","page":"6:1-6:25","volume":158,"user_id":"71541","citation":{"mla":"Broadbent, Anne, et al. “Towards Quantum One-Time Memories from Stateless Hardware.” <i>Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)</i>, vol. 158, Leibniz International Proceedings in Informatics (LIPIcs), 2020, p. 6:1-6:25.","bibtex":"@inproceedings{Broadbent_Gharibian_Zhou_2020, title={Towards Quantum One-Time Memories from Stateless Hardware}, volume={158}, booktitle={Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)}, publisher={Leibniz International Proceedings in Informatics (LIPIcs)}, author={Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng}, year={2020}, pages={6:1-6:25} }","ama":"Broadbent A, Gharibian S, Zhou H-S. Towards Quantum One-Time Memories from Stateless Hardware. In: <i>Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)</i>. Vol 158. Leibniz International Proceedings in Informatics (LIPIcs); 2020:6:1-6:25.","ieee":"A. Broadbent, S. Gharibian, and H.-S. Zhou, “Towards Quantum One-Time Memories from Stateless Hardware,” in <i>Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)</i>, 2020, vol. 158, p. 6:1-6:25.","apa":"Broadbent, A., Gharibian, S., &#38; Zhou, H.-S. (2020). Towards Quantum One-Time Memories from Stateless Hardware. <i>Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)</i>, <i>158</i>, 6:1-6:25.","short":"A. Broadbent, S. Gharibian, H.-S. Zhou, in: Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), Leibniz International Proceedings in Informatics (LIPIcs), 2020, p. 6:1-6:25.","chicago":"Broadbent, Anne, Sevag Gharibian, and Hong-Sheng Zhou. “Towards Quantum One-Time Memories from Stateless Hardware.” In <i>Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)</i>, 158:6:1-6:25. Leibniz International Proceedings in Informatics (LIPIcs), 2020."},"external_id":{"arxiv":["1810.05226"]}},{"user_id":"71541","language":[{"iso":"eng"}],"_id":"16927","main_file_link":[{"url":"https://doi.org/10.1007/s00220-020-03843-9","open_access":"1"}],"publication_status":"published","date_updated":"2023-02-28T11:05:17Z","author":[{"id":"71541","last_name":"Gharibian","first_name":"Sevag","orcid":"0000-0002-9992-3379","full_name":"Gharibian, Sevag"},{"full_name":"Aldi, Marco","last_name":"Aldi","first_name":"Marco"},{"first_name":"Niel","last_name":"de Beaudrap","full_name":"de Beaudrap, Niel"},{"last_name":"Saeedi","first_name":"Seyran","full_name":"Saeedi, Seyran"}],"status":"public","title":"On efficiently solvable cases of Quantum k-SAT","year":"2020","department":[{"_id":"623"},{"_id":"7"}],"oa":"1","type":"journal_article","date_created":"2020-04-30T07:12:00Z","external_id":{"arxiv":["1712.09617"]},"citation":{"apa":"Gharibian, S., Aldi, M., de Beaudrap, N., &#38; Saeedi, S. (2020). On efficiently solvable cases of Quantum k-SAT. <i>Communications in Mathematical Physics</i>.","ieee":"S. Gharibian, M. Aldi, N. de Beaudrap, and S. Saeedi, “On efficiently solvable cases of Quantum k-SAT,” <i>Communications in Mathematical Physics</i>, 2020.","chicago":"Gharibian, Sevag, Marco Aldi, Niel de Beaudrap, and Seyran Saeedi. “On Efficiently Solvable Cases of Quantum K-SAT.” <i>Communications in Mathematical Physics</i>, 2020.","short":"S. Gharibian, M. Aldi, N. de Beaudrap, S. Saeedi, Communications in Mathematical Physics (2020).","mla":"Gharibian, Sevag, et al. “On Efficiently Solvable Cases of Quantum K-SAT.” <i>Communications in Mathematical Physics</i>, 2020.","ama":"Gharibian S, Aldi M, de Beaudrap N, Saeedi S. On efficiently solvable cases of Quantum k-SAT. <i>Communications in Mathematical Physics</i>. Published online 2020.","bibtex":"@article{Gharibian_Aldi_de Beaudrap_Saeedi_2020, title={On efficiently solvable cases of Quantum k-SAT}, journal={Communications in Mathematical Physics}, author={Gharibian, Sevag and Aldi, Marco and de Beaudrap, Niel and Saeedi, Seyran}, year={2020} }"},"publication":"Communications in Mathematical Physics"},{"citation":{"mla":"Gharibian, Sevag, and Ojas Parekh. “Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut.” <i>Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>, vol. 145, 2019, p. 31:1-31:17, doi:<a href=\"https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31\">10.4230/LIPICS.APPROX-RANDOM.2019.31</a>.","bibtex":"@inproceedings{Gharibian_Parekh_2019, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut}, volume={145}, DOI={<a href=\"https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31\">10.4230/LIPICS.APPROX-RANDOM.2019.31</a>}, booktitle={Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, author={Gharibian, Sevag and Parekh, Ojas}, year={2019}, pages={31:1-31:17}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","ama":"Gharibian S, Parekh O. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. In: <i>Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>. Vol 145. Leibniz International Proceedings in Informatics (LIPIcs). ; 2019:31:1-31:17. doi:<a href=\"https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31\">10.4230/LIPICS.APPROX-RANDOM.2019.31</a>","ieee":"S. Gharibian and O. Parekh, “Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut,” in <i>Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>, 2019, vol. 145, p. 31:1-31:17, doi: <a href=\"https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31\">10.4230/LIPICS.APPROX-RANDOM.2019.31</a>.","apa":"Gharibian, S., &#38; Parekh, O. (2019). Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. <i>Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>, <i>145</i>, 31:1-31:17. <a href=\"https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31\">https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31</a>","short":"S. Gharibian, O. Parekh, in: Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2019, p. 31:1-31:17.","chicago":"Gharibian, Sevag, and Ojas Parekh. “Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut.” In <i>Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>, 145:31:1-31:17. Leibniz International Proceedings in Informatics (LIPIcs), 2019. <a href=\"https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31\">https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31</a>."},"oa":"1","status":"public","user_id":"71541","volume":145,"page":"31:1-31:17","_id":"13297","publication":"Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","type":"conference","department":[{"_id":"623"},{"_id":"7"}],"date_created":"2019-09-19T08:33:29Z","publication_status":"published","date_updated":"2023-02-28T11:05:46Z","intvolume":"       145","title":"Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut","year":"2019","author":[{"id":"71541","last_name":"Gharibian","first_name":"Sevag","orcid":"0000-0002-9992-3379","full_name":"Gharibian, Sevag"},{"full_name":"Parekh, Ojas","first_name":"Ojas","last_name":"Parekh"}],"doi":"10.4230/LIPICS.APPROX-RANDOM.2019.31","main_file_link":[{"url":"http://drops.dagstuhl.de/opus/volltexte/2019/11246/","open_access":"1"}],"language":[{"iso":"eng"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)"},{"type":"journal_article","oa":"1","department":[{"_id":"623"},{"_id":"7"}],"date_created":"2019-10-01T08:25:27Z","publication":"Quantum","citation":{"bibtex":"@article{Gharibian_Yirka_2019, title={The complexity of simulating local measurements on quantum systems}, volume={3}, DOI={<a href=\"https://doi.org/10.22331/q-2019-09-30-189\">10.22331/q-2019-09-30-189</a>}, journal={Quantum}, author={Gharibian, Sevag and Yirka, Justin }, year={2019}, pages={189} }","ama":"Gharibian S, Yirka J. The complexity of simulating local measurements on quantum systems. <i>Quantum</i>. 2019;3:189. doi:<a href=\"https://doi.org/10.22331/q-2019-09-30-189\">10.22331/q-2019-09-30-189</a>","mla":"Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” <i>Quantum</i>, vol. 3, 2019, p. 189, doi:<a href=\"https://doi.org/10.22331/q-2019-09-30-189\">10.22331/q-2019-09-30-189</a>.","chicago":"Gharibian, Sevag, and Justin  Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” <i>Quantum</i> 3 (2019): 189. <a href=\"https://doi.org/10.22331/q-2019-09-30-189\">https://doi.org/10.22331/q-2019-09-30-189</a>.","short":"S. Gharibian, J. Yirka, Quantum 3 (2019) 189.","ieee":"S. Gharibian and J. Yirka, “The complexity of simulating local measurements on quantum systems,” <i>Quantum</i>, vol. 3, p. 189, 2019, doi: <a href=\"https://doi.org/10.22331/q-2019-09-30-189\">10.22331/q-2019-09-30-189</a>.","apa":"Gharibian, S., &#38; Yirka, J. (2019). The complexity of simulating local measurements on quantum systems. <i>Quantum</i>, <i>3</i>, 189. <a href=\"https://doi.org/10.22331/q-2019-09-30-189\">https://doi.org/10.22331/q-2019-09-30-189</a>"},"doi":"10.22331/q-2019-09-30-189","user_id":"71541","volume":3,"main_file_link":[{"url":"https://quantum-journal.org/papers/q-2019-09-30-189/","open_access":"1"}],"page":"189","_id":"13558","language":[{"iso":"eng"}],"date_updated":"2023-02-28T11:05:35Z","publication_status":"published","intvolume":"         3","status":"public","title":"The complexity of simulating local measurements on quantum systems","year":"2019","author":[{"orcid":"0000-0002-9992-3379","first_name":"Sevag","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541"},{"full_name":"Yirka, Justin ","first_name":"Justin ","last_name":"Yirka"}]},{"citation":{"ama":"Aldi M, de Beaudrap N, Gharibian S, Saeedi S. On Efficiently Solvable Cases of Quantum k-SAT. In: Potapov I, Spirakis P, Worrell J, eds. <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>. Vol 117. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:38:1-38:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">10.4230/LIPIcs.MFCS.2018.38</a>","bibtex":"@inproceedings{Aldi_de Beaudrap_Gharibian_Saeedi_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={On Efficiently Solvable Cases of Quantum k-SAT}, volume={117}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">10.4230/LIPIcs.MFCS.2018.38</a>}, booktitle={43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran}, editor={Potapov, Igor and Spirakis, Paul and Worrell, James}, year={2018}, pages={38:1-38:16}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","mla":"Aldi, Marco, et al. “On Efficiently Solvable Cases of Quantum K-SAT.” <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>, edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 38:1-38:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">10.4230/LIPIcs.MFCS.2018.38</a>.","chicago":"Aldi, Marco, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi. “On Efficiently Solvable Cases of Quantum K-SAT.” In <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>, edited by Igor Potapov, Paul Spirakis, and James Worrell, 117:38:1-38:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">https://doi.org/10.4230/LIPIcs.MFCS.2018.38</a>.","short":"M. Aldi, N. de Beaudrap, S. Gharibian, S. Saeedi, in: I. Potapov, P. Spirakis, J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 38:1-38:16.","apa":"Aldi, M., de Beaudrap, N., Gharibian, S., &#38; Saeedi, S. (2018). On Efficiently Solvable Cases of Quantum k-SAT. In I. Potapov, P. Spirakis, &#38; J. Worrell (Eds.), <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i> (Vol. 117, p. 38:1-38:16). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">https://doi.org/10.4230/LIPIcs.MFCS.2018.38</a>","ieee":"M. Aldi, N. de Beaudrap, S. Gharibian, and S. Saeedi, “On Efficiently Solvable Cases of Quantum k-SAT,” in <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>, Liverpool, UK, 2018, vol. 117, p. 38:1-38:16, doi: <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">10.4230/LIPIcs.MFCS.2018.38</a>."},"place":"Dagstuhl, Germany","external_id":{"arxiv":["1712.09617"]},"oa":"1","conference":{"location":"Liverpool, UK","name":"43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)"},"status":"public","_id":"8162","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","page":"38:1-38:16","volume":117,"editor":[{"full_name":"Potapov, Igor","first_name":"Igor","last_name":"Potapov"},{"full_name":"Spirakis, Paul","last_name":"Spirakis","first_name":"Paul"},{"last_name":"Worrell","first_name":"James","full_name":"Worrell, James"}],"user_id":"71541","publication":"43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)","abstract":[{"text":"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.","lang":"eng"}],"date_created":"2019-03-01T11:34:41Z","department":[{"_id":"623"},{"_id":"7"}],"keyword":["search complexity","local Hamiltonian","Quantum SAT","algebraic geometry"],"type":"conference","publication_identifier":{"unknown":["978-3-95977-086-6"]},"author":[{"first_name":"Marco","last_name":"Aldi","full_name":"Aldi, Marco"},{"full_name":"de Beaudrap, Niel","last_name":"de Beaudrap","first_name":"Niel"},{"orcid":"0000-0002-9992-3379","first_name":"Sevag","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541"},{"first_name":"Seyran","last_name":"Saeedi","full_name":"Saeedi, Seyran"}],"title":"On Efficiently Solvable Cases of Quantum k-SAT","year":"2018","intvolume":"       117","publication_status":"published","date_updated":"2023-02-28T11:01:16Z","language":[{"iso":"eng"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","main_file_link":[{"url":"http://drops.dagstuhl.de/opus/volltexte/2018/9620/","open_access":"1"}],"doi":"10.4230/LIPIcs.MFCS.2018.38"},{"oa":"1","place":"Dagstuhl, Germany","external_id":{"arxiv":["1805.11139"]},"citation":{"ieee":"S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka, “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2),” in <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>, Liverpool, UK, 2018, vol. 117, p. 58:1-58:16, doi: <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.58\">10.4230/LIPIcs.MFCS.2018.58</a>.","apa":"Gharibian, S., Santha, M., Sikora, J., Sundaram, A., &#38; Yirka, J. (2018). Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In I. Potapov, P. Spirakis, &#38; J. Worrell (Eds.), <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i> (Vol. 117, p. 58:1-58:16). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.58\">https://doi.org/10.4230/LIPIcs.MFCS.2018.58</a>","short":"S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, in: I. Potapov, P. Spirakis, J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 58:1-58:16.","chicago":"Gharibian, Sevag, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” In <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>, edited by Igor Potapov, Paul Spirakis, and James Worrell, 117:58:1-58:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.58\">https://doi.org/10.4230/LIPIcs.MFCS.2018.58</a>.","mla":"Gharibian, Sevag, et al. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).” <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>, edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 58:1-58:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.58\">10.4230/LIPIcs.MFCS.2018.58</a>.","bibtex":"@inproceedings{Gharibian_Santha_Sikora_Sundaram_Yirka_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)}, volume={117}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.58\">10.4230/LIPIcs.MFCS.2018.58</a>}, booktitle={43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin}, editor={Potapov, Igor and Spirakis, Paul and Worrell, James}, year={2018}, pages={58:1-58:16}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","ama":"Gharibian S, Santha M, Sikora J, Sundaram A, Yirka J. Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In: Potapov I, Spirakis P, Worrell J, eds. <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>. Vol 117. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:58:1-58:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.58\">10.4230/LIPIcs.MFCS.2018.58</a>"},"volume":117,"editor":[{"first_name":"Igor","last_name":"Potapov","full_name":"Potapov, Igor"},{"first_name":"Paul","last_name":"Spirakis","full_name":"Spirakis, Paul"},{"full_name":"Worrell, James","last_name":"Worrell","first_name":"James"}],"user_id":"71541","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","_id":"8161","page":"58:1-58:16","conference":{"location":"Liverpool, UK","name":"43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)"},"status":"public","department":[{"_id":"623"},{"_id":"7"}],"type":"conference","keyword":["Complexity Theory","Quantum Computing","Polynomial Hierarchy","Semidefinite Programming","QMA(2)","Quantum Complexity"],"date_created":"2019-03-01T11:29:44Z","abstract":[{"lang":"eng","text":"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."}],"publication":"43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)","doi":"10.4230/LIPIcs.MFCS.2018.58","language":[{"iso":"eng"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","main_file_link":[{"url":"http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=9640","open_access":"1"}],"intvolume":"       117","publication_status":"published","date_updated":"2023-02-28T11:01:03Z","publication_identifier":{"unknown":["978-3-95977-086-6"]},"author":[{"full_name":"Gharibian, Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","first_name":"Sevag","id":"71541"},{"last_name":"Santha","first_name":"Miklos","full_name":"Santha, Miklos"},{"first_name":"Jamie","last_name":"Sikora","full_name":"Sikora, Jamie"},{"full_name":"Sundaram, Aarthi","last_name":"Sundaram","first_name":"Aarthi"},{"full_name":"Yirka, Justin","first_name":"Justin","last_name":"Yirka"}],"title":"Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)","year":"2018"},{"status":"public","conference":{"location":"Paris, France","name":"12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)"},"page":"2:1-2:17","_id":"8160","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","user_id":"71541","volume":73,"editor":[{"full_name":"Wilde, Mark","first_name":"Mark","last_name":"Wilde"}],"citation":{"ieee":"S. Gharibian and J. Yirka, “The Complexity of Simulating Local Measurements on Quantum Systems,” in <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i>, Paris, France, 2018, vol. 73, p. 2:1-2:17, doi: <a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">10.4230/LIPIcs.TQC.2017.2</a>.","mla":"Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i>, edited by Mark Wilde, vol. 73, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 2:1-2:17, doi:<a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">10.4230/LIPIcs.TQC.2017.2</a>.","apa":"Gharibian, S., &#38; Yirka, J. (2018). The Complexity of Simulating Local Measurements on Quantum Systems. In M. Wilde (Ed.), <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i> (Vol. 73, p. 2:1-2:17). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">https://doi.org/10.4230/LIPIcs.TQC.2017.2</a>","bibtex":"@inproceedings{Gharibian_Yirka_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={The Complexity of Simulating Local Measurements on Quantum Systems}, volume={73}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">10.4230/LIPIcs.TQC.2017.2</a>}, booktitle={12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={Gharibian, Sevag and Yirka, Justin}, editor={Wilde, Mark}, year={2018}, pages={2:1-2:17}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","ama":"Gharibian S, Yirka J. The Complexity of Simulating Local Measurements on Quantum Systems. In: Wilde M, ed. <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i>. Vol 73. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:2:1-2:17. doi:<a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">10.4230/LIPIcs.TQC.2017.2</a>","short":"S. Gharibian, J. Yirka, in: M. Wilde (Ed.), 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 2:1-2:17.","chicago":"Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” In <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i>, edited by Mark Wilde, 73:2:1-2:17. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">https://doi.org/10.4230/LIPIcs.TQC.2017.2</a>."},"external_id":{"arxiv":["1606.05626"]},"place":"Dagstuhl, Germany","oa":"1","title":"The Complexity of Simulating Local Measurements on Quantum Systems","year":"2018","publication_identifier":{"unknown":["978-3-95977-034-7"]},"author":[{"id":"71541","full_name":"Gharibian, Sevag","first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian"},{"last_name":"Yirka","first_name":"Justin","full_name":"Yirka, Justin"}],"publication_status":"published","date_updated":"2023-02-28T11:00:48Z","intvolume":"        73","main_file_link":[{"url":"http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8577","open_access":"1"}],"language":[{"iso":"eng"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","doi":"10.4230/LIPIcs.TQC.2017.2","publication":"12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)","abstract":[{"lang":"eng","text":"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."}],"date_created":"2019-03-01T11:25:27Z","keyword":["Complexity theory","Quantum Merlin Arthur (QMA)","local Hamiltonian","local measurement","spectral gap"],"type":"conference","department":[{"_id":"623"},{"_id":"7"}]},{"doi":"10.1145/3186587","main_file_link":[{"url":"https://arxiv.org/abs/1409.3182","open_access":"1"}],"language":[{"iso":"eng"}],"publication_status":"published","date_updated":"2023-02-28T11:01:36Z","intvolume":"        10","year":"2018","title":"Ground State Connectivity of Local Hamiltonians","author":[{"last_name":"Gharibian","first_name":"Sevag","orcid":"0000-0002-9992-3379","full_name":"Gharibian, Sevag","id":"71541"},{"last_name":"Sikora","first_name":"Jamie","full_name":"Sikora, Jamie"}],"publication_identifier":{"issn":["1942-3454"]},"type":"journal_article","keyword":["Local Hamiltonian","ground state connectivity","quantum Hamiltonian complexity","reconfiguration problem"],"department":[{"_id":"623"},{"_id":"7"}],"date_created":"2019-03-01T11:49:31Z","issue":"2","publication":"ACM Transactions on Computation Theory (TOCT)","user_id":"71541","volume":10,"page":"8:1-8:28","publisher":"ACM","_id":"8167","status":"public","oa":"1","external_id":{"arxiv":["1409.3182"]},"citation":{"chicago":"Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” <i>ACM Transactions on Computation Theory (TOCT)</i> 10, no. 2 (2018): 8:1-8:28. <a href=\"https://doi.org/10.1145/3186587\">https://doi.org/10.1145/3186587</a>.","short":"S. Gharibian, J. Sikora, ACM Transactions on Computation Theory (TOCT) 10 (2018) 8:1-8:28.","ieee":"S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,” <i>ACM Transactions on Computation Theory (TOCT)</i>, vol. 10, no. 2, p. 8:1-8:28, 2018, doi: <a href=\"https://doi.org/10.1145/3186587\">10.1145/3186587</a>.","apa":"Gharibian, S., &#38; Sikora, J. (2018). Ground State Connectivity of Local Hamiltonians. <i>ACM Transactions on Computation Theory (TOCT)</i>, <i>10</i>(2), 8:1-8:28. <a href=\"https://doi.org/10.1145/3186587\">https://doi.org/10.1145/3186587</a>","bibtex":"@article{Gharibian_Sikora_2018, title={Ground State Connectivity of Local Hamiltonians}, volume={10}, DOI={<a href=\"https://doi.org/10.1145/3186587\">10.1145/3186587</a>}, number={2}, journal={ACM Transactions on Computation Theory (TOCT)}, publisher={ACM}, author={Gharibian, Sevag and Sikora, Jamie}, year={2018}, pages={8:1-8:28} }","ama":"Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. <i>ACM Transactions on Computation Theory (TOCT)</i>. 2018;10(2):8:1-8:28. doi:<a href=\"https://doi.org/10.1145/3186587\">10.1145/3186587</a>","mla":"Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” <i>ACM Transactions on Computation Theory (TOCT)</i>, vol. 10, no. 2, ACM, 2018, p. 8:1-8:28, doi:<a href=\"https://doi.org/10.1145/3186587\">10.1145/3186587</a>."}},{"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/volltexte/2016/5836/"}],"doi":"10.4230/LIPIcs.CCC.2016.27","author":[{"full_name":"de Beaudrap, Niel","first_name":"Niel","last_name":"de Beaudrap"},{"id":"71541","last_name":"Gharibian","first_name":"Sevag","orcid":"0000-0002-9992-3379","full_name":"Gharibian, Sevag"}],"publication_identifier":{"isbn":["978-3-95977-008-8"]},"title":"A Linear Time Algorithm for Quantum 2-SAT","year":"2016","intvolume":"        50","publication_status":"published","date_updated":"2023-02-28T11:01:53Z","date_created":"2019-03-01T11:19:54Z","department":[{"_id":"623"},{"_id":"7"}],"type":"conference","keyword":["quantum 2-SAT","transfer matrix","strongly connected components","limited backtracking","local Hamiltonian"],"publication":"Proceedings of the 31st Conference on Computational Complexity (CCC 2016)","extern":"1","abstract":[{"text":"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].","lang":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","_id":"8159","page":"27:1-17:21","volume":50,"editor":[{"full_name":"Raz, Ran","last_name":"Raz","first_name":"Ran"}],"user_id":"71541","conference":{"name":"31st Conference on Computational Complexity (CCC 2016)","location":"Tokyo, Japan"},"status":"public","place":"Dagstuhl, Germany","external_id":{"arxiv":["1508.07338"]},"oa":"1","citation":{"ieee":"N. de Beaudrap and S. Gharibian, “A Linear Time Algorithm for Quantum 2-SAT,” in <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>, Tokyo, Japan, 2016, vol. 50, p. 27:1–17:21, doi: <a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">10.4230/LIPIcs.CCC.2016.27</a>.","apa":"de Beaudrap, N., &#38; Gharibian, S. (2016). A Linear Time Algorithm for Quantum 2-SAT. In R. Raz (Ed.), <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i> (Vol. 50, p. 27:1-17:21). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">https://doi.org/10.4230/LIPIcs.CCC.2016.27</a>","mla":"de Beaudrap, Niel, and Sevag Gharibian. “A Linear Time Algorithm for Quantum 2-SAT.” <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>, edited by Ran Raz, vol. 50, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, p. 27:1-17:21, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">10.4230/LIPIcs.CCC.2016.27</a>.","bibtex":"@inproceedings{de Beaudrap_Gharibian_2016, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={A Linear Time Algorithm for Quantum 2-SAT}, volume={50}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">10.4230/LIPIcs.CCC.2016.27</a>}, booktitle={Proceedings of the 31st Conference on Computational Complexity (CCC 2016)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={de Beaudrap, Niel and Gharibian, Sevag}, editor={Raz, Ran}, year={2016}, pages={27:1–17:21}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","chicago":"Beaudrap, Niel de, and Sevag Gharibian. “A Linear Time Algorithm for Quantum 2-SAT.” In <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>, edited by Ran Raz, 50:27:1-17:21. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">https://doi.org/10.4230/LIPIcs.CCC.2016.27</a>.","ama":"de Beaudrap N, Gharibian S. A Linear Time Algorithm for Quantum 2-SAT. In: Raz R, ed. <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>. Vol 50. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2016:27:1-17:21. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">10.4230/LIPIcs.CCC.2016.27</a>","short":"N. de Beaudrap, S. Gharibian, in: R. Raz (Ed.), Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016, p. 27:1–17:21."}},{"date_created":"2019-03-01T11:37:54Z","department":[{"_id":"623"},{"_id":"7"}],"type":"conference","publication":"International Colloquium on Automata, Languages, and Programming (ICALP 2015)","abstract":[{"text":"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.","lang":"eng"}],"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1409.3182"}],"doi":"10.1007/978-3-662-47672-7_50","publication_identifier":{"isbn":["978-3-662-47672-7"]},"author":[{"id":"71541","full_name":"Gharibian, Sevag","orcid":"0000-0002-9992-3379","first_name":"Sevag","last_name":"Gharibian"},{"first_name":"Jamie","last_name":"Sikora","full_name":"Sikora, Jamie"}],"year":"2015","title":"Ground State Connectivity of Local Hamiltonians","publication_status":"published","date_updated":"2023-02-28T11:02:07Z","place":"Berlin, Heidelberg","external_id":{"arxiv":["1409.3182"]},"oa":"1","citation":{"bibtex":"@inproceedings{Gharibian_Sikora_2015, place={Berlin, Heidelberg}, title={Ground State Connectivity of Local Hamiltonians}, DOI={<a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">10.1007/978-3-662-47672-7_50</a>}, booktitle={International Colloquium on Automata, Languages, and Programming (ICALP 2015)}, publisher={Springer Berlin Heidelberg}, author={Gharibian, Sevag and Sikora, Jamie}, editor={Halld{\\’o}rsson, Magn{\\’u}s M. and Iwama, Kazuo and Kobayashi, Naoki and Speckmann, Bettina}, year={2015}, pages={617–628} }","chicago":"Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” In <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i>, edited by Magn{\\’u}s M. Halld{\\’o}rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, 617–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">https://doi.org/10.1007/978-3-662-47672-7_50</a>.","short":"S. Gharibian, J. Sikora, in: M.M. Halld{\\’o}rsson, K. Iwama, N. Kobayashi, B. Speckmann (Eds.), International Colloquium on Automata, Languages, and Programming (ICALP 2015), Springer Berlin Heidelberg, Berlin, Heidelberg, 2015, pp. 617–628.","ama":"Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. In: Halld{\\’o}rsson MM, Iwama K, Kobayashi N, Speckmann B, eds. <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i>. Springer Berlin Heidelberg; 2015:617-628. doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">10.1007/978-3-662-47672-7_50</a>","ieee":"S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,” in <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i>, Kyoto, Japan, 2015, pp. 617–628, doi: <a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">10.1007/978-3-662-47672-7_50</a>.","mla":"Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i>, edited by Magn{\\’u}s M. Halld{\\’o}rsson et al., Springer Berlin Heidelberg, 2015, pp. 617–28, doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">10.1007/978-3-662-47672-7_50</a>.","apa":"Gharibian, S., &#38; Sikora, J. (2015). Ground State Connectivity of Local Hamiltonians. In M. M. Halld{\\’o}rsson, K. Iwama, N. Kobayashi, &#38; B. Speckmann (Eds.), <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i> (pp. 617–628). Springer Berlin Heidelberg. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">https://doi.org/10.1007/978-3-662-47672-7_50</a>"},"_id":"8164","publisher":"Springer Berlin Heidelberg","page":"617-628","editor":[{"full_name":"Halld{\\'o}rsson, Magn{\\'u}s M.","last_name":"Halld{\\'o}rsson","first_name":"Magn{\\'u}s M."},{"full_name":"Iwama, Kazuo","last_name":"Iwama","first_name":"Kazuo"},{"full_name":"Kobayashi, Naoki","last_name":"Kobayashi","first_name":"Naoki"},{"full_name":"Speckmann, Bettina","first_name":"Bettina","last_name":"Speckmann"}],"user_id":"71541","conference":{"name":"International Colloquium on Automata, Languages, and Programming (ICALP)","location":"Kyoto, Japan"},"status":"public"},{"status":"public","volume":10,"user_id":"71541","_id":"8166","page":"159-282","citation":{"mla":"Gharibian, Sevag, et al. “Quantum Hamiltonian Complexity.” <i>Foundations and Trends® in Theoretical Computer Science</i>, vol. 10, no. 3, 2015, pp. 159–282, doi:<a href=\"https://doi.org/10.1561/0400000066\">10.1561/0400000066</a>.","bibtex":"@article{Gharibian_Huang_Landau_Woo Shin_2015, title={Quantum Hamiltonian Complexity}, volume={10}, DOI={<a href=\"https://doi.org/10.1561/0400000066\">10.1561/0400000066</a>}, number={3}, journal={Foundations and Trends® in Theoretical Computer Science}, author={Gharibian, Sevag and Huang, Yichen and Landau, Zeph and Woo Shin, Seung}, year={2015}, pages={159–282} }","ama":"Gharibian S, Huang Y, Landau Z, Woo Shin S. Quantum Hamiltonian Complexity. <i>Foundations and Trends® in Theoretical Computer Science</i>. 2015;10(3):159-282. doi:<a href=\"https://doi.org/10.1561/0400000066\">10.1561/0400000066</a>","ieee":"S. Gharibian, Y. Huang, Z. Landau, and S. Woo Shin, “Quantum Hamiltonian Complexity,” <i>Foundations and Trends® in Theoretical Computer Science</i>, vol. 10, no. 3, pp. 159–282, 2015, doi: <a href=\"https://doi.org/10.1561/0400000066\">10.1561/0400000066</a>.","apa":"Gharibian, S., Huang, Y., Landau, Z., &#38; Woo Shin, S. (2015). Quantum Hamiltonian Complexity. <i>Foundations and Trends® in Theoretical Computer Science</i>, <i>10</i>(3), 159–282. <a href=\"https://doi.org/10.1561/0400000066\">https://doi.org/10.1561/0400000066</a>","chicago":"Gharibian, Sevag, Yichen Huang, Zeph Landau, and Seung Woo Shin. “Quantum Hamiltonian Complexity.” <i>Foundations and Trends® in Theoretical Computer Science</i> 10, no. 3 (2015): 159–282. <a href=\"https://doi.org/10.1561/0400000066\">https://doi.org/10.1561/0400000066</a>.","short":"S. Gharibian, Y. Huang, Z. Landau, S. Woo Shin, Foundations and Trends® in Theoretical Computer Science 10 (2015) 159–282."},"oa":"1","external_id":{"arxiv":["1401.3916"]},"article_type":"review","intvolume":"        10","publication_status":"published","date_updated":"2023-02-28T11:02:21Z","publication_identifier":{"issn":["1551-305X"]},"author":[{"orcid":"0000-0002-9992-3379","last_name":"Gharibian","first_name":"Sevag","full_name":"Gharibian, Sevag","id":"71541"},{"first_name":"Yichen","last_name":"Huang","full_name":"Huang, Yichen"},{"full_name":"Landau, Zeph","last_name":"Landau","first_name":"Zeph"},{"full_name":"Woo Shin, Seung","first_name":"Seung","last_name":"Woo Shin"}],"title":"Quantum Hamiltonian Complexity","year":"2015","doi":"10.1561/0400000066","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1401.3916","open_access":"1"}],"extern":"1","abstract":[{"text":"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.","lang":"eng"}],"publication":"Foundations and Trends® in Theoretical Computer Science","issue":"3","department":[{"_id":"623"},{"_id":"7"}],"type":"journal_article","date_created":"2019-03-01T11:45:40Z"},{"_id":"8168","page":"885-899","volume":15,"user_id":"71541","status":"public","external_id":{"arxiv":["1406.5279"]},"oa":"1","citation":{"bibtex":"@article{Gharibian_Landau_Woo Shin_Wang_2015, title={Tensor network non-zero testing}, volume={15}, number={9{\\ &#38; }10}, journal={Quantum Information &#38; Computation}, author={Gharibian, Sevag and Landau, Zeph and Woo Shin, Seung and Wang, Guoming}, year={2015}, pages={885–899} }","ama":"Gharibian S, Landau Z, Woo Shin S, Wang G. Tensor network non-zero testing. <i>Quantum Information &#38; Computation</i>. 2015;15(9{\\ &#38; }10):885-899.","mla":"Gharibian, Sevag, et al. “Tensor Network Non-Zero Testing.” <i>Quantum Information &#38; Computation</i>, vol. 15, no. 9{\\ &#38; }10, 2015, pp. 885–99.","short":"S. Gharibian, Z. Landau, S. Woo Shin, G. Wang, Quantum Information &#38; Computation 15 (2015) 885–899.","chicago":"Gharibian, Sevag, Zeph Landau, Seung Woo Shin, and Guoming Wang. “Tensor Network Non-Zero Testing.” <i>Quantum Information &#38; Computation</i> 15, no. 9{\\ &#38; }10 (2015): 885–99.","ieee":"S. Gharibian, Z. Landau, S. Woo Shin, and G. Wang, “Tensor network non-zero testing,” <i>Quantum Information &#38; Computation</i>, vol. 15, no. 9{\\ &#38; }10, pp. 885–899, 2015.","apa":"Gharibian, S., Landau, Z., Woo Shin, S., &#38; Wang, G. (2015). Tensor network non-zero testing. <i>Quantum Information &#38; Computation</i>, <i>15</i>(9{\\ &#38; }10), 885–899."},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1406.5279"}],"author":[{"id":"71541","full_name":"Gharibian, Sevag","first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379"},{"full_name":"Landau, Zeph","first_name":"Zeph","last_name":"Landau"},{"full_name":"Woo Shin, Seung","first_name":"Seung","last_name":"Woo Shin"},{"full_name":"Wang, Guoming","last_name":"Wang","first_name":"Guoming"}],"title":"Tensor network non-zero testing","year":"2015","intvolume":"        15","article_type":"original","date_updated":"2023-02-28T11:02:35Z","publication_status":"published","date_created":"2019-03-01T11:53:08Z","department":[{"_id":"623"},{"_id":"7"}],"type":"journal_article","publication":"Quantum Information & Computation","issue":"9{\\&}10","abstract":[{"lang":"eng","text":"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.\r\n"}],"extern":"1"},{"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1209.1055"}],"article_type":"original","intvolume":"        14","publication_status":"published","date_updated":"2023-02-28T11:02:47Z","author":[{"first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541"},{"full_name":"Kempe, Julia","last_name":"Kempe","first_name":"Julia"}],"year":"2014","title":"Hardness of approximation for quantum problems","department":[{"_id":"623"},{"_id":"7"}],"type":"journal_article","keyword":["Hardness of approximation","polynomial time hierarchy","succinct set cover","quantum complexity"],"date_created":"2019-03-01T11:56:55Z","extern":"1","abstract":[{"lang":"eng","text":"The polynomial hierarchy plays a central role in classical complexity theory. Here, we define\r\na quantum generalization of the polynomial hierarchy, and initiate its study. We show that\r\nnot 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\r\nalso obtain hardness of approximation for the class QCMA. Our approach is based on the\r\nuse 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].\r\nThe problems for which we prove hardness of approximation for include, among others, a\r\nquantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian\r\nproblem with hybrid classical-quantum ground states."}],"publication":"Quantum Information & Computation","issue":"5-6","volume":14,"user_id":"71541","_id":"8171","page":"517-540","status":"public","oa":"1","external_id":{"arxiv":["1209.1055"]},"citation":{"mla":"Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” <i>Quantum Information &#38; Computation</i>, vol. 14, no. 5–6, 2014, pp. 517–40.","bibtex":"@article{Gharibian_Kempe_2014, title={Hardness of approximation for quantum problems}, volume={14}, number={5–6}, journal={Quantum Information &#38; Computation}, author={Gharibian, Sevag and Kempe, Julia}, year={2014}, pages={517–540} }","ama":"Gharibian S, Kempe J. Hardness of approximation for quantum problems. <i>Quantum Information &#38; Computation</i>. 2014;14(5-6):517-540.","ieee":"S. Gharibian and J. Kempe, “Hardness of approximation for quantum problems,” <i>Quantum Information &#38; Computation</i>, vol. 14, no. 5–6, pp. 517–540, 2014.","apa":"Gharibian, S., &#38; Kempe, J. (2014). Hardness of approximation for quantum problems. <i>Quantum Information &#38; Computation</i>, <i>14</i>(5–6), 517–540.","chicago":"Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” <i>Quantum Information &#38; Computation</i> 14, no. 5–6 (2014): 517–40.","short":"S. Gharibian, J. Kempe, Quantum Information &#38; Computation 14 (2014) 517–540."}},{"citation":{"apa":"W. Berry, D., Cleve, R., &#38; Gharibian, S. (2014). Gate-efficient discrete simulations of continuous-time quantum query algorithms. <i>Quantum Information &#38; Computation</i>, <i>14</i>(1–2), 1–30.","mla":"W. Berry, Dominic, et al. “Gate-Efficient Discrete Simulations of Continuous-Time Quantum Query Algorithms.” <i>Quantum Information &#38; Computation</i>, vol. 14, no. 1–2, 2014, pp. 1–30.","ieee":"D. W. Berry, R. Cleve, and S. Gharibian, “Gate-efficient discrete simulations of continuous-time quantum query algorithms,” <i>Quantum Information &#38; Computation</i>, vol. 14, no. 1–2, pp. 1–30, 2014.","chicago":"W. Berry, Dominic, Richard Cleve, and Sevag Gharibian. “Gate-Efficient Discrete Simulations of Continuous-Time Quantum Query Algorithms.” <i>Quantum Information &#38; Computation</i> 14, no. 1–2 (2014): 1–30.","short":"D. W. Berry, R. Cleve, S. Gharibian, Quantum Information &#38; Computation 14 (2014) 1–30.","ama":"W. Berry D, Cleve R, Gharibian S. Gate-efficient discrete simulations of continuous-time quantum query algorithms. <i>Quantum Information &#38; Computation</i>. 2014;14(1-2):1-30.","bibtex":"@article{W. Berry_Cleve_Gharibian_2014, title={Gate-efficient discrete simulations of continuous-time quantum query algorithms}, volume={14}, number={1–2}, journal={Quantum Information &#38; Computation}, author={W. Berry, Dominic and Cleve, Richard and Gharibian, Sevag}, year={2014}, pages={1–30} }"},"external_id":{"arxiv":["1211.4637"]},"oa":"1","status":"public","_id":"8172","page":"1-30","volume":14,"user_id":"71541","publication":"Quantum Information & Computation","issue":"1-2","extern":"1","abstract":[{"text":"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.","lang":"eng"}],"date_created":"2019-03-01T11:59:24Z","department":[{"_id":"623"},{"_id":"7"}],"type":"journal_article","author":[{"full_name":"W. Berry, Dominic","first_name":"Dominic","last_name":"W. Berry"},{"last_name":"Cleve","first_name":"Richard","full_name":"Cleve, Richard"},{"first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541"}],"year":"2014","title":"Gate-efficient discrete simulations of continuous-time quantum query algorithms","article_type":"original","intvolume":"        14","publication_status":"published","date_updated":"2023-02-28T11:02:58Z","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1211.4637"}]},{"language":[{"iso":"eng"}],"_id":"8425","page":"240","main_file_link":[{"open_access":"1"}],"user_id":"71541","author":[{"full_name":"Gharibian, Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","first_name":"Sevag","id":"71541"}],"status":"public","title":"Approximation, Proof Systems, and Correlations in a Quantum World","year":"2013","date_updated":"2023-02-28T11:00:15Z","date_created":"2019-03-06T14:35:06Z","external_id":{"arxiv":["1301.2632"]},"department":[{"_id":"623"},{"_id":"7"}],"oa":"1","type":"dissertation","citation":{"short":"S. Gharibian, Approximation, Proof Systems, and Correlations in a Quantum World, 2013.","chicago":"Gharibian, Sevag. <i>Approximation, Proof Systems, and Correlations in a Quantum World</i>, 2013.","ieee":"S. Gharibian, <i>Approximation, Proof Systems, and Correlations in a Quantum World</i>. 2013.","apa":"Gharibian, S. (2013). <i>Approximation, Proof Systems, and Correlations in a Quantum World</i>.","bibtex":"@book{Gharibian_2013, title={Approximation, Proof Systems, and Correlations in a Quantum World}, author={Gharibian, Sevag}, year={2013} }","ama":"Gharibian S. <i>Approximation, Proof Systems, and Correlations in a Quantum World</i>.; 2013.","mla":"Gharibian, Sevag. <i>Approximation, Proof Systems, and Correlations in a Quantum World</i>. 2013."},"extern":"1","related_material":{"link":[{"relation":"confirmation","url":"https://arxiv.org/abs/1301.2632"}]},"abstract":[{"lang":"eng","text":"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. \r\n\r\nIn 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. \r\n\r\nIn 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. \r\n\r\nIn 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. \r\n\r\nAn introduction to all required linear algebra and quantum mechanics is included."}]},{"status":"public","_id":"8173","page":"135-157","volume":13,"user_id":"71541","citation":{"bibtex":"@article{Gharibian_Sikora_Upadhyay_2013, title={QMA variants with polynomially many provers}, volume={13}, number={1–2}, journal={Quantum Information &#38; Computation}, author={Gharibian, Sevag and Sikora, Jamie and Upadhyay, Sarvagya}, year={2013}, pages={135–157} }","ama":"Gharibian S, Sikora J, Upadhyay S. QMA variants with polynomially many provers. <i>Quantum Information &#38; Computation</i>. 2013;13(1-2):135-157.","mla":"Gharibian, Sevag, et al. “QMA Variants with Polynomially Many Provers.” <i>Quantum Information &#38; Computation</i>, vol. 13, no. 1–2, 2013, pp. 135–57.","short":"S. Gharibian, J. Sikora, S. Upadhyay, Quantum Information &#38; Computation 13 (2013) 135–157.","chicago":"Gharibian, Sevag, Jamie Sikora, and Sarvagya Upadhyay. “QMA Variants with Polynomially Many Provers.” <i>Quantum Information &#38; Computation</i> 13, no. 1–2 (2013): 135–57.","ieee":"S. Gharibian, J. Sikora, and S. Upadhyay, “QMA variants with polynomially many provers,” <i>Quantum Information &#38; Computation</i>, vol. 13, no. 1–2, pp. 135–157, 2013.","apa":"Gharibian, S., Sikora, J., &#38; Upadhyay, S. (2013). QMA variants with polynomially many provers. <i>Quantum Information &#38; Computation</i>, <i>13</i>(1–2), 135–157."},"external_id":{"arxiv":["1108.0617"]},"oa":"1","author":[{"full_name":"Gharibian, Sevag","first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","id":"71541"},{"first_name":"Jamie","last_name":"Sikora","full_name":"Sikora, Jamie"},{"full_name":"Upadhyay, Sarvagya","first_name":"Sarvagya","last_name":"Upadhyay"}],"year":"2013","title":"QMA variants with polynomially many provers","intvolume":"        13","article_type":"original","date_updated":"2023-02-28T11:03:13Z","publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1108.0617","open_access":"1"}],"issue":"1-2","publication":"Quantum Information & Computation","abstract":[{"text":"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.","lang":"eng"}],"extern":"1","date_created":"2019-03-01T12:00:39Z","department":[{"_id":"623"},{"_id":"7"}],"type":"journal_article"},{"publication_status":"published","date_updated":"2023-02-28T11:03:26Z","publication_identifier":{"isbn":["978-3-642-31594-7"]},"author":[{"full_name":"Gharibian, Sevag","orcid":"0000-0002-9992-3379","first_name":"Sevag","last_name":"Gharibian","id":"71541"},{"first_name":"Julia","last_name":"Kempe","full_name":"Kempe, Julia"}],"year":"2012","title":"Hardness of Approximation for Quantum Problems","doi":"10.1007/978-3-642-31594-7_33","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1209.1055"}],"extern":"1","abstract":[{"lang":"eng","text":"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."}],"publication":"International Colloquium on Automata, Languages, and Programming (ICALP 2012)","department":[{"_id":"623"},{"_id":"7"}],"type":"conference","date_created":"2019-03-01T11:55:18Z","conference":{"location":"Warwick, UK","name":"International Colloquium on Automata, Languages, and Programming (ICALP)"},"status":"public","editor":[{"last_name":"Czumaj","first_name":"Artur","full_name":"Czumaj, Artur"},{"first_name":"Kurt","last_name":"Mehlhorn","full_name":"Mehlhorn, Kurt"},{"full_name":"Pitts, Andrew","first_name":"Andrew","last_name":"Pitts"},{"full_name":"Wattenhofer, Roger","first_name":"Roger","last_name":"Wattenhofer"}],"user_id":"71541","publisher":"Springer Berlin Heidelberg","_id":"8169","page":"387-398","citation":{"ieee":"S. Gharibian and J. Kempe, “Hardness of Approximation for Quantum Problems,” in <i>International Colloquium on Automata, Languages, and Programming (ICALP 2012)</i>, Warwick, UK, 2012, pp. 387–398, doi: <a href=\"https://doi.org/10.1007/978-3-642-31594-7_33\">10.1007/978-3-642-31594-7_33</a>.","apa":"Gharibian, S., &#38; Kempe, J. (2012). Hardness of Approximation for Quantum Problems. In A. Czumaj, K. Mehlhorn, A. Pitts, &#38; R. Wattenhofer (Eds.), <i>International Colloquium on Automata, Languages, and Programming (ICALP 2012)</i> (pp. 387–398). Springer Berlin Heidelberg. <a href=\"https://doi.org/10.1007/978-3-642-31594-7_33\">https://doi.org/10.1007/978-3-642-31594-7_33</a>","short":"S. Gharibian, J. Kempe, in: A. Czumaj, K. Mehlhorn, A. Pitts, R. Wattenhofer (Eds.), International Colloquium on Automata, Languages, and Programming (ICALP 2012), Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 387–398.","chicago":"Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” In <i>International Colloquium on Automata, Languages, and Programming (ICALP 2012)</i>, edited by Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, 387–98. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. <a href=\"https://doi.org/10.1007/978-3-642-31594-7_33\">https://doi.org/10.1007/978-3-642-31594-7_33</a>.","mla":"Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” <i>International Colloquium on Automata, Languages, and Programming (ICALP 2012)</i>, edited by Artur Czumaj et al., Springer Berlin Heidelberg, 2012, pp. 387–98, doi:<a href=\"https://doi.org/10.1007/978-3-642-31594-7_33\">10.1007/978-3-642-31594-7_33</a>.","bibtex":"@inproceedings{Gharibian_Kempe_2012, place={Berlin, Heidelberg}, title={Hardness of Approximation for Quantum Problems}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-31594-7_33\">10.1007/978-3-642-31594-7_33</a>}, booktitle={International Colloquium on Automata, Languages, and Programming (ICALP 2012)}, publisher={Springer Berlin Heidelberg}, author={Gharibian, Sevag and Kempe, Julia}, editor={Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew and Wattenhofer, Roger}, year={2012}, pages={387–398} }","ama":"Gharibian S, Kempe J. Hardness of Approximation for Quantum Problems. In: Czumaj A, Mehlhorn K, Pitts A, Wattenhofer R, eds. <i>International Colloquium on Automata, Languages, and Programming (ICALP 2012)</i>. Springer Berlin Heidelberg; 2012:387-398. doi:<a href=\"https://doi.org/10.1007/978-3-642-31594-7_33\">10.1007/978-3-642-31594-7_33</a>"},"oa":"1","place":"Berlin, Heidelberg","external_id":{"arxiv":["1209.1055"]}}]