preprint · ArXiv.org · 2002

Quantum Property Testing

Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Roehrig

Cited by 1Open access

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.

Cite this paper

APA 7

Buhrman, H., Fortnow, L., Newman, I., & Roehrig, H. (2002). Quantum Property Testing. ArXiv.org. https://doi.org/10.48550/arxiv.quant-ph/0201117

MLA 9

Buhrman, Harry, et al. “Quantum Property Testing.” ArXiv.org, 2002, https://doi.org/10.48550/arxiv.quant-ph/0201117.

Chicago

Buhrman, Harry, Lance Fortnow, Ilan Newman, and Hein Roehrig. 2002. “Quantum Property Testing.” ArXiv.org. https://doi.org/10.48550/arxiv.quant-ph/0201117.

Harvard

Buhrman, H. et al. (2002) ‘Quantum Property Testing’, ArXiv.org. Available at: https://doi.org/10.48550/arxiv.quant-ph/0201117.

BibTeX

@misc{buhrman2002quantum,
  title = {{Quantum Property Testing}},
  author = {Buhrman, Harry and Fortnow, Lance and Newman, Ilan and Roehrig, Hein},
  journal = {ArXiv.org},
  year = {2002},
  doi = {10.48550/arxiv.quant-ph/0201117}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.