StoqMA meets distribution testing
share
𝖲𝗍𝗈𝗊𝖬𝖠 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 𝖲𝗍𝗈𝗊𝖬𝖠 and the distribution testing via reversible circuits. First, we prove that easy-witness 𝖲𝗍𝗈𝗊𝖬𝖠 (viz. 𝖾𝖲𝗍𝗈𝗊𝖬𝖠, a sub-class of 𝖲𝗍𝗈𝗊𝖬𝖠) is contained in 𝖬𝖠. 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. Second, by showing distinguishing reversible circuits with random ancillary bits is 𝖲𝗍𝗈𝗊𝖬𝖠-complete (as a comparison, distinguishing quantum circuits is 𝖰𝖬𝖠-complete [JWB05]), we construct soundness error reduction of 𝖲𝗍𝗈𝗊𝖬𝖠. This new 𝖲𝗍𝗈𝗊𝖬𝖠-complete problem further signifies that 𝖲𝗍𝗈𝗊𝖬𝖠 with perfect completeness (𝖲𝗍𝗈𝗊𝖬𝖠_1) is contained in 𝖾𝖲𝗍𝗈𝗊𝖬𝖠, which leads us to an alternating proof for 𝖲𝗍𝗈𝗊𝖬𝖠_1 ⊆𝖬𝖠 previously proved in [BBT06, BT10]. Additionally, we show that both variants of 𝖲𝗍𝗈𝗊𝖬𝖠 that without any random ancillary bit and with perfect soundness are contained in 𝖭𝖯. Our results make a step towards collapsing the hierarchy 𝖬𝖠⊆𝖲𝗍𝗈𝗊𝖬𝖠⊆𝖲𝖡𝖯 [BBT06], in which all classes are contained in 𝖠𝖬 and collapse to 𝖭𝖯 under derandomization assumptions.
READ FULL TEXT
