Properties of Quantum Languages

Guo Xiu-hong

Tensor product of two automata over the different alphabets is defined in this paper and quantum languages accepted by the tensor product are studied. Quantum languages and generalized quantum languages are discussed. Some of their properties are derived.

Stanley Gudder

Claudio Garola

Harry Buhrman, Lance Fortnow, Ilan Newman +1 more

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.

Yuxin Deng, Yuan Feng

Harry Buhrman, Lance Fortnow, Ilan Newman +1 more

A language $L$ has a property tester if there exists a probabilistic algorithm that given an input $x$ queries only 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 good 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.