[{"publication_status":"published","publication_identifier":{"unknown":["978-3-95977-034-7"]},"place":"Dagstuhl, Germany","citation":{"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>","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>.","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>.","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)} }","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>.","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.","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>"},"intvolume":"        73","page":"2:1-2:17","date_updated":"2023-02-28T11:00:48Z","oa":"1","author":[{"first_name":"Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","id":"71541","full_name":"Gharibian, Sevag"},{"first_name":"Justin","last_name":"Yirka","full_name":"Yirka, Justin"}],"volume":73,"main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8577"}],"conference":{"location":"Paris, France","name":"12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)"},"doi":"10.4230/LIPIcs.TQC.2017.2","type":"conference","editor":[{"full_name":"Wilde, Mark","last_name":"Wilde","first_name":"Mark"}],"status":"public","_id":"8160","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","user_id":"71541","department":[{"_id":"623"},{"_id":"7"}],"year":"2018","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","date_created":"2019-03-01T11:25:27Z","title":"The Complexity of Simulating Local Measurements on Quantum Systems","publication":"12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)","abstract":[{"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.","lang":"eng"}],"external_id":{"arxiv":["1606.05626"]},"keyword":["Complexity theory","Quantum Merlin Arthur (QMA)","local Hamiltonian","local measurement","spectral gap"],"language":[{"iso":"eng"}]}]