A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has large Hamming distance from all y in L. We define a similar notion of quantum property testing and show that there exist languages with quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.
展开▼
机译：语言 L 是否具有属性测试器，如果存在一种概率算法，该算法在给定输入 x 的情况下仅询问少量的 x 位并进行区分 x 是否在 L 中并且 x 与中所有 y 的汉明距离都很大的情况L 我们定义了类似的量子特性测试概念，并表明存在具有量子特性测试器但没有好的经典测试器的语言。我们还显示，即使对于量子测试，也存在需要大量查询的语言。
展开▼
