论文标题
STOQMA符合分配测试
StoqMA meets distribution testing
论文作者
论文摘要
$ \ Mathsf {stoqma} $捕获了近似于没有所谓的标志问题的当地汉密尔顿人的地面能量的计算硬度。我们在$ \ Mathsf {stoqma} $和通过可逆电路进行分配测试之间提供了新颖的连接。首先，我们证明了Easy-witness $ \ Mathsf {stoqma} $（viz。$ \ Mathsf {estoqma} $，$ \ Mathsf {stoqma} $的子级别包含在$ \ MATHSF {ma} $中。简单的见证人是对子集状态的概括，使得相关集的成员资格可以有效地验证，并且所有非零坐标不一定均匀。此子类$ \ Mathsf {estoqma} $包含$ \ MATHSF {StoQma} $，完整（$ \ m athsf {stoqma} _1 $），这进一步表示$ \ m atssf {stoqma} _1 _1 _1 _1 \ subseteq \ mathsss bb bb bb bb bb bb bb bb bb bb bb bb bb bb bbt baf {ma maths bav {ma mathss baf {ma maths baf {ma maths baksss bb bb bb bakss baf其次，通过显示具有辅助随机位的可逆电路是$ \ Mathsf {stoqma} $ - 完整（作为比较，区分量子电路为$ \ Mathsf {qma} $ - 完整[JWB05]），我们构建了减少$ \ m athsf {stoqma} $的声音误差。此外，我们证明了$ \ mathsf {stoqma} $的两个变体都没有任何辅助随机位，并且具有完美的声音都包含在$ \ mathsf {np} $中。我们的结果迈出了一步，迈出了折叠层次结构$ \ MATHSF {MA} \ subseteq \ MathSf {StoQMA} \ subseteq \ Mathsf {sbp} $ [bbt06]
$\mathsf{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 $\mathsf{StoqMA}$ and distribution testing via reversible circuits. First, we prove that easy-witness $\mathsf{StoqMA}$ (viz. $\mathsf{eStoqMA}$, a sub-class of $\mathsf{StoqMA}$) is contained in $\mathsf{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 $\mathsf{eStoqMA}$ contains $\mathsf{StoqMA}$ with perfect completeness ($\mathsf{StoqMA}_1$), which further signifies a simplified proof for $\mathsf{StoqMA}_1 \subseteq \mathsf{MA}$ [BBT06, BT10]. Second, by showing distinguishing reversible circuits with ancillary random bits is $\mathsf{StoqMA}$-complete (as a comparison, distinguishing quantum circuits is $\mathsf{QMA}$-complete [JWB05]), we construct soundness error reduction of $\mathsf{StoqMA}$. Additionally, we show that both variants of $\mathsf{StoqMA}$ that without any ancillary random bit and with perfect soundness are contained in $\mathsf{NP}$. Our results make a step towards collapsing the hierarchy $\mathsf{MA} \subseteq \mathsf{StoqMA} \subseteq \mathsf{SBP}$ [BBT06], in which all classes are contained in $\mathsf{AM}$ and collapse to $\mathsf{NP}$ under derandomization assumptions.
