Seminar by Yupan Liu, Hebrew University of Jerusalem (November 30, 2020)

Seminar by Yupan Liu, Hebrew University of Jerusalem 

Date: Monday, November 30, 2020
Time: 13:00 (JST) –
Venue: Zoom

Title: The untold story of StoqMA

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’s 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.