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