Quantum property testing
| 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 |
|
| 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
(Final published version)
|
| Permalink to this page | |