标签：#复杂性理论

QMA

在计算复杂性理论中，QMA（，意为量子梅林-亚瑟）是一个复杂性类，它包含了这样一类决策问题：对于一个答案为“是”的实例，证明者（梅林）可以提供一个多项式大小的量子证明（一个量子态），使验证者（亚瑟）在多项式时间内能够以高概率确信其为“是”（这被称为完备性）；反之，对于答案为“否”的实例，任何证明都将以高概率被验证者拒绝（这被称为可靠性）。 QMA 与 BQP 的关系，可类比于经典复杂性类中 NP 与 P 的关系，以及概率复杂性类中 MA…