<\/p>\n
Seminar by Yupan Liu, Hebrew University of Jerusalem<\/strong><\/p>\n \u958b\u50ac\u65e5\u6642\uff1a\u30002020\u5e7411\u670830\u65e5\uff08\u6708\uff09\u300013:00\uff5e Title: The untold story of StoqMA<\/p>\n Abstract: Stoq MA captures the computational hardness of approximating the ground energy of local Hamiltonians that do not suffer the so-called sign problem. In this talk, I will explain my recent results on StoqMA. First, StoqMA with easy witness (eStoqMA) is contained in MA, where easy witness is a non-uniform generalization of a subset state such that the associated set\u2019s membership can be efficiently verifiable. The proof follows from distribution testing techniques, which infers a simplified proof of StoqMA with perfect completeness is contained in MA [BBT06]. Second, by showing distinguishing reversible circuits with random ancillary bits is StoqMA-complete (as a comparison, distinguishing quantum circuits is QMA-complete [JWB03]), we construct a soundness error reduction of StoqMA. This new complete problem also signifies StoqMA with perfect soundness is contained in NP. Third, (completeness) error reduction of StoqMA would imply StoqMA=MA. These results make a step towards collapsing the hierarchy MA, StoqMA, SBP, in which all classes are contained in AM and collapse to NP under derandomization assumptions. These works (arxiv:2011.05733 and arxiv:2010.02835) are partially joint with Dorit Aharonov and Alex B. Grilo.<\/p>\n <\/p>","protected":false},"excerpt":{"rendered":" Seminar by Yupan Liu, Hebrew University of Jerusalem \u958b\u50ac\u65e5\u6642\uff1a\u30002020\u5e7411\u670830\u65e5\uff08\u6708\uff09\u300013:00\uff5e\u958b\u50ac\u5f62\u614b\uff1a\u3000Zoom Title: The untold s […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-173","post","type-post","status-publish","format-standard","hentry","category-events"],"_links":{"self":[{"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=\/wp\/v2\/posts\/173","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=173"}],"version-history":[{"count":8,"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=\/wp\/v2\/posts\/173\/revisions"}],"predecessor-version":[{"id":258,"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=\/wp\/v2\/posts\/173\/revisions\/258"}],"wp:attachment":[{"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=173"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=173"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www2.yukawa.kyoto-u.ac.jp\/~qiunit\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u958b\u50ac\u5f62\u614b\uff1a\u3000Zoom<\/p>\n