Loading...
Please wait, while we are loading the content...
Similar Documents
Quantum property testing (2003)
| Content Provider | CiteSeerX |
|---|---|
| Author | Newman, Ilan Röhrig, Hein Buhrman, Harry Fortnow, Lance |
| Description | In Proceedings of 14th SODA |
| 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. 1 |
| File Format | |
| Publisher Date | 2003-01-01 |
| Access Restriction | Open |
| Subject Keyword | Similar Notion Good Classical Tester Probabilistic Algorithm Property Tester Quantum Property Tester Quantum Property Testing Exist Language Quantum Property |
| Content Type | Text |
| Resource Type | Proceeding |
