摘要 Abstract
复杂性理论通常关注的是利用经典输入和输出解决计算问题的难度,即使是在量子计算机的情况下也是如此。在量子世界中,应用另一种复杂性概念——即合成量子态的复杂性——是自然的。我们研究了NP类的状态合成对应类stateQMA,它涉及通过一个多项式时间内量子验证器,借助来自全能但不可信证明者的单一量子消息来准备某些量子态。这是Rosenthal和Yuen(ITCS 2022)最近引入的stateQIP类的一个子类,该类允许证明者与验证器之间有多项式次交互。我们的主要结果包括对这个类及其具有指数级小间隙或有界空间的变体进行错误减少,以及这个类与其他基本状态合成类之间的关系,即由均匀多项式时间量子电路(stateBQP)和空间均匀多项式空间量子电路(statePSPACE)生成的状态。此外,我们证明了被认为是stateQMA包含最自然候选之一的UQMA见证集属于stateQMA。另外,我们还表明stateQCMA实现了完美的完备性。
Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it is natural to apply a different notion of complexity, namely the complexity of synthesizing quantum states. We investigate a state-synthesizing counterpart of the class NP, referred to as stateQMA, which is concerned with preparing certain quantum states through a polynomial-time quantum verifier with the aid of a single quantum message from an all-powerful but untrusted prover. This is a subclass of the class stateQIP recently introduced by Rosenthal and Yuen (ITCS 2022), which permits polynomially many interactions between the prover and the verifier. Our main result consists of error reduction of this class and its variants with an exponentially small gap or bounded space, as well as how this class relates to other fundamental state synthesizing classes, i.e., states generated by uniform polynomial-time quantum circuits (stateBQP) and space-uniform polynomial-space quantum circuits (statePSPACE). Furthermore, we establish that the family of UQMA witnesses, considered as one of the most natural candidates for stateQMA containments, is in stateQMA. Additionally, we demonstrate that stateQCMA achieves perfect completeness.