论文标题
多项式的统一财产测试下限
Unitary property testing lower bounds by polynomials
论文作者
论文摘要
我们研究了统一的财产测试，其中量子算法可以查询对黑盒统一的查询访问，并且必须决定是否满足某些财产。除了包含标准量子查询复杂性模型（单位编码二进制字符串）作为特殊情况外，该模型还包含没有经典类似物的“固有量子”问题。表征这些问题的查询复杂性需要新的算法技术和下限方法。 我们的主要贡献是用于统一财产测试问题的广义多项式方法。通过利用与不变理论的连接，我们应用此方法在诸如确定单位的复发时间，近似标记子空间的尺寸以及近似标记状态的纠缠熵之类的问题上获得下限。我们还提出了一种基于统一的属性测试方法，用于$ \ mathsf {qma} $和$ \ mathsf {qma（2）} $之间的甲骨文分离，这是量子复杂性理论的长期问题。
We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether it satisfies some property. In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum" problems that have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. Our main contribution is a generalized polynomial method for unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a marked subspace, and approximating the entanglement entropy of a marked state. We also present a unitary property testing-based approach towards an oracle separation between $\mathsf{QMA}$ and $\mathsf{QMA(2)}$, a long standing question in quantum complexity theory.
