Quantum property testing
| Authors |
|
|---|---|
| Publication date | 2008 |
| Journal | SIAM Journal on Computing |
| Volume | Issue number | 37 | 5 |
| Pages (from-to) | 1387-1400 |
| Organisations |
|
| Abstract | 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. |
| Document type | Article |
| Published at |
https://doi.org/10.1137/S0097539704442416
(Final published version)
|
| Downloads | |
| Permalink to this page | |