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.

翻译：我们研究单体属性测试,在这种测试中,量子算法可以查询黑箱单体,并且必须决定它是否满足某些属性。除了将标准量子查询复杂模型(其中单体编码二进制字符串)作为一个特例外,该模型还包含“内在量子”问题,没有古典类比。这些问题的质子复杂性要求采用新的算法技术和较低约束方法。我们的主要贡献是统一属性测试问题的普遍多数值方法。我们利用该方法来获取较低范围的问题,例如确定单体复发时间,接近一个标记的子空间的尺寸,和接近一个标记状态的缠绕。我们还对$\mathfsf ⁇ MA}美元和$\mathsf ⁇ ma(2)}美元之间的骨骼分离提出了一个基于单一属性测试的方法,这是量体复杂性理论中长期存在的问题。