| Authors |
|
| Publication date |
2003
|
| Book title |
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
|
| Book subtitle |
SODA '03 : Baltimore, MD, January 12-13, 2003
|
| ISBN |
|
| Event |
14th ACM-SIAM symposium on discrete algorithms
|
| Pages (from-to) |
480-488
|
| Publisher |
New York: Association for Computing Machinery
|
| Organisations |
-
Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
|
| Abstract |
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.
|
| Document type |
Conference contribution
|
| Language |
English
|
| Published at |
https://dl.acm.org/doi/10.5555/644108.644188
|
|
Permalink to this page
|