Search Results

Documents authored by Liu, Yupan


Document
StoqMA Meets Distribution Testing

Authors: Yupan Liu

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)


Abstract
StoqMA captures the computational hardness of approximating the ground energy of local Hamiltonians that do not suffer the so-called sign problem. We provide a novel connection between StoqMA and distribution testing via reversible circuits. First, we prove that easy-witness StoqMA (viz. eStoqMA, a sub-class of StoqMA) is contained in MA. Easy witness is a generalization of a subset state such that the associated set’s membership can be efficiently verifiable, and all non-zero coordinates are not necessarily uniform. This sub-class eStoqMA contains StoqMA with perfect completeness (StoqMA₁), which further signifies a simplified proof for StoqMA₁ ⊆ MA [Bravyi et al., 2006; Bravyi and Terhal, 2010]. Second, by showing distinguishing reversible circuits with ancillary random bits is StoqMA-complete (as a comparison, distinguishing quantum circuits is QMA-complete [Janzing et al., 2005]), we construct soundness error reduction of StoqMA. Additionally, we show that both variants of StoqMA that without any ancillary random bit and with perfect soundness are contained in NP. Our results make a step towards collapsing the hierarchy MA ⊆ StoqMA ⊆ SBP [Bravyi et al., 2006], in which all classes are contained in AM and collapse to NP under derandomization assumptions.

Cite as

Yupan Liu. StoqMA Meets Distribution Testing. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 4:1-4:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.TQC.2021.4,
  author =	{Liu, Yupan},
  title =	{{StoqMA Meets Distribution Testing}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.4},
  URN =		{urn:nbn:de:0030-drops-139995},
  doi =		{10.4230/LIPIcs.TQC.2021.4},
  annote =	{Keywords: StoqMA, distribution testing, error reduction, reversible circuits}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail