# A basic lower bound for property testing

arXiv: https://arxiv.org/abs/2403.04999 · HTML: https://mlsanity.com/paper/2403.04999/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2024.

## Built on by (most cited first, 1 of 1)

- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)

## Abstract (arXiv)

An ε-test for any non-trivial property (one for which there are both satisfying inputs and inputs of large distance from the property) should use a number of queries that is at least inversely proportional in ε. However, to the best of our knowledge there is no reference proof for this intuition. Such a proof is provided here. It is written so as to not require any prior knowledge of the related literature, and in particular does not use Yao's method.